void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid)
{
	rcAssert(ctx);

	ctx->startTimer(RC_TIMER_FILTER_LOW_OBSTACLES);

	const int w = solid.width;
	const int h = solid.height;

	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			rcSpan* ps = 0;
			bool previousWalkable = false;

			for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next)
			{
				const bool walkable = s->area != RC_NULL_AREA;
				// If current span is not walkable, but there is walkable
				// span just below it, mark the span above it walkable too.
				if (!walkable && previousWalkable)
				{
					if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb)
						s->area = RC_NULL_AREA;
				}
				// Copy walkable flag so that it cannot propagate
				// past multiple non-walkable objects.
				previousWalkable = walkable;
			}
		}
	}

	ctx->stopTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
}

void	rcMergeSpans( rcContext* ctx, rcHeightfield& solid )
{
	rcAssert( ctx );

	ctx->startTimer( RC_TIMER_TEMPORARY );

	const int w = solid.width;
	const int h = solid.height;

	for( int y = 0; y < h; ++y ) {
		for( int x = 0; x < w; ++x ) {
			for( rcSpan* s = solid.spans[x + y*w]; s != NULL && s->next != NULL; s = s->next ) {
				if( !rcIsSimilarTypeArea( s->area, s->next->area ) && rcAbs( static_cast<int>( s->next->smin ) - static_cast<int>( s->smax ) ) <= 2 ) {
					// merge
					rcSpan* next = s->next;
					s->smax = next->smax;
					const bool walkable = rcIsWalkableArea( s->area ) || rcIsWalkableArea( next->area );
					s->area = next->area;
					s->area &= walkable ? ~RC_UNWALKABLE_AREA : ~RC_WALKABLE_AREA;
					s->area |= walkable ? RC_WALKABLE_AREA : RC_UNWALKABLE_AREA;
					s->next = next->next;
					freeSpan( solid, next );
				}
			}
		}
	}

	ctx->stopTimer( RC_TIMER_TEMPORARY );
}

/// @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)
{
	rcAssert(ctx);
	
	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)
	{
		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))
		{
			ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
			return false;
		}
	}

	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.
void rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y,
			   const unsigned short smin, const unsigned short smax,
			   const navAreaMask areaMask, const int flagMergeThr )
{
	rcAssert(ctx);
	addSpan(hf, x,y, smin, smax, areaMask, flagMergeThr);
}

void	rcMarkWalkableLowHangingObstacles( rcContext* ctx, const int walkableClimb, rcHeightfield& solid )
{
	rcAssert( ctx );

	ctx->startTimer( RC_TIMER_TEMPORARY );

	const int w = solid.width;
	const int h = solid.height;

	for( int y = 0; y < h; ++y ) {
		for( int x = 0; x < w; ++x ) {
			rcSpan* ps = 0;
			bool previousWalkable = false;

			for( rcSpan* s = solid.spans[x + y*w]; s != NULL; ps = s, s = s->next ) {
				const bool walkable = rcIsWalkableArea( s->area );
				if( !walkable && previousWalkable ) {
					if( rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb ) {
						s->area &= ~RC_UNWALKABLE_AREA;
						s->area |= RC_WALKABLE_AREA;
					}
				}
				previousWalkable = walkable;
			}
		}
	}

	ctx->stopTimer( RC_TIMER_TEMPORARY );
}

void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid)
{
	rcAssert(ctx);

	ctx->startTimer(RC_TIMER_FILTER_WALKABLE);

	const int w = solid.width;
	const int h = solid.height;
	const int MAX_HEIGHT = 0xffff;

	// Remove walkable flag from spans which do not have enough
	// space above them for the agent to stand there.
	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
			{
				const int bot = (int)(s->smax);
				const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
				if ((top - bot) <= walkableHeight)
					s->area = RC_NULL_AREA;
			}
		}
	}

	ctx->stopTimer(RC_TIMER_FILTER_WALKABLE);
}

