Computer Animation: Algorithms and Techniques

by Rick Parent
Morgan-Kaufmann, 2001.
Copyright © 2001 Rick Parent
All rights reserved

Ordering Information

This is a project under development. I will be adding more structure and more comments concerning the material here as I find time. Initially, I have only dumped the material that I used in developing the book. This will be refined over time.

In case anyone is interested, here is the on-line information I'm using this quarter in my class at OSU - I'm working on the slides as the quarter progresses (1/31/03).

Color Images

Material by Chapter

Chapters C Code Mathematica Code Figures Power Point Slides Animations
Ch. 1     X X  
Ch. 2 X X
Ch. 3 X X X X X
Ch. 4 X X X X
Ch. 5 X X
Ch. 6 X X
App. A X
App. B X X

C CODE Initially, the code is that directly from the book. It was tested with CodeWarrior on a MAC. As bugs are reported and suggestions for improvements are made, the code will deviate from that found in the book.
Mathematica CODE Mathematica was used to check out many of the equations presented in the book. The code used to do this is given here.
FIGURES Currently, the figures are from the manuscript which I submitted to the publisher. The figures which appear in the book are, in many cases, improved versions of these figures.
POWER POINT SLIDES I am currently in the process of converting my class notes to Powerpoint. These slides have been prepared on a MAC with Powerpoint. They are currently at a fairly high level. I will make more detailed slides as time permits and as I get more experience with their use in class. I welcome any comments or contributions anyone would like to make concerning these slides.
ANIMATIONS The animations depict basic techniques discussed in the text. The animations are in a variety of formats including: animated GIFs, MPEGS, and Quicktime Movies.

Jave3D Code

This is some sample Java3D code used to implement some of the algorithms.

Errata by Chapter

[Many thanks to the readers who have contributed to this list, most notably Nelson Max.]

Chapter 1

  1. The contribution of the Lumiere brothers should have been incorporated into Section 1.2.1 "Early Devices."
  2. p.23: P. Bergeron needs to be added to the credits for Dream Flight.
  3. p.24: Vol Libre was in 1980.
  4. p.26: The unnumbered section heading "Animation Comes of Age" should be numbered 1.4.3
Chapter 2
  1. p.43: I certainly could have explained this better. The plane is being rotated from its initial position in which its center is at the origin and its nose is pointed down the positive z-axis. From the values of the plane's final orientation and position in space given in Figure 2.5, the distance from its center to its nose is SQRT(50). So the initial position of its nose is (0,0,SQRT(50)).
  2. p.43: cosine of sigma should be SQRT(34)/SQRT(50) instead of 34/SQRT(50) as it appears. Notice that in the corresponding figure (Figure 2.6), sqrt(34) should be on the diagonal. In Figure 2.7, 'radical 5' should just be 5.
  3. p.44: separation is needed between the multiple matrix equations in Eq. 2.15 and in Eq. 2.16. As it stands now, they run together.
  4. p.51, starting 8 lines down: the cross product of the third and first rows doesn't have to be normalized because those rows are already unit vectors and perpendicular to each other (of course it doesn't hurt anything to do the normalization but it's waisted computation).
  5. p.60, Eq.2.24 and Eq. 2.26: for consistency, 'Rot' should be subscripted with 'q'.
  6. p.60, equations: I have actually mixed my use of 'Rot'. In equations 2.24-2.26, 'Rot' refers to the rotation calculation on a vector. In equations 2.27 and 2.28, 'Rot' refers to the quaternion that represents a rotation. To avoid confusion, I should use different symbols for those two different meanings.
  7. p.73, Eq.3.6: Note that if P(u) is a third degree polynomial, the the equation inside the radical of Eq.3.5 is a second degree polynomial squared. This is where the fourth degree polynomial of Eq. 3.6 comes from.
  8. p.74, Table 3.1: Note that the arc lengths have been normalized - by dividing the actual arc length of each entry by the total arc length.
