i
i
i
i
i
i
i
i
17.5. Physics-Based Animation 435
These expressions are, of course, not the only way. One can, for example, use
f(t − Δt) instead of f(t) above and divide by 2Δt. For an equation containing
a time derivative, it is now possible to propagate values of an unknown function
forward in time in a sequence of Δt-size steps by solving the system of difference
equations (one at each spatial location) for unknown f (t +Δt). Some initial
conditions, i.e., values of the unknown function at t =0, are necessary to start the
process. Other information, such as values on the boundary of the domain, might
also be required depending on the specific problem.
The computation of f(t+Δt) can be done easily for so called explicit schemes
when all other values present are taken at the current time and the only unknown
in the corresponding difference equation f (t +Δt) is expressed through these
known values. Implicit schemes mix values at current and future times and might
use, for example,
f(x +Δx, t +Δt) − f (x, t +Δt)
Δx
as an approximation of
∂f
∂x
. In this case one has to solve a system of algebraic
equations at each step.
The choice of difference scheme can dramatically affect all aspects of the
algorithm. The most obvious among them is accuracy. In the limit Δt → 0
or Δx → 0, expressions of the type in Equation (17.2) are exact, but for finite
step size some schemes allow better approximation of the derivative than others.
Stability of a difference scheme is related to how fast numerical errors, which are
always present in practice, can grow with time. For stable schemes this growth is
bounded, while for unstable ones it is exponential and can quickly overwhelm the
solution one seeks (see Figure 17.24). It is important to realize that while some
stable
f(t)
exact
unstable
Figure 17.24. An unsta-
ble solution might follow the
exact one initially, but can
deviate arbitrarily far from it
with time. Accuracy of a
stable solution might still be
insufficient for a specific ap-
plication.
inaccuracy in the solution is tolerable (and, in fact, accuracy demanded in physics
and engineering is rarely needed for animation), an unstable result is completely
meaningless, and one should avoid using unstable schemes. Generally, explicit
schemes are either unstable or can become unstable at larger step sizes while
implicit ones are unconditionally stable. Implicit schemes allows greater step size
(and, therefore, fewer steps) which is why they are popular despite the need to
solve a system of algebraic equations at each step. Explicit schemes are attractive
because of their simplicity if their stability conditions can be satisfied. Developing
a good difference scheme and corresponding algorithm for a specific problem is
not easy, and for most standard situations it is well advised to use an existing
method. Ample literature discussing details of these techniques is available.
One should remember that, in many cases, just computing all necessary terms
in the equation is a difficult and time-consuming task on its own. In rigid body
or cloth simulation, for example, most of the forces acting on the system are due