void	rcMarkTerrainWalkableUnderFloorSpans( rcContext* ctx, const int walkableClimb, rcHeightfield& solid )
{
	rcAssert( ctx );

	ctx->startTimer( RC_TIMER_TEMPORARY );

	const int w = solid.width;
	const int h = solid.height;

	//////////////////////////////////////////////////////////////////////////
	for( int y = 0; y < h; ++y ) {
		for( int x = 0; x < w; ++x ) {
			rcMarkWalkableLowerFloorSpan( x, y, walkableClimb, solid );
		}
	}
	for( int x = 0; x < w; ++x ) {
		for( int y = 0; y < h; ++y ) {
			rcMarkWalkableLowerFloorSpan( x, y, walkableClimb, solid );
		}
	}
	for( int y = h-1; 0 <= y; --y ) {
		for( int x = w-1; 0 <= x; --x ) {
			rcMarkWalkableLowerFloorSpan( x, y, walkableClimb, solid );
		}
	}
	for( int x = w-1; 0 <= x; --x ) {
		for( int y = h-1; 0 <= y; --y ) {
			rcMarkWalkableLowerFloorSpan( x, y, walkableClimb, solid );
		}
	}
	//////////////////////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////
	for( int y = 0; y < h; ++y ) {
		for( int x = 0; x < w; ++x ) {
			rcMarkLedgeJumpableLowerFloorSpan( x, y, walkableClimb, solid );
		}
	}
	for( int x = 0; x < w; ++x ) {
		for( int y = 0; y < h; ++y ) {
			rcMarkLedgeJumpableLowerFloorSpan( x, y, walkableClimb, solid );
		}
	}
	for( int y = h-1; 0 <= y; --y ) {
		for( int x = w-1; 0 <= x; --x ) {
			rcMarkLedgeJumpableLowerFloorSpan( x, y, walkableClimb, solid );
		}
	}
	for( int x = w-1; 0 <= x; --x ) {
		for( int y = h-1; 0 <= y; --y ) {
			rcMarkLedgeJumpableLowerFloorSpan( x, y, walkableClimb, solid );
		}
	}
	//////////////////////////////////////////////////////////////////////////

	ctx->stopTimer( RC_TIMER_TEMPORARY );
}

/// @par
///
/// Using this method ensures the array is at least large enough to hold
/// the specified number of elements.  This can improve performance by
/// avoiding auto-resizing during use.
void rcIntArray::doResize(int n)
{
	if (!m_cap) m_cap = n;
	while (m_cap < n) m_cap *= 2;
	int* newData = (int*)rcAlloc(m_cap*sizeof(int), RC_ALLOC_TEMP);
	rcAssert(newData);
	if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int));
	rcFree(m_data);
	m_data = newData;
}

/// @par
/// 
/// This is usually the second to the last step in creating a fully built
/// compact heightfield.  This step is required before regions are built
/// using #rcBuildRegions or #rcBuildRegionsMonotone.
/// 
/// After this step, the distance data is available via the rcCompactHeightfield::maxDistance
/// and rcCompactHeightfield::dist fields.
///
/// @see rcCompactHeightfield, rcBuildRegions, rcBuildRegionsMonotone
bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf)
{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD);
    
    if (chf.dist)
    {
        rcFree(chf.dist);
        chf.dist = 0;
    }
    
    unsigned short* src = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
    if (!src)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'src' (%d).", chf.spanCount);
        return false;
    }
    unsigned short* dst = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
    if (!dst)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'dst' (%d).", chf.spanCount);
        rcFree(src);
        return false;
    }
    
    unsigned short maxDist = 0;

    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST);
    
    calculateDistanceField(chf, src, maxDist);
    chf.maxDistance = maxDist;
    
    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST);
    
    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR);
    
    // Blur
    if (boxBlur(chf, 1, src, dst) != src)
        rcSwap(src, dst);
    
    // Store distance.
    chf.dist = src;
    
    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR);

    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD);
    
    rcFree(dst);
    
    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)
{
	rcAssert(ctx);

	if (!addSpan(hf, x, y, smin, smax, area, flagMergeThr))
	{
		ctx->log(RC_LOG_ERROR, "rcAddSpan: Out of memory.");
		return false;
	}

	return true;
}

/// @par
///
/// No spans will be added if the triangle does not overlap the heightfield grid.
///
/// @see rcHeightfield
void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2,
						 const unsigned char area, rcHeightfield& solid,
						 const int flagMergeThr)
{
	rcAssert(ctx);

	ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES);

	const float ics = 1.0f/solid.cs;
	const float ich = 1.0f/solid.ch;
	rasterizeTri(v0, v1, v2, area, solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr);

	ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES);
}

