Graphics Reference
In-Depth Information
Here a half-step is taken to get an intermediate position
x
mid
approximating
the particle's position halfway along the trajectory. The velocity field is
interpolated from the grid at this intermediate location, and that velocity
value is used to finally get to
x
P
. Depending on how large Δ
t
is—see later
in this chapter—it may even be wise to split the trajectory tracing into
smaller substeps for better accuracy.
We now know the position where the imaginary particle started; next
we have to figure out what old value of
q
it had. Most likely
x
P
is not on the
grid, so we don't have the exact value, but we can get a good approximation
by interpolating from
q
n
at nearby grid points. Trilinear (bilinear in two
dimensions) interpolation is often used, though this comes with a serious
penalty which we will fix at the end of the chapter.
Putting this together into a formula, our basic semi-Lagrangian formula,
assuming the particle-tracing algorithm has tracked back to location
x
P
(typically with RK2 above), is
q
n
+1
G
=
interpolate
(
q
n
,x
P
)
.
(3.1)
Note that the particle I've described is purely hypothetical. No particle
is actually created in the computer: we simply use Lagrangian particles
to conceptually figure out the update formula for the Eulerian advection
step. Because we are almost using a Lagrangian approach to do an Eulerian
calculation, this is called the semi-Lagrangian method.
Just for completeness, let's illustrate this in one dimension again, using
linear interpolation for the semi-Lagrangian operations.
For grid point
x
i
, the particle is traced back to
x
P
=
x
i
−
Δ
tu
. Assuming this lies in
the interval [
x
j
,x
j
+1
], and letting
α
=(
x
P
−
x
j
)
/
Δ
x
be the fraction of the
interval the point lands in, the linear interpolation is
q
P
α
)
q
j
+
αq
j
+1
.
=(1
−
So our update is
q
n
+1
i
α
)
q
j
+
αq
j
+1
.
=(1
−
In practice we will need to advect the velocity field, and perhaps addi-
tional variables such as smoke density or temperature. Usually the addi-
tional variables are stored at the grid cell centers, but the velocity compo-
nents are stored at the staggered grid locations discussed in the previous
chapter. In each case, we will need to use the appropriate averaged ve-
locity, given at the end of the previous chapter, to estimate the particle
trajectory.