static int circumCircle(const float xp, const float yp,
						const float x1, const float y1,
						const float x2, const float y2,
						const float x3, const float y3,
						float& xc, float& yc, float& rsqr)
{
	static const float EPSILON = 1e-6f;
	
	const float fabsy1y2 = rcAbs(y1-y2);
	const float fabsy2y3 = rcAbs(y2-y3);
	
	/* Check for coincident points */
	if (fabsy1y2 < EPSILON && fabsy2y3 < EPSILON)
		return 0;
	
	if (fabsy1y2 < EPSILON)
	{
		const float m2 = - (x3-x2) / (y3-y2);
		const float mx2 = (x2 + x3) / 2.0f;
		const float my2 = (y2 + y3) / 2.0f;
		xc = (x2 + x1) / 2.0f;
		yc = m2 * (xc - mx2) + my2;
	}
	else if (fabsy2y3 < EPSILON)
	{
		const float m1 = - (x2-x1) / (y2-y1);
		const float mx1 = (x1 + x2) / 2.0f;
		const float my1 = (y1 + y2) / 2.0f;
		xc = (x3 + x2) / 2.0f;
		yc = m1 * (xc - mx1) + my1;
	}
	else
	{
		const float m1 = - (x2-x1) / (y2-y1);
		const float m2 = - (x3-x2) / (y3-y2);
		const float mx1 = (x1 + x2) / 2.0f;
		const float mx2 = (x2 + x3) / 2.0f;
		const float my1 = (y1 + y2) / 2.0f;
		const float my2 = (y2 + y3) / 2.0f;
		xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
		if (fabsy1y2 > fabsy2y3)
			yc = m1 * (xc - mx1) + my1;
		else
			yc = m2 * (xc - mx2) + my2;
	}
	
	float dx,dy;
	
	dx = x2 - xc;
	dy = y2 - yc;
	rsqr = dx*dx + dy*dy;
	
	dx = xp - xc;
	dy = yp - yc;
	const float drsqr = dx*dx + dy*dy;
	
	return (drsqr <= rsqr) ? 1 : 0;
}

void duDebugDrawTriMeshSlope(duDebugDraw* dd, const float* verts, int /*nverts*/,
							 const int* tris, const float* normals, int ntris,
							 const float walkableSlopeAngle, const float texScale)
{
	if (!dd) return;
	if (!verts) return;
	if (!tris) return;
	if (!normals) return;
	
	const float walkableThr = cosf(walkableSlopeAngle/180.0f*DU_PI);
	
	float uva[2];
	float uvb[2];
	float uvc[2];
	
	dd->texture(true);

	const unsigned int unwalkable = duRGBA(192,128,0,255);
	
	dd->begin(DU_DRAW_TRIS);
	for (int i = 0; i < ntris*3; i += 3)
	{
		const float* norm = &normals[i];
		unsigned int color;
		unsigned char a = (unsigned char)(220*(2+norm[0]+norm[1])/4);
		if (norm[1] < walkableThr)
			color = duLerpCol(duRGBA(a,a,a,255), unwalkable, 64);
		else
			color = duRGBA(a,a,a,255);
		
		const float* va = &verts[tris[i+0]*3];
		const float* vb = &verts[tris[i+1]*3];
		const float* vc = &verts[tris[i+2]*3];
		
		int ax = 0, ay = 0;
		if (rcAbs(norm[1]) > rcAbs(norm[ax]))
			ax = 1;
		if (rcAbs(norm[2]) > rcAbs(norm[ax]))
			ax = 2;
		ax = (1<<ax)&3; // +1 mod 3
		ay = (1<<ax)&3; // +1 mod 3
		
		uva[0] = va[ax]*texScale;
		uva[1] = va[ay]*texScale;
		uvb[0] = vb[ax]*texScale;
		uvb[1] = vb[ay]*texScale;
		uvc[0] = vc[ax]*texScale;
		uvc[1] = vc[ay]*texScale;
		
		dd->vertex(va, color, uva);
		dd->vertex(vb, color, uvb);
		dd->vertex(vc, color, uvc);
	}
	dd->end();

	dd->texture(false);
}

void duDebugDrawLiquidTriMesh(duDebugDraw* dd, const float* verts, int /*nverts*/,
    const int* tris, const float* normals, int ntris,
    const float texScale)
{
    if (!dd) return;
    if (!verts) return;
    if (!tris) return;
    if (!normals) return;

    float uva[2];
    float uvb[2];
    float uvc[2];

    dd->texture(true);

    dd->begin(DU_DRAW_TRIS);
    for (int i = 0; i < ntris * 3; i += 3)
    {
        const float* norm = &normals[i];
        unsigned int color;
        color = duRGBA(0, 183, 205, 255);

        const float* va = &verts[tris[i + 0] * 3];
        const float* vb = &verts[tris[i + 1] * 3];
        const float* vc = &verts[tris[i + 2] * 3];

        int ax = 0, ay = 0;
        if (rcAbs(norm[1]) > rcAbs(norm[ax]))
            ax = 1;
        if (rcAbs(norm[2]) > rcAbs(norm[ax]))
            ax = 2;
        ax = (1 << ax) & 3; // +1 mod 3
        ay = (1 << ax) & 3; // +1 mod 3

        uva[0] = va[ax] * texScale;
        uva[1] = va[ay] * texScale;
        uvb[0] = vb[ax] * texScale;
        uvb[1] = vb[ay] * texScale;
        uvc[0] = vc[ax] * texScale;
        uvc[1] = vc[ay] * texScale;

        dd->vertex(va, color, uva);
        dd->vertex(vb, color, uvb);
        dd->vertex(vc, color, uvc);
    }
    dd->end();
    dd->texture(false);
}

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 );
}

static unsigned short addVertex(unsigned short x, unsigned short y, unsigned short z,
								unsigned short* verts, int* firstVert, int* nextVert, int& nv)
{
	int bucket = computeVertexHash(x, 0, z);
	int i = firstVert[bucket];
	
	while (i != -1)
	{
		const unsigned short* v = &verts[i*3];
		if (v[0] == x && (rcAbs(v[1] - y) <= 2) && v[2] == z)
			return (unsigned short)i;
		i = nextVert[i]; // next
	}
	
	// Could not find, create new.
	i = nv; nv++;
	unsigned short* v = &verts[i*3];
	v[0] = x;
	v[1] = y;
	v[2] = z;
	nextVert[i] = firstVert[bucket];
	firstVert[bucket] = i;
	
	return (unsigned short)i;
}

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);
}

// TODO: Missuses ledge flag, must be called before rcFilterLedgeSpans!
void rcFilterLowHangingWalkableObstacles(const int walkableClimb, rcHeightfield& solid)
{
	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;
			for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next)
			{
				const bool walkable = (s->flags & RC_WALKABLE) != 0;
				const bool previousWalkable = ps && (ps->flags & RC_WALKABLE) != 0;
				// If current span is not walkable, but there is walkable
				// span just below it, mark the span above it walkable too.
				// Missuse the edge flag so that walkable flag cannot propagate
				// past multiple non-walkable objects.
				if (!walkable && previousWalkable)
				{
					if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb)
						s->flags |= RC_LEDGE;
				}
			}
			// Transfer "fake ledges" to walkables.
			for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next)
			{
				if (s->flags & RC_LEDGE)
					s->flags |= RC_WALKABLE;
				s->flags &= ~RC_LEDGE;
			}
		}
	}
}

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	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	rcMarkSideLedgeSpans( 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 ) {
			for( rcSpan* s = solid.spans[x + y*w]; s != NULL; s = s->next ) {
				if( !rcIsObjectArea( s->area ) || !rcIsWalkableObjectArea( s->area ) ) {
					continue;
				}
				for( int dir = 0; dir < 4; ++dir ) {
					const int dx = x + rcGetDirOffsetX(dir);
					const int dy = y + rcGetDirOffsetY(dir);
					if( dx < 0 || dy < 0 || dx >= w || dy >= h ) {
						continue;
					}
					for( rcSpan* ns = solid.spans[dx + dy*w]; ns != NULL; ns = ns->next ) {
						if( (ns->area & RC_UNWALKABLE_AREA) == RC_UNWALKABLE_AREA ) {
							const int gap = rcAbs( static_cast<int>(s->smax) - static_cast<int>(ns->smax) );
							if( gap <= walkableClimb ) {
								s->area |= RC_CLIMBABLE_AREA;
							}
						}
					}
				}
			}
		}
	}

	ctx->stopTimer( RC_TIMER_TEMPORARY );
}

static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
										   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.
	
	// Note: Reads to the compact heightfield are offset by border size (bs)
	// since border size offset is already removed from the polymesh vertices.
	
	memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height);
	
	stack.resize(0);
	
	static const int offset[9*2] =
	{
		0,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1, -1,0,
	};
	
	// Use poly vertices as seed points for the flood fill.
	for (int j = 0; j < npoly; ++j)
	{
		int cx = 0, cz = 0, ci =-1;
		int dmin = RC_UNSET_HEIGHT;
		for (int k = 0; k < 9; ++k)
		{
			const int ax = (int)verts[poly[j]*3+0] + offset[k*2+0];
			const int ay = (int)verts[poly[j]*3+1];
			const int az = (int)verts[poly[j]*3+2] + offset[k*2+1];
			if (ax < hp.xmin || ax >= hp.xmin+hp.width ||
				az < hp.ymin || az >= hp.ymin+hp.height)
				continue;
			
			const rcCompactCell& c = chf.cells[(ax+bs)+(az+bs)*chf.width];
			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
			{
				const rcCompactSpan& s = chf.spans[i];
				int d = rcAbs(ay - (int)s.y);
				if (d < dmin)
				{
					cx = ax;
					cz = az;
					ci = i;
					dmin = d;
				}
			}
		}
		if (ci != -1)
		{
			stack.push(cx);
			stack.push(cz);
			stack.push(ci);
		}
	}
	
	// Find center of the polygon using flood fill.
	int pcx = 0, pcz = 0;
	for (int j = 0; j < npoly; ++j)
	{
		pcx += (int)verts[poly[j]*3+0];
		pcz += (int)verts[poly[j]*3+2];
	}
	pcx /= npoly;
	pcz /= npoly;
	
	for (int i = 0; i < stack.size(); i += 3)
	{
		int cx = stack[i+0];
		int cy = stack[i+1];
		int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width;
		hp.data[idx] = 1;
	}
	
	while (stack.size() > 0)
	{
		int ci = stack.pop();
		int cy = stack.pop();
		int cx = stack.pop();
		
		// Check if close to center of the polygon.
		if (rcAbs(cx-pcx) <= 1 && rcAbs(cy-pcz) <= 1)
		{
			stack.resize(0);
			stack.push(cx);
			stack.push(cy);
			stack.push(ci);
			break;
		}
		
		const rcCompactSpan& cs = chf.spans[ci];
		
		for (int dir = 0; dir < 4; ++dir)
		{
			if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue;
			
			const int ax = cx + rcGetDirOffsetX(dir);
			const int ay = cy + rcGetDirOffsetY(dir);
			
			if (ax < hp.xmin || ax >= (hp.xmin+hp.width) ||
//.........这里部分代码省略.........

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

	ctx->startTimer(RC_TIMER_FILTER_BORDER);

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

	// Mark border spans.
	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)
			{
				// Skip non walkable spans.
				if (s->area == RC_NULL_AREA)
					continue;

				const int bot = (int)(s->smax);
				const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;

				// Find neighbours minimum height.
				int minh = MAX_HEIGHT;

				// Min and max height of accessible neighbours.
				int asmin = s->smax;
				int asmax = s->smax;

				for (int dir = 0; dir < 4; ++dir)
				{
					int dx = x + rcGetDirOffsetX(dir);
					int dy = y + rcGetDirOffsetY(dir);
					// Skip neighbours which are out of bounds.
					if (dx < 0 || dy < 0 || dx >= w || dy >= h)
					{
						minh = rcMin(minh, -walkableClimb - bot);
						continue;
					}

					// From minus infinity to the first span.
					rcSpan* ns = solid.spans[dx + dy*w];
					int nbot = -walkableClimb;
					int ntop = ns ? (int)ns->smin : MAX_HEIGHT;
					// Skip neightbour if the gap between the spans is too small.
					if (rcMin(top, ntop) - rcMax(bot, nbot) > walkableHeight)
						minh = rcMin(minh, nbot - bot);

					// Rest of the spans.
					for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
					{
						nbot = (int)ns->smax;
						ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
						// Skip neightbour if the gap between the spans is too small.
						if (rcMin(top, ntop) - rcMax(bot, nbot) > walkableHeight)
						{
							minh = rcMin(minh, nbot - bot);

							// Find min/max accessible neighbour height.
							if (rcAbs(nbot - bot) <= walkableClimb)
							{
								if (nbot < asmin) asmin = nbot;
								if (nbot > asmax) asmax = nbot;
							}
						}
					}
				}

				// The current span is close to a ledge if the drop to any
				// neighbour span is less than the walkableClimb.
				if (minh < -walkableClimb)
					s->area = RC_NULL_AREA;

				// If the difference between all neighbours is too large,
				// we are at steep slope, mark the span as ledge.
				if ((asmax - asmin) > walkableClimb)
				{
					s->area = RC_NULL_AREA;
				}
			}
		}
	}

	ctx->stopTimer(RC_TIMER_FILTER_BORDER);
}

void rcFilterLedgeSpans(const int walkableHeight,
						const int walkableClimb,
						rcHeightfield& solid)
{
	rcTimeVal startTime = rcGetPerformanceTimer();

	const int w = solid.width;
	const int h = solid.height;
	const int MAX_HEIGHT = 0xffff;
	
	// Mark border spans.
	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)
			{
				// Skip non walkable spans.
				if ((s->flags & RC_WALKABLE) == 0)
					continue;
				
				const int bot = (int)(s->smax);
				const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
				
				// Find neighbours minimum height.
				int minh = MAX_HEIGHT;

				// Min and max height of accessible neighbours.
				int asmin = s->smax;
				int asmax = s->smax;

				for (int dir = 0; dir < 4; ++dir)
				{
					int dx = x + rcGetDirOffsetX(dir);
					int dy = y + rcGetDirOffsetY(dir);
					// Skip neighbours which are out of bounds.
					if (dx < 0 || dy < 0 || dx >= w || dy >= h)
					{
						minh = rcMin(minh, -walkableClimb - bot);
						continue;
					}

					// From minus infinity to the first span.
					rcSpan* ns = solid.spans[dx + dy*w];
					int nbot = -walkableClimb;
					int ntop = ns ? (int)ns->smin : MAX_HEIGHT;
					// Skip neightbour if the gap between the spans is too small.
					if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
						minh = rcMin(minh, nbot - bot);
					
					// Rest of the spans.
					for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
					{
						nbot = (int)ns->smax;
						ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
						// Skip neightbour if the gap between the spans is too small.
						if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
						{
							minh = rcMin(minh, nbot - bot);
						
							// Find min/max accessible neighbour height. 
							if (rcAbs(nbot - bot) <= walkableClimb)
							{
								if (nbot < asmin) asmin = nbot;
								if (nbot > asmax) asmax = nbot;
							}
							
						}
					}
				}
				
				// The current span is close to a ledge if the drop to any
				// neighbour span is less than the walkableClimb.
				if (minh < -walkableClimb)
					s->flags |= RC_LEDGE;
					
				// If the difference between all neighbours is too large,
				// we are at steep slope, mark the span as ledge.
				if ((asmax - asmin) > walkableClimb)
				{
					s->flags |= RC_LEDGE;
				}
			}
		}
	}
	
	rcTimeVal endTime = rcGetPerformanceTimer();
//	if (rcGetLog())
//		rcGetLog()->log(RC_LOG_PROGRESS, "Filter border: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
	if (rcGetBuildTimes())
		rcGetBuildTimes()->filterBorder += rcGetDeltaTimeUsec(startTime, endTime);
}	

bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb,
							   unsigned char flags, rcHeightfield& hf,
							   rcCompactHeightfield& chf)
{
	rcTimeVal startTime = rcGetPerformanceTimer();
	
	const int w = hf.width;
	const int h = hf.height;
	const int spanCount = getSpanCount(flags, hf);

	// Fill in header.
	chf.width = w;
	chf.height = h;
	chf.spanCount = spanCount;
	chf.walkableHeight = walkableHeight;
	chf.walkableClimb = walkableClimb;
	chf.maxRegions = 0;
	vcopy(chf.bmin, hf.bmin);
	vcopy(chf.bmax, hf.bmax);
	chf.bmax[1] += walkableHeight*hf.ch;
	chf.cs = hf.cs;
	chf.ch = hf.ch;
	chf.cells = new rcCompactCell[w*h];
	if (!chf.cells)
	{
		if (rcGetLog())
			rcGetLog()->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
		return false;
	}
	memset(chf.cells, 0, sizeof(rcCompactCell)*w*h);
	chf.spans = new rcCompactSpan[spanCount];
	if (!chf.spans)
	{
		if (rcGetLog())
			rcGetLog()->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
		return false;
	}
	memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount);
	
	const int MAX_HEIGHT = 0xffff;
	
	// Fill in cells and spans.
	int idx = 0;
	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			const rcSpan* s = hf.spans[x + y*w];
			// If there are no spans at this cell, just leave the data to index=0, count=0.
			if (!s) continue;
			rcCompactCell& c = chf.cells[x+y*w];
			c.index = idx;
			c.count = 0;
			while (s)
			{
				if (s->flags == flags)
				{
					const int bot = (int)s->smax;
					const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
					chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
					chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
					idx++;
					c.count++;
				}
				s = s->next;
			}
		}
	}

	// Find neighbour connections.
	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			const rcCompactCell& c = chf.cells[x+y*w];
			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
			{
				rcCompactSpan& s = chf.spans[i];
				for (int dir = 0; dir < 4; ++dir)
				{
					setCon(s, dir, 0xf);
					const int nx = x + rcGetDirOffsetX(dir);
					const int ny = y + rcGetDirOffsetY(dir);
					// First check that the neighbour cell is in bounds.
					if (nx < 0 || ny < 0 || nx >= w || ny >= h)
						continue;
					// Iterate over all neighbour spans and check if any of the is
					// accessible from current cell.
					const rcCompactCell& nc = chf.cells[nx+ny*w];
					for (int k = (int)nc.index, nk = (int)(nc.index+nc.count); k < nk; ++k)
					{
						const rcCompactSpan& ns = chf.spans[k];
						const int bot = rcMax(s.y, ns.y);
						const int top = rcMin(s.y+s.h, ns.y+ns.h);

						// Check that the gap between the spans is walkable,
						// and that the climb height between the gaps is not too high.
						if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb)
						{
							// Mark direction as walkable.
//.........这里部分代码省略.........

static void seedArrayWithPolyCenter(rcContext* ctx, const rcCompactHeightfield& chf,
									const unsigned short* poly, const int npoly,
									const unsigned short* verts, const int bs,
									rcHeightPatch& hp, rcIntArray& array)
{
	// Note: Reads to the compact heightfield are offset by border size (bs)
	// since border size offset is already removed from the polymesh vertices.
	
	static const int offset[9*2] =
	{
		0,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1, -1,0,
	};
	
	// Find cell closest to a poly vertex
	int startCellX = 0, startCellY = 0, startSpanIndex = -1;
	int dmin = RC_UNSET_HEIGHT;
	for (int j = 0; j < npoly && dmin > 0; ++j)
	{
		for (int k = 0; k < 9 && dmin > 0; ++k)
		{
			const int ax = (int)verts[poly[j]*3+0] + offset[k*2+0];
			const int ay = (int)verts[poly[j]*3+1];
			const int az = (int)verts[poly[j]*3+2] + offset[k*2+1];
			if (ax < hp.xmin || ax >= hp.xmin+hp.width ||
				az < hp.ymin || az >= hp.ymin+hp.height)
				continue;
			
			const rcCompactCell& c = chf.cells[(ax+bs)+(az+bs)*chf.width];
			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni && dmin > 0; ++i)
			{
				const rcCompactSpan& s = chf.spans[i];
				int d = rcAbs(ay - (int)s.y);
				if (d < dmin)
				{
					startCellX = ax;
					startCellY = az;
					startSpanIndex = i;
					dmin = d;
				}
			}
		}
	}
	
	rcAssert(startSpanIndex != -1);
	// Find center of the polygon
	int pcx = 0, pcy = 0;
	for (int j = 0; j < npoly; ++j)
	{
		pcx += (int)verts[poly[j]*3+0];
		pcy += (int)verts[poly[j]*3+2];
	}
	pcx /= npoly;
	pcy /= npoly;
	
	// Use seeds array as a stack for DFS
	array.resize(0);
	array.push(startCellX);
	array.push(startCellY);
	array.push(startSpanIndex);

	int dirs[] = { 0, 1, 2, 3 };
	memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height);
	// DFS to move to the center. Note that we need a DFS here and can not just move
	// directly towards the center without recording intermediate nodes, even though the polygons
	// are convex. In very rare we can get stuck due to contour simplification if we do not
	// record nodes.
	int cx = -1, cy = -1, ci = -1;
	while (true)
	{
		if (array.size() < 3)
		{
			ctx->log(RC_LOG_WARNING, "Walk towards polygon center failed to reach center");
			break;
		}

		ci = array.pop();
		cy = array.pop();
		cx = array.pop();

		if (cx == pcx && cy == pcy)
			break;

		// If we are already at the correct X-position, prefer direction
		// directly towards the center in the Y-axis; otherwise prefer
		// direction in the X-axis
		int directDir;
		if (cx == pcx)
			directDir = rcGetDirForOffset(0, pcy > cy ? 1 : -1);
		else
			directDir = rcGetDirForOffset(pcx > cx ? 1 : -1, 0);

		// Push the direct dir last so we start with this on next iteration
		rcSwap(dirs[directDir], dirs[3]);

		const rcCompactSpan& cs = chf.spans[ci];
		for (int i = 0; i < 4; i++)
		{
			int dir = dirs[i];
			if (rcGetCon(cs, dir) == RC_NOT_CONNECTED)
				continue;
//.........这里部分代码省略.........

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)
{
	
	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])
	{
		hf.spans[idx] = s;
		return true;
	}
	rcSpan* prev = 0;
	rcSpan* cur = hf.spans[idx];
	
	// Insert and merge spans.
	while (cur)
	{
		if (cur->smin > s->smax)
		{
			// Current span is further than the new span, break.
			break;
		}
		else if (cur->smax < s->smin)
		{
			// Current span is before the new span advance.
			prev = cur;
			cur = cur->next;
		}
		else
		{
			// Merge spans.
			if (cur->smin < s->smin)
				s->smin = cur->smin;
			if (cur->smax > s->smax)
				s->smax = cur->smax;
			
			// Merge flags.
			if (rcAbs((int)s->smax - (int)cur->smax) <= flagMergeThr)
				s->area = rcMax(s->area, cur->area);
			
			// Remove current span.
			rcSpan* next = cur->next;
			freeSpan(hf, cur);
			if (prev)
				prev->next = next;
			else
				hf.spans[idx] = next;
			cur = next;
		}
	}
	
	// Insert new span.
	if (prev)
	{
		s->next = prev->next;
		prev->next = s;
	}
	else
	{
		s->next = hf.spans[idx];
		hf.spans[idx] = s;
	}

	return true;
}

static void getHeightData(const rcCompactHeightfield& chf,
						  const unsigned short* poly, const int npoly,
						  const unsigned short* verts,
						  rcHeightPatch& hp, rcIntArray& stack)
{
	// Floodfill the heightfield to get 2D height data,
	// starting at vertex locations as seeds.
	
	memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);

	stack.resize(0);
	
	// Use poly vertices as seed points for the flood fill.
	for (int j = 0; j < npoly; ++j)
	{
		const int ax = (int)verts[poly[j]*3+0];
		const int ay = (int)verts[poly[j]*3+1];
		const int az = (int)verts[poly[j]*3+2];
		if (ax < hp.xmin || ax >= hp.xmin+hp.width ||
			az < hp.ymin || az >= hp.ymin+hp.height)
			continue;
			
		const rcCompactCell& c = chf.cells[ax+az*chf.width];
		int dmin = 0xffff;
		int ai = -1;
		for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
		{
			const rcCompactSpan& s = chf.spans[i];
			int d = rcAbs(ay - (int)s.y);
			if (d < dmin)
			{
				ai = i;
				dmin = d;
			}
		}
		if (ai != -1)
		{
			stack.push(ax);
			stack.push(az);
			stack.push(ai);
		}
	}

	while (stack.size() > 0)
	{
		int ci = stack.pop();
		int cy = stack.pop();
		int cx = stack.pop();

		// Skip already visited locations.
		int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width;
		if (hp.data[idx] != 0xffff)
			continue;
		
		const rcCompactSpan& cs = chf.spans[ci];
		hp.data[idx] = cs.y;
		
		for (int dir = 0; dir < 4; ++dir)
		{
			if (rcGetCon(cs, dir) == 0xf) continue;
			
			const int ax = cx + rcGetDirOffsetX(dir);
			const int ay = cy + rcGetDirOffsetY(dir);
		
			if (ax < hp.xmin || ax >= (hp.xmin+hp.width) ||
				ay < hp.ymin || ay >= (hp.ymin+hp.height))
				continue;

			if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != 0xffff)
				continue;

			const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(cs, dir);
			
			stack.push(ax);
			stack.push(ay);
			stack.push(ai);
		}
	}	
}

bool rcMarkReachableSpans(const int walkableHeight,
						  const int walkableClimb,
						  rcHeightfield& solid)
{
	const int w = solid.width;
	const int h = solid.height;
	const int MAX_HEIGHT = 0xffff;
	
	rcTimeVal startTime = rcGetPerformanceTimer();
	
	// Build navigable space.
	const int MAX_SEEDS = w*h;
	rcReachableSeed* stack = new rcReachableSeed[MAX_SEEDS];
	if (!stack)
	{
		if (rcGetLog())
			rcGetLog()->log(RC_LOG_ERROR, "rcMarkReachableSpans: Out of memory 'stack' (%d).", MAX_SEEDS);
		return false;
	}
	int stackSize = 0;
	
	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			rcSpan* topSpan = solid.spans[x + y*w];
			if (!topSpan)
				continue;
			while (topSpan->next)
				topSpan = topSpan->next;
			
			// If the span is not walkable, skip it.
			if ((topSpan->flags & RC_WALKABLE) == 0)
				continue;
			// If the span has been visited already, skip it.
			if (topSpan->flags & RC_REACHABLE)
				continue;
			
			// Start flood fill.
			topSpan->flags |= RC_REACHABLE;
			stackSize = 0;
			stack[stackSize].set(x, y, topSpan);
			stackSize++;
			
			while (stackSize)
			{
				// Pop a seed from the stack.
				stackSize--;
				rcReachableSeed cur = stack[stackSize];
				
				const int bot = (int)cur.s->smax;
				const int top = (int)cur.s->next ? (int)cur.s->next->smin : MAX_HEIGHT;
				
				// Visit neighbours in all 4 directions.
				for (int dir = 0; dir < 4; ++dir)
				{
					int dx = (int)cur.x + rcGetDirOffsetX(dir);
					int dy = (int)cur.y + rcGetDirOffsetY(dir);
					// Skip neighbour which are out of bounds.
					if (dx < 0 || dy < 0 || dx >= w || dy >= h)
						continue;
					for (rcSpan* ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
					{
						// Skip neighbour if it is not walkable.
						if ((ns->flags & RC_WALKABLE) == 0)
							continue;
						// Skip the neighbour if it has been visited already.
						if (ns->flags & RC_REACHABLE)
							continue;
						
						const int nbot = (int)ns->smax;
						const int ntop = (int)ns->next ? (int)ns->next->smin : MAX_HEIGHT;
						// Skip neightbour if the gap between the spans is too small.
						if (rcMin(top,ntop) - rcMax(bot,nbot) < walkableHeight)
							continue;
						// Skip neightbour if the climb height to the neighbour is too high.
						if (rcAbs(nbot - bot) >= walkableClimb)
							continue;
						
						// This neighbour has not been visited yet.
						// Mark it as reachable and add it to the seed stack.
						ns->flags |= RC_REACHABLE;
						if (stackSize < MAX_SEEDS)
						{
							stack[stackSize].set(dx, dy, ns);
							stackSize++;
						}
					}
				}
			}
		}
	}
	
	delete [] stack;	
	
	rcTimeVal endTime = rcGetPerformanceTimer();
	
