Graphics Reference
In-Depth Information
C++, or Java, a function in Python, Scheme, or Matlab, and a function pointer and
void
pointer in C.
The integrator that advances
Y
i
to
Y
i
+
1
is shown in Listing 35.4.
Listing 35.4: ODE integrator using Explicit Euler steps.
1
2
3
4
5
6
7
8
9
10
11
vector<float> integrate
(float
t
,
vector<float>
Y
,
float
Δ
t
,
vector<float>
D
(float
t
, vector<float>
Y
){
// Insert your preferred integration scheme on the next line:
Δ
Y
=
D
(
t
,
Y
)
·
Δ
t
return
Y
+Δ
Y
}
We will replace the center line with alternate expressions in what follows. The
method shown is the least computationally expensive and least accurate reason-
able method for evaluating
Δ
Y
.
There is a tradeoff between the computational cost of a single iteration and the
number of iterations required to maintain accuracy. In general, one is willing to
perform significantly more work per iteration to take large time steps. However,
for graphics applications the time step may be driven by the rendering or user
input rate, and therefore there is a limit to how large it can be made. Furthermore,
the
D
function may be very expensive to evaluate because it can include collision
detection and a constraint solver. Thus, although for general applications the 4th-
order Runge-Kutta scheme is the default choice, many dynamics simulators for
real-time computer graphics still rely on simple Euler integration.
The basic idea underlying all of the integration schemes presented in this chap-
ter is that any infinitely differentiable function
f
can be expressed as the Taylor
polynomial,
4
N
d
n
f
(
t
0
)
dt
n
t
0
)
n
n
!
(
t
−
f
(
t
) = lim
N
→∞
(35.65)
n
=
0
...
t
0
)
2
2
t
0
)
3
6
t
0
)+
f
(
t
0
)
(
t
−
f
(
t
0
)
(
t
−
=
f
(
t
0
)+
f
(
t
0
)(
t
−
+
+
...
(35.66)
A finite number of Taylor terms allows approximation of
f
(
t
)
for arbitrary
t
.
To apply this, we must know the value of the function
f
(
t
0
)
at some specific time
t
0
, and some derivatives of
f
at
t
0
. For the dynamics application of approximat-
ing
Y
X
(
t
)
, we know
X
(
t
0
)
because that is the current state of the system.
We also know
X
(
t
0
)
because that is the velocity and acceleration, which can be
computed by the
D
function. We can therefore immediately make the two-term
approximation:
≈
4. This is only guaranteed to hold on some neighborhood of
t
0
. In practice, this neighbor-
hood is usually the whole real line (for functions which mathematians call “analytic”),
but there exist functions for which the neighborhood is very small. Impulses are one
case where the neighborhood is
not
the entire real line, which gives more intuition as
to why they do not interact well with the ODE framework for dynamics.
