RecastNavigation中的区域切分方法

分水岭分区
- 经典的Recast分区
- 创建最好的细分
- 通常最慢
- 将Heightfield划分为没有孔或重叠的良好区域。
- 在某些极端情况下，此方法创建会产生孔洞和重叠
  - 当小的障碍物靠近较大的开放区域时，可能会出现孔（三角剖分可以解决此问题）
  - 如果您有狭窄的螺旋形走廊（即楼梯），则可能会发生重叠，这会使三角剖分失败
- 如果是预处理网格，通常是最佳选择，如果您有较大的开放区域，这种方法也适用。
单调分区
- 最快的
- 能将高度场划分为无孔和重叠的区域
- 创建长而细的多边形，有时会导致路径走弯
- 如果要快速生成导航网格，请使用此选项
按层分区
- 较快
- 将heighfield划分为非重叠区域
- 依靠三角剖分来处理孔（因此比单调分区要慢）
- 产生比单调分区更好的三角形
- 没有分水岭分区的特殊情况
- 速度可能很慢，并且会产生一些难看的镶嵌效果（仍然比单调效果更好），如果您的开放区域较大且障碍物较小（如果使用瓷砖则没有问题）
- 用于中小型瓷砖的导航网格的好选择

分水岭划分

过程分为两步：

1. 创建距离场

计算每个span到区域边界的距离（四个方向中最小的一个），距离越远越接近中心。

并用boxblur进行平滑处理（计算九宫格内距离的均值）（为什么？）

2. 按距离场进行划分

2.1 关键函数作用

expandRegions():

作用是扩展对应点集的区域id。扩展过程中会进行反复迭代，通过迭代扩散区域id。

扩散方式：检查四周（紧缩span的connection）是否有满足条件的span，条件为：被标记过 && 非边界 &&可走。

迭代停止条件：点集周围（包括点集）无任何标记或达到最大迭代次数（自定义的）

expandRegion运行结束后的结果：

函数运行结束后，点集内会出现两种点，分别有区域标记的点和空白的点。

在本函数大量迭代之后，如果仍有空白的点，则代表这些空白的点是一个新的区域。因为，这些点是无法通过上一层水位的点扩展到的。

floodRegion():

以一个span作为起始点，按4邻域泛洪填充它所能扩展到的区域
遍历搜索的方式采用深度优先(dfs),而dfs的实现则使用了手动压栈的非递归方式
而每次处理新的节点时，会先判断它的8个邻接节点是否已经有了更早的填充标记，如果有，则说明当前节点处于区域相交处，不扩展该节点（该节点会在下一层的expandRegions时被处理）

2.2 具体过程

首先，将边界标记出来

然后，按距离场中的数值进行排序，从大到小排序。

再然后，开始逐渐”加水“，从大的地方慢慢扩散。对于每一层操作如下：