Discrete geodesic graphs

The discrete geodesic problem aims to find the shortest path and distance between arbitrary points on discrete surfaces. It is significant in a variety of computational geometry applications, such as surface parameterization and distance-based shape descriptors for shape analysis. As discrete surfaces are not able to generalize like parametric surfaces, computing the distance metric requires complex models and provides with huge possibilities to algorithm design. With the growth of computation capabilities, geometry processing applications incorporate with larger scale data and demand higher runtime performance, space efficiency, scalability and robustness. Therefore, ever since the initial introduction of the discrete geodesic problem, there are plenty of research constantly focusing on and improving these issues. To improve efficiency, a possible direction is to enhance information reuse. With precomputed essential information, queries are more responsive using more efficient algorithms. It may introduce error to the exact discrete geodesics and is regarded as trade-offs between the performance aspects and the accuracy. In contrast to the window-based exact algorithms, these methods are also called approximation algorithms. In this thesis, we discuss the related scheme in detail and further consider several applications and improvements. We conclude our contribution in three aspects: First, I propose a graph-based approximation method for computing discrete geodesics. The scheme aims at enhancing information reuse for multiple distance queries meanwhile keeping the classical discrete wavefront propagation scheme. The wavefront propagation sticks to the geometric nature of any discrete surface, such that both the distance metric, robustness and accuracy is under control. We prove that a DGG on triangle mesh $M$ has $O(\frac{n}{\sqrt\varepsilon})$ edges and the distance produced from DGG has $O(\varepsilon)$ relative error. We observe that DGG significantly outperforms several approximation methods including the saddle vertex graph (SVG) in terms of accuracy controlling, theoretical soundness, time and spatial consumption. Meanwhile DGG possesses the same features for arbitrary points on mesh surface. Second, I present an algorithm which is capable of computing accurate and robust discrete Green's functions for arbitrary points using DGG. We discover the connection between geodesic distance function and the Green's function by assigning geodesics to the Green's third identity on closed triangle meshes. We build a harmonic B-splines formation equivalent to the Green's third identity. The computational domain shrinks to a local patch as the basis function decays to zero outside one-ring neighbors of the patch. I introduce an optimization scheme to solve the localized harmonic B-spline equation and compute the discrete Green's function quickly, which is a better simulation of ground truth on synthetic models according to experimental results. I also present a refinement procedure for PVG mesh solver - a vector mesh editing method providing with better visual effects on rough models. Third, I explore the improvement and extension to DGG. I improve the complexities of DGG algorithms. I also extend the scheme based on discrete geodesic graphs to point clouds. The proposed algorithm is conceptually simple yet effective. It extends a method which approximates the intrinsic distance with the Euclidean distance in an offset band but allows user to control the error convergence rate and performs the geodesic computation in a Dijkstra-like sweep. In this thesis, I also explore the possibilities in geometric applications based on discrete geodesic graphs. In addition to classical manifold-distance related topics such as Voronoi tessellation, I discover the internal relationship between the discrete Green’s functions and the discrete geodesics. Another application is tracing the iso-curve of geodesic distance fields. DGG provides a fast preprocessing method to compute discrete geodesic distance. The graph nature of DGG enables instant distance query. With the feature of the classical discrete wavefront propagation scheme, I observe that DGG is significantly competitive to the state-of-art preprocessing algorithms. The results of major extensions and improvements of DGG is also illustrated in this thesis.Doctor of Philosoph