aboutsummaryrefslogtreecommitdiff
path: root/dep/recastnavigation/Recast/RecastMeshDetail.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'dep/recastnavigation/Recast/RecastMeshDetail.cpp')
-rw-r--r--dep/recastnavigation/Recast/RecastMeshDetail.cpp123
1 files changed, 99 insertions, 24 deletions
diff --git a/dep/recastnavigation/Recast/RecastMeshDetail.cpp b/dep/recastnavigation/Recast/RecastMeshDetail.cpp
index 77a085c5c2b..8325b883707 100644
--- a/dep/recastnavigation/Recast/RecastMeshDetail.cpp
+++ b/dep/recastnavigation/Recast/RecastMeshDetail.cpp
@@ -200,8 +200,8 @@ static unsigned short getHeight(const float fx, const float fy, const float fz,
{
int ix = (int)floorf(fx*ics + 0.01f);
int iz = (int)floorf(fz*ics + 0.01f);
- ix = rcClamp(ix-hp.xmin, 0, hp.width);
- iz = rcClamp(iz-hp.ymin, 0, hp.height);
+ ix = rcClamp(ix-hp.xmin, 0, hp.width - 1);
+ iz = rcClamp(iz-hp.ymin, 0, hp.height - 1);
unsigned short h = hp.data[ix+iz*hp.width];
if (h == RC_UNSET_HEIGHT)
{
@@ -267,11 +267,11 @@ static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges,
int e = findEdge(edges, nedges, s, t);
if (e == UNDEF)
{
- int* e = &edges[nedges*4];
- e[0] = s;
- e[1] = t;
- e[2] = l;
- e[3] = r;
+ int* edge = &edges[nedges*4];
+ edge[0] = s;
+ edge[1] = t;
+ edge[2] = l;
+ edge[3] = r;
return nedges++;
}
else
@@ -583,10 +583,10 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
int maxi = -1;
for (int m = a+1; m < b; ++m)
{
- float d = distancePtSeg(&edge[m*3],va,vb);
- if (d > maxd)
+ float dev = distancePtSeg(&edge[m*3],va,vb);
+ if (dev > maxd)
{
- maxd = d;
+ maxd = dev;
maxi = m;
}
}
@@ -741,9 +741,10 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
return true;
}
-static void getHeightData(const rcCompactHeightfield& chf,
+
+static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
const unsigned short* poly, const int npoly,
- const unsigned short* verts,
+ const unsigned short* verts, const int bs,
rcHeightPatch& hp, rcIntArray& stack)
{
// Floodfill the heightfield to get 2D height data,
@@ -775,7 +776,7 @@ static void getHeightData(const rcCompactHeightfield& chf,
az < hp.ymin || az >= hp.ymin+hp.height)
continue;
- const rcCompactCell& c = chf.cells[ax+az*chf.width];
+ const rcCompactCell& c = chf.cells[(ax+bs)+(az+bs)*chf.width];
for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
{
const rcCompactSpan& s = chf.spans[i];
@@ -847,7 +848,7 @@ static void getHeightData(const rcCompactHeightfield& chf,
if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != 0)
continue;
- const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(cs, dir);
+ const int ai = (int)chf.cells[(ax+bs)+(ay+bs)*chf.width].index + rcGetCon(cs, dir);
int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width;
hp.data[idx] = 1;
@@ -869,8 +870,83 @@ static void getHeightData(const rcCompactHeightfield& chf,
int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width;
const rcCompactSpan& cs = chf.spans[ci];
hp.data[idx] = cs.y;
+
+ // getHeightData seeds are given in coordinates with borders
+ stack[i+0] += bs;
+ stack[i+1] += bs;
}
+}
+
+
+
+static void getHeightData(const rcCompactHeightfield& chf,
+ const unsigned short* poly, const int npoly,
+ const unsigned short* verts, const int bs,
+ rcHeightPatch& hp, rcIntArray& stack,
+ int region)
+{
+ // Note: Reads to the compact heightfield are offset by border size (bs)
+ // since border size offset is already removed from the polymesh vertices.
+
+ stack.resize(0);
+ memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
+
+ bool empty = true;
+
+ // Copy the height from the same region, and mark region borders
+ // as seed points to fill the rest.
+ for (int hy = 0; hy < hp.height; hy++)
+ {
+ int y = hp.ymin + hy + bs;
+ for (int hx = 0; hx < hp.width; hx++)
+ {
+ int x = hp.xmin + hx + bs;
+ const rcCompactCell& c = chf.cells[x+y*chf.width];
+ for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+ {
+ const rcCompactSpan& s = chf.spans[i];
+ if (s.reg == region)
+ {
+ // Store height
+ hp.data[hx + hy*hp.width] = s.y;
+ empty = false;
+
+ // If any of the neighbours is not in same region,
+ // add the current location as flood fill start
+ bool border = false;
+ for (int dir = 0; dir < 4; ++dir)
+ {
+ if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
+ {
+ const int ax = x + rcGetDirOffsetX(dir);
+ const int ay = y + rcGetDirOffsetY(dir);
+ const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
+ const rcCompactSpan& as = chf.spans[ai];
+ if (as.reg != region)
+ {
+ border = true;
+ break;
+ }
+ }
+ }
+ if (border)
+ {
+ stack.push(x);
+ stack.push(y);
+ stack.push(i);
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ // if the polygon does not contian any points from the current region (rare, but happens)
+ // then use the cells closest to the polygon vertices as seeds to fill the height field
+ if (empty)
+ getHeightDataSeedsFromVertices(chf, poly, npoly, verts, bs, hp, stack);
+
static const int RETRACT_SIZE = 256;
int head = 0;
@@ -895,26 +971,25 @@ static void getHeightData(const rcCompactHeightfield& chf,
const int ax = cx + rcGetDirOffsetX(dir);
const int ay = cy + rcGetDirOffsetY(dir);
+ const int hx = ax - hp.xmin - bs;
+ const int hy = ay - hp.ymin - bs;
- if (ax < hp.xmin || ax >= (hp.xmin+hp.width) ||
- ay < hp.ymin || ay >= (hp.ymin+hp.height))
+ if (hx < 0 || hx >= hp.width || hy < 0 || hy >= hp.height)
continue;
- if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != RC_UNSET_HEIGHT)
+ if (hp.data[hx + hy*hp.width] != RC_UNSET_HEIGHT)
continue;
- const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(cs, dir);
-
+ const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(cs, dir);
const rcCompactSpan& as = chf.spans[ai];
- int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width;
- hp.data[idx] = as.y;
+
+ hp.data[hx + hy*hp.width] = as.y;
stack.push(ax);
stack.push(ay);
stack.push(ai);
}
}
-
}
static unsigned char getEdgeFlags(const float* va, const float* vb,
@@ -961,6 +1036,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
const float cs = mesh.cs;
const float ch = mesh.ch;
const float* orig = mesh.bmin;
+ const int borderSize = mesh.borderSize;
rcIntArray edges(64);
rcIntArray tris(512);
@@ -1071,7 +1147,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
hp.ymin = bounds[i*4+2];
hp.width = bounds[i*4+1]-bounds[i*4+0];
hp.height = bounds[i*4+3]-bounds[i*4+2];
- getHeightData(chf, p, npoly, mesh.verts, hp, stack);
+ getHeightData(chf, p, npoly, mesh.verts, borderSize, hp, stack, mesh.regs[i]);
// Build detail mesh.
int nverts = 0;
@@ -1241,4 +1317,3 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
return true;
}
-