Fast and Exact Discrete Geodesic Computation Based on

Triangle-Oriented Wavefront Propagation

 

Yipeng Qin1*    Xiaoguang Han2*    Hongchuan Yu1   Yizhou Yu2    Jianjun Zhang1

 

1 Bournemouth University    2 The University of Hong Kong   (* Joint first authors)

 

ACM Transactions on Graphics (Proceedings of SIGGRAPH 2016)

 

vtp.png

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 in-depth 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 triangle-oriented 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 4-15 times faster than MMP and ICH algorithms, 2-4 times faster than FWP-MMP and FWP-CH 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 triangle-oriented window propagation. Our new geodesic algorithm has an O(n2) time complexity. It runs 4-15 times faster than MMP [2][3] and ICH [1] algorithms, 2-4 times faster than FWP-MMP and FWP-CH 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

 

Model

Performance

Algorithms

ICH

MMP

FWP-CH

FWP-MMP

VTP

Bunny

(F: 144K)

Time (s)

5.034

4.612

3.056

1.737

0.78

# window propagations

12,305,579

6,485,320

12,327,991

6,451,352

4,943,670

Peak memory (MB)

1.69

340.45

1.70

340.46

1.24

Rocker Arm
(F: 482K)

Time (s)

36.577

33.286

19.536

11.867

4.13

# window propagations

68,553,846

33,989,638

70,513,186

35,940,386

25,654,638

Peak memory (MB)

5.29

1797.16

5.42

1797.19

3.70

Asian Dragon
(F: 1,400K)

Time (s)

73.204

73.092

35.637

23.674

9.495

# window propagations

107,742,094

62,161,583

108,122,218

62,025,717

48,217,896

Peak memory (MB)

5.18

3354.04

5.21

3354.05

4.373

Neptune
(F: 4,008K)

Time (s)

455.271

424.331

193.945

120.012

47.629

# window propagations

585,784,159

270,930,198

602,587,831

284,581,696

246,364,008

Peak memory (MB)

16.96

14225.26

17.14

14219.76

16.38

Lucy
(F: 14,464K)

Time (s)

8894.87

Out of

memory

2415.88

Out of

memory

549.934

# window propagations

6,837,670,602

6,841,729,337

2,808,823,718

Peak memory (MB)

78.29

78.28

69.42

 

Table 1. Performance comparison with state-of-the-art 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), 647-668.

[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. 553-560). 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), 822-834.

 

Acknowledgements

 

We would like to thank the anonymous reviewers for their valuable comments. This project was supported by EU H2020 project-AniAge (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 Triangle-Oriented 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