算法篇 — NavMesh 导航 — （2）生成导航网格

Navmesh 的寻路依赖于导航网格的生成，本文将基于 Recast Navigation 源码进行分析。

简介

初始化生成配置

• 导航网格的生成配置结构 rcConfig 如下：

// Recast/Include/Recast.h

...

struct rcConfig
{
	/// The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
	int width;

	/// The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
	int height;
	
	/// The width/height size of tile's on the xz-plane. [Limit: >= 0] [Units: vx]
	int tileSize;
	
	/// The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
	int borderSize;

	/// The xz-plane cell size to use for fields. [Limit: > 0] [Units: wu] 
	float cs;

	/// The y-axis cell size to use for fields. [Limit: > 0] [Units: wu]
	float ch;

	/// The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
	float bmin[3]; 

	/// The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
	float bmax[3];

	/// The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees] 
	float walkableSlopeAngle;

	/// Minimum floor to 'ceiling' height that will still allow the floor area to 
	/// be considered walkable. [Limit: >= 3] [Units: vx] 
	int walkableHeight;
	
	/// Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx] 
	int walkableClimb;
	
	/// The distance to erode/shrink the walkable area of the heightfield away from 
	/// obstructions.  [Limit: >=0] [Units: vx] 
	int walkableRadius;
	
	/// The maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx] 
	int maxEdgeLen;
	
	/// The maximum distance a simplified contour's border edges should deviate 
	/// the original raw contour. [Limit: >=0] [Units: vx]
	float maxSimplificationError;
	
	/// The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx] 
	int minRegionArea;
	
	/// Any regions with a span count smaller than this value will, if possible, 
	/// be merged with larger regions. [Limit: >=0] [Units: vx] 
	int mergeRegionArea;
	
	/// The maximum number of vertices allowed for polygons generated during the 
	/// contour to polygon conversion process. [Limit: >= 3] 
	int maxVertsPerPoly;
	
	/// Sets the sampling distance to use when generating the detail mesh.
	/// (For height detail only.) [Limits: 0 or >= 0.9] [Units: wu] 
	float detailSampleDist;
	
	/// The maximum distance the detail mesh surface should deviate from heightfield
	/// data. (For height detail only.) [Limit: >=0] [Units: wu] 
	float detailSampleMaxError;
};

...

• rcConfig 参数的含义如下：
  • width
    • 场在 x 轴上的宽度，由网格包围盒的宽度换算成单元格表示。
  • height
    • 场在 z 轴上的高度，由网格包围盒的高度换算成单元格表示。
  • tileSize
    • xz 平面上的瓦片大小。
  • borderSize
    • 高度场不可导航边界的大小。
  • cs
    • 场在 xz 平面上的单元格大小。
  • ch
    • 场在 y 轴上的单元格大小。
  • bmin[3]
    • 场的 AABB 包围盒的最小边界。
  • bmax[3]
    • 场的 AABB 包围盒的最大边界。
  • walkableSlopeAngle
    • 可行走的最大斜坡角度（0° ~ 90°）。
  • walkableHeight
    • 行走时地面到天花板的最小距离（>= 3）。
  • walkableClimb
    • 可跨越的最大高度。
  • walkableRadius
    • 在生成可行走区域时，需要从障碍物边缘向内收缩（侵蚀）的距离。
  • maxEdgeLen
    • 轮廓边缘在网格边界上的最大长度。
  • maxSimplificationError
    • 简化后的轮廓边缘和原轮廓之间需要偏离的最大距离。
  • minRegionArea
    • 形成孤岛区域的最小单元格数量。
  • mergeRegionArea
    • 区域包含的单元格数量少于该值时，尝试将此区域合并到更大的相邻区域。
  • maxVertsPerPoly
    • 单个多边形的最大顶点数（>= 3）。
  • detailSampleDist
    • 生成细节网格（高度细节）的采样间距（0 或 >= 0.9）。
  • detailSampleMaxError
    • 细节网格（高度细节）表面与原始高度场数据的最大允许偏差。

光栅化输入的多边形汤

• 输入的原始 3D 模型数据，通常是一组无序的三角形（或其他多边形），没有明确的拓扑结构或层级关系，这些多边形可能重叠、重复或不封闭，统称为多边形汤，光栅化过程需要对这一组三角形做处理。

标记可行走三角面

• 通过 rcMarkWalkableTriangles 方法，将坡度小于 walkableSlopeAngle 的三角面标记为可行走区域，其实现如下：

// Recast/Source/Recast.cpp

...

void rcMarkWalkableTriangles(rcContext* context, const float walkableSlopeAngle,
                             const float* verts, const int numVerts,
                             const int* tris, const int numTris,
                             unsigned char* triAreaIDs)
{
	rcIgnoreUnused(context);
	rcIgnoreUnused(numVerts);

	const float walkableThr = cosf(walkableSlopeAngle / 180.0f * RC_PI);

	float norm[3];

	for (int i = 0; i < numTris; ++i)
	{
		const int* tri = &tris[i * 3];
		calcTriNormal(&verts[tri[0] * 3], &verts[tri[1] * 3], &verts[tri[2] * 3], norm);
		// Check if the face is walkable.
		if (norm[1] > walkableThr)
		{
			triAreaIDs[i] = RC_WALKABLE_AREA;
		}
	}
}

...

• 其中，calcTriNormal 方法用于计算三角面的归一化法线。三角面和法线的示意图如下：
• 三角面和 xz 平面的夹角即为坡度 θ，而法线和 y 轴的夹角也为 θ。由于法线为归一化，则法线在 y 轴上的投影即为 cosθ。随着坡度 θ 增大，cosθ 逐渐减小，当坡度 θ 小于 walkableSlopeAngle 时，该三角面则为可行走区域，将三角面的 areaID 设置为 RC_WALKABLE_AREA。
• 光栅化前先对坡度较大的三角面进行过滤，比起光栅化后再对每一个 cell 进行坡度判断，可以减少较多的计算量。

光栅化三角面

• 光栅化三角面的过程，主要是对每个三角面，通过 rasterizeTri 方法进行处理，其实现如下：

// Recast/Source/RecastRasterization.cpp

static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
                         const unsigned char areaID, rcHeightfield& heightfield,
                         const float* heightfieldBBMin, const float* heightfieldBBMax,
                         const float cellSize, const float inverseCellSize, const float inverseCellHeight,
                         const int flagMergeThreshold)
{
	// Calculate the bounding box of the triangle.
	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, heightfieldBBMin, heightfieldBBMax))
	{
		return true;
	}

	const int w = heightfield.width;
	const int h = heightfield.height;
	const float by = heightfieldBBMax[1] - heightfieldBBMin[1];

	// Calculate the footprint of the triangle on the grid's z-axis
	int z0 = (int)((triBBMin[2] - heightfieldBBMin[2]) * inverseCellSize);
	int z1 = (int)((triBBMax[2] - heightfieldBBMin[2]) * inverseCellSize);

	// use -1 rather than 0 to cut the polygon properly at the start of the tile
	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;
	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;
	int nvIn = 3;

	for (int z = z0; z <= z1; ++z)
	{
		// Clip polygon to row. Store the remaining polygon as well
		const float cellZ = heightfieldBBMin[2] + (float)z * cellSize;
		dividePoly(in, nvIn, inRow, &nvRow, p1, &nvIn, cellZ + cellSize, RC_AXIS_Z);
		rcSwap(in, p1);
		
		if (nvRow < 3)
		{
			continue;
		}
		if (z < 0)
		{
			continue;
		}
		
		// 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 - heightfieldBBMin[0]) * inverseCellSize);
		int x1 = (int)((maxX - heightfieldBBMin[0]) * inverseCellSize);
		if (x1 < 0 || x0 >= w)
		{
			continue;
		}
		x0 = rcClamp(x0, -1, w - 1);
		x1 = rcClamp(x1, 0, w - 1);

		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 = heightfieldBBMin[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 spanMin = p1[1];
			float spanMax = p1[1];
			for (int vert = 1; vert < nv; ++vert)
			{
				spanMin = rcMin(spanMin, p1[vert * 3 + 1]);
				spanMax = rcMax(spanMax, p1[vert * 3 + 1]);
			}
			spanMin -= heightfieldBBMin[1];
			spanMax -= heightfieldBBMin[1];
			
			// Skip the span if it's completely outside the heightfield bounding box
			if (spanMax < 0.0f)
			{
				continue;
			}
			if (spanMin > by)
			{
				continue;
			}
			
			// 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(heightfield, x, z, spanMinCellIndex, spanMaxCellIndex, areaID, flagMergeThreshold))
			{
				return false;
			}
		}
	}

	return true;
}

...

• 光栅化过程就是将三角面沿着 z 轴和 x 轴进行切分，再计算 y 高度，从而得到多个长方体，主要步骤如下：
  • 计算三角面包围盒的最大最小值，检查包围盒是否和高度场的包围盒有交集，无交集则不需要处理。
  • 将三角面包围盒的 z 坐标最大最小值，以高度场包围盒 z 坐标最小值为基准，转化为 cell 的 z' 表示。
  • 将 z' 最小值限制为 [-1, heightfield.height - 1] ，最大值限制为 [0, heightfield.height - 1] 。
  • 遍历 z' 坐标最小值到最大值区间，通过 dividePoly 方法，将三角面按 cell 的 z' 切分成多个多边形。
  • 对每个切分后的多边形，计算包围盒的 x 坐标最大最小值，，以高度场包围盒 x 坐标最小值为基准，转化为 cell 的 x' 表示。
  • 将 x' 最小值限制为 [-1, heightfield.width - 1] , 最大值限制为 [0, heightfield.width - 1] 。
  • 遍历 x' 坐标最小值到最大值区间，通过 dividePoly 方法，将多边形按 cell 的 x' 坐标再切分成多个子多边形。
  • 对每个子多边形，计算顶点的 y 坐标最大最小值，以高度场包围盒 y 坐标最小值为基准。
  • 将顶点 y 坐标最大最小值，转换成 cell 索引 y' 表示，最小值为 [0, RC_SPAN_MAX_HEIGHT] ，最大值为 [最小值 + 1, RC_SPAN_MAX_HEIGHT] 。
  • 调用 addSpan 方法，将当前 x' 、z' 对应的 cell 的 y' 索引区间，加入到高度场中。
• 分割多边形方法 dividePoly 的实现如下：

// Recast/Source/RecastRasterization.cpp

static void dividePoly(const float* inVerts, int inVertsCount,
                       float* outVerts1, int* outVerts1Count,
                       float* outVerts2, int* outVerts2Count,
                       float axisOffset, rcAxis 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 poly1Vert = 0;
	int poly2Vert = 0;
	for (int inVertA = 0, inVertB = inVertsCount - 1; inVertA < inVertsCount; inVertB = inVertA, ++inVertA)
	{
		// 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 = 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 (inVertAxisDelta[inVertA] > 0)
			{
				rcVcopy(&outVerts1[poly1Vert * 3], &inVerts[inVertA * 3]);
				poly1Vert++;
			}
			else if (inVertAxisDelta[inVertA] < 0)
			{
				rcVcopy(&outVerts2[poly2Vert * 3], &inVerts[inVertA * 3]);
				poly2Vert++;
			}
		}
		else
		{
			// add the inVertA point to the right polygon. Addition is done even for points on the dividing line
			if (inVertAxisDelta[inVertA] >= 0)
			{
				rcVcopy(&outVerts1[poly1Vert * 3], &inVerts[inVertA * 3]);
				poly1Vert++;
				if (inVertAxisDelta[inVertA] != 0)
				{
					continue;
				}
			}
			rcVcopy(&outVerts2[poly2Vert * 3], &inVerts[inVertA * 3]);
			poly2Vert++;
		}
	}

	*outVerts1Count = poly1Vert;
	*outVerts2Count = poly2Vert;
}

...

• 分割多边形的主要步骤为：
  • 沿指定轴 axis 方向，计算分割面和每个顶点的的指定轴坐标差值，用于确定顶点是否在分割面以内。
  • 遍历每一个顶点，根据当前顶点 A 和上一个顶点 B所处位置进行处理。
    • 如果 A 、B 处在分割面两侧:
      • 计算 B 点到分割面的距离占 AB 到分割面距离和的比例。
      • 根据比例，通过 A 、B 的坐标插值得到 AB 和分割面的交点 C 坐标。
      • 将 C 点加入到分割面内顶点列表 outVerts1 和分割面外顶点列表 outVerts2 中。
      • 根据 A 点和分割面的位置关系，将 A 点加入到对应顶点列表中。
    • 如果 A 、B 处在分割面内侧，将 A 点加入到分割面内顶点列表 outVerts1 。
    • 如果 A 、B 处在分割面外侧，将 A 点加入到分割面外顶点列表 outVerts2 。
• 高度场添加 span 信息 addSpan 方法的实现如下：

// Recast/Source/RecastRasterization.cpp




                   const int x, const int z,
                   const unsigned short min, const unsigned short max,
                   const unsigned char areaID, const int flagMergeThreshold)
{
   // Create the new span.
   rcSpan* newSpan = allocSpan(heightfield);
   if (newSpan == NULL)
   {
   	return false;
   }
   newSpan->smin = min;
   newSpan->smax = max;
   newSpan->area = areaID;
   newSpan->next = NULL;
   
   const int columnIndex = x + z * heightfield.width;
   rcSpan* previousSpan = NULL;
   rcSpan* currentSpan = heightfield.spans[columnIndex];
   
   // Insert the new span, possibly merging it with existing spans.
   while (currentSpan != NULL)
   {
   	if (currentSpan->smin > newSpan->smax)
   	{
   		// Current span is completely after the new span, break.
   		break;
   	}
   	
   	if (currentSpan->smax < newSpan->smin)
   	{
   		// Current span is completely before the new span.  Keep going.
   		previousSpan = currentSpan;
   		currentSpan = currentSpan->next;
   	}
   	else
   	{
   		// 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)newSpan->smax - (int)currentSpan->smax) <= flagMergeThreshold)
   		{
   			// Higher area ID numbers indicate higher resolution priority.
   			newSpan->area = rcMax(newSpan->area, currentSpan->area);
   		}
   		
   		// 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(heightfield, currentSpan);
   		if (previousSpan)
   		{
   			previousSpan->next = next;
   		}
   		else
   		{
   			heightfield.spans[columnIndex] = next;
   		}
   		currentSpan = next;
   	}
   }
   
   // Insert new span after prev
   if (previousSpan != NULL)
   {
   	newSpan->next = previousSpan->next;
   	previousSpan->next = newSpan;
   }
   else
   {
   	// This span should go before the others in the list
   	newSpan->next = heightfield.spans[columnIndex];
   	heightfield.spans[columnIndex] = newSpan;
   }


}

• span 信息即多边形的 y' 格子坐标 span，在高度场中，span 信息通过链表存储，记录了每一个 cell 的所有 span 区间，区间按坐标从小到大顺序存储。插入新区间时，同样需要保持从小到大的顺序，找到插入位置。如果新区间和原有区间有相交，则会将两个区间进行合并。

过滤可行走表面

• 在三角面上行走，需要满足几个主要情况：
  • 三角面的坡度较平缓，过于陡峭的坡度无法行走。
  • 相邻三角面高度差较低，支持对象跨越。
  • 相邻三角面的天花板和地面之间的最小距离足够大，支持对象通过。
• 坡度的过滤在光栅化过程已经完成，此阶段不需要再处理。另外两个条件，通过三个过滤方式来处理。

处理低悬挂障碍物

• 通过 rcFilterLowHangingWalkableObstacles 方法，进行低悬挂障碍物的处理，其实现如下:

// Recast/Source/RecastFilter.cpp

...

void rcFilterLowHangingWalkableObstacles(rcContext* context, const int walkableClimb, rcHeightfield& heightfield)
{
	rcAssert(context);

	rcScopedTimer timer(context, RC_TIMER_FILTER_LOW_OBSTACLES);

	const int xSize = heightfield.width;
	const int zSize = heightfield.height;

	for (int z = 0; z < zSize; ++z)
	{
		for (int x = 0; x < xSize; ++x)
		{
			rcSpan* previousSpan = NULL;
			bool previousWasWalkable = false;
			unsigned char previousAreaID = RC_NULL_AREA;

			// For each span in the column...
			for (rcSpan* span = heightfield.spans[x + z * xSize]; span != NULL; previousSpan = span, span = span->next)
			{
				const bool walkable = span->area != RC_NULL_AREA;

				// If current span is not walkable, but there is walkable span just below it and the height difference
				// is small enough for the agent to walk over, mark the current span as walkable too.
				if (!walkable && previousWasWalkable && (int)span->smax - (int)previousSpan->smax <= walkableClimb)
				{
					span->area = previousAreaID;
				}

				// Copy the original walkable value regardless of whether we changed it.
				// This prevents multiple consecutive non-walkable spans from being erroneously marked as walkable.
				previousWasWalkable = walkable;
				previousAreaID = span->area;
			}
		}
	}
}

...

• 检查 xz 平面的每个 cell 的 span 列表，span 列表是从小到大排序的，当前 span 不可行走时，如果上一个 span 可行走，且当前 span 的地面 span->max 和上一个 span 的地面 previousSpan->max 的差不超过可跨域距离 walkableClimb ，则将当前 span->area 标记为可行走区域。
• 加入此检查，可以避免角色因低障碍物（如：门槛、小台阶等）而受到阻挡无法行走，以及对于一些悬挂的障碍（如：桥梁、屋檐）等，可以支持角色跨越通过。

处理边缘跨度

• 处理边缘 span 的方法 rcFilterLedgeSpans 如下：

// Recast/Source/RecastFilter.cpp

...

void rcFilterLedgeSpans(rcContext* context, const int walkableHeight, const int walkableClimb, rcHeightfield& heightfield)
{
	rcAssert(context);
	
	rcScopedTimer timer(context, RC_TIMER_FILTER_BORDER);

	const int xSize = heightfield.width;
	const int zSize = heightfield.height;
	
	// Mark spans that are adjacent to a ledge as unwalkable..
	for (int z = 0; z < zSize; ++z)
	{
		for (int x = 0; x < xSize; ++x)
		{
			for (rcSpan* span = heightfield.spans[x + z * xSize]; span; span = span->next)
			{
				// Skip non-walkable spans.
				if (span->area == RC_NULL_AREA)
				{
					continue;
				}

				const int floor = (int)(span->smax);
				const int ceiling = span->next ? (int)(span->next->smin) : MAX_HEIGHTFIELD_HEIGHT;

				// The difference between this walkable area and the lowest neighbor walkable area.
				// This is the difference between the current span and all neighbor spans that have
				// enough space for an agent to move between, but not accounting at all for surface slope.
				int lowestNeighborFloorDifference = MAX_HEIGHTFIELD_HEIGHT;

				// Min and max height of accessible neighbours.
				int lowestTraversableNeighborFloor = span->smax;
				int highestTraversableNeighborFloor = span->smax;

				for (int direction = 0; direction < 4; ++direction)
				{
					const int neighborX = x + rcGetDirOffsetX(direction);
					const int neighborZ = z + rcGetDirOffsetY(direction);

					// Skip neighbours which are out of bounds.
					if (neighborX < 0 || neighborZ < 0 || neighborX >= xSize || neighborZ >= zSize)
					{
						lowestNeighborFloorDifference = -walkableClimb - 1;
						break;
					}

					const rcSpan* neighborSpan = heightfield.spans[neighborX + neighborZ * xSize];

					// The most we can step down to the neighbor is the walkableClimb distance.
					// Start with the area under the neighbor span
					int neighborCeiling = neighborSpan ? (int)neighborSpan->smin : MAX_HEIGHTFIELD_HEIGHT;

					// Skip neighbour if the gap between the spans is too small.
					if (rcMin(ceiling, neighborCeiling) - floor >= walkableHeight)
					{
						lowestNeighborFloorDifference = (-walkableClimb - 1);
						break;
					}

					// For each span in the neighboring column...
					for (; neighborSpan != NULL; neighborSpan = neighborSpan->next)
					{
						const int neighborFloor = (int)neighborSpan->smax;
						neighborCeiling = neighborSpan->next ? (int)neighborSpan->next->smin : MAX_HEIGHTFIELD_HEIGHT;

						// Only consider neighboring areas that have enough overlap to be potentially traversable.
						if (rcMin(ceiling, neighborCeiling) - rcMax(floor, neighborFloor) < walkableHeight)
						{
							// No space to traverse between them.
							continue;
						}

						const int neighborFloorDifference = neighborFloor - floor;
						lowestNeighborFloorDifference = rcMin(lowestNeighborFloorDifference, neighborFloorDifference);

						// Find min/max accessible neighbor height.
						// Only consider neighbors that are at most walkableClimb away.
						if (rcAbs(neighborFloorDifference) <= walkableClimb)
						{
							// There is space to move to the neighbor cell and the slope isn't too much.
							lowestTraversableNeighborFloor = rcMin(lowestTraversableNeighborFloor, neighborFloor);
							highestTraversableNeighborFloor = rcMax(highestTraversableNeighborFloor, neighborFloor);
						}
						else if (neighborFloorDifference < -walkableClimb)
						{
							// We already know this will be considered a ledge span so we can early-out
							break;
						}
					}
				}

				// The current span is close to a ledge if the magnitude of the drop to any neighbour span is greater than the walkableClimb distance.
				// That is, there is a gap that is large enough to let an agent move between them, but the drop (surface slope) is too large to allow it.
				// (If this is the case, then biggestNeighborStepDown will be negative, so compare against the negative walkableClimb as a means of checking
				// the magnitude of the delta)
				if (lowestNeighborFloorDifference < -walkableClimb)
				{
					span->area = RC_NULL_AREA;
				}
				// If the difference between all neighbor floors is too large, this is a steep slope, so mark the span as an unwalkable ledge.
				else if (highestTraversableNeighborFloor - lowestTraversableNeighborFloor > walkableClimb)
				{
					span->area = RC_NULL_AREA;
				}
			}
		}
	}
}