Chapter 3
  1. p.70, first full paragraph: The first two sentences might be better as
    "Given that the position of an object in three-space is to be interpolated, the parameterized interpolation function defines a space curve. Assume the the path of the object is a cubic polynomial in terms of a single parametric value, as in Equation 3.1">
  2. p.77-78: In the adaptive approach, it should be noted that the error threshold should be scaled according to depth of subdivision.
  3. p. 79: by adaptive forward differencing, I mean to refer to the adaptive approach section on page 76, although that term (forward differencing) is not used there.
  4. p.87, bottom: the term k1/PI/2 should be k1/(PI/2)
  5. p.88, similar to above, the term should be: (1-k2)/(PI/2)
  6. p.93, next to last line: "traversesthe" should be "traverses the"
  7. p.9, "anytimeduring" => "any time during"
  8. p.95, case labeled "stalls": actually backs up a little according to the curve.
  9. p.99, Equation 3.27: The subscript "xu" in the equation should not be there.
  10. p.103, discussing the formatio of u,v,w in the Frenet Frame: there should be some discussion of specifically how the vectors are formed using cross-products, such as:
    1. are the equations for left-hand space or right-hand space?
    2. does the vector v point into the curvature or away from it?
  11. p.130, 5 lines down: "There is no reason why the function (f(x) in Figure 3.63) ..."
    should be:
    "There is no reason why the function (s(x) in Figure 3.63) ..."
  12. p. 133-134: replace occurrances of P0 in Eq. 3.39-3.43 with P0.
  13. p. 135, just below Eq. 3.44: The interpolation function is not necessarily "tricubic" as the text states. The order of the Bezier in each direction depends on the number of control points in that dimension of the lattice.
  14. p.142, Figure 3.77: the FFD diagram appears to generate a deformation that is not C1; it would be in reality (this is a hand-drawn example, not the output of an actual FFD transformation using non-linear interpolation).
  15. p.157, under Section 3.9.2: The surface constructed does not form polygons of a regular polytope.
  16. p.163, 2nd paragraph from the bottom: it could be explained how the initial face Fa is found. The point is tested to see if it's on the inside side of each edge of the traingulated faces. Cross products can be used to generate a vector normal to the plane in which the vertex and the edge lie. This can be formed so that the normal points toward the center of the sphere when the vertex is on the 'inside' side of the edge. The dot product is formed between the normal and the vector from the vertex to the sphere. If the dot product is positive, then the vertex is on the inside side of the sphere. The vertex is inside of the first triangle such that the vertex is on the inside side of all three of its edges.
  17. p. 164, line 6: there is an 'I' that should italicized (e.g. 'I')
  18. p. 170, reference 15: should be "T. Defanti".
Chapter 4
  1. p.184 pseudocode; I extracted this from working code and tried to simplify it down into something transparent - but it looks like I simplified too much and introduced several errors as well...
    1. the 'eval_node' routine should have a parameter of '*node' instead of 'node'
    2. in 'eval_node', the 'obj' should be 'node->obj'
    3. the line
      should be
    4. under the 'node_struct' definition there should be a 'trans_mat m' field (the data preparation matrix)
    5. in a couple places 'struct arc' should be 'struct arc_struct'
    6. in a couple places '->node' should be '->nptr'
    7. the 'eval_tree' parameter should be a pointer
  2. p.184-5: it should be noted that the pushing and popping of the transformation matrices discussed in the text is handled by the subroutine parameter stack in the psuedocode.
  3. p.193, 4th last line of text: L1-L2 should be |L1-L2|; absolute value is required for case L2>L1.
  4. p.194, the last equation of Figure 4.18 has unnecessary pair of parentheses and should be '180-theta2' on the left.
  5. p.194, theta-sub-T = atan2(y,x) would avoid division by zero problems.
  6. p.196, the Jacobian, Eq. 4.15: the numerators should be the change of the position and orientation of the end effector (not the change to the linear velocity and change to the angular velocity).
  7. p.199, Eq. 4.16: the left-hand side should be expressed as a rate of change.
  8. p.200, Eq. 4.20: first line has J clipped so it looks almost like an 'I'
  9. p.200-201, Eq. 4.19-4.23: these need more complete treatment in the text. They are over-simplifications. In particular, the equation of J+ in the text paragraph is only true when J is square and non-singular.
  10. p. 204, Fig. 4.23: The 'object property' box should also list 'orientation' as a property. Forces are calculated using 'momenta' as well as mass.
  11. p. 206-7: the midpoint method is never actually presented in the text although it is mentioned. It is used on p. 205 but not identified as such.
  12. p. 211, Eq. 4.38: the top row of the 3x3 matrix should read [0 -Az Ay] instead of [0 -Ax Ay].
  13. p. 221: edge-face intersections don't quite capture all intersections - coplanar triangles where one is contained inside the other is not detected. However if the endpoints of edges adjacent to the contained face are considered to intersect the containing face. This is not a 'proper' intersection in that, locally, the volume of intersection is zero.
  14. p. 227, pseudocode: refers to obsolete equation numbers.
    1. EQ 121 should be Eq. 4.73
    2. EQ 126 should be Eq. 4.77
  15. p. 226, eq. 4.76: the last '+' in the equation should be a '-'
  16. p.245, pseudocode at bottom:
    should be
  17. p.252, bottom: B is uniquely identified such that B,P, and C form a right triangle. This is not noted in the text.
  18. p.256, bottom of text: Thrust doesn't always exceed drag - only when accelerating.
  19. p.256, "geometric flight": as defined by Reynolds [25], geometric flight "refers to a certain type of motion along a path: a dynamic, incremental, rigid geometrical transformation of an object, moving along and tangent to a 3D curve." The object's steering is "rotations about the local X and Y axes (pitch and yaw), which realign the global orientation of the local Z axis."
  20. p.257, bottom of top partial paragraph:
    "Thus, to maintain level flight during a turn, one must maintain the vertical component of lift by increasing the speed."
    Actually, the thrust needs to be increased, not the speed. The increased thrust will counteract the fact that the lift vector is no longer pointing directly up.
  21. p.263, Figure 4.62: sketch on the left for w1=w2=1.0 is a bit sloppy - it should be symmetric.
