Detour 学习记录之一：创建 dtNavMesh

序

施工中…

这边文章主要讲如何创建 navmesh，添加 tile 的细节流程，tile 内部 link、off-mesh link 的建立，tile 间 link、off-mesh 的建立。以及 navmeshquery 的初始化，其中的成员用处是什么。

dtCreateNavMeshData

将 Recast 得到的导航网格构建数据比如顶点坐标、多边形序号、邻接关系、细节网格、等信息赋值到 dtNavMeshCreateParams 里，然后调用 dtCreateNavMeshData 将导航网格数据进行整合打包，创建出一块连续内存，方便存储以供后续使用。

需要注意，Recast 中 polys 数组包含的邻接多边形 id 信息，会被加上 1，用 0 表示没有邻接多边形。而 tile edge 上的 0x8000 | dir 中的 dir 由 0、1、2、3 被转换为 4、2、0、6。

dtNavMesh::init

dtNavMesh 进行初始化，主要是构建哈希表与 tile 空闲链表。 如果是 SoloMesh，那么在 init 的时候可以直接传入 data 数据，否则需要后续调用 dtNavMesh::addTile。

dtNavMesh::addTile

这是 dtNavMesh 的一个核心函数，其作用是将 data 指定的 tile 数据添加到 navmesh 上，并且构建这个 tile 与邻接 tile 的连接关系。

主要关注以下几个函数：

1. connectIntLinks: 构建 tile 内部多边形之间的连接信息；
2. connectExtLinks: 构建两个 tile 间的多边形连接信息。
3. baseOffMeshLinks: 设置 off-mesh connection 基准位置；
4. connectExtOffMeshLinks: 构建两个 tile 间的 off-mesh connection 信息；

connectIntLinks 构建 tile 内部多边形之间的连接信息

遍历所有多边形，根据多边形邻接信息 dtNavMesh::neis 构建出 dtLink 的静态链表。

struct dtLink
{
    dtPolyRef ref;          // 连接到的多边形的 id
    unsigned int next;      // 下一条连接的 id，构成静态链表
    unsigned char edge;     // 这条连接属于多边形内的边的序号
    unsigned char side;     // 用于 tile 间的连接，表示连接的方向
    unsigned char bmin;     // 用于 tile 间的连接，表示连接所在边占 tile 边的长度比例范围 
    unsigned char bmax;
};

connectExtLinks 构建两个 tile 间的多边形连接信息

遍历起始 tile 内所有多边形的边，找到具有外部连接标记 poly->neis[j] & DT_EXT_LINK 的多边形的边，并根据 poly->neis[j] & 0xff 判断边的方向与当前需要进行连接的方向是否一致。然后调用 findConnectingPolys 找到目标 tile 里与这条边连接的、反方向的多边形。然后为起始多边形与目标邻接多边形一一建立起邻接信息 dtLink。

因为这里是 tile 间的连接关系，所以 side、bmin、bmax 三个参数需要进行设置。

如果该连接是在 x 轴方向上的，那么用边与邻接多边形重合部分的 z 轴差值除以该邻接边在 z 轴上的差值，得到一个最小和最大比例，在将其类型由 float 转换到 char 上。 如果该连接是在 z 轴方向上的，那么就用 x 轴的差值进行计算。

bmin、bmax 在后续计算射线检测的时候可以用到。

TODO 怎么用

findConnectingPolys

calcSlabEndPoints

overlapSlabs

baseOffMeshLinks 校准 off-mesh connection 端点的位置

off-mesh connection 本身有起始、结束两个端点的坐标，也有自己对应的 off-mesh poly。

这个函数的目的主要是对于 tile 内的 off-mesh connections 起始点，通过 findNearestPolyInTile 找到离它最近的多边形 start poly 和最近坐标点，用该坐标来修正 off-mesh poly 的位置，确保 off-mesh connection 的起始点一定在导航网格上。

然后为 off-mesh poly 到 start poly、start poly 到 off-mesh poly 构建 dtLink 连接信息。

connectExtOffMeshLinks 构建两个 tile 间的 off-mesh connection 信息

dtNavMeshQuery::init