Local Clearance Triangulation in NavMeshes

[roland]

Hello!

Thanks for your response! I already came up with a good enough solution which involves calculating the path through a tiled navmesh’s polygon centers plus interpolating the resulting path. At the end I convert the path to a CatmullRomSpline and the result looks quite satisfying.

    private _getPolyCenters(startPos: IVector3Like, endPos: IVector3Like) {
        if (!this._navigationPlugin) {
            return;
        }

        const extents = new Vector3(1, 1, 1);
        const filter = undefined;
        const options = {
            extents,
            filter,
        };
        const startRef = this._navigationPlugin.navMeshQuery.findNearestPoly(
            startPos,
            options
        ).nearestRef;
        const endRef = this._navigationPlugin.navMeshQuery.findNearestPoly(
            endPos,
            options
        ).nearestRef;

        const maxPathPolys = 32;
        const path = this._navigationPlugin.navMeshQuery.findPath(
            startRef,
            endRef,
            startPos,
            endPos,
            {
                filter,
                maxPathPolys,
            }
        );

        const centers = [];
        const polyRefs = path.polys; // List of polygon references
        for (let i = 0; i < polyRefs.size; i++) {
            const polyRef = polyRefs.get(i);
            const center = this._getPolyCenter(polyRef);
            if (center) {
                centers.push(center);
            }
        }

        return centers;
    }

    private _getPolyCenter(polyRef: number) {
        if (!this._navigationPlugin) {
            return;
        }
        const polyResult =
            this._navigationPlugin.navMesh.getTileAndPolyByRef(polyRef);
        if (!polyResult.success) {
            return;
        }
        console.log(polyResult);

        const { tile, poly } = polyResult;
        let tri = 0;
        const positions = [];
        const indices = [];

        const polyVertCount = poly.vertCount();
        const polyDetail = tile.detailMeshes(0);
        const polyDetailTriBase = polyDetail.triBase();
        const polyDetailTriCount = polyDetail.triCount();

        for (
            let polyDetailTriIndex = 0;
            polyDetailTriIndex < polyDetailTriCount;
            ++polyDetailTriIndex
        ) {
            const detailTrisBaseIndex =
                (polyDetailTriBase + polyDetailTriIndex) * 4;

            for (let trianglePoint = 0; trianglePoint < 3; ++trianglePoint) {
                if (
                    tile.detailTris(detailTrisBaseIndex + trianglePoint) <
                    polyVertCount
                ) {
                    const tileVertsBaseIndex =
                        poly.verts(
                            tile.detailTris(detailTrisBaseIndex + trianglePoint)
                        ) * 3;

                    positions.push(
                        tile.verts(tileVertsBaseIndex),
                        tile.verts(tileVertsBaseIndex + 1),
                        tile.verts(tileVertsBaseIndex + 2)
                    );
                } else {
                    const tileVertsBaseIndex =
                        (polyDetail.vertBase() +
                            tile.detailTris(
                                detailTrisBaseIndex + trianglePoint
                            ) -
                            poly.vertCount()) *
                        3;

                    positions.push(
                        tile.detailVerts(tileVertsBaseIndex),
                        tile.detailVerts(tileVertsBaseIndex + 1),
                        tile.detailVerts(tileVertsBaseIndex + 2)
                    );
                }

                indices.push(tri++);
            }
        }

        const polyCenter = this._calculatePolygonCenter(
            positions,
            positions.length / 3
        );

        return polyCenter;
    }

    private _calculatePolygonCenter(vertices: number[], numVerts: number) {
        let centerX = 0,
            centerY = 0,
            centerZ = 0;

        for (let i = 0; i < numVerts; i++) {
            centerX += vertices[i * 3]; // x
            centerY += vertices[i * 3 + 1]; // y
            centerZ += vertices[i * 3 + 2]; // z
        }

        centerX /= numVerts;
        centerY /= numVerts;
        centerZ /= numVerts;

        return new Vector3(centerX, centerY, centerZ); 
    }

(not production ready code)

Works with: [NEW] Navigation plugin for babylon.js [Node/Browser][ES6][Single thread/Worker/WASM]

V1: computeSmoothPath

V2: computePath

Yet still needs some polishing…