Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/extern/recastnavigation/Recast/Source/Recast.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'extern/recastnavigation/Recast/Source/Recast.cpp')
-rw-r--r--extern/recastnavigation/Recast/Source/Recast.cpp335
1 files changed, 278 insertions, 57 deletions
diff --git a/extern/recastnavigation/Recast/Source/Recast.cpp b/extern/recastnavigation/Recast/Source/Recast.cpp
index 0db26c2c1cd..283cf0c128b 100644
--- a/extern/recastnavigation/Recast/Source/Recast.cpp
+++ b/extern/recastnavigation/Recast/Source/Recast.cpp
@@ -1,5 +1,5 @@
//
-// Copyright (c) 2009 Mikko Mononen memon@inside.org
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
//
// This software is provided 'as-is', without any express or implied
// warranty. In no event will the authors be held liable for any damages
@@ -22,35 +22,178 @@
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
+#include <stdarg.h>
#include "Recast.h"
-#include "RecastLog.h"
-#include "RecastTimer.h"
+#include "RecastAlloc.h"
+#include "RecastAssert.h"
+float rcSqrt(float x)
+{
+ return sqrtf(x);
+}
+
+/// @class rcContext
+/// @par
+///
+/// This class does not provide logging or timer functionality on its
+/// own. Both must be provided by a concrete implementation
+/// by overriding the protected member functions. Also, this class does not
+/// provide an interface for extracting log messages. (Only adding them.)
+/// So concrete implementations must provide one.
+///
+/// If no logging or timers are required, just pass an instance of this
+/// class through the Recast build process.
+///
-void rcIntArray::resize(int n)
+/// @par
+///
+/// Example:
+/// @code
+/// // Where ctx is an instance of rcContext and filepath is a char array.
+/// ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not load '%s'", filepath);
+/// @endcode
+void rcContext::log(const rcLogCategory category, const char* format, ...)
{
- if (n > m_cap)
+ if (!m_logEnabled)
+ return;
+ static const int MSG_SIZE = 512;
+ char msg[MSG_SIZE];
+ va_list ap;
+ va_start(ap, format);
+ int len = vsnprintf(msg, MSG_SIZE, format, ap);
+ if (len >= MSG_SIZE)
{
- if (!m_cap) m_cap = 8;
- while (m_cap < n) m_cap *= 2;
- int* newData = new int[m_cap];
- if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int));
- delete [] m_data;
- m_data = newData;
+ len = MSG_SIZE-1;
+ msg[MSG_SIZE-1] = '\0';
}
- m_size = n;
+ va_end(ap);
+ doLog(category, msg, len);
+}
+
+rcHeightfield* rcAllocHeightfield()
+{
+ rcHeightfield* hf = (rcHeightfield*)rcAlloc(sizeof(rcHeightfield), RC_ALLOC_PERM);
+ memset(hf, 0, sizeof(rcHeightfield));
+ return hf;
+}
+
+void rcFreeHeightField(rcHeightfield* hf)
+{
+ if (!hf) return;
+ // Delete span array.
+ rcFree(hf->spans);
+ // Delete span pools.
+ while (hf->pools)
+ {
+ rcSpanPool* next = hf->pools->next;
+ rcFree(hf->pools);
+ hf->pools = next;
+ }
+ rcFree(hf);
+}
+
+rcCompactHeightfield* rcAllocCompactHeightfield()
+{
+ rcCompactHeightfield* chf = (rcCompactHeightfield*)rcAlloc(sizeof(rcCompactHeightfield), RC_ALLOC_PERM);
+ memset(chf, 0, sizeof(rcCompactHeightfield));
+ return chf;
+}
+
+void rcFreeCompactHeightfield(rcCompactHeightfield* chf)
+{
+ if (!chf) return;
+ rcFree(chf->cells);
+ rcFree(chf->spans);
+ rcFree(chf->dist);
+ rcFree(chf->areas);
+ rcFree(chf);
+}
+
+
+rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet()
+{
+ rcHeightfieldLayerSet* lset = (rcHeightfieldLayerSet*)rcAlloc(sizeof(rcHeightfieldLayerSet), RC_ALLOC_PERM);
+ memset(lset, 0, sizeof(rcHeightfieldLayerSet));
+ return lset;
+}
+
+void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset)
+{
+ if (!lset) return;
+ for (int i = 0; i < lset->nlayers; ++i)
+ {
+ rcFree(lset->layers[i].heights);
+ rcFree(lset->layers[i].areas);
+ rcFree(lset->layers[i].cons);
+ }
+ rcFree(lset->layers);
+ rcFree(lset);
+}
+
+
+rcContourSet* rcAllocContourSet()
+{
+ rcContourSet* cset = (rcContourSet*)rcAlloc(sizeof(rcContourSet), RC_ALLOC_PERM);
+ memset(cset, 0, sizeof(rcContourSet));
+ return cset;
+}
+
+void rcFreeContourSet(rcContourSet* cset)
+{
+ if (!cset) return;
+ for (int i = 0; i < cset->nconts; ++i)
+ {
+ rcFree(cset->conts[i].verts);
+ rcFree(cset->conts[i].rverts);
+ }
+ rcFree(cset->conts);
+ rcFree(cset);
+}
+
+rcPolyMesh* rcAllocPolyMesh()
+{
+ rcPolyMesh* pmesh = (rcPolyMesh*)rcAlloc(sizeof(rcPolyMesh), RC_ALLOC_PERM);
+ memset(pmesh, 0, sizeof(rcPolyMesh));
+ return pmesh;
+}
+
+void rcFreePolyMesh(rcPolyMesh* pmesh)
+{
+ if (!pmesh) return;
+ rcFree(pmesh->verts);
+ rcFree(pmesh->polys);
+ rcFree(pmesh->regs);
+ rcFree(pmesh->flags);
+ rcFree(pmesh->areas);
+ rcFree(pmesh);
+}
+
+rcPolyMeshDetail* rcAllocPolyMeshDetail()
+{
+ rcPolyMeshDetail* dmesh = (rcPolyMeshDetail*)rcAlloc(sizeof(rcPolyMeshDetail), RC_ALLOC_PERM);
+ memset(dmesh, 0, sizeof(rcPolyMeshDetail));
+ return dmesh;
+}
+
+void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh)
+{
+ if (!dmesh) return;
+ rcFree(dmesh->meshes);
+ rcFree(dmesh->verts);
+ rcFree(dmesh->tris);
+ rcFree(dmesh);
}
void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax)
{
// Calculate bounding box.
- vcopy(bmin, verts);
- vcopy(bmax, verts);
+ rcVcopy(bmin, verts);
+ rcVcopy(bmax, verts);
for (int i = 1; i < nv; ++i)
{
const float* v = &verts[i*3];
- vmin(bmin, v);
- vmax(bmax, v);
+ rcVmin(bmin, v);
+ rcVmax(bmax, v);
}
}
@@ -60,17 +203,25 @@ void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int*
*h = (int)((bmax[2] - bmin[2])/cs+0.5f);
}
-bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
+/// @par
+///
+/// See the #rcConfig documentation for more information on the configuration parameters.
+///
+/// @see rcAllocHeightfield, rcHeightfield
+bool rcCreateHeightfield(rcContext* /*ctx*/, rcHeightfield& hf, int width, int height,
const float* bmin, const float* bmax,
float cs, float ch)
{
+ // TODO: VC complains about unref formal variable, figure out a way to handle this better.
+// rcAssert(ctx);
+
hf.width = width;
hf.height = height;
- hf.spans = new rcSpan*[hf.width*hf.height];
- vcopy(hf.bmin, bmin);
- vcopy(hf.bmax, bmax);
+ rcVcopy(hf.bmin, bmin);
+ rcVcopy(hf.bmax, bmax);
hf.cs = cs;
hf.ch = ch;
+ hf.spans = (rcSpan**)rcAlloc(sizeof(rcSpan*)*hf.width*hf.height, RC_ALLOC_PERM);
if (!hf.spans)
return false;
memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height);
@@ -80,18 +231,29 @@ bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
static void calcTriNormal(const float* v0, const float* v1, const float* v2, float* norm)
{
float e0[3], e1[3];
- vsub(e0, v1, v0);
- vsub(e1, v2, v0);
- vcross(norm, e0, e1);
- vnormalize(norm);
+ rcVsub(e0, v1, v0);
+ rcVsub(e1, v2, v0);
+ rcVcross(norm, e0, e1);
+ rcVnormalize(norm);
}
-void rcMarkWalkableTriangles(const float walkableSlopeAngle,
- const float* verts, int nv,
+/// @par
+///
+/// Only sets the aread id's for the walkable triangles. Does not alter the
+/// area id's for unwalkable triangles.
+///
+/// See the #rcConfig documentation for more information on the configuration parameters.
+///
+/// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
+void rcMarkWalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle,
+ const float* verts, int /*nv*/,
const int* tris, int nt,
- unsigned char* flags)
+ unsigned char* areas)
{
- const float walkableThr = cosf(walkableSlopeAngle/180.0f*(float)M_PI);
+ // TODO: VC complains about unref formal variable, figure out a way to handle this better.
+// rcAssert(ctx);
+
+ const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
float norm[3];
@@ -101,12 +263,45 @@ void rcMarkWalkableTriangles(const float walkableSlopeAngle,
calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
// Check if the face is walkable.
if (norm[1] > walkableThr)
- flags[i] |= RC_WALKABLE;
+ areas[i] = RC_WALKABLE_AREA;
+ }
+}
+
+/// @par
+///
+/// Only sets the aread id's for the unwalkable triangles. Does not alter the
+/// area id's for walkable triangles.
+///
+/// See the #rcConfig documentation for more information on the configuration parameters.
+///
+/// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
+void rcClearUnwalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle,
+ const float* verts, int /*nv*/,
+ const int* tris, int nt,
+ unsigned char* areas)
+{
+ // TODO: VC complains about unref formal variable, figure out a way to handle this better.
+// rcAssert(ctx);
+
+ const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
+
+ float norm[3];
+
+ for (int i = 0; i < nt; ++i)
+ {
+ const int* tri = &tris[i*3];
+ calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
+ // Check if the face is walkable.
+ if (norm[1] <= walkableThr)
+ areas[i] = RC_NULL_AREA;
}
}
-static int getSpanCount(unsigned char flags, rcHeightfield& hf)
+int rcGetHeightFieldSpanCount(rcContext* /*ctx*/, rcHeightfield& hf)
{
+ // TODO: VC complains about unref formal variable, figure out a way to handle this better.
+// rcAssert(ctx);
+
const int w = hf.width;
const int h = hf.height;
int spanCount = 0;
@@ -116,7 +311,7 @@ static int getSpanCount(unsigned char flags, rcHeightfield& hf)
{
for (rcSpan* s = hf.spans[x + y*w]; s; s = s->next)
{
- if (s->flags == flags)
+ if (s->area != RC_NULL_AREA)
spanCount++;
}
}
@@ -124,21 +319,25 @@ static int getSpanCount(unsigned char flags, rcHeightfield& hf)
return spanCount;
}
-inline void setCon(rcCompactSpan& s, int dir, int i)
-{
- s.con &= ~(0xf << (dir*4));
- s.con |= (i&0xf) << (dir*4);
-}
-
-bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb,
- unsigned char flags, rcHeightfield& hf,
- rcCompactHeightfield& chf)
+/// @par
+///
+/// This is just the beginning of the process of fully building a compact heightfield.
+/// Various filters may be applied applied, then the distance field and regions built.
+/// E.g: #rcBuildDistanceField and #rcBuildRegions
+///
+/// See the #rcConfig documentation for more information on the configuration parameters.
+///
+/// @see rcAllocCompactHeightfield, rcHeightfield, rcCompactHeightfield, rcConfig
+bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,
+ rcHeightfield& hf, rcCompactHeightfield& chf)
{
- rcTimeVal startTime = rcGetPerformanceTimer();
+ rcAssert(ctx);
+
+ ctx->startTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD);
const int w = hf.width;
const int h = hf.height;
- const int spanCount = getSpanCount(flags, hf);
+ const int spanCount = rcGetHeightFieldSpanCount(ctx, hf);
// Fill in header.
chf.width = w;
@@ -147,27 +346,32 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
chf.walkableHeight = walkableHeight;
chf.walkableClimb = walkableClimb;
chf.maxRegions = 0;
- vcopy(chf.bmin, hf.bmin);
- vcopy(chf.bmax, hf.bmax);
+ rcVcopy(chf.bmin, hf.bmin);
+ rcVcopy(chf.bmax, hf.bmax);
chf.bmax[1] += walkableHeight*hf.ch;
chf.cs = hf.cs;
chf.ch = hf.ch;
- chf.cells = new rcCompactCell[w*h];
+ chf.cells = (rcCompactCell*)rcAlloc(sizeof(rcCompactCell)*w*h, RC_ALLOC_PERM);
if (!chf.cells)
{
- if (rcGetLog())
- rcGetLog()->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
+ ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
return false;
}
memset(chf.cells, 0, sizeof(rcCompactCell)*w*h);
- chf.spans = new rcCompactSpan[spanCount];
+ chf.spans = (rcCompactSpan*)rcAlloc(sizeof(rcCompactSpan)*spanCount, RC_ALLOC_PERM);
if (!chf.spans)
{
- if (rcGetLog())
- rcGetLog()->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
+ ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
return false;
}
memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount);
+ chf.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*spanCount, RC_ALLOC_PERM);
+ if (!chf.areas)
+ {
+ ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.areas' (%d)", spanCount);
+ return false;
+ }
+ memset(chf.areas, RC_NULL_AREA, sizeof(unsigned char)*spanCount);
const int MAX_HEIGHT = 0xffff;
@@ -185,12 +389,13 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
c.count = 0;
while (s)
{
- if (s->flags == flags)
+ if (s->area != RC_NULL_AREA)
{
const int bot = (int)s->smax;
const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
+ chf.areas[idx] = s->area;
idx++;
c.count++;
}
@@ -200,6 +405,8 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
}
// Find neighbour connections.
+ const int MAX_LAYERS = RC_NOT_CONNECTED-1;
+ int tooHighNeighbour = 0;
for (int y = 0; y < h; ++y)
{
for (int x = 0; x < w; ++x)
@@ -208,14 +415,16 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
{
rcCompactSpan& s = chf.spans[i];
+
for (int dir = 0; dir < 4; ++dir)
{
- setCon(s, dir, 0xf);
+ rcSetCon(s, dir, RC_NOT_CONNECTED);
const int nx = x + rcGetDirOffsetX(dir);
const int ny = y + rcGetDirOffsetY(dir);
// First check that the neighbour cell is in bounds.
if (nx < 0 || ny < 0 || nx >= w || ny >= h)
continue;
+
// Iterate over all neighbour spans and check if any of the is
// accessible from current cell.
const rcCompactCell& nc = chf.cells[nx+ny*w];
@@ -230,23 +439,34 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb)
{
// Mark direction as walkable.
- setCon(s, dir, k - (int)nc.index);
+ const int idx = k - (int)nc.index;
+ if (idx < 0 || idx > MAX_LAYERS)
+ {
+ tooHighNeighbour = rcMax(tooHighNeighbour, idx);
+ continue;
+ }
+ rcSetCon(s, dir, idx);
break;
}
}
+
}
}
}
}
- rcTimeVal endTime = rcGetPerformanceTimer();
-
- if (rcGetBuildTimes())
- rcGetBuildTimes()->buildCompact += rcGetDeltaTimeUsec(startTime, endTime);
+ if (tooHighNeighbour > MAX_LAYERS)
+ {
+ ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Heightfield has too many layers %d (max: %d)",
+ tooHighNeighbour, MAX_LAYERS);
+ }
+
+ ctx->stopTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD);
return true;
}
+/*
static int getHeightfieldMemoryUsage(const rcHeightfield& hf)
{
int size = 0;
@@ -270,3 +490,4 @@ static int getCompactHeightFieldMemoryusage(const rcCompactHeightfield& chf)
size += sizeof(rcCompactCell) * chf.width * chf.height;
return size;
}
+*/ \ No newline at end of file
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-22 02:24:23 +0300