# 一、简介

开源地址：RecastNavigation
RecastNav 寻路 = 导航网格 + 寻路算法。
- Recast 负责根据输入的环境网格 (Mesh) 生成导航网格。-> 路径数据
- Detour 使用导航网格寻路。-> 路径算法
- RecastDemo 使用 Recast+Detour 的一个示例工程。
知乎大佬详解 Recast Navigation
知乎大佬详解 Recast Navigation

# 二、RecastDemo UML

Recast Demo

程序入口 Main 函数 - 初始化。
While 循环实现 Tick 功能。
构建 UI（文本、按钮...）。监听和处理输入。
输入环境网格，设置参数，生成导航网格（NavMesh）。
绘制显示。
调试和 Debug。

# 三、约定俗成

环境网格 (EnvMesh)：输入的源网格体数据，用于生成导航网格体数据。
导航网格 (NavMesh)：Recast 根据环境网格输出导航网格体数据，该网格数据用于寻路。

# 四、输入源 (环境网格)

RecastDemo 输入的环境网格是从 Obj 文件读取的。文件格式非常简单且两种数据，如下所示：
- 顶点数据：v 32.471557617 31.175949097 3.788104773
- 三角形索引数据：f 1 2 3
解析 Obj 文件，将顶点和索引数据存入下列数据结构中：
- float* rcMeshLoaderObj::m_verts; // 每三个组成一个顶点
- int* rcMeshLoaderObj::m_tris; // 每三个组成一个三角形索引
UE5 的环境网格是由引擎提供。

# 五、Recast 参数

单位 (Units)：Units are usually in voxels (vx) or world units (wu). The units for voxels, grid size, and cell size are all based on the values of #cs and #ch.
- vx：体素单位。这些单位全是 int 值，表示有多少个体素。体素的大小 width (XZ - 竖直面)/ 体素 height (Y - 高度)。
- wu：世界单位。
限制 (Limit)：数据值的限制范围。
坐标系：SDL 库 (Opengl) 是右手坐标系。
C++ 参数

// Specifies a configuration to use when performing Recast builds.
struct rcConfig
{
	/// The minimum/maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
	/// 环境Mesh中顶点XYZ的最大最小值构成的AABB包围盒，将环境都包含在内。
	/// 这个值也可以自定义，毕竟真实的游戏很复杂，有些区域不需要寻路，比如：水里、天空、不可到达的区域...
	float bmin[3]; 
	float bmax[3];

	/// The xz-plane/y-axis cell size/height to use for fields. [Limit: > 0] [Units: wu] 
	/// 体素细分单位。体素长宽高单位大小。
	float cs; // cell size -> 立方体XZ的大小 -> XZ平面正方形
	float ch; // cell height -> 立方体高度大小

	/// The width/height of the field along the x-axis/z-axis. [Limit: >= 0] [Units: vx]
	/// 将上面的AABB包围盒细分。将X轴细分为width块，将Z轴细分为height块。
	int width;  // X轴细分。浮点数向上取整。如：width = (fAABBMax_X - fAABBMin_X)/(cs + 0.5f)
	int height; // Z轴细分。
		    // 注意：Y轴没有被细分。
	
	/// The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
	/// 边界区域大小，这些边界区域不会生成导航网格。
	int borderSize;

	/// The width/height size of tile's on the xz-plane. [Limit: >= 0] [Units: vx]
	int tileSize;
	
	/// 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] 
	/// 行走半径。区域圆的半径大于该值时才可以行走。每个物体都有半径，行走物应该都有半径！[Limit: >=0]
	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] 
	/// 平面XZ最小可行走区域。
	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;
};

# 六、体素化

# 1. 概念

光栅化：将三角形转换为二维平面的像素格子。
体素化：将三角形转换为三维的立方体格子。

# 2. 效果图片

Voxelization

图 a 是三维模型，3D 美术师在 Maya 等软件中创建的三维网格体。
图 b-d 就是对图 a 的体素化，用一个一个立方体切割出来的体素模型。
RecastDemo 体素化图

# 3. 专有名词解释

![Recast Voxel 1](Recast-Voxel_1.png)

立方体由长宽高三个属性确定，体素也一样：CellSize (X) * CellHeight (Y) * CellSize (Z)
Cell：一个体素 (Voxel)。
偷天换日：XYZ 轴的精度被偷换了！常用的 XYZ 轴的精度为 1，现在体素化中 XYZ 以体素大小为精度 (Width\Height\Depth)
- World X = Width * cs; //cs->CellSize，表示 X 轴切割了 Width 份 cs 大小的单元 下面同理。-> 详情可见 Recast 参数和代码
- World Y = Height * ch; //ch->CellHeight
- World Z = Depth(Height_Z) * cs;
  // 注：不论是代码还是参考资料里面，Height 关键字都容易混肴
  // 因为 Height 在代码中被使用在 Z 方向上，而计算机图形、游戏引擎、相关资料以及部分代码的字里行间它又被使用在 Y 方向上！
  // 但计算机图形学和游戏引擎一直是 Y 表示高度，Z 表示深度！
  // 所以本篇文章 Z 轴的 Height_Z 使用 Depth，Y 轴使用 Height 来区分，相关代码也会特别标注是哪个轴向！
BoundsMax/BoundMin：AABB 包围盒，表示整个体素化的范围，该范围内的所有输入的环境网格体都会被体素化，生成导航网格。
Span：由一个或多个体素在竖直方向上的连续集合体。
SpanMax/SpanMin：Span 在 Y 轴上面的体素个数 CellNum = SpanMax - SpanMin
高度场 (rcHeightfield)：由 Width*Depth 个 Span** 二维指针组成，竖直串联所有的 Span * 对象。-> 链表
- 可以想象，XZ 平面每个格子都有一个头指针（一一对应），然后像路边烧烤串串一样，将 Span 都对象串联起来，只不过是竖直放置的。
- 体素化过程中只有一个高度场对象，用来保存 “串串” 的二维头指针。
- 为什么要用二维头指针？-> 这一串竖直方向上没有 Span 或者创建一个空 Span 作为头指针太浪费了！

# 4. 切割原理

二维三角形切割 - 三维的投影
- 首先 XZ 平面有一个三角形 OAB，然后先按 Z 轴横着切，再按 X 轴竖着切。 -> 切块的大小 = CellSize
- Z 轴第一刀将三角形切为两个多边形，一个是四边形 OCDB，一个是三角形 CAD。
- X 轴第一刀将四边形 OCDB 切为两个四边形，一个是 OCGE，一个是 EGDB；然后再将 CAD 切成了两个多边形，一个是三角形 CFG，一个是四边形 FADG。
- 所以 OCGE 就在产生了一个 Span，此时该 Span 的 X 轴的 Width 和 Z 轴的 Depth 都已经确定 (被切出来的)。
三维三角形切割 - 二维转到三维
- 那么 Y 轴的 SpanMax/SpanMin 呢？只有确定了 SpanMax/SpanMin，才能表示一个完整的 Span 立方体，才能知道竖直方向上有多少个体素！
- 其实代码里面并没有真正的切割 Y 轴 (没有调用切割函数 dividePoly)，我刚开始也很困惑 (因为我脑阔还在二维空间中)，直到我把那段代码理解之后，恍然大悟！
- Y 轴的 Height 其实在上面 XZ 轴切割的时候就已经可以算出来了！请看下图：
- 上图就是按照 XZ 轴切割后，一块 Span 和三角形的切割示例图。
- XZ 轴切割后是知道各个 Span 中多边形的顶点数据，比如上面示例红色立方体 Span 中的不规则五边形的五个顶点数据全部已知！
- 那么 SpanMax = 多边形所有顶点 Y 的最大值向上取整，SpanMin = 多边形所有顶点 Y 的最小值向下取整（取整单位为 CellHeight）。
切割代码

/// 体素化所有三角形
/// Rasterizes an indexed triangle mesh into the specified heightfield.
///
/// Spans will only be added for triangles that overlap the heightfield grid.
/// 
/// @see rcHeightfield
/// @ingroup recast
/// @param[in,out]	context				The build context to use during the operation.
/// @param[in]		verts				The vertices. [(x, y, z) * @p nv]
/// @param[in]		numVerts			The number of vertices. (unused) TODO (graham): Remove in next major release
/// @param[in]		tris				The triangle indices. [(vertA, vertB, vertC) * @p nt]
/// @param[in]		triAreaIDs			The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
/// @param[in]		numTris				The number of triangles.
/// @param[in,out]	heightfield			An initialized heightfield.
/// @param[in]		flagMergeThreshold	The distance where the walkable flag is favored over the non-walkable flag. 
///										[Limit: >= 0] [Units: vx]
/// @returns True if the operation completed successfully.
bool rcRasterizeTriangles(rcContext* context, const float* verts, int numVerts, const int* tris,
				const unsigned char* triAreaIDs, int numTris,
				rcHeightfield& heightfield, int flagMergeThreshold = 1)
{
	...	
	// 体素大小的倒数
	const float inverseCellSize = 1.0f / heightfield.cs;
	const float inverseCellHeight = 1.0f / heightfield.ch;
	
	// 遍历三角形，依次体素化
	for (int triIndex = 0; triIndex < numTris; ++triIndex)
	{
		const float* v0 = &verts[tris[triIndex * 3 + 0] * 3];
		const float* v1 = &verts[tris[triIndex * 3 + 1] * 3];
		const float* v2 = &verts[tris[triIndex * 3 + 2] * 3];
		// 体素化该三角形
		if (!rasterizeTri(v0, v1, v2, triAreaIDs[triIndex], heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold))
		{
			context->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
			return false;
		}
	}

	return true;
}




/// 体素化单个三角形
///	Rasterize a single triangle to the heightfield.
///
///	This code is extremely hot, so much care should be given to maintaining maximum perf here.
/// 
/// @param[in] 	v0					Triangle vertex 0
/// @param[in] 	v1					Triangle vertex 1
/// @param[in] 	v2					Triangle vertex 2
/// @param[in] 	areaID				The area ID to assign to the rasterized spans
/// @param[in] 	hf					Heightfield to rasterize into
/// @param[in] 	hfBBMin				The min extents of the heightfield bounding box
/// @param[in] 	hfBBMax				The max extents of the heightfield bounding box
/// @param[in] 	cellSize			The x and z axis size of a voxel in the heightfield
/// @param[in] 	inverseCellSize		1 / cellSize
/// @param[in] 	inverseCellHeight	1 / cellHeight
/// @param[in] 	flagMergeThreshold	The threshold in which area flags will be merged 
/// @returns true if the operation completes successfully.  false if there was an error adding spans to the heightfield.
static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
                         const unsigned char areaID, rcHeightfield& hf,
                         const float* hfBBMin, const float* hfBBMax,
                         const float cellSize, const float inverseCellSize, const float inverseCellHeight,
                         const int flagMergeThreshold)
{
	//////////////////////// 代码较长，精简主要步骤 ////////////////////////
	
	/// 计算三角形的AABB包围盒 -> 世界坐标
	// 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);
	
	/// 计算该三角形z方向上坐标 -> 世界坐标转体素坐标 -> z0和z1表示三角形在体素坐标内AABB包围盒在Z轴方向上的最大最小值！
	// Calculate the footprint of the triangle on the grid's z-axis
	int z0 = (int)((triBBMin[2] - hfBBMin[2]) * inverseCellSize);
	int z1 = (int)((triBBMax[2] - hfBBMin[2]) * inverseCellSize);
	/// 在Z轴上一刀一刀的横切
	for (int z = z0; z <= z1; ++z)
	{
		// 切割函数
		dividePoly(..., RC_AXIS_Z); // 枚举值RC_AXIS_Z表示按照Z轴切割
		
		/// 同z0和z1
		int x0 = (int)((minX - hfBBMin[0]) * inverseCellSize);
		int x1 = (int)((maxX - hfBBMin[0]) * inverseCellSize);
		/// 在X轴上一刀一刀的竖切
		for (int x = x0; x <= x1; ++x)
		{
			dividePoly(..., RC_AXIS_X);// 枚举值RC_AXIS_X表示按照X轴切割
			
			/// 遍历切割后的多边形顶点，求出顶点Y的最大最小值（spanMin/spanMax）
			// 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]);
			}
			/// 减去体素坐标的世界坐标原点，转为体素坐标 -> 但是精度还是世界坐标精度1
			spanMin -= hfBBMin[1];
			spanMax -= hfBBMin[1];
			
			/// 将spanMin/spanMax转为体素坐标精度
			// 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);
			
			/// 添加Span
			if (!addSpan(hf, x, z, spanMinCellIndex, spanMaxCellIndex, areaID, flagMergeThreshold))
			{
				return false;
			}
		}
	}
}




