Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes

Area of Science:

• Computational Geometry
• Computer Graphics
• Scientific Computing

Background:

• Computing geodesic distances on triangle meshes is crucial for various applications.
• Existing exact algorithms like Mitchell-Mount-Papadimitriou (MMP) and Chen-Han (CH) are computationally expensive for large-scale models.
• The high computational cost limits the practical use of these algorithms in time-critical scenarios.

Purpose of the Study:

• To propose a novel framework, fast wavefront propagation (FWP), to enhance the performance of geodesic distance computation algorithms.
• To improve the efficiency of both the Mitchell-Mount-Papadimitriou (MMP) and Chen-Han (CH) algorithms.
• To enable faster geodesic distance calculations on large-scale triangle meshes.

Main Methods:

• Introduced the fast wavefront propagation (FWP) framework.
• Organized computational windows using a bucket data structure for simultaneous processing.
• Maintained wavefront quality while processing multiple windows concurrently.

Main Results:

• The FWP framework significantly improves the speed of MMP and CH algorithms by a factor of 3-10.
• The FWP method demonstrates reduced sensitivity to mesh triangulation compared to original MMP and CH algorithms.
• Evaluations on diverse large-scale real-world models confirm the performance gains.

Conclusions:

• The fast wavefront propagation (FWP) framework offers a substantial performance improvement for computing geodesic distances on triangle meshes.
• FWP makes exact geodesic distance computation more feasible for large-scale and time-sensitive applications.
• This approach enhances the practical utility of fundamental algorithms in computational geometry and graphics.