Please use this identifier to cite or link to this item:
Title: Parallelizing discrete geodesic algorithms with perfect efficiency
Authors: Ying, Xiang
Huang, Caibao
Fu, Xuzhou
He, Ying
Yu, Ruiguo
Wang, Jianrong
Yu, Mei
Keywords: Engineering::Computer science and engineering
Issue Date: 2019
Source: Ying, X., Huang, C., Fu, X., He, Y., Yu, R., Wang, J. & Yu, M. (2019). Parallelizing discrete geodesic algorithms with perfect efficiency. Computer Aided Design, 115, 161-171.
Project: RG26/17
Journal: Computer Aided Design
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(n2∕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 np time, p∈[1.25,1.35], for real-world models with n≤107 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.
ISSN: 0010-4485
DOI: 10.1016/j.cad.2019.05.023
Rights: © 2019 Elsevier Ltd. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 20

Updated on Nov 25, 2022

Web of ScienceTM
Citations 20

Updated on Nov 26, 2022

Page view(s)

Updated on Dec 3, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.