since it tends to produce results more accurate than fast
marching at a similar computational cost. However, accuracy is measured relative to the polyhedral distance rather
than the smooth geodesic distance of the approximated surface. Like fast marching, Surazhsky’s method does not take
advantage of precomputation and therefore exhibits a significantly higher amortized cost than the heat method; it is
also limited to triangle meshes.
4. 3. Robustness
Two factors contribute to the robustness of the heat method,
namely ( 1) the use of an unconditionally stable time discretization and ( 2) an elliptic rather than hyperbolic formulation (i.e., relatively stable local averaging vs. more sensitive
global wavefront propagation). Figure 19 verifies that the
heat method continues to work well even on meshes that
are poorly discretized or corrupted by a large amount of
noise (here modeled as uniform Gaussian noise applied
to the vertex coordinates). In this case we use a moderately
large value of t to investigate the behavior of our smoothed
distance; similar behavior is observed for small t values.
Figure 18 illustrates the robustness of the method on a surface with many small holes as well as long sliver triangles.
The heat method is a simple, general method that can be easily incorporated into a broad class of algorithms. However, a
rule—a number of highly accurate rules have been developed for regular grids (e.g., HJ WENO18), but fewer options
are available on irregular domains such as triangle meshes,
the predominant choice being the first-order update of
Kimmel and Sethian.
19 Finally, the approximate algorithm
of Surazhsky et al.
40 provides an interesting comparison
Figure 18. Smoothed geodesic distance on an extremely poor
triangulation with significant noise—note that small holes are
essentially ignored. Also note good approximation of distance even
along thin slivers in the nose.
Figure 19. Tests of robustness. Left: our smoothed distance (m = 104)
appears similar on meshes of different resolution. Right: even for
meshes with severe noise (top) we recover a good approximation of
the distance function on the original surface (bottom, visualized on
Figure 20. In any method based on a finite element approximation,
mesh quality will affect the quality of the solution. However, because
the heat method is based on solving low-order elliptic equations
(rather than high-order or hyperbolic equations), it often produces
fewer numerical artifacts. Here, for instance, we highlight spurious
extrema in the distance function (i.e., local maxima and minima)
produced by the fast marching method (left), biharmonic distance
(middle), and the heat method (right) on an acute Delaunay mesh
(top) and a badly degenerate mesh (bottom). Inset figures show
closeup view of isolines for the bottom figure.
Fast Marching Biharmonic Heat Method