【译】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的天花板是任意的最大值,例如整数的最大值。

尽管乍一看可能并不明显,但这个示例是前一个示例的开放空间表示。 可视化了三个open span。

基础知识汇总

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

  • 在欧几里得空间中具有位置的轴向包围盒。
  • 宽度、深度和高度的分辨率信息。
  • 用于存储span信息的列所组成的网格。
  • 表示连续的实体空间或实体空间上方连续的开放空间的span。
“cellHeight”的意思有点模糊,它表示单元格列内的高度增量/分辨率,不表示单元格列的高度。
“Grid location”、“cell”和“cell column”是同义词。

杂项

搜索邻居

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

单元格列(Cell columns)有邻居…

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

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

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

IndexNeighbor Offset
0(-1, 0)
1(0, 1)
2(1, 0)
3(0, -1)

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

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

0 0 投票数
文章评分
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论

近期文章

最新评论

分类

标签

归档

0
希望看到您的想法,请发表评论。x
()
x