Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow
Abstract
We introduce the heat method for computing the geodesic distance to a specified subset (e.g., point or curve) of a given domain. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard linear elliptic problems. The resulting systems can be prefactored once and subsequently solved in near-linear time. In practice, distance is updated an order of magnitude faster than with state-of-the-art methods, while maintaining a comparable level of accuracy. The method requires only standard differential operators and can hence be applied on a wide variety of domains (grids, triangle meshes, point clouds, etc.). We provide numerical evidence that the method converges to the exact distance in the limit of refinement; we also explore smoothed approximations of distance suitable for applications where greater regularity is required.
Additional Information
©2013 ACM. This work was funded by a Google PhD Fellowship and a grant from the Fraunhofer Gesellsohaft. Received September 2012; revised January 2013; accepted March 2013. Thanks to Michael Herrmann for inspiring discussions, and Ulrich Pinkall for discussions about Lemma 1. Meshes are provided courtesy of the Stanford Computer Graphics Labora- tory, the AIM@Shape Repository, Luxology LLC, and Jotero GbR (http://www.evolution-of-genius.de/).Additional details
- Eprint ID
- 41807
- DOI
- 10.1145/2516971.2516977
- Resolver ID
- CaltechAUTHORS:20131009-104042691
- Google PhD Fellowship
- Fraunhofer Gessallsohaft
- Created
-
2013-10-09Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field