Graphics Reference
In-Depth Information
X
(
t
0
)+
X
(
t
0
)(
t
X
(
t
)
≈
−
t
0
)
.
(35.67)
The highest-order term present in this approximation is the
n
=
1term,so
this is called a first-order approximation. This particular first-order approximation
leads to the integration scheme just presented, and is known as
Forward Euler
integration.
The error in an approximation of a Taylor polynomial with a finite number of
terms is the missing higher-order terms. If the magnitude of higher-order deriva-
tives grows no faster than the factorial, higher-order terms have successively less
impact. This is true for many functions encountered in practice, especially physi-
cal simulation without impulses. The error in a first-order approximation is there-
fore dominated by a second-order term. That term contains
(
t
t
0
)
2
, so for a time
−
t
0
, it is often referred to as growing like
O(Δ
t
2
)
. This is a bit mis-
leading. For large
n
, the factorial in the denominator decreases the magnitude of
the higher-order terms faster than the exponent on
Δ
t
. Furthermore, for
Δ
t
step
Δ
t
=
t
−
1,
Δ
t
n
increases
with order, and the point at which that occurs depends on the arbi-
trary choice of units for measuring time (although the derivative also changes to
counteract this, as we'll see in a moment). So a better way to think about the accu-
racy of an approximation is that an “
n
th-order approximation” contains
n
terms of
the Taylor expansion.
In a dynamics system we do not have an explicit function for higher-order
derivatives of
X
. However, by applying the definition of the derivative to
D
,we
can estimate higher-order derivatives for specific values of
t
. For example:
>
D
(
t
,
X
(
t
))
−
D
(
t
0
,
X
(
t
0
))
X
(
t
) = lim
t
→
t
0
.
(35.68)
t
−
t
0
t
0
, with accuracy typically
decreasing at larger time steps. Recursively applying the numerical derivative
form allows estimation of arbitrarily high derivatives. Note that the
n
th derivative
contains
(
t
We can approximate the limit by choosing any
t
>
t
0
)
n
in its denominator, which will be canceled by the same coeffi-
cient in the numerator of the Taylor polynomial. Thus, many numerical integrators
don't explicitly contain higher powers of the time step in their final form.
The challenge in estimating the numerical derivatives is that we can't apply
the
D
function at
t
0
unless we know
X
(
t
0
)
. Since we're trying to solve for
X
(
t
0
)
,
this means we can't solve until we already know the solution. Fortunately, we can
estimate
X
(
t
0
)
with some
(
n
−
1
)
th-order method. We can then use that value
to numerically estimate an
n
th-order derivative. To prevent the error from these
successive estimations from accumulating, many schemes then go back and rees-
timate
X
(
t
0
)
.
One can estimate arbitrarily high derivatives with arbitrary accuracy by this
method. Increasing accuracy in the derivatives allows larger time steps, which
allows fewer computations per unit simulation time. However, there is a com-
putational cost for each
D
evaluation. If the net cost of computing an accurate
derivative to take a large time step is higher than that of computing a less accu-
rate derivative and making many small time steps, nothing has been gained. The
choice of what order of integrator to apply therefore depends on the cost of
D
,
which depends on the complexity of the scene and forces. This is why there is no
single “best” integration scheme for dynamics.
−