...

• 和低障碍处理类似，需要对 xz 平面上，每一个 cell 的 span 列表 heightfield.spans 中的每一个 span 进行处理，处理流程大致如下：
  • 下一个跨度的天花板 span->next->smin 和任一邻居跨度列表中的首个跨度天花板 neightborSpan->smin，二者中的较小值，和当前跨度的地面 span->smax 的差值，不小于 walkableHeight 时，表示当前跨度和某个邻居存在较大的高度差，尽管可能只有一个方向存在危险，处于安全考虑，将当前跨度标记为不可行走，避免因局部地形问题卡住。
  • 检查当前跨度和邻居跨度列表的每个跨度，当两者交集不小于 walkableHeight 且地面高度差不大于 walkableClimb 时，认为此邻居跨度为可行走跨度，从所有可行走邻居跨度中，找出最大和最小的地面高度。
  • 如果最大最小地面高度差超过 walkableClimb ，则认为当前跨度为一个陡坡，将其 span->area 标记为不可行走。
• 处理边缘 span 采用保守策略，对于高度差较大的 span，都选择标记为不可行走，减少特殊地形带来的角色移动表现问题的出现。

处理低高度跨度

• 低高度 span 处理，主要是为了确保对象有足够空间可以在表面站立，才能够正常行走，通过 rcFilterWalkableLowHeightSpans 方法实现，代码如下：

// Recast/Source/RecastFilter.cpp

...

void rcFilterWalkableLowHeightSpans(rcContext* context, const int walkableHeight, rcHeightfield& heightfield)
{
	rcAssert(context);
	rcScopedTimer timer(context, RC_TIMER_FILTER_WALKABLE);

	const int xSize = heightfield.width;
	const int zSize = heightfield.height;

	// Remove walkable flag from spans which do not have enough
	// space above them for the agent to stand there.
	for (int z = 0; z < zSize; ++z)
	{
		for (int x = 0; x < xSize; ++x)
		{
			for (rcSpan* span = heightfield.spans[x + z*xSize]; span; span = span->next)
			{
				const int floor = (int)(span->smax);
				const int ceiling = span->next ? (int)(span->next->smin) : MAX_HEIGHTFIELD_HEIGHT;
				if (ceiling - floor < walkableHeight)
				{
					span->area = RC_NULL_AREA;
				}
			}
		}
	}
}

• 低高度 span 处理相对比较简单，就是对每一个 span 做检查，如果当前 span 的天花板（即下一个的最小值 span->next->smin）和地面（span->smax）的高度差小于 walkableHeight ，即当前 span 不支持站立，则标记 span->area 为不可行走。

划分地区

建立紧密高度场

• 经过上一步处理后，得到了一个高度场，高度场的结构如下：

// 高度场
struct rcHeightfield
{
...
	int width;			/// 高度场的宽度（沿 x 轴的单元格数量）
	int height;			/// 高度场的宽度（沿 z 轴的单元格数量）
	float bmin[3];  	/// 高度场在世界空间中的最小边界。 [(x, y, z)]
	float bmax[3];		/// 高度场在世界空间中的最大边界。 [(x, y, z)]
	float cs;			/// 每个单元格的大小（在 xz 平面上）
	float ch;			/// 每个单元格的高度（沿 y 轴的最小增量）
	rcSpan** spans;		/// 高度场的跨度列表，列表包括所有单元格，每个单元格为一个跨度链表

	rcSpanPool* pools;	/// 跨度链表对象池
	rcSpan* freelist;	/// 跨度链表对象池的可用跨度对象列表
...
};


struct rcSpan
{
	unsigned int smin : RC_SPAN_HEIGHT_BITS; /// 跨度的最小值，smin < smax
	unsigned int smax : RC_SPAN_HEIGHT_BITS; /// 跨度的最大值，smax <= RC_SPAN_MAX_HEIGHT
	unsigned int area : 6;                   /// 跨度所属区域 id
	rcSpan* next;                            /// 下一个更高的跨度
};

• 其中，spans 数组长度为 width * height ，每个元素指向一个 span 链表，数据存储比较离散，不利于后续处理过程频繁访问，因此需要转换成更加紧凑的形式，即紧密高度场，其结构如下：

// 紧密高度场
struct rcCompactHeightfield
{
	...
	int width;					/// 同 rcHeightfield::width
	int height;					/// 同 rcHeightfield::height
	int spanCount;				/// rcHeightfield 中的跨度总数
	int walkableHeight;			/// 同 rcConfig::walkableHeight
	int walkableClimb;			/// 同 rcConfig::walkableClimb
	int borderSize;				/// 同 rcConfig::borderSize
	unsigned short maxDistance;	/// 高度场中两个跨度的最大距离
	unsigned short maxRegions;	/// 高度场中的最大地区id
	float bmin[3];				/// 同 rcHeightfield
	float bmax[3];				/// 同 rcHeightfield
	float cs;					/// 同 rcHeightfield
	float ch;					/// 同 rcHeightfield
	rcCompactCell* cells;		/// 单元格数组，数量为 width * height
	rcCompactSpan* spans;		/// 跨度数组，数量为 spanCount
	unsigned short* dist;		/// 跨度和边界的距离数组，数量为 spanCount
	unsigned char* areas;		/// 区域id数组，数量为 spanCount
	
	...
};


struct rcCompactCell
{
	unsigned int index : 24;	/// 当前单元格的首个跨度在的索引 id
	unsigned int count : 8;		/// 当前单元格的跨度数量
};

struct rcCompactSpan
{
	unsigned short y;			/// 当前跨度的地面高度，即 smax
	unsigned short reg;			/// 当前跨度所属的地区 id
	unsigned int con : 24;		/// 连通的邻居数据
	unsigned int h : 8;			/// 下一跨度的天花板到当前跨度的地面高度差，即 next->smin - smax
};

• 建立紧密高度场的方法 rcBuildCompactHeightfield 如下：

// Recast/Source/Recast.cpp

...

bool rcBuildCompactHeightfield(rcContext* context, const int walkableHeight, const int walkableClimb,
                               const rcHeightfield& heightfield, rcCompactHeightfield& compactHeightfield)
{
	...

	const int MAX_HEIGHT = 0xffff;

	// Fill in cells and spans.
	int currentCellIndex = 0;
	const int numColumns = xSize * zSize;
	for (int columnIndex = 0; columnIndex < numColumns; ++columnIndex)
	{
		const rcSpan* span = heightfield.spans[columnIndex];
			
		// If there are no spans at this cell, just leave the data to index=0, count=0.
		if (span == NULL)
		{
			continue;
		}
			
		rcCompactCell& cell = compactHeightfield.cells[columnIndex];
		cell.index = currentCellIndex;
		cell.count = 0;

		for (; span != NULL; span = span->next)
		{
			if (span->area != RC_NULL_AREA)
			{
				const int bot = (int)span->smax;
				const int top = span->next ? (int)span->next->smin : MAX_HEIGHT;
				compactHeightfield.spans[currentCellIndex].y = (unsigned short)rcClamp(bot, 0, 0xffff);
				compactHeightfield.spans[currentCellIndex].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
				compactHeightfield.areas[currentCellIndex] = span->area;
				currentCellIndex++;
				cell.count++;
			}
		}
	}
	
	// Find neighbour connections.
	const int MAX_LAYERS = RC_NOT_CONNECTED - 1;
	int maxLayerIndex = 0;
	const int zStride = xSize; // for readability
	for (int z = 0; z < zSize; ++z)
	{
		for (int x = 0; x < xSize; ++x)
		{
			const rcCompactCell& cell = compactHeightfield.cells[x + z * zStride];
			for (int i = (int)cell.index, ni = (int)(cell.index + cell.count); i < ni; ++i)
			{
				rcCompactSpan& span = compactHeightfield.spans[i];

				for (int dir = 0; dir < 4; ++dir)
				{
					rcSetCon(span, dir, RC_NOT_CONNECTED);
					const int neighborX = x + rcGetDirOffsetX(dir);
					const int neighborZ = z + rcGetDirOffsetY(dir);
					// First check that the neighbour cell is in bounds.
					if (neighborX < 0 || neighborZ < 0 || neighborX >= xSize || neighborZ >= zSize)
					{
						continue;
					}

					// Iterate over all neighbour spans and check if any of the is
					// accessible from current cell.
					const rcCompactCell& neighborCell = compactHeightfield.cells[neighborX + neighborZ * zStride];
					for (int k = (int)neighborCell.index, nk = (int)(neighborCell.index + neighborCell.count); k < nk; ++k)
					{
						const rcCompactSpan& neighborSpan = compactHeightfield.spans[k];
						const int bot = rcMax(span.y, neighborSpan.y);
						const int top = rcMin(span.y + span.h, neighborSpan.y + neighborSpan.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)neighborSpan.y - (int)span.y) <= walkableClimb)
						{
							// Mark direction as walkable.
							const int layerIndex = k - (int)neighborCell.index;
							if (layerIndex < 0 || layerIndex > MAX_LAYERS)
							{
								maxLayerIndex = rcMax(maxLayerIndex, layerIndex);
								continue;
							}
							rcSetCon(span, dir, layerIndex);
							break;
						}
					}
				}
			}
		}
	}

	if (maxLayerIndex > MAX_LAYERS)
	{
		context->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Heightfield has too many layers %d (max: %d)",
		         maxLayerIndex, MAX_LAYERS);
	}

	return true;
}

...

• 建立过程，每个 cell 记录了其中首个 span 的索引及 span 的数量。所有 cell 的 span 都存入到 compactHeightfield.spans 中，其中 y 为当前 span 的地面高度 span->smax，h 为下一 span 的天花板到当前 span 地面的高度差 span->next->smin - span->smax。
• 除了设置基础信息外，还需要计算每个 span 的连通信息。每个 span 会和邻居 cell 的 spans 列表进行计算，当前 span 和邻居连通，需要满足以下条件：
  • 当前 span 和邻居中的任意 spans[index] ，两者的天花板高度 y + h 最小值和地面高度 y 最大值之差，不小于 walkableHeight，即存在一个邻居 span 可以从当前 span 通行。
  • 当前 span 和邻居中的任意 spans[index] ，两者的地面高度 y 之差，不大于 walkableClimb，即存在一个邻居 span 可以从当前 span 跨过。
• 设置连通的方法 rcSetCon 的实现如下：

// Recast/Include/Recast.h

...

inline void rcSetCon(rcCompactSpan& span, int direction, int neighborIndex)
{
	const unsigned int shift = (unsigned int)direction * 6;
	const unsigned int con = span.con;
	span.con = (con & ~(0x3f << shift)) | (((unsigned int)neighborIndex & 0x3f) << shift);
}

...

• 方向为左上右下，分别对应 0 ~ 3 ，每个方向使用一个 6 位的值，代表在邻居 cell 中的第几个 span ，每个 cell 最多能有 62 个 span 。某个方向设置了连通后，则不再检查该方向后续的 span，即取首个可连通的 span。

收缩可行走区域

• 为了防止移动过程由于太靠近障碍边缘而出现问题，需要将可行走区域沿着障碍边缘进行收缩。收缩过程由 rcErodeWalkableArea 方法实现，主要分为三个步骤：
  • 计算整个区域的边缘 span ，其和边缘的距离 distanceToBoundary[spanIndex] 设置为 0。
  • 计算每个非边缘 span 和边缘的距离。
  • 将距离小于阈值（walkableRadius * 2）的 compactHeightfield.areas[spanIndex] 设置为不可通行。
• 计算区域边缘的实现如下：

// Recast/Source/RecastArea.cpp

...
bool rcErodeWalkableArea(rcContext* context, const int erosionRadius, rcCompactHeightfield& compactHeightfield)
{
	rcAssert(context != NULL);

	const int xSize = compactHeightfield.width;
	const int zSize = compactHeightfield.height;
	const int& zStride = xSize; // For readability

	rcScopedTimer timer(context, RC_TIMER_ERODE_AREA);

	unsigned char* distanceToBoundary = (unsigned char*)rcAlloc(sizeof(unsigned char) * compactHeightfield.spanCount,
	                                                            RC_ALLOC_TEMP);
	if (!distanceToBoundary)
	{
		context->log(RC_LOG_ERROR, "erodeWalkableArea: Out of memory 'dist' (%d).", compactHeightfield.spanCount);
		return false;
	}
	memset(distanceToBoundary, 0xff, sizeof(unsigned char) * compactHeightfield.spanCount);
	
	// Mark boundary cells.
	for (int z = 0; z < zSize; ++z)
	{
		for (int x = 0; x < xSize; ++x)
		{
			const rcCompactCell& cell = compactHeightfield.cells[x + z * zStride];
			for (int spanIndex = (int)cell.index, maxSpanIndex = (int)(cell.index + cell.count); spanIndex < maxSpanIndex; ++spanIndex)
			{
				if (compactHeightfield.areas[spanIndex] == RC_NULL_AREA)
				{
					distanceToBoundary[spanIndex] = 0;
					continue;
				}
				const rcCompactSpan& span = compactHeightfield.spans[spanIndex];

				// Check that there is a non-null adjacent span in each of the 4 cardinal directions.
				int neighborCount = 0;
				for (int direction = 0; direction < 4; ++direction)
				{
					const int neighborConnection = rcGetCon(span, direction);
					if (neighborConnection == RC_NOT_CONNECTED)
					{
						break;
					}
					
					const int neighborX = x + rcGetDirOffsetX(direction);
					const int neighborZ = z + rcGetDirOffsetY(direction);
					const int neighborSpanIndex = (int)compactHeightfield.cells[neighborX + neighborZ * zStride].index + neighborConnection;
					
					if (compactHeightfield.areas[neighborSpanIndex] == RC_NULL_AREA)
					{
						break;
					}
					neighborCount++;
				}
				
				// At least one missing neighbour, so this is a boundary cell.
				if (neighborCount != 4)
				{
					distanceToBoundary[spanIndex] = 0;
				}
			}
		}
	}
	
	...
}
...

• 首先建立了 distanceToBoundary 用于记录每个 span 和边缘的距离。其中不可行走的 span（area 为 RC_NULL_AREA）即为边缘，将其 distanceToBoundary[spanIndex] 设为 0。检查四个邻居方向，如果有一个方向不可行走，则将该 span 也视为边缘，设置其距离为 0。
• 得到所有边缘数据后，就需要计算每个 span 和边缘的距离，计算过程如下：

// Recast/Source/RecastArea.cpp

...
bool rcErodeWalkableArea(rcContext* context, const int erosionRadius, rcCompactHeightfield& compactHeightfield)
{
	...
	
	unsigned char newDistance;
	
	// Pass 1
	for (int z = 0; z < zSize; ++z)
	{
		for (int x = 0; x < xSize; ++x)
		{
			const rcCompactCell& cell = compactHeightfield.cells[x + z * zStride];
			const int maxSpanIndex = (int)(cell.index + cell.count);
			for (int spanIndex = (int)cell.index; spanIndex < maxSpanIndex; ++spanIndex)
			{
				const rcCompactSpan& span = compactHeightfield.spans[spanIndex];

				if (rcGetCon(span, 0) != RC_NOT_CONNECTED)
				{
					// (-1,0)
					const int aX = x + rcGetDirOffsetX(0);
					const int aY = z + rcGetDirOffsetY(0);
					const int aIndex = (int)compactHeightfield.cells[aX + aY * xSize].index + rcGetCon(span, 0);
					const rcCompactSpan& aSpan = compactHeightfield.spans[aIndex];
					newDistance = (unsigned char)rcMin((int)distanceToBoundary[aIndex] + 2, 255);
					if (newDistance < distanceToBoundary[spanIndex])
					{
						distanceToBoundary[spanIndex] = newDistance;
					}

					// (-1,-1)
					if (rcGetCon(aSpan, 3) != RC_NOT_CONNECTED)
					{
						const int bX = aX + rcGetDirOffsetX(3);
						const int bY = aY + rcGetDirOffsetY(3);
						const int bIndex = (int)compactHeightfield.cells[bX + bY * xSize].index + rcGetCon(aSpan, 3);
						newDistance = (unsigned char)rcMin((int)distanceToBoundary[bIndex] + 3, 255);
						if (newDistance < distanceToBoundary[spanIndex])
						{
							distanceToBoundary[spanIndex] = newDistance;
						}
					}
				}
				if (rcGetCon(span, 3) != RC_NOT_CONNECTED)
				{
					// (0,-1)
					const int aX = x + rcGetDirOffsetX(3);
					const int aY = z + rcGetDirOffsetY(3);
					const int aIndex = (int)compactHeightfield.cells[aX + aY * xSize].index + rcGetCon(span, 3);
					const rcCompactSpan& aSpan = compactHeightfield.spans[aIndex];
					newDistance = (unsigned char)rcMin((int)distanceToBoundary[aIndex] + 2, 255);
					if (newDistance < distanceToBoundary[spanIndex])
					{
						distanceToBoundary[spanIndex] = newDistance;
					}

					// (1,-1)
					if (rcGetCon(aSpan, 2) != RC_NOT_CONNECTED)
					{
						const int bX = aX + rcGetDirOffsetX(2);
						const int bY = aY + rcGetDirOffsetY(2);
						const int bIndex = (int)compactHeightfield.cells[bX + bY * xSize].index + rcGetCon(aSpan, 2);
						newDistance = (unsigned char)rcMin((int)distanceToBoundary[bIndex] + 3, 255);
						if (newDistance < distanceToBoundary[spanIndex])
						{
							distanceToBoundary[spanIndex] = newDistance;
						}
					}
				}
			}
		}
	}

	// Pass 2
	for (int z = zSize - 1; z >= 0; --z)
	{
		for (int x = xSize - 1; x >= 0; --x)
		{
			const rcCompactCell& cell = compactHeightfield.cells[x + z * zStride];
			const int maxSpanIndex = (int)(cell.index + cell.count);
			for (int spanIndex = (int)cell.index; spanIndex < maxSpanIndex; ++spanIndex)
			{
				const rcCompactSpan& span = compactHeightfield.spans[spanIndex];

				if (rcGetCon(span, 2) != RC_NOT_CONNECTED)
				{
					// (1,0)
					const int aX = x + rcGetDirOffsetX(2);
					const int aY = z + rcGetDirOffsetY(2);
					const int aIndex = (int)compactHeightfield.cells[aX + aY * xSize].index + rcGetCon(span, 2);
					const rcCompactSpan& aSpan = compactHeightfield.spans[aIndex];
					newDistance = (unsigned char)rcMin((int)distanceToBoundary[aIndex] + 2, 255);
					if (newDistance < distanceToBoundary[spanIndex])
					{
						distanceToBoundary[spanIndex] = newDistance;
					}

					// (1,1)
					if (rcGetCon(aSpan, 1) != RC_NOT_CONNECTED)
					{
						const int bX = aX + rcGetDirOffsetX(1);
						const int bY = aY + rcGetDirOffsetY(1);
						const int bIndex = (int)compactHeightfield.cells[bX + bY * xSize].index + rcGetCon(aSpan, 1);
						newDistance = (unsigned char)rcMin((int)distanceToBoundary[bIndex] + 3, 255);
						if (newDistance < distanceToBoundary[spanIndex])
						{
							distanceToBoundary[spanIndex] = newDistance;
						}
					}
				}
				if (rcGetCon(span, 1) != RC_NOT_CONNECTED)
				{
					// (0,1)
					const int aX = x + rcGetDirOffsetX(1);
					const int aY = z + rcGetDirOffsetY(1);
					const int aIndex = (int)compactHeightfield.cells[aX + aY * xSize].index + rcGetCon(span, 1);
					const rcCompactSpan& aSpan = compactHeightfield.spans[aIndex];
					newDistance = (unsigned char)rcMin((int)distanceToBoundary[aIndex] + 2, 255);
					if (newDistance < distanceToBoundary[spanIndex])
					{
						distanceToBoundary[spanIndex] = newDistance;
					}

					// (-1,1)
					if (rcGetCon(aSpan, 0) != RC_NOT_CONNECTED)
					{
						const int bX = aX + rcGetDirOffsetX(0);
						const int bY = aY + rcGetDirOffsetY(0);
						const int bIndex = (int)compactHeightfield.cells[bX + bY * xSize].index + rcGetCon(aSpan, 0);
						newDistance = (unsigned char)rcMin((int)distanceToBoundary[bIndex] + 3, 255);
						if (newDistance < distanceToBoundary[spanIndex])
						{
							distanceToBoundary[spanIndex] = newDistance;
						}
					}
				}
			}
		}
	}

	...
}
...

