94 COMMUNICATIONS OF THE ACM | NOVEMBER 2017 | VOL. 60 | NO. 11
remaining sum. Heat flow can then be computed by solving
the symmetric positive-definite system
(M –tLC)u = δγ,
where Af is the area of the triangle, N is its
outward unit normal, ei is the ith edge vector
(oriented counter-clockwise), and ui is the value of u at the
opposing vertex. The integrated divergence associated with
vertex i can be written as
where the sum is taken over incident triangles j each with a
vector Xj, e1, and e2 are the two edge vectors of triangle j con-
taining i, and θ1, θ2 are the opposing angles. If we let b ∈ R|V|
be the vector of (integrated) divergences of the normalized
vector field X, then the final distance function is computed
by solving the symmetric Poisson problem
As noted in Section 3. 1, the solution to step I is a function
that decays exponentially with distance. Fortunately, nor-
malization of small values is not a problem because floating
point division involves only arithmetic on integer exponents;
likewise, the large range of magnitudes does not adversely
affect accuracy because gradient calculation is local. For
the calculation of phi itself we advocate the use of a direct
(Cholesky) solver in double precision; empirically we observe
roughly uniform pointwise relative error across the domain.
Polygon meshes. Curved surfaces are often described
by polygons that are neither planar nor convex; although
such polygons can of course be triangulated, doing so
can adversely affect an existing computational pipeline.
We instead leverage the polygonal Laplacian of Alexa and
Wardetzky1 to implement the heat method directly on polygonal meshes—the only challenge in this setting is that for
nonplanar polygons the gradient vector no longer has a clear
geometric meaning. This issue is resolved by noting that we
need only the magnitude |∇u| of the gradient; see Crane et
11 Section 3. 2. 2 for further details. Figure 9 demonstrates
distance computed on an irregular polygonal mesh.
Point clouds. Raw geometric data is often represented
as a discrete point sample P ⊂ Rn of some smooth surface
M. Rather than convert this data into a polygon mesh, we
can directly implement the heat method using the point
cloud Laplacian of Liu et al.,
22 which extends previous
work by Belkin et al.
2 Computation of the gradient and di-
vergence are described by Crane et al,
11 Section 3. 2. 3. Other
discretizations are certainly possible (see for instance
the work of Luo et al.
23); we picked one that was simple to
implement in any dimension. It is particularly interesting
to note that the cost of the heat method depends primarily
on the intrinsic dimension n of M, whereas methods based
on fast marching require a grid of the same dimension m
as the ambient space25—this distinction is especially im-
portant in contexts like machine learning where m may be
significantly larger than n.
Choice of time step. Accuracy of the heat method relies
in part on the time step t. In the smooth setting, Equation ( 5)
suggests that smaller values of t yield better approximations of geodesic distance. In the discrete setting we instead observe the somewhat surprising behavior that the
limit solution to Equation ( 3) depends only on the number
of edges between a pair of vertices, independent of how we
might try to incorporate edge lengths into our formulation—
see Crane et al.,
11 Appendix A. Therefore, on a fixed mesh
decreasing the value of t does not necessarily improve accuracy, even in exact arithmetic—to improve accuracy we must
simultaneously refine the mesh and decrease t accordingly.
Moreover, very large values of t produce an over-smoothed
approximation of geodesic distance (Section 3. 3). For a fixed
mesh, we therefore seek an optimal time step t that is neither
too large nor too small.
An optimal value of t is difficult to obtain due to the complexity of analysis involving the cut locus.
28 We instead use a
simple estimate that works well in practice, namely t = mh2
where h is the mean spacing between adjacent nodes and
m > 0 is a constant. This estimate is motivated by the fact that
h2∆ is invariant with respect to scale and refinement; numerical experiments suggest that m = 1 yields near-optimal accuracy
for a wide variety of problems. In this paper the time step
is therefore used uniformly throughout all tests and examples, except where we explicitly seek a smoothed approximation of distance, as in Section 3. 3. For highly nonuniform
meshes one could set h to the maximum spacing, providing
a more conservative estimate. Numerical underflow could
theoretically occur for extremely small t, though we do not
encounter this issue in practice.
Numerics. As demonstrated in Figures 10, 18, and 19, one
does not need a particularly nice mesh or point cloud to get a
reasonable distance function. However, as with any numerical
Figure 9. Since the heat method is based on well-established
discrete operators like the Laplacian, it is easy to adapt to a variety
of geometric domains. Above: distance on a hippo composed of high-degree nonplanar (and sometimes nonconvex) polygonal faces.