Fast wavefront propagation(FWP) for computing exact geodesic distances on meshes

Chunxu Xu Tsinghua University Tuanfeng Y. Wang University of Science and Technology of China Yong-Jin Liu Tsinghua University Ligang Liu University of Science and Technology of China Ying He Nanyang Technological University

Computational Geometry mathscidoc:1608.09004

Distinguished Paper Award in 2017

IEEE Transactions on Visualization and Computer Graphics, 21, (7), 822, 2015.7
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.
Discrete geodesic, fast wavefront propagation, algorithm complexities
[ Download ] [ 2016-08-19 13:44:41 uploaded by liuyj ] [ 550 downloads ] [ 0 comments ] [ Cited by 7 ]
@inproceedings{chunxu2015fast,
  title={Fast wavefront propagation(FWP) for computing exact geodesic distances on meshes},
  author={Chunxu Xu, Tuanfeng Y. Wang, Yong-Jin Liu, Ligang Liu, and Ying He},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819134441920119259},
  booktitle={IEEE Transactions on Visualization and Computer Graphics},
  volume={21},
  number={7},
  pages={822},
  year={2015},
}
Chunxu Xu, Tuanfeng Y. Wang, Yong-Jin Liu, Ligang Liu, and Ying He. Fast wavefront propagation(FWP) for computing exact geodesic distances on meshes. 2015. Vol. 21. In IEEE Transactions on Visualization and Computer Graphics. pp.822. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819134441920119259.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved