Recast 学习记录之四：构建轮廓

序

本文根据 Sample_SoloMesh::handleBuild 中的 Step 5. Trace and simplify region contours 进行源码解析。

前面已经将高度场内的 span 都划分和标记了区域，这一步就是要给区域描边，确定出轮廓线条。同时也将后续处理的重点，从体素转移到顶点和线段上。

`rcBuildContours`

这一步通过函数 rcBuildContours 建立轮廓线条，其主要步骤如下：

填充 `rcContourSet`

填充 rcContourSet，根据 borderSize 对轮廓线集合的包围盒坐标进行调整；

标记 span 的不连通方向

将高度场内所有 span 的 不连通方向 标记出来，存到 flags 数组中，供后续 walkContour 使用。

当 flags[i] == 0 时，有三种可能：

对应的 span 处于区域内部，无需考虑;
对应的 span 位于区域边界，但其已经被处理过；
span 位于 tile 的边界 borderSize 范围内（RC_BORDER_REG），同样可以略过；

当 flags[i] == 0x3f 时，代表对应的 span 其四方向上均不连通，这种 span 可以安全地被忽略掉，不用处理。

遍历高度场内所有 span

遍历高度场内所有 flags 对应值不为 0 的 span，一一构建轮廓线。

`walkContour` 构建轮廓线

和 RecastRegion.cpp 中的 walkContour 类似，这里采用的是相同的遍历方法。

以坐标为 (x, y) 的 chf.spans[i] 为起点，以该 span 第一个不连通的方向 dir 为初始方向开始检测，如果当前 span 在该方向上不连通，那么将对应的坐标添加到轮廓中，并且将方向顺时针转动一个单位；如果在该方向上是连通的，那么将当前位置移动到该邻接 span 的坐标，并且将方向逆时针转动一个单位。达到的效果就是遇到障碍就向右转，不是障碍就前进，并且左转，这样就能达成贴着区域的边将其边界点一个一个记录下来的目的。并且最后记录下来的轮廓顶点是顺时针方向记录下来的。

记录下来的轮廓顶点坐标是个四元组，分别是 x y z r，其中 x z 是格子横纵坐标，y 是 span 在指定方向顺时针四个邻接 span 里的最大高度，r 是遍历时检查的邻接 span 的 reg id。要注意，这个 reg id 并不对应记录的轮廓顶点的 reg id。这个函数比较迷惑的就是具体确定轮廓顶点坐标的这一段代码了：

static void walkContour(int x, int y, int i,
                        rcCompactHeightfield& chf,
                        unsigned char* flags, rcIntArray& points)
{
            // ...
			int px = x;
			int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex);
			int pz = y;
			switch(dir)
			{
				case 0: pz++; break;
				case 1: px++; pz++; break;
				case 2: px++; break;
			}
            // ...
}

可以看到，当方向朝左时，pz 坐标加一，也就是取上方的格子坐标；当方向朝上时，px、pz 坐标各加一，也就是取右上方的格子坐标；当方向朝右时，取右边的格子坐标；当方向朝下时，就取当前格子的坐标。

作者的注释里说 The raw contours will match the region outlines exactly，但是显然有了上面的坐标偏移处理后，生成的轮廓并不能精确地与区域进行匹配。下面是推导的一个例子，从坐标 (31, 18) 开始，方向为 0，最终得到的轮廓线条其实有一部分是位于别的区域里面的：

为什么不直接将八方向里凡是有不连通的邻接关系的区域内 span 直接标记为轮廓顶点呢？这样肯定是完美匹配原始区域形状的，比如：

对于这一点，没能在网上找到相关的解释。对此，我想了想，觉得这种精准匹配的方法反而存在一个问题：区域与区域的轮廓之间完全独立了，不便于后续计算邻接信息。而 Recast 采用的办法，在区域的上边、右边的轮廓线均向相邻的区域延伸出了一个格子的边界，而左边、下边则保持精准匹配。同理，该区域相邻的其它区域也都采用这种类似的划分方式，这就带来一个特点：两块相邻区域相接触的轮廓边总是相同的。而且大家都向上、向右多占一格，等于大家谁都没有多占。