/// 按轴切割多边形
/// Divides a convex polygon of max 12 vertices into two convex polygons
/// across a separating axis.
/// 
/// @param[in]	inVerts			The input polygon vertices
/// @param[in]	inVertsCount	The number of input polygon vertices
/// @param[out]	outVerts1		Resulting polygon 1's vertices
/// @param[out]	outVerts1Count	The number of resulting polygon 1 vertices
/// @param[out]	outVerts2		Resulting polygon 2's vertices
/// @param[out]	outVerts2Count	The number of resulting polygon 2 vertices
/// @param[in]	axisOffset		THe offset along the specified axis
/// @param[in]	axis			The separating axis
static void dividePoly(const float* inVerts, int inVertsCount,
                       float* outVerts1, int* outVerts1Count,
                       float* outVerts2, int* outVerts2Count,
                       float axisOffset, rcAxis axis)
{
	/// 切割算法 -> 没有细看这部分源码 -> 而且这部分源码因为优化非常"好理解"
	/// 每条边都可以确定一个直线线段（两点确定一条直线）-> 可以求出直线方程
	/// 先判断相交情况，用线段的当前轴(axis)最大最小值和当前切割线(axisOffset)比大小，只有线段当前轴最小值<axisOffset<线段当前轴最大值才相交
	/// 相交后，将axisOffset带入直线方程求解就能得到交点

	/// 当前三角形和当前切割线的所有交点（最多只有两个[0-2]）
	/// 判断左右来区分切割后的两个多边形，同一边的就是同一个多边形！ -> 判断左右和判断相交一样，比较大小就可以了
	/// 返回切割后的两个多边形顶点outVerts1/outVerts2和数量outVerts1Count/outVerts2Count
}




/// 向高度场对象插入一个Span -> 链表操作
/// Adds a span to the heightfield.  If the new span overlaps existing spans,
/// it will merge the new span with the existing ones.
///
/// @param[in]	hf					Heightfield to add spans to
/// @param[in]	x					The new span's column cell x index
/// @param[in]	z					The new span's column cell z index
/// @param[in]	min					The new span's minimum cell index
/// @param[in]	max					The new span's maximum cell index
/// @param[in]	areaID				The new span's area type ID
/// @param[in]	flagMergeThreshold	How close two spans maximum extents need to be to merge area type IDs
static bool addSpan(rcHeightfield& hf,
                    const int x, const int z,
                    const unsigned short min, const unsigned short max,
                    const unsigned char areaID, const int flagMergeThreshold)
{
	/// 创建一个Span
	/// 在高度场中找到XZ平面对应的Cell链表头指针
	/// 按照高度从低到高依次遍历已有的Span
	/// 找到链表合适的位置，对于上下重叠的或者小于阈值的临近Span，就合并到新的Span，释放旧Span
	/// 插入新Span
}

# 七、筛选可行走 Span

根据 Recast 参数筛选出对应的 Span，并打上对应的 area id 标签。参数：可行走的高度、可攀爬高度...
参考知乎博主

# 八、CompactHeightfield

# 1. 概念

SolidSpan: 不可行走的空间 (Span)。 -> Heightfield
- Heightfield：高度场中每一个 cell 对象内是一个 span 的链表，span 表示的是玩家不可通过的实心体素。

CompactSpan(Open Span ): 与上面互补，可行走的空间区域。-> CompactHeightfield

CompactHeightfield：紧缩高度场由一个一个 rcCompactSpan 组成。

rcCompactSpan 的数据结构如下

/// Represents a span of unobstructed space within a compact heightfield.
struct rcCompactSpan
{
	/// 底部首个开始的SolidSpan -> Agent寻路的表面
	unsigned short y;				///< The lower extent of the span. (Measured from the heightfield's base.)
	unsigned short reg;			///< The id of the region the span belongs to. (Or zero if not in a region.)
	unsigned int con : 24;		///< Packed neighbor connection data.
	/// CompactSpan的高度，也就是以y开始**连续向上**由多少个**SolidSpan**组成
	unsigned int h : 8;			///< The height of the span.  (Measured from #y.)
};

注意：前文提到的都是 SolidSpan，后文提到的都是 CompactSpan！

# 2. 函数和原理

rcBuildCompactHeightfield 函数：乾坤颠倒。将 Heightfield 转为 CompactHeightfield，然后释放原来的 Heightfield (后面不会使用了)。
rcErodeWalkableArea 函数：根据可走行半径参数，标记靠近边界或障碍物的 CompactSpan 为不可走。
- 每个 CompactSpan 的都有一个 Area 属性标记（可走，不可走，草地，雪地，水域...），寻路时每个 agent 有一个 flag 与 area 对应，例如玩家的 flag 包含草地、雪地和水域，那么寻路路径可穿越这些 area，例如怪的 flag 包含草地、雪地，那么寻路时认为水域是阻挡物而绕开。
- Area 可由开发者扩展！

# 九、创建区域 (CompactRegion)

区域（region）是一组连续的 span，表示可走表面的范围。
函数 rcBuildRegions 为每个 CompactSpan 分配一个所属的 Region Id（即：rcCompactSpan::reg）。
Region 效果图：每块 Region 由不同的颜色区分，黑线代表相邻的 Region 连接可达

# 十、导航网格（三维到二维）

# 1. 步骤

取出 Region 轮廓线 Contours
- 函数 rcBuildContours：将 CompactHeightfield 转换为 ContourSet。根据 Span 的 Region 信息提取出轮廓线多边形和凸包处理。
根据 Contours 生成导航网格 PloyMesh
- 函数 rcBuildPolyMesh：生成导航导航网格，用于寻路算法！

# 2. 效果图

Raw Contours

# 下一章：寻路

导航网格已经生成 (Region)，后面就是用寻路算法在 Region 上寻路。

Navigation Recast

# 一、简介

# 二、RecastDemo UML

# 三、约定俗成

# 四、输入源 (环境网格)

# 五、Recast 参数

# 六、体素化

# 1. 概念

# 2. 效果图片

# 3. 专有名词解释

# 4. 切割原理

# 七、筛选可行走 Span

# 八、CompactHeightfield

# 1. 概念

# 2. 函数和原理

# 九、创建区域 (CompactRegion)

# 十、导航网格（三维到二维）

# 1. 步骤

# 2. 效果图

# 下一章：寻路

菜单系统系统

無題