RecastNavigation 之 Recast

0. 介绍

在实际应用中，导航网格是以邻接的凸多边形集合来表示的，因为在独立的凸多边形内部，可以保证任意两点直线可达。
而寻路算法的关键是通过算法找到一组凸多边形，这组多边形满足这样的条件：

1. 第一个和最后一个多边形包含了寻路的起始点和终点
2. 中间的多边形负责所有多边形的连通性

因此导航网格寻路可以粗略的分成两大部分：

1. 将 3D 场景转化为邻接的凸多边形集合
2. 在凸多边形集合上寻路

在 RecastNavigation 项目中， Recast 工程对应第一部分，Detour 工程对应第二部分，这里主要利用 RecastDemo 对 Recast 生成导航网格的流程进行介绍。
其整体流程大致分为 7 步：

1. load mesh & Initialize build config
2. Rasterize input polygon soup
3. Filter walkables surfaces
4. Partition walkable surface to simple regions
5. Trace and simplify region contours.
6. Build polygons mesh from contours
7. Create detail mesh which allows to access approximate height on each polygon

流程比较繁杂，接下来一步一步进行分析。

RecastNavigation 代码地址：https://github.com/recastnavigation/recastnavigation
RecastNavigation 版本：1.5.1

1. Load mesh & Initialize build config

这一步主要是生成导航网格的前置工作：

• 加载 3D 场景数据
• 生成构建导航网格的配置

1.1 加载 3D 场景数据

导航网格的生成首先依赖 3D 场景的数据，好比做菜的时候总得先有菜，RecastDemo 中提供了 3 种场景，其源数据为 obj 的文本文件（应该是通过 maya 之类的编辑器导出的），其格式大致如下：

f 191/191/191 192/190/192 188/185/188 187/188/187 
f 189/192/189 191/191/191 187/188/187 185/187/185 
v 12.915435 -2.799647 -13.547013
v 15.723457 -2.799647 -13.889110
v 12.915435 10.274025 -13.547013
v 16.034479 10.274025 -11.336161
vn -0.642934 -0.577350 -0.503291
vn 0.503291 -0.577350 -0.642934
vn -0.642934 0.577350 -0.503291
vn 0.503291 0.577350 -0.642934
vn 0.642934 0.577350 0.503291
vt 0.000000 0.000000
vt 0.000000 0.000000

RecastDemo 中采用 InputGemo::loadMesh 接口来解析文件，其主要解析 f 和 v 开头的数据，这两者是相辅相成的，v 表示顶点坐标（vertex） ，f 表示面（face），其格式通常为 3 个"v/vt/vn" 的索引形式组成, 比如 obj 文件中f 3/13/5 4/14/6 5/15/7 ，表示由第3、第13、第5 这三个顶点组成了一个三角平面,平面的纹理由第 4、第 14、第 6这三个纹理坐标形成，而这个平面的朝向是第 5、第 15、第 7这三个顶点的法向量的平均值决定的。关于 obj 文件的格式描述可以参考此处。
总体来说，RecastDemo 这里主要将场景数据的点和面加载解析，形成了一个个三角面，实际的场景可参考下图。

1.2 构建 Bounding volume hierarchy

读取完数据后，为了方便管理 3D 场景物体以及下一步的体素化操作，采用 Bounding volume hierarchy 的方式对场景物体进行管理。其思路就是将场景的空间划分为多块区域，然后用树状结构保存起来，如下图：

大致可以看出树和原场景包围盒的对应关系：根节点为全局的包围盒，依次划分，直到剩下一个独立的几何体作为一个叶子节点。
RecastDemo 中构建该树的接口为 InputGeom::rcCreateChunkyTriMesh ，其执行流程如下：

• 先遍历所有三角面（加载场景数据时保存的），计算每个三角面【投影】的包围盒（此处将问题转换为二维平面）
• 计算当前 3D 场景投影的包围盒，作为根节点
• 当前节点三角面的投影包围盒数量是否大于 256
  • 小于 256，则该节点作为叶子节点，并且返回
  • 如果三角面数量大于 256
    • 先计算当前这个节点空间的包围盒大小
    • 根据包围盒大小，算出 X 轴和 Y 轴的长度
    • 找出较长的（X/Y）轴，对该节点包围盒内的所有三角面包围盒进行（X/Y 轴）坐标排序
    • 将排序后的数组进行对半划分，继续递归处理两个区域

