# Fast and exact Geodesics on meshes, Backtracking confusion

The following is an excerpt from a 2005 paper on geodesics on triangular meshes, taken from section 3.5

In this case $$p$$ is a point on some arbitrary face in a mesh, $$p'$$ is a point on one of the 3 edges in the triangle and $$D(p')$$ is the geodesic distance to that point.

I am very confused as to how this minimization is achieved. The paper doesn't go into detail, so I assume it's trivial, but I am not seeing the solution of the top of my head.

Given an arbitrary interval (segment) the shortest point to it is either the orthogonal projection of the point $$p$$ onto the segment or one of the end points of the segment (depending on where $$p$$ is located with respect to the segment).

However, this is not necessarily the point that minimizes the expression $$||p - p'|| + D(p')$$ or in other words, $$p'$$ is not, in general, the orthogonal projection of $$p$$ onto the segment.

The only algorithm I have is to naively check epsilon offsets along the segment and picking the shortest one. There has to be a better way than that.

I have drawn a diagram on Geogebra to show the problem:

$$\overline{BA}$$ is the segment, $$C$$ is the point we are looking to minimize the distance from. $$D$$ is the frontier point, which is the orthogonal projection of the Geodesic source (the source point of all geodesics in the mesh), $$E$$ is the orthogonal projection of $$C$$ onto $$\overline{BA}$$. Clearly the optimal point is somewhere between $$E$$ and $$D$$ but I don't know how to find it.

• Doesn't 4.3 and onwards deal with this? It's probably also a good idea to consider: code.google.com/archive/p/geodesic/wikis/ExactGeodesic.wiki – lightxbulb Jul 4 '20 at 7:08
• Unfortunately section 4, section 4,3 included deals with their approximating method, however I need to use the exact geodesic, not the approximation. Those notes are indeed interesting, but they don't seem to address the problem I am currently facing, at minimum not explicitly. I have a hypothesis as to what the proper way to do this is, I am testing it right now, if successful I will answer my own question. – Makogan Jul 4 '20 at 20:03

The solution I found to this problem is to ALWAYS intersect the edge. In other words the distance to the geodesic source $$v$$ from a point $$p$$ is $$||v-p'|| + ||p - p'||$$ where $$p'$$ is the intersection of the line $$\overline{vp}$$ with the current edge. In cases where $$p'$$ is "behind" $$p$$ with respect to $$v$$ we set the distance to the edge to be infinity.