除了上面的从区域内部向外搜索出轮廓线的情况外，其实还有一种情况就是一个区域 A 内部包含了另一个区域 B。那么在这种情况下，区域 A 其实有两个轮廓线，一个是外部的 outline 轮廓线，另一个就是内部的 hole 轮廓线了：

通过简单的例子就能知道，这两种轮廓线是反向的，这一点需要注意，后面对区域内部洞的处理需要用到。

`simplifyContour` 对轮廓线进行简化处理

初步的轮廓线计算出来后，和格子组成的区域范围基本上还是贴合的。但是因为基本单位是体素，也就是一个格子的大小，所以会导致轮廓线锯齿感特别明显，同时顶点过多，也对后续的处理造成了不必要的负担。

下面就要对其进行一定的简化。处理过程分为三步：

将与同一个区域邻接的连续顶点，简化为只剩一个；如果没有邻接区域，那么就选取坐标里最左下、最右上的两个顶点。这一步可能会产生非常长的线段，在第三步中进行拆分处理；
遍历简化后的各边 AB，逐一搜索两个端点中间的原始轮廓顶点，查看该顶点 C 与边 AB 的距离，如果距离大于 maxError，则将点 C 插入到 AB 之间，并且以 AC 为边继续遍历；
遍历简化后的各边 AB，如果 AB 的长度大于 maxEdgeLen，那么就在 AB 中间的原始轮廓顶点中，选取一个中位点 C 添加回来，并以 AC 为边继续遍历；
恢复轮廓线顶点所对应的 reg id 字段。注释说 The edge vertex flag is take from the current raw point, and the neighbour region is take from the next raw point.，没太明白为什么这么做。

用上面的例子，第一步简化后：

第二步以后：

看 RecastDemo 的例子，简化处理前的轮廓：

简化处理后的轮廓：

切到 Both Contours 可以直接查看对比：

`removeDegenerateSegments` 删除劣化线段

这个逻辑很简单，遍历轮廓线上的所有顶点，查看相邻的两个顶点的 x、z 轴是否相等，是的话将前一个顶点删掉。

处理区域内的洞

检测洞是否存在

遍历所有轮廓，使用 calcAreaOfPolygon2D 可以计算出轮廓多边形的面积，其值的正负取决于轮廓顶点的顺时针、逆时针顺序，也就是取决于前面 walkContour 所得到的轮廓顶点顺序。显然，对于一个 outline 轮廓，其面积大于 0；对于一个 hole 轮廓，其面积小于 0。

`mergeRegionHoles` 将洞合并到区域轮廓中

一般来说，一块区域必定有一个 outline 轮廓，可能有多个 hole 轮廓。mergeRegionHoles 里先为每一个 hole 找到其 x 轴坐标最小的顶点，再将这些洞按照 x 轴坐标由小到大（x 轴坐标相等则按照 z 轴坐标由小到大）进行排序。

然后从前面找到的 hole 轮廓中 x 轴最小顶点开始遍历，对于每个顶点，在区域对应的 outline 轮廓中，每次取三个连续顶点，判断 hole 顶点是否在这三个点组成的锥形范围内，如果是的话，则认为这个 hole 顶点与 outline 上这三个点的中间点的连线是一个候选的合并线段，并记录下长度。最后遍历找出的候选线段，如果能找到一个长度最小且不与 outline 轮廓相交、不与剩下的 hole 轮廓相交的顶点，这就是该 hole 与 outline 轮廓进行合并的突破口了。

比如下列区域 ABCDEFGH 中有两个洞 IJK 和 LMNO，那么点 I 显然在 ABC 形成的锥形内且 IB 距离最小，所以洞 IJK 从点 I 进行合并。

我们把 outline 轮廓从点 B 处断开，形成点 P 和点 S；将 IJK 从点 I 断开，形成点 Q 和点 R。然后将 P 连接到 Q，将 R连接到 S，得到下图：

注意 PQ、RS 看起来是一条线段，其实是两条重合的线段。

将右边第二个洞也合并后：

这种合并方式虽然暂时让区域看起来比较崎岖了一点儿，但是后面建立 rcPolyMesh 的时候，会将区域按顶点重新划分为三角形再合并为凸多边形，所以不会影响后续导航网格的建立。

Recast 学习记录之四：构建轮廓

序

rcBuildContours

填充 rcContourSet