1 files changed, 93 insertions, 105 deletions

diff --git a/thirdparty/recastnavigation/Recast/Source/RecastRegion.cpp b/thirdparty/recastnavigation/Recast/Source/RecastRegion.cpp
index 38a2bd6bfa..e1fc0ee788 100644
--- a/thirdparty/recastnavigation/Recast/Source/RecastRegion.cpp
+++ b/thirdparty/recastnavigation/Recast/Source/RecastRegion.cpp
@@ -25,8 +25,17 @@
 #include "Recast.h"
 #include "RecastAlloc.h"
 #include "RecastAssert.h"
-#include <new>
 
+namespace
+{
+struct LevelStackEntry
+{
+	LevelStackEntry(int x_, int y_, int index_) : x(x_), y(y_), index(index_) {}
+	int x;
+	int y;
+	int index;
+};
+}  // namespace
 
 static void calculateDistanceField(rcCompactHeightfield& chf, unsigned short* src, unsigned short& maxDist)
 {
@@ -245,17 +254,15 @@ static bool floodRegion(int x, int y, int i,
 						unsigned short level, unsigned short r,
 						rcCompactHeightfield& chf,
 						unsigned short* srcReg, unsigned short* srcDist,
-						rcIntArray& stack)
+						rcTempVector<LevelStackEntry>& stack)
 {
 	const int w = chf.width;
 	
 	const unsigned char area = chf.areas[i];
 	
 	// Flood fill mark region.
-	stack.resize(0);
-	stack.push((int)x);
-	stack.push((int)y);
-	stack.push((int)i);
+	stack.clear();
+	stack.push_back(LevelStackEntry(x, y, i));
 	srcReg[i] = r;
 	srcDist[i] = 0;
 	
@@ -264,9 +271,11 @@ static bool floodRegion(int x, int y, int i,
 	
 	while (stack.size() > 0)
 	{
-		int ci = stack.pop();
-		int cy = stack.pop();
-		int cx = stack.pop();
+		LevelStackEntry& back = stack.back();
+		int cx = back.x;
+		int cy = back.y;
+		int ci = back.index;
+		stack.pop_back();
 		
 		const rcCompactSpan& cs = chf.spans[ci];
 		
@@ -332,9 +341,7 @@ static bool floodRegion(int x, int y, int i,
 				{
 					srcReg[ai] = r;
 					srcDist[ai] = 0;
-					stack.push(ax);
-					stack.push(ay);
-					stack.push(ai);
+					stack.push_back(LevelStackEntry(ax, ay, ai));
 				}
 			}
 		}
@@ -343,12 +350,20 @@ static bool floodRegion(int x, int y, int i,
 	return count > 0;
 }
 
-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,
-									 bool fillStack)
+// Struct to keep track of entries in the region table that have been changed.
+struct DirtyEntry
+{
+	DirtyEntry(int index_, unsigned short region_, unsigned short distance2_)
+		: index(index_), region(region_), distance2(distance2_) {}
+	int index;
+	unsigned short region;
+	unsigned short distance2;
+};
+static void expandRegions(int maxIter, unsigned short level,
+					      rcCompactHeightfield& chf,
+					      unsigned short* srcReg, unsigned short* srcDist,
+					      rcTempVector<LevelStackEntry>& stack,
+					      bool fillStack)
 {
 	const int w = chf.width;
 	const int h = chf.height;
@@ -356,7 +371,7 @@ static unsigned short* expandRegions(int maxIter, unsigned short level,
 	if (fillStack)
 	{
 		// Find cells revealed by the raised level.
-		stack.resize(0);
+		stack.clear();
 		for (int y = 0; y < h; ++y)
 		{
 			for (int x = 0; x < w; ++x)
@@ -366,9 +381,7 @@ static unsigned short* expandRegions(int maxIter, unsigned short level,
 				{
 					if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA)
 					{
-						stack.push(x);
-						stack.push(y);
-						stack.push(i);
+						stack.push_back(LevelStackEntry(x, y, i));
 					}
 				}
 			}
@@ -377,27 +390,26 @@ static unsigned short* expandRegions(int maxIter, unsigned short level,
 	else // use cells in the input stack
 	{
 		// mark all cells which already have a region
-		for (int j=0; j<stack.size(); j+=3)
+		for (int j=0; j<stack.size(); j++)
 		{
-			int i = stack[j+2];
+			int i = stack[j].index;
 			if (srcReg[i] != 0)
-				stack[j+2] = -1;
+				stack[j].index = -1;
 		}
 	}
 
+	rcTempVector<DirtyEntry> dirtyEntries;
 	int iter = 0;
 	while (stack.size() > 0)
 	{
 		int failed = 0;
+		dirtyEntries.clear();
 		
-		memcpy(dstReg, srcReg, sizeof(unsigned short)*chf.spanCount);
-		memcpy(dstDist, srcDist, sizeof(unsigned short)*chf.spanCount);
-		
-		for (int j = 0; j < stack.size(); j += 3)
+		for (int j = 0; j < stack.size(); j++)
 		{
-			int x = stack[j+0];
-			int y = stack[j+1];
-			int i = stack[j+2];
+			int x = stack[j].x;
+			int y = stack[j].y;
+			int i = stack[j].index;
 			if (i < 0)
 			{
 				failed++;
@@ -426,9 +438,8 @@ static unsigned short* expandRegions(int maxIter, unsigned short level,
 			}
 			if (r)
 			{
-				stack[j+2] = -1; // mark as used
-				dstReg[i] = r;
-				dstDist[i] = d2;
+				stack[j].index = -1; // mark as used
+				dirtyEntries.push_back(DirtyEntry(i, r, d2));
 			}
 			else
 			{
@@ -436,11 +447,14 @@ static unsigned short* expandRegions(int maxIter, unsigned short level,
 			}
 		}
 		
-		// rcSwap source and dest.
-		rcSwap(srcReg, dstReg);
-		rcSwap(srcDist, dstDist);
+		// Copy entries that differ between src and dst to keep them in sync.
+		for (int i = 0; i < dirtyEntries.size(); i++) {
+			int idx = dirtyEntries[i].index;
+			srcReg[idx] = dirtyEntries[i].region;
+			srcDist[idx] = dirtyEntries[i].distance2;
+		}
 		
-		if (failed*3 == stack.size())
+		if (failed == stack.size())
 			break;
 		
 		if (level > 0)
@@ -450,16 +464,14 @@ static unsigned short* expandRegions(int maxIter, unsigned short level,
 				break;
 		}
 	}
-	
-	return srcReg;
 }
 
 
 
 static void sortCellsByLevel(unsigned short startLevel,
 							  rcCompactHeightfield& chf,
-							  unsigned short* srcReg,
-							  unsigned int nbStacks, rcIntArray* stacks,
+							  const unsigned short* srcReg,
+							  unsigned int nbStacks, rcTempVector<LevelStackEntry>* stacks,
 							  unsigned short loglevelsPerStack) // the levels per stack (2 in our case) as a bit shift
 {
 	const int w = chf.width;
@@ -467,7 +479,7 @@ static void sortCellsByLevel(unsigned short startLevel,
 	startLevel = startLevel >> loglevelsPerStack;
 
 	for (unsigned int j=0; j<nbStacks; ++j)
-		stacks[j].resize(0);
+		stacks[j].clear();
 
 	// put all cells in the level range into the appropriate stacks
 	for (int y = 0; y < h; ++y)
@@ -487,26 +499,23 @@ static void sortCellsByLevel(unsigned short startLevel,
 				if (sId < 0)
 					sId = 0;
 
-				stacks[sId].push(x);
-				stacks[sId].push(y);
-				stacks[sId].push(i);
+				stacks[sId].push_back(LevelStackEntry(x, y, i));
 			}
 		}
 	}
 }
 
 
-static void appendStacks(rcIntArray& srcStack, rcIntArray& dstStack,
-						 unsigned short* srcReg)
+static void appendStacks(const rcTempVector<LevelStackEntry>& srcStack,
+						 rcTempVector<LevelStackEntry>& dstStack,
+						 const unsigned short* srcReg)
 {
-	for (int j=0; j<srcStack.size(); j+=3)
+	for (int j=0; j<srcStack.size(); j++)
 	{
-		int i = srcStack[j+2];
+		int i = srcStack[j].index;
 		if ((i < 0) || (srcReg[i] != 0))
 			continue;
-		dstStack.push(srcStack[j]);
-		dstStack.push(srcStack[j+1]);
-		dstStack.push(srcStack[j+2]);
+		dstStack.push_back(srcStack[j]);
 	}
 }
 
@@ -671,7 +680,7 @@ static bool isRegionConnectedToBorder(const rcRegion& reg)
 	return false;
 }
 
-static bool isSolidEdge(rcCompactHeightfield& chf, unsigned short* srcReg,
+static bool isSolidEdge(rcCompactHeightfield& chf, const unsigned short* srcReg,
 						int x, int y, int i, int dir)
 {
 	const rcCompactSpan& s = chf.spans[i];
@@ -690,7 +699,7 @@ static bool isSolidEdge(rcCompactHeightfield& chf, unsigned short* srcReg,
 
 static void walkContour(int x, int y, int i, int dir,
 						rcCompactHeightfield& chf,
-						unsigned short* srcReg,
+						const unsigned short* srcReg,
 						rcIntArray& cont)
 {
 	int startDir = dir;
@@ -786,16 +795,15 @@ static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRe
 	const int h = chf.height;
 	
 	const int nreg = maxRegionId+1;
-	rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP);
-	if (!regions)
-	{
+	rcTempVector<rcRegion> regions;
+	if (!regions.reserve(nreg)) {
 		ctx->log(RC_LOG_ERROR, "mergeAndFilterRegions: Out of memory 'regions' (%d).", nreg);
 		return false;
 	}
 
 	// Construct regions
 	for (int i = 0; i < nreg; ++i)
-		new(&regions[i]) rcRegion((unsigned short)i);
+		regions.push_back(rcRegion((unsigned short) i));
 	
 	// Find edge of a region and find connections around the contour.
 	for (int y = 0; y < h; ++y)
@@ -1021,11 +1029,6 @@ static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRe
 		if (regions[i].overlap)
 			overlaps.push(regions[i].id);
 
-	for (int i = 0; i < nreg; ++i)
-		regions[i].~rcRegion();
-	rcFree(regions);
-	
-	
 	return true;
 }
 
@@ -1041,22 +1044,21 @@ static void addUniqueConnection(rcRegion& reg, int n)
 static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea,
 									   unsigned short& maxRegionId,
 									   rcCompactHeightfield& chf,
-									   unsigned short* srcReg, rcIntArray& /*overlaps*/)
+									   unsigned short* srcReg)
 {
 	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)
-	{
+	rcTempVector<rcRegion> regions;
+	
+	// Construct regions
+	if (!regions.reserve(nreg)) {
 		ctx->log(RC_LOG_ERROR, "mergeAndFilterLayerRegions: Out of memory 'regions' (%d).", nreg);
 		return false;
 	}
-	
-	// Construct regions
 	for (int i = 0; i < nreg; ++i)
-		new(&regions[i]) rcRegion((unsigned short)i);
+		regions.push_back(rcRegion((unsigned short) i));
 	
 	// Find region neighbours and overlapping regions.
 	rcIntArray lregs(32);
@@ -1234,10 +1236,6 @@ static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea,
 			srcReg[i] = regions[srcReg[i]].id;
 	}
 	
-	for (int i = 0; i < nreg; ++i)
-		regions[i].~rcRegion();
-	rcFree(regions);
-	
 	return true;
 }
 
@@ -1391,9 +1389,9 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
 		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;
 	}
+
+	chf.borderSize = borderSize;
 	
 	rcIntArray prev(256);
 
@@ -1535,7 +1533,7 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 	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*2, RC_ALLOC_TEMP));
 	if (!buf)
 	{
 		ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4);
@@ -1546,17 +1544,15 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 
 	const int LOG_NB_STACKS = 3;
 	const int NB_STACKS = 1 << LOG_NB_STACKS;
-	rcIntArray lvlStacks[NB_STACKS];
+	rcTempVector<LevelStackEntry> lvlStacks[NB_STACKS];
 	for (int i=0; i<NB_STACKS; ++i)
-		lvlStacks[i].resize(1024);
+		lvlStacks[i].reserve(256);
 
-	rcIntArray stack(1024);
-	rcIntArray visited(1024);
+	rcTempVector<LevelStackEntry> stack;
+	stack.reserve(256);
 	
 	unsigned short* srcReg = buf;
 	unsigned short* srcDist = buf+chf.spanCount;
-	unsigned short* dstReg = buf+chf.spanCount*2;
-	unsigned short* dstDist = buf+chf.spanCount*3;
 	
 	memset(srcReg, 0, sizeof(unsigned short)*chf.spanCount);
 	memset(srcDist, 0, sizeof(unsigned short)*chf.spanCount);
@@ -1581,9 +1577,9 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 		paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
 		paintRectRegion(0, w, 0, bh, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
 		paintRectRegion(0, w, h-bh, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
-
-		chf.borderSize = borderSize;
 	}
+
+	chf.borderSize = borderSize;
 	
 	int sId = -1;
 	while (level > 0)
@@ -1604,22 +1600,19 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 			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);
-			}
+			expandRegions(expandIters, level, chf, srcReg, srcDist, lvlStacks[sId], false);
 		}
 		
 		{
 			rcScopedTimer timerFloor(ctx, RC_TIMER_BUILD_REGIONS_FLOOD);
 
 			// Mark new regions with IDs.
-			for (int j = 0; j<lvlStacks[sId].size(); j += 3)
+			for (int j = 0; j<lvlStacks[sId].size(); j++)
 			{
-				int x = lvlStacks[sId][j];
-				int y = lvlStacks[sId][j+1];
-				int i = lvlStacks[sId][j+2];
+				LevelStackEntry current = lvlStacks[sId][j];
+				int x = current.x;
+				int y = current.y;
+				int i = current.index;
 				if (i >= 0 && srcReg[i] == 0)
 				{
 					if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack))
@@ -1638,11 +1631,7 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 	}
 	
 	// Expand current regions until no empty connected cells found.
-	if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack, true) != srcReg)
-	{
-		rcSwap(srcReg, dstReg);
-		rcSwap(srcDist, dstDist);
-	}
+	expandRegions(expandIters*8, 0, chf, srcReg, srcDist, stack, true);
 	
 	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);
 	
@@ -1709,9 +1698,9 @@ bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
 		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;
 	}
+
+	chf.borderSize = borderSize;
 	
 	rcIntArray prev(256);
 	
@@ -1809,9 +1798,8 @@ bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
 		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))
+		if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg))
 			return false;
 	}