diff options
Diffstat (limited to 'extern/recastnavigation/Recast/Source/RecastContour.cpp')
| -rw-r--r-- | extern/recastnavigation/Recast/Source/RecastContour.cpp | 592 |
1 files changed, 422 insertions, 170 deletions
diff --git a/extern/recastnavigation/Recast/Source/RecastContour.cpp b/extern/recastnavigation/Recast/Source/RecastContour.cpp index df943838ffb..277ab015018 100644 --- a/extern/recastnavigation/Recast/Source/RecastContour.cpp +++ b/extern/recastnavigation/Recast/Source/RecastContour.cpp @@ -20,6 +20,7 @@ #include <math.h> #include <string.h> #include <stdio.h> +#include <stdlib.h> #include "Recast.h" #include "RecastAlloc.h" #include "RecastAssert.h" @@ -36,7 +37,7 @@ static int getCornerHeight(int x, int y, int i, int dir, unsigned int regs[4] = {0,0,0,0}; // Combine region and area codes in order to prevent - // border vertices which are in between two areas to be removed. + // border vertices which are in between two areas to be removed. regs[0] = chf.spans[i].reg | (chf.areas[i] << 16); if (rcGetCon(s, dir) != RC_NOT_CONNECTED) @@ -187,27 +188,6 @@ static float distancePtSeg(const int x, const int z, const int px, const int pz, const int qx, const int qz) { -/* float pqx = (float)(qx - px); - float pqy = (float)(qy - py); - float pqz = (float)(qz - pz); - float dx = (float)(x - px); - float dy = (float)(y - py); - float dz = (float)(z - pz); - float d = pqx*pqx + pqy*pqy + pqz*pqz; - float t = pqx*dx + pqy*dy + pqz*dz; - if (d > 0) - t /= d; - if (t < 0) - t = 0; - else if (t > 1) - t = 1; - - dx = px + t*pqx - x; - dy = py + t*pqy - y; - dz = pz + t*pqz - z; - - return dx*dx + dy*dy + dz*dz;*/ - float pqx = (float)(qx - px); float pqz = (float)(qz - pz); float dx = (float)(x - px); @@ -257,13 +237,13 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, simplified.push(points[i*4+2]); simplified.push(i); } - } + } } if (simplified.size() == 0) { // If there is no connections at all, - // create some initial points for the simplification process. + // create some initial points for the simplification process. // Find lower-left and upper-right vertices of the contour. int llx = points[0]; int lly = points[1]; @@ -311,19 +291,19 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, { int ii = (i+1) % (simplified.size()/4); - const int ax = simplified[i*4+0]; - const int az = simplified[i*4+2]; - const int ai = simplified[i*4+3]; - - const int bx = simplified[ii*4+0]; - const int bz = simplified[ii*4+2]; - const int bi = simplified[ii*4+3]; + int ax = simplified[i*4+0]; + int az = simplified[i*4+2]; + int ai = simplified[i*4+3]; + + int bx = simplified[ii*4+0]; + int bz = simplified[ii*4+2]; + int bi = simplified[ii*4+3]; // Find maximum deviation from the segment. float maxd = 0; - int i_max = -1; + int maxi = -1; int ci, cinc, endi; - + // Traverse the segment in lexilogical order so that the // max deviation is calculated similarly when traversing // opposite segments. @@ -338,6 +318,8 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, cinc = pn-1; ci = (bi+cinc) % pn; endi = ai; + rcSwap(ax, bx); + rcSwap(az, bz); } // Tessellate only outer edges or edges between areas. @@ -350,7 +332,7 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, if (d > maxd) { maxd = d; - i_max = ci; + maxi = ci; } ci = (ci+cinc) % pn; } @@ -359,7 +341,7 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, // If the max deviation is larger than accepted error, // add new point, else continue to next segment. - if (i_max != -1 && maxd > (maxError*maxError)) + if (maxi != -1 && maxd > (maxError*maxError)) { // Add space for the new point. simplified.resize(simplified.size()+4); @@ -372,10 +354,10 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, simplified[j*4+3] = simplified[(j-1)*4+3]; } // Add the point. - simplified[(i+1)*4+0] = points[i_max*4+0]; - simplified[(i+1)*4+1] = points[i_max*4+1]; - simplified[(i+1)*4+2] = points[i_max*4+2]; - simplified[(i+1)*4+3] = i_max; + simplified[(i+1)*4+0] = points[maxi*4+0]; + simplified[(i+1)*4+1] = points[maxi*4+1]; + simplified[(i+1)*4+2] = points[maxi*4+2]; + simplified[(i+1)*4+3] = maxi; } else { @@ -397,11 +379,11 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, const int bx = simplified[ii*4+0]; const int bz = simplified[ii*4+2]; const int bi = simplified[ii*4+3]; - + // Find maximum deviation from the segment. - int i_max = -1; + int maxi = -1; int ci = (ai+1) % pn; - + // Tessellate only outer edges or edges between areas. bool tess = false; // Wall edges. @@ -420,22 +402,20 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, // Round based on the segments in lexilogical order so that the // max tesselation is consistent regardles in which direction // segments are traversed. - if (bx > ax || (bx == ax && bz > az)) + const int n = bi < ai ? (bi+pn - ai) : (bi - ai); + if (n > 1) { - const int n = bi < ai ? (bi+pn - ai) : (bi - ai); - i_max = (ai + n/2) % pn; - } - else - { - const int n = bi < ai ? (bi+pn - ai) : (bi - ai); - i_max = (ai + (n+1)/2) % pn; + if (bx > ax || (bx == ax && bz > az)) + maxi = (ai + n/2) % pn; + else + maxi = (ai + (n+1)/2) % pn; } } } // If the max deviation is larger than accepted error, // add new point, else continue to next segment. - if (i_max != -1) + if (maxi != -1) { // Add space for the new point. simplified.resize(simplified.size()+4); @@ -448,10 +428,10 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, simplified[j*4+3] = simplified[(j-1)*4+3]; } // Add the point. - simplified[(i+1)*4+0] = points[i_max*4+0]; - simplified[(i+1)*4+1] = points[i_max*4+1]; - simplified[(i+1)*4+2] = points[i_max*4+2]; - simplified[(i+1)*4+3] = i_max; + simplified[(i+1)*4+0] = points[maxi*4+0]; + simplified[(i+1)*4+1] = points[maxi*4+1]; + simplified[(i+1)*4+2] = points[maxi*4+2]; + simplified[(i+1)*4+3] = maxi; } else { @@ -466,37 +446,11 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, // and the neighbour region is take from the next raw point. const int ai = (simplified[i*4+3]+1) % pn; const int bi = simplified[i*4+3]; - simplified[i*4+3] = (points[ai*4+3] & RC_CONTOUR_REG_MASK) | (points[bi*4+3] & RC_BORDER_VERTEX); + simplified[i*4+3] = (points[ai*4+3] & (RC_CONTOUR_REG_MASK|RC_AREA_BORDER)) | (points[bi*4+3] & RC_BORDER_VERTEX); } } -static void removeDegenerateSegments(rcIntArray& simplified) -{ - // Remove adjacent vertices which are equal on xz-plane, - // or else the triangulator will get confused. - for (int i = 0; i < simplified.size()/4; ++i) - { - int ni = i+1; - if (ni >= (simplified.size()/4)) - ni = 0; - - if (simplified[i*4+0] == simplified[ni*4+0] && - simplified[i*4+2] == simplified[ni*4+2]) - { - // Degenerate segment, remove. - for (int j = i; j < simplified.size()/4-1; ++j) - { - simplified[j*4+0] = simplified[(j+1)*4+0]; - simplified[j*4+1] = simplified[(j+1)*4+1]; - simplified[j*4+2] = simplified[(j+1)*4+2]; - simplified[j*4+3] = simplified[(j+1)*4+3]; - } - simplified.resize(simplified.size()-4); - } - } -} - static int calcAreaOfPolygon2D(const int* verts, const int nverts) { int area = 0; @@ -509,54 +463,155 @@ static int calcAreaOfPolygon2D(const int* verts, const int nverts) return (area+1) / 2; } -inline bool ileft(const int* a, const int* b, const int* c) +// TODO: these are the same as in RecastMesh.cpp, consider using the same. +// 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; } + +inline int area2(const int* a, const int* b, const int* c) +{ + return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]); +} + +// Exclusive or: true iff exactly one argument is true. +// The arguments are negated to ensure that they are 0/1 +// values. Then the bitwise Xor operator may apply. +// (This idea is due to Michael Baldwin.) +inline bool xorb(bool x, bool y) { - return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]) <= 0; + return !x ^ !y; } -static void getClosestIndices(const int* vertsa, const int nvertsa, - const int* vertsb, const int nvertsb, - int& ia, int& ib) +// Returns true iff c is strictly to the left of the directed +// line through a to b. +inline bool left(const int* a, const int* b, const int* c) { - int closestDist = 0xfffffff; - ia = -1, ib = -1; - for (int i = 0; i < nvertsa; ++i) + return area2(a, b, c) < 0; +} + +inline bool leftOn(const int* a, const int* b, const int* c) +{ + return area2(a, b, c) <= 0; +} + +inline bool collinear(const int* a, const int* b, const int* c) +{ + return area2(a, b, c) == 0; +} + +// 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. +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) || + collinear(c,d,a) || collinear(c,d,b)) + return false; + + return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b)); +} + +// Returns T iff (a,b,c) are collinear and point c lies +// on the closed segement ab. +static bool between(const int* a, const int* b, const int* c) +{ + if (!collinear(a, b, c)) + return false; + // If ab not vertical, check betweenness on x; else on y. + if (a[0] != b[0]) + return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0])); + else + return ((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2])); +} + +// Returns true iff segments ab and cd intersect, properly or improperly. +static bool intersect(const int* a, const int* b, const int* c, const int* d) +{ + if (intersectProp(a, b, c, d)) + return true; + else if (between(a, b, c) || between(a, b, d) || + between(c, d, a) || between(c, d, b)) + return true; + else + return false; +} + +static bool vequal(const int* a, const int* b) +{ + return a[0] == b[0] && a[2] == b[2]; +} + +static bool intersectSegCountour(const int* d0, const int* d1, int i, int n, const int* verts) +{ + // For each edge (k,k+1) of P + for (int k = 0; k < n; k++) + { + int k1 = next(k, n); + // Skip edges incident to i. + if (i == k || i == k1) + continue; + const int* p0 = &verts[k * 4]; + const int* p1 = &verts[k1 * 4]; + if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1)) + continue; + + if (intersect(d0, d1, p0, p1)) + return true; + } + return false; +} + +static bool inCone(int i, int n, const int* verts, const int* pj) +{ + const int* pi = &verts[i * 4]; + const int* pi1 = &verts[next(i, n) * 4]; + const int* pin1 = &verts[prev(i, n) * 4]; + + // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ]. + if (leftOn(pin1, pi, pi1)) + return left(pi, pj, pin1) && left(pj, pi, pi1); + // Assume (i-1,i,i+1) not collinear. + // else P[i] is reflex. + return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1)); +} + + +static void removeDegenerateSegments(rcIntArray& simplified) +{ + // Remove adjacent vertices which are equal on xz-plane, + // or else the triangulator will get confused. + int npts = simplified.size()/4; + for (int i = 0; i < npts; ++i) { - const int in = (i+1) % nvertsa; - const int ip = (i+nvertsa-1) % nvertsa; - const int* va = &vertsa[i*4]; - const int* van = &vertsa[in*4]; - const int* vap = &vertsa[ip*4]; + int ni = next(i, npts); - for (int j = 0; j < nvertsb; ++j) + if (vequal(&simplified[i*4], &simplified[ni*4])) { - const int* vb = &vertsb[j*4]; - // vb must be "infront" of va. - if (ileft(vap,va,vb) && ileft(va,van,vb)) + // Degenerate segment, remove. + for (int j = i; j < simplified.size()/4-1; ++j) { - const int dx = vb[0] - va[0]; - const int dz = vb[2] - va[2]; - const int d = dx*dx + dz*dz; - if (d < closestDist) - { - ia = i; - ib = j; - closestDist = d; - } + simplified[j*4+0] = simplified[(j+1)*4+0]; + simplified[j*4+1] = simplified[(j+1)*4+1]; + simplified[j*4+2] = simplified[(j+1)*4+2]; + simplified[j*4+3] = simplified[(j+1)*4+3]; } + simplified.resize(simplified.size()-4); + npts--; } } } + static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib) { const int maxVerts = ca.nverts + cb.nverts + 2; int* verts = (int*)rcAlloc(sizeof(int)*maxVerts*4, RC_ALLOC_PERM); if (!verts) return false; - + int nv = 0; - + // Copy contour A. for (int i = 0; i <= ca.nverts; ++i) { @@ -584,7 +639,7 @@ static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib) rcFree(ca.verts); ca.verts = verts; ca.nverts = nv; - + rcFree(cb.verts); cb.verts = 0; cb.nverts = 0; @@ -592,18 +647,179 @@ static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib) return true; } +struct rcContourHole +{ + rcContour* contour; + int minx, minz, leftmost; +}; + +struct rcContourRegion +{ + rcContour* outline; + rcContourHole* holes; + int nholes; +}; + +struct rcPotentialDiagonal +{ + int vert; + int dist; +}; + +// Finds the lowest leftmost vertex of a contour. +static void findLeftMostVertex(rcContour* contour, int* minx, int* minz, int* leftmost) +{ + *minx = contour->verts[0]; + *minz = contour->verts[2]; + *leftmost = 0; + for (int i = 1; i < contour->nverts; i++) + { + const int x = contour->verts[i*4+0]; + const int z = contour->verts[i*4+2]; + if (x < *minx || (x == *minx && z < *minz)) + { + *minx = x; + *minz = z; + *leftmost = i; + } + } +} + +static int compareHoles(const void* va, const void* vb) +{ + const rcContourHole* a = (const rcContourHole*)va; + const rcContourHole* b = (const rcContourHole*)vb; + if (a->minx == b->minx) + { + if (a->minz < b->minz) + return -1; + if (a->minz > b->minz) + return 1; + } + else + { + if (a->minx < b->minx) + return -1; + if (a->minx > b->minx) + return 1; + } + return 0; +} + + +static int compareDiagDist(const void* va, const void* vb) +{ + const rcPotentialDiagonal* a = (const rcPotentialDiagonal*)va; + const rcPotentialDiagonal* b = (const rcPotentialDiagonal*)vb; + if (a->dist < b->dist) + return -1; + if (a->dist > b->dist) + return 1; + return 0; +} + + +static void mergeRegionHoles(rcContext* ctx, rcContourRegion& region) +{ + // Sort holes from left to right. + for (int i = 0; i < region.nholes; i++) + findLeftMostVertex(region.holes[i].contour, ®ion.holes[i].minx, ®ion.holes[i].minz, ®ion.holes[i].leftmost); + + qsort(region.holes, region.nholes, sizeof(rcContourHole), compareHoles); + + int maxVerts = region.outline->nverts; + for (int i = 0; i < region.nholes; i++) + maxVerts += region.holes[i].contour->nverts; + + rcScopedDelete<rcPotentialDiagonal> diags((rcPotentialDiagonal*)rcAlloc(sizeof(rcPotentialDiagonal)*maxVerts, RC_ALLOC_TEMP)); + if (!diags) + { + ctx->log(RC_LOG_WARNING, "mergeRegionHoles: Failed to allocated diags %d.", maxVerts); + return; + } + + rcContour* outline = region.outline; + + // Merge holes into the outline one by one. + for (int i = 0; i < region.nholes; i++) + { + rcContour* hole = region.holes[i].contour; + + int index = -1; + int bestVertex = region.holes[i].leftmost; + for (int iter = 0; iter < hole->nverts; iter++) + { + // Find potential diagonals. + // The 'best' vertex must be in the cone described by 3 cosequtive vertices of the outline. + // ..o j-1 + // | + // | * best + // | + // j o-----o j+1 + // : + int ndiags = 0; + const int* corner = &hole->verts[bestVertex*4]; + for (int j = 0; j < outline->nverts; j++) + { + if (inCone(j, outline->nverts, outline->verts, corner)) + { + int dx = outline->verts[j*4+0] - corner[0]; + int dz = outline->verts[j*4+2] - corner[2]; + diags[ndiags].vert = j; + diags[ndiags].dist = dx*dx + dz*dz; + ndiags++; + } + } + // Sort potential diagonals by distance, we want to make the connection as short as possible. + qsort(diags, ndiags, sizeof(rcPotentialDiagonal), compareDiagDist); + + // Find a diagonal that is not intersecting the outline not the remaining holes. + index = -1; + for (int j = 0; j < ndiags; j++) + { + const int* pt = &outline->verts[diags[j].vert*4]; + bool intersect = intersectSegCountour(pt, corner, diags[i].vert, outline->nverts, outline->verts); + for (int k = i; k < region.nholes && !intersect; k++) + intersect |= intersectSegCountour(pt, corner, -1, region.holes[k].contour->nverts, region.holes[k].contour->verts); + if (!intersect) + { + index = diags[j].vert; + break; + } + } + // If found non-intersecting diagonal, stop looking. + if (index != -1) + break; + // All the potential diagonals for the current vertex were intersecting, try next vertex. + bestVertex = (bestVertex + 1) % hole->nverts; + } + + if (index == -1) + { + ctx->log(RC_LOG_WARNING, "mergeHoles: Failed to find merge points for %p and %p.", region.outline, hole); + continue; + } + if (!mergeContours(*region.outline, *hole, index, bestVertex)) + { + ctx->log(RC_LOG_WARNING, "mergeHoles: Failed to merge contours %p and %p.", region.outline, hole); + continue; + } + } +} + + /// @par /// /// The raw contours will match the region outlines exactly. The @p maxError and @p maxEdgeLen /// parameters control how closely the simplified contours will match the raw contours. /// -/// Simplified contours are generated such that the vertices for portals between areas match up. +/// Simplified contours are generated such that the vertices for portals between areas match up. /// (They are considered mandatory vertices.) /// /// Setting @p maxEdgeLength to zero will disabled the edge length feature. -/// +/// /// See the #rcConfig documentation for more information on the configuration parameters. -/// +/// /// @see rcAllocContourSet, rcCompactHeightfield, rcContourSet, rcConfig bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, const float maxError, const int maxEdgeLen, @@ -615,7 +831,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, const int h = chf.height; const int borderSize = chf.borderSize; - ctx->startTimer(RC_TIMER_BUILD_CONTOURS); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_CONTOURS); rcVcopy(cset.bmin, chf.bmin); rcVcopy(cset.bmax, chf.bmax); @@ -633,6 +849,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, cset.width = chf.width - chf.borderSize*2; cset.height = chf.height - chf.borderSize*2; cset.borderSize = chf.borderSize; + cset.maxError = maxError; int maxContours = rcMax((int)chf.maxRegions, 8); cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM); @@ -640,7 +857,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, return false; cset.nconts = 0; - rcScopedDelete<unsigned char> flags = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP); + rcScopedDelete<unsigned char> flags((unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP)); if (!flags) { ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount); @@ -706,17 +923,17 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, verts.resize(0); simplified.resize(0); - + ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE); walkContour(x, y, i, chf, flags, verts); ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE); - + ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY); simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags); removeDegenerateSegments(simplified); ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY); - + // Store region->contour remap info. // Create contour. if (simplified.size()/4 >= 3) @@ -724,7 +941,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, if (cset.nconts >= maxContours) { // Allocate more contours. - // This can happen when there are tiny holes in the heightfield. + // This happens when a region has holes. const int oldMax = maxContours; maxContours *= 2; rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM); @@ -737,10 +954,10 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, } rcFree(cset.conts); cset.conts = newConts; - + ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours); } - + rcContour* cont = &cset.conts[cset.nconts++]; cont->nverts = simplified.size()/4; @@ -754,9 +971,9 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, if (borderSize > 0) { // If the heightfield was build with bordersize, remove the offset. - for (int i = 0; i < cont->nverts; ++i) + for (int j = 0; j < cont->nverts; ++j) { - int* v = &cont->verts[i*4]; + int* v = &cont->verts[j*4]; v[0] -= borderSize; v[2] -= borderSize; } @@ -773,25 +990,14 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, if (borderSize > 0) { // If the heightfield was build with bordersize, remove the offset. - for (int i = 0; i < cont->nrverts; ++i) + for (int j = 0; j < cont->nrverts; ++j) { - int* v = &cont->rverts[i*4]; + int* v = &cont->rverts[j*4]; v[0] -= borderSize; v[2] -= borderSize; } } -/* cont->cx = cont->cy = cont->cz = 0; - for (int i = 0; i < cont->nverts; ++i) - { - cont->cx += cont->verts[i*4+0]; - cont->cy += cont->verts[i*4+1]; - cont->cz += cont->verts[i*4+2]; - } - cont->cx /= cont->nverts; - cont->cy /= cont->nverts; - cont->cz /= cont->nverts;*/ - cont->reg = reg; cont->area = area; } @@ -799,55 +1005,101 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, } } - // Check and merge droppings. - // Sometimes the previous algorithms can fail and create several contours - // per area. This pass will try to merge the holes into the main region. - for (int i = 0; i < cset.nconts; ++i) + // Merge holes if needed. + if (cset.nconts > 0) { - rcContour& cont = cset.conts[i]; - // Check if the contour is would backwards. - if (calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0) + // Calculate winding of all polygons. + rcScopedDelete<char> winding((char*)rcAlloc(sizeof(char)*cset.nconts, RC_ALLOC_TEMP)); + if (!winding) + { + ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'hole' (%d).", cset.nconts); + return false; + } + int nholes = 0; + for (int i = 0; i < cset.nconts; ++i) + { + rcContour& cont = cset.conts[i]; + // If the contour is wound backwards, it is a hole. + winding[i] = calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0 ? -1 : 1; + if (winding[i] < 0) + nholes++; + } + + if (nholes > 0) { - // Find another contour which has the same region ID. - int mergeIdx = -1; - for (int j = 0; j < cset.nconts; ++j) + // Collect outline contour and holes contours per region. + // We assume that there is one outline and multiple holes. + const int nregions = chf.maxRegions+1; + rcScopedDelete<rcContourRegion> regions((rcContourRegion*)rcAlloc(sizeof(rcContourRegion)*nregions, RC_ALLOC_TEMP)); + if (!regions) + { + ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'regions' (%d).", nregions); + return false; + } + memset(regions, 0, sizeof(rcContourRegion)*nregions); + + rcScopedDelete<rcContourHole> holes((rcContourHole*)rcAlloc(sizeof(rcContourHole)*cset.nconts, RC_ALLOC_TEMP)); + if (!holes) { - if (i == j) continue; - if (cset.conts[j].nverts && cset.conts[j].reg == cont.reg) + ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'holes' (%d).", cset.nconts); + return false; + } + memset(holes, 0, sizeof(rcContourHole)*cset.nconts); + + for (int i = 0; i < cset.nconts; ++i) + { + rcContour& cont = cset.conts[i]; + // Positively would contours are outlines, negative holes. + if (winding[i] > 0) { - // Make sure the polygon is correctly oriented. - if (calcAreaOfPolygon2D(cset.conts[j].verts, cset.conts[j].nverts)) - { - mergeIdx = j; - break; - } + if (regions[cont.reg].outline) + ctx->log(RC_LOG_ERROR, "rcBuildContours: Multiple outlines for region %d.", cont.reg); + regions[cont.reg].outline = &cont; + } + else + { + regions[cont.reg].nholes++; + } + } + int index = 0; + for (int i = 0; i < nregions; i++) + { + if (regions[i].nholes > 0) + { + regions[i].holes = &holes[index]; + index += regions[i].nholes; + regions[i].nholes = 0; } } - if (mergeIdx == -1) + for (int i = 0; i < cset.nconts; ++i) { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i); + rcContour& cont = cset.conts[i]; + rcContourRegion& reg = regions[cont.reg]; + if (winding[i] < 0) + reg.holes[reg.nholes++].contour = &cont; } - else + + // Finally merge each regions holes into the outline. + for (int i = 0; i < nregions; i++) { - rcContour& mcont = cset.conts[mergeIdx]; - // Merge by closest points. - int ia = 0, ib = 0; - getClosestIndices(mcont.verts, mcont.nverts, cont.verts, cont.nverts, ia, ib); - if (ia == -1 || ib == -1) + rcContourRegion& reg = regions[i]; + if (!reg.nholes) continue; + + if (reg.outline) { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to find merge points for %d and %d.", i, mergeIdx); - continue; + mergeRegionHoles(ctx, reg); } - if (!mergeContours(mcont, cont, ia, ib)) + else { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to merge contours %d and %d.", i, mergeIdx); - continue; + // The region does not have an outline. + // This can happen if the contour becaomes selfoverlapping because of + // too aggressive simplification settings. + ctx->log(RC_LOG_ERROR, "rcBuildContours: Bad outline for region %d, contour simplification is likely too aggressive.", i); } } } + } - ctx->stopTimer(RC_TIMER_BUILD_CONTOURS); - return true; } |