diff options
Diffstat (limited to 'extern/recastnavigation/Recast/Source/RecastRegion.cpp')
-rw-r--r-- | extern/recastnavigation/Recast/Source/RecastRegion.cpp | 693 |
1 files changed, 593 insertions, 100 deletions
diff --git a/extern/recastnavigation/Recast/Source/RecastRegion.cpp b/extern/recastnavigation/Recast/Source/RecastRegion.cpp index 4290972ed24..54acf4b736b 100644 --- a/extern/recastnavigation/Recast/Source/RecastRegion.cpp +++ b/extern/recastnavigation/Recast/Source/RecastRegion.cpp @@ -286,7 +286,10 @@ static bool floodRegion(int x, int y, int i, if (nr & RC_BORDER_REG) // Do not take borders into account. continue; if (nr != 0 && nr != r) + { ar = nr; + break; + } const rcCompactSpan& as = chf.spans[ai]; @@ -298,9 +301,12 @@ static bool floodRegion(int x, int y, int i, const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2); if (chf.areas[ai2] != area) continue; - unsigned short nr = srcReg[ai2]; - if (nr != 0 && nr != r) - ar = nr; + unsigned short nr2 = srcReg[ai2]; + if (nr2 != 0 && nr2 != r) + { + ar = nr2; + break; + } } } } @@ -309,6 +315,7 @@ static bool floodRegion(int x, int y, int i, srcReg[ci] = 0; continue; } + count++; // Expand neighbours. @@ -340,30 +347,44 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, rcCompactHeightfield& chf, unsigned short* srcReg, unsigned short* srcDist, unsigned short* dstReg, unsigned short* dstDist, - rcIntArray& stack) + rcIntArray& stack, + bool fillStack) { const int w = chf.width; const int h = chf.height; - // Find cells revealed by the raised level. - stack.resize(0); - for (int y = 0; y < h; ++y) + if (fillStack) { - for (int x = 0; x < w; ++x) + // Find cells revealed by the raised level. + stack.resize(0); + for (int y = 0; y < h; ++y) { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + for (int x = 0; x < w; ++x) { - if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA) + const rcCompactCell& c = chf.cells[x+y*w]; + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) { - stack.push(x); - stack.push(y); - stack.push(i); + if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA) + { + stack.push(x); + stack.push(y); + stack.push(i); + } } } } } - + else // use cells in the input stack + { + // mark all cells which already have a region + for (int j=0; j<stack.size(); j+=3) + { + int i = stack[j+2]; + if (srcReg[i] != 0) + stack[j+2] = -1; + } + } + int iter = 0; while (stack.size() > 0) { @@ -434,6 +455,61 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, } + +static void sortCellsByLevel(unsigned short startLevel, + rcCompactHeightfield& chf, + unsigned short* srcReg, + unsigned int nbStacks, rcIntArray* stacks, + unsigned short loglevelsPerStack) // the levels per stack (2 in our case) as a bit shift +{ + const int w = chf.width; + const int h = chf.height; + startLevel = startLevel >> loglevelsPerStack; + + for (unsigned int j=0; j<nbStacks; ++j) + stacks[j].resize(0); + + // put all cells in the level range into the appropriate stacks + 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 (chf.areas[i] == RC_NULL_AREA || srcReg[i] != 0) + continue; + + int level = chf.dist[i] >> loglevelsPerStack; + int sId = startLevel - level; + if (sId >= (int)nbStacks) + continue; + if (sId < 0) + sId = 0; + + stacks[sId].push(x); + stacks[sId].push(y); + stacks[sId].push(i); + } + } + } +} + + +static void appendStacks(rcIntArray& srcStack, rcIntArray& dstStack, + unsigned short* srcReg) +{ + for (int j=0; j<srcStack.size(); j+=3) + { + int i = srcStack[j+2]; + if ((i < 0) || (srcReg[i] != 0)) + continue; + dstStack.push(srcStack[j]); + dstStack.push(srcStack[j+1]); + dstStack.push(srcStack[j+2]); + } +} + struct rcRegion { inline rcRegion(unsigned short i) : @@ -441,7 +517,11 @@ struct rcRegion id(i), areaType(0), remap(false), - visited(false) + visited(false), + overlap(false), + connectsToBorder(false), + ymin(0xffff), + ymax(0) {} int spanCount; // Number of spans belonging to this region @@ -449,6 +529,9 @@ struct rcRegion unsigned char areaType; // Are type. bool remap; bool visited; + bool overlap; + bool connectsToBorder; + unsigned short ymin, ymax; rcIntArray connections; rcIntArray floors; }; @@ -678,25 +761,26 @@ static void walkContour(int x, int y, int i, int dir, // Remove adjacent duplicates. if (cont.size() > 1) { - for (int i = 0; i < cont.size(); ) + for (int j = 0; j < cont.size(); ) { - int ni = (i+1) % cont.size(); - if (cont[i] == cont[ni]) + int nj = (j+1) % cont.size(); + if (cont[j] == cont[nj]) { - for (int j = i; j < cont.size()-1; ++j) - cont[j] = cont[j+1]; + for (int k = j; k < cont.size()-1; ++k) + cont[k] = cont[k+1]; cont.pop(); } else - ++i; + ++j; } } } -static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize, - unsigned short& maxRegionId, - rcCompactHeightfield& chf, - unsigned short* srcReg) + +static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize, + unsigned short& maxRegionId, + rcCompactHeightfield& chf, + unsigned short* srcReg, rcIntArray& overlaps) { const int w = chf.width; const int h = chf.height; @@ -705,7 +789,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP); if (!regions) { - ctx->log(RC_LOG_ERROR, "filterSmallRegions: Out of memory 'regions' (%d).", nreg); + ctx->log(RC_LOG_ERROR, "mergeAndFilterRegions: Out of memory 'regions' (%d).", nreg); return false; } @@ -728,7 +812,6 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio rcRegion& reg = regions[r]; reg.spanCount++; - // Update floors. for (int j = (int)c.index; j < ni; ++j) { @@ -736,6 +819,8 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio unsigned short floorId = srcReg[j]; if (floorId == 0 || floorId >= nreg) continue; + if (floorId == r) + reg.overlap = true; addUniqueFloorRegion(reg, floorId); } @@ -806,14 +891,14 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio connectsToBorder = true; continue; } - rcRegion& nreg = regions[creg.connections[j]]; - if (nreg.visited) + rcRegion& neireg = regions[creg.connections[j]]; + if (neireg.visited) continue; - if (nreg.id == 0 || (nreg.id & RC_BORDER_REG)) + if (neireg.id == 0 || (neireg.id & RC_BORDER_REG)) continue; // Visit - stack.push(nreg.id); - nreg.visited = true; + stack.push(neireg.id); + neireg.visited = true; } } @@ -831,7 +916,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio } } } - + // Merge too small regions to neighbour regions. int mergeCount = 0 ; do @@ -841,7 +926,9 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio { rcRegion& reg = regions[i]; if (reg.id == 0 || (reg.id & RC_BORDER_REG)) - continue; + continue; + if (reg.overlap) + continue; if (reg.spanCount == 0) continue; @@ -858,7 +945,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio { if (reg.connections[j] & RC_BORDER_REG) continue; rcRegion& mreg = regions[reg.connections[j]]; - if (mreg.id == 0 || (mreg.id & RC_BORDER_REG)) continue; + if (mreg.id == 0 || (mreg.id & RC_BORDER_REG) || mreg.overlap) continue; if (mreg.spanCount < smallest && canMergeWithRegion(reg, mreg) && canMergeWithRegion(mreg, reg)) @@ -928,6 +1015,224 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio if ((srcReg[i] & RC_BORDER_REG) == 0) srcReg[i] = regions[srcReg[i]].id; } + + // Return regions that we found to be overlapping. + for (int i = 0; i < nreg; ++i) + if (regions[i].overlap) + overlaps.push(regions[i].id); + + for (int i = 0; i < nreg; ++i) + regions[i].~rcRegion(); + rcFree(regions); + + + return true; +} + + +static void addUniqueConnection(rcRegion& reg, int n) +{ + for (int i = 0; i < reg.connections.size(); ++i) + if (reg.connections[i] == n) + return; + reg.connections.push(n); +} + +static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea, + unsigned short& maxRegionId, + rcCompactHeightfield& chf, + unsigned short* srcReg, rcIntArray& /*overlaps*/) +{ + const int w = chf.width; + const int h = chf.height; + + const int nreg = maxRegionId+1; + rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP); + if (!regions) + { + ctx->log(RC_LOG_ERROR, "mergeAndFilterLayerRegions: Out of memory 'regions' (%d).", nreg); + return false; + } + + // Construct regions + for (int i = 0; i < nreg; ++i) + new(®ions[i]) rcRegion((unsigned short)i); + + // Find region neighbours and overlapping regions. + rcIntArray lregs(32); + for (int y = 0; y < h; ++y) + { + for (int x = 0; x < w; ++x) + { + const rcCompactCell& c = chf.cells[x+y*w]; + + lregs.resize(0); + + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + { + const rcCompactSpan& s = chf.spans[i]; + const unsigned short ri = srcReg[i]; + if (ri == 0 || ri >= nreg) continue; + rcRegion& reg = regions[ri]; + + reg.spanCount++; + + reg.ymin = rcMin(reg.ymin, s.y); + reg.ymax = rcMax(reg.ymax, s.y); + + // Collect all region layers. + lregs.push(ri); + + // Update neighbours + 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*w].index + rcGetCon(s, dir); + const unsigned short rai = srcReg[ai]; + if (rai > 0 && rai < nreg && rai != ri) + addUniqueConnection(reg, rai); + if (rai & RC_BORDER_REG) + reg.connectsToBorder = true; + } + } + + } + + // Update overlapping regions. + for (int i = 0; i < lregs.size()-1; ++i) + { + for (int j = i+1; j < lregs.size(); ++j) + { + if (lregs[i] != lregs[j]) + { + rcRegion& ri = regions[lregs[i]]; + rcRegion& rj = regions[lregs[j]]; + addUniqueFloorRegion(ri, lregs[j]); + addUniqueFloorRegion(rj, lregs[i]); + } + } + } + + } + } + + // Create 2D layers from regions. + unsigned short layerId = 1; + + for (int i = 0; i < nreg; ++i) + regions[i].id = 0; + + // Merge montone regions to create non-overlapping areas. + rcIntArray stack(32); + for (int i = 1; i < nreg; ++i) + { + rcRegion& root = regions[i]; + // Skip already visited. + if (root.id != 0) + continue; + + // Start search. + root.id = layerId; + + stack.resize(0); + stack.push(i); + + while (stack.size() > 0) + { + // Pop front + rcRegion& reg = regions[stack[0]]; + for (int j = 0; j < stack.size()-1; ++j) + stack[j] = stack[j+1]; + stack.resize(stack.size()-1); + + const int ncons = (int)reg.connections.size(); + for (int j = 0; j < ncons; ++j) + { + const int nei = reg.connections[j]; + rcRegion& regn = regions[nei]; + // Skip already visited. + if (regn.id != 0) + continue; + // Skip if the neighbour is overlapping root region. + bool overlap = false; + for (int k = 0; k < root.floors.size(); k++) + { + if (root.floors[k] == nei) + { + overlap = true; + break; + } + } + if (overlap) + continue; + + // Deepen + stack.push(nei); + + // Mark layer id + regn.id = layerId; + // Merge current layers to root. + for (int k = 0; k < regn.floors.size(); ++k) + addUniqueFloorRegion(root, regn.floors[k]); + root.ymin = rcMin(root.ymin, regn.ymin); + root.ymax = rcMax(root.ymax, regn.ymax); + root.spanCount += regn.spanCount; + regn.spanCount = 0; + root.connectsToBorder = root.connectsToBorder || regn.connectsToBorder; + } + } + + layerId++; + } + + // Remove small regions + for (int i = 0; i < nreg; ++i) + { + if (regions[i].spanCount > 0 && regions[i].spanCount < minRegionArea && !regions[i].connectsToBorder) + { + unsigned short reg = regions[i].id; + for (int j = 0; j < nreg; ++j) + if (regions[j].id == reg) + regions[j].id = 0; + } + } + + // Compress region Ids. + for (int i = 0; i < nreg; ++i) + { + regions[i].remap = false; + if (regions[i].id == 0) continue; // Skip nil regions. + if (regions[i].id & RC_BORDER_REG) continue; // Skip external regions. + regions[i].remap = true; + } + + unsigned short regIdGen = 0; + for (int i = 0; i < nreg; ++i) + { + if (!regions[i].remap) + continue; + unsigned short oldId = regions[i].id; + unsigned short newId = ++regIdGen; + for (int j = i; j < nreg; ++j) + { + if (regions[j].id == oldId) + { + regions[j].id = newId; + regions[j].remap = false; + } + } + } + maxRegionId = regIdGen; + + // Remap regions. + for (int i = 0; i < chf.spanCount; ++i) + { + if ((srcReg[i] & RC_BORDER_REG) == 0) + srcReg[i] = regions[srcReg[i]].id; + } for (int i = 0; i < nreg; ++i) regions[i].~rcRegion(); @@ -936,6 +1241,8 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio return true; } + + /// @par /// /// This is usually the second to the last step in creating a fully built @@ -950,7 +1257,7 @@ bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf) { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_DISTANCEFIELD); if (chf.dist) { @@ -974,25 +1281,23 @@ bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf) unsigned short maxDist = 0; - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST); - - calculateDistanceField(chf, src, maxDist); - chf.maxDistance = maxDist; - - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST); - - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR); - - // Blur - if (boxBlur(chf, 1, src, dst) != src) - rcSwap(src, dst); - - // Store distance. - chf.dist = src; - - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR); + { + rcScopedTimer timerDist(ctx, RC_TIMER_BUILD_DISTANCEFIELD_DIST); - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD); + calculateDistanceField(chf, src, maxDist); + chf.maxDistance = maxDist; + } + + { + rcScopedTimer timerBlur(ctx, RC_TIMER_BUILD_DISTANCEFIELD_BLUR); + + // Blur + if (boxBlur(chf, 1, src, dst) != src) + rcSwap(src, dst); + + // Store distance. + chf.dist = src; + } rcFree(dst); @@ -1052,13 +1357,13 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_REGIONS); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS); const int w = chf.width; const int h = chf.height; unsigned short id = 1; - rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP); + rcScopedDelete<unsigned short> srcReg((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP)); if (!srcReg) { ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount); @@ -1067,7 +1372,7 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, memset(srcReg,0,sizeof(unsigned short)*chf.spanCount); const int nsweeps = rcMax(chf.width,chf.height); - rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP); + rcScopedDelete<rcSweepSpan> sweeps((rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP)); if (!sweeps) { ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps); @@ -1181,20 +1486,22 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, } } - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); - // Filter out small regions. - chf.maxRegions = id; - if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg)) - return false; + { + rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER); - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER); + // Merge regions and filter out small regions. + rcIntArray overlaps; + chf.maxRegions = id; + if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps)) + return false; + + // Monotone partitioning does not generate overlapping regions. + } // Store the result out. for (int i = 0; i < chf.spanCount; ++i) chf.spans[i].reg = srcReg[i]; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS); return true; } @@ -1223,12 +1530,12 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_REGIONS); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS); const int w = chf.width; const int h = chf.height; - rcScopedDelete<unsigned short> buf = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP); + rcScopedDelete<unsigned short> buf((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP)); if (!buf) { ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4); @@ -1236,7 +1543,13 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, } ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED); - + + const int LOG_NB_STACKS = 3; + const int NB_STACKS = 1 << LOG_NB_STACKS; + rcIntArray lvlStacks[NB_STACKS]; + for (int i=0; i<NB_STACKS; ++i) + lvlStacks[i].resize(1024); + rcIntArray stack(1024); rcIntArray visited(1024); @@ -1262,6 +1575,13 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, // Make sure border will not overflow. const int bw = rcMin(w, borderSize); const int bh = rcMin(h, borderSize); + + if (regionId > 0xFFFB) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegions: Region ID overflow"); + return false; + } + // Paint regions paintRectRegion(0, bw, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; @@ -1271,44 +1591,60 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, chf.borderSize = borderSize; } + int sId = -1; while (level > 0) { level = level >= 2 ? level-2 : 0; - - ctx->startTimer(RC_TIMER_BUILD_REGIONS_EXPAND); - - // Expand current regions until no empty connected cells found. - if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg) + sId = (sId+1) & (NB_STACKS-1); + +// ctx->startTimer(RC_TIMER_DIVIDE_TO_LEVELS); + + if (sId == 0) + sortCellsByLevel(level, chf, srcReg, NB_STACKS, lvlStacks, 1); + else + appendStacks(lvlStacks[sId-1], lvlStacks[sId], srcReg); // copy left overs from last level + +// ctx->stopTimer(RC_TIMER_DIVIDE_TO_LEVELS); + { - rcSwap(srcReg, dstReg); - rcSwap(srcDist, dstDist); + rcScopedTimer timerExpand(ctx, RC_TIMER_BUILD_REGIONS_EXPAND); + + // Expand current regions until no empty connected cells found. + if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, lvlStacks[sId], false) != srcReg) + { + rcSwap(srcReg, dstReg); + rcSwap(srcDist, dstDist); + } } - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_EXPAND); - - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FLOOD); - - // Mark new regions with IDs. - for (int y = 0; y < h; ++y) { - for (int x = 0; x < w; ++x) + rcScopedTimer timerFloor(ctx, RC_TIMER_BUILD_REGIONS_FLOOD); + + // Mark new regions with IDs. + for (int j = 0; j<lvlStacks[sId].size(); j += 3) { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + int x = lvlStacks[sId][j]; + int y = lvlStacks[sId][j+1]; + int i = lvlStacks[sId][j+2]; + if (i >= 0 && srcReg[i] == 0) { - if (chf.dist[i] < level || srcReg[i] != 0 || chf.areas[i] == RC_NULL_AREA) - continue; if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack)) + { + if (regionId == 0xFFFF) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegions: Region ID overflow"); + return false; + } + regionId++; + } } } } - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FLOOD); } // Expand current regions until no empty connected cells found. - if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg) + if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack, true) != srcReg) { rcSwap(srcReg, dstReg); rcSwap(srcDist, dstDist); @@ -1316,22 +1652,179 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED); - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); - - // Filter out small regions. - chf.maxRegions = regionId; - if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg)) - return false; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER); + { + rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER); + + // Merge regions and filter out smalle regions. + rcIntArray overlaps; + chf.maxRegions = regionId; + if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps)) + return false; + + // If overlapping regions were found during merging, split those regions. + if (overlaps.size() > 0) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegions: %d overlapping regions.", overlaps.size()); + } + } // Write the result out. for (int i = 0; i < chf.spanCount; ++i) chf.spans[i].reg = srcReg[i]; - ctx->stopTimer(RC_TIMER_BUILD_REGIONS); - return true; } +bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, + const int borderSize, const int minRegionArea) +{ + rcAssert(ctx); + + rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS); + + const int w = chf.width; + const int h = chf.height; + unsigned short id = 1; + + rcScopedDelete<unsigned short> srcReg((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP)); + if (!srcReg) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount); + return false; + } + memset(srcReg,0,sizeof(unsigned short)*chf.spanCount); + + const int nsweeps = rcMax(chf.width,chf.height); + rcScopedDelete<rcSweepSpan> sweeps((rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP)); + if (!sweeps) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps); + return false; + } + + + // Mark border regions. + if (borderSize > 0) + { + // Make sure border will not overflow. + const int bw = rcMin(w, borderSize); + const int bh = rcMin(h, borderSize); + // Paint regions + paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++; + paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++; + paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++; + paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++; + + chf.borderSize = borderSize; + } + + rcIntArray prev(256); + + // Sweep one line at a time. + for (int y = borderSize; y < h-borderSize; ++y) + { + // Collect spans from this row. + prev.resize(id+1); + memset(&prev[0],0,sizeof(int)*id); + unsigned short rid = 1; + + for (int x = borderSize; x < w-borderSize; ++x) + { + const rcCompactCell& c = chf.cells[x+y*w]; + + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + { + const rcCompactSpan& s = chf.spans[i]; + if (chf.areas[i] == RC_NULL_AREA) continue; + + // -x + unsigned short previd = 0; + if (rcGetCon(s, 0) != RC_NOT_CONNECTED) + { + const int ax = x + rcGetDirOffsetX(0); + const int ay = y + rcGetDirOffsetY(0); + const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0); + if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai]) + previd = srcReg[ai]; + } + + if (!previd) + { + previd = rid++; + sweeps[previd].rid = previd; + sweeps[previd].ns = 0; + sweeps[previd].nei = 0; + } + + // -y + if (rcGetCon(s,3) != RC_NOT_CONNECTED) + { + const int ax = x + rcGetDirOffsetX(3); + const int ay = y + rcGetDirOffsetY(3); + const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3); + if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai]) + { + unsigned short nr = srcReg[ai]; + if (!sweeps[previd].nei || sweeps[previd].nei == nr) + { + sweeps[previd].nei = nr; + sweeps[previd].ns++; + prev[nr]++; + } + else + { + sweeps[previd].nei = RC_NULL_NEI; + } + } + } + + srcReg[i] = previd; + } + } + + // Create unique ID. + for (int i = 1; i < rid; ++i) + { + if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 && + prev[sweeps[i].nei] == (int)sweeps[i].ns) + { + sweeps[i].id = sweeps[i].nei; + } + else + { + sweeps[i].id = id++; + } + } + + // Remap IDs + for (int x = borderSize; x < w-borderSize; ++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 (srcReg[i] > 0 && srcReg[i] < rid) + srcReg[i] = sweeps[srcReg[i]].id; + } + } + } + + + { + rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER); + + // Merge monotone regions to layers and remove small regions. + rcIntArray overlaps; + chf.maxRegions = id; + if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg, overlaps)) + return false; + } + + + // Store the result out. + for (int i = 0; i < chf.spanCount; ++i) + chf.spans[i].reg = srcReg[i]; + + return true; +} |