void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId, rcCompactHeightfield& chf)
{
    rcAssert(ctx);

    ctx->startTimer(RC_TIMER_MARK_BOX_AREA);

    int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs);
    int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch);
    int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs);
    int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs);
    int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch);
    int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs);

    if (maxx < 0)
        return;

    if (minx >= chf.width)
        return;

    if (maxz < 0)
        return;

    if (minz >= chf.height)
        return;

    if (minx < 0) minx = 0;
    if (maxx >= chf.width) maxx = chf.width-1;
    if (minz < 0) minz = 0;
    if (maxz >= chf.height) maxz = chf.height-1;

    for (int z = minz; z <= maxz; ++z)
    {
        for (int x = minx; x <= maxx; ++x)
        {
            const rcCompactCell& c = chf.cells[x+z*chf.width];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                rcCompactSpan& s = chf.spans[i];
                if ((int)s.y >= miny && (int)s.y <= maxy)
                {
                    chf.areas[i] = areaId;
                }
            }
        }
    }
    ctx->stopTimer(RC_TIMER_MARK_BOX_AREA);
}

/// @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)
{
	rcAssert(ctx);

	rcScopedTimer timer(ctx, 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))
	{
		ctx->log(RC_LOG_ERROR, "rcRasterizeTriangle: Out of memory.");
		return false;
	}

	return true;
}

void	rcFilterUnwalkableLedgeSpans( rcContext* ctx, const int /*walkableHeight*/, const int walkableClimb, rcHeightfield& solid )
{
	rcAssert( ctx );

	ctx->startTimer( RC_TIMER_TEMPORARY );

	const int w = solid.width;
	const int h = solid.height;

	for( int y = 0; y < h; ++y ) {
		for( int x = 0; x < w; ++x ) {
			for( rcSpan* s = solid.spans[x + y*w]; s != NULL; s = s->next ) {
				if( !rcCanMovableArea( s->area ) || !rcIsObjectArea( s->area ) ) {
					continue;
				}

				const int smax = static_cast<int>( s->smax );
				int connectedEdgeCount = 0;

				for( int dir = 0; dir < 4; ++dir ) {
					int dx = x + rcGetDirOffsetX(dir);
					int dy = y + rcGetDirOffsetY(dir);
					if( dx < 0 || dy < 0 || dx >= w || dy >= h ) {
						++connectedEdgeCount;
						continue;
					}

					for( rcSpan* ns = solid.spans[dx + dy*w]; ns != NULL; ns = ns->next ) {
						const int nsmax = static_cast<int>( ns->smax );
						if( rcAbs( smax - nsmax ) <= walkableClimb*0.25f ) {
							++connectedEdgeCount;
						}
					}
				}

				if( connectedEdgeCount < 2 ) {
					s->area = RC_NULL_AREA;
				}
			}
		}
	}

	ctx->stopTimer( RC_TIMER_TEMPORARY );
}

void	rcMarkLevelSpans( rcContext* ctx, rcHeightfield& solid )
{
	rcAssert( ctx );

	ctx->startTimer( RC_TIMER_TEMPORARY );

	const int w = solid.width;
	const int h = solid.height;

	for( int y = 0; y < h; ++y ) {
		for( int x = 0; x < w; ++x ) {
			int level = 0;
			for( rcSpan* s = solid.spans[x + y*w]; s != NULL; s = s->next ) {
				s->level = level++;
			}
		}
	}

	ctx->stopTimer( RC_TIMER_TEMPORARY );
}

void	rcFilterUnderFloorObjectSpans( rcContext* ctx, rcHeightfield& solid )
{
	rcAssert( ctx );

	ctx->startTimer( RC_TIMER_TEMPORARY );

	const int w = solid.width;
	const int h = solid.height;

	for( int y = 0; y < h; ++y ) {
		for( int x = 0; x < w; ++x ) {
			for( rcSpan* s = solid.spans[x + y*w]; s != NULL && s->next != NULL; s = s->next ) {
				if( rcCanMovableArea( s->area ) /*&& rcCanMovableArea( s->next->area )*/ ) {
					s->area |= RC_UNDER_FLOOR_AREA;
				}
			}
		}
	}

	ctx->stopTimer( RC_TIMER_TEMPORARY );
}

