[This is preliminary documentation and is subject to change.]

In order to use the advanced navigation mesh build features you will need to understand the core NMGen build process, and in order to understand that process you'll need to understand heightfields. There are two types of heightfields: voxel field, and vertex fields. Voxel fields include Heightfield and CompactHeightfield objects. Vertext fields include ContourSet and PolyMesh objects.

Basic Heightfield Structure

Consider an AABB at an arbitrary location in euclidean space. Its bounds are defined by a minimum and maximum vertex.

Heightfield: AABB

Now slice the box into vertical columns of uniform width and depth (XZCellSize). The columns make up a grid.

Heightfield: Columns

Now slice the columns in uniform increments up the height axis (YCellSize), breaking the columns into small axis-aligned boxes. The boxes represent a voxel field. The vertices at the eight corners of the boxes represent a vertex field.

Heightfield: Voxel Grid

Vertex fields are fairly easy to understand. They are simply a way of representing vertices laid out in a grid pattern. But voxel fields require a bit more explanation...

The Solid Heightfield

In this documentation, the term voxel is usually discarded in favor of span because spans are how voxel information is compressed by NMGen objects.

Consider a column of voxels. The area defined by each voxel is either solid, representing obstructed space, or open, representing space that does not contain any obstructions.

Heightfield: ColumnVoxels

We merge the contiguous solid voxels within the column and we get a span of solid voxels.

Heightfield: Solid Span

These solid spans, represented by the HeightfieldSpan structure, are combined to form a Heightfield representing obstructed space.

Heightfield: Solid Field

The Open Compact Heightfield

We don't only care about solid space. Many algorithms operate on the space above solid spans. For navigation mesh generation this is the most important part of solid space, its upper surface. Open spans represent this space.

It is important to note that this is not a simple inversion of the solid space. If an open heightfield column does not contain any solid spans, then it doesn't have any open spans. Also, the area below the lowest solid span is ignored. An open span extends from the top of a solid span to the bottom of the next higher solid span in the column. (Or to "infinity" if there is no higher solid span.)


Though it may not be obvious at first glance, this example is the open space representation of the previous example. Three open spans are fully visualized.

Heightfield: Open Field

The open spans, represented by the CompactSpan structure, are combined to form a CompactHeightfield representing open space.

See Also