其接口参数和树结构体如下所示：

const float* verts;///输入的顶点集合
const int* tris;///输入的三角形集合
int ntris;///输入的三角形个数

///三角形在xz平面投影的包围盒
struct BoundsItem
{
    float bmin[2];
    float bmax[2];
    int i;///由于会对包围盒按坐标排序，id记录了这个包围盒对应的输入三角形的id
};

///BVH的节点
struct rcChunkyTriMeshNode
{
    float bmin[2];///包含区域内所有三角形的包围盒
    float bmax[2];
    int i;///i为正表示是叶子节点；i为负表示是非叶子节点，大小等于在数组内的覆盖范围
    int n;///节点内包含的三角形个数
};

///一棵BVH树
struct rcChunkyTriMesh
{
    rcChunkyTriMeshNode* nodes;///根节点
    int nnodes;///节点个数
    int* tris;///按区域划分排序后的三角形集合
    int ntris;///三角形个数
    int maxTrisPerChunk;///叶子节点最多包含的三角形数
}

1.3 配置初始化

主要列举一些比较重要的配置：

其中 Sample 选项提供了几种 Mesh：

• Solo Mesh
• Tile Mesh
• Temp Obstacles

其中 Temp Obstacles 是在 Tile Mesh 的基础上做了动态阻挡的优化，NavMesh 的生成主要还是区分为 Solo Mesh 和 Tile Mesh，这两者的主要区别在于，Solo Mesh 每次生成的时候，都是对整块地图进行生成导航网格，而 Tile Mesh 可以按另一个配置 TileSize ，将地图划分成多个 Tile 块，然后对单个 Tile 进行生成导航网格。

2. Rasterize input polygon soup

核心接口如下：

/// @par
///
/// Spans will only be added for triangles that overlap the heightfield grid.
///
/// @see rcHeightfield
bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/,
						  const int* tris, const unsigned char* areas, const int nt,
						  rcHeightfield& solid, const int flagMergeThr)

由于这里选择的是 TileMesh，接下来需要对所有 Tile 中的三角面进行体素化，创建高度场等操作，这里主要分为如下操作：

• 创建高度场
• 找到 Tile 中的三角面，标记其是否可以行走
• 对三角面执行体素化，将体素格子合并为 Span 加入高度场

2.1 基础概念

由于体素化操作会将体素盒子合并为 Span 并且加入到高度场中，因此这里先对这几个名词进行简单介绍

体素盒子（Voxel）：

根据配置的参数在空间中画出3维网格，3维网格的一个单元就是一个体素盒子（配置中的 Cell Size 表示盒子在 XZ 轴的长度，Cell Height 表示盒子的高度）

区间（Span）：

一列（xz平面投影相同）【连续体素】盒子，由 rcSpan 这个结构体来表示，smin 和 smax 表示【连续体素】的最低 y 坐标和最高 y 坐标（底面和顶面），next 指针实现了一个链表，方便管理投影相同的所有区间（区间与区域之前不连续），xz 的坐标记录在高度场中。

struct rcSpan
{
    unsigned int smin : RC_SPAN_HEIGHT_BITS; ///< The lower limit of the span. [Limit: < #smax]
    unsigned int smax : RC_SPAN_HEIGHT_BITS; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]
    unsigned int area : 6;                   ///< The area id assigned to the span.
    rcSpan* next;                            ///< The next span higher up in column.
};

包围盒

通常说某个物体的包围盒，即指为包含该物体，且边平行于坐标轴的最小六面体

坐标轴

如下

高度场（HeightFields）

高度场是容纳了所有地图元素的一个容器，其维护了一个二维数组（表示 XZ 平面），数组元素是在 XZ 平面投影相同的 span 的链表，大致如下：

struct rcHeightfield
{
    rcHeightfield();
    ~rcHeightfield();

