Graphics Reference
In-Depth Information
Here
f
i
is the known function value at
x
i
,and
s
i
is the known derivative
(slope). It's not hard to verify that the cubic
5
is
x
i
)+
−
(
x
3
f
i
+3
f
i
+1
Δ
x
2
+
−
2
s
i
−
s
i
+1
x
i
)
2
p
(
x
)=
f
i
+
s
i
(
x
−
−
Δ
x
+
2
f
i
−
(
x
2
f
i
+1
Δ
x
3
+
s
i
+
s
i
+1
Δ
x
2
x
i
)
3
.
−
Catmull-Rom uses a central finite difference to approximate the derivatives
from nearby function values:
f
i
+1
−
f
i−
1
2Δ
x
s
i
+1
=
f
i
+2
−
f
i
s
i
=
,
.
2Δ
x
Plugging this in, regrouping terms, and substituting
x
x
i
Δ
x
−
x
=
gives the following:
p
(
x
)=
f
i−
1
2
x
3
+
f
i
1
2
x
3
1
2
x
+
x
2
1
5
2
x
2
+
3
−
−
−
+
f
i
+1
1
2
x
3
+
f
i
+2
2
x
3
.
3
1
2
x
2
+
1
2
x
+2
x
2
−
−
This can be shown to have cubic accuracy when approximating a smooth
function, as opposed to the lower quadratic accuracy of linear interpola-
tion. To extend this to higher dimensions, we simply interpolate along each
dimension in turn, in exactly the same way as bi- or trilinear interpolation
can be constructed from one-dimensional linear interpolation.
Using Catmull-Rom interpolation in the semi-Lagrangian method for
advection boosts the accuracy to second order (from first order for linear
interpolation) and significantly reduces the numerical dissipation. How-
ever, it doesn't have quite the same guarantees for stability as linear in-
terpolation. The issue is under- or overshooting: near local maximums
or minimums in the data, the cubic can go higher or lower than the data
points. Whereas linear interpolating between two data points always gives
you a number bounded by those data points, Catmull-Rom interpolation
might give you something larger or smaller. There is a worry, then, that if
used for advection there might be an unstable feedback loop: if each time
5
If you refer back to the paper by Fedkiw et al. [Fedkiw et al. 01], be aware that
there are small typos in the quadratic and cubic coecients, corrected here.
