# 【译】NMGen – 凸多边形生成

## 概述

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

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

…直到三角形剖分完成。

## 检测有效分割边（Valid Partitions）

### 内角算法（The Internal Angle Algorithm）

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…

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.

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.

## 合为成凸多边形

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

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

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.

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.

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.

## 最后加工

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 投票数 0 评论

0

()
x