[Seminar] Graphics seminar: Fast exact and approximate geodesics on meshes

[Jingyi Jin]

Hi everyone,

In the same seminar tomorrow, I will present another SIGGRAPH'05 paper, 
named "Fast exact and approximate geodesics on meshes". The following is the 
original paper abstract:

The computation of geodesic paths and distances on triangle meshes is a 
common operation in many computer graphics applications. We present several 
practical algorithms for computing such geodesics from a source vertex to 
one or all other vertices efficiently. First, we describe an implementation 
of the "single source, all destination" algorithm presented by Mitchell, 
Mount, and Papadimitriou (MMP), and demonstrate that it runs much faster in 
practice than suggested by worst case analysis. Next, we extend the 
algorithm with a merging operation to obtain computationally efficient and 
accurate approximations. Finally, to compute the shortest path between two 
given points, we use a lower-bound property of our approximate geodesic 
algorithm to efficiently prune the frontier of the MMP algorithm, thereby 
obtaining an exact solution even more quickly. 

Jingyi