从零开始学习导航网格#7 recast代码分析之solomesh

上回说到将空间内的span都打上了区域标记
到目前为止，可行走区域都是以span为粒度表示的（一个一个的小方格），现在我们要根据区域标记来合并这些“小方格”，形成整片的连续区域

Step 5. Trace and simplify region contours.

a.遍历紧缩高度场中的span,根据regid（区域标记）求出每个span与周围相邻span的区域关系，用一个4位的2进制数来表示：
若与某个方向的邻居区域相同，则对应的标记记为0，这样最后得到的flag若为0，则表示是一个区域内部的span(4面都是自己人),否则就是一个区域边界上的span
这样处理完之后，就明确知道了哪些span是区域的边界

这里要特别区分一个咬文嚼字的问题：
“区域的边界”和“边界区域”是两个不同的概念。边界区域在recast中的定义为：
the region is a border region and its spans are considered unwalkable.
是整个包围盒外面的4块区域，被认为是不可行走的

边界区域

b.遍历所有作为区域边界的span，在遍历的过程中得到区域边界的轮廓顶点集
具体流程是这样的：
以一个边界span作为起始位置，顺时针方向判断它的4条边：
若当前边是区域分界边，则将边的一个顶点加入到轮廓顶点集中，并继续判断下一条边
若当前边不是区域分界边，则移动到与这条边相邻的span中（这个span是在同一个区域内），重新判断新的span的边

walkContour

具体的实现在这个函数中

static void walkContour(int x, int y, int i,
                        rcCompactHeightfield& chf,
                        unsigned char* flags, rcIntArray& points)

rcIntArray& points是输出的轮廓顶点集，每个元素是一个四元组：(x,y,z,r)
特别注意这里的第四个参数，r表示对应的邻接区域id以及一些附加细节信息（是否是边界区域的顶点、是否是区域边界顶点）

顶点的xz坐标好处理，高度值y的计算是通过这个函数

static int getCornerHeight(int x, int y, int i, int dir,
                           const rcCompactHeightfield& chf,
                           bool& isBorderVertex)

它做的事情是考虑以一个顶点为中心的4块相邻格子的span，取这4个span中高度最高的span作为顶点高度
（注意下图是一开始的实心高度域，铁子们自行脑补一下紧缩高度域）

计算顶点高度

c.执行完walkContour后就得到了轮廓顶点集，但是这个集合中的点可能非常多（区域是基于体素的粒度，所以现在的边是由许多长度为体素格子边长的短边拼接成的）
所以需要简化轮廓线

有两个顶点集：
rcIntArray points 原始轮廓顶点集合
rcIntArray simplified 简化顶点集合(需要保留下来的点)
简化的策略是：
首先不同区域的过渡点需要保留，放到simplified中
然后对于simplified中的每个相邻点对(假设记为AB)，检查points中位置在AB之间的点，若这些点到AB的距离大于某个值maxError
则将其中距离最远的点加入到simplified中，重复这个过程直到所有点距离简化的轮廓线都不超过maxError

简化轮廓线

至此我们就将体素方格化表示的可行走区域转化成了由顶点集合表示