本页介绍了构建导航网格的第五个也是最后一个阶段,即生成具有详细高度信息的三角形网格。

源数据类:PolyMeshFieldOpenHeightField
构建类:DetailMeshBuilder
数据类:TriangleMesh

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

原文
This page describes the fifth and final stage in building a navigation mesh, the generation of a triangle mesh with detailed height information.

Source data class: PolyMeshField and OpenHeightField
Builder class: DetailMeshBuilder
Data class: TriangleMesh

If you need an overview of what is performed in this stage, please refer back to the high level process.

为什么要执行这一步

如果将原始源网格的可通过表面投影到xz平面上,并与上一阶段生成的多边形网格重叠,两者将会非常匹配。但在三维空间中,多边形网格可能无法充分遵循源网格的高度轮廓 。这个阶段增加了高度细节,这样细节网格(detail mesh)将在所有轴上与源网格的表面相匹配。为了实现这一点,我们遍历所有多边形并在多边形与源网格过度偏离时沿着多边形的边和其表面插入顶点。

在下面的例子中,楼梯附近的多边形网格在xz平面上匹配,但在y轴上偏差很大。

原文
If the traversable surfaces of the original source mesh is projected onto the xz-plane and overlayed with the polygon mesh generated in the previous stage, the two will match up quite well. But in 3-dimensional space the polygon mesh may not adequately follow the height contour of the source mesh. This stage adds height detail such that the detail mesh will match the surfaces of source mesh on all axes. To accomplish this we iterate over all of the polygons and insert vertices along the polygon edges and within its surface whenever the polygon deviates excessively from the source mesh.

In the following example, the polygon mesh in the vicinity of a stairway matches on the xz-plane, but deviates by a large amount on the y-axis.

在添加了高度细节后,y轴匹配要好得多。

原文
The y-axis match is much better after height detail is added.
从技术上来讲,从寻路的角度来看,这一步不是必需的。凸多边形网格是生成适合使用寻路算法的图(graph)所需要的全部,而在上一阶段创建的多边形网格提供了所有必要的数据。这尤其适用于使用物理或ray-casting将agent放置在源网格表面的情况。事实上,Recast Navigation的Detour库只使用多边形网格来寻路。这个阶段生成的高度细节被认为是可选的,当包含它时,它仅用于完善由各种Detour函数返回的点的位置。

同样重要的是要注意,这个过程仍然只会产生原始网格表面的一个更好的近似。体素化过程已经决定了精确的位置是不可能的。除此之外,由于搜索性能和内存的考虑,过多的高度细节通常比太少的细节更糟糕。

原文
Technically, from a path-finding perspective, this step is not required. A convex polygon mesh is all that is needed to generate a graph suitable for use with path-finding algorithms, and the polygon mesh created in the last stage provides all the necessary data. This is especially the case for situations where physics or ray-casting is used to place an agent on the surface of the source mesh. In fact, Recast Navigation's Detour library only uses the polygon mesh for pathfinding. The height detail generated by this stage is considered optional, and when included it is only used to refine point positions returned by various Detour functions.

It is also important to note that this process will still only result in a better approximation of the surfaces of the original mesh. The voxelation process guarentees that exact positions will never be possible. Besides that, excess height detail is often worse than too little detail due to search performance and memory considerations.

首先:高度补丁(The Height Patch)

所以你觉得你不用再研究体素空间和高度场了?嗯,不完全是。为了添加高度细节,我们需要能够确定一个多边形的表面是否与导出它的开放高度场的span距离太远。高度补丁(height patch)即用于此目的。它包含与多边形相交的每个开放高度场网格位置的预期高度。基本上,它是具有以下特征的开放高度场的部分的简化切口(simplified cutout)。

  • 它只包含单个多边形的AABB的高度信息。
  • 它只包含每个网格位置(grid location)的地板高度(没有span)。
  • 对于每个网格位置,它只有一个高度(不重叠)。
原文
So you thought you were done with voxel space and heightfields? Well, not quite. In order to add height detail we need to be able to determine if the surface of a polygon is too far from the open heightfield spans from which it was derived. The height patch is used for this purpose. It contains the expected height for each open heightfield grid location a polygon intersects. Basically, it is a simplified cutout of a section of the open heightfield with the following characteristics.

It only contains height information for the AABB of a single polygon.
It only contains the floor height for each grid location. (No spans.)
It only has a single height for each grid location. (No overlapping.)

概览

该阶段的主要步骤如下,对于每个多边形:

  1. 对多边形的外壳边缘(hull edges)进行采样。向任何偏离高度补丁数据超过contourMaxDeviation的边添加顶点。
  2. 对多边形执行 Delaunay 三角形剖分
  3. 对多边形的内部表面进行采样。 如果表面与高度补丁数据的偏差超过 contourMaxDeviation 的值,则添加顶点。 更新新顶点的三角形剖分。
原文
The main steps in this stage are as follows. For each polygon:

1. Sample the hull edges of the polygon. Add vertices to any edge that deviates by more than the value of contourMaxDeviation from the height patch data.
2. Perform a Delaunay triangulation of the polygon.
3. Sample the internal surface of the polygon. Add vertices if the surface deviates by more than the value of contourMaxDeviation from the height patch data. Update the triangulation for any new vertices.

向多边形的边添加细节

这一步更好地将多边形边的高度与高度补丁中的数据匹配起来。它是两次采样的第一次,第二次采样处理多边形的表面。

为2D做好准备,对于下一组可视化,我们从侧面观察网格,y轴向上。

对于多边形中的每条边:根据contourSampleDistance的值将边分割成段。比如,如果边长是10个单位,采样距离为2个单位,那么将边分成5个等长段。并不是所有的“样本顶点”都会被使用,这些只是此时的潜在顶点。

原文
This step better matches the height of the polygon edges with the data in the height patch. It is the first of two sampling passes, with the second pass dealing with the polygon surface.

Get ready for some 2D. For the next group of visualizations, we are looking at the mesh from the side, with the y-axis up

For each edge in the polygon: Split the edge into segments based on the value of contourSampleDistance. E.g. If the edge is 10 units long and the sample distance is 2 units, then break the edge into 5 segments of equal length. Not all of these "sample vertices" will be used. These are only potential vertices at this point.

使用高度补丁数据将每个样本顶点的高度(y 值)对齐到高度场。

原文
Use the height patch data to snap the height (y-value) of each sample vertex to the heightfield.

检查样本顶点与原始边的距离,如果超过最大偏差,则插入距离原始边最远的样本顶点。

原文
Check the distance of the sample vertices from the original edge. If the maximum deviation is exceeded, insert the sample vertex that is farthest from the original edge.

重复距离检查,直到多边形的新部分完成。

原文
Repeat the distance checks until the new section of the polygon is complete.

三角形剖分(Triangulation)

网上有很多关于 Delaunay 三角形剖分的信息, 所以我在这里就不赘述了,我只想说它是在为边添加细节后用来对多边形进行三角形剖分的。在此之后,原始多边形不再存在,所有操作都在三角形网格上进行。

这是潜在的多次三角形剖分中的第一次。从这开始,当任何新顶点添加到网格时,都将发生重新三角形剖分。

原文
There is plenty of information on Delaunay triangulation on the web, so I won't cover it here except to say that it is used to triangulate the the polygon after adding detail to the edges. After this point the original polygon no longer exists. All operations are on a mesh of triangles.

This is the first of potentially multiple triangulations. From this point on, a re-triangulation will occur when any new vertex is added to the mesh.

向多边形内部表面添加细节

此时,我们有一个小的三角形网格,而不是一个单一的多边形。(或者,如果原来的多边形是一个三角形,并且在边缘细节步骤中没有添加新的顶点,我们可能仍然有一个单一的三角形。)所有的顶点仍然在网格的边上。在这一步中,我们检查网格的内部表面,看看它是否偏离高度补丁中的数据太多。

下一组可视化仍然是2D的。但是我们切换到xz平面的自上而下的视图。

在三角形网格的内表面添加高度细节的概念类似于在边缘添加细节。在网格的AABB的xz平面上构建一个样本顶点网格(grid)。间距基于contourSampleDistance的值。样本顶点的y轴值被对齐到高度补丁中的数据。

原文
At this point we have a small mesh of triangles instead of a single polygon. (Or, if the original polygon was a triangle and no new vertices were added in the edge detail step, we may still have a single triangle.) All vertices are still on the edge of the mesh. During this step, we check the internal surface of the mesh to see if it deviates too much from the data in the height patch.

The next group of visualizations is still in 2D. But we switch to a top-down view of the xz-plane.

The concept of adding height detail to the internal surface of the triangle mesh is similar to adding detail to the edges. A grid of sample vertices is built across the xz-plane of the mesh's AABB. The spacing is based on the value of contourSampleDistance. The y-axis values of the sample vertices are snapped to the data in the height patch.

网格(mesh)外的样本顶点被丢弃。

原文
The sample vertices outside of the mesh are discarded.

在幸存的样本顶点中,找出离三角形网格表面最远的那个。如果它比contourMaxDeviation的值更远,那么将它添加到网格中并重新进行三角形剖分。

原文
Of the surviving sample vertices, find the one that is farthest from the surface of the triangle mesh. If it is farther than the value of contourMaxDeviation, then add it to the mesh and re-triangulate.

重复这个过程,直到没有样本顶点超过contourMaxDeviation 的值。

原文
Repeat the process until no sample vertex exceeds the value of contourMaxDeviation.

结束

此阶段的其余工作是管理操作。由单个多边形创建的详细三角形网格被合并到一个网格中,并加载到一个TriangleMesh实例中。整个过程完成了,我们得到一个导航网格。

原文
The rest of the work in this stage is administrative operations. The detail triangle meshes that were created from the individual polygons are merged into a single mesh and loaded into the an instance of TriangleMesh. The entire process is complete. We have a navigation mesh.