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

上回说到我们已经将场景内的可行走区域转换成了邻接的多边形网格，其实到这里已经可以支持寻路了。不过多边形网格与原始场景的地表高度可能会有比较大的偏差，所以如果对高度要求特别精确的话，需要进一步生成带高度的细节网格（如图中，多边形网格对应粉色的区域是一整块，所以与原来地表的高度不是很匹配）

细节网格

Step 7. Create detail mesh which allows to access approximate height on each polygon

生成细节网格的主要思路就是通过紧缩高度域对多边形网格进行高度采样，将高度差距过大的部分重新切割成更碎的三角网格。具体的实现步骤是这样的：

a.先得到多边形的高度补丁

遍历每个多边形,按体素网格细分多边形的高度：
多边形在xz格子内的高度被记为改格子上与多边形regid相同的span的高度
另外还附带计算了多边形包围盒内不是多边形区域的格子的高度（用多边形边界做一次bfs）
具体实现可以参考这个函数

static void getHeightData(rcContext* ctx, const rcCompactHeightfield& chf,
                          const unsigned short* poly, const int npoly,
                          const unsigned short* verts, const int bs,
                          rcHeightPatch& hp, rcIntArray& queue,
                          int region)

b.处理每个多边形时，先对多边形的边（外轮廓）进行采样修正

1.设置采样点（将每条边按sampleDist分成若干段）
2.判断采样点对应的高度点与边的距离是否超过sampleMaxError，若超过，则需要用这个点重新构造外轮廓
3.将新的外轮廓三角化

边采样修正

这里三角化外轮廓的方式是这样的：
1.先找到轮廓中最小的“耳朵”，做一次划分
2.以这个耳朵为中心，判断新的左耳朵和右耳朵哪个更小，取较小的再做一次划分
3.更新左右边界，重复2的过程，直到三角化完成

三角化外轮廓

具体的实现可以参考这个函数

static void triangulateHull(const int /*nverts*/, const float* verts, const int nhull, const int* hull, const int nin, rcIntArray& tris)

c.再对多边形内部进行采样修正

1.设置采样点（按xz坐标中设置）
2.取采样点中偏离多边形网格最大的点，用这个点对当前网格做一次Delaunay三角剖
3.重复步骤2，直到所有采样点都在偏离的允许范围内，或者点集超过上限

内部采样修正

至此我们就得到了与原始场景更贴近的细节网格，不过项目中在做寻路的时候用的还是非细节的多边形网格（节点更少，搜索效率高），细节网格只是一个可选项，可以优化寻路路径点上的坐标位置。