Recast 学习记录之三：划分区域

序

本文根据 Sample_SoloMesh::handleBuild 中的 Step 4. Partition walkable surface to simple regions 进行源码解析。

前面 Recast 已经将三角形面体素化为了高度场，并对可行走表面进行了进一步的筛选。这一步要做的就是将实心高度场（solid heightfield）转换到开放高度场（open heightfield），然后将可行走的体素表面经过一定处理后，划分为多个区域（region）。因时间关系，这里先只看分水岭算法，其它两种划分算法以后有时间再研究。

一共有五个步骤：

1. rcBuildCompactHeightfield: 将实心高度场转换到开放高度场。
2. rcErodeWalkableArea: 根据 walkableRadius 将可行走区域边界进行一定的收缩
3. rcMarkConvexPolyArea: 将凸多边形区域标记为用户自定义的可行走标记
4. rcBuildDistanceField: 构建距离场
5. rcBuildRegions: 分水岭算法划分区域

前面的实心高度场数据结构是 rcHeightField，因为后续处理关心的不是实心部分，而是空心的部分，所以这里将转换为代表 open span 的高度场，Recast 称其为 rcCompactHeightfield，因为其中的数据经过了一定程度上的压缩处理。基本数据结构如下：

// @Recast.h

/// Provides information on the content of a cell column in a compact heightfield. 
// 高度场内的一个格子
struct rcCompactCell
{
    unsigned int index : 24;        // 格子内第一个 span 在 rcCompactHeightfield::spans 数组中的序号
                                    // 占 24 位，同一个格子内 span 的序号是递增的
    unsigned int count : 8;         // 格子内 span 的数量，占 8 位，也就是一个格子内最多只能有 255 个 span
};

/// Represents a span of unobstructed space within a compact heightfield.
// 代表一个 open span
struct rcCompactSpan
{
    unsigned short y;               // span 的起始 y 坐标
    unsigned short reg;             // span 所属的区域 id，0 代表不在任何一个区域内
    unsigned int con : 24;          // 用于存储四方向 [0, 4) 的邻接关系，每个方向 6 位
                                    // 存连通的邻接 span 的序号相对于隔壁格子起始 span 序号的差值
                                    // 最大值 RC_NOT_CONNECTED (0x3F/63) 代表这个方向不连通
    unsigned int h : 8;             // span 在 y 轴上延伸的高度 [y, y + h)，最大为 255
};

/// A compact, static heightfield representing unobstructed space.
// 开放空间高度场
struct rcCompactHeightfield
{
    rcCompactHeightfield();
    ~rcCompactHeightfield();
    int width;                      // 高度场在 x 轴上的格子数量
    int height;                     // 高度场在 z 轴上的格子数量
    int spanCount;                  // 高度场内的 open span 总数
    int walkableHeight;             //
    int walkableClimb;              //
    int borderSize;                 // 高度场 AABB 包围盒的边框大小
    unsigned short maxDistance;     // 距离场内的最大距离
    unsigned short maxRegions;      // 最大的 reg id 序号
    float bmin[3];                  // 距离场 AABB 包围盒的最小坐标
    float bmax[3];                  // 距离场 AABB 包围盒的最大坐标
    float cs;                       // cellSize
    float ch;                       // cellHeight
    rcCompactCell* cells;           // 格子数组
    rcCompactSpan* spans;           // open span 数组
    unsigned short* dist;           // 距离场，用于存储 span 到不可行走边界的距离
    unsigned char* areas;           // 存储 span 的可行走标记 area id 的数组
};

rcBuildCompactHeightfield

这个函数为 rcCompactHeightfield 分配空间，将 rcHeightfield 的 solid span (rcSpan) 转换为 open span (rcCompactSpan)，并且根据一个 span 与其四方向邻接 span 的底部高度差（注意现在是 open span 了，底部高度就是之前 solid span 的顶部高度）是否在 walkableHeight 以内来建立邻接信息。

