Compressing Geodesic Information for Fast Point-to-Point Geodesic Distance Queries

Craig Gotsman, Kai Hormann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Geodesic distances between pairs of points on a 3D mesh surface are a crucial ingredient of many geometry processing tasks, but are notoriously difficult to compute efficiently on demand. We propose a novel method for the compact storage of geodesic distance information, which enables answering point-to-point geodesic distance queries very efficiently. For a triangle mesh with n vertices, if computing the geodesic distance to all vertices from a single source vertex costs O(f(n)) time, then we generate a database of size O(mnlog n) in time in a preprocessing stage, where m is a constant that depends on the geometric complexity of the surface. We achieve this by computing a nested bisection of the mesh surface using separator curves and storing compactly-described functions approximating the distances between each mesh vertex and a small relevant subset of these curves. Using this database, the geodesic distance between two mesh vertices can then be approximated well by solving a small number of simple univariate minimization problems in O(mlog n) worst case time and O(m) average case time. Our method provides an excellent tradeoff between the size of the database, query runtime, and accuracy of the result. It can be used to compress exact or approximate geodesic distances, e.g., those obtained by VTP (exact), fast DGG, fast marching, or the heat method (approximate) and is very efficient if f(n) = n, as for the fast DGG method.

Original languageEnglish (US)
Title of host publicationProceedings - SIGGRAPH Asia 2022 Conference Papers
EditorsStephen N. Spencer
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450394703
DOIs
StatePublished - Nov 29 2022
EventSIGGRAPH Asia 2022 - Computer Graphics and Interactive Techniques Conference - Asia, SA 2022 - Daegu, Korea, Republic of
Duration: Dec 6 2022Dec 9 2022

Publication series

NameProceedings - SIGGRAPH Asia 2022 Conference Papers

Conference

ConferenceSIGGRAPH Asia 2022 - Computer Graphics and Interactive Techniques Conference - Asia, SA 2022
Country/TerritoryKorea, Republic of
CityDaegu
Period12/6/2212/9/22

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design
  • Human-Computer Interaction

Keywords

  • compression
  • geodesics
  • meshes
  • separators

Fingerprint

Dive into the research topics of 'Compressing Geodesic Information for Fast Point-to-Point Geodesic Distance Queries'. Together they form a unique fingerprint.

Cite this