Parallelizing discrete geodesic algorithms with perfect efficiency. (October 2019)

• Record Type: Journal Article
• Authors: Ying, Xiang; Huang, Caibao; Fu, Xuzhou; He, Ying; Yu, Ruiguo; Wang, Jianrong; Yu, Mei
• Is Part Of: Computer aided design. Volume 115(2019)
• Page Start: 161
• Page End: 171
• Publication Date: 2019-10
• Subjects: Discrete geodesics -- Autonomous wavefront propagation -- The Chen–Han algorithm -- The fast marching method -- Parallel algorithm -- Perfect efficiency; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2019.05.023
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: This paper presents a new method for parallelizing geodesic algorithms on triangle meshes. Using the half-edge data structure, we define the propagation dependency graph to characterize data dependency in computing geodesics. Then, we design an active strategy such that the vertices and half-edges on the wavefront take the initiative to collect their input data and then propagate windows and update geodesic information in their own memory space. As a result, all the read and write operations can be carried out simultaneously. Our method, named AWP, works for both exact (e.g., the CH algorithm) and approximate (e.g., the fast marching method) geodesic algorithms. Our implementation on various NVIDIA GPUs exhibit perfect linear speedup, i.e., doubling the computational power (i.e., FLOPS) doubles the speed. We prove that the AWP-CH algorithm runs in O ( n 2 ∕ min ( C, n ) ) time, where n and C are the numbers of faces and cores, respectively. Evaluation on GTX Titan XP shows that AWP-CH empirically runs in n p time, p ∈ [ 1 . 25, 1 . 35 ], for real-world models with n ≤ 1 0 7 and anisotropy measure τ ≤ 2 . 0 . Thanks to its perfect efficiency and the trend of increasing the number of processors in graphics hardware, we believe that the actual performance of AWP can be further improved in the near future. Highlights: An algorithm for parallelizing discrete geodesic algorithms with perfect efficiency. The algorithm works for both the CH algorithm and the fast marching method. Source code is publically available athttps://github.com/openawp/awp .