1 files changed, 378 insertions, 280 deletions

diff --git a/thirdparty/recastnavigation/Recast/Source/RecastRasterization.cpp b/thirdparty/recastnavigation/Recast/Source/RecastRasterization.cpp
index 673550e79e..2a4f619fb8 100644
--- a/thirdparty/recastnavigation/Recast/Source/RecastRasterization.cpp
+++ b/thirdparty/recastnavigation/Recast/Source/RecastRasterization.cpp
@@ -16,377 +16,485 @@
 // 3. This notice may not be removed or altered from any source distribution.
 //
 
-#define _USE_MATH_DEFINES
 #include <math.h>
 #include <stdio.h>
 #include "Recast.h"
 #include "RecastAlloc.h"
 #include "RecastAssert.h"
 
-inline bool overlapBounds(const float* amin, const float* amax, const float* bmin, const float* bmax)
+/// Check whether two bounding boxes overlap
+///
+/// @param[in]	aMin	Min axis extents of bounding box A
+/// @param[in]	aMax	Max axis extents of bounding box A
+/// @param[in]	bMin	Min axis extents of bounding box B
+/// @param[in]	bMax	Max axis extents of bounding box B
+/// @returns true if the two bounding boxes overlap.  False otherwise.
+static bool overlapBounds(const float* aMin, const float* aMax, const float* bMin, const float* bMax)
 {
-	bool overlap = true;
-	overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
-	overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
-	overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap;
-	return overlap;
+	return
+		aMin[0] <= bMax[0] && aMax[0] >= bMin[0] &&
+		aMin[1] <= bMax[1] && aMax[1] >= bMin[1] &&
+		aMin[2] <= bMax[2] && aMax[2] >= bMin[2];
 }
 
-inline bool overlapInterval(unsigned short amin, unsigned short amax,
-							unsigned short bmin, unsigned short bmax)
-{
-	if (amax < bmin) return false;
-	if (amin > bmax) return false;
-	return true;
-}
-
-
+/// Allocates a new span in the heightfield.
+/// Use a memory pool and free list to minimize actual allocations.
+/// 
+/// @param[in]	hf		The heightfield
+/// @returns A pointer to the allocated or re-used span memory. 
 static rcSpan* allocSpan(rcHeightfield& hf)
 {
-	// If running out of memory, allocate new page and update the freelist.
-	if (!hf.freelist || !hf.freelist->next)
+	// If necessary, allocate new page and update the freelist.
+	if (hf.freelist == NULL || hf.freelist->next == NULL)
 	{
 		// Create new page.
 		// Allocate memory for the new pool.
-		rcSpanPool* pool = (rcSpanPool*)rcAlloc(sizeof(rcSpanPool), RC_ALLOC_PERM);
-		if (!pool) return 0;
+		rcSpanPool* spanPool = (rcSpanPool*)rcAlloc(sizeof(rcSpanPool), RC_ALLOC_PERM);
+		if (spanPool == NULL)
+		{
+			return NULL;
+		}
 
 		// Add the pool into the list of pools.
-		pool->next = hf.pools;
-		hf.pools = pool;
-		// Add new items to the free list.
-		rcSpan* freelist = hf.freelist;
-		rcSpan* head = &pool->items[0];
-		rcSpan* it = &pool->items[RC_SPANS_PER_POOL];
+		spanPool->next = hf.pools;
+		hf.pools = spanPool;
+		
+		// Add new spans to the free list.
+		rcSpan* freeList = hf.freelist;
+		rcSpan* head = &spanPool->items[0];
+		rcSpan* it = &spanPool->items[RC_SPANS_PER_POOL];
 		do
 		{
 			--it;
-			it->next = freelist;
-			freelist = it;
+			it->next = freeList;
+			freeList = it;
 		}
 		while (it != head);
 		hf.freelist = it;
 	}
-	
-	// Pop item from in front of the free list.
-	rcSpan* it = hf.freelist;
+
+	// Pop item from the front of the free list.
+	rcSpan* newSpan = hf.freelist;
 	hf.freelist = hf.freelist->next;
-	return it;
+	return newSpan;
 }
 
