Parallel computation of discrete geodesics and its applications

• Main Author: Le, Tien Hung
• Other Authors: He Ying
• Format: Theses and Dissertations
• Language: English
• Published: 2017
• Subjects: DRNTU::Science::Mathematics::Geometry
• Online Access: http://hdl.handle.net/10356/72861
• Institution: Nanyang Technological University

Computing geodesics on meshes is a classical problem in computational and differential geometry. It measures the length of the local shortest path with minimum curvature along the surface between two points. Previous studies have documented many important properties of geodesics, such as being a distance metric, locally isotropic and invariant to isometric transformation. With those properties, geodesic distance could be considered as a more general definition of Euclidean distance. Thus, it plays an important role in constructing various algorithms, solving many real-world problems and developing countless applications in a wide range of fields, including computer graphic, digital geometric processing, computer vision and image processing, etc. Although computing discrete geodesics has been widely studied, there are still many difficult barriers in finding of geodesic distances and paths, including high computational cost, dependence on quality of the input mesh and scalability for other input data types with less connectivity information. Effectively computing discrete geodesics overcoming those issues can be a key to open larger doors to solving a lot of related problems. Traditionally, the proposed geodesic algorithms have tended to focus on geodesics between vertices rather than between arbitrary points on input mesh surfaces. Geodesics between two arbitrary points could be computed in a simple but inaccurate way using interpolation or in other way using re-triangulation which always is very expensive and can globally change the topology of the input meshes. The lack of this ability in computing geodesics can diminish its area of applications. This thesis aims at developing efficient and flexible geodesic algorithms to address the challenges of computing geodesics at vertices/surface points on large real-world models with high time performance for interactive applications. Our contributions include: The first contribution is the analysis and development of an algorithm for computing approximate geodesics on triangle meshes. We adapt the unfolding strategy and the label correcting algorithm to the well-known ”Saddle Vertex Graph” algorithm to take their advantages for approximating geodesic distances at vertices/points with good time performance. The combination can work smoothly with very large-scale models and it is promising for developing interactive applications. Based on the classical ”Mitchell, Mount, and Papadimitriou” (MMP) algorithm, we introduced its improved version (IMMP) as the second contribution for discrete geodesic computation with high performance on triangle meshes. The first major improvement is about designing an efficient approach for windows clipping, which can be used extensively in other geodesic algorithms. In our approach, solving quadratic equations and computing Euclidean distance are required only in special cases, thus the number of calling expensive square-root function is significantly reduced. In addition, we use vertices instead of windows as the primitive in a priority queue with a simple window merging/updating to significantly cut down the overhead of the windows propagation management. We also proposed parallel improved MMP algorithm (PIMMP) as a parallelize version of IMMP by dividing the IMMP sequential algorithm into four phases, front node selection, window list propagation, window list merging and vertex update. We use two separating buffers for income windows on each edge so there is no data dependence or conflicts in each phase and the operations within each phase can be carried out in a CPU-base parallel fashion. The PIMMP algorithm is able to propagate a large number of windows simultaneously and independently, thus its performance is highly improved on real-world models. As the third contribution, we apply our discrete geodesic algorithm into a multi-class shape distribution application. It allows users to control different properties of randomly distributed shapes, including their sampling rate, direction field and density. Furthermore, the anisotropic point-based and curve-base exponential mapping techniques are supported, which are used to draw shapes at points or follow curves. In our application, multiple complex 2D objects can be distributed on 3D surface without conflict. With the high performance of our geodesic algorithm, our application can work interactively, even when input meshes are very large.