Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/80804
Title: Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes
Authors: Xu, Chunxu
Wang, Tuanfeng Y.
Liu, Yong-Jin
Liu, Ligang
He, Ying
Keywords: Discrete Geodesic
Fast Wavefront Propagation
Issue Date: 2015
Source: Xu, C., Wang, T. Y., Liu, Y.-J., Liu, L., & He, Y. (2015). Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes. IEEE Transactions on Visualization and Computer Graphics, 21(7), 822-834.
Series/Report no.: IEEE Transactions on Visualization and Computer Graphics
Abstract: Computing 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.
URI: https://hdl.handle.net/10356/80804
http://hdl.handle.net/10220/45015
ISSN: 1077-2626
DOI: 10.1109/TVCG.2015.2407404
Rights: © 2015 Institute of Electrical and Electronics Engineers (IEEE). This is the author created version of a work that has been peer reviewed and accepted for publication by IEEE Transactions on Visualization and Computer Graphics, Institute of Electrical and Electronics Engineers (IEEE). It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1109/TVCG.2015.2407404].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes.pdf5.64 MBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 20

31
checked on Sep 5, 2020

WEB OF SCIENCETM
Citations 20

22
checked on Oct 24, 2020

Page view(s) 20

187
checked on Oct 25, 2020

Download(s) 20

44
checked on Oct 25, 2020

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.