构建导航网格的第一阶段是使用体素化(voxelization)创建实体高度场(solid heightfield)。

构建类:SolidHeightfieldBuilder
数据类:SolidHeightfield

如果你需要回顾体素化过程中执行的操作,请参阅:处理过程概览

原文

The Voxelization Process

The first stage in building the navigation mesh is the creation of a solid heightfield using voxelization.

Builder class: SolidHeightfieldBuilder
Data class: SolidHeightfield

If you need a reminder of what is performed in the voxelization process, refer back to the high level process.

实体高度场的创建

在检测到源网格的轴对齐包围盒,并创建实体高度场以保存体素信息后,我们对源网格中的每个多边形执行以下过程:

确定多边形在高度场网格上的覆盖区(footprint)。 这是多边形的 2D 轴对齐包围盒,它限定了找出与该多边形相交的网格列,所需要的相交测试次数。

原文

Creation of the Solid Heightfield

After the axis-aligned bounding box of the source mesh is detected and a solid heightfield created to hold the voxel information, we perform the following process for each polygon in the source mesh:

Determine the footprint of the polygon on the heightfield's grid. This is the 2D axis-aligned bounding box of the polygon and limits the number of intersection tests required to find the grid columns intersected by the polygon.

遍历覆盖区内的所有高度场网格列,并导出源多边形与网格列列相交的部分。 如果发生相交,则导出一个新的“裁剪(clipped)”多边形。 然后确定裁剪多边形的最小-最大高度。 这表示网格列被源多边形遮挡的部分。

原文
Loop through all heightfield grid columns within the footprint and derive the portion of the source polygon that intersects the column. If an intersection occurs, derive a new "clipped" polygon. Then determine the min-max height of the clipped polygon. This represents the portion of the column obstructed by the source polygon.

我们使用以下信息向实体高度场添加span信息:

  • 与多边形相交的网格列。
  • 裁剪多边形的最小-最大高度范围(网格列被阻挡的部分)。
  • 裁剪多边形的表面是否是可穿越(traversable)的。

最后一段数据是根据源多边形的 y 斜度和 maxTraversableSlope 的值确定的。如果源多边形的 y 斜度低于配置的设置(例如 45 度),则它的表面是可穿越的。

将新的span数据添加到高度场时,会发生以下情况:

  • 如果新span不与网格列中的任何已经存在的span相交,则会创建一个新span。如果新span与已经存在的span相交或被已经存在的span所包含,则合并这两个span。
  • 当新span与已经存在的span合并时,必须评估生成的聚合span是否是可穿越的。这个“可穿越标志”只适用于span的顶部表面。如果设置了,就意味着span顶部表示多边形,该多边形有足够低的斜率是可穿越的。
  • 如果新span的顶部高于它正在合并到的span,则新span的可穿越标志用于聚合span。
  • 如果新span的顶部低于它正在合并到的span,那么我们不关心新span的标志,新span的标志被丢弃。
  • 如果新span的顶部与其合并到的span处于同一高度,则如果其中任意一个被认为是可穿越的,聚合span就被标记为可穿越。
原文
We use the following information to add span information to the solid heightfield:

  • The grid column that is intersected by the polygon.
  • The min-max height range of the clipped polygon. (The portion of the column that is obstructed.)
  • Whether the surface of the clipped polygon is considered traversable.

That final piece of data is decided based on the y-incline of the source polygon and the value of maxTraversableSlope. If the source polygon's y-incline is below the configured setting, 45 degrees for example, then it's surface is traversable.
When new span data is added to the heightfield, the following occurs:
If the new span does not intersect any existing spans within the column, a new span is created. If the new span intersects with or is encompassed by an existing span, then the two spans are merged.

When a new span is merged with an existing span, an evaluation of whether or not the resulting aggregate span is traversable must be performed. This "traversable flag" only applies to the top surface of the span. If set, it means that the the top of the span represents polygons with a low enough slope to be traversable.
If the new span's top is higher than the span it is being merged into, then the new span's traversable flag is used for the aggregate span.
If the new span's top is lower than the span it is being merged into, then we don't care about the flag of the new span. The new span's flag is discarded.
If the new span's top is at the same height as the span it is being merged into, then if either is considered traversable, the aggregate span is flagged as traversable.

更多高度场span标记

从技术上讲,源网格的体素化是竞争性的,高度场包含代表障碍空间的实体体素的span。span也有一个标志,指示其顶面是否被认为是可穿越的。 但是此标志仅根据与span相交的多边形的斜率来设置。现在是进行更多过滤的好时机。此过滤从某些span中删除可穿越标志。

有两种类型的过滤:

首先,如果在span上方有太近的障碍物,那么span的顶面是不能穿越的。想象一张桌子放在地板上,桌子下面的地板表面是平的,但由于不能在上面行走,所以不能被认为是可穿越的。

原文

More Heightfield Span Flagging

Technically, the voxelization of the source mesh is compete and the heightfield contains spans of solid voxels representing obstructed space. The span's also have a flag that indicates whether the top surface is considered traversable. But this flag was set based only on the slope of the polygons that intersected the span. Now is a good time to do some more filtering. This filtering removes the traversable flags from some spans.

Two types of filtering occurs:

First, the top surface of a span is not traversable if there is an obstruction above it that is too close. Visualize a table set on a floor. The surface of the floor below the table is flat, but it is not considered traversable since it can't be walked on.

一个可选的过滤器涉及窗台检测(ledge detection)。如果从span的顶部向下走到轴邻居超过了某个配置值,那么该span就被认为是一个窗台(ledge),是不可穿越的。

原文
An optional filter involves ledge detection. If stepping from the top of the span down to an axis-neighbor exceeds a configurable value, then the span is considered a ledge and not traversable.

我们在哪

在这一步结束时,我们有一个高度场,它表示被源网格阻塞的区域。已执行了初始过滤,以将障碍区域的顶面标记为可穿越或不可穿越。

原文

Where We Are

At the end of this step we have a heightfield that represents the area obstructed by the source mesh. Initial filtering has been performed to mark the top surface of the obstructed area as traversable or not.