[This is preliminary documentation and is subject to change.]
This topic covers the core process used by NMGen to create polygon data that will represent the navigation mesh surface. There are many variations on the mesh generation process, but they all include these steps.
The IncrementalBuilder extension implements this process.
The high level process is as follows:
- Voxelization: Create a solid heightfield from the source geometry representing obstructed space.
- Generate Regions: Detect the upper surface of the solid heightfield and divide it up into regions of contiguous spans.
- Generate Contours: Detect the contours of the regions and form them into simple polygons.
- Generate Polygon Mesh: Sub-divide the contours into convex polygons.
- Generate Height Detail: Triangulate the polygon mesh and add height detail. (Optional)
Core Class: Heightfield
During voxelization the source geometry is abstracted into a heightfield which represents obstructed space. Then some initial culling of un-walkable surfaces is performed.
Each triangle in the source geometry is voxelized using conservative voxelization and added to the field. Conservative voxelization is an algorithm that ensures the triangle surfaces are completely encompassed by the the generated voxels.
After voxelization, the solid heightfield contains spans that completely encompass the surface of all polygons in the source geometry.
Core Class: CompactHeightfield
The goal of this stage is to further define what portion of the solid surface is traversable, and to segregate the traversable areas into contiguous regions of spans (surfaces) that can eventually be formed into simple polygons.
The first step is to translate the solid heightfield into an open heightfield which represents the potential traversable surfaces on top of the solid space. An open heightfield represents the potential floor area on the surface of solid space.
In the below example, the green area represents the floor defined by the open spans. These correspond to the top of all traversable spans in the solid heightfield. Note that walls, areas under the tables, and some thin areas such as the balcony banisters were culled during the solid heightfield generation process. Some un-walkable areas such as table tops, the stair banisters, and thin wall ledges still show as traversable at this point.
Next, further culling of un-walkable spans occurs. At the end of the process, open spans are only considered traversable if they pass the following tests:
- The span is not too close to an obstruction. (Such as walls, furniture, etc.) (WalkableRadius)
- The span has sufficient unobstructed space above its floor. (Agents can legally walk on the span without colliding with objects above the span.) (WalkableHeight)
Neighbor information is generated for all surviving open spans to help group them together into true surface areas. The algorithm takes into account a maximum vertical step threshold to determine which spans can connect. (WalkableStep) This permits structures such as stairs, curbs, table tops, etc. to be properly taken into account. For example, spans that make up different steps in a stairway will be connected as neighbors. But spans on a table top will not be connected to spans that make up the adjacent floor.
Regions are generated using the neighbor information and the watershed algorithm. Region size is optimized and island regions too small to be of use (e.g. table tops) are culled. (MinRegionArea)
The below example shows regions. Note that regions flow up the stairs, even though the spans that make up stairways don't actually connect. Also note that the table tops, stair banisters, and all other un-walkable surfaces that made it through the solid heightfield generation process have been successfully culled. (Black indicates culled spans.)
At the end of this stage, the traversable surface is represented by regions of connected spans.
Core Class: ContourSet
The contours of the regions are 'walked', forming simple polygons. This is the first step in the process of moving from voxel space back into vector space.
First, highly detailed polygons are generated from the regions.
Next, various algorithms are used to accomplish the following:
- Simplify the edges between adjacent polygons. (The portals between regions.)
- Simplify the border edges (Border edges are the contour edges that connect to empty or obstructed space.) (EdgeMaxDeviation)
- Optimize the length of the border edges. (Borders that are too long can form non-optimal triangles later in the process.) (MaxEdgeLength)
This next example shows the contours after these algorithms have been run.
At the end of this stage, the traversable surface is represented by simple polygons.
Convex Polygon Generation
Core Class: PolyMesh
Many algorithms can only be used with convex polygons. So this step subdivides the simple polygons that make up the contours into a mesh of convex polygons.
This is the mesh used for most pathfinding purposes.
Below you can see that a mixture of concave polygons have been formed from the contours.
At the end of this stage, the traversable surface is represented by a mesh of convex polygons.
Height Detail Generation
Core Class: PolyMeshDetail
In the final stage, the convex polygon mesh is triangulated using Delaunay triangulation so that height detail can be added. Vertices are added internally and to the edges of polygons to ensure the original geometry's surface is adequately followed. (DetailSampleDistance and DetailMaxDeviation)
Technically, this is an optional step. The detail mesh is not required for pathfinding. But certain queries will return more accurate height data if the detail mesh is available.