项目中有两个地方都用到了分层分割算法
bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
const int borderSize, const int minRegionArea)
bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
const int borderSize, const int walkableHeight,
rcHeightfieldLayerSet& lset)
代码基本上大同小异，这里我们只对rcBuildLayerRegions进行说明
算法的思想其实比较朴素：
1.逐行扫描，将相邻的span合并成严格的“矩形区域”（这个下面会解释）
2.将第一步得到的矩形区域按是否相邻进一步合并，但需要保证合并的两个区域之间没有重叠的区域
这里“重叠”的含义是：两个区域存在各存在一个span，他们在zx的投影相同
下面着重解释一下第一步的处理过程
以每个cell最多只有一层span为例，看下面这个例子（注意是对xz平面的俯视图）
初始状态
注意逐行合并这里，如果1和2之间，还有一个span，那么123会在这一步就合并成一个大矩形，但是由于例子中存在一个空缺，所以无法合并
逐行合并
逐行扫描完毕后，再合并矩形区域
合并矩形区域
这里是单层的情况。如果是多层，需要判断两个区域之间是否重叠，如果重叠，则不能合并（如下图中蓝色和红色的区域在标记的位置重叠，不能继续合并）
区域合并
网友评论