docs

[manuel3108]

Hey! First of all thanks for that port, im hoping that it will help me avoid writing a lot of code. But we will see this over the next weeks.

Maybe im totally missing something, but for me it looks like there are no docs at all, not even a readme. The main readme links two two test that in theory should get you started.

RecastSoloMeshTest

is a nice starting point for seeing how it works and drawing the detected triangles on the scene. The readme suggest that you should find out how to create a navmesh "To create a NavMesh, please check out". Sadly this is not at all shown in this test, as it's stops way earlier. Also it uses RcSimpleInputGeomProvider instead of DemoInputGeomProvider (RcSimpleInputGeomProvider has 3 not implemented methods, that cause problems later on)

FindPathTest

This test is ok, if the previous one actually showed how to create a navmesh. But since this is not currently the case, it's hard to figure out what its doing. Also the most curcial part FindNearestPoly is not showcased here.

Having some small actual docs would probably saved me hours. Either with the github wiki functionality or in a small readme.

For reference i have attached the code i came up today. It's written in combination with raylib-cs, so you might not be able to re-use everything. There are probably tons of bugs and misconceptions, but at a first glance from the debugger it seems to be working as expected. The code is copied togther from different places in the source code, that's why there are some extensive comments as well.

Code

using DotRecast.Core;
using DotRecast.Core.Collections;
using DotRecast.Core.Numerics;
using DotRecast.Detour;
using DotRecast.Recast;
using DotRecast.Recast.Toolset.Builder;
using DotRecast.Recast.Toolset.Geom;

namespace TheHub.Ecs.Utils;

public unsafe class PassengerPathDebug
{
    private const float m_cellSize = 0.3f;
    private const float m_cellHeight = 0.2f;
    private const float m_agentHeight = 2.0f;
    private const float m_agentRadius = 0.6f;
    private const float m_agentMaxClimb = 0.9f;
    private const float m_agentMaxSlope = 45.0f;
    private const int m_regionMinSize = 8;
    private const int m_regionMergeSize = 20;
    private const float m_edgeMaxLen = 6.0f;
    private const float m_edgeMaxError = 0.5f;
    private const int m_vertsPerPoly = 6;
    private const float m_detailSampleDist = 6.0f;
    private const float m_detailSampleMaxError = 1.0f;
    private const int tileSize = 200; // TODO what is this?
    private const int borderSize = 1; // TODO what is this?
    private readonly RcPartition m_partitionType = RcPartition.WATERSHED;
    private Material _material;
    private Mesh _mesh;
    private RcPolyMeshDetail _polyMesh;
    private Matrix4x4 _transform;

    public void Initialize(GameData world)
    {
        // raylib-cs specific stuff
        // _mesh = GenMeshCube(1, 1, 1);
        var model = world.AssetManager.TrainLocomotiveModel;
        _mesh = model.Meshes[0];
        _transform = MathUtils.CreateTransform(new Vector3(0, 0, 0), Quaternion.Identity, new Vector3(10, 10, 10), false);
        _material = LoadMaterialDefault();
        _material.Maps[(int)MaterialMapIndex.Albedo].Color = Color.Purple;
        var (verticesRecast, indexesRecast) = InternalSetup();

        // dotrecast
        var navMeshBuildResult = DoDotRecastStuff(verticesRecast, indexesRecast);
        _polyMesh = navMeshBuildResult.RecastBuilderResults[0].MeshDetail;

        var start = new RcVec3f(0, 10, 0);
        var end = new Vector3(5, 10, 5);

        var query = new DtNavMeshQuery(navMeshBuildResult.NavMesh);

        var filter = new DtQueryDefaultFilter();
        // If you didn’t customize areas, default is usually fine.
        // Otherwise you’ll set include/exclude flags here.

        var extents = new RcVec3f(2f, 4f, 2f); // x,y,z half-extents (tune this)

        var startRef = query.FindNearestPoly(start, extents * 2f, filter, out var nearestStart, out var nearestStartPt, out var isOverPolyStart);
        var endRef = query.FindNearestPoly(end, extents * 2f, filter, out var nearestEnd, out var nearestEndPt, out var isOverPolyEnd);

        if (startRef.Succeeded())
        {
            var test123 = 0f;
        }

        var path = new RcFixedArray256<long>();

        var polyPath = query.FindPath(nearestStart, nearestEnd, nearestStartPt, nearestEndPt, filter, path.AsSpan(), out var pathCount, 10000);

        if (polyPath.Succeeded())
        {
            var test343 = 0;
        }

        var actualPathPoints = new RcFixedArray256<DtStraightPath>();
        query.FindStraightPath(nearestStartPt, nearestEndPt, path.AsSpan(), pathCount, actualPathPoints.AsSpan(), out var straightPathCount, 10000,
            0);

        var test = 0;
    }

