Algorithm

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

Posted by Xun on Monday, July 7, 2025

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 方法用于计算三角面的归一化法线。三角面和法线的示意图如下： Nav2_1.png
  • 三角面和 xz 平面的夹角即为坡度 θ，而法线和 y 轴的夹角也为 θ。由于法线为归一化，则法线在 y 轴上的投影即为 cosθ。随着坡度 θ 增大，cosθ 逐渐减小，当坡度 θ 小于 walkableSlopeAngle 时，该三角面则为可行走区域，将三角面的 areaID 设置为 RC_WALKABLE_AREA。
光栅化三角面
  • 光栅化三角面的过程，主要是对每个三角面，通过 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 坐标最小值为基准，转化为单元格 z' 表示。
    • 将 z' 最小值限制为 [-1, heightfield.height - 1] ，最大值限制为 [0, heightfield.height - 1] 。
    • 遍历 z' 坐标最小值到最大值区间，通过 dividePoly 方法，将三角面按单元格 z' 切分成多个多边形。
    • 对每个切分后的多边形，计算包围盒的 x 坐标最大最小值，，以高度场包围盒 x 坐标最小值为基准，转化为单元格 x' 表示。
    • 将 x' 最小值限制为 [-1, heightfield.width - 1] , 最大值限制为 [0, heightfield.width - 1] 。
    • 遍历 x' 坐标最小值到最大值区间，通过 dividePoly 方法，将多边形按单元格 x' 坐标再切分成多个子多边形。
    • 对每个子多边形，计算顶点的 y 坐标最大最小值，以高度场包围盒 y 坐标最小值为基准。
    • 将顶点 y 坐标最大最小值，转换成单元格索引 y' 表示，最小值为 [0, RC_SPAN_MAX_HEIGHT] ，最大值为 [最小值 + 1, RC_SPAN_MAX_HEIGHT] 。
    • 调用 addSpan 方法，将当前 x' 、z' 对应的单元格的 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 。 Nav2_1.png
  • 高度场添加跨度信息 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;
   }


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

过滤可行走表面

参考

CATALOG