Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms

• Main Authors: Adikusuma, Yohanes Yudhi, Zheng, Fang
• Other Authors: He Ying
• Format: Final Year Project
• Language: English
• Published: 2017
• Subjects: DRNTU::Engineering
• Online Access: http://hdl.handle.net/10356/70313
• Institution: Nanyang Technological University

Discrete geodesic graph (DGG) is an emerging technique for computing geodesic distances and paths on polyhedral surfaces. DGG has many advantages, such as information reuse, accuracy control, ease of parallelization, good scalability, and guaranteed metric, fast linear time SSAD search. To construct DGG, the existing method by Wang et al. firstly finds a large graph with the user-specified accuracy, and then iteratively prunes the redundant edges from it. Finally, it adds pseudo vertices and edges to the graph for the poorly sampled regions. Computational results show that for real-world meshes, more than 80\% of the candidate edges do not contribute to the final graph and are hereby deleted. Moreover, for anisotropic meshes, a large amount of pseudo vertices and edges (up to 40 times the original vertex number) in order to maintain the graph quality, which significantly increases the graph complexity by up to 400x larger. As a result, the existing indirect approach is conservative and far from optimal. This paper aims at improving the performance of DGG construction on general meshes models. Towards this goal, we develop a novel accuracy aware window propagation scheme, allowing us to compute DGG edges in a direct manner. We prove that the new method greatly improving the time complexity of Wang et al's approach. Our method is memory efficient and it scales very well. Through extensive evaluation, we demonstrate that our method produces DGGs with comparable or better accuracy than the existing method, but running up to 2 orders of magnitude faster on common meshes with millions of vertices.In sharp contrast to Wang et al's algorithm, our algorithm can handle anisotropic meshes well without adding pseudo vertices or edges, thanks to its better understanding of the theoretical underpinning of Discrete Geodesic Graph. This effectively generalize DGG to other highly anisotropic and non-uniform cases of polyhedron with a far better time complexity. This novel improvements also brings DGG to be a better performing algorithm than all existing practical approaches - such as SVG or heat method, not only in term of its SSAD solving time, but also in its initial construction time.