Graphics Reference
In-Depth Information
points where smoothness is lost, and unfortunately the signed distance
function is not smooth at precisely the locations of interesting features that
we want to be able to preserve in advection. (Recall that
φ
has a “kink,” a
discontinuity in its gradient, at places that are equidistant from two or more
points on the boundary, i.e., the medial axis: the sharper a surface feature
is the closer this kink is to the surface and the more problems pure Eulerian
methods have with dissipation no matter how formally accurate they are.)
PLS, with help from particles, can achieve nearly the full accuracy possible
for a grid-based method and maybe a little bit more. . .
PLS begins with a grid-sampled level set,
φ
i,j,k
. Noting that it's only the
values of
φ
near the zero isocontour that define the surface, we'll concentrate
attention on accurately advecting just the grid cells where
is small
enough, say less than 3Δ
x
. Away from these critical grid cells, as long
as the advection algorithm doesn't erroneously flip the sign of
φ
,which
even the simplest semi-Lagrangian advection guarantees, we don't care how
much it diffuses or smears out the values: these can easily be corrected with
a distance reinitialization as discussed in Chapter 6.
It is these cells, within a 3Δ
x
band of the interface, where we'll add
particles. To avoid bias, particles are added on
both
sides of the interface,
φ
positive and negative—for a free surface liquid this means there are “air”
particles as well as “water” particles. Each particle, in addition to its po-
sition, includes its own estimate of the
φ
value, i.e., how far that particle
is from the true interface. Since we only need particles near the interface,
we can afford a relative dense sampling: in three dimensions, Fedkiw and
coauthors recommend seeding 64 per grid cell, perhaps at randomly jit-
tered positions. A particle's initial
φ
p
value can be interpolated from the
grid. Finally, to limit the effect of errant particles later on, the particle
φ
p
values are limited to [0
.
1Δ
x,
0
.
5Δ
x
] in absolute magnitude: particles with
smaller interpolated
φ
values shouldn't be seeded at all, and particles at
larger distances have their values clamped to
|
φ
|
0
.
5Δ
x
. More complicated
seeding is possible, attracting particles from their initial positions towards
a randomly-decided goal isocontour (distance from the interface): see the
original paper for details [Enright et al. 02a]. A particle
φ
p
value can be
thought of as the signed radius of the particle, with the smaller particles
actually touching the surface.
Both the grid level set values and the particles are advected forward each
time step. In smooth regions it's expected they will continue to agree, but
in more interesting regions the particles should be much more accurate.
Thus a series of error-correction passes are applied, where the particles
attempt to correct numerical dissipation errors in the grid, but features
±
