Core/MMAPs: Update recast

Update recast to https://github.com/memononen/recastnavigation/commit/42b96b7306d39bb7680ddb0f89d480a8296c83ff
Previous MMAPs might still work but it's recommended to re-extract them.

5 files changed, 1077 insertions, 252 deletions

diff --git a/dep/recastnavigation/Recast/Source/RecastContour.cpp b/dep/recastnavigation/Recast/Source/RecastContour.cpp
index 5c324bcedfe..8aa9d1d92a1 100644
--- a/dep/recastnavigation/Recast/Source/RecastContour.cpp
+++ b/dep/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 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.
@@ -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 maxi = -1;
 			int ci = (ai+1) % pn;
-
+			
 			// Tessellate only outer edges or edges between areas.
 			bool tess = false;
 			// Wall edges.
@@ -469,32 +451,6 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
 	
 }
 
-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;
@@ -507,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.
+
+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)
 {
-	return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]) <= 0;
+	// 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 void getClosestIndices(const int* vertsa, const int nvertsa,
-							  const int* vertsb, const int nvertsb,
-							  int& ia, int& ib)
+static bool	inCone(int i, int n, const int* verts, const int* pj)
 {
-	int closestDist = 0xfffffff;
-	ia = -1, ib = -1;
-	for (int i = 0; i < nvertsa; ++i)
+	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)
 	{
@@ -582,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;
@@ -590,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, &region.holes[i].minx, &region.holes[i].minz, &region.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,
@@ -704,17 +922,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)
@@ -722,7 +940,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);
@@ -735,10 +953,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;
@@ -779,17 +997,6 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
 						}
 					}
 					