• 计算 span 到边缘的最小距离，最简单的做法就是计算其到每个边缘的距离，再从中取出最小值，显然效率非常低。这里使用了 8SSEDT 光栅扫描算法 来优化计算，做了两次扫描，这里按坐标原点在左下角计算，具体流程为：
  • 从下到上扫描，获取左、左下、下、右下邻居 span 的距离，分别加上其到当前 span 的距离，取其中最小值作为当前 span 的距离。
  • 从上到下扫描，获取右、右上、上、左上邻居 span 的距离，分别加上其到当前 span 的距离，取其中最小值作为当前 span 的距离。
• 其中，水平竖直方向的邻居和当前 span 的距离设置为 2，对角线邻居和当前 span 的距离设置为 3，对角线邻居和水平竖直邻居的距离比为 1.5，接近 1.414，通过近似的结果来避免过程计算中出现频繁开根号的情况。扫描完成后，即可得到整个区域的距离场。
• 确定每个 span 的距离后，即可通过比较距离和阈值的大小，来确定是否可通行，实现如下：

// Recast/Source/RecastArea.cpp

...
bool rcErodeWalkableArea(rcContext* context, const int erosionRadius, rcCompactHeightfield& compactHeightfield)
{
	...

	const unsigned char minBoundaryDistance = (unsigned char)(erosionRadius * 2);
	for (int spanIndex = 0; spanIndex < compactHeightfield.spanCount; ++spanIndex)
	{
		if (distanceToBoundary[spanIndex] < minBoundaryDistance)
		{
			compactHeightfield.areas[spanIndex] = RC_NULL_AREA;
		}
	}

	rcFree(distanceToBoundary);
	
	return true;
}
...

• 为了尽可能远离边缘，使用两倍的 walkableRadius 作为阈值划分，小于这个值的，该 span 的 area 都要标记为不可通行。

标记凸多边形区域

• 地图编辑过程，可能会预先对一些区域进行标记，如：不可通行、特殊区域（水池、草地等），此时则需要通过 rcMarkConvexPolyArea 方法将这些区域更新到 area 中，其实现如下：

// Recast/Source/RecastArea.cpp

...
void rcMarkConvexPolyArea(rcContext* context, const float* verts, const int numVerts,
						  const float minY, const float maxY, unsigned char areaId,
						  rcCompactHeightfield& compactHeightfield)
{
	rcAssert(context);

	rcScopedTimer timer(context, RC_TIMER_MARK_CONVEXPOLY_AREA);

	const int xSize = compactHeightfield.width;
	const int zSize = compactHeightfield.height;
	const int zStride = xSize; // For readability

	// Compute the bounding box of the polygon
	float bmin[3];
	float bmax[3];
	rcVcopy(bmin, verts);
	rcVcopy(bmax, verts);
	for (int i = 1; i < numVerts; ++i)
	{
		rcVmin(bmin, &verts[i * 3]);
		rcVmax(bmax, &verts[i * 3]);
	}
	bmin[1] = minY;
	bmax[1] = maxY;

	// Compute the grid footprint of the polygon 
	int minx = (int)((bmin[0] - compactHeightfield.bmin[0]) / compactHeightfield.cs);
	int miny = (int)((bmin[1] - compactHeightfield.bmin[1]) / compactHeightfield.ch);
	int minz = (int)((bmin[2] - compactHeightfield.bmin[2]) / compactHeightfield.cs);
	int maxx = (int)((bmax[0] - compactHeightfield.bmin[0]) / compactHeightfield.cs);
	int maxy = (int)((bmax[1] - compactHeightfield.bmin[1]) / compactHeightfield.ch);
	int maxz = (int)((bmax[2] - compactHeightfield.bmin[2]) / compactHeightfield.cs);

	// Early-out if the polygon lies entirely outside the grid.
	if (maxx < 0) { return; }
    if (minx >= xSize) { return; }
    if (maxz < 0) { return; }
    if (minz >= zSize) { return; }

	// Clamp the polygon footprint to the grid
    if (minx < 0) { minx = 0; }
    if (maxx >= xSize) { maxx = xSize - 1; }
    if (minz < 0) { minz = 0; }
    if (maxz >= zSize) { maxz = zSize - 1; }

	// TODO: Optimize.
	for (int z = minz; z <= maxz; ++z)
	{
		for (int x = minx; x <= maxx; ++x)
		{
			const rcCompactCell& cell = compactHeightfield.cells[x + z * zStride];
			const int maxSpanIndex = (int)(cell.index + cell.count);
			for (int spanIndex = (int)cell.index; spanIndex < maxSpanIndex; ++spanIndex)
			{
				rcCompactSpan& span = compactHeightfield.spans[spanIndex];

				// Skip if span is removed.
				if (compactHeightfield.areas[spanIndex] == RC_NULL_AREA)
				{
					continue;
				}

				// Skip if y extents don't overlap.
				if ((int)span.y < miny || (int)span.y > maxy)
				{
					continue;
				}

				const float point[] = {
					compactHeightfield.bmin[0] + ((float)x + 0.5f) * compactHeightfield.cs,
					0,
					compactHeightfield.bmin[2] + ((float)z + 0.5f) * compactHeightfield.cs
				};
				
				if (pointInPoly(numVerts, verts, point))
				{
					compactHeightfield.areas[spanIndex] = areaId;
				}
			}
		}
	}
}

...

• 根据多边形的顶点，计算出多边形的包围盒信息，找到紧密高度场中对应的 cell ，遍历其中的 span ，找到可通行且和包围盒相交的 span，计算其中心点在 xz 平面上的点。如果该点在多边形的投影面内，则表示该 span 属于当前的多边形，将其 area 设置为多边形的 areaId 。

建立地区

• 建立地区有几种算法：
  • 分水岭划分（SAMPLE_PARTITION_WATERSHED）
  • 单调划分（SAMPLE_PARTITION_MONOTONE）
  • 分层划分（SAMPLE_PARTITION_LAYERS）

分水岭划分

• 分水岭划分算法，需要通过 rcBuildDistanceField 先建立紧密高度场对应的高度场，包括两个步骤：
  • calculateDistanceField 计算高度场。
  • boxBlur 进行模糊处理。
• calculateDistanceField 的实现如下：

// Recast/Source/RecastRegion.cpp

...
static void calculateDistanceField(rcCompactHeightfield& chf, unsigned short* src, unsigned short& maxDist)
{
	const int w = chf.width;
	const int h = chf.height;
	
	// Init distance and points.
	for (int i = 0; i < chf.spanCount; ++i)
		src[i] = 0xffff;
	
	// Mark boundary cells.
	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)
			{
				const rcCompactSpan& s = chf.spans[i];
				const unsigned char area = chf.areas[i];
				
				int nc = 0;
				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);
						if (area == chf.areas[ai])
							nc++;
					}
				}
				if (nc != 4)
					src[i] = 0;
			}
		}
	}
	
			
	// Pass 1
	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)
			{
				const rcCompactSpan& s = chf.spans[i];
				
				if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
				{
					// (-1,0)
					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);
					const rcCompactSpan& as = chf.spans[ai];
					if (src[ai]+2 < src[i])
						src[i] = src[ai]+2;
					
					// (-1,-1)
					if (rcGetCon(as, 3) != RC_NOT_CONNECTED)
					{
						const int aax = ax + rcGetDirOffsetX(3);
						const int aay = ay + rcGetDirOffsetY(3);
						const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3);
						if (src[aai]+3 < src[i])
							src[i] = src[aai]+3;
					}
				}
				if (rcGetCon(s, 3) != RC_NOT_CONNECTED)
				{
					// (0,-1)
					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);
					const rcCompactSpan& as = chf.spans[ai];
					if (src[ai]+2 < src[i])
						src[i] = src[ai]+2;
					
					// (1,-1)
					if (rcGetCon(as, 2) != RC_NOT_CONNECTED)
					{
						const int aax = ax + rcGetDirOffsetX(2);
						const int aay = ay + rcGetDirOffsetY(2);
						const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2);
						if (src[aai]+3 < src[i])
							src[i] = src[aai]+3;
					}
				}
			}
		}
	}
	
	// Pass 2
	for (int y = h-1; y >= 0; --y)
	{
		for (int x = w-1; x >= 0; --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 (rcGetCon(s, 2) != RC_NOT_CONNECTED)
				{
					// (1,0)
					const int ax = x + rcGetDirOffsetX(2);
					const int ay = y + rcGetDirOffsetY(2);
					const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 2);
					const rcCompactSpan& as = chf.spans[ai];
					if (src[ai]+2 < src[i])
						src[i] = src[ai]+2;
					
					// (1,1)
					if (rcGetCon(as, 1) != RC_NOT_CONNECTED)
					{
						const int aax = ax + rcGetDirOffsetX(1);
						const int aay = ay + rcGetDirOffsetY(1);
						const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 1);
						if (src[aai]+3 < src[i])
							src[i] = src[aai]+3;
					}
				}
				if (rcGetCon(s, 1) != RC_NOT_CONNECTED)
				{
					// (0,1)
					const int ax = x + rcGetDirOffsetX(1);
					const int ay = y + rcGetDirOffsetY(1);
					const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 1);
					const rcCompactSpan& as = chf.spans[ai];
					if (src[ai]+2 < src[i])
						src[i] = src[ai]+2;
					
					// (-1,1)
					if (rcGetCon(as, 0) != RC_NOT_CONNECTED)
					{
						const int aax = ax + rcGetDirOffsetX(0);
						const int aay = ay + rcGetDirOffsetY(0);
						const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 0);
						if (src[aai]+3 < src[i])
							src[i] = src[aai]+3;
					}
				}
			}
		}
	}	
	
	maxDist = 0;
	for (int i = 0; i < chf.spanCount; ++i)
		maxDist = rcMax(src[i], maxDist);
	
}

...

• 建立高度场的过程和 rcErodeWalkableArea 的计算过程基本一致，rcErodeWalkableArea 是将四个邻居中存在不可行走的 span 作为边缘，而 calculateDistanceField 则是再加上条件，如果四个邻居中存在和当前 span 的 area 不相同的，则认为是区域的边缘。得到边缘信息后，同样通过光栅扫描方式来计算距离，最终得到一个距离场。
• boxBlur 的实现如下：

// Recast/Source/RecastRegion.cpp

...
static unsigned short* boxBlur(rcCompactHeightfield& chf, int thr,
							   unsigned short* src, unsigned short* dst)
{
	const int w = chf.width;
	const int h = chf.height;
	
	thr *= 2;
	
	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)
			{
				const rcCompactSpan& s = chf.spans[i];
				const unsigned short cd = src[i];
				if (cd <= thr)
				{
					dst[i] = cd;
					continue;
				}

				int d = (int)cd;
				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);
						d += (int)src[ai];
						
						const rcCompactSpan& as = chf.spans[ai];
						const int dir2 = (dir+1) & 0x3;
						if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
						{
							const int ax2 = ax + rcGetDirOffsetX(dir2);
							const int ay2 = ay + rcGetDirOffsetY(dir2);
							const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
							d += (int)src[ai2];
						}
						else
						{
							d += cd;
						}
					}
					else
					{
						d += cd*2;
					}
				}
				dst[i] = (unsigned short)((d+5)/9);
			}
		}
	}
	return dst;
}

...

• 如果 span 的距离不超过阈值 thr（这里设置为 2），则不进行模糊计算，保持距离不变。如果超过，则需要以自身为中心，和周围八个邻居的距离进行平均，得到新的距离。其中，对于每个不可行走的邻居，使用中心的距离代替。
• 建立距离场后，就需要通过 rcBuildRegions 划分地区，其实现如下：

// Recast/Source/RecastRegion.cpp

...
bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
					const int borderSize, const int minRegionArea, const int mergeRegionArea)
{
	rcAssert(ctx);
	
	rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS);
	
	const int w = chf.width;
	const int h = chf.height;
	
	rcScopedDelete<unsigned short> buf((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*2, RC_ALLOC_TEMP));
	if (!buf)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4);
		return false;
	}
	
	ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);

	const int LOG_NB_STACKS = 3;
	const int NB_STACKS = 1 << LOG_NB_STACKS;
	rcTempVector<LevelStackEntry> lvlStacks[NB_STACKS];
	for (int i=0; i<NB_STACKS; ++i)
		lvlStacks[i].reserve(256);

	rcTempVector<LevelStackEntry> stack;
	stack.reserve(256);
	
	unsigned short* srcReg = buf;
	unsigned short* srcDist = buf+chf.spanCount;
	
	memset(srcReg, 0, sizeof(unsigned short)*chf.spanCount);
	memset(srcDist, 0, sizeof(unsigned short)*chf.spanCount);
	
	unsigned short regionId = 1;
	unsigned short level = (chf.maxDistance+1) & ~1;

	// TODO: Figure better formula, expandIters defines how much the 
	// watershed "overflows" and simplifies the regions. Tying it to
	// agent radius was usually good indication how greedy it could be.
//	const int expandIters = 4 + walkableRadius * 2;
	const int expandIters = 8;

	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, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
		paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
		paintRectRegion(0, w, 0, bh, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
		paintRectRegion(0, w, h-bh, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
	}

	chf.borderSize = borderSize;
	
	int sId = -1;
	while (level > 0)
	{
		level = level >= 2 ? level-2 : 0;
		sId = (sId+1) & (NB_STACKS-1);

//		ctx->startTimer(RC_TIMER_DIVIDE_TO_LEVELS);

		if (sId == 0)
			sortCellsByLevel(level, chf, srcReg, NB_STACKS, lvlStacks, 1);
		else 
			appendStacks(lvlStacks[sId-1], lvlStacks[sId], srcReg); // copy left overs from last level

//		ctx->stopTimer(RC_TIMER_DIVIDE_TO_LEVELS);

		{
			rcScopedTimer timerExpand(ctx, RC_TIMER_BUILD_REGIONS_EXPAND);

			// Expand current regions until no empty connected cells found.
			expandRegions(expandIters, level, chf, srcReg, srcDist, lvlStacks[sId], false);
		}
		
		{
			rcScopedTimer timerFloor(ctx, RC_TIMER_BUILD_REGIONS_FLOOD);

			// Mark new regions with IDs.
			for (int j = 0; j<lvlStacks[sId].size(); j++)
			{
				LevelStackEntry current = lvlStacks[sId][j];
				int x = current.x;
				int y = current.y;
				int i = current.index;
				if (i >= 0 && srcReg[i] == 0)
				{
					if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack))
					{
						if (regionId == 0xFFFF)
						{
							ctx->log(RC_LOG_ERROR, "rcBuildRegions: Region ID overflow");
							return false;
						}
						
						regionId++;
					}
				}
			}
		}
	}
	
	// Expand current regions until no empty connected cells found.
	expandRegions(expandIters*8, 0, chf, srcReg, srcDist, stack, true);
	
	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);
	
	{
		rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER);

		// Merge regions and filter out small regions.
		rcTempVector<int> overlaps;
		chf.maxRegions = regionId;
		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());
		}
	}
		
	// Write the result out.
	for (int i = 0; i < chf.spanCount; ++i)
		chf.spans[i].reg = srcReg[i];
	
	return true;
}

...

• rcBuildRegions 的步骤如下：
  • 首先，根据边界尺寸 borderSize，通过 paintRectRegion 方法，将边界范围的 region 进行设置。
  • 接着，设置 level 为距离最大值向上取偶数，根据 level 的大小，从大到小，每次处理两级，处理流程如下：
    • 收集本次处理的所有 span 到 lvlStacks 数组中。
      • 首次执行时，通过 sortCellsByLevel 方法，检查所有 span ，将可行走且未设置 region 的，根据距离进行分段，放入 lvlStacks[sId]，sId 越小，距离越远。第 0 段距离最小为 level - 2 向下取偶数，第 1 段为第 0 段的一半，以此类推，如：level 为 7 ，则
        • sId 为 0，span 距离不小于 (7 - 2) / 2 * 2 / 2 ^ 0 = 4。
        • sId 为 1，span 距离不小于 (7 - 2) / 2 * 2 / 2 ^ 1 = 2。
        • sId 为 2，span 距离不小于 (7 - 2) / 2 * 2 / 2 ^ 2 = 1。
      • 非首次执行，则通过 appendStacks 方法，将上一次 lvlStacks[sId-1] 没有分配到 region 的，加入到 lvlStacks[sId] 中。
    • 通过 expandRegions 方法，沿边界将当前 region 进行扩展。
    • 遍历当前 lvlStacks[sId] ，通过 floodRegion 方法，填充 span 及其扩展的 span 的 region ，成功填充则 regionId + 1。
  • 调用 expandRegions 方法，扩展所有未分配 region 的 span 。
  • 调用 mergeAndFilterRegions 方法，合并 region，过滤掉 region 数量太小的 span。
  • 最后，将 srcReg 记录的最终 region 信息，应用到紧密高度场中的每一个 span，完成划分。
• expandRegions 的实现如下：

// Recast/Source/RecastRegion.cpp

