【译】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)中已经有一些很棒的分水岭算法可视化,这里我就不重复了。

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

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

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

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

有时分水岭算法会导致一个区域绕着小的空区域(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.)

示例:在应用算法之前。

示例:应用算法之后。

我们在哪

在这一步结束时,我们有一个开放高度场,由代表源几何的可穿越表面的区域组成。

0 0 投票数
文章评分
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论

近期文章

最新评论

分类

标签

归档

0
希望看到您的想法,请发表评论。x
()
x