Navigation Mesh Generation

For my graduation project, I decided to dive into researching navigation systems with a specific focus on navigation meshes as I was very familiar with the built-in systems provided by game engines such as Unreal and Unity, but I had no knowledge of how navigation meshes were working and generated under the hood.

Looking into games such as "Sunset Overdrive" and into the aforementioned engines, I came into contact with Recast and its voxelized based approach to creating navmeshes.

Starting from there and with the excellent reference material offered by CritterAI, I created a custom implementation of it into Unreal.
The intended outcome of the project was ultimately to learn about navigation meshes and about their possibilities and limits.

The code for the project can be found on my Github.

Project Information

Development Time: 24 Weeks (Ongoing)

Made in : Unreal Engine 4

Team Size : 1

Platform Support : Windows

Software Used & Languages

Github

Visual Studio

Unreal Engine 4

Trello

C++

Detailed Information

Voxelization & Solid Heightfield

The first step of the Navmesh generation.
During voxelization, the source geometry is abstracted into a heightfield - a 3D grid of voxels - that represents obstructed space.

The obstructed space is found by iterating through all the polygons of the source mesh, filtering out the ones that do not comply with certain conditions (example: inclination over a certain angle).

The single polygons are then expanded through the vertex coordinates to find the AABB surrounding them and detect to which column/s of the 3D voxel grid they belong to.

Finally, a clipping is performed to find the resulting polygon between the voxel column/s and the original polygon mesh and determine is min-max height.

Visual representation of the Sutherland -Hodgeman algorithm used to clip a polygon inside a AABB box.

Subdivision of the polygons of the geometries into voxels to create the Solid Heightfield.

Aggregation of the voxels into columns, representing the solid area of a geometry.

Open Heightfield & Region Generation

In this second stage, a detection and definition of the traversable solid surface are done by using the space data retrieved from the solid heightfield.

The solid heightfield is then translated into an open heightfield containing the potential traversable surfaces on top of the solid space.

Additional conditions are applied again to filter out the unnecessary/non-valid data (surfaces too close to obstructions and surfaces which do not have enough space above them).

From the open heightfield, a distance field is generated to evaluate the areas furthest from the borders of the geometry.
The distance field data are then used to create aggregates of surfaces called regions.

The regions are formed by using the watershed algorithm, which result is improved with additional steps by optimizing the region size and removing the island regions that are too small.

Visual representation of the Open Heightfield and how the data are filtered based on height (the minimum height parameter can be tweaked).

Visual representation of the Distance Field

From the distance field, regions are generated using the watershed algorithm.

Contour & Polygon Mesh Generation

In the third and final stage, an iteration through the edge region data is done to find the contours defining the single regions.

These contours, the raw contours, formed by the vertices derived from the corner of the spans, are reduced to simplified contours, by keeping only the mandatory vertices, the ones located on the edges between regions.

Starting from the mandatory vertices the Douglas-Pecker algorithm is then applied to select which additional vertices from the raw contour need to be added to the simplified one.

From the simplified contours, triangulation is performed to detect all the triangles it is possible to generate based on the vertices available.

According to the conditions established (a number specifying how many vertices the polygons generating the navmesh can have), an additional step can be performed to merge the triangles into more complex polygons.

Visual representation of the Simplified Contour.

From the simplified contour, the Polygon Mesh is generated. In the image above the polygons can be merged up to 6 sides.

Unreal Integration & Navmesh Controller

The system has been then integrated into the engine as a replacement for the default navigation system provided.

A controller has also been added (the controller automatically spawns when the NavBound component, the default one provided by Unreal which specifies the area affected by the navmesh) to allow the user to have total control over the navmesh parameter and control them directly inside the editor.

Demo showing the navmesh controller in action inside the Unreal editor.