...
static void expandRegions(int maxIter, unsigned short level,
					      rcCompactHeightfield& chf,
					      unsigned short* srcReg, unsigned short* srcDist,
					      rcTempVector<LevelStackEntry>& stack,
					      bool fillStack)
{
	const int w = chf.width;
	const int h = chf.height;

	if (fillStack)
	{
		// Find cells revealed by the raised level.
		stack.clear();
		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)
				{
					if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA)
					{
						stack.push_back(LevelStackEntry(x, y, i));
					}
				}
			}
		}
	}
	else // use cells in the input stack
	{
		// mark all cells which already have a region
		for (int j=0; j<stack.size(); j++)
		{
			int i = stack[j].index;
			if (srcReg[i] != 0)
				stack[j].index = -1;
		}
	}

	rcTempVector<DirtyEntry> dirtyEntries;
	int iter = 0;
	while (stack.size() > 0)
	{
		int failed = 0;
		dirtyEntries.clear();
		
		for (int j = 0; j < stack.size(); j++)
		{
			int x = stack[j].x;
			int y = stack[j].y;
			int i = stack[j].index;
			if (i < 0)
			{
				failed++;
				continue;
			}
			
			unsigned short r = srcReg[i];
			unsigned short d2 = 0xffff;
			const unsigned char area = chf.areas[i];
			const rcCompactSpan& s = chf.spans[i];
			for (int dir = 0; dir < 4; ++dir)
			{
				if (rcGetCon(s, dir) == RC_NOT_CONNECTED) continue;
				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);
				if (chf.areas[ai] != area) continue;
				if (srcReg[ai] > 0 && (srcReg[ai] & RC_BORDER_REG) == 0)
				{
					if ((int)srcDist[ai]+2 < (int)d2)
					{
						r = srcReg[ai];
						d2 = srcDist[ai]+2;
					}
				}
			}
			if (r)
			{
				stack[j].index = -1; // mark as used
				dirtyEntries.push_back(DirtyEntry(i, r, d2));
			}
			else
			{
				failed++;
			}
		}
		
		// Copy entries that differ between src and dst to keep them in sync.
		for (int i = 0; i < dirtyEntries.size(); i++) {
			int idx = dirtyEntries[i].index;
			srcReg[idx] = dirtyEntries[i].region;
			srcDist[idx] = dirtyEntries[i].distance2;
		}
		
		if (failed == stack.size())
			break;
		
		if (level > 0)
		{
			++iter;
			if (iter >= maxIter)
				break;
		}
	}
}

...

• expandRegions 有两种处理模式：
  • 当 fillStack 为 true 时，会清空 stack，将所有不小于 level 、未分配 region 且可行走的 span 加入到 stack 中。
  • 当 fillStack 为 false 时，则使用已经收集好的 stack，将其中已分配 region 的 index 设置为 -1 作为标记。
• 根据传入的 maxIter，决定进行循环迭代的次数，每次循环的处理流程为：
  • 遍历 stack 中的 span。
    • 如果 index 为 -1 ，则不再处理。
    • 检查四个邻居中，可行走，已分配 region 且不为边界（即不在 borderSize 范围）的 span ，找到其中距离最小的，将 index 、region 、距离加入到 dirtyEntries 中，设置为 stack[j].index = -1 ，即标记已处理。
  • 遍历 dirtyEntries ，将其中的 index 对应的 region 和距离设置到 srcReg 和 srcDist 中。
  • 进入下一次循环，直到 stack 中没有未处理的 span 或者迭代次数达到上限。
• floodRegion 的实现如下：

// Recast/Source/RecastRegion.cpp

...
static bool floodRegion(int x, int y, int i,
						unsigned short level, unsigned short r,
						rcCompactHeightfield& chf,
						unsigned short* srcReg, unsigned short* srcDist,
						rcTempVector<LevelStackEntry>& stack)
{
	const int w = chf.width;
	
	const unsigned char area = chf.areas[i];
	
	// Flood fill mark region.
	stack.clear();
	stack.push_back(LevelStackEntry(x, y, i));
	srcReg[i] = r;
	srcDist[i] = 0;
	
	unsigned short lev = level >= 2 ? level-2 : 0;
	int count = 0;
	
	while (stack.size() > 0)
	{
		LevelStackEntry& back = stack.back();
		int cx = back.x;
		int cy = back.y;
		int ci = back.index;
		stack.pop_back();
		
		const rcCompactSpan& cs = chf.spans[ci];
		
		// Check if any of the neighbours already have a valid region set.
		unsigned short ar = 0;
		for (int dir = 0; dir < 4; ++dir)
		{
			// 8 connected
			if (rcGetCon(cs, dir) != RC_NOT_CONNECTED)
			{
				const int ax = cx + rcGetDirOffsetX(dir);
				const int ay = cy + rcGetDirOffsetY(dir);
				const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(cs, dir);
				if (chf.areas[ai] != area)
					continue;
				unsigned short nr = srcReg[ai];
				if (nr & RC_BORDER_REG) // Do not take borders into account.
					continue;
				if (nr != 0 && nr != r)
				{
					ar = nr;
					break;
				}
				
				const rcCompactSpan& as = chf.spans[ai];
				
				const int dir2 = (dir+1) & 0x3;
				if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
				{
					const int ax2 = ax + rcGetDirOffsetX(dir2);
					const int ay2 = ay + rcGetDirOffsetY(dir2);
					const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
					if (chf.areas[ai2] != area)
						continue;
					unsigned short nr2 = srcReg[ai2];
					if (nr2 != 0 && nr2 != r)
					{
						ar = nr2;
						break;
					}
				}				
			}
		}
		if (ar != 0)
		{
			srcReg[ci] = 0;
			continue;
		}
		
		count++;
		
		// Expand neighbours.
		for (int dir = 0; dir < 4; ++dir)
		{
			if (rcGetCon(cs, dir) != RC_NOT_CONNECTED)
			{
				const int ax = cx + rcGetDirOffsetX(dir);
				const int ay = cy + rcGetDirOffsetY(dir);
				const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(cs, dir);
				if (chf.areas[ai] != area)
					continue;
				if (chf.dist[ai] >= lev && srcReg[ai] == 0)
				{
					srcReg[ai] = r;
					srcDist[ai] = 0;
					stack.push_back(LevelStackEntry(ax, ay, ai));
				}
			}
		}
	}
	
	return count > 0;
}

...

• floodRegion 每次从 lvlStacks[sId] 取一个 index，处理其对应的 span，放入 stack 中进行循环处理，流程如下：
  • 从 stack 中取出一个 span 。
  • 检查 span 的八个邻居，如果没有分配过 region 或者 region 和传入的 regionId 相同，则将当前 span 的 region 设置为传入的 regionId，距离设置为 0 。
  • 如果当前 span 设置了 region，则将四个邻居中，可行走且大于 level - 2，同时还未分配 region 的 span，设置其 region 为 regionId，距离设置为 0。
  • 将处理的邻居 span 放入 stack 中，循环处理 stack，实现传播，直到 stack 处理完毕。
• mergeAndFilterRegions 使用了新的结构 rcRegion 来进行处理，其实现如下：

// Recast/Source/RecastRegion.cpp

...

struct rcRegion
{
	...
	
	int spanCount;					// 当前地区的所有跨度的数量
	unsigned short id;				// 当前地区的 id
	unsigned char areaType;			// 当前地区的区域类型
	bool remap;						// 是否需要重新映射地区 id
	bool visited;					// 是否访问处理过
	bool overlap;					// 是否重叠，即在同一个单元格上存在多个相同地区的跨度
	bool connectsToBorder;			// 是否连接到 borderSize 范围内的边缘
	unsigned short ymin, ymax;
	rcTempVector<int> connections;	// 地区的轮廓的地区 id 连接
	rcTempVector<int> floors;		// 和当前地区存在重叠（即处在同一个单元格）的所有其他地区 id
};

...

static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize,
								  unsigned short& maxRegionId,
								  rcCompactHeightfield& chf,
								  unsigned short* srcReg, rcTempVector<int>& overlaps)
{
	const int w = chf.width;
	const int h = chf.height;
	
	const int nreg = maxRegionId+1;
	rcTempVector<rcRegion> regions;
	if (!regions.reserve(nreg)) {
		ctx->log(RC_LOG_ERROR, "mergeAndFilterRegions: Out of memory 'regions' (%d).", nreg);
		return false;
	}

	// Construct regions
	for (int i = 0; i < nreg; ++i)
		regions.push_back(rcRegion((unsigned short) i));
	
	// Find edge of a region and find connections around the contour.
	for (int y = 0; y < h; ++y)
	{
		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)
			{
				unsigned short r = srcReg[i];
				if (r == 0 || r >= nreg)
					continue;
				
				rcRegion& reg = regions[r];
				reg.spanCount++;
				
				// Update floors.
				for (int j = (int)c.index; j < ni; ++j)
				{
					if (i == j) continue;
					unsigned short floorId = srcReg[j];
					if (floorId == 0 || floorId >= nreg)
						continue;
					if (floorId == r)
						reg.overlap = true;
					addUniqueFloorRegion(reg, floorId);
				}
				
				// Have found contour
				if (reg.connections.size() > 0)
					continue;
				
				reg.areaType = chf.areas[i];
				
				// Check if this cell is next to a border.
				int ndir = -1;
				for (int dir = 0; dir < 4; ++dir)
				{
					if (isSolidEdge(chf, srcReg, x, y, i, dir))
					{
						ndir = dir;
						break;
					}
				}
				
				if (ndir != -1)
				{
					// The cell is at border.
					// Walk around the contour to find all the neighbours.
					walkContour(x, y, i, ndir, chf, srcReg, reg.connections);
				}
			}
		}
	}

	// Remove too small regions.
	rcTempVector<int> stack(32);
	rcTempVector<int> trace(32);
	for (int i = 0; i < nreg; ++i)
	{
		rcRegion& reg = regions[i];
		if (reg.id == 0 || (reg.id & RC_BORDER_REG))
			continue;                       
		if (reg.spanCount == 0)
			continue;
		if (reg.visited)
			continue;
		
		// Count the total size of all the connected regions.
		// Also keep track of the regions connects to a tile border.
		bool connectsToBorder = false;
		int spanCount = 0;
		stack.clear();
		trace.clear();

		reg.visited = true;
		stack.push_back(i);
		
		while (stack.size())
		{
			// Pop
			int ri = stack.back(); stack.pop_back();
			
			rcRegion& creg = regions[ri];

			spanCount += creg.spanCount;
			trace.push_back(ri);

			for (int j = 0; j < creg.connections.size(); ++j)
			{
				if (creg.connections[j] & RC_BORDER_REG)
				{
					connectsToBorder = true;
					continue;
				}
				rcRegion& neireg = regions[creg.connections[j]];
				if (neireg.visited)
					continue;
				if (neireg.id == 0 || (neireg.id & RC_BORDER_REG))
					continue;
				// Visit
				stack.push_back(neireg.id);
				neireg.visited = true;
			}
		}
		
		// If the accumulated regions size is too small, remove it.
		// Do not remove areas which connect to tile borders
		// as their size cannot be estimated correctly and removing them
		// can potentially remove necessary areas.
		if (spanCount < minRegionArea && !connectsToBorder)
		{
			// Kill all visited regions.
			for (int j = 0; j < trace.size(); ++j)
			{
				regions[trace[j]].spanCount = 0;
				regions[trace[j]].id = 0;
			}
		}
	}
	
	// Merge too small regions to neighbour regions.
	int mergeCount = 0 ;
	do
	{
		mergeCount = 0;
		for (int i = 0; i < nreg; ++i)
		{
			rcRegion& reg = regions[i];
			if (reg.id == 0 || (reg.id & RC_BORDER_REG))
				continue;
			if (reg.overlap)
				continue;
			if (reg.spanCount == 0)
				continue;
			
			// Check to see if the region should be merged.
			if (reg.spanCount > mergeRegionSize && isRegionConnectedToBorder(reg))
				continue;
			
			// Small region with more than 1 connection.
			// Or region which is not connected to a border at all.
			// Find smallest neighbour region that connects to this one.
			int smallest = 0xfffffff;
			unsigned short mergeId = reg.id;
			for (int j = 0; j < reg.connections.size(); ++j)
			{
				if (reg.connections[j] & RC_BORDER_REG) continue;
				rcRegion& mreg = regions[reg.connections[j]];
				if (mreg.id == 0 || (mreg.id & RC_BORDER_REG) || mreg.overlap) continue;
				if (mreg.spanCount < smallest &&
					canMergeWithRegion(reg, mreg) &&
					canMergeWithRegion(mreg, reg))
				{
					smallest = mreg.spanCount;
					mergeId = mreg.id;
				}
			}
			// Found new id.
			if (mergeId != reg.id)
			{
				unsigned short oldId = reg.id;
				rcRegion& target = regions[mergeId];
				
				// Merge neighbours.
				if (mergeRegions(target, reg))
				{
					// Fixup regions pointing to current region.
					for (int j = 0; j < nreg; ++j)
					{
						if (regions[j].id == 0 || (regions[j].id & RC_BORDER_REG)) continue;
						// If another region was already merged into current region
						// change the nid of the previous region too.
						if (regions[j].id == oldId)
							regions[j].id = mergeId;
						// Replace the current region with the new one if the
						// current regions is neighbour.
						replaceNeighbour(regions[j], oldId, mergeId);
					}
					mergeCount++;
				}
			}
		}
	}
	while (mergeCount > 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;
	}

	// Return regions that we found to be overlapping.
	for (int i = 0; i < nreg; ++i)
		if (regions[i].overlap)
			overlaps.push_back(regions[i].id);

	return true;
}

...

• mergeAndFilterRegions 主要分为几个步骤：
  • 寻找 region 的轮廓及其连接信息。
    • 为每一个 regionId 创建一个 rcRegion，遍历所有 cell 上的所有 span 进行处理，包括：
      • 将同一 regionId 的 span 数量统计到 reg.spanCount 中。
      • 检查当前 cell 上是否有其他 span 的 regionId 和当前 regionId 相同，如果有则设置 reg.overlap 为 true，即有重叠。
      • 将当前 cell 上所有 span 的 regionId，加入到 reg.floors 中。
      • 设置当前 reg.areaType。
      • 通过 isSolidEdge 方法，检查四个邻居，如果有一个邻居的 regionId 是否为其他 region 或者不可行走，则当前 span 是当前 region 的边界。
      • 如果当前 span 是边界，则通过 walkContour 方法找到当前 region 的轮廓，并计算轮廓的 region 连接信息。
  • 移除过小的 region。
    • 遍历所有的 region，对每个 region 进行检查，主要流程：
      • 设置 spanCount 总数量为 0。
      • 将当前 regionId 加入到 stack 中，迭代处理。
        • 从 stack 中取出 creg，将当前 creg.spanCount 数量加到 spanCount。
        • 遍历 creg.connections，对其中每一个 neireg 进行检查。
          • 如果 neireg 为 borderSize 的范围，则设置 connectsToBorder 为 true，代表连接到边界。
          • 如果 neireg 已经访问过，则不再处理。
          • 将 neireg 标记为已经访问过，并将 neireg 的 regionId 加入到 stack 中。
        • 继续进行 stack 的迭代处理，直到 stack 处理完成。
    • 如果 spanCount 小于 minRegionArea，并且 connectsToBorder 为 false，则代表当前 regionId 及其所有 connections 的 regionId 组成的整体区域太小，并且没有连接到边界，则将其移除，即当前 regionId 以及 connections 的 spanCount 和 regionId 都设置为 0。但如果连接到边界，因为无法准确估计其大小，可能导致移除必要的区域，所以会保留。
    • 如果移除了 region ，后续的 region 在计算时会直接跳过。计算总数量时，已经移除的 region 原本的数量也不会计入。
  • 合并小的 region 到邻居 region 中。
    • 遍历所有的 region，对每个 region 进行检查，主要流程：
      • 如果 region 被移除（reg.spanCount 为 0）或者 region 有重叠（reg.overlap 为 true），则不处理。
      • 从 connections 中，通过依次将两个 region 设置为源 region，调用两次 canMergeWithRegion 方法，找到两者相互都能合并的 region。
      • 从所有能合并的 region 中取 spanCount 最小的作为目标 region，通过 mergeRegions 方法进行合并。
      • 合并成功后，将当前 region、connections、floors 中的 regionId 都更换目标的 regionId。
    • 所有 region 处理完成后，如果有成功合并过，则再重复执行一次处理，直到不再有可以合并的 region。
  • 重新映射 regionId。
    • 遍历所有的 region，从 1 开始设置剩余的 region，将 regionId 映射为新的区间。
  • 应用新的 regionId。
    • 遍历 srcReg，使用新的 regionId 进行替换。
  • 记录所有重叠的 regionId。
    • 使用新的 regionId，记录所有有重叠的 region。
• walkContour 方法的实现如下：

// Recast/Source/RecastRegion.cpp

...
static void walkContour(int x, int y, int i, int dir,
						rcCompactHeightfield& chf,
						const unsigned short* srcReg,
						rcTempVector<int>& cont)
{
	int startDir = dir;
	int starti = i;

	const rcCompactSpan& ss = chf.spans[i];
	unsigned short curReg = 0;
	if (rcGetCon(ss, dir) != RC_NOT_CONNECTED)
	{
		const int ax = x + rcGetDirOffsetX(dir);
		const int ay = y + rcGetDirOffsetY(dir);
		const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(ss, dir);
		curReg = srcReg[ai];
	}
	cont.push_back(curReg);
			
	int iter = 0;
	while (++iter < 40000)
	{
		const rcCompactSpan& s = chf.spans[i];
		
		if (isSolidEdge(chf, srcReg, x, y, i, dir))
		{
			// Choose the edge corner
			unsigned short r = 0;
			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*chf.width].index + rcGetCon(s, dir);
				r = srcReg[ai];
			}
			if (r != curReg)
			{
				curReg = r;
				cont.push_back(curReg);
			}
			
			dir = (dir+1) & 0x3;  // Rotate CW
		}
		else
		{
			int ni = -1;
			const int nx = x + rcGetDirOffsetX(dir);
			const int ny = y + rcGetDirOffsetY(dir);
			if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
			{
				const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
				ni = (int)nc.index + rcGetCon(s, dir);
			}
			if (ni == -1)
			{
				// Should not happen.
				return;
			}
			x = nx;
			y = ny;
			i = ni;
			dir = (dir+3) & 0x3;	// Rotate CCW
		}
		
		if (starti == i && startDir == dir)
		{
			break;
		}
	}

	// Remove adjacent duplicates.
	if (cont.size() > 1)
	{
		for (int j = 0; j < cont.size(); )
		{
			int nj = (j+1) % cont.size();
			if (cont[j] == cont[nj])
			{
				for (int k = j; k < cont.size()-1; ++k)
					cont[k] = cont[k+1];
				cont.pop_back();
			}
			else
				++j;
		}
	}
}

...

• walkContour 从边界 span 出发寻找轮廓和连接 region ，其主要步骤为：
  • 计算边界 span 目标方向邻居的 regionId，加入 cont 中。
  • 按照左上右下的方向顺序，从当前 span 和方向开始，检查对应的邻居是否为当前 region 的边界。
    • 如果是边界，则方向变更为下一个方向，再进行检查。此时如果邻居的 regionId 和上一次记录的不同，则将邻居 regionId 加入 cont 中。
    • 如果不是边界，则将当前 span 改为邻居 span，方向改为上一个方向，再进行检查。
    • 如果当前 span 和方向，和起始的相同，则说明回到了起点，轮廓寻找完成，此时所有经过的 span 组成了整个边界。
  • 遍历 cont，移除相邻重复的 regionId，包括首尾，最终得到一个 region 的连接 regionId 列表，即为 reg.connections。
• canMergeWithRegion 的实现如下：

// Recast/Source/RecastRegion.cpp

...
static bool canMergeWithRegion(const rcRegion& rega, const rcRegion& regb)
{
	if (rega.areaType != regb.areaType)
		return false;
	int n = 0;
	for (int i = 0; i < rega.connections.size(); ++i)
	{
		if (rega.connections[i] == regb.id)
			n++;
	}
	if (n > 1)
		return false;
	for (int i = 0; i < rega.floors.size(); ++i)
	{
		if (rega.floors[i] == regb.id)
			return false;
	}
	return true;
}

...

