diff options
Diffstat (limited to 'extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp')
| -rw-r--r-- | extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp | 681 |
1 files changed, 450 insertions, 231 deletions
diff --git a/extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp b/extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp index b52da597675..f1270cf2027 100644 --- a/extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp +++ b/extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp @@ -37,11 +37,12 @@ struct rcHeightPatch int xmin, ymin, width, height; }; + inline float vdot2(const float* a, const float* b) { return a[0]*b[0] + a[2]*b[2]; } - + inline float vdistSq2(const float* p, const float* q) { const float dx = q[0] - p[0]; @@ -55,7 +56,7 @@ inline float vdist2(const float* p, const float* q) } inline float vcross2(const float* p1, const float* p2, const float* p3) -{ +{ const float u1 = p2[0] - p1[0]; const float v1 = p2[2] - p1[2]; const float u2 = p3[0] - p1[0]; @@ -67,21 +68,27 @@ static bool circumCircle(const float* p1, const float* p2, const float* p3, float* c, float& r) { static const float EPS = 1e-6f; + // Calculate the circle relative to p1, to avoid some precision issues. + const float v1[3] = {0,0,0}; + float v2[3], v3[3]; + rcVsub(v2, p2,p1); + rcVsub(v3, p3,p1); - const float cp = vcross2(p1, p2, p3); + const float cp = vcross2(v1, v2, v3); if (fabsf(cp) > EPS) { - const float p1Sq = vdot2(p1,p1); - const float p2Sq = vdot2(p2,p2); - const float p3Sq = vdot2(p3,p3); - c[0] = (p1Sq*(p2[2]-p3[2]) + p2Sq*(p3[2]-p1[2]) + p3Sq*(p1[2]-p2[2])) / (2*cp); - c[2] = (p1Sq*(p3[0]-p2[0]) + p2Sq*(p1[0]-p3[0]) + p3Sq*(p2[0]-p1[0])) / (2*cp); - r = vdist2(c, p1); + const float v1Sq = vdot2(v1,v1); + const float v2Sq = vdot2(v2,v2); + const float v3Sq = vdot2(v3,v3); + c[0] = (v1Sq*(v2[2]-v3[2]) + v2Sq*(v3[2]-v1[2]) + v3Sq*(v1[2]-v2[2])) / (2*cp); + c[1] = 0; + c[2] = (v1Sq*(v3[0]-v2[0]) + v2Sq*(v1[0]-v3[0]) + v3Sq*(v2[0]-v1[0])) / (2*cp); + r = vdist2(c, v1); + rcVadd(c, c, p1); return true; } - - c[0] = p1[0]; - c[2] = p1[2]; + + rcVcopy(c, p1); r = 0; return false; } @@ -92,7 +99,7 @@ static float distPtTri(const float* p, const float* a, const float* b, const flo rcVsub(v0, c,a); rcVsub(v1, b,a); rcVsub(v2, p,a); - + const float dot00 = vdot2(v0, v0); const float dot01 = vdot2(v0, v1); const float dot02 = vdot2(v0, v2); @@ -177,7 +184,7 @@ static float distToTriMesh(const float* p, const float* verts, const int /*nvert static float distToPoly(int nvert, const float* verts, const float* p) { - + float dmin = FLT_MAX; int i, j, c = 0; for (i = 0, j = nvert-1; i < nvert; j = i++) @@ -195,42 +202,79 @@ static float distToPoly(int nvert, const float* verts, const float* p) static unsigned short getHeight(const float fx, const float fy, const float fz, const float /*cs*/, const float ics, const float ch, - const rcHeightPatch& hp) + const int radius, const rcHeightPatch& hp) { 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) { // Special case when data might be bad. - // Find nearest neighbour pixel which has valid height. - const int off[8*2] = { -1,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1}; + // Walk adjacent cells in a spiral up to 'radius', and look + // for a pixel which has a valid height. + int x = 1, z = 0, dx = 1, dz = 0; + int maxSize = radius * 2 + 1; + int maxIter = maxSize * maxSize - 1; + + int nextRingIterStart = 8; + int nextRingIters = 16; + float dmin = FLT_MAX; - for (int i = 0; i < 8; ++i) + for (int i = 0; i < maxIter; i++) { - const int nx = ix+off[i*2+0]; - const int nz = iz+off[i*2+1]; - if (nx < 0 || nz < 0 || nx >= hp.width || nz >= hp.height) continue; - const unsigned short nh = hp.data[nx+nz*hp.width]; - if (nh == RC_UNSET_HEIGHT) continue; + const int nx = ix + x; + const int nz = iz + z; + + if (nx >= 0 && nz >= 0 && nx < hp.width && nz < hp.height) + { + const unsigned short nh = hp.data[nx + nz*hp.width]; + if (nh != RC_UNSET_HEIGHT) + { + const float d = fabsf(nh*ch - fy); + if (d < dmin) + { + h = nh; + dmin = d; + } + } + } - const float d = fabsf(nh*ch - fy); - if (d < dmin) + // We are searching in a grid which looks approximately like this: + // __________ + // |2 ______ 2| + // | |1 __ 1| | + // | | |__| | | + // | |______| | + // |__________| + // We want to find the best height as close to the center cell as possible. This means that + // if we find a height in one of the neighbor cells to the center, we don't want to + // expand further out than the 8 neighbors - we want to limit our search to the closest + // of these "rings", but the best height in the ring. + // For example, the center is just 1 cell. We checked that at the entrance to the function. + // The next "ring" contains 8 cells (marked 1 above). Those are all the neighbors to the center cell. + // The next one again contains 16 cells (marked 2). In general each ring has 8 additional cells, which + // can be thought of as adding 2 cells around the "center" of each side when we expand the ring. + // Here we detect if we are about to enter the next ring, and if we are and we have found + // a height, we abort the search. + if (i + 1 == nextRingIterStart) { - h = nh; - dmin = d; + if (h != RC_UNSET_HEIGHT) + break; + + nextRingIterStart += nextRingIters; + nextRingIters += 8; } - -/* const float dx = (nx+0.5f)*cs - fx; - const float dz = (nz+0.5f)*cs - fz; - const float d = dx*dx+dz*dz; - if (d < dmin) + + if ((x == z) || ((x < 0) && (x == -z)) || ((x > 0) && (x == 1 - z))) { - h = nh; - dmin = d; - } */ + int tmp = dx; + dx = -dz; + dz = tmp; + } + x += dx; + z += dz; } } return h; @@ -239,8 +283,8 @@ static unsigned short getHeight(const float fx, const float fy, const float fz, enum EdgeValues { - UNDEF = -1, - HULL = -2, + EV_UNDEF = -1, + EV_HULL = -2, }; static int findEdge(const int* edges, int nedges, int s, int t) @@ -251,7 +295,7 @@ static int findEdge(const int* edges, int nedges, int s, int t) if ((e[0] == s && e[1] == t) || (e[0] == t && e[1] == s)) return i; } - return UNDEF; + return EV_UNDEF; } static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, int s, int t, int l, int r) @@ -259,33 +303,33 @@ static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, if (nedges >= maxEdges) { ctx->log(RC_LOG_ERROR, "addEdge: Too many edges (%d/%d).", nedges, maxEdges); - return UNDEF; + return EV_UNDEF; } - // Add edge if not already in the triangulation. + // Add edge if not already in the triangulation. int e = findEdge(edges, nedges, s, t); - if (e == UNDEF) + if (e == EV_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 { - return UNDEF; + return EV_UNDEF; } } static void updateLeftFace(int* e, int s, int t, int f) { - if (e[0] == s && e[1] == t && e[2] == UNDEF) + if (e[0] == s && e[1] == t && e[2] == EV_UNDEF) e[2] = f; - else if (e[1] == s && e[0] == t && e[3] == UNDEF) + else if (e[1] == s && e[0] == t && e[3] == EV_UNDEF) e[3] = f; -} +} static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d) { @@ -297,7 +341,7 @@ static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float a4 = a3 + a2 - a1; if (a3 * a4 < 0.0f) return 1; - } + } return 0; } @@ -319,28 +363,28 @@ static bool overlapEdges(const float* pts, const int* edges, int nedges, int s1, static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e) { static const float EPS = 1e-5f; - + int* edge = &edges[e*4]; // Cache s and t. int s,t; - if (edge[2] == UNDEF) + if (edge[2] == EV_UNDEF) { s = edge[0]; t = edge[1]; } - else if (edge[3] == UNDEF) + else if (edge[3] == EV_UNDEF) { s = edge[1]; t = edge[0]; } else { - // Edge already completed. + // Edge already completed. return; } - // Find best point on left of edge. + // Find best point on left of edge. int pt = npts; float c[3] = {0,0,0}; float r = -1; @@ -384,23 +428,23 @@ static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges } } - // Add new triangle or update edge info if s-t is on hull. + // Add new triangle or update edge info if s-t is on hull. if (pt < npts) { - // Update face information of edge being completed. + // Update face information of edge being completed. updateLeftFace(&edges[e*4], s, t, nfaces); - // Add new edge or update face info of old edge. + // Add new edge or update face info of old edge. e = findEdge(edges, nedges, pt, s); - if (e == UNDEF) - addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, UNDEF); + if (e == EV_UNDEF) + addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, EV_UNDEF); else updateLeftFace(&edges[e*4], pt, s, nfaces); - // Add new edge or update face info of old edge. + // Add new edge or update face info of old edge. e = findEdge(edges, nedges, t, pt); - if (e == UNDEF) - addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, UNDEF); + if (e == EV_UNDEF) + addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, EV_UNDEF); else updateLeftFace(&edges[e*4], t, pt, nfaces); @@ -408,7 +452,7 @@ static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges } else { - updateLeftFace(&edges[e*4], s, t, HULL); + updateLeftFace(&edges[e*4], s, t, EV_HULL); } } @@ -422,18 +466,18 @@ static void delaunayHull(rcContext* ctx, const int npts, const float* pts, edges.resize(maxEdges*4); for (int i = 0, j = nhull-1; i < nhull; j=i++) - addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], HULL, UNDEF); + addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], EV_HULL, EV_UNDEF); int currentEdge = 0; while (currentEdge < nedges) { - if (edges[currentEdge*4+2] == UNDEF) + if (edges[currentEdge*4+2] == EV_UNDEF) completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge); - if (edges[currentEdge*4+3] == UNDEF) + if (edges[currentEdge*4+3] == EV_UNDEF) completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge); currentEdge++; } - + // Create tris tris.resize(nfaces*4); for (int i = 0; i < nfaces*4; ++i) @@ -488,6 +532,97 @@ static void delaunayHull(rcContext* ctx, const int npts, const float* pts, } } +// Calculate minimum extend of the polygon. +static float polyMinExtent(const float* verts, const int nverts) +{ + float minDist = FLT_MAX; + for (int i = 0; i < nverts; i++) + { + const int ni = (i+1) % nverts; + const float* p1 = &verts[i*3]; + const float* p2 = &verts[ni*3]; + float maxEdgeDist = 0; + for (int j = 0; j < nverts; j++) + { + if (j == i || j == ni) continue; + float d = distancePtSeg2d(&verts[j*3], p1,p2); + maxEdgeDist = rcMax(maxEdgeDist, d); + } + minDist = rcMin(minDist, maxEdgeDist); + } + return rcSqrt(minDist); +} + +// Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv). +inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; } +inline int next(int i, int n) { return i+1 < n ? i+1 : 0; } + +static void triangulateHull(const int /*nverts*/, const float* verts, const int nhull, const int* hull, rcIntArray& tris) +{ + int start = 0, left = 1, right = nhull-1; + + // Start from an ear with shortest perimeter. + // This tends to favor well formed triangles as starting point. + float dmin = 0; + for (int i = 0; i < nhull; i++) + { + int pi = prev(i, nhull); + int ni = next(i, nhull); + const float* pv = &verts[hull[pi]*3]; + const float* cv = &verts[hull[i]*3]; + const float* nv = &verts[hull[ni]*3]; + const float d = vdist2(pv,cv) + vdist2(cv,nv) + vdist2(nv,pv); + if (d < dmin) + { + start = i; + left = ni; + right = pi; + dmin = d; + } + } + + // Add first triangle + tris.push(hull[start]); + tris.push(hull[left]); + tris.push(hull[right]); + tris.push(0); + + // Triangulate the polygon by moving left or right, + // depending on which triangle has shorter perimeter. + // This heuristic was chose emprically, since it seems + // handle tesselated straight edges well. + while (next(left, nhull) != right) + { + // Check to see if se should advance left or right. + int nleft = next(left, nhull); + int nright = prev(right, nhull); + + const float* cvleft = &verts[hull[left]*3]; + const float* nvleft = &verts[hull[nleft]*3]; + const float* cvright = &verts[hull[right]*3]; + const float* nvright = &verts[hull[nright]*3]; + const float dleft = vdist2(cvleft, nvleft) + vdist2(nvleft, cvright); + const float dright = vdist2(cvright, nvright) + vdist2(cvleft, nvright); + + if (dleft < dright) + { + tris.push(hull[left]); + tris.push(hull[nleft]); + tris.push(hull[right]); + tris.push(0); + left = nleft; + } + else + { + tris.push(hull[left]); + tris.push(hull[nright]); + tris.push(hull[right]); + tris.push(0); + right = nright; + } + } +} + inline float getJitterX(const int i) { @@ -501,9 +636,9 @@ inline float getJitterY(const int i) static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, const float sampleDist, const float sampleMaxError, - const rcCompactHeightfield& chf, const rcHeightPatch& hp, - float* verts, int& nverts, rcIntArray& tris, - rcIntArray& edges, rcIntArray& samples) + const int heightSearchRadius, const rcCompactHeightfield& chf, + const rcHeightPatch& hp, float* verts, int& nverts, + rcIntArray& tris, rcIntArray& edges, rcIntArray& samples) { static const int MAX_VERTS = 127; static const int MAX_TRIS = 255; // Max tris for delaunay is 2n-2-k (n=num verts, k=num hull verts). @@ -511,16 +646,22 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, float edge[(MAX_VERTS_PER_EDGE+1)*3]; int hull[MAX_VERTS]; int nhull = 0; - + nverts = 0; - + for (int i = 0; i < nin; ++i) rcVcopy(&verts[i*3], &in[i*3]); nverts = nin; + edges.resize(0); + tris.resize(0); + const float cs = chf.cs; const float ics = 1.0f/cs; + // Calculate minimum extents of the polygon based on input data. + float minExtent = polyMinExtent(verts, nverts); + // Tessellate outlines. // This is done in separate pass in order to ensure // seamless height values across the ply boundaries. @@ -566,7 +707,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, pos[0] = vj[0] + dx*u; pos[1] = vj[1] + dy*u; pos[2] = vj[2] + dz*u; - pos[1] = getHeight(pos[0],pos[1],pos[2], cs, ics, chf.ch, hp)*chf.ch; + pos[1] = getHeight(pos[0],pos[1],pos[2], cs, ics, chf.ch, heightSearchRadius, hp)*chf.ch; } // Simplify samples. int idx[MAX_VERTS_PER_EDGE] = {0,nn}; @@ -579,23 +720,23 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, const float* vb = &edge[b*3]; // Find maximum deviation along the segment. float maxd = 0; - int i_max = -1; + 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; - i_max = m; + maxd = dev; + maxi = m; } } // If the max deviation is larger than accepted error, // add new point, else continue to next segment. - if (i_max != -1 && maxd > rcSqr(sampleMaxError)) + if (maxi != -1 && maxd > rcSqr(sampleMaxError)) { for (int m = nidx; m > k; --m) idx[m] = idx[m-1]; - idx[k+1] = i_max; + idx[k+1] = maxi; nidx++; } else @@ -627,27 +768,26 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, } } - + // If the polygon minimum extent is small (sliver or small triangle), do not try to add internal points. + if (minExtent < sampleDist*2) + { + triangulateHull(nverts, verts, nhull, hull, tris); + return true; + } + // Tessellate the base mesh. - edges.resize(0); - tris.resize(0); - - delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges); + // We're using the triangulateHull instead of delaunayHull as it tends to + // create a bit better triangulation for long thing triangles when there + // are no internal points. + triangulateHull(nverts, verts, nhull, hull, tris); if (tris.size() == 0) { // Could not triangulate the poly, make sure there is some valid data there. - ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon, adding default data."); - for (int i = 2; i < nverts; ++i) - { - tris.push(0); - tris.push(i-1); - tris.push(i); - tris.push(0); - } + ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon (%d verts).", nverts); return true; } - + if (sampleDist > 0) { // Create sample locations in a grid. @@ -675,12 +815,12 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, // Make sure the samples are not too close to the edges. if (distToPoly(nin,in,pt) > -sampleDist/2) continue; samples.push(x); - samples.push(getHeight(pt[0], pt[1], pt[2], cs, ics, chf.ch, hp)); + samples.push(getHeight(pt[0], pt[1], pt[2], cs, ics, chf.ch, heightSearchRadius, hp)); samples.push(z); samples.push(0); // Not added } } - + // Add the samples starting from the one that has the most // error. The procedure stops when all samples are added // or when the max error is within treshold. @@ -689,7 +829,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, { if (nverts >= MAX_VERTS) break; - + // Find sample with most error. float bestpt[3] = {0,0,0}; float bestd = 0; @@ -727,45 +867,38 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, edges.resize(0); tris.resize(0); delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges); - } + } } - + const int ntris = tris.size()/4; if (ntris > MAX_TRIS) { tris.resize(MAX_TRIS*4); ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Shrinking triangle count from %d to max %d.", ntris, MAX_TRIS); } - + return true; } -static void getHeightData(const rcCompactHeightfield& chf, - const unsigned short* poly, const int npoly, - const unsigned short* verts, const int bs, - rcHeightPatch& hp, rcIntArray& stack) +static void seedArrayWithPolyCenter(rcContext* ctx, const rcCompactHeightfield& chf, + const unsigned short* poly, const int npoly, + const unsigned short* verts, const int bs, + rcHeightPatch& hp, rcIntArray& array) { - // Floodfill the heightfield to get 2D height data, - // starting at vertex locations as seeds. - // Note: Reads to the compact heightfield are offset by border size (bs) // since border size offset is already removed from the polymesh vertices. - memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height); - - stack.resize(0); - static const int offset[9*2] = { 0,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1, -1,0, }; - // Use poly vertices as seed points for the flood fill. - for (int j = 0; j < npoly; ++j) + // Find cell closest to a poly vertex + int startCellX = 0, startCellY = 0, startSpanIndex = -1; + int dmin = RC_UNSET_HEIGHT; + for (int j = 0; j < npoly && dmin > 0; ++j) { - int cx = 0, cz = 0, ci =-1; - int dmin = RC_UNSET_HEIGHT; - for (int k = 0; k < 9; ++k) + for (int k = 0; k < 9 && dmin > 0; ++k) { const int ax = (int)verts[poly[j]*3+0] + offset[k*2+0]; const int ay = (int)verts[poly[j]*3+1]; @@ -775,118 +908,210 @@ static void getHeightData(const rcCompactHeightfield& chf, continue; 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) + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni && dmin > 0; ++i) { const rcCompactSpan& s = chf.spans[i]; int d = rcAbs(ay - (int)s.y); if (d < dmin) { - cx = ax; - cz = az; - ci = i; + startCellX = ax; + startCellY = az; + startSpanIndex = i; dmin = d; } } } - if (ci != -1) - { - stack.push(cx); - stack.push(cz); - stack.push(ci); - } } - // Find center of the polygon using flood fill. - int pcx = 0, pcz = 0; + rcAssert(startSpanIndex != -1); + // Find center of the polygon + int pcx = 0, pcy = 0; for (int j = 0; j < npoly; ++j) { pcx += (int)verts[poly[j]*3+0]; - pcz += (int)verts[poly[j]*3+2]; + pcy += (int)verts[poly[j]*3+2]; } pcx /= npoly; - pcz /= npoly; - - for (int i = 0; i < stack.size(); i += 3) - { - int cx = stack[i+0]; - int cy = stack[i+1]; - int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width; - hp.data[idx] = 1; - } + pcy /= npoly; - while (stack.size() > 0) + // Use seeds array as a stack for DFS + array.resize(0); + array.push(startCellX); + array.push(startCellY); + array.push(startSpanIndex); + + int dirs[] = { 0, 1, 2, 3 }; + memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height); + // DFS to move to the center. Note that we need a DFS here and can not just move + // directly towards the center without recording intermediate nodes, even though the polygons + // are convex. In very rare we can get stuck due to contour simplification if we do not + // record nodes. + int cx = -1, cy = -1, ci = -1; + while (true) { - int ci = stack.pop(); - int cy = stack.pop(); - int cx = stack.pop(); - - // Check if close to center of the polygon. - if (rcAbs(cx-pcx) <= 1 && rcAbs(cy-pcz) <= 1) + if (array.size() < 3) { - stack.resize(0); - stack.push(cx); - stack.push(cy); - stack.push(ci); + ctx->log(RC_LOG_WARNING, "Walk towards polygon center failed to reach center"); break; } - + + ci = array.pop(); + cy = array.pop(); + cx = array.pop(); + + if (cx == pcx && cy == pcy) + break; + + // If we are already at the correct X-position, prefer direction + // directly towards the center in the Y-axis; otherwise prefer + // direction in the X-axis + int directDir; + if (cx == pcx) + directDir = rcGetDirForOffset(0, pcy > cy ? 1 : -1); + else + directDir = rcGetDirForOffset(pcx > cx ? 1 : -1, 0); + + // Push the direct dir last so we start with this on next iteration + rcSwap(dirs[directDir], dirs[3]); + const rcCompactSpan& cs = chf.spans[ci]; - - for (int dir = 0; dir < 4; ++dir) + for (int i = 0; i < 4; i++) { - if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue; - - const int ax = cx + rcGetDirOffsetX(dir); - const int ay = cy + rcGetDirOffsetY(dir); - - if (ax < hp.xmin || ax >= (hp.xmin+hp.width) || - ay < hp.ymin || ay >= (hp.ymin+hp.height)) + int dir = dirs[i]; + if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue; - - if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != 0) + + int newX = cx + rcGetDirOffsetX(dir); + int newY = cy + rcGetDirOffsetY(dir); + + int hpx = newX - hp.xmin; + int hpy = newY - hp.ymin; + if (hpx < 0 || hpx >= hp.width || hpy < 0 || hpy >= hp.height) continue; - - 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; - - stack.push(ax); - stack.push(ay); - stack.push(ai); + if (hp.data[hpx+hpy*hp.width] != 0) + continue; + + hp.data[hpx+hpy*hp.width] = 1; + array.push(newX); + array.push(newY); + array.push((int)chf.cells[(newX+bs)+(newY+bs)*chf.width].index + rcGetCon(cs, dir)); } + + rcSwap(dirs[directDir], dirs[3]); } + array.resize(0); + // getHeightData seeds are given in coordinates with borders + array.push(cx+bs); + array.push(cy+bs); + array.push(ci); + memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height); + const rcCompactSpan& cs = chf.spans[ci]; + hp.data[cx-hp.xmin+(cy-hp.ymin)*hp.width] = cs.y; +} + - // Mark start locations. - for (int i = 0; i < stack.size(); i += 3) +static void push3(rcIntArray& queue, int v1, int v2, int v3) +{ + queue.resize(queue.size() + 3); + queue[queue.size() - 3] = v1; + queue[queue.size() - 2] = v2; + queue[queue.size() - 1] = v3; +} + +static void getHeightData(rcContext* ctx, const rcCompactHeightfield& chf, + const unsigned short* poly, const int npoly, + const unsigned short* verts, const int bs, + rcHeightPatch& hp, rcIntArray& queue, + 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. + + queue.resize(0); + // Set all heights to RC_UNSET_HEIGHT. + memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height); + + bool empty = true; + + // We cannot sample from this poly if it was created from polys + // of different regions. If it was then it could potentially be overlapping + // with polys of that region and the heights sampled here could be wrong. + if (region != RC_MULTIPLE_REGS) { - int cx = stack[i+0]; - int cy = stack[i+1]; - int ci = stack[i+2]; - int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width; - const rcCompactSpan& cs = chf.spans[ci]; - hp.data[idx] = cs.y; + // 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) + push3(queue, x, y, i); + break; + } + } + } + } } + // if the polygon does not contain any points from the current region (rare, but happens) + // or if it could potentially be overlapping polygons of the same region, + // then use the center as the seed point. + if (empty) + seedArrayWithPolyCenter(ctx, chf, poly, npoly, verts, bs, hp, queue); + static const int RETRACT_SIZE = 256; int head = 0; - while (head*3 < stack.size()) + // We assume the seed is centered in the polygon, so a BFS to collect + // height data will ensure we do not move onto overlapping polygons and + // sample wrong heights. + while (head*3 < queue.size()) { - int cx = stack[head*3+0]; - int cy = stack[head*3+1]; - int ci = stack[head*3+2]; + int cx = queue[head*3+0]; + int cy = queue[head*3+1]; + int ci = queue[head*3+2]; head++; if (head >= RETRACT_SIZE) { head = 0; - if (stack.size() > RETRACT_SIZE*3) - memmove(&stack[0], &stack[RETRACT_SIZE*3], sizeof(int)*(stack.size()-RETRACT_SIZE*3)); - stack.resize(stack.size()-RETRACT_SIZE*3); + if (queue.size() > RETRACT_SIZE*3) + memmove(&queue[0], &queue[RETRACT_SIZE*3], sizeof(int)*(queue.size()-RETRACT_SIZE*3)); + queue.resize(queue.size()-RETRACT_SIZE*3); } - + const rcCompactSpan& cs = chf.spans[ci]; for (int dir = 0; dir < 4; ++dir) { @@ -894,26 +1119,23 @@ 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 ((unsigned int)hx >= (unsigned int)hp.width || (unsigned int)hy >= (unsigned int)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+bs)+(ay+bs)*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; - - stack.push(ax); - stack.push(ay); - stack.push(ai); + + hp.data[hx + hy*hp.width] = as.y; + + push3(queue, ax, ay, ai); } } - } static unsigned char getEdgeFlags(const float* va, const float* vb, @@ -923,7 +1145,7 @@ static unsigned char getEdgeFlags(const float* va, const float* vb, static const float thrSqr = rcSqr(0.001f); for (int i = 0, j = npoly-1; i < npoly; j=i++) { - if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr && + if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr && distancePtSeg2d(vb, &vpoly[j*3], &vpoly[i*3]) < thrSqr) return 1; } @@ -951,8 +1173,8 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_POLYMESHDETAIL); - + rcScopedTimer timer(ctx, RC_TIMER_BUILD_POLYMESHDETAIL); + if (mesh.nverts == 0 || mesh.npolys == 0) return true; @@ -961,23 +1183,24 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa const float ch = mesh.ch; const float* orig = mesh.bmin; const int borderSize = mesh.borderSize; + const int heightSearchRadius = rcMax(1, (int)ceilf(mesh.maxEdgeError)); rcIntArray edges(64); rcIntArray tris(512); - rcIntArray stack(512); + rcIntArray arr(512); rcIntArray samples(512); float verts[256*3]; rcHeightPatch hp; int nPolyVerts = 0; int maxhw = 0, maxhh = 0; - rcScopedDelete<int> bounds = (int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP); + rcScopedDelete<int> bounds((int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP)); if (!bounds) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'bounds' (%d).", mesh.npolys*4); return false; } - rcScopedDelete<float> poly = (float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP); + rcScopedDelete<float> poly((float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP)); if (!poly) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'poly' (%d).", nvp*3); @@ -1015,7 +1238,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa maxhh = rcMax(maxhh, ymax-ymin); } - hp.data = (unsigned short *)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP); + hp.data = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP); if (!hp.data) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'hp.data' (%d).", maxhw*maxhh); @@ -1031,10 +1254,10 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4); return false; } - + int vcap = nPolyVerts+nPolyVerts/2; int tcap = vcap*2; - + dmesh.nverts = 0; dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM); if (!dmesh.verts) @@ -1043,7 +1266,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa return false; } dmesh.ntris = 0; - dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char*)*tcap*4, RC_ALLOC_PERM); + dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM); if (!dmesh.tris) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4); @@ -1071,18 +1294,19 @@ 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, borderSize, hp, stack); + getHeightData(ctx, chf, p, npoly, mesh.verts, borderSize, hp, arr, mesh.regs[i]); // Build detail mesh. int nverts = 0; if (!buildPolyDetail(ctx, poly, npoly, sampleDist, sampleMaxError, - chf, hp, verts, nverts, tris, + heightSearchRadius, chf, hp, + verts, nverts, tris, edges, samples)) { return false; } - + // Move detail verts to world space. for (int j = 0; j < nverts; ++j) { @@ -1097,21 +1321,21 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa poly[j*3+1] += orig[1]; poly[j*3+2] += orig[2]; } - + // Store detail submesh. const int ntris = tris.size()/4; - + dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts; dmesh.meshes[i*4+1] = (unsigned int)nverts; dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris; - dmesh.meshes[i*4+3] = (unsigned int)ntris; + dmesh.meshes[i*4+3] = (unsigned int)ntris; // Store vertices, allocate more memory if necessary. if (dmesh.nverts+nverts > vcap) { while (dmesh.nverts+nverts > vcap) vcap += 256; - + float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM); if (!newv) { @@ -1157,9 +1381,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa dmesh.ntris++; } } - - ctx->stopTimer(RC_TIMER_BUILD_POLYMESHDETAIL); - + return true; } @@ -1168,12 +1390,12 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int { rcAssert(ctx); - ctx->startTimer(RC_TIMER_MERGE_POLYMESHDETAIL); - + rcScopedTimer timer(ctx, RC_TIMER_MERGE_POLYMESHDETAIL); + int maxVerts = 0; int maxTris = 0; int maxMeshes = 0; - + for (int i = 0; i < nmeshes; ++i) { if (!meshes[i]) continue; @@ -1181,7 +1403,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int maxTris += meshes[i]->ntris; maxMeshes += meshes[i]->nmeshes; } - + mesh.nmeshes = 0; mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM); if (!mesh.meshes) @@ -1189,7 +1411,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4); return false; } - + mesh.ntris = 0; mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM); if (!mesh.tris) @@ -1197,7 +1419,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4); return false; } - + mesh.nverts = 0; mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM); if (!mesh.verts) @@ -1221,7 +1443,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int dst[3] = src[3]; mesh.nmeshes++; } - + for (int k = 0; k < dm->nverts; ++k) { rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]); @@ -1236,9 +1458,6 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int mesh.ntris++; } } - - ctx->stopTimer(RC_TIMER_MERGE_POLYMESHDETAIL); return true; } - |