implementation; Potential is the time taken to compute the
right hand side in step III.
In practice, a number of factors affect the run time of
the heat method including the choice of spatial discretization, discrete Laplacian, and geometric data structures.
As a typical example, we compared the scheme from
Triangle meshes section to the first-order fast marching method of Kimmel and Sethian19 and the exact algorithm of Mitchell et al., 27 using the state-of-the-art fast
marching implementation of Peyré and Cohen31 and the
exact implementation of Kirsanov. 40 The heat method
was implemented in ANSI C in double precision using a
vertex-face adjacency list. Single-threaded performance
was measured on a 2. 4 GHz Intel Core 2 Duo (Table 1).
Note that even for a single distance computation the heat
method outperforms fast marching; more importantly,
updating distance for new subsets γ is consistently an
order of magnitude faster (or more) than both fast marching and the exact algorithm.
4. 2. Accuracy
We examined errors in the heat method, fast marching, 19
and the polyhedral distance, 27 relative to mean edge length
h on triangulated surfaces. Both fast marching and the
heat method appear to exhibit linear convergence; it is
interesting to note that even the exact polyhedral distance
provides only quadratic convergence. Keeping this fact in
mind, Table 1 uses the polyhedral distance as a baseline
for comparison on more complicated geometries—Max is
the maximum error as a percentage of mesh diameter and
Mean is the mean relative error at each vertex. Note that
fast marching tends to achieve a smaller maximum error,
whereas the heat method does better on average. Figure 16
gives a visual comparison of accuracy; the only notable discrepancy is a slight smoothing at sharp cusps, which may
explain the larger maximum error. Figure 17 indicates that
smoothing does not interfere with the extraction of the
cut locus—here we visualize values of |∆φ| above a fixed
threshold. Overall, the heat method exhibits errors of the
same order and magnitude as fast marching (at lower computational cost) and is therefore suitable in applications
where fast marching is presently used; see Crane et al. 11 for
more extensive comparisons.
Table 1. Comparison with fast marching and exact polyhedral distance
Figure 16. Visual comparison of accuracy. Left: exact polyhedral
distance. Using default parameters, the heat method (middle) and
fast marching (right) both produce results of comparable accuracy,
here within less than 1% of the polyhedral distance—see Table 1 for a
more detailed comparison.
Figure 17. Medial axis of the hiragana letter “a” extracted by
thresholding second derivatives of the distance to the boundary. Left:
fast marching. Right: heat method.
More recent implementations of the heat method improve
accuracy by using a different spatial discretization, 29 or
by iteratively updating the solution. 3 The accuracy of fast
marching schemes is determined by the choice of update
Heat method Fast marching
error (%) Time (s)
error (%) Exact time (s)
Bunny 28k 0.21 0.01s (28x) 3. 22 1. 12 0.28 1.06 1. 15 0.95
Isis 93k 0.73 0.05s (21x) 1. 19 0.55 1.06 0.60 0.76 5. 61
Horse 96k 0.74 0.05s (20x) 1. 18 0.42 1.00 0.74 0.66 6. 42
Kitten 106k 1. 13 0.06s (22x) 0.78 0.43 1. 29 0.47 0.55 11. 18
Bimba 149k 1. 79 0.09s (29x) 1. 92 0.73 2. 62 0.63 0.69 13. 55
Aphrodite 205k 2. 66 0.12s (47x) 1. 20 0.46 5. 58 0.58 0.59 25. 74
Lion 353k 5. 25 0.24s (24x) 1. 92 0.84 10. 92 0.68 0.67 22. 33
Ramses 1.6M 63. 4 1.45s (68x) 0.49 0.24 98. 11 0.29 0.35 268.87
Best speed/accuracy in bold; speedup in orange.