-/*					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;
 				}
@@ -797,52 +1004,100 @@ 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)
 		{
-			// Find another contour which has the same region ID.
-			int mergeIdx = -1;
-			for (int j = 0; j < cset.nconts; ++j)
+			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)
 			{
-				if (i == j) continue;
-				if (cset.conts[j].nverts && cset.conts[j].reg == cont.reg)
+				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++;
 				}
 			}
-			if (mergeIdx == -1)
+			int index = 0;
+			for (int i = 0; i < nregions; i++)
 			{
-				ctx->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i);
+				if (regions[i].nholes > 0)
+				{
+					regions[i].holes = &holes[index];
+					index += regions[i].nholes;
+					regions[i].nholes = 0;
+				}
 			}
-			else
+			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++)
 			{
-				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);
diff --git a/dep/recastnavigation/Recast/Source/RecastLayers.cpp b/dep/recastnavigation/Recast/Source/RecastLayers.cpp
index 204f72e8cb2..cb1a39f4bda 100644
--- a/dep/recastnavigation/Recast/Source/RecastLayers.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastLayers.cpp
@@ -38,7 +38,7 @@ struct rcLayerRegion
 	unsigned char layerId;		// Layer ID
 	unsigned char nlayers;		// Layer count
 	unsigned char nneis;		// Neighbour count
-	unsigned char base;			// Flag indicating if the region is hte base of merged regions.
+	unsigned char base;			// Flag indicating if the region is the base of merged regions.
 };
 
 
diff --git a/dep/recastnavigation/Recast/Source/RecastMesh.cpp b/dep/recastnavigation/Recast/Source/RecastMesh.cpp
index 8af609b79fb..e4f9c4b3629 100644
--- a/dep/recastnavigation/Recast/Source/RecastMesh.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastMesh.cpp
@@ -288,6 +288,53 @@ static bool diagonal(int i, int j, int n, const int* verts, int* indices)
 	return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices);
 }
 
+
+static bool diagonalieLoose(int i, int j, int n, const int* verts, int* indices)
+{
+	const int* d0 = &verts[(indices[i] & 0x0fffffff) * 4];
+	const int* d1 = &verts[(indices[j] & 0x0fffffff) * 4];
+	
+	// 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 or j
+		if (!((k == i) || (k1 == i) || (k == j) || (k1 == j)))
+		{
+			const int* p0 = &verts[(indices[k] & 0x0fffffff) * 4];
+			const int* p1 = &verts[(indices[k1] & 0x0fffffff) * 4];
+			
+			if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
+				continue;
+			
+			if (intersectProp(d0, d1, p0, p1))
+				return false;
+		}
+	}
+	return true;
+}
+
+static bool	inConeLoose(int i, int j, int n, const int* verts, int* indices)
+{
+	const int* pi = &verts[(indices[i] & 0x0fffffff) * 4];
+	const int* pj = &verts[(indices[j] & 0x0fffffff) * 4];
+	const int* pi1 = &verts[(indices[next(i, n)] & 0x0fffffff) * 4];
+	const int* pin1 = &verts[(indices[prev(i, n)] & 0x0fffffff) * 4];
+	
+	// If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
+	if (leftOn(pin1, pi, pi1))
+		return leftOn(pi, pj, pin1) && leftOn(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 bool diagonalLoose(int i, int j, int n, const int* verts, int* indices)
+{
+	return inConeLoose(i, j, n, verts, indices) && diagonalieLoose(i, j, n, verts, indices);
+}
+
+
 static int triangulate(int n, const int* verts, int* indices, int* tris)
 {
 	int ntris = 0;
@@ -328,14 +375,41 @@ static int triangulate(int n, const int* verts, int* indices, int* tris)
 		
 		if (mini == -1)
 		{
-			// Should not happen.
-/*			printf("mini == -1 ntris=%d n=%d\n", ntris, n);
+			// We might get here because the contour has overlapping segments, like this:
+			//
+			//  A o-o=====o---o B
+			//   /  |C   D|    \
+			//  o   o     o     o
+			//  :   :     :     :
+			// We'll try to recover by loosing up the inCone test a bit so that a diagonal
+			// like A-B or C-D can be found and we can continue.
+			minLen = -1;
+			mini = -1;
 			for (int i = 0; i < n; i++)
 			{
-				printf("%d ", indices[i] & 0x0fffffff);
+				int i1 = next(i, n);
+				int i2 = next(i1, n);
+				if (diagonalLoose(i, i2, n, verts, indices))
+				{
+					const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4];
+					const int* p2 = &verts[(indices[next(i2, n)] & 0x0fffffff) * 4];
+					int dx = p2[0] - p0[0];
+					int dy = p2[2] - p0[2];
+					int len = dx*dx + dy*dy;
+					
+					if (minLen < 0 || len < minLen)
+					{
+						minLen = len;
+						mini = i;
+					}
+				}
+			}
+			if (mini == -1)
+			{
+				// The contour is messed up. This sometimes happens
+				// if the contour simplification is too aggressive.
+				return -ntris;
 			}
-			printf("\n");*/
-			return -ntris;
 		}
 		
 		int i = mini;
@@ -1463,7 +1537,7 @@ bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst)
 		ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.flags' (%d).", src.npolys);
 		return false;
 	}
-	memcpy(dst.flags, src.flags, sizeof(unsigned char)*src.npolys);
+	memcpy(dst.flags, src.flags, sizeof(unsigned short)*src.npolys);
 	
 	return true;
 }
diff --git a/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp b/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp
index 8325b883707..5cc2adf0320 100644
--- a/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp
@@ -56,7 +56,7 @@ inline float vdist2(const float* p, const float* q)
 }
 
 inline float vcross2(const float* p1, const float* p2, const float* p3)
-{ 
+{
 	const float u1 = p2[0] - p1[0];
 	const float v1 = p2[2] - p1[2];
 	const float u2 = p3[0] - p1[0];
@@ -68,21 +68,27 @@ static bool circumCircle(const float* p1, const float* p2, const float* p3,
 						 float* c, float& r)
 {
 	static const float EPS = 1e-6f;
+	// Calculate the circle relative to p1, to avoid some precision issues.
+	const float v1[3] = {0,0,0};
+	float v2[3], v3[3];
+	rcVsub(v2, p2,p1);
+	rcVsub(v3, p3,p1);
 	
-	const float cp = vcross2(p1, p2, p3);
+	const float cp = vcross2(v1, v2, v3);
 	if (fabsf(cp) > EPS)
 	{
-		const float p1Sq = vdot2(p1,p1);
-		const float p2Sq = vdot2(p2,p2);
-		const float p3Sq = vdot2(p3,p3);
-		c[0] = (p1Sq*(p2[2]-p3[2]) + p2Sq*(p3[2]-p1[2]) + p3Sq*(p1[2]-p2[2])) / (2*cp);
-		c[2] = (p1Sq*(p3[0]-p2[0]) + p2Sq*(p1[0]-p3[0]) + p3Sq*(p2[0]-p1[0])) / (2*cp);
-		r = vdist2(c, p1);
+		const float v1Sq = vdot2(v1,v1);
+		const float v2Sq = vdot2(v2,v2);
+		const float v3Sq = vdot2(v3,v3);
+		c[0] = (v1Sq*(v2[2]-v3[2]) + v2Sq*(v3[2]-v1[2]) + v3Sq*(v1[2]-v2[2])) / (2*cp);
+		c[1] = 0;
+		c[2] = (v1Sq*(v3[0]-v2[0]) + v2Sq*(v1[0]-v3[0]) + v3Sq*(v2[0]-v1[0])) / (2*cp);
+		r = vdist2(c, v1);
+		rcVadd(c, c, p1);
 		return true;
 	}
-
-	c[0] = p1[0];
-	c[2] = p1[2];
+	
+	rcVcopy(c, p1);
 	r = 0;
 	return false;
 }
@@ -93,7 +99,7 @@ static float distPtTri(const float* p, const float* a, const float* b, const flo
 	rcVsub(v0, c,a);
 	rcVsub(v1, b,a);
 	rcVsub(v2, p,a);
-
+	
 	const float dot00 = vdot2(v0, v0);
 	const float dot01 = vdot2(v0, v1);
 	const float dot02 = vdot2(v0, v2);
@@ -178,7 +184,7 @@ static float distToTriMesh(const float* p, const float* verts, const int /*nvert
 
 static float distToPoly(int nvert, const float* verts, const float* p)
 {
-
+	
 	float dmin = FLT_MAX;
 	int i, j, c = 0;
 	for (i = 0, j = nvert-1; i < nvert; j = i++)
@@ -216,22 +222,13 @@ static unsigned short getHeight(const float fx, const float fy, const float fz,
 			if (nx < 0 || nz < 0 || nx >= hp.width || nz >= hp.height) continue;
 			const unsigned short nh = hp.data[nx+nz*hp.width];
 			if (nh == RC_UNSET_HEIGHT) continue;
-
+			
 			const float d = fabsf(nh*ch - fy);
 			if (d < dmin)
 			{
 				h = nh;
 				dmin = d;
 			}
-			
-/*			const float dx = (nx+0.5f)*cs - fx; 
-			const float dz = (nz+0.5f)*cs - fz;
-			const float d = dx*dx+dz*dz;
-			if (d < dmin)
-			{
-				h = nh;
-				dmin = d;
-			} */
 		}
 	}
 	return h;
@@ -263,7 +260,7 @@ static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges,
 		return UNDEF;
 	}
 	
-	// Add edge if not already in the triangulation. 
+	// Add edge if not already in the triangulation.
 	int e = findEdge(edges, nedges, s, t);
 	if (e == UNDEF)
 	{
@@ -286,7 +283,7 @@ static void updateLeftFace(int* e, int s, int t, int f)
 		e[2] = f;
 	else if (e[1] == s && e[0] == t && e[3] == UNDEF)
 		e[3] = f;
-}	
+}
 
 static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d)
 {
@@ -298,7 +295,7 @@ static int overlapSegSeg2d(const float* a, const float* b, const float* c, const
 		float a4 = a3 + a2 - a1;
 		if (a3 * a4 < 0.0f)
 			return 1;
-	}	
+	}
 	return 0;
 }
 
@@ -320,7 +317,7 @@ static bool overlapEdges(const float* pts, const int* edges, int nedges, int s1,
 static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e)
 {
 	static const float EPS = 1e-5f;
-
+	
 	int* edge = &edges[e*4];
 	
 	// Cache s and t.
@@ -337,11 +334,11 @@ static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges
 	}
 	else
 	{
-	    // Edge already completed. 
+	    // Edge already completed.
 	    return;
 	}
     
-	// Find best point on left of edge. 
+	// Find best point on left of edge.
 	int pt = npts;
 	float c[3] = {0,0,0};
 	float r = -1;
