Keenan Crane

CARNEGIE MELLON UNIVERSITY

The Vector Heat Method

ACM Transactions on Graphics (2019)

This paper describes a method for efficiently computing parallel transport of tangent vectors on curved surfaces, or more generally, any vector-valued data on a curved manifold. More precisely, it extends a vector field defined over any region to the rest of the domain via parallel transport along shortest geodesics. This basic operation enables fast, robust algorithms for extrapolating level set velocities, inverting the exponential map, computing geometric medians and Karcher/Fréchet means of arbitrary distributions, constructing centroidal Voronoi diagrams, and finding consistently ordered landmarks. Rather than evaluate parallel transport by explicitly tracing geodesics, we show that it can be computed via a short-time heat flow involving the *connection Laplacian*. As a result, transport can be achieved by solving three prefactored linear systems, each akin to a standard Poisson problem. To implement the method we need only a discrete connection Laplacian, which we describe for a variety of geometric data structures (point clouds, polygon meshes, *etc.*). We also study the numerical behavior of our method, showing empirically that it converges under refinement, and augment the construction of intrinsic Delaunay triangulations (iDT) so that they can be used in the context of tangent vector field processing.

The Heat Method for Distance Computation - the original heat method paper provides a nice introduction to the principle of computation from diffusion (as well as some useful implementation details).

Teaser Video

Presentation

Heat Methods Overview

vector-heat-demo—C++ implementation and interactive demo, including parallel transport and the log map, with visualization in Polyscope.

@article{Sharp:2019:VHM,
author = {Sharp, Nicholas and Soliman, Yousuf and Crane, Keenan},
title = {The Vector Heat Method},
journal = {ACM Trans. Graph.},
volume = {38},
number = {3},
year = {2019},
publisher = {ACM},
address = {New York, NY, USA},
}

Thanks to Jooyoung Hahn for early discussions about signed distance computation, and Jim McCann for project feedback. This work was supported by a Packard Fellowship, NSF Award 1717320, an NSF Graduate Research Fellowship, and gifts from Autodesk, Adobe, and Facebook.

Figures