Graphics Reference
In-Depth Information
Semi-Implicit Euler methods, and to the scheme previously presented in Equa-
tions 35.37 and 35.38. Heun's method is also known as the
Modified Euler
and
Explicit Trapezoidal
methods.
Let
Z
=
Y
+
D
(
t
,
Y
)
·
Δ
t
(35.74)
s
=
t
+Δ
t
(35.75)
Δ
Y
=
D
(
t
,
Y
)+
D
(
s
,
Z
)
2
·
Δ
t
(35.76)
35.6.7.5 Explicit Fourth-Order Runge-Kutta
The classic fourth-order Runge-Kutta method is one of the most commonly used
integrators for dynamics in computer graphics and is the most accurate integrator
in this chapter. It is:
K
1
=
D
(
t
,
Y
)
(35.77)
K
2
=
D
(
t
+
Δ
t
Δ
t
2
)
2
,
Y
+
K
1
·
(35.78)
K
3
=
D
(
t
+
Δ
t
Δ
t
2
)
2
,
Y
+
K
2
·
(35.79)
K
4
=
D
(
t
+Δ
t
,
Y
+
K
3
·
Δ
t
)
(35.80)
Δ
Y
=
1
6
(
K
1
+
2
K
2
+
2
K
3
+
K
4
)
·
Δ
t
(35.81)
One might always use fourth-order Runge-Kutta, and in fact, that is the
approach of many dynamics experts. However, for state configurations in which
evaluating
D
is very expensive, one must consider the net cost of using a better
integrator compared to using more and smaller time steps with a worse integrator.
We generally care about the wall-clock time to achieve stable integration, and that
might be better achieved through taking many small Euler steps. Again we see
analogy to light transport: Many inexpensive samples may achieve faster conver-
gence than few expensive samples. Thus, only with an end-to-end convergence,
stability, and performance goal can we make a design decision for a particular
system.
While performance and scalability are important, dynamics is one of the few areas
in computer graphics where numerical stability, and not performance, is the pri-
mary concern and focus of advancement. Numerical stability is related to preci-
sion and accuracy, but it is not the same as them. A simulation of a block tumbling
down stairs is
accurate
if it produces results close to those of the corresponding
real-world scenario. The simulation is
precise
if there are many bits in the output
(regardless of whether they have the correct values!). The simulation is
stable
if
the block reliably tumbles down, rather than gaining energy and launching into
space or exploding, for example. The challenge is that stability is often opposed
to accuracy. If the block merely remains sitting at the top of the stairs, even when
unbalanced, the simulation is stable but so inaccurate that it is useless. Although
stability is often driven by energy conservation, such events as missed collisions,
infinite (conserving) spring oscillations, and infinite (conserving) micro-collisions
may also be characterized as instability.
