【译】NMGen - 区域生成

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

本页介绍了构建导航网格的第二阶段，即生成表面区域，用以表示源几何结构的可通过表面。

源数据类：SolidHeightfield
Builder 类：OpenHeightfieldBuilder
数据类：OpenHeightfield

如果你需要回顾此阶段执行的操作，请参见：处理过程概览。

solid span比open span更容易可视化。所以这个页面的大多数可视化都使用了solid span。但要记住，这里描述的大多数算法使用open高度场而不是solid高度场。

创建开放高度场（Open Heightfield）

如高度场简介中所述，开放高度场表示实体高度场中span上方的区域。开放高度场的创建相对简单，循环遍历所有实体span，如果span被标记为可通过，则确定它的最高值与其所在列中下一个更高span的最低值之间的开放空间。这些值分别形成了新的开放span的地板和天花板。如果一个实体span是它所在列中最高的span，则其关联的开放span将其天花板设置为任意高值（例如 Integer.MAX_VALUE）。新生成的开放span形成所谓的开放高度场。

创建邻居链接（Neighbor Links）

我们现在有一个开放高度场，里面充满了不相关的开放span。下一步是找出哪些span形成了连续span的潜在表面。这是通过创建轴邻居链接（axis-neighbor links）来实现的。在搜索邻居中涵盖了轴邻居（axis-neighbors）的概念。

对于每个span，搜索其轴相邻列以查找候选对象。如果满足以下两个条件，则相邻列中的span被视为邻居span：

两个span的地板之间上升或下降的步长小于 maxTraversableStep 的值。这允许将楼梯台阶和路缘这样的表面检测为有效的邻居。

当前span的地板和潜在邻居span的天花板之间的开放空间间隙足够大，可以通过。例如，如果agent要从一个span跨到另一个span，它会用头撞到邻居的天花板上吗？

这是与潜在邻居之间的间隙检查。我们已经知道地板到天花板的高度对于每个单独的span来说都是足够的，该检查是在构建实体高度场时进行的。但是不能保证在潜在邻居之间移动时的间隙满足相同的高度要求。

此外，虽然下面的可视化显示了一个agent站在span上，但span的大小很少（如果有的话）大到足以让这种情况发生。但从算法的角度来看，这并不重要。如果从一个span到另一个span的模拟运动在微观层面上是无效的，那么它在宏观层面上也是无效的。

没有必要搜索和存储所有8个邻居的链接，因为如果需要，可以通过执行邻居的邻居的链接遍历（neighbor-of-neighbor link traversal）来找到对角线邻居。（有关更多信息，请参阅搜索邻居。）

创建距离场（Distance Field）

距离场（distance field）由每个span与其最近的边界span之间的距离估计组成。生成区域的算法需要这些信息。

边界span（border span）是指少于8个邻居的span。边界span表示源几何体的可穿越表面与障碍物(如墙壁)或空间空间之间的边界。空白空间可能是下降点(例如阳台或悬崖的边缘)或源几何的边缘。

下面的示例显示了一种特殊情况，在这种情况下，非边界span被错误地标识为边界span。这是使用距离场算法使用的标准8邻居搜索的一个缺点。然而，在实践中，这并不会造成问题。

距离场的一个例子：

创建区域

到目前为止，所有的一切都是在为区域创建做准备。区域（region）是一组连续的span，表示可穿越表面的范围。区域的一个重要方面是，当投影到xz平面上时，它们会形成简单的多边形。

分水岭算法（watershed algorithm）用于初始区域的创建。使用分水岭类比，距离边界最远的span代表分水岭中的最低点，边界span代表可能的最高水位。主循环从分水岭的最低点开始迭代，然后随着每个循环递增，直到达到允许的最高水位。这从最低点开始缓慢地“淹没”span。在循环的每次迭代期间，都会定位出低于当前水位的span，并尝试将它们添加到现有区域或创建新的区域。在区域扩展（region expansion）阶段，如果新淹没的span与一个已经存在的区域接壤，则通常会将其添加到该区域中。任何在区域扩展阶段残留下来的新淹没的span都被用作创建新区域的种子。

Denis Haumont、Olivier Debeir和François Sillion在Volumetric Cell-and-Portal Generation(PDF和Postscript)中已经有一些很棒的分水岭算法可视化，这里我就不重复了。

分水岭算法并不完美，它有时会创建一些在导航网格生成过程的后期阶段有问题的区域。所以在初始区域生成之后，会使用各种算法进行清理。

算法由FilterOutSmallRegions和CleanNullRegionBorders类实现。以下是一些应用于区域的“修复”示例:

太小而无法使用的岛屿区域被丢弃(标记为不可行走)。

不必要的小区域被合并为更大的区域（没有可视化）。

有时分水岭算法会导致一个区域绕着小的空区域（small null regions）流动。在这种情况下，该区域在空区域被分成两个区域（没有可视化）。

在有问题的空区域的边界上可能会出现各种span配置。例如：如果一个区域只用一个span包裹着一个角，那么轮廓生成步骤可能会创建一个自交多边形。这些有问题的配置被检查和消除。
（原文：Various span configurations can occur on the border of null regions that are problematic. For example: If a region wraps a corner by just one span, the contour generation step may create a self intersecting polygon. These problematic configurations are detected and eliminated.）

示例：在应用算法之前。