Keenan Crane

CARNEGIE MELLON UNIVERSITY

Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow

ACM Transactions on Graphics 2013

(to appear in the Communications of the ACM)

(to appear in the Communications of the ACM)

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.

Fast Forward

Additional Notes

None of the current implementations of the heat method (listed on this page) fully exploit its potential for speed or accuracy. To substantially improve performance on multi-core or GPU-based systems, one need only link against a parallel sparse linear solver that can handle symmetric positive-definite systems. (One might also parallelize matrix construction.) To further improve accuracy, one can incorporate the very nice iterative scheme of Belyaev & Fayolle from their paper On Variational and PDE-Based Distance Function Approximations. Like the heat method, this scheme lends itself nicely to prefactorization (hence low amortized cost relative to fast marching/fast sweeping or window-based methods), and would be easy to implement on top of the existing reference implementation.

For a very cool application of the heat method, see Floraform.

It is also possible to use the heat method to solve the single- or multiple-source shortest path problem on general graphs.

Presentation

@article{Crane:2013:GH,
author = {Keenan Crane and Clarisse Weischedel and Max Wardetzky},
title = {{Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow}},
journal = {ACM Trans. Graph.},
volume = {32},
issue = {5},
year = {2013},
publisher = {ACM},
address = {New York, NY, USA}
}

Source

ANSI C— | optimized reference implementation written by the authors; depends on an external linear solver like CHOLMOD or HSL MA87. |

PyCortex— | (Python) |

StarLab— | (C++) |

DGPDEC— | (C++, from our SIGGRAPH course) |

Unity— [Mac] [Windows] [Linux] | Cool interactive demo by Ruoqi He & Chia-Man Hung from Ecole Polytechnique. |

This work was funded by a Google PhD Fellowship and a grant from the Fraunhofer Gesellschaft. Thanks to Michael Herrmann for inspiring discussions, and Ulrich Pinkall for discussions about Lemma 1. Meshes are provided courtesy of the Stanford Computer Graphics Laboratory, the AIM@Shape Repository, Luxology LLC, and Jotero GbR.

Figures