Fast Construction of Discrete Geodesic Graphs

Yohanes Yudhi Adikusuma, Zheng Fang, Ying He

Abstract

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.
BibTeX
@article{adikusuma2020fast,
  author = {Yohanes Yudhi Adikusuma and Zheng Fang and Ying He},
  title = {{Fast Construction of Discrete Geodesic Graphs}},
  journal = {ACM Trans. Graphics},
  year = {2020},
  doi = {10.1145/3144567},
}

Loading related content...

Figure