    int width;          ///< The width of the heightfield. (Along the x-axis in cell units.)
    int height;         ///< The height of the heightfield. (Along the z-axis in cell units.)
    float bmin[3];      ///< The minimum bounds in world space. [(x, y, z)]
    float bmax[3];      ///< The maximum bounds in world space. [(x, y, z)]
    float cs;           ///< The size of each cell. (On the xz-plane.)
    float ch;           ///< The height of each cell. (The minimum increment along the y-axis.)
    rcSpan** spans;     ///< Heightfield of spans (width*height).
    rcSpanPool* pools;  ///< Linked list of span pools.
    rcSpan* freelist;   ///< The next free span.

private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcHeightfield(const rcHeightfield&);
    rcHeightfield& operator=(const rcHeightfield&);
};

2.2 过滤掉不可行走的三角面

首先我们需要找到与当前 Tile 相交的三角面，可以借助到前面构建的 BVH 结构，BVH 的结构如下：

///BVH的节点
struct rcChunkyTriMeshNode
{
    float bmin[2];///包含区域内所有三角形的包围盒
    float bmax[2];
    int i;///i为正表示是叶子节点；i为负表示是非叶子节点，大小等于在数组内的覆盖范围
    int n;///节点内包含的三角形个数
};

///一棵BVH树
struct rcChunkyTriMesh
{
    rcChunkyTriMeshNode* nodes;///根节点
    int nnodes;///节点个数
    int* tris;///按区域划分排序后的三角形集合
    int ntris;///三角形个数
    int maxTrisPerChunk;///叶子节点最多包含的三角形数
}

我们只需要遍历 BVH 树，判断当前节点的【投影】包围盒与 Tile 的 【投影】包围盒是否相交，以此筛选满足条件的节点，这样比遍历所有三角面要快的多。
找到符合条件的节点后，遍历所有节点内的三角面，找到可以行走的三角面。这里主要根据配置的 Max Slope ，该值表示 agent 可以行走的斜坡的最大角度是多少，当三角面的角度大于该值，表示 agent 也无法行走上去，因此可以剔除掉该三角面。

2.3 体素化三角面（rasterizeTri）

体素化三角面主要遍历所有三角面转换成空间内的体素集，这里将地图的信息从三角面再拆分到体素盒子。这里针对体素化单个三角面的流程进行介绍。

• 找到三角形的 AABB 包围盒（三维空间的包围盒，被定义为包含该对象，且边平行于坐标轴的最小六面体）
• 计算三角形的高度
• 按投影的 XZ 平面切割三角形（每次切割的单位长度都是一个 Cell Size，也就是一个体素盒子的长度）

• 计算切割后的格子中，点坐标的最高值和最小值（XZ切割后与面的相交点坐标），作为 Span 的高度。
• 在同个 XZ 坐标下的 Span 如果间距小于一定值会被合并，且如果其中一个 Span 为可行走的，则合并后的 Span 也为可行走的。Span 链表都是按高度从低到高排序的, Span 有多个邻居时,取高度最高的,

体素化后的三角面效果大致如下：

最终建立的高度场效果如下：

每个 Span XZ 长度固定（Cell Size）, Y 轴方向包含一个最大值和最小值, 同一个 XZ 坐标会有多个span，同一个 XZ 坐标处的所有 Span 形成一个链表,并且按高度排序(从小到大)

3. Filter walkables surfaces

过滤可行走表面，主要分为 3 步：

• 过滤可行走的障碍物
• 过滤四周都无法行走的 Span
• 过滤同个 XZ 坐标下，Span 之间高度差较小的 Span

不可行走的 Span 都会标记为 RC_NULL_AREA

3.1 标记同个 XZ 坐标下可攀爬的 Span（rcFilterLowHangingWalkableObstacles）

根据同一个 XZ 坐标不同 Span 之间,如果它们的距离小于 walkableClimb ,并且下面的 Span可走,则把上面的 Span 也标记成可走, 即处理台阶楼梯之类的情形

3.2 过滤周围高度较低的 Span（rcFilterLedgeSpans）

和周围的 Span 比较，Span 的高度差是否大于 Agent 高度，小于 Agent 高度，说明不够高，无法行走，如果 Span 的 4 个方向都不满足,该 Span 也会被判断定为不能走。如下

