Computer Animation : Algorithms and Techniques

Driven by demand from the entertainment industry for better and more realistic animation, technology continues to evolve and improve. The algorithms and techniques behind this technology are the foundation of this comprehensive book, which is written to teach you the fundamentals of animation programming. In this third edition, the most current techniques are covered along with the theory and high-level computation that have earned the book a reputation as the best technically-oriented animation resource. Key topics such as fluids, hair, and crowd animation have been expanded, and extensive new coverage of clothes and cloth has been added. New material on simulation provides a more diverse look at this important area and more example animations and chapter projects and exercises are included. Additionally, spline coverage has been expanded and new video compression and formats (e.g., iTunes) are covered. * Includes companion site with contemporary animation examples drawn from research and entertainment, sample animations, and example code * Describes the key mathematical and algorithmic foundations of animation that provide you with a deep understanding and control of technique * Expanded and new coverage of key topics including: fluids and clouds, cloth and clothes, hair, and crowd animation * Explains the algorithms used for path following, hierarchical kinematic modelling, rigid body dynamics, flocking behaviour, particle systems, collision detection, and more Front Cover Computer Animation: Algorithms and Techniques Copyright Dedication Contents Preface Overview Organization of the Book Acknowledgments References About the Author Chapter 1: Introduction 1.1. Motion perception 1.2. The heritage of animation 1.2.1. Early devices 1.2.2. The early days of ``conventional ́ ́ animation 1.2.3. Disney 1.2.4. Contributions of others 1.2.5. Other media for animation 1.3. Animation production 1.3.1. Principles of animation Simulating physics Designing aesthetically pleasing actions Effectively presenting action Production technique 1.3.2. Principles of filmmaking Three-point lighting 180 rule Rule of thirds Types of shots Tilt Framing Focus the viewer's attention 1.3.3. Sound 1.4. Computer animation production 1.4.1. Computer animation production tasks 1.4.2. Digital editing In the old days Digital on-line nonlinear editing 1.4.3. Digital video 1.4.4. Digital audio Digital musical device control Digital audio sampling 1.5. A brief history of computer animation 1.5.1. Early activity (pre-1980) 1.5.2. The middle years (the 1980s) 1.5.3. Animation comes of age (the mid-1980s and beyond) 1.6. Summary References Chapter 2: Technical Background 2.1. Spaces and transformations 2.1.1. The display pipeline 2.1.2. Homogeneous coordinates and the transformation matrix 2.1.3. Concatenating transformations: multiplying transformation matrices 2.1.4. Basic transformations 2.1.5. Representing an arbitrary orientation Fixed-angle representation 2.1.6. Extracting transformations from a matrix 2.1.7. Description of transformations in the display pipeline Object space to world space transformation World space to eye space transformation Perspective matrix multiply Perspective divide Image to screen space mapping 2.1.8. Error considerations Accumulated round-off error Orthonormalization Considerations of scale 2.2. Orientation representation 2.2.1. Fixed-angle representation 2.2.2. Euler angle representation 2.2.3. Angle and axis representation 2.2.4. Quaternion representation Basic quaternion math Representing rotations using quaternions Rotating vectors using quaternions 2.2.5. Exponential map representation 2.3. Summary References Chapter 3: Interpolating Values 3.1. Interpolation 3.1.1. The appropriate function Interpolation versus approximation Complexity Continuity Global versus local control 3.1.2. Summary 3.2. Controlling the motion of a point along a curve 3.2.1. Computing arc length The analytic approach to computing arc length Estimating arc length by forward differencing Adaptive approach Estimating the arc length integral numerically Adaptive Gaussian integration Find a point that is a given distance along a curve 3.2.2. Speed control 3.2.3. Ease-in/ease-out Sine interpolation Using sinusoidal pieces for acceleration and deceleration Single cubic polynomial ease-in/ease-out Constant acceleration: parabolic ease-in/ease-out 3.2.4. General distance-time functions 3.2.5. Curve fitting to position-time pairs 3.3. Interpolation of orientations 3.3.1. Interpolating quaternions 3.4. Working with paths 3.4.1. Path following 3.4.2. Orientation along a path Use of the Frenet frame Camera path following 3.4.3. Smoothing a path Smoothing with linear interpolation of adjacent values Smoothing with cubic interpolation of adjacent values Smoothing with convolution kernels Smoothing by B-spline approximation 3.4.4. Determining a path along a surface 3.4.5. Path finding 3.5. Chapter summary References Chapter 4: Interpolation-Based Animation 4.1. Key-frame systems 4.2. Animation languages 4.2.1. Artist-oriented animation languages 4.2.2. Full-featured programming languages for animation 4.2.3. Articulation variables 4.2.4. Graphical languages 4.2.5. Actor-based animation languages 4.3. Deforming objects 4.3.1. Picking and pulling 4.3.2. Deforming an embedding space Two-dimensional grid deformation Polyline deformation Global deformation FFD Composite FFDs-sequential and hierarchical Animated FFDs Deformation tools Moving the tool Moving the object Animating the FFD control points 4.4. Three-dimensional shape interpolation 4.4.1. Matching topology 4.4.2. Star-shaped polyhedra 4.4.3. Axial slices 4.4.4. Map to sphere 4.4.5. Recursive subdivision 4.5. Morphing (two-dimensional) 4.5.1. Coordinate grid approach 4.5.2. Feature-based morphing 4.6. Chapter summary References Chapter 5: Kinematic Linkages 5.1. Hierarchical modeling 5.1.1. Data structure for hierarchical modeling A simple example 5.1.2. Local coordinate frames 5.2. Forward kinematics 5.3. Inverse kinematics 5.3.1. Solving a simple system by analysis 5.3.2. The Jacobian A simple example 5.3.3. Numeric solutions to IK Solution using the inverse Jacobian Adding more control Alternative Jacobian Avoiding the inverse: using the transpose of the Jacobian Procedurally determining the angles: cyclic coordinate descent 5.3.4. Summary 5.4. Chapter summary References Chapter 6: Motion Capture 6.1. Motion capture technologies 6.2. Processing the images 6.3. Camera calibration 6.4. Three-dimensional position reconstruction 6.4.1. Multiple markers 6.4.2. Multiple cameras 6.5. Fitting to the skeleton 6.6. Output from motion capture systems 6.7. Manipulating motion capture data 6.7.1. Processing the signals 6.7.2. Retargeting the motion 6.7.3. Combining motions 6.8. Chapter summary References Chapter 7: Physically Based Animation 7.1. Basic physics-a review 7.1.1. Spring-damper pair 7.2. Spring animation examples 7.2.1. Flexible objects Mass-spring-damper modeling of flexible objects A simple example 7.2.2. Virtual springs 7.3. Particle systems 7.3.1. Particle generation 7.3.2. Particle attributes 7.3.3. Particle termination 7.3.4. Particle animation 7.3.5. Particle rendering 7.3.6. Particle system representation Updating particle system status 7.3.7. Forces on particles 7.3.8. Particle life span 7.4. Rigid body simulation 7.4.1. Bodies in free fall A simple example A note about numeric approximation Equations of motion for a rigid body Orientation and rotational movement Center of mass Forces Momentum Inertia tensor The equations 7.4.2. Bodies in collision Colliding bodies Particle-plane collision and kinematic response The penalty method Testing polyhedra Impulse force of collision Computing impulse forces Friction Resting contact 7.4.3. Dynamics of linked hierarchies Constrained dynamics The Featherstone equations 7.5. Cloth 7.5.1. Direct modeling of folds 7.5.2. Physically based modeling 7.6. Enforcing soft and hard constraints 7.6.1. Energy minimization Three useful functions Useful constraints Point-to-fixed-point Point-to-point Point-to-point locally abutting Floating attachment Floating attachment locally abutting Energy constraints are not hard constraints 7.6.2. Space-time constraints Space-time particle Numerical solution 7.7. Chapter summary References Chapter 8: Fluids 8.1. Specific fluid models 8.1.1. Models of water Still waters and small-amplitude waves The anatomy of waves Modeling ocean waves Finding its way downhill Summary 8.1.2. Modeling and animating clouds Anatomy of clouds and cloud formation Cloud models in CG 8.1.3. Modeling and animating fire Procedurally generated image Particle system approach Other approaches 8.1.4. Summary 8.2. Computational fluid dynamics 8.2.1. General approaches to modeling fluids Grid-based method Particle-based method Hybrid method 8.2.2. CFD equations Conservation of mass Conservation of momentum 8.2.3. Grid-based approach Stable fluids Density update The velocity update The simulation 8.2.4. Particle-based approaches including smoothed particle hydrodynamics 8.3. Chapter summary References Chapter 9: Modeling and Animating Human Figures 9.1. Overview of virtual human representation 9.1.1. Representing body geometry Polygonal representations Patch representations Other representations 9.1.2. Geometry data acquisition 9.1.3. Geometry deformation 9.1.4. Surface detail 9.1.5. Layered approach to human figure modeling Rigging 9.2. Reaching and grasping 9.2.1. Modeling the arm 9.2.2. The shoulder joint 9.2.3. The hand 9.2.4. Coordinated movement 9.2.5. Reaching around obstacles 9.2.6. Strength 9.3. Walking 9.3.1. The mechanics of locomotion Walk cycle Run cycle Pelvic transport Pelvic rotation Pelvic list Knee flexion Ankle and toe joints 9.3.2. The kinematics of the walk 9.3.3. Using dynamics to help produce realistic motion 9.3.4. Forward dynamic control 9.3.5. Summary 9.4. Coverings 9.4.1. Clothing 9.4.4. Hair 9.5. Chapter summary References Chapter 10: Facial Animation 10.1. The human face 10.1.1. Anatomic structure 10.1.2. The facial action coding system 10.2. Facial models 10.2.1. Creating a continuous surface model 10.2.2. Textures 10.3. Animating the face 10.3.1. Parameterized models 10.3.2. Blend shapes 10.3.3. Muscle models 10.3.4. Expressions 10.3.5. Summary 10.4. Lip-sync animation 10.4.1. Articulators of speech 10.4.2. Phonemes 10.4.3. Coarticulation 10.4.4. Prosody 10.5. Chapter summary References Chapter 11: Behavioral Animation Cognitive modeling Aggregate behavior 11.1. Primitive behaviors 11.1.1. Flocking behavior Local control Perception Interacting with other members Interacting with the environment Global control Flock leader Negotiating the motion Collision avoidance Splitting and rejoining Modeling flight 11.1.2. Prey-predator behavior 11.2. Knowledge of the environment 11.2.1. Vision 11.2.2. Memory 11.3. Modeling intelligent behavior 11.3.1. Autonomous behavior Internal state Levels of behavior Keeping behavior under control Arbitration between competing intentions 11.3.2. Expressions and gestures 11.4.3. Modeling individuality: personality and emotions 11.4. Crowds 11.4.1. Crowd behaviors 11.4.2. Internal structure 11.4.3. Crowd control 11.4.4. Managing n-squared complexity 11.4.5. Appearance 11.6. Chapter summary References Chapter 12: Special Models for Animation 12.1. Implicit surfaces 12.1.1. Basic implicit surface formulation 12.1.2. Animation using implicitly defined objects 12.1.3. Collision detection 12.1.4. Deforming the implicit surface as a result of collision 12.1.5. Level set methods 12.1.6. Summary 12.2. Plants 12.2.1. A little bit of botany 12.2.2. L-systems D0L-systems Geometric interpretation of L-systems Bracketed L-systems Stochastic L-systems Context free versus context sensitive 12.2.3. Animating plant growth Parametric L-systems Timed L-systems Interacting with the environment 12.2.4. Summary 12.3. Subdivision surfaces 12.4. Chapter summary References Appendix A: Rendering Issues A.1. Double buffering A.2. Compositing A.2.1. Compositing without pixel depth information A.2.2. Compositing with pixel depth information A.3. Displaying moving objects: motion blur A.4. Drop shadows A.5. Billboarding and impostors A.6. Summary References Appendix B: Background Informationand Techniques B B.1. Vectors and matrices B.1.1. Inverse matrix and solving linear systems B.1.2. Singular value decomposition B.2. Geometric computations B.2.1. Components of a vector B.2.2. Length of a vector B.2.3. Dot product of two vectors B.2.4. Cross-product of two vectors B.2.5. Vector and matrix routines Vector routines B.2.6. Closest point between two lines in three-space B.2.7. Area calculations Area of a triangle Area of a polygon B.2.8. The cosine rule B.2.9. Barycentric coordinates B.2.10. Computing bounding shapes Bounding boxes Bounding slabs Bounding spheres Convex hull B.3. Transformations B.3.1. Transforming a point using vector-matrix multiplication B.3.2. Transforming a vector using vector-matrix multiplication B.3.3. Axis-angle rotations B.3.4. Quaternions Quaternion arithmetic Rotations by quaternions Conversions B.4. Denevit and Hartenberg representation for linked appendages B.4.1. Denavit-Hartenberg notation B.4.2. A simple example B.4.3. Including a ball-and-socket joint B.4.4. Constructing the frame description B.5. Interpolating and approximating curves B.5.1. Equations: some basic terms B.5.2. Simple linear interpolation: geometric and algebraic forms B.5.3. Parameterization by arc length B.5.4. Computing derivatives B.5.5. Hermite interpolation B.5.6. Catmull-Rom spline B.5.7. Four-point form B.5.8. Blended parabolas B.5.9. Bezier interpolation/approximation B.5.10. De Casteljau construction of Bezier curves B.5.11. Tension, continuity, and bias control B.5.12. B-splines B.5.13. Fitting curves to a given set of points B.6. Randomness B.6.1. Noise B.6.2. Turbulence B.6.3. Random number generator B.7. Physics primer B.7.1. Position, velocity, and acceleration B.7.2. Circular motion B.7.3. Newton's laws of motion B.7.4. Inertia and inertial reference frames B.7.5. Center of mass B.7.6. Torque B.7.7. Equilibrium: balancing forces B.7.8. Gravity B.7.9. Centripetal force B.7.10. Contact forces Friction Viscosity B.7.11. Centrifugal force B.7.12. Work and potential energy B.7.13. Kinetic energy B.7.14. Conservation of energy B.7.15. Conservation of momentum B.7.16. Oscillatory motion B.7.17. Damping B.7.18. Angular momentum B.7.19. Inertia tensors B.8. Numerical integration techniques B.8.1. Function integration for arc length computation B.8.2. Updating function values The (explicit) Euler method Runge-Kutta The implicit Euler method The semi-implicit Euler method B.8.3. Updating position The Heun method The Verlet method The Leapfrog method B.9. Optimization B.9.1. Analytic Solution B.9.2. Numerical methods Hard and soft constraints, equality constraints, and inequality constraints B.10. Standards for moving pictures B.10.1. In the beginning, there was analog Broadcast video standard Black-and-white signal Incorporating color into the black-and-white signal Videotape formats B.10.2. In the digital world Compression/decompression Digital video formats Digital television formats High-definition television and wide-screen format B.11. Camera calibration References Index Color Plates