Background Information and Techniques - Computer Animation: Algorithms and Techniques - page 485

vðt iþ 1 Þ¼vðt i Þþaðt i ÞDt

1
2 ðvðt i Þþvðt iþ 1 ÞÞDt
xðt iþ 1 Þ¼xðt i Þþvðt i ÞDt þ

xðt iþ 1 Þ¼xðt i Þþ

(B.155)

1
2 aðt i ÞDt

2

The Verlet method
Verlet integration is used to update the position directly from acceleration without explicitly calculat-
ing velocity. Essentially, the difference between the current position and the previous position is used
as velocity. This vector is updated by acceleration and added to the current position to generate the next
position (see Eq. B.156 ) .

xðt iþ 1 Þ¼

2 xðt i Þxðt i 1 Þþaðt i ÞDt

2

(B.156)

The Leapfrog method
The Leapfrog method is unique in its temporal symmetry. It can be run forward in time or backward in
time and it will trace out the same path. Position and acceleration are evaluated on the interval while
velocity is evaluated on the half interval relative to the position (see Eq. B.157 ) .

xðt iþ 1 Þ¼xðt i Þþvðt iþ

2 ÞDt

1

(B.157)

vðt iþ Þ¼vðt iþ Þþaðt iþ 1 ÞDt

3
2

1
2

B.9 Optimization
As the field of computer graphics and computer animation matures, more complex and mathemat-
ically sophisticated techniques are being used. An increasingly important mathematical tool is
optimization ,alsoknowas mathematical programming . 2 This discussion is intended for the reader
who is well versed in computer graphics and familiar with the basics of calculus, but who has not had
much, if any, exposure to mathematical techniques involving optimization and who might be a
bit intimidated whenever discussion turns that direction. Optimization is a complex and expansive
topic, and finds application in control theory, chemistry, meteorology, VLSI CAD, geophysics,
power grid design, and many others. A complete treatment is beyond the scope of the current
discussion and the interested reader should follow up with material from the graphics literature
(e.g., [ 27 ][ 28 ] ) or the mass of material on optimization in general (e.g., [ 29 ] ) or in the literature
concerning a specific application of interest.
In computer graphics, optimization finds application in areas such as surface fitting, decimation,
inverse kinematics, motion capture data editing, physically based motion, and path construction. These
tasks have certain features in common. For example, problems in these areas usually have a large

2 The term “programming” refers to the U.S. military's use of the term program as applied to logistics, the problem domain for
the first early optimization techniques, referring to a well-defined procedure for doing something (i.e., linear programming),
and has nothing to do with computer programming.