Robust discrete geodesic and its applications in digital geometry processing

• Main Author: Dao Thi Phuong Quynh
• Other Authors: He Ying
• Format: Theses and Dissertations
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Computer graphics; DRNTU::Science::Mathematics::Geometry
• Online Access: https://hdl.handle.net/10356/53515
• Institution: Nanyang Technological University

Geodesic is a fundamental concept of Differential Geometry; it measures the length of the shortest path along the surface between two points. Geodesic has many important properties such as being a distance metric, locally isotropic, invariant to isometric transformation. Facilitated by these advantages, geodesic plays an important role in many applications, ranging from computer graphics, digital geometric processing to computer vision and image processing, etc. Computing discrete geodesics on meshes been extensively studied since 1980s. A number of efficient methods to compute discrete geodesics on polygonal meshes have been presented, allowing us to efficiently compute the discrete geodesics on large-scale real-world models. However, in spite of its popularity, geodesics are highly sensitive to local geometric and topological noises, which seriously diminish their application. Introducing arbitrary small topological changes (e.g., holes, gaps, small handles) might cause arbitrarily large change in geodesic distance between pair of points. Therefore, to obtain robust and accurate geodesics, the input meshes are usually required to be free of noise and with good tessellation. However, this requirement may not be met for real-world models obtained from 3D scanning, a careful preprocessing (e.g., hole/gap filling, denoising, re meshing, etc) must be done before applying the discrete geodesic algorithms. Thus, it is highly desirable to develop an efficient and robust method to compute geodesics on defect models. This thesis aims at developing robust discrete geodesic algorithms to address the challenges of computing geodesics on the defect models. Our contributions include: 1) The first contribution is an intrinsic algorithm for computing the meaningful approximate geodesics on polygonal meshes with holes. Without the explicit hole filling, our algorithm is completely intrinsic and independent of the embedding space, thus, it has the potential for isometrically deforming objects as well as meshes in high dimensional space. Furthermore, our method can guarantee the exact solution if the surface is developable. We demonstrate the efficacy of our algorithm on both real-world and synthetic models. 2) We investigate in follow up work to compute the meaningful approximate geodesics for meshes with other types of defects such as noise, gaps, shortcuts, etc. The second contribution is a novel algorithm to compute defect-insensitive geodesic (DIG) on broken meshes. In contrast to the existing approaches which compute the distance from source to destinations in a single Dijkstra-like sweep, our method proceeds in an iterative and global manner. Thanks to its global nature, the resulting distance is tolerant to some defects (e.g. holes, gaps, shortcuts), insensitive to mesh tessellation/resolution, and robust to noise, which provides a meaningful approximation of geodesics on broken meshes. 3) The third contribution is about potential applications of our above algorithms in digital geometry processing, especially for the motion data captured by 3D structure light camera that inevitably has several kinds of defects such as noise, holes, gaps, etc. First, we present three applications in common geometry processing including texture mapping, DIG-based D2 shape signature and DIG-based Heat Kernel Signature (HKS). Second, we develop a robust 3D face segmentation algorithm leading to highly consistent results and propose a framework to parameterize 3D faces with guaranteed feature correspondence. The final application is modeling 3D articulated motion data with conformal geometry videos (CGVs). As the scanned motion data is usually bulky, a challenge for finding a more compact representation for this data is becoming more prevalent. While the traditional geometry videos (GVs) capture 3D motion by three channels, we prove that CGVs take only one channel of mean curvature H and the first frame of the conformal factor λ, i.e., approximately 1/3 the storage of the GVs. The experimental results demonstrate that the proposed CGVs is promising for modeling 3D motion data. In conclusion, we develop robust algorithms to compute geodesics on defect meshes. Potential applications in real-world are implemented to show the correctness and robustness of our algorithms.