-static void freeSpan(rcHeightfield& hf, rcSpan* ptr)
+/// Releases the memory used by the span back to the heightfield, so it can be re-used for new spans.
+/// @param[in]	hf		The heightfield.
+/// @param[in]	span	A pointer to the span to free
+static void freeSpan(rcHeightfield& hf, rcSpan* span)
 {
-	if (!ptr) return;
-	// Add the node in front of the free list.
-	ptr->next = hf.freelist;
-	hf.freelist = ptr;
+	if (span == NULL)
+	{
+		return;
+	}
+	// Add the span to the front of the free list.
+	span->next = hf.freelist;
+	hf.freelist = span;
 }
 
-static bool addSpan(rcHeightfield& hf, const int x, const int y,
-					const unsigned short smin, const unsigned short smax,
-					const unsigned char area, const int flagMergeThr)
+/// Adds a span to the heightfield.  If the new span overlaps existing spans,
+/// it will merge the new span with the existing ones.
+///
+/// @param[in]	hf					Heightfield to add spans to
+/// @param[in]	x					The new span's column cell x index
+/// @param[in]	z					The new span's column cell z index
+/// @param[in]	min					The new span's minimum cell index
+/// @param[in]	max					The new span's maximum cell index
+/// @param[in]	areaID				The new span's area type ID
+/// @param[in]	flagMergeThreshold	How close two spans maximum extents need to be to merge area type IDs
+static bool addSpan(rcHeightfield& hf,
+                    const int x, const int z,
+                    const unsigned short min, const unsigned short max,
+                    const unsigned char areaID, const int flagMergeThreshold)
 {
-	
-	int idx = x + y*hf.width;
-	
-	rcSpan* s = allocSpan(hf);
-	if (!s)
-		return false;
-	s->smin = smin;
-	s->smax = smax;
-	s->area = area;
-	s->next = 0;
-	
-	// Empty cell, add the first span.
-	if (!hf.spans[idx])
+	// Create the new span.
+	rcSpan* newSpan = allocSpan(hf);
+	if (newSpan == NULL)
 	{
-		hf.spans[idx] = s;
-		return true;
+		return false;
 	}
-	rcSpan* prev = 0;
-	rcSpan* cur = hf.spans[idx];
+	newSpan->smin = min;
+	newSpan->smax = max;
+	newSpan->area = areaID;
+	newSpan->next = NULL;
+	
+	const int columnIndex = x + z * hf.width;
+	rcSpan* previousSpan = NULL;
+	rcSpan* currentSpan = hf.spans[columnIndex];
 	
-	// Insert and merge spans.
-	while (cur)
+	// Insert the new span, possibly merging it with existing spans.
+	while (currentSpan != NULL)
 	{
-		if (cur->smin > s->smax)
+		if (currentSpan->smin > newSpan->smax)
 		{
-			// Current span is further than the new span, break.
+			// Current span is completely after the new span, break.
 			break;
 		}
-		else if (cur->smax < s->smin)
+		
+		if (currentSpan->smax < newSpan->smin)
 		{
-			// Current span is before the new span advance.
-			prev = cur;
-			cur = cur->next;
+			// Current span is completely before the new span.  Keep going.
+			previousSpan = currentSpan;
+			currentSpan = currentSpan->next;
 		}
 		else
 		{
-			// Merge spans.
-			if (cur->smin < s->smin)
-				s->smin = cur->smin;
-			if (cur->smax > s->smax)
-				s->smax = cur->smax;
+			// The new span overlaps with an existing span.  Merge them.
+			if (currentSpan->smin < newSpan->smin)
+			{
+				newSpan->smin = currentSpan->smin;
+			}
+			if (currentSpan->smax > newSpan->smax)
+			{
+				newSpan->smax = currentSpan->smax;
+			}
 			
 			// Merge flags.
-			if (rcAbs((int)s->smax - (int)cur->smax) <= flagMergeThr)
-				s->area = rcMax(s->area, cur->area);
+			if (rcAbs((int)newSpan->smax - (int)currentSpan->smax) <= flagMergeThreshold)
+			{
+				// Higher area ID numbers indicate higher resolution priority.
+				newSpan->area = rcMax(newSpan->area, currentSpan->area);
+			}
 			
-			// Remove current span.
-			rcSpan* next = cur->next;
-			freeSpan(hf, cur);
-			if (prev)
-				prev->next = next;
+			// Remove the current span since it's now merged with newSpan.
+			// Keep going because there might be other overlapping spans that also need to be merged.
+			rcSpan* next = currentSpan->next;
+			freeSpan(hf, currentSpan);
+			if (previousSpan)
+			{
+				previousSpan->next = next;
+			}
 			else
-				hf.spans[idx] = next;
-			cur = next;
+			{
+				hf.spans[columnIndex] = next;
+			}
+			currentSpan = next;
 		}
 	}
 	
-	// Insert new span.
-	if (prev)
+	// Insert new span after prev
+	if (previousSpan != NULL)
 	{
-		s->next = prev->next;
-		prev->next = s;
+		newSpan->next = previousSpan->next;
+		previousSpan->next = newSpan;
 	}
 	else
 	{
-		s->next = hf.spans[idx];
-		hf.spans[idx] = s;
+		// This span should go before the others in the list
+		newSpan->next = hf.spans[columnIndex];
+		hf.spans[columnIndex] = newSpan;
 	}
 
 	return true;
 }
 
