Technical Papers

Date/Time: 04 – 13 December 2020
All presentations are available in the virtual platform on-demand.

Lecturer(s):
Yohanes Yudhi Adikusuma, Nanyang Technological University, Singapore
Zheng Fang, Nanyang Technological University, Singapore
Ying He, Nanyang Technological University, Singapore

Bio:

Description: This paper develops a new method for constructing Discrete Geodesic Graph (DGG)—an undirected, sparse graph for computing discrete geodesic distances and paths on triangle meshes. Based on a novel accuracy aware window propagation scheme, our method is able to compute the graph edges in a direct and efficient manner. Given a triangle mesh with n vertices and a user-specified accuracy parameter ɛ, our method produces a DGG with O(n\√ɛ) edges in empirical O(n\ɛ0.75 log 1\ɛ) time, which greatly improves the time complexity O(n\ɛ log 1\ɛ) of the existing method. Extensive evaluation on a large-scale 3D shape repository shows that our method is efficient and can produce high-quality geodesic distances with predictable accuracy and guaranteed true distance metric. In particular, our method has a great advantage over the existing approximate methods on meshes with high degree of anisotropy. The source code is available at https://github.com/GeodesicGraph..