Differences Between NMGen and Recast

This page covers the high level functional and structural differences between NMGen and Recast. It will be useful to those moving back and forth between the two.  Further differences are documented within NMGen code comments.

Functional Differences

Follows are the main functional differences between NMGen and Recast.

NMGen is Scoped Less Than Recast

NMGen implements a subset of the functionality found in Recast v1.4. Specifically the static mesh functionality found in the Sample_StateMeshSimple.cpp handleBuild() operation.

Exception: Certain algorithms in the DetailMeshBuilder were adapted from post-1.4 Recast code. Mikko was making useful updates to Recast at the same time DetailMeshBuilder was being created. So some of his post v1.4 updates were incorporated.

NMGen is Static

Mikko is continually enhancing Recast, while the NMGen code base will likely only get bug fixes.

Conservative Region Expansion

See: useConservativeExpansion

This is a functionality not implemented by Recast. While experimenting with region generation I found that I was sometimes getting poorly formed regions. Specifically, regions that flow partly or fully around open spaces, and regions that have long single width voxel offshoots. So I added this functionality.

Structural Differences

Follows are the high level differences in code structure.

Functionality and Data Mapping

This table contains the mapping of Recast functionality and data structures to NMGen classes. The Recast source files can be obtained from the download section of the Recast site.

Functionality Recast Operation/Structure Recast Source NMGen Class
Entry Point handleBuild Sample_SoloMeshSimple.cpp NavmeshGenerator
Voxelization rcCreateHeightfield
rcMarkWalkableTriangles
rcRasterizeTriangles
rcFilterLedgeSpans
rcFilterWalkableLowHeightSpans

Recast.cpp
Recast.cpp
RecastRasterization.cpp
RecastFilter.cpp
RecastFilter.cpp

SolidHeightfieldBuilder
Solid Heightfield Data rcHeightfield Recast.h SolidHeightfield
Region Generation rcBuildCompactHeightfield
rcBuildDistanceField
rcBuildRegions
Recast.cpp
RecastRegion.cpp
RecastRegion.cpp
OpenHeightfieldBuilder
Region Heightfield Data rcCompactHeightfield Recast.h OpenHeightfield
Contour Generation rcBuildContours RecastContour.cpp ContourSetBuilder
Contour Data rcContourSet Recast.h ContourSet
Polygon Mesh Generation rcBuildPolyMesh RecastMesh.cpp PolyMeshFieldBuilder
Polygon Mesh Data rcPolyMesh Recast.h PolyMeshField
Final Navmesh Generation rcBuildPolyMeshDetail RecastMeshDetail.cpp DetailMeshBuilder
Final Navmesh Data rcPolyMeshDetail Recast.h TriangleMesh

Heightfield Nomenclature

The heightfield grid in Recast is defined by width and height.  In NMGen, the grid is defined by width and depth.

Recast width == NMGen width
Recast height == NMGen depth

In both Recast and NMGen, the spans represent height within columns above the base grid.

rcCompactHeightfield versus OpenHeightfield

While the Recast rcCompactHeightfield structure and NMGen OpenHeightField class perform the same functionality within the two code bases, they have very different internal structures.

Two of the highest priorities for Recast are performance and minimizing memory footprint.  So the internal structure of rcCompactHeightfield is implemented very differently from rcHeightfield, even though the information contained by both is similar.

The main priority in NMGen is usefulness for study.  So there was no reason to radically diverge the structure of the SolidHeightfield and OpenHeightfield classes.  On the other hand, keeping them similar makes the code easier to study and understand.

If you are coming from Recast, or going to Recast after studying NMGen, then take some extra time to understand rcCompactHeightfield, OpenHeightfield, and their differences.

Iterating Heightfields

NMGen hides the complexities of iterating heightfield spans using standard Java iterators.  E.g.:

    IHeightfieldIterator<HeightSpan> iter = heightField.dataIterator();
    while (iter.hasNext())
    {
        HeightSpan span = iter.next();
        // Do stuff...
    }

If you are going from NMGen to Recast, then it may take some time before you recognize the standard iteration patterns.  There are two main patterns.

For rcHeightfield structures:

    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
            {
                // Do stuff...
            }
        }
    }

For rcCompactHeightfield structures:

    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                const rcCompactSpan& s = chf.spans[i];
                // Do stuff...
            }
        }
    }