-/// @par
-///
-/// The span addition can be set to favor flags. If the span is merged to
-/// another span and the new @p smax is within @p flagMergeThr units
-/// from the existing span, the span flags are merged.
-///
-/// @see rcHeightfield, rcSpan.
-bool rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y,
-			   const unsigned short smin, const unsigned short smax,
-			   const unsigned char area, const int flagMergeThr)
+bool rcAddSpan(rcContext* context, rcHeightfield& heightfield,
+               const int x, const int z,
+               const unsigned short spanMin, const unsigned short spanMax,
+               const unsigned char areaID, const int flagMergeThreshold)
 {
-	rcAssert(ctx);
+	rcAssert(context);
 
-	if (!addSpan(hf, x, y, smin, smax, area, flagMergeThr))
+	if (!addSpan(heightfield, x, z, spanMin, spanMax, areaID, flagMergeThreshold))
 	{
-		ctx->log(RC_LOG_ERROR, "rcAddSpan: Out of memory.");
+		context->log(RC_LOG_ERROR, "rcAddSpan: Out of memory.");
 		return false;
 	}
 
 	return true;
 }
 
-// divides a convex polygons into two convex polygons on both sides of a line
-static void dividePoly(const float* in, int nin,
-					  float* out1, int* nout1,
-					  float* out2, int* nout2,
-					  float x, int axis)
+enum rcAxis
+{
+	RC_AXIS_X = 0,
+	RC_AXIS_Y = 1,
+	RC_AXIS_Z = 2
+};
+
+/// Divides a convex polygon of max 12 vertices into two convex polygons
+/// across a separating axis.
+/// 
+/// @param[in]	inVerts			The input polygon vertices
+/// @param[in]	inVertsCount	The number of input polygon vertices
+/// @param[out]	outVerts1		Resulting polygon 1's vertices
+/// @param[out]	outVerts1Count	The number of resulting polygon 1 vertices
+/// @param[out]	outVerts2		Resulting polygon 2's vertices
+/// @param[out]	outVerts2Count	The number of resulting polygon 2 vertices
+/// @param[in]	axisOffset		THe offset along the specified axis
+/// @param[in]	axis			The separating axis
+static void dividePoly(const float* inVerts, int inVertsCount,
+                       float* outVerts1, int* outVerts1Count,
+                       float* outVerts2, int* outVerts2Count,
+                       float axisOffset, rcAxis axis)
 {
-	float d[12];
-	for (int i = 0; i < nin; ++i)
-		d[i] = x - in[i*3+axis];
+	rcAssert(inVertsCount <= 12);
+	
+	// How far positive or negative away from the separating axis is each vertex.
+	float inVertAxisDelta[12];
+	for (int inVert = 0; inVert < inVertsCount; ++inVert)
+	{
+		inVertAxisDelta[inVert] = axisOffset - inVerts[inVert * 3 + axis];
+	}
 
-	int m = 0, n = 0;
-	for (int i = 0, j = nin-1; i < nin; j=i, ++i)
+	int poly1Vert = 0;
+	int poly2Vert = 0;
+	for (int inVertA = 0, inVertB = inVertsCount - 1; inVertA < inVertsCount; inVertB = inVertA, ++inVertA)
 	{
-		bool ina = d[j] >= 0;
-		bool inb = d[i] >= 0;
-		if (ina != inb)
+		// If the two vertices are on the same side of the separating axis
+		bool sameSide = (inVertAxisDelta[inVertA] >= 0) == (inVertAxisDelta[inVertB] >= 0);
+
+		if (!sameSide)
 		{
-			float s = d[j] / (d[j] - d[i]);
-			out1[m*3+0] = in[j*3+0] + (in[i*3+0] - in[j*3+0])*s;
-			out1[m*3+1] = in[j*3+1] + (in[i*3+1] - in[j*3+1])*s;
-			out1[m*3+2] = in[j*3+2] + (in[i*3+2] - in[j*3+2])*s;
-			rcVcopy(out2 + n*3, out1 + m*3);
-			m++;
-			n++;
-			// add the i'th point to the right polygon. Do NOT add points that are on the dividing line
+			float s = inVertAxisDelta[inVertB] / (inVertAxisDelta[inVertB] - inVertAxisDelta[inVertA]);
+			outVerts1[poly1Vert * 3 + 0] = inVerts[inVertB * 3 + 0] + (inVerts[inVertA * 3 + 0] - inVerts[inVertB * 3 + 0]) * s;
+			outVerts1[poly1Vert * 3 + 1] = inVerts[inVertB * 3 + 1] + (inVerts[inVertA * 3 + 1] - inVerts[inVertB * 3 + 1]) * s;
+			outVerts1[poly1Vert * 3 + 2] = inVerts[inVertB * 3 + 2] + (inVerts[inVertA * 3 + 2] - inVerts[inVertB * 3 + 2]) * s;
+			rcVcopy(&outVerts2[poly2Vert * 3], &outVerts1[poly1Vert * 3]);
+			poly1Vert++;
+			poly2Vert++;
+			
+			// add the inVertA point to the right polygon. Do NOT add points that are on the dividing line
 			// since these were already added above
-			if (d[i] > 0)
+			if (inVertAxisDelta[inVertA] > 0)
 			{
-				rcVcopy(out1 + m*3, in + i*3);
-				m++;
+				rcVcopy(&outVerts1[poly1Vert * 3], &inVerts[inVertA * 3]);
+				poly1Vert++;
 			}
-			else if (d[i] < 0)
+			else if (inVertAxisDelta[inVertA] < 0)
 			{
-				rcVcopy(out2 + n*3, in + i*3);
-				n++;
+				rcVcopy(&outVerts2[poly2Vert * 3], &inVerts[inVertA * 3]);
+				poly2Vert++;
 			}
 		}
-		else // same side
+		else
 		{
-			// add the i'th point to the right polygon. Addition is done even for points on the dividing line
-			if (d[i] >= 0)
+			// add the inVertA point to the right polygon. Addition is done even for points on the dividing line
+			if (inVertAxisDelta[inVertA] >= 0)
 			{
-				rcVcopy(out1 + m*3, in + i*3);
-				m++;
-				if (d[i] != 0)
+				rcVcopy(&outVerts1[poly1Vert * 3], &inVerts[inVertA * 3]);
+				poly1Vert++;
+				if (inVertAxisDelta[inVertA] != 0)
+				{
 					continue;
+				}
 			}
-			rcVcopy(out2 + n*3, in + i*3);
-			n++;
+			rcVcopy(&outVerts2[poly2Vert * 3], &inVerts[inVertA * 3]);
+			poly2Vert++;
 		}
 	}
 
-	*nout1 = m;
-	*nout2 = n;
+	*outVerts1Count = poly1Vert;
+	*outVerts2Count = poly2Vert;
 }
 