@@ -385,20 +382,20 @@ static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges
 		}
 	}
 	
-	// Add new triangle or update edge info if s-t is on hull. 
+	// Add new triangle or update edge info if s-t is on hull.
 	if (pt < npts)
 	{
-		// Update face information of edge being completed. 
+		// Update face information of edge being completed.
 		updateLeftFace(&edges[e*4], s, t, nfaces);
 		
-		// Add new edge or update face info of old edge. 
+		// Add new edge or update face info of old edge.
 		e = findEdge(edges, nedges, pt, s);
 		if (e == UNDEF)
 		    addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, UNDEF);
 		else
 		    updateLeftFace(&edges[e*4], pt, s, nfaces);
 		
-		// Add new edge or update face info of old edge. 
+		// Add new edge or update face info of old edge.
 		e = findEdge(edges, nedges, t, pt);
 		if (e == UNDEF)
 		    addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, UNDEF);
@@ -434,7 +431,7 @@ static void delaunayHull(rcContext* ctx, const int npts, const float* pts,
 			completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge);
 		currentEdge++;
 	}
-
+	
 	// Create tris
 	tris.resize(nfaces*4);
 	for (int i = 0; i < nfaces*4; ++i)
@@ -489,6 +486,103 @@ static void delaunayHull(rcContext* ctx, const int npts, const float* pts,
 	}
 }
 
+// Calculate minimum extend of the polygon.
+static float polyMinExtent(const float* verts, const int nverts)
+{
+	float minDist = FLT_MAX;
+	for (int i = 0; i < nverts; i++)
+	{
+		const int ni = (i+1) % nverts;
+		const float* p1 = &verts[i*3];
+		const float* p2 = &verts[ni*3];
+		float maxEdgeDist = 0;
+		for (int j = 0; j < nverts; j++)
+		{
+			if (j == i || j == ni) continue;
+			float d = distancePtSeg2d(&verts[j*3], p1,p2);
+			maxEdgeDist = rcMax(maxEdgeDist, d);
+		}
+		minDist = rcMin(minDist, maxEdgeDist);
+	}
+	return rcSqrt(minDist);
+}
+
+inline int next(int i, int n)
+{
+	return (i+1) % n;
+}
+
+inline int prev(int i, int n)
+{
+	return (i + n-1) % n;
+}
+
+static void triangulateHull(const int nverts, const float* verts, const int nhull, const int* hull, rcIntArray& tris)
+{
+	int start = 0, left = 1, right = nhull-1;
+	
+	// Start from an ear with shortest perimeter.
+	// This tends to favor well formed triangles as starting point.
+	float dmin = 0;
+	for (int i = 0; i < nhull; i++)
+	{
+		int pi = prev(i, nhull);
+		int ni = next(i, nhull);
+		const float* pv = &verts[hull[pi]*3];
+		const float* cv = &verts[hull[i]*3];
+		const float* nv = &verts[hull[ni]*3];
+		const float d = vdist2(pv,cv) + vdist2(cv,nv) + vdist2(nv,pv);
+		if (d < dmin)
+		{
+			start = i;
+			left = ni;
+			right = pi;
+			dmin = d;
+		}
+	}
+	
+	// Add first triangle
+	tris.push(hull[start]);
+	tris.push(hull[left]);
+	tris.push(hull[right]);
+	tris.push(0);
+	
+	// Triangulate the polygon by moving left or right,
+	// depending on which triangle has shorter perimeter.
+	// This heuristic was chose emprically, since it seems
+	// handle tesselated straight edges well.
+	while (next(left, nhull) != right)
+	{
+		// Check to see if se should advance left or right.
+		int nleft = next(left, nhull);
+		int nright = prev(right, nhull);
+		
+		const float* cvleft = &verts[hull[left]*3];
+		const float* nvleft = &verts[hull[nleft]*3];
+		const float* cvright = &verts[hull[right]*3];
+		const float* nvright = &verts[hull[nright]*3];
+		const float dleft = vdist2(cvleft, nvleft) + vdist2(nvleft, cvright);
+		const float dright = vdist2(cvright, nvright) + vdist2(cvleft, nvright);
+		
+		if (dleft < dright)
+		{
+			tris.push(hull[left]);
+			tris.push(hull[nleft]);
+			tris.push(hull[right]);
+			tris.push(0);
+			left = nleft;
+		}
+		else
+		{
+			tris.push(hull[left]);
+			tris.push(hull[nright]);
+			tris.push(hull[right]);
+			tris.push(0);
+			right = nright;
+		}
+	}
+}
+
 
 inline float getJitterX(const int i)
 {
@@ -512,16 +606,22 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 	float edge[(MAX_VERTS_PER_EDGE+1)*3];
 	int hull[MAX_VERTS];
 	int nhull = 0;
-
+	
 	nverts = 0;
-
+	
 	for (int i = 0; i < nin; ++i)
 		rcVcopy(&verts[i*3], &in[i*3]);
 	nverts = nin;
 	
+	edges.resize(0);
+	tris.resize(0);
+	
 	const float cs = chf.cs;
 	const float ics = 1.0f/cs;
 	
+	// Calculate minimum extents of the polygon based on input data.
+	float minExtent = polyMinExtent(verts, nverts);
+	
 	// Tessellate outlines.
 	// This is done in separate pass in order to ensure
 	// seamless height values across the ply boundaries.
@@ -628,27 +728,26 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 		}
 	}
 	