• canMergeWithRegion 主要过滤不能合并的情况，包括：
  • 源 region 和目标 region 的 area 不同。
  • 源 region 的 connections 出现超过一次目标 region 的 regionId，即目标 region 和源 region 交界处可能还有其他 region。
  • 源 region 的 floors 中存在目标 region 的 regionId，即目标 region 和源 region 具有出现在同一 cell 的情况。
• mergeRegions 的实现如下：

// Recast/Source/RecastRegion.cpp

...
static bool mergeRegions(rcRegion& rega, rcRegion& regb)
{
	unsigned short aid = rega.id;
	unsigned short bid = regb.id;
	
	// Duplicate current neighbourhood.
	rcTempVector<int> acon;
	acon.resize(rega.connections.size());
	for (int i = 0; i < rega.connections.size(); ++i)
		acon[i] = rega.connections[i];
	rcTempVector<int>& bcon = regb.connections;
	
	// Find insertion point on A.
	int insa = -1;
	for (int i = 0; i < acon.size(); ++i)
	{
		if (acon[i] == bid)
		{
			insa = i;
			break;
		}
	}
	if (insa == -1)
		return false;
	
	// Find insertion point on B.
	int insb = -1;
	for (int i = 0; i < bcon.size(); ++i)
	{
		if (bcon[i] == aid)
		{
			insb = i;
			break;
		}
	}
	if (insb == -1)
		return false;
	
	// Merge neighbours.
	rega.connections.clear();
	for (int i = 0, ni = static_cast<int>(acon.size()); i < ni-1; ++i)
	{
		rega.connections.push_back(acon[(insa+1+i) % ni]);
	}
		
	for (int i = 0, ni = static_cast<int>(bcon.size()); i < ni-1; ++i)
	{
		rega.connections.push_back(bcon[(insb+1+i) % ni]);
	}
	
	removeAdjacentNeighbours(rega);
	
	for (int j = 0; j < regb.floors.size(); ++j)
		addUniqueFloorRegion(rega, regb.floors[j]);
	rega.spanCount += regb.spanCount;
	regb.spanCount = 0;
	regb.connections.resize(0);

	return true;
}

...

• mergeRegions 合并的主要过程为：
  • 找出目标 regionId 在源 region 的 connections 中的索引 insa 。
  • 找出源 regionId 在目标 region 的 connections 中的索引 insb 。
  • 清空源 region 的 connections，从 insa + 1 的位置将源 connections 重新加入，insa 位置不加入，因为和目标 region 将要合并，所以原来边界中的目标 regionId，需要插入目标 region 的边界连接。
  • 从 insb + 1 的位置将目标 connections 加入源 connections，同理 insb 位置不加入。
  • 调用 removeAdjacentNeighbours 方法，移除源 connections 中相邻重复的 regionId 。
  • 调用 addUniqueFloorRegion 方法，将目标 floors 加入到源 floors 中。
  • 将目标 spanCount 加到源 spanCount 上，并清空目标 region 的 spanCount 和 connections，完成合并过程。
• 以 2D 为例，分水岭划分的全过程如下图：

单调划分

• 单调划分通过 rcBuildRegionsMonotone 方法进行，其实现如下：

// Recast/Source/RecastRegion.cpp

...

static const unsigned short RC_NULL_NEI = 0xffff;

struct rcSweepSpan
{
	unsigned short rid;	// 行索引 id
	unsigned short id;	// 地区 id
	unsigned short ns;	// 该地区 id 采样的跨度个数
	unsigned short nei;	// 邻居的地区 id，通常指下方的 id
};

...
bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
							const int borderSize, const int minRegionArea, const int mergeRegionArea)
{
	rcAssert(ctx);
	
	rcScopedTimer timer(ctx, 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;
	
	rcTempVector<int> 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;
			}
		}
	}


	{
		rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER);

		// Merge regions and filter out small regions.
		rcTempVector<int> overlaps;
		chf.maxRegions = id;
		if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
			return false;

		// Monotone partitioning does not generate overlapping regions.
	}
	
	// Store the result out.
	for (int i = 0; i < chf.spanCount; ++i)
		chf.spans[i].reg = srcReg[i];

	return true;
}

...

• rcBuildRegionsMonotone 使用了 rcSweepSpan 结构来记录处理过程的关系，主要流程为：
  • 通过 paintRectRegion 方法，将 borderSize 范围内的 span 的 region 进行标识（id|RC_BORDER_REG）。
  • 遍历非 borderSize 范围的 cell，对其中的每个可行走的 span 进行处理。
    • 遍历每一行时，将记录当前行 span 被连接的次数 prev 重置为 0，将 rid 重置为 1，
    • 如果当前 span 及其左邻居都可行走，且不在 borderSize 范围，则设置 previd 为左邻居的 regionId。
    • 如果 previd 为 0，则将其设置为当前未分配给 region 的 rid，并将 rid + 1，同时把 previd 记录到 sweeps[pervid] 中。
    • 如果当前 span 及其下邻居都可行走，且不在 borderSize 范围，且下邻居已分配 regionId，则需要设置 sweeps[previd].nei。
      • 如果 sweeps[previd].nei 未设置，或者和下邻居的 regionId 相同，则将 sweeps[previd].nei 设置为下邻居的 regionId。
        • sweeps[previd].ns 自增，即记录 previd 连接到 nr 的次数。
        • prev[nr] 自增，即记录 nr 被连接的次数。
      • 如果 sweeps[previd].nei 已设置，并且和下邻居的 regionId 不同，则将 sweeps[previd].nei 设置为 RC_NULL_NEI，表示有多个邻居。
    • 将 previd 设置为 srcReg[i] ，即作为当前 span 的 regionId。
    • 设置完每一行 span 的 regionId 后，遍历所有 regionId。
      • 如果 sweeps[regionId].nei 不为 0 且不为 RC_NULL_NEI，并且 nei 的连接和被连接数量相同，则将 sweeps[regionId].id 设置为下一行的 regionId，认为是相同的 region。
      • 如果 sweeps[regionId].nei 为 0 或 RC_NULL_NEI，或 nei 的连接和被连接数量不相同，则将 sweeps[regionId].id 设置为 id ，即当前未使用的 regionId，认为是不同的 region，并将 id 自增。
    • 将每一行 sweeps 记录的 regionId，更新到 srcReg 中。
  • 通过 mergeAndFilterRegions，进行 region 的合并和过滤。
  • 将 srcReg 记录的最终 region 信息，应用到紧密高度场中的每一个 span，完成划分。
• 以 2D 为例，单调划分的全过程如下图：

分层划分

• 分层划分通过 rcBuildRegionsLayer 方法进行，其实现和单调划分基本一致，唯一不同的，就是单调划分使用 mergeAndFilterRegions 方法进行合并和过滤，而分层划分使用 mergeAndFilterLayerRegions 方法，其实现如下：

// Recast/Source/RecastRegion.cpp

...

static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea,
									   unsigned short& maxRegionId,
									   rcCompactHeightfield& chf,
									   unsigned short* srcReg)
{
	const int w = chf.width;
	const int h = chf.height;
	
	const int nreg = maxRegionId+1;
	rcTempVector<rcRegion> regions;
	
	// Construct regions
	if (!regions.reserve(nreg)) {
		ctx->log(RC_LOG_ERROR, "mergeAndFilterLayerRegions: Out of memory 'regions' (%d).", nreg);
		return false;
	}
	for (int i = 0; i < nreg; ++i)
		regions.push_back(rcRegion((unsigned short) i));
	
	// Find region neighbours and overlapping regions.
	rcTempVector<int> 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.clear();
			
			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
			{
				const rcCompactSpan& s = chf.spans[i];
				const unsigned char area = chf.areas[i];
				const unsigned short ri = srcReg[i];
				if (ri == 0 || ri >= nreg) continue;
				rcRegion& reg = regions[ri];
				
				reg.spanCount++;
				reg.areaType = area;

				reg.ymin = rcMin(reg.ymin, s.y);
				reg.ymax = rcMax(reg.ymax, s.y);
				
				// Collect all region layers.
				lregs.push_back(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.
	rcTempVector<int> 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.clear();
		stack.push_back(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 different area type, do not connect regions with different area type.
				if (reg.areaType != regn.areaType)
					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_back(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;
	}
	
	return true;
}

...

• mergeAndFilterLayerRegions 的主要流程为：
  • 设置 region 的基本信息。
    • 为每一个 regionId 创建一个 rcRegion，遍历所有 cell 上的所有 span 进行处理，包括：
      • 将同一 regionId 的 span 数量统计到 reg.spanCount 中。
      • 设置当前 reg.areaType。
      • 设置当前 reg.ymin 和 reg.ymax 为 cell 上所有 span 中的最小最大 span.y。
      • 检查四个方向的邻居，通过 addUniqueConnection 方法将邻居的 regionId 加入到 reg.connections 中。如果邻居为 borderSize 范围的边界，则设置 reg.connectsToBorder 为 true。
      • 检查当前 cell 上所有连续且 regionId 不同的 span，通过 addUniqueFloorRegion 方法，分别将 regionId 加入到彼此的 floors 列表中。
  • 合并没有重叠的 region。
    • 初始化 layerId 为 1 。
    • 将所有 region 的 id 初始化为 0 。
    • 遍历每一个 region 进行处理。
      • 如果当前 regionId 不为 0 ，则表示该 regionId 已经处理过，则不再处理。
      • 设置当前 region 的 regionId 为 layerId。
      • 清空 stack，将当前 region 加入到 stack 中，进行迭代处理。
        • 从 stack 中取出一个 reg，从 connections 中找到所有未处理过的可行走的邻居 regionId，如果当前 region 的 floors 中不包含邻居 regionId，则代表该 regionId 没有和当前 region 重叠，则将邻居 region 合并到当前 region。
          • 将邻居 regionId 加入到 stack 中。
          • 将邻居 region 的 id 设置为 layerId，即标记为已处理。
          • 将邻居的 floors 添加到当前 region 中。
          • 将邻居和当前 region 中最小的 ymin 和最大的 ymax 设置到当前 region 中。
          • 将邻居的 spanCount 加入到当前 region，清空邻居的 spanCount。
          • 如果邻居或当前 region 连接到 borderSize 范围的边界，则设置当前 region 的 connectsToBorder 为 true。
        • 如果出现重叠，则继续 stack 的迭代处理。
      • 处理完一个 regionId ，则 layerId 自增，继续下一个 regionId 。
  • 移除过小的 region。
    • 从 1 开始遍历所有的 region，如果 spanCount 大于 0 且小于 minRegionArea，且没有连接到 borderSize 范围的边界，则此 regionId 需要被移除。由于上一步中合并后，同一个 regionId 会处于多个 region 中，但其中只有一个 spanCount 大于 0 ，所以需要将所有 id 为此 regionId 的 region，设置其 id 为 0。
  • 重新映射 regionId。
    • 遍历所有的 region，从 1 开始设置剩余的 region，将 regionId 映射为新的区间。
  • 应用新的 regionId。
    • 遍历 srcReg，使用新的 regionId 进行替换。
• 以 2D 为例，分层划分的全过程如下图：

算法对比

	分水岭划分	单调划分	分层划分
主要内容	计算距离场，洪水填充，按块合并	扫描填充，按块合并	扫描填充，分层合并
性能开销	高 （需要计算整个距离场，洪水填充过程也需要多次迭代处理）	低 （扫描填充计算量少，按块合并跳过在同一个 cell 上出现多次的 region ，即仅处理单层 region）	中 （分层合并需要检查每个 region 的 connections 是否出现在当前 cell ，即需要层级关系，合并后还需要递归检查）
适用场景	开放空间和复杂地形	简单的平面	多层或垂直空间

查找并简化地区轮廓

• 处理地区轮廓过程，引入了几个新的结构：
  • rcContourSet ：整个高度场的轮廓信息。
  • rcContour：单个轮廓的信息。
  • rcContourRegion ：单个 region 下的轮廓信息。
  • rcContourHole ： 单个孔洞的轮廓信息。
  • rcPotentialDiagonal ： 对角线信息。

// Recast/Include/Recast.h

...

struct  rcContour
{
	int* verts;			/// 简化后的轮廓顶点
	int nverts;			/// 简化后的轮廓顶点数量 
	int* rverts;		/// 原始轮廓顶点
	int nrverts;		/// 原始轮廓顶点数量
	unsigned short reg;	/// 轮廓的地区id
	unsigned char area;	/// 轮廓的区域id
};


struct rcContourSet
{
	...

	rcContour* conts;	/// 轮廓列表
	int nconts;			/// 轮廓数量
	float bmin[3];  	/// 同 rcHeightfield
	float bmax[3];		/// 同 rcHeightfield
	float cs;			/// 同 rcHeightfield
	float ch;			/// 同 rcHeightfield
	int width;			/// 同 rcHeightfield
	int height;			/// 同 rcHeightfield
	int borderSize;		/// 同 rcConfig::borderSize
	float maxError;		/// 轮廓简化后的最大边缘误差
	
	...
};

...

// Recast/Source/RecastContour.cpp
...

struct rcContourHole
{
	rcContour* contour;			/// 孔洞的轮廓
	int minx, minz, leftmost;	/// 孔洞的轮廓点中最小 x、z 坐标和对应的索引
};

struct rcContourRegion
{
	rcContour* outline;			/// 当前地区的外轮廓（一个地区只能有一个外轮廓）
 	rcContourHole* holes;		/// 当前地区的孔洞列表
	int nholes;					/// 当前地区的孔洞数量
};

struct rcPotentialDiagonal
{
	int vert;					/// 外轮廓的顶点索引
	int dist;					/// 外轮廓顶点到目标点的距离平方
};

...

• 处理过程主要通过 rcBuildContours 方法实现，其代码如下：

// Recast/Source/RecastContour.cpp

...

bool rcBuildContours(rcContext* ctx, const rcCompactHeightfield& chf,
					 const float maxError, const int maxEdgeLen,
					 rcContourSet& cset, const int buildFlags)
{
	rcAssert(ctx);
	
	const int w = chf.width;
	const int h = chf.height;
	const int borderSize = chf.borderSize;
	
	rcScopedTimer timer(ctx, RC_TIMER_BUILD_CONTOURS);
	
	rcVcopy(cset.bmin, chf.bmin);
	rcVcopy(cset.bmax, chf.bmax);
	if (borderSize > 0)
	{
		// If the heightfield was build with bordersize, remove the offset.
		const float pad = borderSize*chf.cs;
		cset.bmin[0] += pad;
		cset.bmin[2] += pad;
		cset.bmax[0] -= pad;
		cset.bmax[2] -= pad;
	}
	cset.cs = chf.cs;
	cset.ch = chf.ch;
	cset.width = chf.width - chf.borderSize*2;
	cset.height = chf.height - chf.borderSize*2;
	cset.borderSize = chf.borderSize;
	cset.maxError = maxError;
	
	int maxContours = rcMax((int)chf.maxRegions, 8);
	cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
	if (!cset.conts)
		return false;
	cset.nconts = 0;
	
	rcScopedDelete<unsigned char> flags((unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP));
	if (!flags)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount);
		return false;
	}
	
	ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
	
	// Mark boundaries.
	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)
			{
				unsigned char res = 0;
				const rcCompactSpan& s = chf.spans[i];
				if (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG))
				{
					flags[i] = 0;
					continue;
				}
				for (int dir = 0; dir < 4; ++dir)
				{
					unsigned short r = 0;
					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);
						r = chf.spans[ai].reg;
					}
					if (r == chf.spans[i].reg)
						res |= (1 << dir);
				}
				flags[i] = res ^ 0xf; // Inverse, mark non connected edges.
			}
		}
	}
	
	ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
	
	rcTempVector<int> verts(256);
	rcTempVector<int> simplified(64);
	
	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)
			{
				if (flags[i] == 0 || flags[i] == 0xf)
				{
					flags[i] = 0;
					continue;
				}
				const unsigned short reg = chf.spans[i].reg;
				if (!reg || (reg & RC_BORDER_REG))
					continue;
				const unsigned char area = chf.areas[i];
				
				verts.clear();
				simplified.clear();
				
				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)
				{
					if (cset.nconts >= maxContours)
					{
						// Allocate more contours.
						// This happens when a region has holes.
						const int oldMax = maxContours;
						maxContours *= 2;
						rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
						for (int j = 0; j < cset.nconts; ++j)
						{
							newConts[j] = cset.conts[j];
							// Reset source pointers to prevent data deletion.
							cset.conts[j].verts = 0;
							cset.conts[j].rverts = 0;
						}
						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 = static_cast<int>(simplified.size()) / 4;
					cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM);
					if (!cont->verts)
					{
						ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts);
						return false;
					}
					memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4);
					if (borderSize > 0)
					{
						// If the heightfield was build with bordersize, remove the offset.
						for (int j = 0; j < cont->nverts; ++j)
						{
							int* v = &cont->verts[j*4];
							v[0] -= borderSize;
							v[2] -= borderSize;
						}
					}
					
					cont->nrverts = static_cast<int>(verts.size()) / 4;
					cont->rverts = static_cast<int*>(rcAlloc(sizeof(int) * cont->nrverts * 4, RC_ALLOC_PERM));
					if (!cont->rverts)
					{
						ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts);
						return false;
					}
					memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4);
					if (borderSize > 0)
					{
						// If the heightfield was build with bordersize, remove the offset.
						for (int j = 0; j < cont->nrverts; ++j)
						{
							int* v = &cont->rverts[j*4];
							v[0] -= borderSize;
							v[2] -= borderSize;
						}
					}
					
					cont->reg = reg;
					cont->area = area;
				}
			}
		}
	}
	
	// Merge holes if needed.
	if (cset.nconts > 0)
	{
		// Calculate winding of all polygons.
		rcScopedDelete<signed char> winding((signed char*)rcAlloc(sizeof(signed char)*cset.nconts, RC_ALLOC_TEMP));
		if (!winding)
		{
			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)
			{
				rcContour& cont = cset.conts[i];
				// Positively would contours are outlines, negative holes.
				if (winding[i] > 0)
				{
					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++;
				}
			}
			int index = 0;
			for (int i = 0; i < nregions; i++)
			{
				if (regions[i].nholes > 0)
				{
					regions[i].holes = &holes[index];
					index += regions[i].nholes;
					regions[i].nholes = 0;
				}
			}
			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++)
			{
				rcContourRegion& reg = regions[i];
				if (!reg.nholes) continue;
				
				if (reg.outline)
				{
					mergeRegionHoles(ctx, reg);
				}
				else
				{
					// 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);
				}
			}
		}
		
	}
	
	return true;
}

• 处理轮廓的主要步骤如下：
  • 初始化 rcContourSet 结构 cset，创建 rcContour 数组 cset.conts ，用于存储轮廓数据。
  • 遍历每个 cell 上的 span 进行处理。
    • 如果 span 不可通行或者为 borderSize 范围的边界，则标记当前 span 的无边界。
    • 检查 span 的四个邻居，将不可通行或 region 与自身不同的方向标记为边界。
  • 再次遍历每个 cell 上的 span进行处理。
    • 如果 span 无边界或四个方向都为边界，则标记为无边界，不处理。
    • 如果 span 不可通行或者为 borderSize 范围的边界，则不处理。
    • 通过 walkContour 方法找到 span 的轮廓顶点。
    • 通过 simplifyContour 方法简化轮廓顶点。
    • 通过 removeDegenerateSegments 方法，将相邻轮廓顶点中 x、z 坐标相同的顶点移除。
    • 将简化前后的轮廓顶点减去 borderSize 后记录到 cset 中，设置所属的 region 和 area。
  • 合并孔洞。
    • 遍历 cset.conts 中的每个轮廓，通过 calcAreaOfPolygon2D 方法计算轮廓组成的多边形面积，如果小于 0，表示该轮廓为孔洞。
    • 如果没有孔洞，则直接跳过。如果存在孔洞，则需要进行处理。
      • 遍历所有轮廓，将轮廓按所属的 region 分组，将轮廓分为 outline 和 holes。每个 region 有且只能有一个 outline，可以有多个 hole。
      • 遍历所有 region 对应的分组，对有 outline 和 holes 的轮廓，调用 mergeRegionHoles 方法进行合并处理。