-
-
+///	Rasterize a single triangle to the heightfield.
+///
+///	This code is extremely hot, so much care should be given to maintaining maximum perf here.
+/// 
+/// @param[in] 	v0					Triangle vertex 0
+/// @param[in] 	v1					Triangle vertex 1
+/// @param[in] 	v2					Triangle vertex 2
+/// @param[in] 	areaID				The area ID to assign to the rasterized spans
+/// @param[in] 	hf					Heightfield to rasterize into
+/// @param[in] 	hfBBMin				The min extents of the heightfield bounding box
+/// @param[in] 	hfBBMax				The max extents of the heightfield bounding box
+/// @param[in] 	cellSize			The x and z axis size of a voxel in the heightfield
+/// @param[in] 	inverseCellSize		1 / cellSize
+/// @param[in] 	inverseCellHeight	1 / cellHeight
+/// @param[in] 	flagMergeThreshold	The threshold in which area flags will be merged 
+/// @returns true if the operation completes successfully.  false if there was an error adding spans to the heightfield.
 static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
-						 const unsigned char area, rcHeightfield& hf,
-						 const float* bmin, const float* bmax,
-						 const float cs, const float ics, const float ich,
-						 const int flagMergeThr)
+                         const unsigned char areaID, rcHeightfield& hf,
+                         const float* hfBBMin, const float* hfBBMax,
+                         const float cellSize, const float inverseCellSize, const float inverseCellHeight,
+                         const int flagMergeThreshold)
 {
-	const int w = hf.width;
-	const int h = hf.height;
-	float tmin[3], tmax[3];
-	const float by = bmax[1] - bmin[1];
-	
 	// Calculate the bounding box of the triangle.
-	rcVcopy(tmin, v0);
-	rcVcopy(tmax, v0);
-	rcVmin(tmin, v1);
-	rcVmin(tmin, v2);
-	rcVmax(tmax, v1);
-	rcVmax(tmax, v2);
-	
-	// If the triangle does not touch the bbox of the heightfield, skip the triagle.
-	if (!overlapBounds(bmin, bmax, tmin, tmax))
+	float triBBMin[3];
+	rcVcopy(triBBMin, v0);
+	rcVmin(triBBMin, v1);
+	rcVmin(triBBMin, v2);
+
+	float triBBMax[3];
+	rcVcopy(triBBMax, v0);
+	rcVmax(triBBMax, v1);
+	rcVmax(triBBMax, v2);
+
+	// If the triangle does not touch the bounding box of the heightfield, skip the triangle.
+	if (!overlapBounds(triBBMin, triBBMax, hfBBMin, hfBBMax))
+	{
 		return true;
-	
-	// Calculate the footprint of the triangle on the grid's y-axis
-	int y0 = (int)((tmin[2] - bmin[2])*ics);
-	int y1 = (int)((tmax[2] - bmin[2])*ics);
+	}
+
+	const int w = hf.width;
+	const int h = hf.height;
+	const float by = hfBBMax[1] - hfBBMin[1];
+
+	// Calculate the footprint of the triangle on the grid's z-axis
+	int z0 = (int)((triBBMin[2] - hfBBMin[2]) * inverseCellSize);
+	int z1 = (int)((triBBMax[2] - hfBBMin[2]) * inverseCellSize);
+
 	// use -1 rather than 0 to cut the polygon properly at the start of the tile
-	y0 = rcClamp(y0, -1, h-1);
-	y1 = rcClamp(y1, 0, h-1);
-	
+	z0 = rcClamp(z0, -1, h - 1);
+	z1 = rcClamp(z1, 0, h - 1);
+
 	// Clip the triangle into all grid cells it touches.
-	float buf[7*3*4];
-	float *in = buf, *inrow = buf+7*3, *p1 = inrow+7*3, *p2 = p1+7*3;
+	float buf[7 * 3 * 4];
+	float* in = buf;
+	float* inRow = buf + 7 * 3;
+	float* p1 = inRow + 7 * 3;
+	float* p2 = p1 + 7 * 3;
 
 	rcVcopy(&in[0], v0);
-	rcVcopy(&in[1*3], v1);
-	rcVcopy(&in[2*3], v2);
-	int nvrow, nvIn = 3;
-	
-	for (int y = y0; y <= y1; ++y)
+	rcVcopy(&in[1 * 3], v1);
+	rcVcopy(&in[2 * 3], v2);
+	int nvRow;
+	int nvIn = 3;
+
+	for (int z = z0; z <= z1; ++z)
 	{
 		// Clip polygon to row. Store the remaining polygon as well
-		const float cz = bmin[2] + y*cs;
-		dividePoly(in, nvIn, inrow, &nvrow, p1, &nvIn, cz+cs, 2);
+		const float cellZ = hfBBMin[2] + (float)z * cellSize;
+		dividePoly(in, nvIn, inRow, &nvRow, p1, &nvIn, cellZ + cellSize, RC_AXIS_Z);
 		rcSwap(in, p1);
-		if (nvrow < 3) continue;
-		if (y < 0) continue;
-		// find the horizontal bounds in the row
-		float minX = inrow[0], maxX = inrow[0];
-		for (int i=1; i<nvrow; ++i)
+		
+		if (nvRow < 3)
 		{
-			if (minX > inrow[i*3])	minX = inrow[i*3];
-			if (maxX < inrow[i*3])	maxX = inrow[i*3];
+			continue;
 		}
-		int x0 = (int)((minX - bmin[0])*ics);
-		int x1 = (int)((maxX - bmin[0])*ics);
-		if (x1 < 0 || x0 >= w) {
+		if (z < 0)
+		{
 			continue;
 		}
-		x0 = rcClamp(x0, -1, w-1);
-		x1 = rcClamp(x1, 0, w-1);
+		
+		// find X-axis bounds of the row
+		float minX = inRow[0];
+		float maxX = inRow[0];
+		for (int vert = 1; vert < nvRow; ++vert)
+		{
+			if (minX > inRow[vert * 3])
+			{
+				minX = inRow[vert * 3];
+			}
+			if (maxX < inRow[vert * 3])
+			{
+				maxX = inRow[vert * 3];
+			}
+		}
+		int x0 = (int)((minX - hfBBMin[0]) * inverseCellSize);
+		int x1 = (int)((maxX - hfBBMin[0]) * inverseCellSize);
+		if (x1 < 0 || x0 >= w)
+		{
+			continue;
+		}
+		x0 = rcClamp(x0, -1, w - 1);
+		x1 = rcClamp(x1, 0, w - 1);
 
-		int nv, nv2 = nvrow;
+		int nv;
+		int nv2 = nvRow;
 
 		for (int x = x0; x <= x1; ++x)
 		{
 			// Clip polygon to column. store the remaining polygon as well
-			const float cx = bmin[0] + x*cs;
-			dividePoly(inrow, nv2, p1, &nv, p2, &nv2, cx+cs, 0);
-			rcSwap(inrow, p2);
-			if (nv < 3) continue;
-			if (x < 0) continue;
+			const float cx = hfBBMin[0] + (float)x * cellSize;
+			dividePoly(inRow, nv2, p1, &nv, p2, &nv2, cx + cellSize, RC_AXIS_X);
+			rcSwap(inRow, p2);
+			
+			if (nv < 3)
+			{
+				continue;
+			}
+			if (x < 0)
+			{
+				continue;
+			}
+			
 			// Calculate min and max of the span.
-			float smin = p1[1], smax = p1[1];
-			for (int i = 1; i < nv; ++i)
+			float spanMin = p1[1];
+			float spanMax = p1[1];
+			for (int vert = 1; vert < nv; ++vert)
 			{
-				smin = rcMin(smin, p1[i*3+1]);
-				smax = rcMax(smax, p1[i*3+1]);
+				spanMin = rcMin(spanMin, p1[vert * 3 + 1]);
+				spanMax = rcMax(spanMax, p1[vert * 3 + 1]);
 			}
-			smin -= bmin[1];
-			smax -= bmin[1];
-			// Skip the span if it is outside the heightfield bbox
-			if (smax < 0.0f) continue;
-			if (smin > by) continue;
-			// Clamp the span to the heightfield bbox.
-			if (smin < 0.0f) smin = 0;
-			if (smax > by) smax = by;
+			spanMin -= hfBBMin[1];
+			spanMax -= hfBBMin[1];
 			
-			// Snap the span to the heightfield height grid.
-			unsigned short ismin = (unsigned short)rcClamp((int)floorf(smin * ich), 0, RC_SPAN_MAX_HEIGHT);
-			unsigned short ismax = (unsigned short)rcClamp((int)ceilf(smax * ich), (int)ismin+1, RC_SPAN_MAX_HEIGHT);
+			// Skip the span if it's completely outside the heightfield bounding box
+			if (spanMax < 0.0f)
+			{
+				continue;
+			}
+			if (spanMin > by)
+			{
+				continue;
+			}
 			
-			if (!addSpan(hf, x, y, ismin, ismax, area, flagMergeThr))
+			// Clamp the span to the heightfield bounding box.
+			if (spanMin < 0.0f)
+			{
+				spanMin = 0;
+			}
+			if (spanMax > by)
+			{
+				spanMax = by;
+			}
+
+			// Snap the span to the heightfield height grid.
+			unsigned short spanMinCellIndex = (unsigned short)rcClamp((int)floorf(spanMin * inverseCellHeight), 0, RC_SPAN_MAX_HEIGHT);
+			unsigned short spanMaxCellIndex = (unsigned short)rcClamp((int)ceilf(spanMax * inverseCellHeight), (int)spanMinCellIndex + 1, RC_SPAN_MAX_HEIGHT);
+
+			if (!addSpan(hf, x, z, spanMinCellIndex, spanMaxCellIndex, areaID, flagMergeThreshold))
+			{
 				return false;
+			}
 		}
 	}
 
 	return true;
 }
 
-/// @par
-///
-/// No spans will be added if the triangle does not overlap the heightfield grid.
-///
-/// @see rcHeightfield
-bool rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2,
-						 const unsigned char area, rcHeightfield& solid,
-						 const int flagMergeThr)
+bool rcRasterizeTriangle(rcContext* context,
+                         const float* v0, const float* v1, const float* v2,
+                         const unsigned char areaID, rcHeightfield& heightfield, const int flagMergeThreshold)
 {
-	rcAssert(ctx);
+	rcAssert(context != NULL);
 
-	rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);
+	rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);
 
