title: shortest paths & geodesics
body: <p>given a mesh made entirely of quads, where every vertex has valence n (with n >= 3), and does not lie on the same plane, I need to find the distance of every vertex in the mesh from a closed set of seed vertices. That is, given one or more mesh vertices (a seed set), I need to build a distance map that stores the distance of each mesh vertex from the seed set (which will have distance 0 from themselves).</p>
  
  <p>after spending some time searching for possible solutions, I got the following picture:</p>
  
  <p>1) it is not trivial, and different approaches have been developed during the last 20 years or so</p>
  
  <p>2) every algorithm that takes into account a 3d domain is restricted to a triangular domain</p>
  
  <p>said that, this is the picture I got:</p>
  
  <p>Dijkstra algorithm may be used as a way to find the shortest path between 2 vertices, following the edges of the mesh, but it is very inaccurate and  will lead to an erroneous geodesic. Lanthier (LA) proposed an improvement, but the error is still quite high.</p>
  
  <p>Kimmel and Sethian (KS) proposed a Fast Marching Method -FMM- to solve the Eikonal equation, addressing the issue calculating the propagation of a wave starting at the seed points and recording the time the wave crosses every vertex. Unfortunately this algorithm, while simple enough to implement, still brings a quite inaccurate result, and care has to be taken to avoid obtuse triangles, or treat them in a very special way.
  Novotni (NV) addressed the problem of (KS) precision in a single seed scenario, but it is unclear to me if:</p>
  
  <p>a) it still suffers from the obtuse angle problem</p>
  
  <p>b) when used in a multiple seed points scenario, a single FMM has to be implemented for every single seed in order to find the minimum distance for each mesh vertex from each seed (that is, in a 10 seed points scenario, FMM would have to be run 10 times per each mesh vertex)</p>
  
  <p>On the other side, an exact algorithm -MMP- that leads to 0 error has been presented by Mitchell &amp; al. (MI) in 87, and AFAIK has never been really implmeneted (probably due to the computing power required). On the same exact approach, Surazhsky &amp; al. (SU) provided an alternative exact algorithm based on MMP that should outperform the latter in terms of speed, still leading to a correct result. Unfortunately the computing power required for the calculation, even if much less than the original MMP, is still high enough so that realtime interactive implementation is not feasible at this time.
  (SU) also proposed an approximation of their exact algorithm, what they called flat-exact. It should take the same computational time of FMM, while bringing only 1/5th of the error, but:</p>
  
  <p>c) it is unclear to me if it can be used in a multiple seeds scenario.</p>
  
  <p>Other exact shortest path algorithms have been proposed by Chen &amp; Han (CH) and Kapoor (KP), but while the first is absolutely slow, the second is just too complicated to be implemented in practice.</p>
  
  <p>so.. the bottom line is: I need a distance from a set, not the shortest path between 2 points.</p>
  
  <p>if I got it right,</p>
  
  <p>either I use FMM to get a distance of each vertex from a set in a single pass,</p>
  
  <p>-or-</p>
  
  <p>use another algorithm to calulate the geodesic from every mesh vertex to every seed point and find the shortest one (and If I got it right that would mean calling that algorithm on every seed point for every mesh vertex, that is, on a 10,000 vertex mesh and a seed set of 50 points, I would have to calculate 500,000 geodesics in order to get the 10,000 shortest one)</p>
  
  <p>Am I missing something? is FMM the only way to deal with multiple seeds distances in a single pass? Someone knows if the flat-exact algorithm may be used in a multiple seed points scenario?</p>
  
  <p>thnx</p>
  
  <p>Notes:</p>
  
  <p>(LA): Lanthier &amp; al. "Approximating weighted shortest paths on polyhedral surfaces"</p>
  
  <p>(KS): Kimmel, Sethian "Computing geodesic paths on manifolds"</p>
  
  <p>(NV): Novotni "Computing geodesic distances on triangular meshes"</p>
  
  <p>(MI): Mitchell &amp; al. "The discrete geodesic problem"</p>
  
  <p>(SU): Surazhsky, Kirsanov &amp; al. "Fast exact and approximate geodesics on meshes"</p>
  
  <p>(CH): Chen, Han, "Shortest paths on polyhedron"</p>
  
  <p>(KP): Kapoor "Efficient computation of geodeisc shortest paths"</p>