On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation

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...

Full description

Bibliographic Details
Main Authors: Du, Jie, He, Ying, Fang, Zheng, Meng, Wenlong, Xin, Shi-Qing
Other Authors: School of Computer Science and Engineering
Format: Journal Article
Language:English
Published: 2021
Subjects:
Online Access:https://hdl.handle.net/10356/152296
_version_ 1826124097567850496
author Du, Jie
He, Ying
Fang, Zheng
Meng, Wenlong
Xin, Shi-Qing
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Du, Jie
He, Ying
Fang, Zheng
Meng, Wenlong
Xin, Shi-Qing
author_sort Du, Jie
collection NTU
description 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 https://github.com/djie-0329/PVTP.
first_indexed 2024-10-01T06:15:06Z
format Journal Article
id ntu-10356/152296
institution Nanyang Technological University
language English
last_indexed 2024-10-01T06:15:06Z
publishDate 2021
record_format dspace
spelling ntu-10356/1522962021-08-04T02:29:45Z On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation Du, Jie He, Ying Fang, Zheng Meng, Wenlong Xin, Shi-Qing School of Computer Science and Engineering Engineering::Computer science and engineering Discrete Geodesics Parallel Computing 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 https://github.com/djie-0329/PVTP. Ministry of Education (MOE) We would like to thank the authors of VTP [7] for releasing their source code and the anonymous reviewers for their constructive comments. This project is partially supported by Singapore MOE Grant RG20/20 and National Natural Science Foundation of China (61772016). 2021-08-04T02:29:45Z 2021-08-04T02:29:45Z 2021 Journal Article 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-. https://dx.doi.org/10.1016/j.cad.2020.102943 0010-4485 https://hdl.handle.net/10356/152296 10.1016/j.cad.2020.102943 2-s2.0-85092087494 130 102943 en RG20/20 Computer-Aided Design © 2020 Elsevier Ltd. All rights reserved.
spellingShingle Engineering::Computer science and engineering
Discrete Geodesics
Parallel Computing
Du, Jie
He, Ying
Fang, Zheng
Meng, Wenlong
Xin, Shi-Qing
On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation
title On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation
title_full On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation
title_fullStr On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation
title_full_unstemmed On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation
title_short On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation
title_sort on the vertex oriented triangle propagation vtp algorithm parallelization and approximation
topic Engineering::Computer science and engineering
Discrete Geodesics
Parallel Computing
url https://hdl.handle.net/10356/152296
work_keys_str_mv AT dujie onthevertexorientedtrianglepropagationvtpalgorithmparallelizationandapproximation
AT heying onthevertexorientedtrianglepropagationvtpalgorithmparallelizationandapproximation
AT fangzheng onthevertexorientedtrianglepropagationvtpalgorithmparallelizationandapproximation
AT mengwenlong onthevertexorientedtrianglepropagationvtpalgorithmparallelizationandapproximation
AT xinshiqing onthevertexorientedtrianglepropagationvtpalgorithmparallelizationandapproximation