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

Advanced search
Browse by:

Department | Year

UCL Theses | Latest

Deposit your research

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

Xu, C; Wang, TY; 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) pp. 822-834. 10.1109/TVCG.2015.2407404. Green open access

Preview

Text
FWP.pdf - Published Version
Download (13MB) | Preview

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.

Type:	Article
Title:	Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes
Open access status:	An open access version is available from UCL Discovery
DOI:	10.1109/TVCG.2015.2407404
Publisher version:	http://dx.doi.org/10.1109/TVCG.2015.2407404
Language:	English
Additional information:	Copyright © 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Keywords:	Data structures, Time complexity, Educational institutions, Approximation algorithms, Computational geometry, Computational modeling, algorithm complexities, Discrete geodesic, fast wavefront propagation
UCL classification:	UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI:	https://discovery.ucl.ac.uk/id/eprint/1503714