3 years ago

Fast Construction of Discrete Geodesic Graphs

Yohanes Yudhi Adikusuma, Zheng Fang, Ying He
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(n0.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.

Publisher URL: https://dl.acm.org/doi/abs/10.1145/3144567

DOI: 10.1145/3144567

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.