aboutsummaryrefslogtreecommitdiff
path: root/dep/recastnavigation/Recast/RecastMesh.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'dep/recastnavigation/Recast/RecastMesh.cpp')
-rw-r--r--dep/recastnavigation/Recast/RecastMesh.cpp170
1 files changed, 157 insertions, 13 deletions
diff --git a/dep/recastnavigation/Recast/RecastMesh.cpp b/dep/recastnavigation/Recast/RecastMesh.cpp
index 088b67aafd3..8af609b79fb 100644
--- a/dep/recastnavigation/Recast/RecastMesh.cpp
+++ b/dep/recastnavigation/Recast/RecastMesh.cpp
@@ -59,6 +59,7 @@ static bool buildMeshAdjacency(unsigned short* polys, const int npolys,
unsigned short* t = &polys[i*vertsPerPoly*2];
for (int j = 0; j < vertsPerPoly; ++j)
{
+ if (t[j] == RC_MESH_NULL_IDX) break;
unsigned short v0 = t[j];
unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
if (v0 < v1)
@@ -83,6 +84,7 @@ static bool buildMeshAdjacency(unsigned short* polys, const int npolys,
unsigned short* t = &polys[i*vertsPerPoly*2];
for (int j = 0; j < vertsPerPoly; ++j)
{
+ if (t[j] == RC_MESH_NULL_IDX) break;
unsigned short v0 = t[j];
unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
if (v0 > v1)
@@ -195,7 +197,7 @@ inline bool collinear(const int* a, const int* b, const int* c)
// Returns true iff ab properly intersects cd: they share
// a point interior to both segments. The properness of the
// intersection is ensured by using strict leftness.
-bool intersectProp(const int* a, const int* b, const int* c, const int* d)
+static bool intersectProp(const int* a, const int* b, const int* c, const int* d)
{
// Eliminate improper cases.
if (collinear(a,b,c) || collinear(a,b,d) ||
@@ -548,9 +550,9 @@ static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned sho
// Check if the edge exists
bool exists = false;
- for (int k = 0; k < nedges; ++k)
+ for (int m = 0; m < nedges; ++m)
{
- int* e = &edges[k*3];
+ int* e = &edges[m*3];
if (e[1] == b)
{
// Exists, increment vertex share count.
@@ -659,7 +661,8 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short
}
// Remove the polygon.
unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*nvp*2];
- memcpy(p,p2,sizeof(unsigned short)*nvp);
+ if (p != p2)
+ memcpy(p,p2,sizeof(unsigned short)*nvp);
memset(p+nvp,0xff,sizeof(unsigned short)*nvp);
mesh.regs[i] = mesh.regs[mesh.npolys-1];
mesh.areas[i] = mesh.areas[mesh.npolys-1];
@@ -859,7 +862,9 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short
unsigned short* pa = &polys[bestPa*nvp];
unsigned short* pb = &polys[bestPb*nvp];
mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp);
- memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*nvp);
+ unsigned short* last = &polys[(npolys-1)*nvp];
+ if (pb != last)
+ memcpy(pb, last, sizeof(unsigned short)*nvp);
pregs[bestPb] = pregs[npolys-1];
pareas[bestPb] = pareas[npolys-1];
npolys--;
@@ -893,8 +898,13 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short
return true;
}
-
-bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& mesh)
+/// @par
+///
+/// @note If the mesh data is to be used to construct a Detour navigation mesh, then the upper
+/// limit must be retricted to <= #DT_VERTS_PER_POLYGON.
+///
+/// @see rcAllocPolyMesh, rcContourSet, rcPolyMesh, rcConfig
+bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh)
{
rcAssert(ctx);
@@ -904,6 +914,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& me
rcVcopy(mesh.bmax, cset.bmax);
mesh.cs = cset.cs;
mesh.ch = cset.ch;
+ mesh.borderSize = cset.borderSize;
int maxVertices = 0;
int maxTris = 0;
@@ -926,7 +937,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& me
rcScopedDelete<unsigned char> vflags = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP);
if (!vflags)
{
- ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
+ ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'vflags' (%d).", maxVertices);
return false;
}
memset(vflags, 0, maxVertices);
@@ -937,7 +948,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& me
ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
return false;
}
- mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2*2, RC_ALLOC_PERM);
+ mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2, RC_ALLOC_PERM);
if (!mesh.polys)
{
ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2);
@@ -1097,7 +1108,9 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& me
unsigned short* pa = &polys[bestPa*nvp];
unsigned short* pb = &polys[bestPb*nvp];
mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp);
- memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*nvp);
+ unsigned short* lastPoly = &polys[(npolys-1)*nvp];
+ if (pb != lastPoly)
+ memcpy(pb, lastPoly, sizeof(unsigned short)*nvp);
npolys--;
}
else
@@ -1155,6 +1168,37 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& me
ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Adjacency failed.");
return false;
}
+
+ // Find portal edges
+ if (mesh.borderSize > 0)
+ {
+ const int w = cset.width;
+ const int h = cset.height;
+ for (int i = 0; i < mesh.npolys; ++i)
+ {
+ unsigned short* p = &mesh.polys[i*2*nvp];
+ for (int j = 0; j < nvp; ++j)
+ {
+ if (p[j] == RC_MESH_NULL_IDX) break;
+ // Skip connected edges.
+ if (p[nvp+j] != RC_MESH_NULL_IDX)
+ continue;
+ int nj = j+1;
+ if (nj >= nvp || p[nj] == RC_MESH_NULL_IDX) nj = 0;
+ const unsigned short* va = &mesh.verts[p[j]*3];
+ const unsigned short* vb = &mesh.verts[p[nj]*3];
+
+ if ((int)va[0] == 0 && (int)vb[0] == 0)
+ p[nvp+j] = 0x8000 | 0;
+ else if ((int)va[2] == h && (int)vb[2] == h)
+ p[nvp+j] = 0x8000 | 1;
+ else if ((int)va[0] == w && (int)vb[0] == w)
+ p[nvp+j] = 0x8000 | 2;
+ else if ((int)va[2] == 0 && (int)vb[2] == 0)
+ p[nvp+j] = 0x8000 | 3;
+ }
+ }
+ }
// Just allocate the mesh flags array. The user is resposible to fill it.
mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*mesh.npolys, RC_ALLOC_PERM);
@@ -1167,11 +1211,11 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& me
if (mesh.nverts > 0xffff)
{
- ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
+ ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
}
if (mesh.npolys > 0xffff)
{
- ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
+ ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
}
ctx->stopTimer(RC_TIMER_BUILD_POLYMESH);
@@ -1271,7 +1315,7 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r
ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'vremap' (%d).", maxVertsPerMesh);
return false;
}
- memset(nextVert, 0, sizeof(int)*maxVerts);
+ memset(vremap, 0, sizeof(unsigned short)*maxVertsPerMesh);
for (int i = 0; i < nmeshes; ++i)
{
@@ -1280,6 +1324,12 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r
const unsigned short ox = (unsigned short)floorf((pmesh->bmin[0]-mesh.bmin[0])/mesh.cs+0.5f);
const unsigned short oz = (unsigned short)floorf((pmesh->bmin[2]-mesh.bmin[2])/mesh.cs+0.5f);
+ bool isMinX = (ox == 0);
+ bool isMinZ = (oz == 0);
+ bool isMaxX = ((unsigned short)floorf((mesh.bmax[0] - pmesh->bmax[0]) / mesh.cs + 0.5f)) == 0;
+ bool isMaxZ = ((unsigned short)floorf((mesh.bmax[2] - pmesh->bmax[2]) / mesh.cs + 0.5f)) == 0;
+ bool isOnBorder = (isMinX || isMinZ || isMaxX || isMaxZ);
+
for (int j = 0; j < pmesh->nverts; ++j)
{
unsigned short* v = &pmesh->verts[j*3];
@@ -1300,6 +1350,36 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r
if (src[k] == RC_MESH_NULL_IDX) break;
tgt[k] = vremap[src[k]];
}
+
+ if (isOnBorder)
+ {
+ for (int k = mesh.nvp; k < mesh.nvp * 2; ++k)
+ {
+ if (src[k] & 0x8000 && src[k] != 0xffff)
+ {
+ unsigned short dir = src[k] & 0xf;
+ switch (dir)
+ {
+ case 0: // Portal x-
+ if (isMinX)
+ tgt[k] = src[k];
+ break;
+ case 1: // Portal z+
+ if (isMaxZ)
+ tgt[k] = src[k];
+ break;
+ case 2: // Portal x+
+ if (isMaxX)
+ tgt[k] = src[k];
+ break;
+ case 3: // Portal z-
+ if (isMinZ)
+ tgt[k] = src[k];
+ break;
+ }
+ }
+ }
+ }
}
}
@@ -1323,3 +1403,67 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r
return true;
}
+
+bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst)
+{
+ rcAssert(ctx);
+
+ // Destination must be empty.
+ rcAssert(dst.verts == 0);
+ rcAssert(dst.polys == 0);
+ rcAssert(dst.regs == 0);
+ rcAssert(dst.areas == 0);
+ rcAssert(dst.flags == 0);
+
+ dst.nverts = src.nverts;
+ dst.npolys = src.npolys;
+ dst.maxpolys = src.npolys;
+ dst.nvp = src.nvp;
+ rcVcopy(dst.bmin, src.bmin);
+ rcVcopy(dst.bmax, src.bmax);
+ dst.cs = src.cs;
+ dst.ch = src.ch;
+ dst.borderSize = src.borderSize;
+
+ dst.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.nverts*3, RC_ALLOC_PERM);
+ if (!dst.verts)
+ {
+ ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.verts' (%d).", src.nverts*3);
+ return false;
+ }
+ memcpy(dst.verts, src.verts, sizeof(unsigned short)*src.nverts*3);
+
+ dst.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys*2*src.nvp, RC_ALLOC_PERM);
+ if (!dst.polys)
+ {
+ ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.polys' (%d).", src.npolys*2*src.nvp);
+ return false;
+ }
+ memcpy(dst.polys, src.polys, sizeof(unsigned short)*src.npolys*2*src.nvp);
+
+ dst.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM);
+ if (!dst.regs)
+ {
+ ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.regs' (%d).", src.npolys);
+ return false;
+ }
+ memcpy(dst.regs, src.regs, sizeof(unsigned short)*src.npolys);
+
+ dst.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*src.npolys, RC_ALLOC_PERM);
+ if (!dst.areas)
+ {
+ ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.areas' (%d).", src.npolys);
+ return false;
+ }
+ memcpy(dst.areas, src.areas, sizeof(unsigned char)*src.npolys);
+
+ dst.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM);
+ if (!dst.flags)
+ {
+ ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.flags' (%d).", src.npolys);
+ return false;
+ }
+ memcpy(dst.flags, src.flags, sizeof(unsigned char)*src.npolys);
+
+ return true;
+}