Recast 学习记录之零：构建流程总览

序

最近准备把大神 Mikko 的导航网格库 Recastnavigation 的源码给好好看一下，并且把学习内容总结下来，记录成博客。

本文尽量不长篇地贴代码，而是用自己的理解将流程重新讲一遍，并且尽可能地配上图。

源码里读过的部分也添加了自己的理解和注释，上传到 Github 上了，可以参考 cybroxtu/recastnavigation-study 。

这里先看 Recast 构建导航网格部分的代码。本文以源码 RecastDemo/Source/Sample_SoloMesh.cpp 中的 Sample_SoloMesh::handleBuild 构建流程为例。

步骤总览

从 GUI 收集构建参数
光栅化三角形，构建高度场 rcHeightField
进一步对可行走表面进行筛选
将可行走表面划分出区域 region
根据区域确定出其轮廓 contour
根据轮廓将区域划分为凸多边形集合，构建初步的导航网格 rcPolyMesh
创建带有详细高度信息的导航网格 rcPolyMeshDetail
创建 dtNavMesh，供后续寻路处理

详细的解析可见：

Step 1. 初始化构建参数

构建参数存储于数据结构 rcConfig 中，其成员如下：

// [email protected]
struct rcConfig
{
    int width; // 体素空间在 x 轴上的长度
    int height; // 体素空间在 z 轴上的长度，height 这个名字有点儿迷惑性

    int tileSize; // tile 的长宽。对于 SoloMesh，这个值是 0
    int borderSize; // tile 边沿上的不可移动区域的大小

    float cs; // cell 的长宽
    float ch; // cell 的高度, 与 cs 共同构成了一个体素的大小

    // 输入 obj 文件里的 AABB 包围盒坐标
    // 用来表示模型文件里的哪一部分空间需要进行导航网格构建
    float bmin[3];
    float bmax[3];

    // 可行走表面的倾斜角度，用于在三角形光栅化时标记其表面的可行走性质
    float walkableSlopeAngle;

    int walkableHeight; // 最小可行走空间的高度
    int walkableClimb; // 最大可行走表面的高度差
    int walkableRadius; // 行走实体的半径，用于处理狭窄通道、边缘处收缩可行走范围等情况

    int maxEdgeLen; // 区域轮廓线上一条线段的最大长度
    float maxSimplificationError; // 区域轮廓线进行平滑去锯齿处理时，原始点离简化线的最大误差距离

    int minRegionArea; // 区域的最小面积，小于这个面积的区域需要被剔除
    int mergeRegionArea; // 小于这个面积的区域需要被合并成更大的区域

    int maxVertsPerPoly; // 从轮廓生成多边形时，一个多边形允许的最大顶点数

    float detailSampleDist; // 生成高度网格时的采样距离
    float detailSampleMaxError; // 生成高度网格时的最大误差距离
};

另外可以看看库作者 Mikko 的博文 Recast Settings Uncovered 。

Step 2. 输入三角形体素化

体素化流程包含有三个步骤：

rcCreateHeightfield: 为高度场数据结构分配空间。
rcMarkWalkableTriangles: 根据 walkableSlopeAngle 指定的倾斜角度，将输入模型文件里的三角形面标记出是否可以行走。
rcRasterizeTriangles: 将三角形面进行体素化，建立实心高度场 solid height filed，并根据 2 中得到的可行走标记，将对应的上表面 solid span 也标记为是否可以行走。

上面的步骤完成后，就把 obj 文件中由三角形面构成的模型转换为了由体素构成的模型。

Step 3. 筛选出可行走的表面

这一流程将进一步对体素的上表面进行检查，判断其是否可以行走。

rcFilterLowHangingWalkableObstacles: 对于仅高度有差异的两个相邻 span，如果下方 span 可以行走，且两者间的上表面高度差小于 walkableClimb，则认为上方的 span 也是可以行走的。如果上方 span 被标记为了不可行走，那么需要重新将其标记为可以行走。
rcFilterLedgeSpans: 将周围有较大高度差的 span 标记为不可行走区域。
rcFilterWalkableLowHeightSpans: 将标记为可行走、但是其上留出的空间高度小于 walkableHeight 的 span 标记为不可行走。

Step 4. 将可行走表面划分成不同的区域

rcBuildCompactHeightfield: 上面光栅化后得到的高度场是 solid span 集合，因为寻路不关心实心空间，只关心其上表面以及开放空间，这里将根据 solid span 生成对应的 open span，并且构建每个 span 与其邻接 span 的连接信息。
rcErodeWalkableArea: 根据 walkableRadius 将可行走区域与不可行走区域的交界处向内收缩对应的空间，避免在模型在边缘移动时部分穿模，以及避免寻路实体穿过比起直径小的狭窄通道。
rcMarkConvexPolyArea: 将凸多边形区域标记为用户自定义的可行走标记，用于区分不同的可行走类型，比如草地、河道、泥地等，后续可以对不同的行走标记设置不同的寻路开销。
将可行走区域划分为不同的区域，供后续按区域轮廓生成多边形: 只看最常用的分水岭算法，其包含两个步骤：
1. rcBuildDistanceField: 构建距离场，用于保存每一个 span 离不可行走区域的距离。
2. rcBuildRegions: 根据距离场数据，使用分水岭泛洪算法，将 span 表面划分为多个区域 (region)。

Step 5. 根据区域确定出其轮廓

rcBuildContours: 根据区域数据，将区域边缘的轮廓勾勒出来，并进行简化等处理。

Step 6. 根据轮廓将区域划分为凸多边形集合，构建初步的导航网格

rcBuildPolyMesh: 根据区域的轮廓顶点数据，将区域内部划分为数个凸多边形，并计算出多边形与多边形之间的连通关系。这时已经可以使用 A* 算法在网格上进行寻路计算了，但是因为轮廓线的简化和合并步骤，此时只有多边形顶点的高度数据是大致正确的，而多边形内部区域则损失了具体的高度数据。如果严格按照导航网格上的坐标设置位置，则会出现陷入地面和悬空等情况。

Step 7. 创建带有详细高度信息的导航网格

rcBuildPolyMeshDetail: 前面从轮廓生成多边形时，是先将区域轮廓线上 n 个节点连接成 n - 2 个三角形，然后对三角形进行合并操作得到最大顶点数为 maxVertsPerPoly 的凸多边形。这一步会根据原始高度，重建凸多边形内的三角形，在误差 detailSampleMaxError 内得到更精确的高度数据。

Step 8. 创建 `dtNavMesh`，供后续寻路处理

到这里，导航网格数据就已经创建完成了，通过 dtCreateNavMeshData 就能将所有数据存储到一块连续内存中，将其序列化保存到磁盘上，后续就可以直接加载导航网格数据用于初始化 dtNavMesh。