Fast Construction of Discrete Geodesic Graphs
Lists
Only you see this
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...