That is true. However, if the mesh is a fairly isotropic triangle mesh (e.g. remeshed using TriRemesh), and you operate on face-face graphs, that does appear to work fairly predictably. See an example here:
Yes it can be pretty tricky to find the right combination of resolution/constraints/settings. Edit: Regarding the cutting corners issue, one might use the Collider goal to prevent the relaxed polyline edges cutting into vertices of the mesh naked perimeter vertices. I haven’t tried it, but it might be worth considering.
The example you posted can be solved using the convex hull to find two paths around the obstacle and picking the shorter one, or using a visibility graph. Which can both be extended to work on 2.5D meshes. It would probably help if we had a mesh/case that can not be solved using such relatively simple methods.
Obviously, you are right.
Unfortunately I can’t share those, and the examples I create seems too trivial.
I did study this thread and the others, I like the results, but they often require some manual processing (like tinkering with kangaroo) to smooth/optimize the path and/or do not reach the actual true shortest path in “one-shot”.
I’m not sure if that’s actually possible. All the methods I’ve ever seen are based on some iterative logic (e.g. agent-based, relaxation, graph search), but there are surely some I’ve missed. Anywho, if I were to develop things further, I’d probably start by extending visibility graphs into 3D (maybe something like this). At least finding e.g Dijkstra shortest paths in such networks would be stable/fast and feel “one-shot”.
Hello here is away that should work but doesn’t work well with my tool but I think the logic is good.
So measure the geodesic distance on the whole mesh with each point. This give you 2 maps of distance. Sum them so if you want the shortest path you just have to stay on the path that has the same distance as the distance on each point.
Shortest path is there. in the green zone. Not easy to find because my tool is not good and gives artefacts and also because it is a valley (0 could be between values that are higher ! )
I should have said it was long, sorry it is not really optimized. I must work on it. In theory it must work with geodesic distance calculated by Heat Method or other tool. Perhaps @DanielPiker could give some hint in order to have a tool that outputs directly the geodesic distances.
All the little islands are errors! They doesn’t help. Also in theory my tool doesn’t need fine mesh as it used real propagation of arcs. So depending on the mesh the number of steps could be lowered.
I would guess that for an exact geodesic on a mesh, an explicit face/edge based approach would be the way to go.
This approach from Nick Sharp could be worth looking at https://nmwsharp.com/research/flip-geodesics/
(and the references give a good overview of other methods)
