Geodesic Distance Computation via Virtual Source Propagation

Computer Graphics Forum, vol. 40, pp. 247–260

Abstract

Abstract We present a highly practical, efficient, and versatile approach for computing approximate geodesic distances. The method is designed to operate on triangle meshes and a set of point sources on the surface. We also show extensions for all kinds of geometric input including inconsistent triangle soups and point clouds, as well as other source types, such as lines. The algorithm is based on the propagation of virtual sources and hence easy to implement. We extensively evaluate our method on about 10000 meshes taken from the Thingi10k and the Tet Meshing in the Wild data sets. Our approach clearly outperforms previous approximate methods in terms of runtime efficiency and accuracy. Through careful implementation and cache optimization, we achieve runtimes comparable to other elementary mesh operations (e.g. smoothing, curvature estimation) such that geodesic distances become a “first‐class citizen” in the toolbox of geometric operations. Our method can be parallelized and we observe up to 6× speed‐up on the CPU and 20× on the GPU. We present a number of mesh processing tasks easily implemented on the basis of fast geodesic distances. The source code of our method is provided as a C++ library under the MIT license.

Authors 3

1. Philip Trettner Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University Germany

   RWTH Aachen University, Germany

2. David Bommes

   University of Bern

   Affiliation as printed

   University of Bern Switzerland

   University of Bern, Switzerland

3. Leif P. Kobbelt Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University Germany

   RWTH Aachen University, Germany