TY - GEN

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

AU - Gotsman, Craig

AU - Hormann, Kai

N1 - Publisher Copyright:
© 2022 ACM.

PY - 2022/11/29

Y1 - 2022/11/29

N2 - 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.

AB - 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.

KW - compression

KW - geodesics

KW - meshes

KW - separators

UR - http://www.scopus.com/inward/record.url?scp=85143974604&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85143974604&partnerID=8YFLogxK

U2 - 10.1145/3550469.3555412

DO - 10.1145/3550469.3555412

M3 - Conference contribution

AN - SCOPUS:85143974604

T3 - Proceedings - SIGGRAPH Asia 2022 Conference Papers

BT - Proceedings - SIGGRAPH Asia 2022 Conference Papers

A2 - Spencer, Stephen N.

PB - Association for Computing Machinery, Inc

T2 - SIGGRAPH Asia 2022 - Computer Graphics and Interactive Techniques Conference - Asia, SA 2022

Y2 - 6 December 2022 through 9 December 2022

ER -