注意这里的邻接信息只保存一个邻接方向上，从低到高第一个可达的邻接 span 的序号与邻接格子第一个 span 序号的差值或者说偏移。

从 rcCompactSpan 的 unsigned int con : 24; 与 rcSetCon 可以看到，一共 24 位，四个邻接方向，每个方向的序号偏移占 6 位。而 RC_NOT_CONNECTED(63) 代表该方向不可达。

rcErodeWalkableArea: 根据 walkableRadius 将可行走区域边界进行一定的收缩

这个函数建立了一个临时的距离场数组 dist，首先将不可行走 span、有不连通邻居的 span 标记距离为 0。然后通过对高度场格子的由左上到右下、右下到左上的两次遍历，计算出每一个可行走 span 与不可行走 span、不连通 span 的最小距离。

为什么要分两次遍历？因为第一次正向遍历时，当前格子的左、左上、上、右上四个方向的格子已经被处理过了，而左下、下、右下、右边依旧是未处理的格子，其中邻接 span 距离不能用来计算当前 span 的最小距离。所以要先从左上向右下遍历一次，这一次只根据已经处理过的左、左上、上、右上四个方向的格子来计算当前 span 的最小距离。然后再从右下到左上处理一次，这次只根据左下、下、右下、右四个方向的格子来计算当前 span 的最小距离。两次遍历确保所有格子的距离都是最小的。

最后再遍历距离数组 dist，根据寻路实体的半径阈值 radius*2，判断一个 span 是否应该被标记为不可行走。注意这里乘以了 2，而前面计算最小距离的遍历对于横竖四个邻接方向的距离是加了 2，而斜向的 span 距离则是加了 3。因为横竖向格子的坐标距离其实是1，斜向应该是，所以猜测是为了省掉浮点计算和开根计算，直接乘以 2 ，将横竖和斜向的距离按 2 和 3 （）来进行计算了，所以 radius 才需要乘以 2。

这个步骤完成后，可以达成的效果：

1. 寻路实体在边墙边寻路时，不会穿模；
2. 宽度小于 walkableRadius 的狭小通道不允许通过；

注意就算 rcFilterLedgeSpans 没开启，这个函数依旧会在悬崖边缘生成不可行走区域。

如果 rcFilterLedgeSpans 开启了，那么该函数可能会导致悬崖边缘额外向内收缩一个格子的距离。

开启 rcFilterLedgeSpans：

关闭 rcFilterLedgeSpans：

rcMarkConvexPolyArea: 将凸多边形区域标记为用户自定义的可行走标记

这个是将用户自定义的凸多边形区域内的可行走 span 标记为指定的 area id。

函数逻辑比较简单，遍历所有 span，先判断是否在凸多边形包围盒内，然后进一步判断是否在凸多边形内，如果都为真，则将 span 标记为指定的 area id。

在 Recast 中，所有的不可行走 span 的 area 都为 RC_NULL_AREA(0)，非 0 都代表可行走区域，默认的可行走 area id 为 RC_WALKABLE_AREA(63)，用户可以将一些区域自定义为其它的 id。这些 id 将会影响区域 region 的划分，也会影响到最终的导航网格的形状，并且用户可以通过 dtQueryFilter::setAreaCost 为指定 area id 设置寻路开销。

rcBuildDistanceField: 构建距离场

calculateDistanceField

和前面 rcErodeWalkableArea 里建立距离场的代码大同小异，唯一的几点区别：

1. 距离数组的数据类型前者为 unsigned char，后者为 unsigned short；
2. 前者初始化距离数组时，对于不可行走区域都初始化为 0，而后者是走统一逻辑，判断四方向邻接 span 的 area id 是否一致。

所以，此处建立的距离场，对于不可行走区域内部也是要计算出距离的。

前者计算出的距离场，计算的是可行走 span 距离一切不可行走 span 的最小距离；

后者计算出的距离场，计算的是所有 span 距离可行走与不可行走发生变化的边界处的最小距离。

