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

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.