【译】NMGen - 高度场简介

原文：http://www.critterai.org/projects/nmgen_study/heightfields.html

为了理解 NMGen 生成导航网格的过程，首先了解如何使用高度场（heightfields）来表示体素（voxel ）数据是很重要的。

高度场提供了良好的压缩和数据结构，这对于从几何图形中提取上表面信息特别有用。

基本的高度场结构

考虑欧几里得空间中任意位置的轴对齐的盒子，它的边界由最小和最大顶点定义。

现在将盒子切成宽度和深度相同的垂直列，这些列构成了一个网格。

现在沿高度轴（竖轴）以均匀的增量对列进行切片，将列分成与轴对齐的小盒子。 这种结构很好地表示了体素空间。

高度Span（Height Spans）

标准的Solid Span

考虑一列体素， 每个体素定义的区域要么是实体的（solid），代表有障碍的空间，要么是开放的（open），代表不包含任何障碍的空间。

通常我们只关心高度场的实体区域。所以我们合并列内连续的实体体素，得到一个实体体素的跨度（span），使得结构更简单。这是一个“高度跨度（heightspan）”，或简称“跨度（span）”。

将span放入高度场结构中，我们得到一个实体高度场。这是该区域内阻塞区域的一种表示方式。

特殊的Open Span

我们不只关心实体空间，许多算法都是在solid span上方的空间上操作的，Open height span用于表示这个空间。对于导航网格的生成来说，solid span的上表面是其最重要的部分。

需要注意的是，这不是实体空间的简单反转。如果一个高度场列不包含任何solid span，则它也没有任何open span。 最低的solid span以下的区域也被忽略，只有solid span上方的空间由open span来表示。

因此，open span使用“地板（floor）”和“天花板（ceiling）”的术语。open span的地板是其关联的solid span的顶部。 open span的天花板是它所属的列中下一个更高的solid span的底部。如果没有更高的solid span，则open span的天花板是任意的最大值，例如整数的最大值。

基础知识汇总

我们现在有了在高度场中表示体素信息所需的所有结构片段：

• 在欧几里得空间中具有位置的轴向包围盒。
• 宽度、深度和高度的分辨率信息。
• 用于存储span信息的列所组成的网格。
• 表示连续的实体空间或实体空间上方连续的开放空间的span。

杂项

搜索邻居

NMGen实现的高度场提供了一些操作，这些操作使得遍历所有span和列中的span变得容易，但是有些算法通常需要执行邻居搜索。

单元格列（Cell columns）有邻居...

Span可以有邻居，只有当邻居span在高度上与当前span足够接近时才被认为是邻居。只有开放的高度场实现提供了一种方法来搜索邻居span...

邻居通过它们从当前列或当前span开始的偏移量来引用。例如(referenceWidthIndex+widthOffset, referenceDepthIndex+depthOffset)

轴邻居（Axis-neighbors）是沿宽度轴/深度轴偏移的四个邻居:(- 1, 0) (0, 1) (1, 0) (0, -1)。

在所有的高度场实现中，轴邻居的搜索都以标准方式执行，从 (0, -1) 开始并使用标准索引沿顺时针方向进行。

对角线邻居（Diagonal-neighbors ）是四个沿着对角线轴偏移的邻居:(- 1, 1) (1, 1) (1, -1) (-1, -1)。

对角线邻居没有标准的搜索索引，通常的做法是顺时针查找轴邻居对应的对角线邻居。