【译】NMGen – 轮廓生成

本页介绍了构建导航网格的第三阶段,即生成表示源几何体的可穿越表面(traversable surface area)的简单多边形(凸多边形和凹多边形)。轮廓仍然以体素空间为单位表示,但这是从体素空间回到向量空间的第一步。

源数据类:OpenHeightfield
构建器类:ContourSetBuilder
数据类:ContourSetContour

如果您需要了解此阶段执行的操作,请回顾处理过程概览

搜索区域边缘(Region Edges)

从开放高度场结构转向轮廓结构时,最大的概念变化是从关注span的表面(surface)转变为关注span的边(edges)。

对于轮廓,我们关心span的边。 有两种类型的边:区域边和内部边(region and internal)。 区域边是其邻居位于另一个区域中的span的边。 内部边是其邻居在同一区域中的span的边。

为了便于可视化,接下来的几个示例仅处理 2D,稍后我们将回到 3D。

在此步骤中,我们希望将边分类为区域边或内部边。这些信息很容易找到。我们遍历所有span,对于每个span,我们检查所有轴邻居,如果轴邻居与当前span不在同一区域中,则该边将被标记为区域边。

查找区域轮廓(Region Contours)

一旦我们有了关于哪些span的边是区域边的信息,我们就可以通过“遍历这些边”来构建一个轮廓。我们再一次遍历这些span,如果一个span有一个区域边,我们做以下工作:

首先面向已知的区域边,把它加到轮廓中。

旋转90度,增加区域边到轮廓中,直到找到一个内部边。向前步进到邻居span。

逆时针旋转90度,重复上一步操作。一直继续到我们回到起始span,面对起始方向。

从边到顶点

如果我们想回到向量空间,我们需要的是顶点,而不是边。顶点的(x, z)值很容易确定。对于每条边,我们从边沿顺时针方向取span顶部的角(corner)的(x, z)值(从span内部看)。

确定顶点的y值就比较棘手了。这就是我们回归3D可视化的地方。在下面的例子中,我们选择哪个顶点?

所有的边的顶点最多有四个可能的y值(译注:4个高低不同的span相邻)。选择最高的y值有两个原因:它确保最终顶点(x, y, z)位于源网格表面的上方。它还提供了一个通用的选择机制,以便所有使用该顶点的轮廓将使用相同的高度。

简化轮廓

至此,我们已经为所有区域生成了轮廓。轮廓是由从span的角导出的顶点所组成的。下面是一个宏观的视角。

请注意,有两种类型的轮廓部分(contour sections)。代表两个相邻区域之间门户(portal)的部分,以及与“空白”空间(”empty” space)接壤的部分。在代码的文档中,空白空间被称为“空区域”(null region),我在这里使用同样的术语。

真的需要这么多顶点吗?即使在直线轮廓上,构成边的每个span都有一个顶点。显然,答案是否定的。唯一真正必需的顶点是那些在区域连接中发生变化的顶点。例如,在区域门户(portal)的边上的顶点。

区域-区域门户(region-region portals)的简化很容易。我们丢弃除强制顶点(mandatory vertices)之外的所有顶点。

对于与空区域(null region)的连接,事情变得有点复杂了,使用了两种算法。

第一个是由 MatchNullRegionEdges 实现的 Douglas-Peucker 算法。 它使用 edgeMaxDeviation 参数来决定丢弃哪些顶点以得到简化的线段。它从强制顶点(mandatory vertices)开始,然后将顶点添加回来,这样原始顶点与简化边之间的距离都不会超过edgeMaxDeviation。

一步一步地来:从最简单的边开始。

找到离简化边最远的点,如果它超过了edgeMaxDeviation,则将顶点添加回轮廓。

重复这个过程,直到不再有顶点到简化边的距离超过允许值。

一个简化过的轮廓示例…

如前所述,还有一种算法用于连接到空区域(null region)的边。第一种算法可以生成长线段,以至在随后的网格生成过程中生成长而细的三角形。第二个算法由NullRegionMaxEdge实现,使用maxEdgeLength参数重新插入顶点,以确保没有线段超过最大长度。它是通过检测长边,然后将它们分成两半来实现这一点的。它会继续这个过程,直到检测不到过长的边为止。

举个例子来说明对最终网格的影响,之前…

之后…

我们在哪

在这个阶段结束时,我们有形成简化多边形的轮廓。顶点仍然在体素空间中。但是我们正在回到向量空间的路上。

0 0 投票数
文章评分
订阅评论
提醒
guest
2 评论
最久
最新 最赞
内联反馈
查看所有评论
xixi

博主,哈喽你好,每日更新。

近期文章

最新评论

分类

标签

归档

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