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

（上回说到Step1 Step2已经将场景模型转化为带有可行走信息的体素集span）

Step 3. Filter walkables surfaces.

这一步主要是根据walkableClimb和walkableHeight这两个参数对span的可行走性做一些修正
将一些原本是不可走面，但可以通过其他可行走的地方爬上去的span标记为可行走(比如楼梯台阶垂直面对应的span)
将一些原本是可行走面，但span高度不够的标记为不可行走（比如床底下）

Step 4. Partition walkable surface to simple regions.

这一步应该是生成导航网格中最复杂也最难理解的一步，需要做很多处理

a.将高度域转化为紧缩高度域

紧缩空间

高度场中的span是三角面的体素集，是“实心”的部分
紧缩空间是将实心区域之间的“空心”部分取出来
每个紧缩空间的起始位置是一个实心空间的可行走顶面，高度是“空心”区域的连续高度
找出所有紧缩空间后，再计算出每个紧缩空间与周围相邻的紧缩空间的联通情况
两个紧缩空间的联通条件是这样的：
1.两个底面的高度差小于可爬行高度
2.高底面与低顶面的高度差大于玩家模型高度

相邻判断条件

b.用玩家模型半径修剪可行走区域边界（把靠近阻挡或者区域边界的可行走区域标记为不可行走）

dist[]数组表示每个span(以后的span都特指CompactSpan)到边界或者阻挡的距离（单位是格子）
1.先找到不可行走的span和边界span(可行走但邻居数<4),把它们的dist标记为0
2.从左上角开始向右下角遍历每个格子的span，用上半方4个格子更新dist
3.从右下角开始向左上角遍历每个格子的span，用下半方4个格子更新dist
4.将dist小于直径的span都标记为不可行走

修剪边界

c.对高度场进行区域划分

有多种种算法可以选择，由于服务器是离线生成导航网格，所以我们只看速度最慢但效果最好的分水岭算法
（如果有需要请参看分水岭算法的说明）
1.创建距离域
先计算出每个span到区域边界的距离（这一步和b中找区域边界时求dist[]是一样的），距离越远表示越接近区域的中心，距离越小表示越接近区域边界
再用boxblur来做一次模糊处理（即把span实际的dist修改为周围九宫格内的span的dist的平均值），使得span的距离值比较平滑
用颜色的深浅来表示距离边界的远近，则处理之后的结果如图所示

距离域

2.根据距离域划分区域

bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
    const int borderSize, const int minRegionArea, const int mergeRegionArea)

这个函数是分水岭算法的实现部分，作者在编码时做了很多内存上的优化，所以有些地方写的比较晦涩，把我看自闭了 ( ᖛ ̫ ᖛ )
算法的主流程其实并不复杂：
由于距离域中已经记录了每个span到边界的距离，距离越远表示越接近区域的中心
那么将span按距离排序（这里用的是类似于基数排序，把距离相同的span都放到同一个容器中），然后按距离从大到小分批处理（可以看成从每个区域的中心开始扩展填充的过程）
对于当前批次的span，首先看能否加入之前已经存在的区域(与一个标记过的span相邻)，对于不能加入已有区域的span，做一次泛洪填充(调用floodRegion函数)
floodRegion函数做的事情：
以一个span作为起始点，按4邻域泛洪填充它所能扩展到的区域
遍历搜索的方式采用深度优先(dfs),而dfs的实现则使用了手动压栈的非递归方式
而每次处理新的节点时，会先判断它的8个邻接节点是否已经有了更早的填充标记，如果有，则说明当前节点处于区域相交处，不扩展该节点（该节点会在下一层的expandRegions时被处理）

最后说下代码中让人费解的数据结构

const int LOG_NB_STACKS = 3;
const int NB_STACKS = 1 << LOG_NB_STACKS;
rcTempVector<LevelStackEntry> lvlStacks[NB_STACKS];

这是一个层数为8的栈，然后栈中的每个元素又是一个栈

rcTempVector<LevelStackEntry> stack;
stack.reserve(256);

这是一个初始大小为256的栈
这两个东西其实没什么关系。。
lvlStacks[NB_STACKS]这个东西是用来做基数排序，然后存放不同距离的span用的，其实没用到什么栈的特性
至于为什么lvlStacks[]要定义8层。。。我看下来只是作者的一种处于内存考虑的优化写法,一次性最多处理8层，多余8层下一轮再处理，没有什么数学上的含义
stack这个东西是在floodRegion时用来手动压栈实现非递归dfs的