-
+	// If the polygon minimum extent is small (sliver or small triangle), do not try to add internal points.
+	if (minExtent < sampleDist*2)
+	{
+		triangulateHull(nverts, verts, nhull, hull, tris);
+		return true;
+	}
+	
 	// Tessellate the base mesh.
-	edges.resize(0);
-	tris.resize(0);
-
-	delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges);
+	// We're using the triangulateHull instead of delaunayHull as it tends to
+	// create a bit better triangulation for long thing triangles when there
+	// are no internal points.
+	triangulateHull(nverts, verts, nhull, hull, tris);
 	
 	if (tris.size() == 0)
 	{
 		// Could not triangulate the poly, make sure there is some valid data there.
-		ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon, adding default data.");
-		for (int i = 2; i < nverts; ++i)
-		{
-			tris.push(0);
-			tris.push(i-1);
-			tris.push(i);
-			tris.push(0);
-		}
+		ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon (%d verts).", nverts);
 		return true;
 	}
-
+	
 	if (sampleDist > 0)
 	{
 		// Create sample locations in a grid.
@@ -681,7 +780,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 				samples.push(0); // Not added
 			}
 		}
-				
+		
 		// Add the samples starting from the one that has the most
 		// error. The procedure stops when all samples are added
 		// or when the max error is within treshold.
@@ -690,7 +789,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 		{
 			if (nverts >= MAX_VERTS)
 				break;
-
+			
 			// Find sample with most error.
 			float bestpt[3] = {0,0,0};
 			float bestd = 0;
@@ -728,24 +827,24 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 			edges.resize(0);
 			tris.resize(0);
 			delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges);
-		}		
+		}
 	}
-
+	
 	const int ntris = tris.size()/4;
 	if (ntris > MAX_TRIS)
 	{
 		tris.resize(MAX_TRIS*4);
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Shrinking triangle count from %d to max %d.", ntris, MAX_TRIS);
 	}
-
+	
 	return true;
 }
 
 
 static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
-						  const unsigned short* poly, const int npoly,
-						  const unsigned short* verts, const int bs,
-						  rcHeightPatch& hp, rcIntArray& stack)
+										   const unsigned short* poly, const int npoly,
+										   const unsigned short* verts, const int bs,
+										   rcHeightPatch& hp, rcIntArray& stack)
 {
 	// Floodfill the heightfield to get 2D height data,
 	// starting at vertex locations as seeds.
@@ -849,7 +948,7 @@ static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
 				continue;
 			
 			const int ai = (int)chf.cells[(ax+bs)+(ay+bs)*chf.width].index + rcGetCon(cs, dir);
-
+			
 			int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width;
 			hp.data[idx] = 1;
 			
@@ -858,9 +957,9 @@ static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
 			stack.push(ai);
 		}
 	}
-
+	
 	memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
-
+	
 	// Mark start locations.
 	for (int i = 0; i < stack.size(); i += 3)
 	{
@@ -870,8 +969,8 @@ static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
 		int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width;
 		const rcCompactSpan& cs = chf.spans[ci];
 		hp.data[idx] = cs.y;
-
-		// getHeightData seeds are given in coordinates with borders 
+		
+		// getHeightData seeds are given in coordinates with borders
 		stack[i+0] += bs;
 		stack[i+1] += bs;
 	}
@@ -888,12 +987,12 @@ static void getHeightData(const rcCompactHeightfield& chf,
 {
 	// Note: Reads to the compact heightfield are offset by border size (bs)
 	// since border size offset is already removed from the polymesh vertices.
-
+	
 	stack.resize(0);
 	memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
 	
 	bool empty = true;
-
+	
 	// Copy the height from the same region, and mark region borders
 	// as seed points to fill the rest.
 	for (int hy = 0; hy < hp.height; hy++)
@@ -911,7 +1010,7 @@ static void getHeightData(const rcCompactHeightfield& chf,
 					// Store height
 					hp.data[hx + hy*hp.width] = s.y;
 					empty = false;
-
+					
 					// If any of the neighbours is not in same region,
 					// add the current location as flood fill start
 					bool border = false;
@@ -940,8 +1039,8 @@ static void getHeightData(const rcCompactHeightfield& chf,
 				}
 			}
 		}
-	}	
-
+	}
+	
 	// if the polygon does not contian any points from the current region (rare, but happens)
 	// then use the cells closest to the polygon vertices as seeds to fill the height field
 	if (empty)
@@ -963,7 +1062,7 @@ static void getHeightData(const rcCompactHeightfield& chf,
 				memmove(&stack[0], &stack[RETRACT_SIZE*3], sizeof(int)*(stack.size()-RETRACT_SIZE*3));
 			stack.resize(stack.size()-RETRACT_SIZE*3);
 		}
-
+		
 		const rcCompactSpan& cs = chf.spans[ci];
 		for (int dir = 0; dir < 4; ++dir)
 		{
@@ -982,9 +1081,9 @@ static void getHeightData(const rcCompactHeightfield& chf,
 			
 			const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(cs, dir);
 			const rcCompactSpan& as = chf.spans[ai];
-
+			
 			hp.data[hx + hy*hp.width] = as.y;
-
+			
 			stack.push(ax);
 			stack.push(ay);
 			stack.push(ai);
@@ -999,7 +1098,7 @@ static unsigned char getEdgeFlags(const float* va, const float* vb,
 	static const float thrSqr = rcSqr(0.001f);
 	for (int i = 0, j = npoly-1; i < npoly; j=i++)
 	{
-		if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr && 
+		if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr &&
 			distancePtSeg2d(vb, &vpoly[j*3], &vpoly[i*3]) < thrSqr)
 			return 1;
 	}
@@ -1028,7 +1127,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 	rcAssert(ctx);
 	
 	ctx->startTimer(RC_TIMER_BUILD_POLYMESHDETAIL);
-
+	
 	if (mesh.nverts == 0 || mesh.npolys == 0)
 		return true;
 	
@@ -1107,10 +1206,10 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4);
 		return false;
 	}
-
+	
 	int vcap = nPolyVerts+nPolyVerts/2;
 	int tcap = vcap*2;
-
+	
 	dmesh.nverts = 0;
 	dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
 	if (!dmesh.verts)
@@ -1119,7 +1218,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 		return false;
 	}
 	dmesh.ntris = 0;
-	dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char*)*tcap*4, RC_ALLOC_PERM);
+	dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
 	if (!dmesh.tris)
 	{
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4);
@@ -1158,7 +1257,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 		{
 			return false;
 		}
-
+		
 		// Move detail verts to world space.
 		for (int j = 0; j < nverts; ++j)
 		{
@@ -1173,21 +1272,21 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 			poly[j*3+1] += orig[1];
 			poly[j*3+2] += orig[2];
 		}
-	
+		
 		// Store detail submesh.
 		const int ntris = tris.size()/4;
-
+		
 		dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts;
 		dmesh.meshes[i*4+1] = (unsigned int)nverts;
 		dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris;
