http://www.critterai.org/projects/cainav/

RecastNavigation下载地址

https://github.com/recastnavigation/recastnavigation

CritterAI 下载地址

http://www.critterai.org/

Recast/Detour文档

http://masagroup.github.io/recastdetour/index.html

理解 Heightfileds

http://www.critterai.org/projects/cainav/doc/html/6fb3041b-e9be-4f03-868b-dcac944df19b.htm

处理过程（这个文档描述的更为详细）

http://www.critterai.org/projects/cainav/doc/html/e72bd1ee-04b0-4bbb-a21d-d8d7ecaa11af.htm

Recast Navigation

Recsat 是先进的游戏导航网格制作工具。

自动生成，可输入任意关卡几何体并会生成网格。
快速，可快速生成关卡数据。
代码开放，可自定义核心数据。

Recast 先用关卡几何体生成体素模型，然后再生成导航网格覆盖它。处理过程有三步组成：①构建体素模型 ②把模型划分到简单的区域 ③用多边形替换这些区域

体素模型是将输入的三角面栅格化到多层高度域，并简单剔角色不会移动的位置而成。
可移动区被划分为多层二维区域。这些区域都有唯一的非重叠等高线，这样可以简化最后一步的处理过程。
用多边形替换这些区域：导航多边形沿着这些区域的边界被剥离并简化。

Detour

Recast

Recast 中的模块用于创建网格数据，Detour会用这些数据创建导航网格。

创建导航网格需要好多步骤，具体如下：

准备三角面
构建 rcHeightfield：描述高度域阻挡，rcCreateHeightfield，rcAllocHeightfield
构建 rcCompactHeightfield：描述无阻挡高度域
构建 rcContourSet：描述所有轮廓的集合
构建 rcPolyMesh：描述多边形网格，用于构建导航网格（未三角化的凸多边形集合）
构建 rcPolyMeshDetail：三角面网格
用 rcPolyMesh 和 rcPolyMeshDetail 构建 Detour 的导航网格

 正常生命周期大致如下：

分配 Recast allocator 分配对象（如 rcAllocHeightfield）
初始化并构建对象（如 rcCreateHeightfield）
更新对象（如 rcRasterizeTriangles）
把对象作为管线的一部分
释放 Recast allocator 分配对象（如 rcFreeHeightField）

体素化：Recast通过栅格化三角形将输入场景变为体素数组（使用 Conservative voxelization 算法）。可以指定长、宽、高(3D矩形，沿着 X,Z,Y轴方向的)。体素体积越小，计算量越大。Conservative voxelization算法能够确保输入的三角形面被完全包裹在生成的体素中。
过滤：体素数组生成后，会通过一些简单过滤隔离可行走区域的体素。体素是否可行走受许多因素影响。除受自身大小因素，还受到许多代理参数影响。例如：
    高度
    半径
    能爬的最大高度
    能行走斜坡的最大角度
分割：可行走区确定后，Recast将把这些区域转化到2D区域。这些区域不重叠（应该是Y轴重叠的区域），这么做有利于下一步骤的处理。
创建多边形：Recast用之前创建的区域和边界生成简单的凸多边形。区域的边界就是多边形的顶点（尽可能大），这些凸多边形用来计算两点间的最短路径。最终会生成两种网格：导航网格和详细网格。
    导航网格：可行走区域连接起来的网格，用于描述寻径空间。
    详细网格：这个网格对应于导航网格，但有更详细的高度信息。这个高度信息决定是否将不同高度差多边形连接起来。