• 处理完成后，通常情况下，cset.conts 中只剩下多个不同 region 的 outline ，而 holes 则都会被合并到 outline 中。

寻找轮廓顶点

• 寻找轮廓顶点通过 walkContour(RecastContour.cpp) 方法实现，而前面分水岭算法中使用的是 walkContour(RecastRegion.cpp)，两者思路类似，具体实现如下：

// Recast/Source/RecastContour.cpp

...

static void walkContour(int x, int y, int i,
						const rcCompactHeightfield& chf,
						unsigned char* flags, rcTempVector<int>& points)
{
	// Choose the first non-connected edge
	unsigned char dir = 0;
	while ((flags[i] & (1 << dir)) == 0)
		dir++;
	
	unsigned char startDir = dir;
	int starti = i;
	
	const unsigned char area = chf.areas[i];
	
	int iter = 0;
	while (++iter < 40000)
	{
		if (flags[i] & (1 << dir))
		{
			// Choose the edge corner
			bool isBorderVertex = false;
			bool isAreaBorder = false;
			int px = x;
			int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex);
			int pz = y;
			switch(dir)
			{
				case 0: pz++; break;
				case 1: px++; pz++; break;
				case 2: px++; break;
			}
			int r = 0;
			const rcCompactSpan& s = chf.spans[i];
			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*chf.width].index + rcGetCon(s, dir);
				r = (int)chf.spans[ai].reg;
				if (area != chf.areas[ai])
					isAreaBorder = true;
			}
			if (isBorderVertex)
				r |= RC_BORDER_VERTEX;
			if (isAreaBorder)
				r |= RC_AREA_BORDER;
			points.push_back(px);
			points.push_back(py);
			points.push_back(pz);
			points.push_back(r);
			
			flags[i] &= ~(1 << dir); // Remove visited edges
			dir = (dir+1) & 0x3;  // Rotate CW
		}
		else
		{
			int ni = -1;
			const int nx = x + rcGetDirOffsetX(dir);
			const int ny = y + rcGetDirOffsetY(dir);
			const rcCompactSpan& s = chf.spans[i];
			if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
			{
				const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
				ni = (int)nc.index + rcGetCon(s, dir);
			}
			if (ni == -1)
			{
				// Should not happen.
				return;
			}
			x = nx;
			y = ny;
			i = ni;
			dir = (dir+3) & 0x3;	// Rotate CCW
		}
		
		if (starti == i && startDir == dir)
		{
			break;
		}
	}
}

...

• 寻找轮廓顶点过程，使用了 points 数组来记录原始轮廓点，每个原始轮廓点使用 4 个整数来表示，依次为 x 、y 、z 和 region 信息。其中 region 信息经过二次处理，加上了 area 边界标记（和邻居的 area 不同时）和 borderSize 边界标记（和 borderSize 相邻或处于其中）。
• walkContour 的主要步骤如下：
  • 找到第一个边界方向，作为起始方向，当前 span 作为起始 span。
  • 迭代检查当前 span 的当前方向是否为边界方向。
    • 如果当前方向为边界，则
      • 通过 getCornerHeight 方法获取当前点的 y 坐标即是否为 borderSize 边界点，如果方向为 0 或 1，则 z 坐标加 1，如果方向为 1 或 2 ，则 x 坐标加 1。
        • x 、z 坐标通过边界所在的方向进行偏移，从而保证最终得到的每个轮廓都为右上包含边界，左下不包含边界，避免出现重复。
      • 获取当前方向的邻居 span 的 region 信息，将边界信息记录到其中。
      • 将当前点的坐标 x 、y 、z 和 region 记录到 points 中，作为一个轮廓顶点。
      • 清除当前 span 的当前方向标记，后续不再处理该方向。
      • 将方向设置为下一个方向。
    • 如果当前方向不为边界或已经处理过，则
      • 将当前方向的邻居 span 作为当前 span，并设置方向为上一个方向，迭代进行检查处理。
  • 直到当前 span 和起始 span 相同，且方向相同，则结束迭代，完成轮廓的查找。
• getCornerHeight 方法的实现如下：

// Recast/Source/RecastContour.cpp

...

static int getCornerHeight(int x, int y, int i, int dir,
						   const rcCompactHeightfield& chf,
						   bool& isBorderVertex)
{
	const rcCompactSpan& s = chf.spans[i];
	int ch = (int)s.y;
	int dirp = (dir+1) & 0x3;
	
	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.
	regs[0] = chf.spans[i].reg | (chf.areas[i] << 16);
	
	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*chf.width].index + rcGetCon(s, dir);
		const rcCompactSpan& as = chf.spans[ai];
		ch = rcMax(ch, (int)as.y);
		regs[1] = chf.spans[ai].reg | (chf.areas[ai] << 16);
		if (rcGetCon(as, dirp) != RC_NOT_CONNECTED)
		{
			const int ax2 = ax + rcGetDirOffsetX(dirp);
			const int ay2 = ay + rcGetDirOffsetY(dirp);
			const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dirp);
			const rcCompactSpan& as2 = chf.spans[ai2];
			ch = rcMax(ch, (int)as2.y);
			regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16);
		}
	}
	if (rcGetCon(s, dirp) != RC_NOT_CONNECTED)
	{
		const int ax = x + rcGetDirOffsetX(dirp);
		const int ay = y + rcGetDirOffsetY(dirp);
		const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dirp);
		const rcCompactSpan& as = chf.spans[ai];
		ch = rcMax(ch, (int)as.y);
		regs[3] = chf.spans[ai].reg | (chf.areas[ai] << 16);
		if (rcGetCon(as, dir) != RC_NOT_CONNECTED)
		{
			const int ax2 = ax + rcGetDirOffsetX(dir);
			const int ay2 = ay + rcGetDirOffsetY(dir);
			const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dir);
			const rcCompactSpan& as2 = chf.spans[ai2];
			ch = rcMax(ch, (int)as2.y);
			regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16);
		}
	}

	// Check if the vertex is special edge vertex, these vertices will be removed later.
	for (int j = 0; j < 4; ++j)
	{
		const int a = j;
		const int b = (j+1) & 0x3;
		const int c = (j+2) & 0x3;
		const int d = (j+3) & 0x3;
		
		// The vertex is a border vertex there are two same exterior cells in a row,
		// followed by two interior cells and none of the regions are out of bounds.
		const bool twoSameExts = (regs[a] & regs[b] & RC_BORDER_REG) != 0 && regs[a] == regs[b];
		const bool twoInts = ((regs[c] | regs[d]) & RC_BORDER_REG) == 0;
		const bool intsSameArea = (regs[c]>>16) == (regs[d]>>16);
		const bool noZeros = regs[a] != 0 && regs[b] != 0 && regs[c] != 0 && regs[d] != 0;
		if (twoSameExts && twoInts && intsSameArea && noZeros)
		{
			isBorderVertex = true;
			break;
		}
	}
	
	return ch;
}

...

• getCornerHeight 的主要步骤为：
  • 初始化 y 坐标为当前 span 的 y 坐标。
  • 如果当前方向邻居 span 可通行，则取邻居 span 的 y 坐标和当前 y 坐标中的最大值作为当前 y 坐标。
  • 如果当前方向邻居 span 可通行，且邻居 span 的下一个方向邻居 span 可通行，则同样取其 y 坐标和当前 y 坐标中的最大值作为当前 y 坐标。
  • 如果下一个方向邻居 span 可通行，则取其 y 坐标和当前 y 坐标中的最大值作为当前 y 坐标。
  • 如果下一个方向邻居 span 可通行，且当前方向邻居 span 可通行，则同样取其 y 坐标和当前 y 坐标中的最大值作为当前 y 坐标。
  • 检查完成后，当前 y 坐标即为轮廓点的 y 坐标。
  • 当前 span 、当前方向邻居 span 、当前方向邻居 span 的下一个方向邻居 span 、下一个方向邻居 span ，保持先后顺序，每次以其中一个为起始进行迭代检查。
    • 以当前的起始算起，如果前两个的 region 相同且为 borderSize 边界，后两个的 area 相同且不为 borderSize 边界，且四个 span 都可通行，则当前点为 borderSize 边界点。

简化轮廓顶点

• 简化轮廓顶点的方法 simplifyContour 实现如下：

// Recast/Source/RecastContour.cpp

...

static void simplifyContour(rcTempVector<int>& points, rcTempVector<int>& simplified,
							const float maxError, const int maxEdgeLen, const int buildFlags)
{
	// Add initial points.
	bool hasConnections = false;
	for (int i = 0; i < points.size(); i += 4)
	{
		if ((points[i+3] & RC_CONTOUR_REG_MASK) != 0)
		{
			hasConnections = true;
			break;
		}
	}
	
	if (hasConnections)
	{
		// The contour has some portals to other regions.
		// Add a new point to every location where the region changes.
		for (int i = 0, ni = static_cast<int>(points.size()) / 4; i < ni; ++i)
		{
			int ii = (i+1) % ni;
			const bool differentRegs = (points[i*4+3] & RC_CONTOUR_REG_MASK) != (points[ii*4+3] & RC_CONTOUR_REG_MASK);
			const bool areaBorders = (points[i*4+3] & RC_AREA_BORDER) != (points[ii*4+3] & RC_AREA_BORDER);
			if (differentRegs || areaBorders)
			{
				simplified.push_back(points[i*4+0]);
				simplified.push_back(points[i*4+1]);
				simplified.push_back(points[i*4+2]);
				simplified.push_back(i);
			}
		}
	}
	
	if (simplified.size() == 0)
	{
		// If there is no connections at all,
		// 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];
		int llz = points[2];
		int lli = 0;
		int urx = points[0];
		int ury = points[1];
		int urz = points[2];
		int uri = 0;
		for (int i = 0; i < points.size(); i += 4)
		{
			int x = points[i+0];
			int y = points[i+1];
			int z = points[i+2];
			if (x < llx || (x == llx && z < llz))
			{
				llx = x;
				lly = y;
				llz = z;
				lli = i/4;
			}
			if (x > urx || (x == urx && z > urz))
			{
				urx = x;
				ury = y;
				urz = z;
				uri = i/4;
			}
		}
		simplified.push_back(llx);
		simplified.push_back(lly);
		simplified.push_back(llz);
		simplified.push_back(lli);
		
		simplified.push_back(urx);
		simplified.push_back(ury);
		simplified.push_back(urz);
		simplified.push_back(uri);
	}
	
	// Add points until all raw points are within
	// error tolerance to the simplified shape.
	const int pn = static_cast<int>(points.size()) / 4;
	for (int i = 0; i < simplified.size()/4; )
	{
		int ii = (i+1) % (simplified.size()/4);
		
		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.
		if (bx > ax || (bx == ax && bz > az))
		{
			cinc = 1;
			ci = (ai+cinc) % pn;
			endi = bi;
		}
		else
		{
			cinc = pn-1;
			ci = (bi+cinc) % pn;
			endi = ai;
			rcSwap(ax, bx);
			rcSwap(az, bz);
		}
		
		// Tessellate only outer edges or edges between areas.
		if ((points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0 ||
			(points[ci*4+3] & RC_AREA_BORDER))
		{
			while (ci != endi)
			{
				float d = distancePtSeg(points[ci*4+0], points[ci*4+2], ax, az, bx, bz);
				if (d > maxd)
				{
					maxd = d;
					maxi = ci;
				}
				ci = (ci+cinc) % pn;
			}
		}
		
		
		// If the max deviation is larger than accepted error,
		// add new point, else continue to next segment.
		if (maxi != -1 && maxd > (maxError*maxError))
		{
			// Add space for the new point.
			simplified.resize(simplified.size()+4);
			const int n = static_cast<int>(simplified.size()) / 4;
			for (int j = n-1; j > i; --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];
			}
			// Add the point.
			simplified[(i+1)*4+0] = points[maxi*4+0];
			simplified[(i+1)*4+1] = points[maxi*4+1];
			simplified[(i+1)*4+2] = points[maxi*4+2];
			simplified[(i+1)*4+3] = maxi;
		}
		else
		{
			++i;
		}
	}
	
	// Split too long edges.
	if (maxEdgeLen > 0 && (buildFlags & (RC_CONTOUR_TESS_WALL_EDGES|RC_CONTOUR_TESS_AREA_EDGES)) != 0)
	{
		for (int i = 0; i < simplified.size()/4; )
		{
			const 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];
			
			// 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.
			if ((buildFlags & RC_CONTOUR_TESS_WALL_EDGES) && (points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0)
				tess = true;
			// Edges between areas.
			if ((buildFlags & RC_CONTOUR_TESS_AREA_EDGES) && (points[ci*4+3] & RC_AREA_BORDER))
				tess = true;
			
			if (tess)
			{
				int dx = bx - ax;
				int dz = bz - az;
				if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen)
				{
					// Round based on the segments in lexilogical order so that the
					// max tesselation is consistent regardless in which direction
					// segments are traversed.
					const int n = bi < ai ? (bi+pn - ai) : (bi - ai);
					if (n > 1)
					{
						if (bx > ax || (bx == ax && bz > az))
							maxi = (ai + n/2) % pn;
						else
							maxi = (ai + (n+1)/2) % pn;
					}
				}
			}
			
			// If the max deviation is larger than accepted error,
			// add new point, else continue to next segment.
			if (maxi != -1)
			{
				// Add space for the new point.
				simplified.resize(simplified.size()+4);
				const int n = static_cast<int>(simplified.size()) / 4;
				for (int j = n-1; j > i; --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];
				}
				// Add the point.
				simplified[(i+1)*4+0] = points[maxi*4+0];
				simplified[(i+1)*4+1] = points[maxi*4+1];
				simplified[(i+1)*4+2] = points[maxi*4+2];
				simplified[(i+1)*4+3] = maxi;
			}
			else
			{
				++i;
			}
		}
	}
	
	for (int i = 0; i < simplified.size()/4; ++i)
	{
		// The edge vertex flag is take from the current raw point,
		// and the neighbour region is take from the next raw point.
		const int ai = (simplified[i*4+3]+1) % pn;
		const int bi = simplified[i*4+3];
		simplified[i*4+3] = (points[ai*4+3] & (RC_CONTOUR_REG_MASK|RC_AREA_BORDER)) | (points[bi*4+3] & RC_BORDER_VERTEX);
	}
	
}

...

• 简化轮廓的过程使用了 simplified 数组记录简化后的轮廓点信息，每个简化点使用 4 个整数表示，依次为 x 、y 、z 和在原始轮廓 points 中的索引信息，简化完成后再将索引信息替换为 region 信息。
• simplifyContour 的过程如下：
  • 如果轮廓中存在可行走的点，则依次遍历每个原轮廓点，如果当前点和下个点的 region 或 area 不同，则将当前点加入到简化轮廓列表 simplified 中。
  • 如果 simplified 为空，即没有找到 region 或 area 不同的点，则将轮廓的左下点和右上点加入到 simplified 中。
  • 遍历 simplified 组成的每一条边，找到所有 region 不为 0 或者是 area 边界的原轮廓点，通过 distancePtSeg 方法计算这些原轮廓点到这条边的距离，从中找到距离最大的原轮廓点，如果该距离大于 maxError，则将该原轮廓点插入到 simplified 中此边的中间，否则跳过此边。
  • 如果设置了 maxEdgeLen 且设置了需要进行细化，则依次遍历 simplified 组成的每一条边.
    • 如果边的起点的下一个原始轮廓点的 region 不为 0 且设置了细化墙边（RC_CONTOUR_TESS_WALL_EDGES），或者下一个原始轮廓点为 area 边界且设置了细化区域边（RC_CONTOUR_TESS_AREA_EDGES），则此边需要进行细化处理。
    • 对于需要细化处理的边，如果边的长度大于 maxEdgeLen，且边上除端点外的原始轮廓点数量大于 1，则取中间的原始轮廓点，插入到 simplified 中此边的中间。
  • 遍历 simplified 的每个点，将索引信息替换为 region 信息。

查找孔洞

• 通过 calcAreaOfPolygon2D 方法，在所有轮廓中识别出孔洞，其实现如下：

// Recast/Source/RecastContour.cpp
...

static int calcAreaOfPolygon2D(const int* verts, const int nverts)
{
	int area = 0;
	for (int i = 0, j = nverts-1; i < nverts; j=i++)
	{
		const int* vi = &verts[i*4];
		const int* vj = &verts[j*4];
		area += vi[0] * vj[2] - vj[0] * vi[2];
	}
	return (area+1) / 2;
}

...

• 查找轮廓的时候是按顺时针方向进行得到的结果，而多边形的顶点是按逆时针方向排序的，所以计算面积时需要使用轮廓的当前顶点和上一个顶点来计算。
• 遍历每个顶点，根据原点和当前顶点的向量，以及原点到上一个顶点的向量，两者的叉积得到三个点组成的三角形的面积，而所有三角形面积之和即为多边形的面积。其中，叉积为正，表示从向量 1 到向量 2 为逆时针旋转。叉积为负，表示从向量 1 到向量 2 为顺时针旋转。
• 如果最终多边形的面积为负，则表示该轮廓为逆时针方向，即为孔洞。相反，如果面积为正，则表示该轮廓为外轮廓。

合并孔洞

• 通过 mergeRegionHoles 方法，将孔洞合并到外轮廓中，其实现如下：

// Recast/Source/RecastContour.cpp

...

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 consecutive 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 = intersectSegContour(pt, corner, diags[i].vert, outline->nverts, outline->verts);	//这里的 diags[i] 应该是错误的，实际应该是 diags[j]
				for (int k = i; k < region.nholes && !intersect; k++)
					intersect |= intersectSegContour(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;
		}
	}
}

...

• mergeRegionHoles 合并的主要步骤如下：
  • 遍历当前 region 的每个 hole，设置每个 hole 的左下点坐标及索引，并将 hole 按照左下点坐标进行排序，越靠近左下的排在前面。
  • 遍历当前 region 的每个 hole，对每个 hole 进行处理。
    • 从当前 hole 最左下点开始，依次将每个点为拐角点，迭代进行检查。
      • 遍历当前 region 外轮廓的每个点，通过 inCone 方法判断拐角点是否在当前外轮廓点及其前后两个点组成的角度区域内，如果在，则计算该点和拐角点的距离，并将该点加入到 diags 数组中。
      • 对 diags 数组按照距离从小到大进行排序。
      • 遍历 diags 数组，通过 intersectSegContour 方法依次检查 diags[j] 和拐角点的线段的包围盒是否和 outline 中不包含 diags[j] 的边的包围盒不相交，并且和剩余的 hole 的任意边的包围盒也不相交，如果都不相交，则 diags[j] 为合并点，结束迭代。
      • 如果没有找到合并点，则将下一个点设置为拐角点，继续迭代。
    • 如果找到了合并点，则通过 mergeContours 方法将 hole 合并到 outline 中，检查相交情况时，则不需要再检查此 hole，因为已经加入到 outline 中，检查和 outline 的相交情况已经同时处理了。（如果没有找到合并点，后续也没有重新检查未被合并的 hole 的相交情况，可能存在问题？）
• inCone 方法的实现如下：

// Recast/Source/RecastContour.cpp

...

static bool	inCone(int i, int n, const int* verts, const int* pj)
{
	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));
}

...

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

// 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;
}
...

• inCone 方法通过当前顶点、上一个顶点、下一个顶点组成的角，判断目标点是否在角组成的范围内。left 方法通过向量 AB 和向量 AC 的叉积，来判断点所在的位置。通常情况下，如果向量叉积为正，则点 C 在向量 AB 的逆时针方向，即左侧，如果为负，则点 C 在向量 AB 的顺时针方向，即右侧。而这里的 left 方法判断相反，但前面提到，轮廓顶点是按顺时针方向得到的，多边形顶点则是按逆时针方向排序的，而这里使用的是轮廓的顶点顺序，因此 left 代表的是多边形排序的左侧，所以结果上也是正确的。
• intersectSegContour 方法的实现如下：

