Graphics Reference
In-Depth Information
It's actually a little worse: the Nyquist limit essentially means that
even in a pure translation velocity field with no distortion, the maximum
spatial frequency that can be reliably advected has period 4Δ
x
.Higher-
frequency signals, even though you might resolve them on the grid at
a particular instant in time, cannot be handled in general: e.g., just in
one dimension the highest-frequency component you can see on the grid,
cos(
πx/
Δ
x
), exactly disappears from the grid once you advect it by a
distance of
1
2
Δ
x
.
A “perfect” Eulerian scheme would filter out the high-frequency com-
ponents that can't be reliably resampled at each time step, and a bad one
will allow them to alias as artifacts. The distortions inherent in non-rigid
velocity fields mean that as time progresses, some of the lower-frequency
components get transferred to higher frequencies—and thus must be de-
stroyed. But note that the fluid flow, after squeezing the field along some
axes at some point, may later stretch it back out—transferring higher fre-
quencies down to lower frequencies. However, it's too late if the Eulerian
scheme has already filtered them out.
At small enough length scales, viscosity and other molecular diffusion
processes end up dominating advection: if Δ
x
is small enough, Eulerian
schemes can behave perfectly well since the physics itself is effectively band-
limiting everything, dissipating information at higher frequencies. This
brute-force approach leads to the area called direct numerical simulation
(DNS), which comes in handy in the scientific study of turbulence for ex-
ample. However, since many scenarios of practical interest would require
Δ
x
less than a millimeter, DNS is usually far too expensive for graphics
work.
A more ecient approach is to use adaptive grids, where the grid res-
olution is increased where higher resampling density is required to avoid
informationloss,anddecreasedwherethefieldissmoothenoughthatlow
resolution suces. This can be done using octrees (see for example Losasso
et al. [Losasso et al. 04]) or unstructured tetrahedral meshes (see for exam-
ple by Feldman et al. [Feldman et al. 05] or Wendt et al. [Wendt et al. 07]).
However, these approaches suffer from considerable implementation com-
plexity, increased overhead in execution, and typically lower accuracy com-
pared to regular grids of similar resolution—and still must enforce a maxi-
mum resolution that, for practical purposes, tends to be much coarser than
the DNS ideal.
This is where the subject of particle methods comes into play. If we store
a field on particles that move with the flow, it doesn't matter how the flow
distorts the distribution of particles: the advection equation
Dq/Dt
=0
