【译】NMGen – 凸多边形生成

本页描述了构建导航网格的第四个阶段,即从由轮廓表示的简单多边形生成凸多边形。这也是我们从体素空间回到向量空间的地方。

源数据类:ContourSet
构建类:PolyMeshFieldBuilder
数据类:PolyMeshField

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

概述

本阶段的主要任务如下:

  • 轮廓的顶点在体素空间中,这意味着它们的坐标采用整数格式并表示到高度场原点的距离。因此轮廓顶点数据被转换为原始源几何体的向量空间坐标。
  • 每个轮廓完全独立于所有其他轮廓。在此阶段,我们合并重复的数据并将所有内容合并到一个单一网格中。
  • 轮廓只能保证表示简单的多边形,包括凸多边形和凹多边形。凹多边形对导航网格来说是没有用的,所以我们根据需要细分轮廓以获得凸多边形。
  • 我们收集指示每个多边形的哪些边连接到另一个多边形的连接信息(多边形邻居信息)。

坐标转换和顶点数据合并是相对简单的过程,所以我不会在这里讨论它们。如果您对这些算法感兴趣,可以查看文档详尽的源代码。这里我们将专注于凸多边形的细分。对每个轮廓会执行以下步骤:

  1. 对每个轮廓进行三角面化(triangulate)。
  2. 合并三角形以形成最大可能的凸多边形。

我们通过生成邻居连接信息来结束这个阶段。

三角形剖分(Triangulation)

三角形剖分是通过沿着轮廓的边往前走(walking the edges of the contour)来完成的,对于每组三个顶点,确定是否可以形成有效的内部三角形。从所有潜在的候选者中,选择具有最短的新边(译注:即下图中的虚线)的那个。新边被称为“分割边”(partition edges),或简称为“分割”(partition)。该过程继续处理剩余的顶点,直到三角形剖分完成。

为了提高性能,三角形剖分在轮廓的 xz 平面投影上运行。

一步一步地来:先找到潜在的分割边(partitions)。

选择最短的分割边并形成一个三角形。删除无效的分割边并生成新的潜在分割边。

继续分割…

…直到三角形剖分完成。

检测有效分割边(Valid Partitions)

使用两种算法来确定一组三个顶点是否可以形成有效的内部三角形。第一种算法很快,可以快速剔除完全位于多边形之外的分割边。如果分割边在多边形内部,则使用更昂贵的算法来确保它不与任何现有多边形的边相交。

内角算法(The Internal Angle Algorithm)

这个算法可能有点难以描述。所以这里有一些例子。首先看一个有效分割边的例子。对于顶点 A、B 和 C,其中 AB 是潜在的分割边…

原文
This algorithm can be a little difficult to describe. So here are some examples. First, a valid partition. For the vertices A, B, and C, where AB is the potential partition…

沿着连接到顶点 A 的边打出两条射线。内角是多边形方向上的角。 如果分割边的端点(顶点 B)在内角内,则它是潜在的有效分割边。

原文
Cast two rays out along the edges connected to vertex A. The interior angle is the angle in the direction of the polygon. If the partition endpoint (vertex B) is within the interior angle, then it is a potential valid partition.

第二个例子是使用不同顶点的相同场景。因为分割边的端点(顶点B)在内角之外,所以它不是一个有效分割边。

原文
This second example is the same scenario with different vertices. Since the partition endpoint (vertex B) is outside the interior angle, it can’t be a valid partition.

边相交算法(The Edge Intersection Algorithm)

这个算法容易理解一些。它只是循环遍历多边形中的所有边并检查潜在的分割边是否与它们中的任何一个相交。如果是,则它不是有效的分割边。

只有当两个算法都通过时,分割边才被认为是有效的。

原文
This algorithm is much easier to understand. It simply loops through all edges in the polygon and checks to see if the potential partition intersects with any of them. If it does, it isn’t a valid partition.

Only if both algorithms pass is the partition considered valid.

合为成凸多边形

合并只能发生在从单个轮廓创建的多边形之间。不会尝试合并来自相邻轮廓的多边形。