// Recast/Source/RecastContour.cpp

...

inline bool collinear(const int* a, const int* b, const int* c)
{
	return area2(a, b, c) == 0;
}

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 (left(a,b,c) ^ left(a,b,d)) && (left(c,d,a) ^ left(c,d,b));
}

// Returns T iff (a,b,c) are collinear and point c lies
// on the closed segment 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 intersectSegContour(const int* d0, const int* d1, int i, int n, const int* verts)
{
	// 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;
}

• intersectSegContour 方法通过传入的两个点组成的线段，遍历顶点数组中的每条边，跳过和输入点及指定索引相同的顶点所在的边，通过 intersect 方法判断在 xz 平面上线段的包围盒和边的包围盒是否相交。同样，也是通过向量叉积的方式进行计算，当两条线段中各自的顶点，都处在另一线段的两侧，说明两条线段直接相交。当两条线段中的任一顶点，处在另一条线段的包围盒中，则两条线段的包围盒相交。
• mergeContours 方法的实现如下：

// Recast/Source/RecastContour.cpp

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)
	{
		int* dst = &verts[nv*4];
		const int* src = &ca.verts[((ia+i)%ca.nverts)*4];
		dst[0] = src[0];
		dst[1] = src[1];
		dst[2] = src[2];
		dst[3] = src[3];
		nv++;
	}

	// Copy contour B
	for (int i = 0; i <= cb.nverts; ++i)
	{
		int* dst = &verts[nv*4];
		const int* src = &cb.verts[((ib+i)%cb.nverts)*4];
		dst[0] = src[0];
		dst[1] = src[1];
		dst[2] = src[2];
		dst[3] = src[3];
		nv++;
	}
	
	rcFree(ca.verts);
	ca.verts = verts;
	ca.nverts = nv;
	
	rcFree(cb.verts);
	cb.verts = 0;
	cb.nverts = 0;
	
	return true;
}

...

• mergeContours 方法，从 outline 找到的合并点起，将 outline 的所有点加入的到新的轮廓中，再把合并点加入，接着从 hole 的拐角点起，将 hole 的所有点加入，再把拐角点加入，得到合并后的轮廓。每个轮廓都将起始点重复加入，确保闭合。

建立多边形网格

• 建立多边形网格过程，使用 rcPolyMesh 结构保存多边形网格数据，其定义如下：

// Recast/Include/Recast.h

...

struct rcPolyMesh
{
	...

	unsigned short* verts;	/// 顶点坐标，每个顶点占 3 位
	unsigned short* polys;	/// 多边形顶点索引，以及其每条边的邻居多边形索引，尺寸为 npolys * nvp * 2，[0 , npolys * nvp - 1] 为顶点索引，[npolys * nvp , npolys * nvp * 2 - 1] 为邻居多边形索引
	unsigned short* regs;	/// 每个多边形的地区
	unsigned short* flags;	/// 每个多边形的标记
	unsigned char* areas;	/// 每个多边形的区域
	int nverts;				/// 顶点数量
	int npolys;				/// 多边形数量
	int maxpolys;			/// 已申请的最大多边形数量
	int nvp;				/// 每个多边形的最大顶点数量
	float bmin[3];			/// 同 rcHeightfield
	float bmax[3];			/// 同 rcHeightfield
	float cs;				/// 同 rcHeightfield
	float ch;				/// 同 rcHeightfield
	int borderSize;			/// 同 rcConfig::borderSize
	float maxEdgeError;		/// 同 rcContourSet::maxError
	
	...
};

• 建立过程通过 rcBuildPolyMesh 方法实现，其代码如下：

bool rcBuildPolyMesh(rcContext* ctx, const rcContourSet& cset, const int nvp, rcPolyMesh& mesh)
{
	rcAssert(ctx);
	
	rcScopedTimer timer(ctx, RC_TIMER_BUILD_POLYMESH);

	rcVcopy(mesh.bmin, cset.bmin);
	rcVcopy(mesh.bmax, cset.bmax);
	mesh.cs = cset.cs;
	mesh.ch = cset.ch;
	mesh.borderSize = cset.borderSize;
	mesh.maxEdgeError = cset.maxError;
	
	int maxVertices = 0;
	int maxTris = 0;
	int maxVertsPerCont = 0;
	for (int i = 0; i < cset.nconts; ++i)
	{
		// Skip null contours.
		if (cset.conts[i].nverts < 3) continue;
		maxVertices += cset.conts[i].nverts;
		maxTris += cset.conts[i].nverts - 2;
		maxVertsPerCont = rcMax(maxVertsPerCont, cset.conts[i].nverts);
	}
	
	if (maxVertices >= 0xfffe)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many vertices %d.", maxVertices);
		return false;
	}
		
	rcScopedDelete<unsigned char> vflags((unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP));
	if (!vflags)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'vflags' (%d).", maxVertices);
		return false;
	}
	memset(vflags, 0, maxVertices);
	
	mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertices*3, RC_ALLOC_PERM);
	if (!mesh.verts)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
		return false;
	}
	mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2, RC_ALLOC_PERM);
	if (!mesh.polys)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2);
		return false;
	}
	mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris, RC_ALLOC_PERM);
	if (!mesh.regs)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.regs' (%d).", maxTris);
		return false;
	}
	mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris, RC_ALLOC_PERM);
	if (!mesh.areas)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.areas' (%d).", maxTris);
		return false;
	}
	
	mesh.nverts = 0;
	mesh.npolys = 0;
	mesh.nvp = nvp;
	mesh.maxpolys = maxTris;
	
	memset(mesh.verts, 0, sizeof(unsigned short)*maxVertices*3);
	memset(mesh.polys, 0xff, sizeof(unsigned short)*maxTris*nvp*2);
	memset(mesh.regs, 0, sizeof(unsigned short)*maxTris);
	memset(mesh.areas, 0, sizeof(unsigned char)*maxTris);
	
	rcScopedDelete<int> nextVert((int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP));
	if (!nextVert)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices);
		return false;
	}
	memset(nextVert, 0, sizeof(int)*maxVertices);
	
	rcScopedDelete<int> firstVert((int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP));
	if (!firstVert)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
		return false;
	}
	for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
		firstVert[i] = -1;
	
	rcScopedDelete<int> indices((int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP));
	if (!indices)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont);
		return false;
	}
	rcScopedDelete<int> tris((int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP));
	if (!tris)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3);
		return false;
	}
	rcScopedDelete<unsigned short> polys((unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP));
	if (!polys)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp);
		return false;
	}
	unsigned short* tmpPoly = &polys[maxVertsPerCont*nvp];

	for (int i = 0; i < cset.nconts; ++i)
	{
		rcContour& cont = cset.conts[i];
		
		// Skip null contours.
		if (cont.nverts < 3)
			continue;
		
		// Triangulate contour
		for (int j = 0; j < cont.nverts; ++j)
			indices[j] = j;
			
		int ntris = triangulate(cont.nverts, cont.verts, &indices[0], &tris[0]);
		if (ntris <= 0)
		{
			// Bad triangulation, should not happen.
/*			printf("\tconst float bmin[3] = {%ff,%ff,%ff};\n", cset.bmin[0], cset.bmin[1], cset.bmin[2]);
			printf("\tconst float cs = %ff;\n", cset.cs);
			printf("\tconst float ch = %ff;\n", cset.ch);
			printf("\tconst int verts[] = {\n");
			for (int k = 0; k < cont.nverts; ++k)
			{
				const int* v = &cont.verts[k*4];
				printf("\t\t%d,%d,%d,%d,\n", v[0], v[1], v[2], v[3]);
			}
			printf("\t};\n\tconst int nverts = sizeof(verts)/(sizeof(int)*4);\n");*/
			ctx->log(RC_LOG_WARNING, "rcBuildPolyMesh: Bad triangulation Contour %d.", i);
			ntris = -ntris;
		}
				
		// Add and merge vertices.
		for (int j = 0; j < cont.nverts; ++j)
		{
			const int* v = &cont.verts[j*4];
			indices[j] = addVertex((unsigned short)v[0], (unsigned short)v[1], (unsigned short)v[2],
								   mesh.verts, firstVert, nextVert, mesh.nverts);
			if (v[3] & RC_BORDER_VERTEX)
			{
				// This vertex should be removed.
				vflags[indices[j]] = 1;
			}
		}

		// Build initial polygons.
		int npolys = 0;
		memset(polys, 0xff, maxVertsPerCont*nvp*sizeof(unsigned short));
		for (int j = 0; j < ntris; ++j)
		{
			int* t = &tris[j*3];
			if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
			{
				polys[npolys*nvp+0] = (unsigned short)indices[t[0]];
				polys[npolys*nvp+1] = (unsigned short)indices[t[1]];
				polys[npolys*nvp+2] = (unsigned short)indices[t[2]];
				npolys++;
			}
		}
		if (!npolys)
			continue;
		
		// Merge polygons.
		if (nvp > 3)
		{
			for(;;)
			{
				// Find best polygons to merge.
				int bestMergeVal = 0;
				int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
				
				for (int j = 0; j < npolys-1; ++j)
				{
					unsigned short* pj = &polys[j*nvp];
					for (int k = j+1; k < npolys; ++k)
					{
						unsigned short* pk = &polys[k*nvp];
						int ea, eb;
						int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);
						if (v > bestMergeVal)
						{
							bestMergeVal = v;
							bestPa = j;
							bestPb = k;
							bestEa = ea;
							bestEb = eb;
						}
					}
				}
				
				if (bestMergeVal > 0)
				{
					// Found best, merge.
					unsigned short* pa = &polys[bestPa*nvp];
					unsigned short* pb = &polys[bestPb*nvp];
					mergePolyVerts(pa, pb, bestEa, bestEb, tmpPoly, nvp);
					unsigned short* lastPoly = &polys[(npolys-1)*nvp];
					if (pb != lastPoly)
						memcpy(pb, lastPoly, sizeof(unsigned short)*nvp);
					npolys--;
				}
				else
				{
					// Could not merge any polygons, stop.
					break;
				}
			}
		}
		
		// Store polygons.
		for (int j = 0; j < npolys; ++j)
		{
			unsigned short* p = &mesh.polys[mesh.npolys*nvp*2];
			unsigned short* q = &polys[j*nvp];
			for (int k = 0; k < nvp; ++k)
				p[k] = q[k];
			mesh.regs[mesh.npolys] = cont.reg;
			mesh.areas[mesh.npolys] = cont.area;
			mesh.npolys++;
			if (mesh.npolys > maxTris)
			{
				ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
				return false;
			}
		}
	}
	
	
	// Remove edge vertices.
	for (int i = 0; i < mesh.nverts; ++i)
	{
		if (vflags[i])
		{
			if (!canRemoveVertex(ctx, mesh, (unsigned short)i))
				continue;
			if (!removeVertex(ctx, mesh, (unsigned short)i, maxTris))
			{
				// Failed to remove vertex
				ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Failed to remove edge vertex %d.", i);
				return false;
			}
			// Remove vertex
			// Note: mesh.nverts is already decremented inside removeVertex()!
			// Fixup vertex flags
			for (int j = i; j < mesh.nverts; ++j)
				vflags[j] = vflags[j+1];
			--i;
		}
	}
	
	// Calculate adjacency.
	if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, nvp))
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Adjacency failed.");
		return false;
	}
	
	// Find portal edges
	if (mesh.borderSize > 0)
	{
		const int w = cset.width;
		const int h = cset.height;
		for (int i = 0; i < mesh.npolys; ++i)
		{
			unsigned short* p = &mesh.polys[i*2*nvp];
			for (int j = 0; j < nvp; ++j)
			{
				if (p[j] == RC_MESH_NULL_IDX) break;
				// Skip connected edges.
				if (p[nvp+j] != RC_MESH_NULL_IDX)
					continue;
				int nj = j+1;
				if (nj >= nvp || p[nj] == RC_MESH_NULL_IDX) nj = 0;
				const unsigned short* va = &mesh.verts[p[j]*3];
				const unsigned short* vb = &mesh.verts[p[nj]*3];

				if ((int)va[0] == 0 && (int)vb[0] == 0)
					p[nvp+j] = 0x8000 | 0;
				else if ((int)va[2] == h && (int)vb[2] == h)
					p[nvp+j] = 0x8000 | 1;
				else if ((int)va[0] == w && (int)vb[0] == w)
					p[nvp+j] = 0x8000 | 2;
				else if ((int)va[2] == 0 && (int)vb[2] == 0)
					p[nvp+j] = 0x8000 | 3;
			}
		}
	}

	// Just allocate the mesh flags array. The user is resposible to fill it.
	mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*mesh.npolys, RC_ALLOC_PERM);
	if (!mesh.flags)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.flags' (%d).", mesh.npolys);
		return false;
	}
	memset(mesh.flags, 0, sizeof(unsigned short) * mesh.npolys);
	
	if (mesh.nverts > 0xffff)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
	}
	if (mesh.npolys > 0xffff)
	{
		ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
	}
	
	return true;
}

...

• rcBuildPolyMesh 的主要步骤如下：
  • 初始化 rcPolyMesh 结构 mesh 对象，用于存储网格信息。
  • 遍历 cset 中的轮廓处理。
    • 初始化顶点索引 indices，通过 triangulate 方法将轮廓划分成三角形，存储到 tris 中。
    • 遍历轮廓的每个顶点，通过 addVertex 方法去除重复顶点（x、z 坐标相同，y 坐标差值在 2 以内），重新生成顶点索引，更新到 indices 中，并将顶点坐标记录到 mesh.verts 中。同时，对处在 borderSize 范围内的顶点标记到 vflags 中。
    • 将 indices 每个三角形的顶点索引存储到临时数组 polys 中。
    • 如果每个多边形的最大顶点数 nvp 大于 3，则进行多边形合并。
      • 遍历 polys 中每两个多边形，通过 getPolyMergeValue 方法找到所有具有公共边的多边形组合，取其中公共边最长的多边形组合，通过 mergePolyVerts方法，按照顶点顺序，从各自的公共边终点起，依次加入到新的多边形顶点数组中。
      • 直到没有多边形能进行合并时，结束合并。
    • 将多边形数据存储到 mesh.polys[i * nvp * 2] 中，且记录每个多边形所属的 region 和 area，mesh.polys[i * nvp] 的暂时不填充数据。
  • 遍历 mesh.verts 中的每个顶点，如果该顶点标记在 vflags 中，则通过 canRemoveVertex 方法检查该顶点能否移除，如果能移除则通过 removeVertex 方法移除。
  • 通过 buildMeshAdjacency 方法，计算并记录多边形的邻居信息。
  • 如果 borderSize 大于 0，则检查所有多边形的非共享边，根据边的 x 、z 坐标，将边界信息记录到 mesh.polys[nvp + j] 中（j 为边的起始点索引）。
    • 如果边的 x 坐标都为 0 ，即为左边界，则 mesh.polys[nvp + j] = 0x8001。
    • 如果边的 z 坐标都为 cset.height ，即为上边界，则 mesh.polys[nvp + j] = 0x8002。
    • 如果边的 x 坐标都为 cset.width ，即为右边界，则 mesh.polys[nvp + j] = 0x8003。
    • 如果边的 z 坐标都为 0 ，即为下边界，则 mesh.polys[nvp + j] = 0x8004。
  • 初始化 mesh.flags 数组，大小为 mesh.npolys，用于后续标记使用。

将轮廓点划分成三角形

• triangulate 方法的实现如下：

// Recase/Source/RecastMesh.cpp

...

