Abstract
In many graphics applications, the computation of exact geodesic distance is very important. However, the high computational cost of existing geodesic algorithms means that they are not practical for large-scale models or time-critical applications. To tackle this challenge, we propose the Parallel Chen-Han (or PCH) algorithm, which extends the classic Chen-Han (CH) discrete geodesic algorithm to the parallel setting. The original CH algorithm and its variant both lack a parallel solution because the windows (a key data structure that carries the shortest distance in the wavefront propagation) are maintained in a strict order or a tightly coupled manner, which means that only one window is processed at a time. We propose dividing the CH's sequential algorithm into four phases, window selection, window propagation, data organization, and events processing so that there is no data dependence or conflicts in each phase and the operations within each phase can be carried out in parallel. The proposed PCH algorithm is able to propagate a large number of windows simultaneously and independently. We also adopt a simple yet effective strategy to control the total number of windows. We implement the PCH algorithm on modern GPUs (such as Nvidia GTX 580) and analyze the performance in detail. The performance improvement (compared to the sequential algorithms) is highly consistent with GPU double-precision performance (GFLOPS). Extensive experiments on real-world models demonstrate an order of magnitude improvement in execution time compared to the state-of-the-art.
Supplemental Material
- N. Bell and J. Hoberock. 2011. Thrust: A productivity-oriented library for cuda. In GPU Computing Gems, Jade Ed., Morgan Kaufmann, San Fransisco, 359--371.Google Scholar
- M. Campen and L. Kobbelt. 2011. Walking on broken mesh: Defect-tolerant geodesic distances and parameterizations. Comput. Graph. Forum 30, 2, 623--632.Google ScholarCross Ref
- J. Chen and Y. Han. 1990. Shortest paths on a polyhedron. In Proceedings of the Symposium on Computational Geometry. 360--369. Google ScholarDigital Library
- R. Kimmel and J. A. Sethian. 1998. Computing geodesic paths on manifolds. Proc. Nat. Acad. Sci. 95, 8431--8435.Google ScholarCross Ref
- A. Lieutier and B. Thibert. 2009. Convergence of geodesics on triangulations. Comput.-Aid. Geom. Des. 26, 4, 412--424. Google ScholarDigital Library
- Y.-J. Liu, Z. Chen, and K. Tang. 2011. Construction of iso-contours, bisectors, and voronoi diagrams on triangulated surfaces. IEEE Trans. Pattern Anal. Mach. Intell. 33, 8, 1502--1517. Google ScholarDigital Library
- Y.-J. Liu, Q.-Y. Zhou, and S.-M. Hu. 2007. Handling degenerate cases in exact geodesic computation on triangle meshes. Vis. Comput. 23, 9--11, 661--668. Google ScholarDigital Library
- F. Memoli and G. Sapiro. 2001. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. J. Comput. Phys. 173, 2, 730--764. Google ScholarDigital Library
- F. Memoli and G. Sapiro. 2005. Distance functions and geodesics on submanifolds of rd and point clouds. SIAM J. Appl. Math. 65, 4, 1227--1260.Google ScholarCross Ref
- J. S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4, 647--668. Google ScholarDigital Library
- L. Monroe, J. Wendelberger, and S. Michalak. 2011. Randomized selection on the gpu. In Proceedings of the Symposium on High Performance Graphics. 89--98. Google ScholarDigital Library
- K. Polthier and M. Schmies. 1998. Straightest geodesics on polyhedral surfaces. In Mathematical Visualization, 391.Google Scholar
- Y. Schreiber and M. Sharir. 2006. An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. In Proceedings of the Symposium on Computational Geometry. 30--39. Google ScholarDigital Library
- J. Sethian. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Nat. Acad. Sci. 93, 4, 1591--1595.Google ScholarCross Ref
- M. Sharir and A. Schorr. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 1, 193--215. Google ScholarDigital Library
- V. Surazhsky, T. Surazhsky, D. Kirsanov, S. J. Gortler, and H. Hoppe. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3, 553--560. Google ScholarDigital Library
- O. Weber, Y. S. Devir, A. M. Bronstein, M. M. Bronstein, and R. Kimmel. 2008. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Trans. Graph. 27, 4, 104:1--104:16. Google ScholarDigital Library
- S.-Q. Xin, D. T. P. Quynh, X. Ying, and Y. He. 2012. A global algorithm to compute defect-tolerant geodesic distance. In ACM SIGGRAPH ASIA Technical Briefs. 23:1--23:4. Google ScholarDigital Library
- S.-Q. Xin and G.-J. Wang. 2009. Improving chen and han's algorithm on the discrete geodesic problem. ACM Trans. Graph. 28, 4, 104:1--104:8. Google ScholarDigital Library
- X. Ying, X. Wang, and Y. He. 2013. Saddle vertex graph (SVG): A novel solution to the discrete geodesic problem. ACM Trans. Graph. 32, 6, 170:1--170:12. Google ScholarDigital Library
Index Terms
- Parallel chen-han (PCH) algorithm for discrete geodesics
Recommendations
On the Efficacy of a Fused CPU+GPU Processor (or APU) for Parallel Computing
SAAHPC '11: Proceedings of the 2011 Symposium on Application Accelerators in High-Performance ComputingThe graphics processing unit (GPU) has made significant strides as an accelerator in parallel computing. However, because the GPU has resided out on PCIe as a discrete device, the performance of GPU applications can be bottlenecked by data transfers ...
Parallel strategies for 2D Discrete Wavelet Transform in shared memory systems and GPUs
In this work, we analyze the behavior of several parallel algorithms developed to compute the two-dimensional discrete wavelet transform using both OpenMP over a multicore platform and CUDA over a GPU. The proposed parallel algorithms are based on both ...
GPU Based Spot Noise Parallel Algorithm for 2D Vector Field Visualization
ICOIP '10: Proceedings of the 2010 International Conference on Optoelectronics and Image Processing - Volume 01Graphic Processing Unit (GPU) has involved into a parallel computation for it’s massively multi threaded architecture. Due to its high computational power, GPU has been used to deal with many problems that can be easily parallelized. This paper will ...
Comments