Parallel discrete geodesic algorithms

• Main Author: Du, Jie
• Other Authors: He Ying
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/143580
• Institution: Nanyang Technological University

The computation of geodesic paths and distances on a 3D triangle mesh is an important and fundamental problem in computer graphics domain. Developing faster geodesic algorithms is the eternal pursuit of researchers. We focus on developing parallel exact and approximate discrete geodesic algorithms in this thesis. There are two main difficulties in parallelizing discrete geodesic algorithms. One is the strong dependence of data, the other one is the strict order of elements (windows or vertices) in sequential Dijkstra-like geodesic algorithms. First of all, we propose the Parallel Mitchell-Mount-Papadimitriou (PMMP) algorithm, which extends the classical Mitchell-Mount-Papadimitriou (MMP) algorithm to the parallel framework. The classical MMP algorithm takes windows as primitives and maintains a priority queue to control the order of window propagation and window clipping to make sure that each window covers the shortest paths. To overcome the strong dependence of data, we divide our framework into five main steps: window selection, window propagation, window organization, window clipping, and window pushing. There is no data conflict in our concurrent steps: window propagation and window clipping. To concurrently propagate multi-windows and meanwhile maintain wavefront with great quality, we adopt the ``buckets'' structure to control windows in our implementation. Experimental results show that our parallel MMP algorithm is 1.6-1.7 times faster than FWP-MMP (the fastest version of sequential MMP) on 4 CPU cores. Considering that the MMP algorithm occupies too much memory and the major requirement of related applications is computing geodesic distance instead of geodesic paths, we move towards developing a parallel framework for vertex-oriented triangle propagation (VTP) algorithm, the fastest sequential exact geodesic algorithm up to now. The VTP algorithm takes vertices as primitives and maintains a priority queue to control the order of window list propagation around the vertex to update wavefront. Our parallel-VTP (PVTP) framework includes three main steps: K-window-list selection, parallel window list propagation, vertex distance updating and window list merging. Although there is only one concurrent step that window list propagation, the time complexity of other three steps is only O(n) time complexity. Thus, our algorithm has an empirical O(n^2/T) time complexity, where n is the number of vertices and T is the number of threads. The experimental results show expected performance that our parallel VTP is 2.5-3 times faster than sequential VTP on a 4-core CPU and 4-5 times faster than sequential VTP algorithm on an 8-core CPU for most of regular triangle meshes with over 1 million vertices. Subsequently, we propose an approximate method based on VTP. Our approximate-VTP (AVTP) algorithm controls the global precision by parameter \lambda. Once the radius of the new wavefront achieves a multiple of \lambda h, we delete all windows on wavefront and consider all vertices on the wavefront as new sources to reduce the number of windows and maintain geodesic properties. \lambda is a user-specified parameter for accuracy and speed control and h is average edge length. AVTP has a theoretical time complexity O(n\lambda). The proposed parallelization and approximation techniques can be either used separately or combined together. There are many applications requiring the query of geodesic distances between vertices on a given triangle mesh. Herein, we present an application of discrete geodesic problems. Near repetitive patterns are ubiquitous in man-made and natural objects. Discovering their arrangement is helpful in understanding and analyzing of model geometry. Observing that patterns have consistent matching between the corresponding points, we propose a local feature matching algorithm. Our method is able to work for isotropic, anisotropic, and size varied patterns. This thesis puts emphasis on developing faster discrete geodesic algorithms by parallelizing existing fast sequential geodesic algorithms. Our parallel-MMP algorithm is the fastest exact discrete geodesic algorithm that can trace the geodesic paths. Our parallel-VTP algorithm is also the fastest exact geodesic algorithm that can compute the geodesic distance. Our approximate-VTP algorithm has better performance than other homogeneous approximate geodesic algorithms so far.