-		dmesh.meshes[i*4+3] = (unsigned int)ntris;		
+		dmesh.meshes[i*4+3] = (unsigned int)ntris;
 		
 		// Store vertices, allocate more memory if necessary.
 		if (dmesh.nverts+nverts > vcap)
 		{
 			while (dmesh.nverts+nverts > vcap)
 				vcap += 256;
-				
+			
 			float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
 			if (!newv)
 			{
@@ -1233,9 +1332,9 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 			dmesh.ntris++;
 		}
 	}
-		
+	
 	ctx->stopTimer(RC_TIMER_BUILD_POLYMESHDETAIL);
-
+	
 	return true;
 }
 
@@ -1245,11 +1344,11 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 	rcAssert(ctx);
 	
 	ctx->startTimer(RC_TIMER_MERGE_POLYMESHDETAIL);
-
+	
 	int maxVerts = 0;
 	int maxTris = 0;
 	int maxMeshes = 0;
-
+	
 	for (int i = 0; i < nmeshes; ++i)
 	{
 		if (!meshes[i]) continue;
@@ -1257,7 +1356,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 		maxTris += meshes[i]->ntris;
 		maxMeshes += meshes[i]->nmeshes;
 	}
-
+	
 	mesh.nmeshes = 0;
 	mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM);
 	if (!mesh.meshes)
@@ -1265,7 +1364,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4);
 		return false;
 	}
-
+	
 	mesh.ntris = 0;
 	mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM);
 	if (!mesh.tris)
@@ -1273,7 +1372,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4);
 		return false;
 	}
-
+	
 	mesh.nverts = 0;
 	mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM);
 	if (!mesh.verts)
@@ -1297,7 +1396,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 			dst[3] = src[3];
 			mesh.nmeshes++;
 		}
-			
+		
 		for (int k = 0; k < dm->nverts; ++k)
 		{
 			rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]);
@@ -1312,7 +1411,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 			mesh.ntris++;
 		}
 	}
-
+	
 	ctx->stopTimer(RC_TIMER_MERGE_POLYMESHDETAIL);
 	
 	return true;
diff --git a/dep/recastnavigation/Recast/Source/RecastRegion.cpp b/dep/recastnavigation/Recast/Source/RecastRegion.cpp
index 589fac29203..38bc4ff476f 100644
--- a/dep/recastnavigation/Recast/Source/RecastRegion.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastRegion.cpp
@@ -315,6 +315,7 @@ static bool floodRegion(int x, int y, int i,
 			srcReg[ci] = 0;
 			continue;
 		}
+		
 		count++;
 		
 		// Expand neighbours.
@@ -516,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
@@ -524,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;
 };
@@ -768,10 +776,11 @@ static void walkContour(int x, int y, int i, int dir,
 	}
 }
 
-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;
@@ -780,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;
 	}
 
@@ -803,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)
 				{
@@ -811,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);
 				}
 				
@@ -906,7 +916,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 			}
 		}
 	}
-		
+	
 	// Merge too small regions to neighbour regions.
 	int mergeCount = 0 ;
 	do
@@ -916,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;
 			
@@ -933,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))
@@ -1003,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(&regions[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();
@@ -1011,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
@@ -1256,13 +1488,17 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
 		}
 	}
 
+
 	ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 
-	// Filter out small regions.
+	// Merge regions and filter out small regions.
+	rcIntArray overlaps;
 	chf.maxRegions = id;
-	if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg))
+	if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
 		return false;
 
+	// Monotone partitioning does not generate overlapping regions.
+	
 	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 	
 	// Store the result out.
@@ -1407,11 +1643,18 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 	
 	ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 	
-	// Filter out small regions.
+	// Merge regions and filter out smalle regions.
+	rcIntArray overlaps;
 	chf.maxRegions = regionId;
-	if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg))
+	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());
+	}
+
 	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 		
 	// Write the result out.
@@ -1424,3 +1667,157 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 }
 
 
+bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
+						 const int borderSize, const int minRegionArea)
+{
+	rcAssert(ctx);
+	
+	ctx->startTimer(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;
+			}
+		}
+	}
+	
+	
+	ctx->startTimer(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;
+	
+	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
+	
+	
+	// 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;
+}