3.3 过滤开放空间高度过小的 Span（rcFilterWalkableLowHeightSpans）

判断当前格子所形成的空间，是否足够高（> Agent 高度），不够高也判断为不可走，如下图所示，同一个 XZ 坐标上，一系列的 Span 之间的高度差要足够

4. Partition walkable surface to simple regions

这一步是生成导航网格中最复杂的一步，处理比较多。

4.1 将高度场转换为紧缩高度场（rcBuildCompactHeightfield）

高度场中的 Span 是三角面的体素集，是【实心】的部分，而紧缩高度场实际上就是将【实心】区域之间的【空心】区域取出来，每个【紧缩空间】的起始位置是一个 【实心空间】的可行走顶部，高度是【空心】区域的连续高度。大致如下所示，CompactSpan 就是我们的 【紧缩空间】，因此【紧缩高度场】其实就是【紧缩空间】的集合。

理论上【实心区域】实际上只需要其表面，主要还是为了获取【空心区域】而构建的。

获取到所有 CompactSpan 之后，再计算每个 CompactSpan 与它的 Neighbor Compact Span 的【联通性】（XZ 平面下，上下左右 4 个方向）。判断【联通性】的条件其实与前面过滤可行走 Span 的操作有些类似，主要有两个条件，如下所示：

一个 CompactSpan 与周围 Neighbor Compact Span【联通性】数据保存主要存放在 rcCompactSpan 结构中的 con 字段，该字段长 24 bit，每个方向占 6 bit，比如 con 字段的二进制值为 000001 000010 000000 000100 时，意义如下：

1. 左方向，该 Span 与 layer id 为 1 的 Span 连通
2. 上方向，该 Span 与 layer id 为 2 的 Span 连通
3. 右方向，该 Span 无连通 Span
4. 下方向，该 Span 与 layer id 为 4 的 Span 连通

layer id 指在该 XZ 坐标下，可能有多个 Compact Span，因此 layer id 用来区分是第几层的 Span。

对于这 4 个方向，recast 也有自身的定义

// 对于 (0,0) 的坐标														        (1,0)                          
Direction 0 = (-1, 0) 左                     (-1,0)   (0,0)   (0,1)
Direction 1 = (0, 1)	右											         (0,-1)
Direction 2 = (1, 0)	上											               
Direction 3 = (0, -1) 下					

转换为紧缩高度场后，其数据结构定义有所变化。

• 【紧缩高度场】保存了每个 XZ 坐标的格子（数组保存），定义为 struct CompactCell ，主要记录该 XZ 坐标上有几个 CompactSpan，其次可以通过数组索引快速定位到某个 Span
• 【高度场】中的 struct rcSpan 采用【链表】结构保存，而【紧缩高度场】则采用【数组】结构保存 struct rcCompactSpan，这样索引的效率也更快，假设索引坐标为 （1,2）上的第 N 个 CompactSpan，只需要 （1+2*width）+ N 即可直接得到索引

紧缩高度场的数据结构完整定义如下：

/// Provides information on the content of a cell column in a compact heightfield. 
struct rcCompactCell
{
	unsigned int index : 24;	///< Index to the first span in the column. XZ 平面下的坐标，参考右图 					
	unsigned int count : 8;		///< Number of spans in the column. 8 位，理论上不会超过 256 个 Span					      
};							    ///  XZ 平面投影下，一个格子就是一个 Cell															     
                                ///  -------------																 
                                ///	 |1 |2 |3 |4 |
                                ///  -------------
                                ///  |5 |6 |7 |8 |
                                ///  -------------

/// Represents a span of unobstructed space within a compact heightfield.
struct rcCompactSpan
{
	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.    与 Neighbor Span 的连通性，这里 24bit，每 6 bit 一个方向（）
	unsigned int h : 8;			///< The height of the span.  (Measured from #y.)
};

