Please use this identifier to cite or link to this item:
Title: On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation
Authors: Du, Jie
He, Ying
Fang, Zheng
Meng, Wenlong
Xin, Shi-Qing
Keywords: Engineering::Computer science and engineering
Issue Date: 2021
Source: Du, J., He, Y., Fang, Z., Meng, W. & Xin, S. (2021). On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation. Computer-Aided Design, 130, 102943-.
Project: RG20/20
Journal: Computer-Aided Design
Abstract: Computing geodesic distances on polyhedral surfaces is a fundamental problem in digital geometry processing and computer-aided design. Most of the existing exact algorithms partition mesh edges into intervals, called windows, and propagate one window at a time. The state-of-the-art, Vertex-oriented Triangle Propagation (VTP), groups the windows on the same half-edge as a window list, and propagates window lists across triangular faces using a vertex-oriented priority queue. VTP runs much faster than the conventional algorithms thanks to its group nature. However, as a sequential algorithm, VTP is still computationally expensive for large-scale meshes. In this paper, we develop a parallel version of VTP, called Parallel-VTP or PVTP, that can propagate multiple window lists from multiple vertices simultaneously. To avoid data conflicts, PVTP proceeds with 3 steps in each iteration, which are K-window-list selection, parallel window list propagation, and vertex distance updating and window list merging. Extensive evaluation shows that PVTP improves the speed of the sequential VTP by a factor of 2.5∼3 for T=4 and 4∼5 for T=8 for triangular meshes with regular tessellation and over 1 million vertices, where T is the number of threads. We observe that wavefront propagation in the exact geodesic algorithms slows down when the wavefront has a long circumference, hereby containing a large number of windows pending processing. To improve the efficiency of window propagation, we develop an approximate variant of VTP, called Approximate VTP or AVTP, which trades speed for accuracy by resetting window when the wavefront radius is a multiple of λh, where λ is a user-specified parameter and h is average edge length. We show that AVTP becomes Dijkstra's algorithm when λh is less than the minimal edge length and becomes the exact VTP when λh is greater than the longest geodesic distance on the model. AVTP has a theoretical time complexity O(nλ), which is also confirmed by computational results. It is worth noting that the proposed parallelization and approximation techniques can be either used separately or combined together. Our source code is available at
ISSN: 0010-4485
DOI: 10.1016/j.cad.2020.102943
Rights: © 2020 Elsevier Ltd. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Sep 30, 2022

Page view(s)

Updated on Oct 3, 2022

Google ScholarTM




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