    // converts raylib stuff to dotrecast - not relevant
    private (float[] vertecies, int[] indexes) InternalSetup()
    {

        // get vertices
        var vertCount = _mesh.VertexCount;
        var floatCount = vertCount * 3;
        var verts = new float[floatCount];
        var srcVertices = _mesh.Vertices;
        for (var i = 0; i < floatCount; i++)
            verts[i] = srcVertices[i];

        // get indices
        var triCount = _mesh.TriangleCount;
        var indexCount = triCount * 3;
        var indexes = new ushort[indexCount];
        var srcIndices = _mesh.Indices;

        for (var i = 0; i < indexCount; i++)
            indexes[i] = srcIndices[i];

        // transform vertices
        var vertices = new List<Vector3>();
        for (var i = 0; i < vertCount; i++)
        {
            var o = i * 3;
            Vector3 v = new(
                verts[o + 0],
                verts[o + 1],
                verts[o + 2]
            );

            v = Vector3.Transform(v, _transform);

            vertices.Add(v);
        }

        // filter out planes that do not face up
        var verticesUp = new List<Vector3>();
        var indexesUp = new List<int>();
        for (var i = 0; i < indexes.Length; i += 3)
        {
            var i1 = indexes[i];
            var i2 = indexes[i + 1];
            var i3 = indexes[i + 2];

            var v1 = vertices[i1];
            var v2 = vertices[i2];
            var v3 = vertices[i3];

            var e1 = v2 - v1;
            var e2 = v3 - v1;
            var normal = Vector3.Normalize(Vector3.Cross(e1, e2));
            var facesUp = normal.Y > 0f;

            if (facesUp)
            {
                verticesUp.Add(v1);
                indexesUp.Add(verticesUp.Count - 1);

                verticesUp.Add(v2);
                indexesUp.Add(verticesUp.Count - 1);

                verticesUp.Add(v3);
                indexesUp.Add(verticesUp.Count - 1);

            }

        }

        // prepare for dotrecast
        var verticesRecast = verticesUp
            .SelectMany(x => new[] { x.X, x.Y, x.Z })
            .ToArray();
        var indexesRecast = indexesUp.Select(x => x).ToArray();
        return (verticesRecast, indexesRecast);
    }

