diff options
Diffstat (limited to 'extern/recastnavigation/Recast/Source/RecastContour.cpp')
-rw-r--r-- | extern/recastnavigation/Recast/Source/RecastContour.cpp | 1105 |
1 files changed, 0 insertions, 1105 deletions
diff --git a/extern/recastnavigation/Recast/Source/RecastContour.cpp b/extern/recastnavigation/Recast/Source/RecastContour.cpp deleted file mode 100644 index 277ab015018..00000000000 --- a/extern/recastnavigation/Recast/Source/RecastContour.cpp +++ /dev/null @@ -1,1105 +0,0 @@ -// -// 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 -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#define _USE_MATH_DEFINES -#include <math.h> -#include <string.h> -#include <stdio.h> -#include <stdlib.h> -#include "Recast.h" -#include "RecastAlloc.h" -#include "RecastAssert.h" - - -static int getCornerHeight(int x, int y, int i, int dir, - const rcCompactHeightfield& chf, - bool& isBorderVertex) -{ - const rcCompactSpan& s = chf.spans[i]; - int ch = (int)s.y; - int dirp = (dir+1) & 0x3; - - 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. - regs[0] = chf.spans[i].reg | (chf.areas[i] << 16); - - 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]; - ch = rcMax(ch, (int)as.y); - regs[1] = chf.spans[ai].reg | (chf.areas[ai] << 16); - if (rcGetCon(as, dirp) != RC_NOT_CONNECTED) - { - const int ax2 = ax + rcGetDirOffsetX(dirp); - const int ay2 = ay + rcGetDirOffsetY(dirp); - const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dirp); - const rcCompactSpan& as2 = chf.spans[ai2]; - ch = rcMax(ch, (int)as2.y); - regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16); - } - } - if (rcGetCon(s, dirp) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dirp); - const int ay = y + rcGetDirOffsetY(dirp); - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dirp); - const rcCompactSpan& as = chf.spans[ai]; - ch = rcMax(ch, (int)as.y); - regs[3] = chf.spans[ai].reg | (chf.areas[ai] << 16); - if (rcGetCon(as, dir) != RC_NOT_CONNECTED) - { - const int ax2 = ax + rcGetDirOffsetX(dir); - const int ay2 = ay + rcGetDirOffsetY(dir); - const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dir); - const rcCompactSpan& as2 = chf.spans[ai2]; - ch = rcMax(ch, (int)as2.y); - regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16); - } - } - - // Check if the vertex is special edge vertex, these vertices will be removed later. - for (int j = 0; j < 4; ++j) - { - const int a = j; - const int b = (j+1) & 0x3; - const int c = (j+2) & 0x3; - const int d = (j+3) & 0x3; - - // The vertex is a border vertex there are two same exterior cells in a row, - // followed by two interior cells and none of the regions are out of bounds. - const bool twoSameExts = (regs[a] & regs[b] & RC_BORDER_REG) != 0 && regs[a] == regs[b]; - const bool twoInts = ((regs[c] | regs[d]) & RC_BORDER_REG) == 0; - const bool intsSameArea = (regs[c]>>16) == (regs[d]>>16); - const bool noZeros = regs[a] != 0 && regs[b] != 0 && regs[c] != 0 && regs[d] != 0; - if (twoSameExts && twoInts && intsSameArea && noZeros) - { - isBorderVertex = true; - break; - } - } - - return ch; -} - -static void walkContour(int x, int y, int i, - rcCompactHeightfield& chf, - unsigned char* flags, rcIntArray& points) -{ - // Choose the first non-connected edge - unsigned char dir = 0; - while ((flags[i] & (1 << dir)) == 0) - dir++; - - unsigned char startDir = dir; - int starti = i; - - const unsigned char area = chf.areas[i]; - - int iter = 0; - while (++iter < 40000) - { - if (flags[i] & (1 << dir)) - { - // Choose the edge corner - bool isBorderVertex = false; - bool isAreaBorder = false; - int px = x; - int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex); - int pz = y; - switch(dir) - { - case 0: pz++; break; - case 1: px++; pz++; break; - case 2: px++; break; - } - int r = 0; - const rcCompactSpan& s = chf.spans[i]; - 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); - r = (int)chf.spans[ai].reg; - if (area != chf.areas[ai]) - isAreaBorder = true; - } - if (isBorderVertex) - r |= RC_BORDER_VERTEX; - if (isAreaBorder) - r |= RC_AREA_BORDER; - points.push(px); - points.push(py); - points.push(pz); - points.push(r); - - flags[i] &= ~(1 << dir); // Remove visited edges - dir = (dir+1) & 0x3; // Rotate CW - } - else - { - int ni = -1; - const int nx = x + rcGetDirOffsetX(dir); - const int ny = y + rcGetDirOffsetY(dir); - const rcCompactSpan& s = chf.spans[i]; - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const rcCompactCell& nc = chf.cells[nx+ny*chf.width]; - ni = (int)nc.index + rcGetCon(s, dir); - } - if (ni == -1) - { - // Should not happen. - return; - } - x = nx; - y = ny; - i = ni; - dir = (dir+3) & 0x3; // Rotate CCW - } - - if (starti == i && startDir == dir) - { - break; - } - } -} - -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 pqz = (float)(qz - pz); - float dx = (float)(x - px); - float dz = (float)(z - pz); - float d = pqx*pqx + pqz*pqz; - float t = pqx*dx + pqz*dz; - if (d > 0) - t /= d; - if (t < 0) - t = 0; - else if (t > 1) - t = 1; - - dx = px + t*pqx - x; - dz = pz + t*pqz - z; - - return dx*dx + dz*dz; -} - -static void simplifyContour(rcIntArray& points, rcIntArray& simplified, - const float maxError, const int maxEdgeLen, const int buildFlags) -{ - // Add initial points. - bool hasConnections = false; - for (int i = 0; i < points.size(); i += 4) - { - if ((points[i+3] & RC_CONTOUR_REG_MASK) != 0) - { - hasConnections = true; - break; - } - } - - if (hasConnections) - { - // The contour has some portals to other regions. - // Add a new point to every location where the region changes. - for (int i = 0, ni = points.size()/4; i < ni; ++i) - { - int ii = (i+1) % ni; - const bool differentRegs = (points[i*4+3] & RC_CONTOUR_REG_MASK) != (points[ii*4+3] & RC_CONTOUR_REG_MASK); - const bool areaBorders = (points[i*4+3] & RC_AREA_BORDER) != (points[ii*4+3] & RC_AREA_BORDER); - if (differentRegs || areaBorders) - { - simplified.push(points[i*4+0]); - simplified.push(points[i*4+1]); - 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. - // Find lower-left and upper-right vertices of the contour. - int llx = points[0]; - int lly = points[1]; - int llz = points[2]; - int lli = 0; - int urx = points[0]; - int ury = points[1]; - int urz = points[2]; - int uri = 0; - for (int i = 0; i < points.size(); i += 4) - { - int x = points[i+0]; - int y = points[i+1]; - int z = points[i+2]; - if (x < llx || (x == llx && z < llz)) - { - llx = x; - lly = y; - llz = z; - lli = i/4; - } - if (x > urx || (x == urx && z > urz)) - { - urx = x; - ury = y; - urz = z; - uri = i/4; - } - } - simplified.push(llx); - simplified.push(lly); - simplified.push(llz); - simplified.push(lli); - - simplified.push(urx); - simplified.push(ury); - simplified.push(urz); - simplified.push(uri); - } - - // Add points until all raw points are within - // error tolerance to the simplified shape. - const int pn = points.size()/4; - for (int i = 0; i < simplified.size()/4; ) - { - int ii = (i+1) % (simplified.size()/4); - - 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 maxi = -1; - int ci, cinc, endi; - - // Traverse the segment in lexilogical order so that the - // max deviation is calculated similarly when traversing - // opposite segments. - if (bx > ax || (bx == ax && bz > az)) - { - cinc = 1; - ci = (ai+cinc) % pn; - endi = bi; - } - else - { - cinc = pn-1; - ci = (bi+cinc) % pn; - endi = ai; - rcSwap(ax, bx); - rcSwap(az, bz); - } - - // Tessellate only outer edges or edges between areas. - if ((points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0 || - (points[ci*4+3] & RC_AREA_BORDER)) - { - while (ci != endi) - { - float d = distancePtSeg(points[ci*4+0], points[ci*4+2], ax, az, bx, bz); - if (d > maxd) - { - maxd = d; - maxi = ci; - } - ci = (ci+cinc) % pn; - } - } - - - // If the max deviation is larger than accepted error, - // add new point, else continue to next segment. - if (maxi != -1 && maxd > (maxError*maxError)) - { - // Add space for the new point. - simplified.resize(simplified.size()+4); - const int n = simplified.size()/4; - for (int j = n-1; j > i; --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]; - } - // Add the point. - 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 - { - ++i; - } - } - - // Split too long edges. - if (maxEdgeLen > 0 && (buildFlags & (RC_CONTOUR_TESS_WALL_EDGES|RC_CONTOUR_TESS_AREA_EDGES)) != 0) - { - for (int i = 0; i < simplified.size()/4; ) - { - const 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]; - - // Find maximum deviation from the segment. - int maxi = -1; - int ci = (ai+1) % pn; - - // Tessellate only outer edges or edges between areas. - bool tess = false; - // Wall edges. - if ((buildFlags & RC_CONTOUR_TESS_WALL_EDGES) && (points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0) - tess = true; - // Edges between areas. - if ((buildFlags & RC_CONTOUR_TESS_AREA_EDGES) && (points[ci*4+3] & RC_AREA_BORDER)) - tess = true; - - if (tess) - { - int dx = bx - ax; - int dz = bz - az; - if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen) - { - // Round based on the segments in lexilogical order so that the - // max tesselation is consistent regardles in which direction - // segments are traversed. - const int n = bi < ai ? (bi+pn - ai) : (bi - ai); - if (n > 1) - { - 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 (maxi != -1) - { - // Add space for the new point. - simplified.resize(simplified.size()+4); - const int n = simplified.size()/4; - for (int j = n-1; j > i; --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]; - } - // Add the point. - 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 - { - ++i; - } - } - } - - for (int i = 0; i < simplified.size()/4; ++i) - { - // The edge vertex flag is take from the current raw point, - // 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|RC_AREA_BORDER)) | (points[bi*4+3] & RC_BORDER_VERTEX); - } - -} - -static int calcAreaOfPolygon2D(const int* verts, const int nverts) -{ - int area = 0; - for (int i = 0, j = nverts-1; i < nverts; j=i++) - { - const int* vi = &verts[i*4]; - const int* vj = &verts[j*4]; - area += vi[0] * vj[2] - vj[0] * vi[2]; - } - return (area+1) / 2; -} - -// 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 !x ^ !y; -} - -// 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) -{ - 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) - { - int ni = next(i, npts); - - if (vequal(&simplified[i*4], &simplified[ni*4])) - { - // 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); - 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) - { - int* dst = &verts[nv*4]; - const int* src = &ca.verts[((ia+i)%ca.nverts)*4]; - dst[0] = src[0]; - dst[1] = src[1]; - dst[2] = src[2]; - dst[3] = src[3]; - nv++; - } - - // Copy contour B - for (int i = 0; i <= cb.nverts; ++i) - { - int* dst = &verts[nv*4]; - const int* src = &cb.verts[((ib+i)%cb.nverts)*4]; - dst[0] = src[0]; - dst[1] = src[1]; - dst[2] = src[2]; - dst[3] = src[3]; - nv++; - } - - rcFree(ca.verts); - ca.verts = verts; - ca.nverts = nv; - - rcFree(cb.verts); - cb.verts = 0; - cb.nverts = 0; - - 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. -/// (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, - rcContourSet& cset, const int buildFlags) -{ - rcAssert(ctx); - - const int w = chf.width; - const int h = chf.height; - const int borderSize = chf.borderSize; - - rcScopedTimer timer(ctx, RC_TIMER_BUILD_CONTOURS); - - rcVcopy(cset.bmin, chf.bmin); - rcVcopy(cset.bmax, chf.bmax); - if (borderSize > 0) - { - // If the heightfield was build with bordersize, remove the offset. - const float pad = borderSize*chf.cs; - cset.bmin[0] += pad; - cset.bmin[2] += pad; - cset.bmax[0] -= pad; - cset.bmax[2] -= pad; - } - cset.cs = chf.cs; - cset.ch = chf.ch; - 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); - if (!cset.conts) - return false; - cset.nconts = 0; - - 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); - return false; - } - - ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE); - - // Mark boundaries. - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - unsigned char res = 0; - const rcCompactSpan& s = chf.spans[i]; - if (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG)) - { - flags[i] = 0; - continue; - } - for (int dir = 0; dir < 4; ++dir) - { - unsigned short r = 0; - 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*w].index + rcGetCon(s, dir); - r = chf.spans[ai].reg; - } - if (r == chf.spans[i].reg) - res |= (1 << dir); - } - flags[i] = res ^ 0xf; // Inverse, mark non connected edges. - } - } - } - - ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE); - - rcIntArray verts(256); - rcIntArray simplified(64); - - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - if (flags[i] == 0 || flags[i] == 0xf) - { - flags[i] = 0; - continue; - } - const unsigned short reg = chf.spans[i].reg; - if (!reg || (reg & RC_BORDER_REG)) - continue; - const unsigned char area = chf.areas[i]; - - 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) - { - if (cset.nconts >= maxContours) - { - // Allocate more contours. - // This happens when a region has holes. - const int oldMax = maxContours; - maxContours *= 2; - rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM); - for (int j = 0; j < cset.nconts; ++j) - { - newConts[j] = cset.conts[j]; - // Reset source pointers to prevent data deletion. - cset.conts[j].verts = 0; - cset.conts[j].rverts = 0; - } - 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; - cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM); - if (!cont->verts) - { - ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts); - return false; - } - memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4); - if (borderSize > 0) - { - // If the heightfield was build with bordersize, remove the offset. - for (int j = 0; j < cont->nverts; ++j) - { - int* v = &cont->verts[j*4]; - v[0] -= borderSize; - v[2] -= borderSize; - } - } - - cont->nrverts = verts.size()/4; - cont->rverts = (int*)rcAlloc(sizeof(int)*cont->nrverts*4, RC_ALLOC_PERM); - if (!cont->rverts) - { - ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts); - return false; - } - memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4); - if (borderSize > 0) - { - // If the heightfield was build with bordersize, remove the offset. - for (int j = 0; j < cont->nrverts; ++j) - { - int* v = &cont->rverts[j*4]; - v[0] -= borderSize; - v[2] -= borderSize; - } - } - - cont->reg = reg; - cont->area = area; - } - } - } - } - - // Merge holes if needed. - if (cset.nconts > 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) - { - // 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) - { - 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) - { - 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; - } - } - for (int i = 0; i < cset.nconts; ++i) - { - rcContour& cont = cset.conts[i]; - rcContourRegion& reg = regions[cont.reg]; - if (winding[i] < 0) - reg.holes[reg.nholes++].contour = &cont; - } - - // Finally merge each regions holes into the outline. - for (int i = 0; i < nregions; i++) - { - rcContourRegion& reg = regions[i]; - if (!reg.nholes) continue; - - if (reg.outline) - { - mergeRegionHoles(ctx, reg); - } - else - { - // 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); - } - } - } - - } - - return true; -} |