void	rcFilterUnwalkableAreaSpans( rcContext* ctx, const unsigned char area, rcHeightfield& solid )
{
	rcAssert( ctx );

	ctx->startTimer( RC_TIMER_TEMPORARY );

	const int w = solid.width;
	const int h = solid.height;

	for( int y = 0; y < h; ++y ) {
		for( int x = 0; x < w; ++x ) {
			for( rcSpan* s = solid.spans[x + y*w]; s; s = s->next ) {
				if( s->area & area ) {
					s->area = RC_NULL_AREA;
				}
			}
		}
	}

	ctx->stopTimer( RC_TIMER_TEMPORARY );
}

/// @par
///
/// Spans will only be added for triangles that overlap the heightfield grid.
///
/// @see rcHeightfield
void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt,
						  rcHeightfield& solid, const int flagMergeThr)
{
	rcAssert(ctx);
	
	ctx->startTimer(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)
	{
		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.
		rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr);
	}
	
	ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES);
}

bool rcBuildHeightfieldLayersChunky(rcContext* ctx, rcCompactHeightfield& chf,
									const int borderSize, const int walkableHeight,
									const int chunkSize,
									rcHeightfieldLayerSet& lset)
{
	rcAssert(ctx);

	ctx->startTimer(RC_TIMER_BUILD_LAYERS);

	rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
	if (!srcReg)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount);
		return false;
	}
	memset(srcReg,0xff,sizeof(unsigned short)*chf.spanCount);

	rcLayerRegionMonotone* regs = NULL;
	int nregs = 0;

	const bool bHasRegions = CollectLayerRegionsChunky(ctx, chf, borderSize, chunkSize, srcReg, regs, nregs);
	if (!bHasRegions)
	{
		return false;
	}

	const bool bHasSaved = SplitAndStoreLayerRegions(ctx, chf, borderSize, walkableHeight, srcReg, regs, nregs, lset);
	rcFree(regs);

	if (!bHasSaved)
	{
		return false;
	}

	ctx->stopTimer(RC_TIMER_BUILD_LAYERS);

	return true;
}

/// @par
/// 
/// Non-null regions will consist of connected, non-overlapping walkable spans that form a single contour.
/// Contours will form simple polygons.
/// 
/// If multiple regions form an area that is smaller than @p minRegionArea, then all spans will be
/// re-assigned to the zero (null) region.
/// 
/// Watershed partitioning can result in smaller than necessary regions, especially in diagonal corridors. 
/// @p mergeRegionArea helps reduce unecessarily small regions.
/// 
/// See the #rcConfig documentation for more information on the configuration parameters.
/// 
/// The region data will be available via the rcCompactHeightfield::maxRegions
/// and rcCompactSpan::reg fields.
/// 
/// @warning The distance field must be created using #rcBuildDistanceField before attempting to build regions.
/// 
/// @see rcCompactHeightfield, rcCompactSpan, rcBuildDistanceField, rcBuildRegionsMonotone, rcConfig
bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
					const int borderSize, const int minRegionArea, const int mergeRegionArea)
{
	rcAssert(ctx);
	
	ctx->startTimer(RC_TIMER_BUILD_REGIONS);
	
	rcScopedDelete<unsigned short> spanBuf4 = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP);
	if (!spanBuf4)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'spanBuf4' (%d).", chf.spanCount*4);
		return false;
	}

	ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);

	unsigned short* srcReg = spanBuf4;
	if (!rcGatherRegionsNoFilter(ctx, chf, borderSize, spanBuf4))
		return false;

	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);	
	ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
	
	// Filter out small regions.
	const int chunkSize = rcMax(chf.width, chf.height);
	if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chunkSize, chf.maxRegions, chf, srcReg))
		return false;
	
	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
		
	// Write the result out.
	for (int i = 0; i < chf.spanCount; ++i)
		chf.spans[i].reg = srcReg[i];
	
	ctx->stopTimer(RC_TIMER_BUILD_REGIONS);
	
	return true;
}