Graphics Reference
In-Depth Information
35.6.7.1 Explicit Forward Euler
We've already seen the Explicit (a.k.a. Forward) Euler method,
Δ
Y
=
D
(
t
,
Y
)
·
Δ
t
,
(35.69)
in which
Y
is the initial state of the system,
D
is the field for which
D
(
t
0
,
Y
)
≈
d
Y
(
t
0
)
dt
, and
Δ
t
is the duration of the time interval.
This is perhaps the simplest and most intuitive integrator. The change in state
of the system is our estimate of the current derivative scaled by the time step. For
position, this corresponds to assuming that velocity is constant (i.e., acceleration is
zero) and thus advancing by the current velocity. It obviously is a good estimator
when those conditions are true and is a worse estimator when there is significant
acceleration.
/
35.6.7.2 Semi-Implicit Euler
Explicit Euler integration only considers the derivative (e.g., velocity) at the begin-
ning of a time step. Under large accelerations, that is a poor estimate for the deriva-
tive throughout the time step. An alternative is to use the derivative from the
end
of the time step. The challenge in doing so is that since we're trying to estimate
the state of the system at the end of the time step, it is hard to use values from that
time to reach it.
The Semi-Implicit Euler (confusingly also known as Semi-Explicit Euler)
method performs a tentative Explicit Euler step to the end of a time interval and
measures the derivative there. It then returns to the beginning of the interval and
applies the discovered derivative to the original position. This is more stable than
Explicit Euler and much less expensive than the full Implicit Euler method, which
requires iterating on this process to find a fixed point [Par07].
Expressed in our state notation, the Semi-Implicit Euler integrator is
Let
Z
=
Y
+
D
(
t
,
Y
)
·
Δ
t
;
(35.70)
s
=
t
+Δ
t
;
(35.71)
Δ
Y
=
D
(
s
,
Z
)
·
Δ
t
.
(35.72)
35.6.7.3 Second-Order Runge-Kutta
Runge-Kutta
5
refers to a family of related iterative methods for approximating
solutions to ODEs. They are described by a set of coefficients and the number
of stages, where each stage requires one evaluation of
D
based on the result of
previous evaluations. See [Pre95] for the general form of Runge-Kutta methods.
Explicit Euler is the only one-stage Runge-Kutta method. A commonly
employed one of the many possible two-stage Runge-Kutta methods is
Δ
Y
=
D
t
i
+
Δ
t
2
D
(
t
i
,
Y
i
)
2
,
Y
i
+
Δ
t
·
Δ
t
.
(35.73)
35.6.7.4 Heun
Heun's method is an improved two-stage Runge-Kutta method compared to the
one just presented. It is equivalent to averaging the steps from the Explicit and
5. Phonetically: “run-ga cut-a”
