Graphics Reference
In-Depth Information
not). For more accuracy, we can repeat the sweeps again; in practice two
times through the sweep gives good results, though more iterations are
possible.
The benefit of fast sweeping over fast marching is that it is
O
(
n
), re-
quires no extra data structures beyond grids, and thus is extremely simple
to implement. However, the fast marching method has a significant ad-
vantage in that it permits
narrow-band
methods: that is, if we don't need
the signed distance function more than, say, five grid cells away from the
surface, we can stop the algorithm once we hit that distance. For example,
in our fluid code, if we choose the time step based on the five-grid cell
heuristic (3.2), we shouldn't ever go beyond five grid cells from the current
surface. In this case, fast marching only takes
O
(
m
log
m
) time, where
m
is the number of grid cells set—typically much smaller than the number of
grid cells in the whole grid. The remaining grid points can have their
φ
values set to
±
5Δ
x
in this example.
6.2.3 Moving the Level Set
The most critical part of the simulation is actually moving the surface
represented by the level set. The free surface, i.e., the points where
φ
=0,
should be advected with the fluid velocity: we can simply advect the entire
function to capture this. That is, we solve
Dφ
Dt
=0
.
(6.1)
Unfortunately, advecting a signed distance field doesn't in general pre-
serve the signed distance property. Thus, we generally need to periodically
recalculate signed distance as we have discussed above. Recalculating dis-
tance can perturb the interface, though, so we don't want to do this too
frequently—perhaps just once a frame.
A worse problem in advection is numerical dissipation. Any small fea-
tures in the surface—ripples, droplets, thin sheets, etc.—are in danger of
being smoothed out of existence. Tri- or bilinear interpolation in a semi-
Lagrangian method really is inadequate in this case; at the very least your
code should use the sharper Catmull-Rom interpolation, if not other more
accurate techniques.
This leads us to a sampling condition of sorts for level sets. Any part of
the geometry less than
Δ
x
in width cannot be reliably captured on the
grid: in some configurations it may show up, but after advection it may fall
between grid points and disappear, never to return. This is very similar to
the Nyquist limit when considering which functions can be reconstructed
∼