    private NavMeshBuildResult DoDotRecastStuff(float[] verticesRecast, int[] indexesRecast)
    {

        var geomProvider = new DemoInputGeomProvider(verticesRecast, indexesRecast);
        var bmin = geomProvider.GetMeshBoundsMin();
        var bmax = geomProvider.GetMeshBoundsMax();
        var m_ctx = new RcContext();

        //
        // Step 1. Initialize build config.
        //
        var cfg = new RcConfig(
            true,
            tileSize,
            tileSize,
            borderSize,
            m_partitionType,
            m_cellSize, m_cellHeight,
            m_agentMaxSlope, m_agentHeight, m_agentRadius, m_agentMaxClimb,
            m_regionMinSize, m_regionMergeSize,
            m_edgeMaxLen, m_edgeMaxError,
            m_vertsPerPoly,
            m_detailSampleDist, m_detailSampleMaxError,
            true, true, true,
            SampleAreaModifications.SAMPLE_AREAMOD_WALKABLE, true);
        var bcfg = new RcBuilderConfig(cfg, bmin, bmax);

        //
        // Step 2. Rasterize input polygon soup.
        //

        // Allocate voxel heightfield where we rasterize our input data to.
        var m_solid = new RcHeightfield(bcfg.width, bcfg.height, bcfg.bmin, bcfg.bmax, cfg.Cs, cfg.Ch, cfg.BorderSize);

        foreach (var geom in geomProvider.Meshes())
        {
            var verts = geom.GetVerts();
            var tris = geom.GetTris();
            var ntris = tris.Length / 3;

            // Allocate array that can hold triangle area types.
            // If you have multiple meshes you need to process, allocate
            // and array which can hold the max number of triangles you need to process.

            // Find triangles which are walkable based on their slope and rasterize them.
            // If your input data is multiple meshes, you can transform them here, calculate
            // the are type for each of the meshes and rasterize them.
            var m_triareas = RcRecast.MarkWalkableTriangles(m_ctx, cfg.WalkableSlopeAngle, verts, tris, ntris, cfg.WalkableAreaMod);
            RcRasterizations.RasterizeTriangles(m_ctx, verts, tris, m_triareas, ntris, m_solid, cfg.WalkableClimb);
        }

        //
        // Step 3. Filter walkable surfaces.
        //

        // Once all geometry is rasterized, we do initial pass of filtering to
        // remove unwanted overhangs caused by the conservative rasterization
        // as well as filter spans where the character cannot possibly stand.
        RcFilters.FilterLowHangingWalkableObstacles(m_ctx, cfg.WalkableClimb, m_solid);
        RcFilters.FilterLedgeSpans(m_ctx, cfg.WalkableHeight, cfg.WalkableClimb, m_solid);
        RcFilters.FilterWalkableLowHeightSpans(m_ctx, cfg.WalkableHeight, m_solid);

        //
        // Step 4. Partition walkable surface to simple regions.
        //

        // Compact the heightfield so that it is faster to handle from now on.
        // This will result more cache coherent data as well as the neighbors
        // between walkable cells will be calculated.
        var m_chf = RcCompacts.BuildCompactHeightfield(m_ctx, cfg.WalkableHeight, cfg.WalkableClimb, m_solid);

        // Erode the walkable area by agent radius.
        RcAreas.ErodeWalkableArea(m_ctx, cfg.WalkableRadius, m_chf);

        // (Optional) Mark areas.
        /*
         * ConvexVolume vols = m_geom->GetConvexVolumes(); for (int i = 0; i < m_geom->GetConvexVolumeCount(); ++i)
         * RcMarkConvexPolyArea(m_ctx, vols[i].verts, vols[i].nverts, vols[i].hmin, vols[i].hmax, (unsigned
         * char)vols[i].area, *m_chf);
         */

        // Partition the heightfield so that we can use simple algorithm later
        // to triangulate the walkable areas.
        // There are 3 partitioning methods, each with some pros and cons:
        // 1) Watershed partitioning
        // - the classic Recast partitioning
        // - creates the nicest tessellation
        // - usually slowest
        // - partitions the heightfield into nice regions without holes or
        // overlaps
        // - the are some corner cases where this method creates produces holes
        // and overlaps
        // - holes may appear when a small obstacles is close to large open area
        // (triangulation can handle this)
        // - overlaps may occur if you have narrow spiral corridors (i.e
        // stairs), this make triangulation to fail
        // * generally the best choice if you precompute the navmesh, use this
        // if you have large open areas
        // 2) Monotone partioning
        // - fastest
        // - partitions the heightfield into regions without holes and overlaps
        // (guaranteed)
        // - creates long thin polygons, which sometimes causes paths with
        // detours
        // * use this if you want fast navmesh generation
        // 3) Layer partitoining
        // - quite fast
        // - partitions the heighfield into non-overlapping regions
        // - relies on the triangulation code to cope with holes (thus slower
        // than monotone partitioning)
        // - produces better triangles than monotone partitioning
        // - does not have the corner cases of watershed partitioning
        // - can be slow and create a bit ugly tessellation (still better than
        // monotone)
        // if you have large open areas with small obstacles (not a problem if
        // you use tiles)
        // * good choice to use for tiled navmesh with medium and small sized
        // tiles
        if (m_partitionType == RcPartition.WATERSHED)
        {
            // Prepare for region partitioning, by calculating distance field
            // along the walkable surface.
            RcRegions.BuildDistanceField(m_ctx, m_chf);
            // Partition the walkable surface into simple regions without holes.
            RcRegions.BuildRegions(m_ctx, m_chf, cfg.MinRegionArea, cfg.MergeRegionArea);
        }
        else if (m_partitionType == RcPartition.MONOTONE)
        {
            // Partition the walkable surface into simple regions without holes.
            // Monotone partitioning does not need distancefield.
            RcRegions.BuildRegionsMonotone(m_ctx, m_chf, cfg.MinRegionArea, cfg.MergeRegionArea);
        }
        else
        {
            // Partition the walkable surface into simple regions without holes.
            RcRegions.BuildLayerRegions(m_ctx, m_chf, cfg.MinRegionArea);
        }

        //
        // Step 5. Trace and simplify region contours.
        //

        // Create contours.
        var m_cset = RcContours.BuildContours(m_ctx, m_chf, cfg.MaxSimplificationError, cfg.MaxEdgeLen,
            RcBuildContoursFlags.RC_CONTOUR_TESS_WALL_EDGES);

        //
        // Step 6. Build polygons mesh from contours.
        //

        // Build polygon navmesh from the contours.
        var m_pmesh = RcMeshs.BuildPolyMesh(m_ctx, m_cset, cfg.MaxVertsPerPoly);

        //
        // Step 7. Create detail mesh which allows to access approximate height
        // on each polygon.
        //

        var m_dmesh = RcMeshDetails.BuildPolyMeshDetail(m_ctx, m_pmesh, m_chf, cfg.DetailSampleDist,
            cfg.DetailSampleMaxError);


        var rcBuilder = new RcBuilder();
        var results = rcBuilder.BuildTiles(geomProvider, cfg, true, true, Environment.ProcessorCount + 1, Task.Factory);
        var navMeshBuildResult = new NavMeshBuildResult(cfg, results);

        var tileNavMeshBuilder = new TileNavMeshBuilder();
        var tileMeshData = tileNavMeshBuilder.BuildMeshData(geomProvider, m_cellSize, m_cellHeight, m_agentHeight, m_agentRadius, m_agentMaxClimb,
            navMeshBuildResult.RecastBuilderResults);
        var tileNavMesh = tileNavMeshBuilder.BuildNavMesh(geomProvider, tileMeshData, m_cellSize, tileSize, m_vertsPerPoly);
        return new NavMeshBuildResult(navMeshBuildResult.Cfg, navMeshBuildResult.RecastBuilderResults, tileNavMesh);
    }
 