Chapter 5
  1. p.283, bottom: ref [25] should be [26].
  2. p.286, bottom text: the reference to Figure 5.16 should be to Figure 5.18
  3. p.300, line 2: reference [30] should be [29].
  4. p.300-302, Figure 2.26-2.27: titles of the figures are reversed
  5. p.301: a reference to Plate 4 would be appropriate.
Chapter 6
  1. p.319, top: someone questioned the statement "the elbow can...extend to as much as 160 degrees". I'm not sure where I got that value from. It's probably closer to 180 degrees unless you're a body builder. Most references state the range of motion as being 150 degrees but don't nail down the extension.
  2. p.350, top partial paragraph:
    "it is usually possible to animate interesting expressions with a single parameter."
    should be
    "it is usually NOT possible to animate interesting expressions with a single parameter."
  3. p.350, middle:
    "The sphincter muscle contractes radially toward an imaginary center."
    It doesn't really 'contract radially' of course. It contracts and thereby shortens the loop around an orifice. This shortening might be considered equivalent to a radial contraction.
  4. p.351, Figure 6.34, (c): the bold line indicates the angular limit of the muscle effect.
  5. p.362, Eq.6.2: the negative sign after 'c' should be a '+'.
  6. p.364, bottom: "replace "squares" by "average of the squares"
Appendix A
Appendix B
  1. p.451, Eq.B.54: the left had side is clipped off; 'ot' should be 'Rot'
  2. p.469, Eq. B.85: row vector [u3 u2 u 1] is missing from the right hand side of the equation.
  3. p.477, Eq. B.93-B.94: upper case omega is used in the text but lower case omega is used in these equations.
  4. p.478, Eq. B.96: the second line should be: -w2p(t)
  5. p.483, Eq.B.116 and associated text:
    "momentum is given by Equation B.116"
    should be
    "change in momentum is given by Equation B.116"
  6. p.492, Figure B.48 (b):
    "Step to midpoint (using derivative previously compute d) and compute derivative"
    should be
    "Step to midpoint (using derivative previously computed) and compute derivative"
  7. p.494, 65mm: IMAX is 70mm film and is shot at 24fps. See the IMAX web site at, specifically:¶m_subMenuSelect=imaxWorksSelect¶m_subLeftSelect=imaxWorksImaxSelect
    However, I've seen some (apparently informed) discussion online that says some IMAX plays back at up to 48fps.
  8. p.500, 6th line: "undersampling" should be "undersampled".
Color Plates
  1. Plates 4 & 5: titles of the plates are reversed.
  2. Plates 9 and 10: reference [70] should be [62].

Rick Parent (; name: parent)