//	if (rcGetLog())
//		rcGetLog()->log(RC_LOG_PROGRESS, "Mark reachable: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
	if (rcGetBuildTimes())
//.........这里部分代码省略.........

static void getHeightData(const rcCompactHeightfield& chf,
						  const unsigned short* poly, const int npoly,
						  const unsigned short* verts,
						  rcHeightPatch& hp, rcIntArray& stack)
{
	// Floodfill the heightfield to get 2D height data,
	// starting at vertex locations as seeds.

	memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height);

	stack.resize(0);

	static const int offset[9*2] =
	{
		0,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1, -1,0,
	};

	// Use poly vertices as seed points for the flood fill.
	for (int j = 0; j < npoly; ++j)
	{
		int cx = 0, cz = 0, ci =-1;
		int dmin = RC_UNSET_HEIGHT;
		for (int k = 0; k < 9; ++k)
		{
			const int ax = (int)verts[poly[j]*3+0] + offset[k*2+0];
			const int ay = (int)verts[poly[j]*3+1];
			const int az = (int)verts[poly[j]*3+2] + offset[k*2+1];
			if (ax < hp.xmin || ax >= hp.xmin+hp.width ||
				az < hp.ymin || az >= hp.ymin+hp.height)
				continue;

			const rcCompactCell& c = chf.cells[ax+az*chf.width];
			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
			{
				const rcCompactSpan& s = chf.spans[i];
				int d = rcAbs(ay - (int)s.y);
				if (d < dmin)
				{
					cx = ax;
					cz = az;
					ci = i;
					dmin = d;
				}
			}
		}
		if (ci != -1)
		{
			stack.push(cx);
			stack.push(cz);
			stack.push(ci);
		}
	}

	// Find center of the polygon using flood fill.
	int pcx = 0, pcz = 0;
	for (int j = 0; j < npoly; ++j)
	{
		pcx += (int)verts[poly[j]*3+0];
		pcz += (int)verts[poly[j]*3+2];
	}
	pcx /= npoly;
	pcz /= npoly;

	for (int i = 0; i < stack.size(); i += 3)
	{
		int cx = stack[i+0];
		int cy = stack[i+1];
		int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width;
		hp.data[idx] = 1;
	}

	while (stack.size() > 0)
	{
		int ci = stack.pop();
		int cy = stack.pop();
		int cx = stack.pop();

		// Check if close to center of the polygon.
		if (rcAbs(cx-pcx) <= 1 && rcAbs(cy-pcz) <= 1)
		{
			stack.resize(0);
			stack.push(cx);
			stack.push(cy);
			stack.push(ci);
			break;
		}

		const rcCompactSpan& cs = chf.spans[ci];

		for (int dir = 0; dir < 4; ++dir)
		{
			if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue;

			const int ax = cx + rcGetDirOffsetX(dir);
			const int ay = cy + rcGetDirOffsetY(dir);

			if (ax < hp.xmin || ax >= (hp.xmin+hp.width) ||
				ay < hp.ymin || ay >= (hp.ymin+hp.height))
				continue;

//.........这里部分代码省略.........

//.........这里部分代码省略.........
	memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount);
	chf.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*spanCount, RC_ALLOC_PERM);
	if (!chf.areas)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.areas' (%d)", spanCount);
		return false;
	}
	memset(chf.areas, RC_NULL_AREA, sizeof(unsigned char)*spanCount);

	const int MAX_HEIGHT = 0xffff;

	// Fill in cells and spans.
	int idx = 0;
	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			const rcSpan* s = hf.spans[x + y*w];
			// If there are no spans at this cell, just leave the data to index=0, count=0.
			if (!s) continue;
			rcCompactCell& c = chf.cells[x + y*w];
			c.index = idx;
			c.count = 0;
			while (s)
			{
				if (s->area != RC_NULL_AREA)
				{
					const int bot = (int)s->smax;
					const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
					chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
					chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
					chf.areas[idx] = s->area;
					idx++;
					c.count++;
				}
				s = s->next;
			}
		}
	}

	// Find neighbour connections.
	const int MAX_LAYERS = RC_NOT_CONNECTED - 1;
	int tooHighNeighbour = 0;
	for (int y = 0; y < h; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			const rcCompactCell& c = chf.cells[x + y*w];
			for (int i = (int)c.index, ni = (int)(c.index + c.count); i < ni; ++i)
			{
				rcCompactSpan& s = chf.spans[i];

				for (int dir = 0; dir < 4; ++dir)
				{
					rcSetCon(s, dir, RC_NOT_CONNECTED);
					const int nx = x + rcGetDirOffsetX(dir);
					const int ny = y + rcGetDirOffsetY(dir);
					// First check that the neighbour cell is in bounds.
					if (nx < 0 || ny < 0 || nx >= w || ny >= h)
						continue;

					// Iterate over all neighbour spans and check if any of the is
					// accessible from current cell.
					const rcCompactCell& nc = chf.cells[nx + ny*w];
					for (int k = (int)nc.index, nk = (int)(nc.index + nc.count); k < nk; ++k)
					{
						const rcCompactSpan& ns = chf.spans[k];
						const int bot = rcMax(s.y, ns.y);
						const int top = rcMin(s.y + s.h, ns.y + ns.h);

						// Check that the gap between the spans is walkable,