    // again, this is raylib related, so you might not be able to copy this one
    public void Draw()
    {
        DrawMesh(_mesh, _material, Matrix4x4.Transpose(_transform));

        for (var m = 0; m < _polyMesh.nmeshes; m++)
        {
            var mb = m * 4;

            var vbase = _polyMesh.meshes[mb + 0];
            var vcount = _polyMesh.meshes[mb + 1];
            var tbase = _polyMesh.meshes[mb + 2];
            var tcount = _polyMesh.meshes[mb + 3];

            for (var t = 0; t < tcount; t++)
            {
                var ti = (tbase + t) * 4;

                var i0 = (vbase + _polyMesh.tris[ti + 0]) * 3;
                var i1 = (vbase + _polyMesh.tris[ti + 1]) * 3;
                var i2 = (vbase + _polyMesh.tris[ti + 2]) * 3;

                var v0 = new Vector3(
                    _polyMesh.verts[i0], _polyMesh.verts[i0 + 1], _polyMesh.verts[i0 + 2]);
                var v1 = new Vector3(
                    _polyMesh.verts[i1], _polyMesh.verts[i1 + 1], _polyMesh.verts[i1 + 2]);
                var v2 = new Vector3(
                    _polyMesh.verts[i2], _polyMesh.verts[i2 + 1], _polyMesh.verts[i2 + 2]);

                DrawTriangle3D(v0, v1, v2, Color.Green);
                DrawLine3D(v0, v1, Color.Red);
                DrawLine3D(v1, v2, Color.Red);
                DrawLine3D(v2, v0, Color.Red);
            }
        }
    }
}

[manuel3108]

Actually i found a extremly simple way to do all that. Yes, that's it. That's all you need to do to generate a NavMesh. The pathfinding code from above still applies.

var geomProvider = new RcSimpleInputGeomProvider(verticesRecast, indicesRecast);
var bMin = geomProvider.GetMeshBoundsMin();
var bMax = geomProvider.GetMeshBoundsMax();

var cfg = new RcConfig(
    config.PartitionType,
    config.CellSize, config.CellSize,
    config.AgentMaxSlope, config.AgentHeight, config.AgentRadius, config.AgentMaxClimb,
    config.RegionMinSize, config.RegionMergeSize,
    config.EdgeMaxLen, config.EdgeMaxError,
    config.VertsPerPoly,
    config.DetailSampleDist, config.DetailSampleMaxError,
    true, true, true,
    SampleAreaModifications.SAMPLE_AREAMOD_WALKABLE, true);
var builderConfig = new RcBuilderConfig(cfg, bMin, bMax);

var rcBuilder = new RcBuilder();
var rcBuilderResult = rcBuilder.Build(geomProvider, builderConfig, true);
return rcBuilderResult.MeshDetail;

[ikpil]

I apologize for the lack of clarity in the manual.
I’ve been relying on the unit tests to serve as the primary documentation for the time being.

It appears that RcSimpleInputGeomProvider does indeed have some issues. I agree that it should either be restricted for use only in unit tests or have its current functionality disabled to prevent confusion. I will make sure to address this in a future update.