static int triangulate(int n, const int* verts, int* indices, int* tris)
{
	int ntris = 0;
	int* dst = tris;
	
	// The last bit of the index is used to indicate if the vertex can be removed.
	for (int i = 0; i < n; i++)
	{
		int i1 = next(i, n);
		int i2 = next(i1, n);
		if (diagonal(i, i2, n, verts, indices))
			indices[i1] |= 0x80000000;
	}
	
	while (n > 3)
	{
		int minLen = -1;
		int mini = -1;
		for (int i = 0; i < n; i++)
		{
			int i1 = next(i, n);
			if (indices[i1] & 0x80000000)
			{
				const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4];
				const int* p2 = &verts[(indices[next(i1, 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)
		{
			// 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++)
			{
				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;
			}
		}
		
		int i = mini;
		int i1 = next(i, n);
		int i2 = next(i1, n);
		
		*dst++ = indices[i] & 0x0fffffff;
		*dst++ = indices[i1] & 0x0fffffff;
		*dst++ = indices[i2] & 0x0fffffff;
		ntris++;
		
		// Removes P[i1] by copying P[i+1]...P[n-1] left one index.
		n--;
		for (int k = i1; k < n; k++)
			indices[k] = indices[k+1];
		
		if (i1 >= n) i1 = 0;
		i = prev(i1,n);
		// Update diagonal flags.
		if (diagonal(prev(i, n), i1, n, verts, indices))
			indices[i] |= 0x80000000;
		else
			indices[i] &= 0x0fffffff;
		
		if (diagonal(i, next(i1, n), n, verts, indices))
			indices[i1] |= 0x80000000;
		else
			indices[i1] &= 0x0fffffff;
	}
	
	// Append the remaining triangle.
	*dst++ = indices[0] & 0x0fffffff;
	*dst++ = indices[1] & 0x0fffffff;
	*dst++ = indices[2] & 0x0fffffff;
	ntris++;
	
	return ntris;
}

...

• 将轮廓点划分成三角形的步骤如下：
  • 遍历每个顶点 i，通过 diagonal 方法，检查顶点 i 和 i + 2 组成的线段的包围盒是否和轮廓不包含这两个点的边的包围盒相交，如果不相交，表示该线段可以划分三角形，标记 indices[i + 1] 的最高位为 1。
    • diagonal 方法最终也是通过 inCone 和 intersect 方法实现。
  • 当轮廓顶点数量超过 3 时，即可以划分成多个三角形，则进行迭代检查处理。
    • 遍历每个顶点 i，如果 indices[i + 1] 已经标记，则计算 i 和 i + 2 组成的线段长度，记录所有长度中的最小值及对应的顶点索引。
    • 如果顶点都没有标记，则通过 diagonalLoose 方法，再次遍历每个顶点 i 检查相交情况。如果不相交，同样计算 i 和 i + 2 组成的线段长度，记录所有长度中的最小值及对应的顶点索引。如果还是没有找到不相交的对角线，则当前轮廓无法再划分三角形，返回 -ntris。
      • diagonalLoose 方法是通过 inConeLoose 和 intersectProp 方法实现，降低了对划分三角形的对角线要求，即。其中，inConeLoose 检查点是否在角度范围内时，增加了三个点共线的情况，intersectProp 方法只检查线段直接相交的情况。
    • 将长度最小值对应的顶点索引 i 及其后续两个顶点 i + 1 和 i + 2，依次加入到 tris 中，作为一个划分的三角形，并从轮廓点中移除 i + 1 顶点。
    • 对顶点 i - 1 和 i，通过 diagonal 方法，重新检查相交情况进行标记。
    • 继续进行迭代划分，直到不能再划分为止。

查找多边形公共边

• getPolyMergeValue 的实现如下：

// Recast/Source/RecastMesh.cpp

...

static int getPolyMergeValue(unsigned short* pa, unsigned short* pb,
							 const unsigned short* verts, int& ea, int& eb,
							 const int nvp)
{
	const int na = countPolyVerts(pa, nvp);
	const int nb = countPolyVerts(pb, nvp);
	
	// If the merged polygon would be too big, do not merge.
	if (na+nb-2 > nvp)
		return -1;
	
	// Check if the polygons share an edge.
	ea = -1;
	eb = -1;
	
	for (int i = 0; i < na; ++i)
	{
		unsigned short va0 = pa[i];
		unsigned short va1 = pa[(i+1) % na];
		if (va0 > va1)
			rcSwap(va0, va1);
		for (int j = 0; j < nb; ++j)
		{
			unsigned short vb0 = pb[j];
			unsigned short vb1 = pb[(j+1) % nb];
			if (vb0 > vb1)
				rcSwap(vb0, vb1);
			if (va0 == vb0 && va1 == vb1)
			{
				ea = i;
				eb = j;
				break;
			}
		}
	}
	
	// No common edge, cannot merge.
	if (ea == -1 || eb == -1)
		return -1;
	
	// Check to see if the merged polygon would be convex.
	unsigned short va, vb, vc;
	
	va = pa[(ea+na-1) % na];
	vb = pa[ea];
	vc = pb[(eb+2) % nb];
	if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
		return -1;
	
	va = pb[(eb+nb-1) % nb];
	vb = pb[eb];
	vc = pa[(ea+2) % na];
	if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
		return -1;
	
	va = pa[ea];
	vb = pa[(ea+1)%na];
	
	int dx = (int)verts[va*3+0] - (int)verts[vb*3+0];
	int dy = (int)verts[va*3+2] - (int)verts[vb*3+2];
	
	return dx*dx + dy*dy;
}

...

• getPolyMergeValue 查找公共边的步骤如下：
  • 检查两个多边形合并后的顶点数量，如果超过 nvp 则不能合并。
  • 遍历第一个多边形的每条边，从第二个多边形中查找是否有相同的边，找到则记录边对应的顶点索引。
  • 检查公共边合并后新的两个角是否为凸角，如果是则计算公共边距离平方返回，表示该公共边可以合并。检查方式为：
    • 检查第二个多边形中公共边的下一个顶点，是否在第一个多边形公共边的上一个顶点及第一个顶点组成的向量右侧。
    • 检查第一个多边形中公共边的下一个顶点，是否在第二个多边形公共边的上一个顶点及第一个顶点组成的向量右侧。

移除边界顶点

• 合并完成后，对于处在 borderSize 范围内的顶点，通过 canRemoveVertex 检查是否能移除，其实现如下：

// Recast/Source/RecastMesh.cpp

...

static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem)
{
	const int nvp = mesh.nvp;
	
	// Count number of polygons to remove.
	int numTouchedVerts = 0;
	int numRemainingEdges = 0;
	for (int i = 0; i < mesh.npolys; ++i)
	{
		unsigned short* p = &mesh.polys[i*nvp*2];
		const int nv = countPolyVerts(p, nvp);
		int numRemoved = 0;
		int numVerts = 0;
		for (int j = 0; j < nv; ++j)
		{
			if (p[j] == rem)
			{
				numTouchedVerts++;
				numRemoved++;
			}
			numVerts++;
		}
		if (numRemoved)
		{
			numRemainingEdges += numVerts-(numRemoved+1);
		}
	}
	
	// There would be too few edges remaining to create a polygon.
	// This can happen for example when a tip of a triangle is marked
	// as deletion, but there are no other polys that share the vertex.
	// In this case, the vertex should not be removed.
	if (numRemainingEdges <= 2)
		return false;
	
	// Find edges which share the removed vertex.
	const int maxEdges = numTouchedVerts*2;
	int nedges = 0;
	rcScopedDelete<int> edges((int*)rcAlloc(sizeof(int)*maxEdges*3, RC_ALLOC_TEMP));
	if (!edges)
	{
		ctx->log(RC_LOG_WARNING, "canRemoveVertex: Out of memory 'edges' (%d).", maxEdges*3);
		return false;
	}
		
	for (int i = 0; i < mesh.npolys; ++i)
	{
		unsigned short* p = &mesh.polys[i*nvp*2];
		const int nv = countPolyVerts(p, nvp);

		// Collect edges which touches the removed vertex.
		for (int j = 0, k = nv-1; j < nv; k = j++)
		{
			if (p[j] == rem || p[k] == rem)
			{
				// Arrange edge so that a=rem.
				int a = p[j], b = p[k];
				if (b == rem)
					rcSwap(a,b);
					
				// Check if the edge exists
				bool exists = false;
				for (int m = 0; m < nedges; ++m)
				{
					int* e = &edges[m*3];
					if (e[1] == b)
					{
						// Exists, increment vertex share count.
						e[2]++;
						exists = true;
					}
				}
				// Add new edge.
				if (!exists)
				{
					int* e = &edges[nedges*3];
					e[0] = a;
					e[1] = b;
					e[2] = 1;
					nedges++;
				}
			}
		}
	}

	// There should be no more than 2 open edges.
	// This catches the case that two non-adjacent polygons
	// share the removed vertex. In that case, do not remove the vertex.
	int numOpenEdges = 0;
	for (int i = 0; i < nedges; ++i)
	{
		if (edges[i*3+2] < 2)
			numOpenEdges++;
	}
	if (numOpenEdges > 2)
		return false;
	
	return true;
}

...

• canRemoveVertex 的检查过程如下：
  • 遍历 mesh 中的所有多边形，统计顶点总数和包含待移除的顶点数量，计算移除顶点后的剩余边数，确保不能小于 2。
  • 遍历 mesh 的每个多边形，记录包含待移除顶点的边的出现次数，如果出现次数大于 2，则该边为公共边，否则为开放边。
  • 检查包含待移除顶点的所有边，如果出现超过 2 条开放边，则表示该顶点移除会出现多个开口，会破坏多边形结构，因此不能移除。
• 移除顶点的方法 removeVertex 的实现如下：

// Recast/Source/RecastMesh.cpp

...

static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem, const int maxTris)
{
	const int nvp = mesh.nvp;

	// Count number of polygons to remove.
	int numRemovedVerts = 0;
	for (int i = 0; i < mesh.npolys; ++i)
	{
		unsigned short* p = &mesh.polys[i*nvp*2];
		const int nv = countPolyVerts(p, nvp);
		for (int j = 0; j < nv; ++j)
		{
			if (p[j] == rem)
				numRemovedVerts++;
		}
	}
	
	int nedges = 0;
	rcScopedDelete<int> edges((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp*4, RC_ALLOC_TEMP));
	if (!edges)
	{
		ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'edges' (%d).", numRemovedVerts*nvp*4);
		return false;
	}

	int nhole = 0;
	rcScopedDelete<int> hole((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP));
	if (!hole)
	{
		ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hole' (%d).", numRemovedVerts*nvp);
		return false;
	}

	int nhreg = 0;
	rcScopedDelete<int> hreg((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP));
	if (!hreg)
	{
		ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hreg' (%d).", numRemovedVerts*nvp);
		return false;
	}

	int nharea = 0;
	rcScopedDelete<int> harea((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP));
	if (!harea)
	{
		ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'harea' (%d).", numRemovedVerts*nvp);
		return false;
	}
	
	for (int i = 0; i < mesh.npolys; ++i)
	{
		unsigned short* p = &mesh.polys[i*nvp*2];
		const int nv = countPolyVerts(p, nvp);
		bool hasRem = false;
		for (int j = 0; j < nv; ++j)
			if (p[j] == rem) hasRem = true;
		if (hasRem)
		{
			// Collect edges which does not touch the removed vertex.
			for (int j = 0, k = nv-1; j < nv; k = j++)
			{
				if (p[j] != rem && p[k] != rem)
				{
					int* e = &edges[nedges*4];
					e[0] = p[k];
					e[1] = p[j];
					e[2] = mesh.regs[i];
					e[3] = mesh.areas[i];
					nedges++;
				}
			}
			// Remove the polygon.
			unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*nvp*2];
			if (p != p2)
				memcpy(p,p2,sizeof(unsigned short)*nvp);
			memset(p+nvp,0xff,sizeof(unsigned short)*nvp);
			mesh.regs[i] = mesh.regs[mesh.npolys-1];
			mesh.areas[i] = mesh.areas[mesh.npolys-1];
			mesh.npolys--;
			--i;
		}
	}
	
	// Remove vertex.
	for (int i = (int)rem; i < mesh.nverts - 1; ++i)
	{
		mesh.verts[i*3+0] = mesh.verts[(i+1)*3+0];
		mesh.verts[i*3+1] = mesh.verts[(i+1)*3+1];
		mesh.verts[i*3+2] = mesh.verts[(i+1)*3+2];
	}
	mesh.nverts--;

	// Adjust indices to match the removed vertex layout.
	for (int i = 0; i < mesh.npolys; ++i)
	{
		unsigned short* p = &mesh.polys[i*nvp*2];
		const int nv = countPolyVerts(p, nvp);
		for (int j = 0; j < nv; ++j)
			if (p[j] > rem) p[j]--;
	}
	for (int i = 0; i < nedges; ++i)
	{
		if (edges[i*4+0] > rem) edges[i*4+0]--;
		if (edges[i*4+1] > rem) edges[i*4+1]--;
	}

	if (nedges == 0)
		return true;

	// Start with one vertex, keep appending connected
	// segments to the start and end of the hole.
	pushBack(edges[0], hole, nhole);
	pushBack(edges[2], hreg, nhreg);
	pushBack(edges[3], harea, nharea);
	
	while (nedges)
	{
		bool match = false;
		
		for (int i = 0; i < nedges; ++i)
		{
			const int ea = edges[i*4+0];
			const int eb = edges[i*4+1];
			const int r = edges[i*4+2];
			const int a = edges[i*4+3];
			bool add = false;
			if (hole[0] == eb)
			{
				// The segment matches the beginning of the hole boundary.
				pushFront(ea, hole, nhole);
				pushFront(r, hreg, nhreg);
				pushFront(a, harea, nharea);
				add = true;
			}
			else if (hole[nhole-1] == ea)
			{
				// The segment matches the end of the hole boundary.
				pushBack(eb, hole, nhole);
				pushBack(r, hreg, nhreg);
				pushBack(a, harea, nharea);
				add = true;
			}
			if (add)
			{
				// The edge segment was added, remove it.
				edges[i*4+0] = edges[(nedges-1)*4+0];
				edges[i*4+1] = edges[(nedges-1)*4+1];
				edges[i*4+2] = edges[(nedges-1)*4+2];
				edges[i*4+3] = edges[(nedges-1)*4+3];
				--nedges;
				match = true;
				--i;
			}
		}
		
		if (!match)
			break;
	}

	rcScopedDelete<int> tris((int*)rcAlloc(sizeof(int)*nhole*3, RC_ALLOC_TEMP));
	if (!tris)
	{
		ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tris' (%d).", nhole*3);
		return false;
	}

	rcScopedDelete<int> tverts((int*)rcAlloc(sizeof(int)*nhole*4, RC_ALLOC_TEMP));
	if (!tverts)
	{
		ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tverts' (%d).", nhole*4);
		return false;
	}

	rcScopedDelete<int> thole((int*)rcAlloc(sizeof(int)*nhole, RC_ALLOC_TEMP));
	if (!thole)
	{
		ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'thole' (%d).", nhole);
		return false;
	}

	// Generate temp vertex array for triangulation.
	for (int i = 0; i < nhole; ++i)
	{
		const int pi = hole[i];
		tverts[i*4+0] = mesh.verts[pi*3+0];
		tverts[i*4+1] = mesh.verts[pi*3+1];
		tverts[i*4+2] = mesh.verts[pi*3+2];
		tverts[i*4+3] = 0;
		thole[i] = i;
	}

	// Triangulate the hole.
	int ntris = triangulate(nhole, &tverts[0], &thole[0], tris);
	if (ntris < 0)
	{
		ntris = -ntris;
		ctx->log(RC_LOG_WARNING, "removeVertex: triangulate() returned bad results.");
	}
	
	// Merge the hole triangles back to polygons.
	rcScopedDelete<unsigned short> polys((unsigned short*)rcAlloc(sizeof(unsigned short)*(ntris+1)*nvp, RC_ALLOC_TEMP));
	if (!polys)
	{
		ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'polys' (%d).", (ntris+1)*nvp);
		return false;
	}
	rcScopedDelete<unsigned short> pregs((unsigned short*)rcAlloc(sizeof(unsigned short)*ntris, RC_ALLOC_TEMP));
	if (!pregs)
	{
		ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pregs' (%d).", ntris);
		return false;
	}
	rcScopedDelete<unsigned char> pareas((unsigned char*)rcAlloc(sizeof(unsigned char)*ntris, RC_ALLOC_TEMP));
	if (!pareas)
	{
		ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pareas' (%d).", ntris);
		return false;
	}
	
	unsigned short* tmpPoly = &polys[ntris*nvp];
			
	// Build initial polygons.
	int npolys = 0;
	memset(polys, 0xff, ntris*nvp*sizeof(unsigned short));
	for (int j = 0; j < ntris; ++j)
	{
		int* t = &tris[j*3];
		if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
		{
			polys[npolys*nvp+0] = (unsigned short)hole[t[0]];
			polys[npolys*nvp+1] = (unsigned short)hole[t[1]];
			polys[npolys*nvp+2] = (unsigned short)hole[t[2]];

			// If this polygon covers multiple region types then
			// mark it as such
			if (hreg[t[0]] != hreg[t[1]] || hreg[t[1]] != hreg[t[2]])
				pregs[npolys] = RC_MULTIPLE_REGS;
			else
				pregs[npolys] = (unsigned short)hreg[t[0]];

			pareas[npolys] = (unsigned char)harea[t[0]];
			npolys++;
		}
	}
	if (!npolys)
		return true;
	
	// Merge polygons.
	if (nvp > 3)
	{
		for (;;)
		{
			// Find best polygons to merge.
			int bestMergeVal = 0;
			int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
			
			for (int j = 0; j < npolys-1; ++j)
			{
				unsigned short* pj = &polys[j*nvp];
				for (int k = j+1; k < npolys; ++k)
				{
					unsigned short* pk = &polys[k*nvp];
					int ea, eb;
					int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);
					if (v > bestMergeVal)
					{
						bestMergeVal = v;
						bestPa = j;
						bestPb = k;
						bestEa = ea;
						bestEb = eb;
					}
				}
			}
			
			if (bestMergeVal > 0)
			{
				// Found best, merge.
				unsigned short* pa = &polys[bestPa*nvp];
				unsigned short* pb = &polys[bestPb*nvp];
				mergePolyVerts(pa, pb, bestEa, bestEb, tmpPoly, nvp);
				if (pregs[bestPa] != pregs[bestPb])
					pregs[bestPa] = RC_MULTIPLE_REGS;

				unsigned short* last = &polys[(npolys-1)*nvp];
				if (pb != last)
					memcpy(pb, last, sizeof(unsigned short)*nvp);
				pregs[bestPb] = pregs[npolys-1];
				pareas[bestPb] = pareas[npolys-1];
				npolys--;
			}
			else
			{
				// Could not merge any polygons, stop.
				break;
			}
		}
	}
	
	// Store polygons.
	for (int i = 0; i < npolys; ++i)
	{
		if (mesh.npolys >= maxTris) break;
		unsigned short* p = &mesh.polys[mesh.npolys*nvp*2];
		memset(p,0xff,sizeof(unsigned short)*nvp*2);
		for (int j = 0; j < nvp; ++j)
			p[j] = polys[i*nvp+j];
		mesh.regs[mesh.npolys] = pregs[i];
		mesh.areas[mesh.npolys] = pareas[i];
		mesh.npolys++;
		if (mesh.npolys > maxTris)
		{
			ctx->log(RC_LOG_ERROR, "removeVertex: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
			return false;
		}
	}
	
	return true;
}

...

• removeVertex 移除的主要步骤如下：
  • 遍历 mesh 的所有多边形，将所有包含待移除顶点的边记录到 edges 中，并将该多边形从 mesh.polys 中移除。
  • 将目标顶点从 mesh 的 verts 中移除，且更新 mesh.polys[i * nvp * 2] 和 edges 中的顶点索引。
  • 以 edges 的第一条边的两个顶点为左侧点和右侧点，遍历 edges 中的剩余边，找到和左侧点相邻的边，将其的左侧点作为左侧点，找到和右侧点相邻的边，将其右侧点作为右侧点，最终得到一组重新排序的顶点。
  • 将排序后的顶点，通过 triangulate 方法划分成三角形。
  • 将三角形加入到临时数组 polys 中，并记录对应的 region 和 area 到 pregs 和 pareas 中。如果三角形的 region 不同，则将 pregs 中对应的值设置为 RC_MULTIPLE_REGS。
  • 如果每个多边形的最大顶点数 nvp 大于 3，则进行多边形合并。通过 getPolyMergeValue 方法找到公共边，mergePolyVerts 方法进行合并。如果两个多边形的 region 不同，则合并后的多边形的 region 设置为 RC_MULTIPLE_REGS。
  • 将合并后的多边形加入到 mesh.polys[i * nvp * 2] 中，同时更新 mesh.regs 和 mesh.areas。

计算多边形邻居

• 计算多边形邻居时，使用了 rcEdge 记录边的信息，其结构如下：

// Recast/Source/RecastMesh.cpp

...

struct rcEdge
{
	unsigned short vert[2];			
	unsigned short polyEdge[2];
	unsigned short poly[2];
};

...

• buildMeshAdjacency 的实现如下：

// Recast/Source/RecastMesh.cpp

...

static bool buildMeshAdjacency(unsigned short* polys, const int npolys,
							   const int nverts, const int vertsPerPoly)
{
	// Based on code by Eric Lengyel from:
	// https://web.archive.org/web/20080704083314/http://www.terathon.com/code/edges.php
	
	int maxEdgeCount = npolys*vertsPerPoly;
	unsigned short* firstEdge = (unsigned short*)rcAlloc(sizeof(unsigned short)*(nverts + maxEdgeCount), RC_ALLOC_TEMP);
	if (!firstEdge)
		return false;
	unsigned short* nextEdge = firstEdge + nverts;
	int edgeCount = 0;
	
	rcEdge* edges = (rcEdge*)rcAlloc(sizeof(rcEdge)*maxEdgeCount, RC_ALLOC_TEMP);
	if (!edges)
	{
		rcFree(firstEdge);
		return false;
	}
	
	for (int i = 0; i < nverts; i++)
		firstEdge[i] = RC_MESH_NULL_IDX;
	
	for (int i = 0; i < npolys; ++i)
	{
		unsigned short* t = &polys[i*vertsPerPoly*2];
		for (int j = 0; j < vertsPerPoly; ++j)
		{
			if (t[j] == RC_MESH_NULL_IDX) break;
			unsigned short v0 = t[j];
			unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
			if (v0 < v1)
			{
				rcEdge& edge = edges[edgeCount];
				edge.vert[0] = v0;
				edge.vert[1] = v1;
				edge.poly[0] = (unsigned short)i;
				edge.polyEdge[0] = (unsigned short)j;
				edge.poly[1] = (unsigned short)i;
				edge.polyEdge[1] = 0;
				// Insert edge
				nextEdge[edgeCount] = firstEdge[v0];
				firstEdge[v0] = (unsigned short)edgeCount;
				edgeCount++;
			}
		}
	}
	
	for (int i = 0; i < npolys; ++i)
	{
		unsigned short* t = &polys[i*vertsPerPoly*2];
		for (int j = 0; j < vertsPerPoly; ++j)
		{
			if (t[j] == RC_MESH_NULL_IDX) break;
			unsigned short v0 = t[j];
			unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
			if (v0 > v1)
			{
				for (unsigned short e = firstEdge[v1]; e != RC_MESH_NULL_IDX; e = nextEdge[e])
				{
					rcEdge& edge = edges[e];
					if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1])
					{
						edge.poly[1] = (unsigned short)i;
						edge.polyEdge[1] = (unsigned short)j;
						break;
					}
				}
			}
		}
	}
	
	// Store adjacency
	for (int i = 0; i < edgeCount; ++i)
	{
		const rcEdge& e = edges[i];
		if (e.poly[0] != e.poly[1])
		{
			unsigned short* p0 = &polys[e.poly[0]*vertsPerPoly*2];
			unsigned short* p1 = &polys[e.poly[1]*vertsPerPoly*2];
			p0[vertsPerPoly + e.polyEdge[0]] = e.poly[1];
			p1[vertsPerPoly + e.polyEdge[1]] = e.poly[0];
		}
	}
	
	rcFree(firstEdge);
	rcFree(edges);
	
	return true;
}

...

创建细节网格

创建导航数据

参考

• Github - Recast Navigation

---

• ← Previous Post