Algorithm to calculate the shortest path between two points on the surface of a 3D mesh

Question

I am looking for an algorithm to calculate the following:

I have:

1. A 3D triangle mesh. The triangles do not necessarily lie in one plane. The angle between the norm vectors of two neighbouring triangles is less then 90 degrees.

2. Two points. The two points lie either on an edge of the triangle mesh or inside a triangle of the mesh.

I need to calculate the polyline which represents the shortest path between the two points on the mesh.

What is the simplest and/or most effective strategy to do this?

Answer 1

As it stands, your problem is not well defined; there can be many solutions depending on the direction used to "project" the line segment onto the mesh.

Once you have chosen the direction of projection, flatten the mesh onto a plane perpendicular to the direction of projection. At this point, your mesh is a collection of 2d edges (line segments); just determine the intersection (if any) of each edge with your target line segment.

---

Edit:

The updated question is now well defined. Since my answer to the original question (above) has been marked as accepted, presumably that means the information given in the comments below are actually what was really being "accepted" for the update question. I'll summarize:

• A google search of "shortest distance on 3d mesh" turns up some relevant information, like Shortest Path Approximation on Triangulated Meshes
• Also, see: https://stackoverflow.com/a/10389377/294949 -- danh

Answer 2

Since your start/end points potentially lie anywhere on the mesh (not restricted to vertices) I guess you are searching for the geodesic shortest path (not Dikstra shortest path following edges). A nice algorithm is implemented in geometry-central: http://geometry-central.net/surface/algorithms/flip_geodesics/

The algorithm is described in the paper "You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges".