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.

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.

Large

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.

Large

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.

Large

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.

Large

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.

Large

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.