Geodesic Distance Computation via Virtual Source Propagation

Trettner, P.; Bommes, David; Kobbelt, L. (2021). Geodesic Distance Computation via Virtual Source Propagation. Computer graphics forum, 40(5), pp. 247-260. Wiley 10.1111/cgf.14371

Text geodesic-source-propagation.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (30MB)

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 10 000 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.

Interest & Impact

Downloads

1 since deposited on 30 Sep 2021
0 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item