Recast 学习记录之五：构建多边形网格

序

本文根据 Sample_SoloMesh::handleBuild 中的 Step 6. Build polygons mesh from contours 进行源码解析。

函数 rcBuildPolyMesh 负责将前面得到的轮廓顶点集合转换为可供寻路使用的多边形网格，其主要步骤有：

1. 将轮廓三角化，得到一个三角形集合；
2. 将三角形进行合并，得到凸多边形集合；
3. 将 RC_BORDER_VERTEX 点移除；
4. buildMeshAdjacency 计算邻接关系；
5. 计算与外部 tile 连接的边的邻接信息；

施工中…

rcPolyMesh

// @Recast.h
struct rcPolyMesh
{
        rcPolyMesh();
        ~rcPolyMesh();
        unsigned short* verts;  // 多边形网格内的所有顶点坐标，格式 [x, y, z]，数组大小 3*nverts
        unsigned short* polys;  ///< Polygon and neighbor data. [Length: #maxpolys * 2 * #nvp]
        unsigned short* regs;   // 多边形对应的 reg id 数组
        unsigned short* flags;  // 用户可自定义的多边形标记数组
        unsigned char* areas;   // 多边形可行走标记数组
        int nverts;             // 顶点数量
        int npolys;             // 多边形数量
        int maxpolys;           // 多边形数量上限
        int nvp;                // 单个多边形最大顶点数
        float bmin[3];          // AABB 包围盒
        float bmax[3];          //
        float cs;               // cellSize
        float ch;               // cellHeight
        int borderSize;         ///< The AABB border size used to generate the source data from which the mesh was derived.
        float maxEdgeError;     ///< The max error of the polygon edges in the mesh.
};

rcBuildPolyMesh

triangulate 将轮廓多边形拆分为三角形

顺序遍历区域轮廓，每次取三个连续顶点 p[i]、p[i+1]、p[i+2]，diagonal 判断 p[i] 与 p[i+2] 的连线是否在多边形内部且不与多边形的其它点相交，如果条件符合，则可以认为点 p[i+1] 在后续的三角化里可以被安全地当做一个三角形的顶点。

然后在这些点中进行搜索，每次找出一个点 p[i]，其前后两个点 p[i-1] 和 p[i+1] 的连线距离最短。可以将这三个点连接作为一个三角形，将 p[i] 从轮廓线中去除。因为删掉了一个点，所以 p[i-1] 和 p[i+1] 这两个点各自前后两个点的连线要再次进行 diagonal 检查。然后对剩余的点重复这个流程，直到轮廓多边形被完全划分为三角形。

比如下图的区域，显然第一个点是 E，可以将三角形 EFD 划分出来：

第二个点是 D：

划分完毕后：

如果前面找不到合适的顶点，那说明轮廓上可能有重叠的线段（之前区域划分时对洞的合并）。将前面的 diagonal 换成 diagonalLoose，区别是这个函数允许与边重合的情况。

mergePolyVerts 将三角形合并为凸多边形

把轮廓多边形划分为多个三角形后，下一步要做的就是将其再合并回多边形。不过这一步并非原样将其复原，而是根据构建参数里的多边形最大顶点数，将这些三角形合并为凸多边形。

两个多边形要进行合并，必须满足几个条件：

1. 两个多边形合并后，顶点数不能超过单个多边形的顶点数上限 rcPolyMesh::nvp；
2. 两个多边形必须有公共边；
3. 合并后的多边形必须是凸多边形。

首先将三角形复制到多边形数组内作为初始多边形数据。

然后遍历所有的多边形，根据 getPolyMergeValue 找到可以与其合并的、公共边最长的一个多边形进行合并。

将 RC_BORDER_VERTEX 点移除

TODO 为什么要移除？这点还没细看，作者在 Google Groups 里针对别人的提问 why rcBuildPolyMesh need remove vertex with the flag RC_BORDER_VERTEX 里说 The region generation code can leave vertices along the tile edges. While Detour can handle these, things work better if they are removed, and the connecting edge to the next tile is always just one segment.。

buildMeshAdjacency 计算邻接关系

这一步要计算多边形之间的邻接关系，供后续寻路时的搜索使用。

buildMeshAdjacency 这个函数对所有多边形的边进行了两次遍历，第一次建立边的信息 rcEdge， 第二次遍历搜索其邻接多边形的信息。

因为多边形的顶点是按照顺序进行排列的，所以对于两个邻接的多边形 A 和 B，它们的公共边的顶点顺序必然相反。对于 A 来说，这条边的是 vi-vj，但是对于 B 来说，这条边的必定是 vj-vi。

所以两次遍历，第一次遍历所有顶点序号 v0 < v1 的边，即可为所有的正向边建立 edge 信息，第二次遍历找到 v0 > v1 的边，设置邻接信息。

第一次遍历只为正向边创建 edge 信息，必然会导致一些并非公共边的反向边的遗漏，但是因为它们没有邻接关系，所以漏了就漏了。

计算与外部 tile 连接的边的邻接信息

遍历多边形的所有没有邻接信息的边，判断它为什么没有邻接信息。这里是判断这条边的两个端点，是否与 tile 的边界坐标重合（不是 tile border 的范围，而是严格判断 x 轴坐标是否均为 0 或者 tile width，z 轴坐标是否均为 0 或者 tile height），并且根据边所在的四个方向，为其邻接关系赋值为 0x8000 | dir，这里的 0x8000，就是 Detour 中的 DT_EXT_LINK，代表是与 tile 外部相连的边。

所以 rcPolyMesh 中多边形边的邻接数据一共有三种情况：

1. 邻接多边形的序号
2. tile edge 上的边，0x8000 | dir
3. RC_MESH_NULL_IDX(0xffff)

至此，导航网格就建立完成了。

现在的导航网格里有多边形，有邻接信息，已经可以使用 A* 算法进行路径搜索了。唯一的问题在于，因为有区域的合并和区域到轮廓的抽象，导致区域内部的高度信息基本丢失。