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

[img] 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.

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Other Institutions > Teaching Staff, Faculty of Science
08 Faculty of Science > Institute of Computer Science (INF)
08 Faculty of Science > Institute of Computer Science (INF) > Computer Graphics Group (CGG)

UniBE Contributor:

Bommes, David

Subjects:

000 Computer science, knowledge & systems
500 Science > 510 Mathematics

ISSN:

1467-8659

Publisher:

Wiley

Language:

English

Submitter:

Nicolas Gallego Ortiz

Date Deposited:

30 Sep 2021 13:57

Last Modified:

26 Mar 2024 13:10

Publisher DOI:

10.1111/cgf.14371

Additional Information:

Eurographics Symposium on Geometry Processing 2021

Uncontrolled Keywords:

Computing methodologies, Mesh geometry models; Theory of computation, Computational geometry

BORIS DOI:

10.48350/159313

URI:

https://boris.unibe.ch/id/eprint/159313

Actions (login required)

Edit item Edit item
Provide Feedback