IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics (TVCG) is a monthly journal that publishes research on subjects related to computer graphics and visualization techniques, systems, software, hardware, and user interface issues. Read the full scope of TVCG.

From the July 2015 issue

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

By Chunxu Xu, Tuanfeng Y. Wang, Yong-Jin Liu, Ligang Liu, and Ying He

Featured articleComputing geodesic distances on triangle meshes is a fundamental problem in computational geometry and computer graphics. To date, two notable classes of algorithms, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been proposed. Although these algorithms can compute exact geodesic distances if numerical computation is exact, they are computationally expensive, which diminishes their usefulness for large-scale models and/or time-critical applications. In this paper, we propose the fast wavefront propagation (FWP) framework for improving the performance of both the MMP and CH algorithms. Unlike the original algorithms that propagate only a single window (a data structure locally encodes geodesic information) at each iteration, our method organizes windows with a bucket data structure so that it can process a large number of windows simultaneously without compromising wavefront quality. Thanks to its macro nature, the FWP method is less sensitive to mesh triangulation than the MMP and CH algorithms. We evaluate our FWP-based MMP and CH algorithms on a wide range of large-scale real-world models. Computational results show that our method can improve the speed by a factor of 3-10.

download PDF View the PDF of this article       csdl View this issue in the digital library

Editorials and Announcements



Guest Editorials

Reviewers List

Annual Index

Access recently published TVCG articles

RSS Subscribe to the RSS feed of latest TVCG content added to the digital library.

Mail Sign up for the Transactions Connection newsletter.

           TVCG is indexed in MEDLINE®/PubMed® & ISI

Computing Now