Guys!
Does anyone have experience on this topic and willing to share some code so I don’t have to write it myself? 
What I am really after starts at point 4.
http://graphics.ucmerced.edu/papers/10-sca-tripath.pdf
thanks!
2 Likes
I worked on it with Python (designed in Python for research, recoded in C++ for efficiency) but in a slightly different context : ADAS-AD. So, the navigation mesh being a car, reducing the range of movements to what’s possible with wheels 
The final goal was to retrieve optimal path for automatic parking in an arbitratry parking lot geometry.
Are you looking for any solution, or the exact optimized solution proposed in the paper ?
1 Like
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…
Ehm, no 
Welcome anyway 