Region Generation

This page describes the second stage in building the navigation mesh, the generation of surface regions representing the traversable surface of the source geometry.

Source data class: SolidHeightfield
Builder class: OpenHeightfieldBuilder
Data class: OpenHeightfield

If you need a reminder of what is performed in this stage, refer back to the high level process.

It is much easier to visualize solid spans rather than open spans. So solid spans are used in most visualizations on this page. Just remember that most of the algorithms described here use open heightfield rather than solid heightfield data.

Create the Open Heightfield

As described in introduction to heightfields, the open heightfield represents the area above the spans of a solid heightfield. Creation of the open heightfield is relatively simple. Loop through all solid spans. If the span is flagged as traversable, then determine the open space between its maximum and the minimum of the next higher span in its column. These values form the floor and ceiling respectively of a new open span. If a solid span is the highest span in its particular column, its associated open span has its ceiling set to an arbitrary high value. (E.g. Integer.MAX_VALUE) The newly generated open spans form the open heightfield.

Large

Create Neighbor Links

We now have an open heightfield filled with unrelated open spans. The next step is to figure out which spans form potential surfaces of contiguous spans. This is accomplished through the creation of axis-neighbor links. The concept of axis-neighbors is covered in searching the neighborhood.

For each span, its axis-neighbor columns are searched for candidates. A span in the neighbor column is considered a neighbor span if both of the following conditions are met:

The step up or down between the floors of the two spans is less than the value of maxTraversableStep. This allows for surfaces such as stair steps and curbs to be detected as valid neighbors.

Large

The open space gap between the current and potential neighbor is large enough to be traversed. E.g. If an agent were to step from one span to the other, would it bash its head on the ceiling of the neighbor?

This is a gap check between potential neighbors. We already know that the floor-to-ceiling height is adequate for each individual span. That check was performed when building the solid heightfield. But there is no guarantee that the gap when moving between potential neighbors satisfies the same height requirement.

Also, while the below visualization shows an agent standing on a span, spans are rarely, if ever, large enough in size for this to happen. But it doesn't matter from the algorithm's perspective. If simulated movement from one span to another is invalid at a microscopic level, it isn't valid at the macroscopic level either.

Large

There is no need to search for and store links for all eight neighbors since, if needed, diagonal-neighbors can be found by doing a neighbor-of-neighbor link traversal. (See searching the neighborhood for more information.)

Create a Distance Field

A distance field consists of an estimate of how far each span is from its nearest border span. This information is needed by the algorithm that generates the regions.

A border span is a span that has less than eight neighbors. Border spans represent the boundary between the traversable surface of the source geometry and either obstructions (such as walls) or empty space. Empty space may be a drop off (such as the edge of a balcony or a cliff) or the edge of the source geometry.

The below example shows a special case in which a non-border span is improperly identified as a border span. This is a drawback of using the standard 8-neighbor search used by the distance field algorithm. However, in practice this does not cause problems.

Large

An example of a distance field:

Large

Create Regions

Everything up to this point has been performed in preparation for region creation. Regions are groups of contiguous spans that represent traversable surface areas. An important aspect of regions is that they form simple polygons when projected onto the xz-plane.

The watershed algorithm is used for initial region creation. Using the watershed analogy, the spans which are furthest from a border represent the lowest points in the watershed. A border span represents the highest possible water level. The main loop iterates, starting at the lowest point in the watershed, then increments with each loop until the highest allowed water level is reached. This slowly "floods" the spans starting at the lowest points. During each iteration of the loop, spans that are below the current water level are located and an attempt is made to either add them to exiting regions or create new regions. During the region expansion phase, if a newly flooded span borders an existing region, it is usually added to the region. Any newly flooded span that survives the region expansion phase is used as a seed for new region creation.

There are already some great visualizations of the watershed algorithm in Volumetric Cell-and-Portal Generation (PDF and Postscript) by Denis Haumont, Olivier Debeir, and François Sillion. So I won't attempt to reproduce any here.

The watershed algorithm isn't perfect. It can sometimes create regions that are problematic for later stages in the navigation mesh generation process. So after initial region generation, various algorithms are applied to clean things up. 

The algorithms are implemented by the FilterOutSmallRegions and CleanNullRegionBorders classes. Follows are some examples of the "fixes" applied to regions:

Island regions that are too small to be useful are discarded. (Flagged as un-walkable)

Large

Regions that are unnecessarily small are merged into larger regions. (No visualization.)

Sometimes the watershed algorithm will cause a region to flow around small null regions. In such cases the region is broken into two regions at the null region. (No visualization.)

Various span configurations can occur on the border of null regions that are problematic. For example: If a region wraps a corner by just one span, the contour generation step may create a self intersecting polygon. These problematic configurations are detected and eliminated.

Example: Before the algorithm is applied.

Large

Example: After the algorithm is applied.

Large

Where We Are

At the end of this step we have an open heightfield made up of regions representing the traversable surface of the source geometry.

Large