/// A compact, static heightfield representing unobstructed space.
/// @ingroup recast
struct rcCompactHeightfield
{
    // some define 
	float bmin[3];				///< The minimum bounds in world space. [(x, y, z)]
	float bmax[3];				///< The maximum bounds in world space. [(x, y, z)]
	float cs;					///< The size of each cell. (On the xz-plane.)
	float ch;					///< The height of each cell. (The minimum increment along the y-axis.)
	rcCompactCell* cells;		///< Array of cells. [Size: #width*#height]                          Cell 的合集，这里采用一维数组表示
	rcCompactSpan* spans;		///< Array of spans. [Size: #spanCount]							     所有数组的合集，这里采用一维数组表示
	unsigned short* dist;		///< Array containing border distance data. [Size: #spanCount]       记录距离场
	unsigned char* areas;		///< Array containing area id data. [Size: #spanCount]               记录区域是否可行走，或者草地山地等情况
};

CompactSpan的集合存放在 rcCompactHeightfield.spans 。

4.2 用玩家模型半径修剪可行走区域边界（rcErodeWalkableArea）

这里主要对边界区域进行裁剪，目的主要是为了让玩家模型和边界保留一定距离（防止贴着墙走，穿模到墙内），这里主要需要如下操作（现在开始这里的 Span 均指 CompactSpan）：

• 筛选【边界 Span】，Span 需要满足 【Neighbor Span 数量小于 4】（比如地图边界或者在柱子旁） 条件
• 新增一个 dist 整型数组（长度为 Span 的数量），记录可行走 Span 与上述筛选出来的 Span 的距离（单位是体素盒子），第一步筛选出来的 Span 的 dist 值均设置为 0，其他 Span 默认值为 255
• 分【两次】遍历，第一次从左下角到右上角遍历 XZ 平面每个格子的 Span ，用当前 Span 下半部分的 4 个格子更新 dist 数组（比较格子与 Span 的大小，取 min 值作为 dist 值），第二次从右上角向左下角遍历 XZ 平面每个格子，用当前 Span 上半部分的 4 个格子更新 dist 数组
• 遍历 dist 数组，将对应 Span 的 dist 距离小于（角色半径 / Cell Size）的 Span 都设置为不可行走

4.3 自定义区域（可选功能）

目前为止，其实只有 2 种 area id，可行走和不可行走，RecastDemo 提供了一种功能，通过射线绘制多个点，形成多面体，多面体包围的区域会被设置为对应的 area，如下图，不同区域包围的 voxel 颜色不一样（不同颜色表示不同的 area id）

主要通过 RecastArea::rcMarkConvexPolyArea 接口进行设置，该功能为可选功能，这里只做简要介绍。

4.4 对紧缩高度场进行区域划分 构建距离场

在对区域进行划分之前，需要构建距离场，其步骤与 4.2 用玩家模型半径修剪可行走区域边界 中构建的 dist 数组基本一致，唯一的区别是对 【非边界 Span】的定义，前者需要前后左右 4 个方向都存在连通邻居，而现在还有一个额外条件，连通邻居的 area id 也需要与当前 Span 的 area id 相同。

模糊降噪处理

距离场的 dist 数组构建完成之后，接下来对 dist 数组进行模糊降噪处理，具体做法是：
遍历 Span 的 8 个邻居 Span，合计 9 个 Span，(dist[1] + ... dist[9]) / 9，当某个邻居不连通时，则用自身的 Dist 值补上。然后将计算出来的值作为当前 Span 新的 Dist 值。

区域划分

Recast 中提供的区域划分算法主要分为三种：

1. 分水岭(watershed) :recast默认算法，效果好，速度慢。
2. Monotone：速度快。但是生成的 Region 可能会又细又长，效果一般。
3. layers：类同monotone，只是区域在生成过程中不会有叠层(不会跨相同x、z坐标的多个y坐标体素)

这里只针对默认的分水岭算法介绍。大致流程如下：

• 首先对当前区域根据前面构建的距离进行划分，默认情况下如果区域过大（距离场中最大的距离 maxDist > 16），会划分为 maxDist / 16 次进行处理

• 选定好区域之后，对区域内的 Span 进一步划分，拆分到 8 个 数组中（这里的拆分根据距离来，如 dist 值为 0~2 的存放到一个数组，2~4 为一个数组，以此类推）
• 首先对最中心的区域（距离最远的那个数组）先调用 floodRegion 进行注水，floodRegion 函数做的事情：以一个 Span 作为起始点，按 4 邻域泛洪填充它所能扩展到的区域（填充操作就是给 Span 设置 Region id），每次处理新的节点时，会先判断它的 8 个邻接节点是否已经有了更早的填充标记，如果有，则说明当前节点处于区域相交处，先跳过该节点
• 接着遍历下一个数组，先检查能否通过 expandRegion 合并到之前的区域中，合并条件是两个 Span 是否有相同的 area_id （目前来看除了不能行走的区域，area id 应该都是相同的），有则合并
• expandRegion 完毕后检查有没有 Span 仍然没有 region id，如果有，说明 area id 不一样，再对其进行 floodRegion 注水操作
• 以此类推，直到所有区域的数组遍历操作完毕，区域也就划分完了

这里附上一张参考图片（来源）：

5. Trace and simplify region contours

这一步主要从体素面转换为多个顶点集合（即从上一步中划分出来的区域，将其简化成轮廓），同时对区域进行简化，较小的区域合并到其他区域（如果可以合并的话）。

5.1 合并较小的 Region

• 先获取每个 Region 的邻接 Region
• 对于 Region 中 Span 数量小于 minRegionArea 配置值的，认为该 Region 需要 Merge 到其他 Region
• 遍历需要 Merge 的 Region 的邻接 Region，检查能否合并，能则合并。假如对 region a 合并到 region b ，合并的前提需要 b 没有 merge 过其他 region。

5.2 寻找 Region 之间相邻的 Span

遍历紧缩高度场中的 Span，根据 Region id（区域标记）求出每个 span与周围相邻 Span 的区域关系，用一个 4 位的 2 进制数来表示，如果相邻 Span 为同个 Region，则对应的标记记为 0，这样最后得到的 flag 若为0，则表示是一个区域内部的span (4 面都是同一个 Region)，否则就是一个区域边界上的 span

5.3 获取 Region 边界的轮廓顶点集（walkContour）

前面已经获取到所有 Region 之间相邻的 Span，接下来遍历 Span，具体流程如下：

• 以一个边界span作为起始位置，【顺时针方向】判断它的4条边：
• 若当前边是区域分界边，则将边的一个顶点加入到轮廓顶点集中，并继续判断下一条边
• 若当前边不是区域分界边，则移动到与这条边相邻的 Span中（这个 Span 是在同一个区域内），重新判断新的 Span的边（重新顺时针方向依次判断）

如下图

5.4 简化轮廓顶点集（simplifyContour）

简化的目的是使用尽可能少的直线段来逼近带毛刺的边界。整个简化过程如下：

• 左下角和右上角顶点作为初始轮廓
• 对于轮廓线段，遍历线段中间的其它顶点，找到偏离线段最远的顶点，如果偏离距离大于指定值，则将该顶点加入轮廓
• 一直迭代，直到所有顶点与轮廓的距离在指定值内

5.5 合并轮廓中的空洞

可能出现如下情况，轮廓中出现一个空洞（空洞其实是另一个轮廓），这种需要将其合并为一个轮廓，以下图为例：

• 首先找到空洞的左下角顶点 A1
• 将轮廓 B 的 4 个顶点都与 A1 相连，形成 4 条线段
• 去掉所有与空洞相交的线段，此时剩下 B1-A1，B3-A1，B4-A1 三条线段
• 选择最短的线，至此轮廓的顶点序列从 B1 B2 B3 B4 变为 B1 B2 B3 B4 A1 A3 A4 A2

6. Build polygons mesh from contours

我们需要将顶点集组成的多边形转换成凸多边形（凸多边形可以保证内部任意两点均可达），主要步骤如下：

• 先进行三角剖分，三角形为最简单的凸多边形
• 三角形合并多新的凸多边形（合并可以提升寻路的效率，减少了需要检索的凸多边形）
• 计算凸多边形的邻接关系

6.1 三角剖分

Recast 中采用了一种叫做 EarClipping 的算法进行裁剪，其主要接口为 static int triangulate(int n, const int* verts, int* indices, int* tris)。
首先有一个【耳尖】的定义：该顶点是一个凸点，且左右顶点相连的对角线与其他边不相交，比如有 v1 v2 v3 连续顶点，v1 和 v3 对角线不与其他边相交，v2 为凸点，则 v2 为耳尖。如下图：