请注意,我已切换到一般形式的“多边形”(polygon)而不是三角形(triangle)。虽然初始合并将在三角形之间进行,但随着合并过程的进行,非三角形多边形可能会相互合并。

该过程如下:

  1. 找出所有可以合并的多边形。
  2. 从该列表中,选择共享边最长的两个多边形并将它们合并。
  3. 重复这个过程直到没有可以进行的合并。

如果满足以下所有条件,则可以合并两个多边形:

  • 多边形共享一条边。
  • 合并后的多边形仍然是凸多边形。
  • 合并后的多边形的边数不会超过 maxVertsPerPoly 参数允许的数量。

检测共享边和确定合并后的边数都很容易。确定合并后的多边形是否为凸多边形有点复杂。此检查的关键是共享顶点。检查两个共享顶点在合并后的样子,如果两者都形成内部锐角(internal acute angles),则合并后的多边形仍将是凸多边形。我们为每个共享顶点确定这一点,如下所示:

  1. 创建由共享顶点之前和之后的顶点形成的有向参考线。
  2. 如果共享顶点在其参考线的左侧,则形成锐角。

最好使用可视化,第一个示例演示了有效的合并。

原文
Merging can only occur between the polygons created from a single contour. No attempt is made to merge polygons from adjacent contours.

Note that I have switched to the general form “polygon” rather than triangle. While initial merging will be between triangles, as the merge process proceeds non-triangle polygons may be merged with each other.

The process works as follows:

1. Find all polygons that can be merged.
2. From this list, select the two polygons with the longest shared edge and merge them.
3. Repeat until there are no further allowed merges.

Two polygons can be merged if all of the following conditions are met:

· The polygons share an edge.
· The resulting polygon will still be convex.
· The resulting polygon will not have more edges than allowed by the maxVertsPerPoly parameter.

Detecting shared edges and determining the merged edge count are both easy. Determining whether the merged polygon will be convex is a little more complex. The key to this check is the shared vertices. Both are checked for what they will look like after the merge. If both will form internal acute angles, then the merged polygon will still be convex. We determine this for each shared vertex as follows:

1. Create a directed reference line formed by the vertices just before and just after the shared vertex.
2. If the shared vertex is to the left of its reference line, then is forms an acute angle.

It is best to use visualizations. The first example demonstrates a valid merge.

如果把共享顶点标记为A,那么参考线将从顶点A-1到顶点A+1。顶点A在参考线的左侧吗?

原文
If the shared vertex is labeled A, then the reference line will be from vertex A-1 to vertex A+1. Is vertex A to the left of the reference line?

现在检查第二个共享顶点,它是否在其参考线的左侧?

原文
Now check the second shared vertex. Is it to the left of its reference line?

在下一个例子中,合并是无效的,因为如果合并发生,其中一个共享顶点将形成一个钝角内角。

原文
In this next example, the merge is invalid since one of the shared vertices will form an obtuse internal angle if the merge occurs.

如果您不熟悉用于检查点相对于有向线位置的算法,Soft Surfer 给出了很好的解释。核心算法由 PolyMeshFieldBuilder 中的 getSignedAreaX2() 操作实现。

原文
If you are unfamiliar with the algorithm used to check the position of a point relative to a directed line, a good explanation is given at Soft Surfer. The core algorithm is implemented by the getSignedAreaX2() operation in the PolyMeshFieldBuilder.

最后加工

这个阶段的最后一步是遍历整个网格中的所有多边形并生成连接信息(connection information)。虽然算法经过了优化,但在最基本的层面上,它只是简单地遍历所有多边形的边,并寻找其他具有相同顶点的边的多边形。

原文
The last step in this stage is to iterate through all the polygons in the entire mesh and generate connection information. While the algorithm is optimized, at its most basic level it simply steps through all the polygon edges and looks for other polygons that have an edge with the same vertices.

我们在哪

我们终于回到了向量空间,并得到一个凸多边形网格。

原文
We are finally back into vector space and have a mesh of convex polygons.
0 0 投票数
文章评分
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论

近期文章

最新评论

分类

标签

归档

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