Please use this identifier to cite or link to this item:
|Title:||Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes||Authors:||Xu, Chunxu
Wang, Tuanfeng Y.
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
|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:
|Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes.pdf||5.64 MB||Adobe PDF|
Updated on Nov 22, 2022
Web of ScienceTM
Updated on Nov 30, 2022
Page view(s) 50450
Updated on Dec 1, 2022
Updated on Dec 1, 2022
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.