构建导航网格的第一阶段是使用体素化(voxelization)创建实体高度场(solid heightfield)。
构建类:SolidHeightfieldBuilder
数据类:SolidHeightfield
如果你需要回顾体素化过程中执行的操作,请参阅:处理过程概览。
实体高度场的创建
在检测到源网格的轴对齐包围盒,并创建实体高度场以保存体素信息后,我们对源网格中的每个多边形执行以下过程:
确定多边形在高度场网格上的覆盖区(footprint)。 这是多边形的 2D 轴对齐包围盒,它限定了找出与该多边形相交的网格列,所需要的相交测试次数。

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

我们使用以下信息向实体高度场添加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就被标记为可穿越。

更多高度场span标记
从技术上讲,源网格的体素化是竞争性的,高度场包含代表障碍空间的实体体素的span。span也有一个标志,指示其顶面是否被认为是可穿越的。 但是此标志仅根据与span相交的多边形的斜率来设置。现在是进行更多过滤的好时机。此过滤从某些span中删除可穿越标志。
有两种类型的过滤:
首先,如果在span上方有太近的障碍物,那么span的顶面是不能穿越的。想象一张桌子放在地板上,桌子下面的地板表面是平的,但由于不能在上面行走,所以不能被认为是可穿越的。

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

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