-	const float ics = 1.0f/solid.cs;
-	const float ich = 1.0f/solid.ch;
-	if (!rasterizeTri(v0, v1, v2, area, solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
+	// Rasterize the single triangle.
+	const float inverseCellSize = 1.0f / heightfield.cs;
+	const float inverseCellHeight = 1.0f / heightfield.ch;
+	if (!rasterizeTri(v0, v1, v2, areaID, heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
 	{
-		ctx->log(RC_LOG_ERROR, "rcRasterizeTriangle: Out of memory.");
+		context->log(RC_LOG_ERROR, "rcRasterizeTriangle: Out of memory.");
 		return false;
 	}
 
 	return true;
 }
 
-/// @par
-///
-/// Spans will only be added for triangles that overlap the heightfield grid.
-///
-/// @see rcHeightfield
-bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/,
-						  const int* tris, const unsigned char* areas, const int nt,
-						  rcHeightfield& solid, const int flagMergeThr)
+bool rcRasterizeTriangles(rcContext* context,
+                          const float* verts, const int /*nv*/,
+                          const int* tris, const unsigned char* triAreaIDs, const int numTris,
+                          rcHeightfield& heightfield, const int flagMergeThreshold)
 {
-	rcAssert(ctx);
+	rcAssert(context != NULL);
 
-	rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);
+	rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);
 	
-	const float ics = 1.0f/solid.cs;
-	const float ich = 1.0f/solid.ch;
-	// Rasterize triangles.
-	for (int i = 0; i < nt; ++i)
+	// Rasterize the triangles.
+	const float inverseCellSize = 1.0f / heightfield.cs;
+	const float inverseCellHeight = 1.0f / heightfield.ch;
+	for (int triIndex = 0; triIndex < numTris; ++triIndex)
 	{
-		const float* v0 = &verts[tris[i*3+0]*3];
-		const float* v1 = &verts[tris[i*3+1]*3];
-		const float* v2 = &verts[tris[i*3+2]*3];
-		// Rasterize.
-		if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
+		const float* v0 = &verts[tris[triIndex * 3 + 0] * 3];
+		const float* v1 = &verts[tris[triIndex * 3 + 1] * 3];
+		const float* v2 = &verts[tris[triIndex * 3 + 2] * 3];
+		if (!rasterizeTri(v0, v1, v2, triAreaIDs[triIndex], heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
 		{
-			ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
+			context->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
 			return false;
 		}
 	}
@@ -394,31 +502,26 @@ bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/,
 	return true;
 }
 
-/// @par
-///
-/// Spans will only be added for triangles that overlap the heightfield grid.
-///
-/// @see rcHeightfield
-bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/,
-						  const unsigned short* tris, const unsigned char* areas, const int nt,
-						  rcHeightfield& solid, const int flagMergeThr)
+bool rcRasterizeTriangles(rcContext* context,
+                          const float* verts, const int /*nv*/,
+                          const unsigned short* tris, const unsigned char* triAreaIDs, const int numTris,
+                          rcHeightfield& heightfield, const int flagMergeThreshold)
 {
-	rcAssert(ctx);
+	rcAssert(context != NULL);
 
-	rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);
-	
-	const float ics = 1.0f/solid.cs;
-	const float ich = 1.0f/solid.ch;
-	// Rasterize triangles.
-	for (int i = 0; i < nt; ++i)
+	rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);
+
+	// Rasterize the triangles.
+	const float inverseCellSize = 1.0f / heightfield.cs;
+	const float inverseCellHeight = 1.0f / heightfield.ch;
+	for (int triIndex = 0; triIndex < numTris; ++triIndex)
 	{
-		const float* v0 = &verts[tris[i*3+0]*3];
-		const float* v1 = &verts[tris[i*3+1]*3];
-		const float* v2 = &verts[tris[i*3+2]*3];
-		// Rasterize.
-		if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
+		const float* v0 = &verts[tris[triIndex * 3 + 0] * 3];
+		const float* v1 = &verts[tris[triIndex * 3 + 1] * 3];
+		const float* v2 = &verts[tris[triIndex * 3 + 2] * 3];
+		if (!rasterizeTri(v0, v1, v2, triAreaIDs[triIndex], heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
 		{
-			ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
+			context->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
 			return false;
 		}
 	}
@@ -426,30 +529,25 @@ bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/,
 	return true;
 }
 
-/// @par
-///
-/// Spans will only be added for triangles that overlap the heightfield grid.
-///
-/// @see rcHeightfield
-bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt,
-						  rcHeightfield& solid, const int flagMergeThr)
+bool rcRasterizeTriangles(rcContext* context,
+                          const float* verts, const unsigned char* triAreaIDs, const int numTris,
+                          rcHeightfield& heightfield, const int flagMergeThreshold)
 {
-	rcAssert(ctx);
-	
-	rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);
+	rcAssert(context != NULL);
+
+	rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);
 	
-	const float ics = 1.0f/solid.cs;
-	const float ich = 1.0f/solid.ch;
-	// Rasterize triangles.
-	for (int i = 0; i < nt; ++i)
+	// Rasterize the triangles.
+	const float inverseCellSize = 1.0f / heightfield.cs;
+	const float inverseCellHeight = 1.0f / heightfield.ch;
+	for (int triIndex = 0; triIndex < numTris; ++triIndex)
 	{
-		const float* v0 = &verts[(i*3+0)*3];
-		const float* v1 = &verts[(i*3+1)*3];
-		const float* v2 = &verts[(i*3+2)*3];
-		// Rasterize.
-		if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
+		const float* v0 = &verts[(triIndex * 3 + 0) * 3];
+		const float* v1 = &verts[(triIndex * 3 + 1) * 3];
+		const float* v2 = &verts[(triIndex * 3 + 2) * 3];
+		if (!rasterizeTri(v0, v1, v2, triAreaIDs[triIndex], heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
 		{
-			ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
+			context->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
 			return false;
 		}
 	}