Fast and Exact Discrete Geodesic
Computation Based on TriangleOriented Wavefront
Propagation Yipeng Qin^{1}* Xiaoguang Han^{2}* Hongchuan Yu^{1} Yizhou Yu^{2} Jianjun Zhang^{1} ^{1 }Bournemouth University ^{2} The
University of Hong Kong (* Joint first authors) ACM Transactions on
Graphics (Proceedings of SIGGRAPH 2016) 


Abstract: Computing
discrete geodesic distance over triangle meshes is one of the fundamental
problems in computational geometry and computer graphics. In this problem, an
effective window pruning strategy can significantly affect the actual running
time. Due to its importance, we conduct an indepth study of window pruning
operations in this paper, and produce an exhaustive list of scenarios where
one window can make another window partially or completely redundant. To
identify a maximal number of redundant windows using such pairwise cross
checking, we propose a set of procedures to synchronize local window
propagation within the same triangle by simultaneously propagating a
collection of windows from one triangle edge to its two opposite edges. On
the basis of such synchronized window propagation, we design a new geodesic
computation algorithm based on a triangleoriented region growing scheme. Our
geodesic algorithm can remove most of the redundant windows at the earliest
possible stage, thus significantly reducing computational cost and memory
usage at later stages. In addition, by adopting triangles instead of windows
as the primitive in propagation management, our algorithm significantly cuts
down the data management overhead. As a result, it runs 415 times faster
than MMP and ICH algorithms, 24 times faster than FWPMMP and FWPCH
algorithms, and also incurs the least memory usage. 

Contributions 
The fastest algorithm with the least memory usage to calculate
“Exact Shortest Path/Distance” over triangular meshes. ·
A new geodesic computation
framework based on triangleoriented window propagation. Our new geodesic
algorithm has an O(n^{2})
time complexity. It runs 415 times faster than MMP ^{[2][3]} and ICH
^{[1]} algorithms, 24 times faster than FWPMMP and FWPCH
algorithms ^{[4]} and also incurs the least memory usage. ·
A complete list of scenarios
for pairwise window cross checking and pruning inside a triangle. ·
A set of rules and
algorithms for synchronized windows propagation within a triangle. 

Results 
Table
1. Performance comparison with stateoftheart geodesic algorithms on
running time, peak memory usage and total number of window propagations. F: means the number of faces on a
model. 

Download 
Paper Slides Supplemental Code 

Related works 
[1] Xin,
S. Q., & Wang, G. J. (2009). Improving Chen and Han's algorithm on the
discrete geodesic problem. ACM Transactions on Graphics (TOG), 28(4),
104. [2] Mitchell, J.
S., Mount, D. M., & Papadimitriou, C. H. (1987). The discrete geodesic
problem. SIAM Journal on Computing, 16(4), 647668. [3] Surazhsky, V.,
Surazhsky, T., Kirsanov, D., Gortler, S. J., & Hoppe, H. (2005, July).
Fast exact and approximate geodesics on meshes. In ACM transactions
on graphics (TOG) (Vol. 24, No. 3, pp. 553560). ACM. [4] Xu, C. X.,
Wang, T. Y., Liu, Y. J., Liu, L. G., & He, Y. (2015). Fast Wavefront
Propagation (FWP) for Computing Exact Geodesic Distances on Meshes. IEEE
transactions on visualization and computer graphics, 21(7),
822834. 

Acknowledgements 
^{ } We would like to thank the anonymous
reviewers for their valuable comments. This project was supported by EU H2020
projectAniAge (No.691215) and Hong Kong Research Grants Council under
General Research Funds (HKU718712). All our testing models are from the
AIM@SHAPE shape repository, Large Geometric Models Archive at Georgia
Institute of Technology and Suggestive Contour Gallery provided by Princeton
University. ^{ } 

Bibtex 
^{ } @article{QH2016, title = {Fast and Exact Discrete Geodesic
Computation Based on TriangleOriented Wavefront Propagation}, author = {Yipeng Qin and
Xiaoguang Han and Hongchuan Yu and Yizhou Yu and Jianjun Zhang}, journal = {ACM
Transactions on Graphics (Proc. SIGGRAPH)}, volume = {?}, number = {?}, year = {2016}, pages = {?},
} 

Copyright © 2016 Xiaoguang Han