看起来后者是可以兼容前者的，两处计算应该可以省掉一个。

boxBlur

距离场构建完成后，其中的值还比较粗糙，不够平顺，不利于后面的区域划分，所以 Recast 使用 boxBlur 对距离场内的距离值进行一次平滑处理。

boxBlur 就是方框模糊算法，用于将一个 span 对应的距离值，修改为其九宫格范围内的平均值。

入参 thr 是固定的 1，函数开头便将其乘以了 2。如果一个 span 的距离值小于 thr，则将其距离直接修改为 thr，不再进行均值计算。

而前面 calculateDistanceField 得到的距离场里，边缘 span 的距离是 0，横 竖、斜向的距离增量分别是 2、3。所以最小的距离值应该是 0、2，不会有 1，这一步会将所有 0 距离的 span 都修改为 2，有什么意义呢？

因为要计算 9 个 span 的距离总值，所以如果八方向里有任一方向上不连通，则直接加上当前 span 的距离值。

最后的 dst[i] = (unsigned short)((d+5)/9) 这里 +5 是为了向上取整。

我分别测试了开启和关闭 boxBlur 后生成的 Compact Distance，却并没有发现肉眼可见的区别，可能是因为试所用的 obj 文件地形简单，体现不出来平滑效果吧。

生成的距离场长这个样子：

其中颜色越浅代表离边界越远，颜色越深代表离边界越近。

rcBuildRegions

TODO 分水岭算法

分水岭算法有兴趣可以看一下 图像分割的经典算法：分水岭算法

rcBuildRegions 这个函数稍微绕一点儿，因为用了辅助结构 lvlStacks 来进行遍历。

现在已经有了代表 span 与边界距离的距离场数据，离边界越远距离越大，离边界越近距离越小。

使用分水岭算法划分区域的时候，认为距离最大的 span 为最低点，从这些点开始进行处理。

首先第一步，将高度场边界 borderSize 范围内可行走的 span 的 reg id 标记为头四个 reg id（从 1 开始）。对于 SoloMesh 而言，borderSize 是 0。

函数内定义了一个水平线的变量 unsigned short level = (chf.maxDistance+1) & ~1;，它的初始值是距离场内的最大距离。先加 1 再与 ~1 按位与，是为了向上取整到偶数，方便后面减 2 的处理。因为后面每次循环会将水平线上升 2 个单位的距离。这个 level 比较关键。

sortCellsByLevel 会将高度场内距离大于 level 的、未被分配 reg id 的可行走 span 加入到 lvlStacks 里对应的 stack 中。lvlStacks 一共有 NB_STACKS(8) 个元素，每个 stack 存储 2 个单位距离的 span，其中 stack 在 lvlStacks 中的序号越小，其中存储的 span 距离越大；序号越大，其中存储的 span 距离越小。但是一次最多只添加比 level 的距离小 14 个单位的 span，如果距离小到对应的 sId 大于 lvlStacks 的大小了，则直接略过，等待后续处理。而如果遇到了距离比 level 更大的 span，则通通加入到 lvlStacks[0] 中，因为这部分是之前遍历未能处理的，需要带入到当前循环里继续处理。

while (level > 0) 这个循环会在 lvlStacks 为空时（sId == 0），调用 sortCellsByLevel 进行填充，同时每次遍历将水平线 level 上升两个单位，并且从代表距离最远的 lvlStacks[0] 开始进行处理，逐步往代表着距离更近的 stack 靠近。当 sId != 0 时，appendStacks 会将前一次遍历中未被处理完的元素添加到当前的 stack 中。

while 循环内的主要逻辑有两块，一个是 expandRegions，它会检查 stack 中所有未被分配 reg id 的 span，如果其四方向邻接 span 里存在分配过 reg id、不是 border 的 span，那么找到其中距离最小的一个，将自己的 reg id 赋为该邻接 span 的 reg id。换句话说，也就是从已分配 reg id 的外层区域，尝试向外再扩展一圈。

然后是 floodRegion，这就是分水岭算法中的泛洪填充了。rcBuildRegions 会遍历 stack 中剩下的所有未被分配 reg id 的 span，依次调用 floodRegion 为其分配一个新的区域 id，并尝试使用 bfs 算法将这个区域进行扩展。扩展的范围由 unsigned short lev = level >= 2 ? level-2 : 0; 和 if (chf.dist[ai] >= lev && srcReg[ai] == 0) 确定，也就是比当前水平线 level 最多小 2 个单位距离范围内的未被分配 reg id 的 span。

需要注意，如果 floodRegion 在填充时发现一个 span 其八方向里已经有被分配了不同 reg id 的邻接 span，那么跳过对这个 span 得到 reg id 填充，等待后续处理（下次 expandRegions 时会将其 reg id 赋值为其四方向邻接里最近的 reg id）。

当水平线 level 减到 0 后，再调用 expandRegions 对所有未处理的 span 的 reg id 赋值，整个分水岭算法就结束了。

mergeAndFilterRegions

下一步是调用 mergeAndFilterRegions 对前面生成的区域进行合并与筛选。

它主要做四件事：

1. 预处理生成临时数据 rcRegion：

   • 记录每一个区域其垂直方向上重叠的所有区域 id 存储到 rcRegion::floors；
   • 判断一个区域内垂直方向上是否有同区域的重叠 span，记录到 rcRegion::overlap；
   • 通过 walkContour 遍历区域边界，将邻接区域的 id 按顺序存储到 rcRegion::connections 中，并对连续相同的 id 去重；

2. 将相连区域面积小于 minRegionArea 的区域进行剔除：

   遍历每一个 rcRegion，再用 bfs 搜索其 connections 记录的所有邻接区域，统计相连区域的面积总和。如果其中任一区域属于 borderSize 留出的边界区域，则相关区域均不会被剔除。如果相连区域的面积总和小于 minRegionArea，则将这些区域全部删除。

   之所以与边界区域相连就一定不会被剔除，应该是因为 navmesh 可能是以 tile 为单位构建的，在 tile 边界上的小区域无法得知会不会被隔壁 tile 所需要，所以就只能保留下来。

   为什么是相连区域的总面积而不是单个区域的面积小于 minRegionArea 即剔除？猜测是为了给后面的合并留下足够的小区域，而不至于全被删掉以至少浪了很多原本可以被合并的小区域。不过有两点疑问：

   1. 后面的区域合并必须在相同 reg id 内进行，而这里的相连面积统计并未考虑 reg id，可能导致小于 minRegionArea 的区域无法被剔除也无法被合并？
   2. 为什么不先合并再剔除，这样不就可以安全地直接剔除掉非边界的小区域了吗？

3. 将面积小于 mergeRegionSize 的区域与邻接区域进行合并：

   遍历所有区域，如果当前区域面积小于 mergeRegionSize 或者不是边界区域（与未分配区域的 span 相连），那么找到与该区域连接的所有区域中，面积最小的一个可合并区域，将自己合并到目标区域中。

   canMergeWithRegion 判断两个区域是否可以合并，需要满足条件：
   *. reg id 必须相同；
   *. 两个区域之间只有一段连续的边相交；
   *. 两个区域不存在垂直方向上的重叠部分。

4. 因前面的剔除与合并操作，有效 reg id 不再连续，这里将其进行重排。

看如下例子，有区域 1、2、3、4，其中 1、2 是孤立不连通的区域，3 是大区域，1、4 是小区域。在不开启 mergeRegionSize 的情况下如图：

开启 mergeRegionSize 后：

可以看到区域 1 被剔除了，区域 2 足够大，所以保留了下来。区域 4 虽然小，但是它与区域 3 连通，所以也保留了下来。这里测试的是 SoloMesh，没有 tile border，如果这里是一个 tile，且区域 1 邻接 tile border 的话，那么区域 1 也需要被保留下来。