6.2 凸多边形合并

为了提升效率，这里再将多边形进行合并，合并的条件如下：

• 首先两个多边形需要邻接，有公共边
• 合并后公共边的两个顶点需要为凸点（不然又变成了凹多边形）

参考下图：

6.3 凸多边形邻接关系

先得到所有多边形的边，用 链式前向星 的方式存起来（每个点记录以它为起始点的边），然后遍历所有边，对每条边设置以它为公共边的多边形的邻接信息，邻接信息是跟多边形的顶点信息存在一起的，在 rcPolyMesh这个结构体里，每个区域轮廓对应一个 rcPolyMesh，内部包含了这个轮廓内的所有凸多边形

struct rcPolyMesh
{
    unsigned short* verts;  ///所有多边形的顶点，注意这里顶点的坐标不是实际坐标，而是网格坐标
    unsigned short* polys;  ///所有凸多边形的信息
    ///polys数组长度为 多边形数量maxpolys*多边形最大顶点数nvp
    ///对于每个多边形，前nvp个数存顶点id，后nvp个数存与它相邻的多边形id（n个顶点最多与n个多边形相邻）
};

至此，基本完成了可以支撑寻路的的 Mesh 结构，但是仍存在一些问题，参考第七步

7. Create detail mesh which allows to access approximate height on each polygon

这一步的主要接口如下：

/// @par
///
/// See the #rcConfig documentation for more information on the configuration parameters.
///
/// @see rcAllocPolyMeshDetail, rcPolyMesh, rcCompactHeightfield, rcPolyMeshDetail, rcConfig
bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
						   const float sampleDist, const float sampleMaxError,
						   rcPolyMeshDetail& dmesh)

这一步事实上是可选的，理论上第6步输出的结果已经可以支持寻路算法了，但是第六步生产的 Mesh 会有一种情况，如下：

轮廓包围的区域，中间高，四周低，生产的 PolyMesh 与实际的地表高度并不匹配，因此这里需要加入高度相关的计算对其进行修整，将轮廓高度差距过大的部分再进行裁剪成更精细的多边形。

7.1 获取多边形的高度（getHeightData）

遍历所有的多边形，每个多边形都按 Span 来细分多边形的高度，多边形在 XZ 格子内的高度被记为该格子上与多边形 Region id 相同的 Span的高度（Region id 需要一致，同个 XZ 格子中有可能存在多个 Span）

7.2 多边形轮廓修正

• 先对多边形的每条边按一定距离裁剪成 N 段，然后对每个裁剪的点进行判断，其高度与实际的高度差距是否超过一定值，如果超过，则新增一个新的轮廓点到其实际高度上，如下图：

• 对新的轮廓进行三角化（三角化的方式跟 6.1 基本一致）
  • 先找到轮廓中对角线最短的【耳尖】，做一次【划分】
  • 【划分】就是以这个【耳尖】为中心，判断新的左【耳尖】和右【耳尖】哪个的对角线更短，取更短的再做一次划分
  • 更新左右边界（会把当前的【耳尖】移出计算），重复第二步，直到三角化完成

7.3 多边形内部修正

多边形内部修正的方式基本也是 采样 -> 找出高度差大过一定值的点 -> 三角剖分 -> 重新采样 -> 找出高度差大过一定值的点 -> ...

• 设置采样点（按 XZ 坐标中设置）
• 取采样点中偏离多边形网格最大的点，用这个点对当前网格做一次三角剖分
• 重复步骤 2，直到所有采样点都在偏离的允许范围内，或者点集超过上限

7.4 效果

8. 总结

总体的流程如下：

总体来说就是将输入的三角面过滤出可行走的表面，然后对其进行区域划分（主要根据距离），收集区域的轮廓顶点集进行三角剖分，转换成可以寻路用的凸多边形，最后对凸多边形的高度进行修正（可跳过该步骤）

9. 参考资料

• 从零开始学习导航网格
• recastnavigation源码解析
• recast navigation navmesh导航网格算法源码分析

关于动态阻挡的处理，可以参考 动态阻挡的处理