【译】NMGen - 处理过程概览

原文：http://www.critterai.org/projects/nmgen_study/overview.html

本页面描述了NMGen用于创建导航网格数据的过程概览。这个过程是由NavmeshGenerator类实现的。

一般流程如下:

1. 体素化：从源几何结构创建一个实体高度场。
2. 生成区域：检测实体高度场的顶部表面，并将其划分为由相邻span组成的区域。
3. 生成轮廓：检测区域的轮廓，并将它们形成简单多边形。
4. 生成多边形网格：将轮廓细分为凸多边形。
5. 生成详细网格：将多边形网格三角形化，并添加高度细节。

体素化（Voxelization）

由SolidHeightfieldBuilder类实现。

在体素化过程中，源几何结构被抽象为一个表示障碍空间的高度场。 然后对不可行走的表面进行一些初始剔除。

源几何结构中的每个三角形都使用保守体素化的方式进行体素化并添加到高度场中。保守体素化是一种确保多边形表面完全被生成的体素包围的算法。

下面是使用保守体素化包围三角形的一个例子：

体素化后，实体高度场包含了将源几何结构中所有多边形表面完全包围的span。

体素化完成后，通过以下测试的span被标记为“可通过”（traversable）：

• span的顶部与其上方span的底部至少有一个最小距离（最高的agent可以站在span上而不会与上方的障碍物发生碰撞）。
• span的顶部体素所表示的几何体的斜率（slope）低于一个最大允许值（坡度足够低，使得agent可以通过）。
• 如果启用了壁架剔除（ledge culling），则span顶部不代表壁架（ledge）（agent可以合法地从span“走下（step down）”到其所有邻居）。

区域生成（Region Generation）

由 OpenHeightfieldBuilder 类实现。

这一阶段的目标，是进一步定义实体表面的哪些部分是可通过的，并将可通过的区域分割成可以最终形成简单多边形的相邻的span（表面）区域。

第一步是将实体高度场转换为开放高度场，该高度场表示实体空间顶部的潜在可通过表面。开放高度场代表实体空间表面的潜在地板区域。

在下面的例子中，绿色区域表示由open span定义的地板。这对应于实体高度场中所有可通过的span的顶部。注意，墙壁、桌子下面的区域，和诸如阳台扶手等一些薄的区域，在实体高度场的生成过程中被剔除了。一些无法行走的区域，如桌面、楼梯扶手和薄壁架，此时仍显示为可通过。

接下来，进一步淘汰不可行走的span。在处理过程结束时，只有通过以下测试的open span才被认为是可通过的：

• span不能靠障碍物太近 （如墙壁、家具等）。
• span在其地板上方有足够的无障碍空间（agent可以合法地在span上行走而不会与span上方的物体发生碰撞）。

为所有尚存的open span生成邻居信息，以帮助将span组合成真实的表面区域。该算法考虑了一个最大垂直步长阈值（maximum vertical step threshold），以确定哪些span是可以连接的。这会允许诸如楼梯、路缘、桌面等结构被适当的考虑进来。例如，组成楼梯的不同台阶的span将作为邻居连接起来。但是桌面上的span不会与构成其相邻的地板的span相连。

区域是使用邻居信息和分水岭算法（watershed algorithm）生成的。区域的大小会被优化，太小而无法使用的孤岛区域(例如桌面)会被剔除。

下面的例子展示了区域（region）。请注意，即使构成楼梯的span实际上并没有连接，区域也会沿着楼梯延伸。还需要注意的是，通过了实体高度场生成过程的桌面、楼梯栏杆和所有其他无法行走的表面都已被成功剔除。 （黑色表示被剔除的span。）

在这一阶段的最后，可通过表面用连接在一起的span组成的区域（region）来表示。

轮廓生成（Contour Generation）

由ContourSetBuilder类实现。

区域的轮廓被“走过”（walked），形成简单的多边形。这是从体素空间（voxel space）回到向量空间（vector space）的过程中的第一步。

首先，从区域生成高度详细的多边形。

接下来，使用各种算法来完成以下任务：

• 简化相邻多边形之间的边（区域之间的入口（portal））。
• 确保边界边（border edges）与可通过表面的边界一致。(边界边是连接到空白或障碍空间的轮廓边。)
• 优化边界边的长度（过长的边界可能会在随后的过程中形成非最优三角形）。

下面的例子显示了运行这些算法后的轮廓。

在这一阶段的最后，可通过的表面由简单的多边形表示。

凸多边形生成（Convex Polygon Generation）

由PolyMeshBuilder类实现。

许多算法只能用于凸多边形。因此，这一步将构成轮廓的简单多边形细分为凸多边形网格。

这是通过使用一个适用于简单多边形的三角形划分（triangulation），然后再将三角形合并为最大可能的凸多边形来实现的。

下面你可以看到一个混合的凹多边形（原文是concave polygons，不知道是否写错了）已经形成的轮廓。

在这一阶段的最后，可通过的表面由凸多边形网格表示。

详细网格生成（Detailed Mesh Generation）

由DetailMeshBuilder类实现。

在最后阶段，使用 Delaunay 三角剖分（Delaunay triangulation）对凸多边形网格进行三角剖分，以便添加高度细节。顶点在内部添加到多边形的边缘，以确保充分遵循原始几何体的表面。

下面的例子展示了一个详细的网格。

在这一阶段的最后，可通过表面由与源几何体的高度轮廓相匹配的三角形网格表示。