dc.contributor.author	Trettner, Philip	en_US
dc.contributor.author	Bommes, David	en_US
dc.contributor.author	Kobbelt, Leif	en_US
dc.contributor.editor	Digne, Julie and Crane, Keenan	en_US
dc.date.accessioned	2021-07-10T07:46:31Z
dc.date.available	2021-07-10T07:46:31Z
dc.date.issued	2021
dc.description.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 theWild 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 6x speed-up on the CPU and 20x 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.	en_US
dc.description.number	5
dc.description.sectionheaders	Distances
dc.description.seriesinformation	Computer Graphics Forum
dc.description.volume	40
dc.identifier.doi	10.1111/cgf.14371
dc.identifier.issn	1467-8659
dc.identifier.pages	247-260
dc.identifier.uri	https://doi.org/10.1111/cgf.14371
dc.identifier.uri	https://diglib.eg.org:443/handle/10.1111/cgf14371
dc.publisher	The Eurographics Association and John Wiley & Sons Ltd.	en_US
dc.subject	Computing methodologies
dc.subject	Mesh geometry models
dc.subject	Theory of computation
dc.subject	Computational geometry
dc.title	Geodesic Distance Computation via Virtual Source Propagation	en_US

Geodesic Distance Computation via Virtual Source Propagation

Files

Original bundle

Collections