Navigation Mesh Generation

For my graduation project (half a year), 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: 20 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 Heighfield

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 Heighfield & 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. 

Disclaimer: As the project is still ongoing, there are still some steps missing to reach the final navmesh.
Again the code for the project can be found on my
Github.

 Copyright 2020 - Stefano Lazzaroni