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 Computer Animation: Algorithms and Techniques (2009) 978-0-12-415842-9 Front Cover 1 Computer Animation: Algorithms and Techniques 4 Copyright 5 Dedication 6 Contents 8 Preface 14 Overview 14 Organization of the Book 15 Acknowledgments 16 References 17 About the Author 18 Chapter 1: Introduction 20 1.1. Motion perception 21 1.2. The heritage of animation 23 1.2.1. Early devices 23 1.2.2. The early days of ``conventional ́ ́ animation 25 1.2.3. Disney 26 1.2.4. Contributions of others 27 1.2.5. Other media for animation 27 1.3. Animation production 28 1.3.1. Principles of animation 29 Simulating physics 29 Designing aesthetically pleasing actions 31 Effectively presenting action 31 Production technique 31 1.3.2. Principles of filmmaking 31 Three-point lighting 31 180 rule 32 Rule of thirds 32 Types of shots 32 Tilt 32 Framing 33 Focus the viewer's attention 33 1.3.3. Sound 33 1.4. Computer animation production 34 1.4.1. Computer animation production tasks 35 1.4.2. Digital editing 37 In the old days 37 Digital on-line nonlinear editing 38 1.4.3. Digital video 39 1.4.4. Digital audio 40 Digital musical device control 40 Digital audio sampling 41 1.5. A brief history of computer animation 41 1.5.1. Early activity (pre-1980) 41 1.5.2. The middle years (the 1980s) 44 1.5.3. Animation comes of age (the mid-1980s and beyond) 45 1.6. Summary 48 References 49 Chapter 2: Technical Background 52 2.1. Spaces and transformations 52 2.1.1. The display pipeline 53 2.1.2. Homogeneous coordinates and the transformation matrix 57 2.1.3. Concatenating transformations: multiplying transformation matrices 59 2.1.4. Basic transformations 59 2.1.5. Representing an arbitrary orientation 61 Fixed-angle representation 61 2.1.6. Extracting transformations from a matrix 65 2.1.7. Description of transformations in the display pipeline 66 Object space to world space transformation 66 World space to eye space transformation 66 Perspective matrix multiply 66 Perspective divide 67 Image to screen space mapping 67 2.1.8. Error considerations 67 Accumulated round-off error 67 Orthonormalization 69 Considerations of scale 70 2.2. Orientation representation 71 2.2.1. Fixed-angle representation 73 2.2.2. Euler angle representation 75 2.2.3. Angle and axis representation 76 2.2.4. Quaternion representation 77 Basic quaternion math 77 Representing rotations using quaternions 78 Rotating vectors using quaternions 78 2.2.5. Exponential map representation 79 2.3. Summary 79 References 79 Chapter 3: Interpolating Values 80 3.1. Interpolation 80 3.1.1. The appropriate function 81 Interpolation versus approximation 81 Complexity 82 Continuity 82 Global versus local control 83 3.1.2. Summary 84 3.2. Controlling the motion of a point along a curve 84 3.2.1. Computing arc length 85 The analytic approach to computing arc length 88 Estimating arc length by forward differencing 88 Adaptive approach 91 Estimating the arc length integral numerically 92 Adaptive Gaussian integration 93 Find a point that is a given distance along a curve 97 3.2.2. Speed control 97 3.2.3. Ease-in/ease-out 99 Sine interpolation 100 Using sinusoidal pieces for acceleration and deceleration 100 Single cubic polynomial ease-in/ease-out 102 Constant acceleration: parabolic ease-in/ease-out 103 3.2.4. General distance-time functions 105 3.2.5. Curve fitting to position-time pairs 109 3.3. Interpolation of orientations 110 3.3.1. Interpolating quaternions 110 3.4. Working with paths 115 3.4.1. Path following 115 3.4.2. Orientation along a path 115 Use of the Frenet frame 116 Camera path following 118 3.4.3. Smoothing a path 119 Smoothing with linear interpolation of adjacent values 120 Smoothing with cubic interpolation of adjacent values 120 Smoothing with convolution kernels 123 Smoothing by B-spline approximation 125 3.4.4. Determining a path along a surface 125 3.4.5. Path finding 127 3.5. Chapter summary 127 References 128 Chapter 4: Interpolation-Based Animation 130 4.1. Key-frame systems 130 4.2. Animation languages 134 4.2.1. Artist-oriented animation languages 135 4.2.2. Full-featured programming languages for animation 135 4.2.3. Articulation variables 136 4.2.4. Graphical languages 136 4.2.5. Actor-based animation languages 137 4.3. Deforming objects 138 4.3.1. Picking and pulling 138 4.3.2. Deforming an embedding space 140 Two-dimensional grid deformation 140 Polyline deformation 142 Global deformation 143 FFD 144 Composite FFDs-sequential and hierarchical 149 Animated FFDs 149 Deformation tools 151 Moving the tool 151 Moving the object 151 Animating the FFD control points 151 4.4. Three-dimensional shape interpolation 154 4.4.1. Matching topology 155 4.4.2. Star-shaped polyhedra 156 4.4.3. Axial slices 156 4.4.4. Map to sphere 158 4.4.5. Recursive subdivision 164 4.5. Morphing (two-dimensional) 166 4.5.1. Coordinate grid approach 166 4.5.2. Feature-based morphing 172 4.6. Chapter summary 178 References 178 Chapter 5: Kinematic Linkages 180 5.1. Hierarchical modeling 181 5.1.1. Data structure for hierarchical modeling 183 A simple example 184 5.1.2. Local coordinate frames 189 5.2. Forward kinematics 190 5.3. Inverse kinematics 191 5.3.1. Solving a simple system by analysis 192 5.3.2. The Jacobian 193 A simple example 196 5.3.3. Numeric solutions to IK 197 Solution using the inverse Jacobian 197 Adding more control 200 Alternative Jacobian 201 Avoiding the inverse: using the transpose of the Jacobian 202 Procedurally determining the angles: cyclic coordinate descent 203 5.3.4. Summary 204 5.4. Chapter summary 204 References 204 Chapter 6: Motion Capture 206 6.1. Motion capture technologies 206 6.2. Processing the images 207 6.3. Camera calibration 209 6.4. Three-dimensional position reconstruction 210 6.4.1. Multiple markers 211 6.4.2. Multiple cameras 211 6.5. Fitting to the skeleton 212 6.6. Output from motion capture systems 214 6.7. Manipulating motion capture data 215 6.7.1. Processing the signals 215 6.7.2. Retargeting the motion 216 6.7.3. Combining motions 216 6.8. Chapter summary 217 References 217 Chapter 7: Physically Based Animation 218 7.1. Basic physics-a review 219 7.1.1. Spring-damper pair 221 7.2. Spring animation examples 221 7.2.1. Flexible objects 221 Mass-spring-damper modeling of flexible objects 221 A simple example 222 7.2.2. Virtual springs 224 7.3. Particle systems 224 7.3.1. Particle generation 225 7.3.2. Particle attributes 226 7.3.3. Particle termination 226 7.3.4. Particle animation 226 7.3.5. Particle rendering 226 7.3.6. Particle system representation 227 Updating particle system status 227 7.3.7. Forces on particles 227 7.3.8. Particle life span 228 7.4. Rigid body simulation 228 7.4.1. Bodies in free fall 229 A simple example 229 A note about numeric approximation 231 Equations of motion for a rigid body 233 Orientation and rotational movement 233 Center of mass 235 Forces 235 Momentum 236 Inertia tensor 237 The equations 238 7.4.2. Bodies in collision 238 Colliding bodies 239 Particle-plane collision and kinematic response 239 The penalty method 241 Testing polyhedra 242 Impulse force of collision 244 Computing impulse forces 245 Friction 248 Resting contact 249 7.4.3. Dynamics of linked hierarchies 251 Constrained dynamics 251 The Featherstone equations 252 7.5. Cloth 254 7.5.1. Direct modeling of folds 256 7.5.2. Physically based modeling 259 7.6. Enforcing soft and hard constraints 263 7.6.1. Energy minimization 263 Three useful functions 264 Useful constraints 265 Point-to-fixed-point 265 Point-to-point 265 Point-to-point locally abutting 265 Floating attachment 265 Floating attachment locally abutting 266 Energy constraints are not hard constraints 266 7.6.2. Space-time constraints 266 Space-time particle 266 Numerical solution 267 7.7. Chapter summary 268 References 268 Chapter 8: Fluids 270 8.1. Specific fluid models 270 8.1.1. Models of water 270 Still waters and small-amplitude waves 271 The anatomy of waves 274 Modeling ocean waves 276 Finding its way downhill 278 Summary 281 8.1.2. Modeling and animating clouds 281 Anatomy of clouds and cloud formation 282 Cloud models in CG 284 8.1.3. Modeling and animating fire 287 Procedurally generated image 288 Particle system approach 288 Other approaches 289 8.1.4. Summary 289 8.2. Computational fluid dynamics 289 8.2.1. General approaches to modeling fluids 290 Grid-based method 290 Particle-based method 291 Hybrid method 291 8.2.2. CFD equations 291 Conservation of mass 292 Conservation of momentum 294 8.2.3. Grid-based approach 295 Stable fluids 295 Density update 295 The velocity update 296 The simulation 296 8.2.4. Particle-based approaches including smoothed particle hydrodynamics 296 8.3. Chapter summary 299 References 299 Chapter 9: Modeling and Animating Human Figures 302 9.1. Overview of virtual human representation 302 9.1.1. Representing body geometry 303 Polygonal representations 303 Patch representations 304 Other representations 304 9.1.2. Geometry data acquisition 304 9.1.3. Geometry deformation 305 9.1.4. Surface detail 305 9.1.5. Layered approach to human figure modeling 306 Rigging 308 9.2. Reaching and grasping 309 9.2.1. Modeling the arm 309 9.2.2. The shoulder joint 312 9.2.3. The hand 312 9.2.4. Coordinated movement 314 9.2.5. Reaching around obstacles 315 9.2.6. Strength 316 9.3. Walking 317 9.3.1. The mechanics of locomotion 317 Walk cycle 318 Run cycle 319 Pelvic transport 319 Pelvic rotation 319 Pelvic list 320 Knee flexion 321 Ankle and toe joints 321 9.3.2. The kinematics of the walk 322 9.3.3. Using dynamics to help produce realistic motion 322 9.3.4. Forward dynamic control 327 9.3.5. Summary 327 9.4. Coverings 328 9.4.1. Clothing 328 9.4.4. Hair 328 9.5. Chapter summary 330 References 331 Chapter 10: Facial Animation 336 10.1. The human face 336 10.1.1. Anatomic structure 336 10.1.2. The facial action coding system 338 10.2. Facial models 339 10.2.1. Creating a continuous surface model 341 10.2.2. Textures 344 10.3. Animating the face 346 10.3.1. Parameterized models 346 10.3.2. Blend shapes 346 10.3.3. Muscle models 348 10.3.4. Expressions 351 10.3.5. Summary 351 10.4. Lip-sync animation 352 10.4.1. Articulators of speech 352 10.4.2. Phonemes 353 10.4.3. Coarticulation 354 10.4.4. Prosody 354 10.5. Chapter summary 354 References 355 Chapter 11: Behavioral Animation 358 Cognitive modeling 359 Aggregate behavior 360 11.1. Primitive behaviors 361 11.1.1. Flocking behavior 361 Local control 362 Perception 362 Interacting with other members 363 Interacting with the environment 363 Global control 363 Flock leader 363 Negotiating the motion 363 Collision avoidance 364 Splitting and rejoining 368 Modeling flight 368 11.1.2. Prey-predator behavior 370 11.2. Knowledge of the environment 371 11.2.1. Vision 371 11.2.2. Memory 372 11.3. Modeling intelligent behavior 373 11.3.1. Autonomous behavior 373 Internal state 374 Levels of behavior 374 Keeping behavior under control 375 Arbitration between competing intentions 375 11.3.2. Expressions and gestures 375 11.4.3. Modeling individuality: personality and emotions 376 11.4. Crowds 377 11.4.1. Crowd behaviors 378 11.4.2. Internal structure 378 11.4.3. Crowd control 379 11.4.4. Managing n-squared complexity 379 11.4.5. Appearance 380 11.6. Chapter summary 380 References 380 Chapter 12: Special Models for Animation 384 12.1. Implicit surfaces 384 12.1.1. Basic implicit surface formulation 384 12.1.2. Animation using implicitly defined objects 386 12.1.3. Collision detection 387 12.1.4. Deforming the implicit surface as a result of collision 387 12.1.5. Level set methods 390 12.1.6. Summary 391 12.2. Plants 391 12.2.1. A little bit of botany 391 12.2.2. L-systems 393 D0L-systems 393 Geometric interpretation of L-systems 394 Bracketed L-systems 395 Stochastic L-systems 397 Context free versus context sensitive 398 12.2.3. Animating plant growth 398 Parametric L-systems 399 Timed L-systems 399 Interacting with the environment 400 12.2.4. Summary 400 12.3. Subdivision surfaces 401 12.4. Chapter summary 403 References 403 Appendix A: Rendering Issues 406 A.1. Double buffering 406 A.2. Compositing 407 A.2.1. Compositing without pixel depth information 408 A.2.2. Compositing with pixel depth information 414 A.3. Displaying moving objects: motion blur 416 A.4. Drop shadows 419 A.5. Billboarding and impostors 422 A.6. Summary 424 References 424 Appendix B: Background Informationand Techniques B 426 B.1. Vectors and matrices 426 B.1.1. Inverse matrix and solving linear systems 427 B.1.2. Singular value decomposition 431 B.2. Geometric computations 435 B.2.1. Components of a vector 435 B.2.2. Length of a vector 435 B.2.3. Dot product of two vectors 436 B.2.4. Cross-product of two vectors 437 B.2.5. Vector and matrix routines 439 Vector routines 439 B.2.6. Closest point between two lines in three-space 439 B.2.7. Area calculations 443 Area of a triangle 443 Area of a polygon 444 B.2.8. The cosine rule 445 B.2.9. Barycentric coordinates 445 B.2.10. Computing bounding shapes 446 Bounding boxes 446 Bounding slabs 446 Bounding spheres 448 Convex hull 448 B.3. Transformations 461 B.3.1. Transforming a point using vector-matrix multiplication 461 B.3.2. Transforming a vector using vector-matrix multiplication 461 B.3.3. Axis-angle rotations 462 B.3.4. Quaternions 463 Quaternion arithmetic 463 Rotations by quaternions 463 Conversions 464 B.4. Denevit and Hartenberg representation for linked appendages 465 B.4.1. Denavit-Hartenberg notation 465 B.4.2. A simple example 467 B.4.3. Including a ball-and-socket joint 468 B.4.4. Constructing the frame description 468 B.5. Interpolating and approximating curves 470 B.5.1. Equations: some basic terms 470 B.5.2. Simple linear interpolation: geometric and algebraic forms 472 B.5.3. Parameterization by arc length 473 B.5.4. Computing derivatives 473 B.5.5. Hermite interpolation 473 B.5.6. Catmull-Rom spline 474 B.5.7. Four-point form 478 B.5.8. Blended parabolas 478 B.5.9. Bezier interpolation/approximation 479 B.5.10. De Casteljau construction of Bezier curves 480 B.5.11. Tension, continuity, and bias control 480 B.5.12. B-splines 482 B.5.13. Fitting curves to a given set of points 484 B.6. Randomness 486 B.6.1. Noise 486 B.6.2. Turbulence 488 B.6.3. Random number generator 488 B.7. Physics primer 490 B.7.1. Position, velocity, and acceleration 490 B.7.2. Circular motion 490 B.7.3. Newton's laws of motion 491 B.7.4. Inertia and inertial reference frames 492 B.7.5. Center of mass 492 B.7.6. Torque 492 B.7.7. Equilibrium: balancing forces 493 B.7.8. Gravity 493 B.7.9. Centripetal force 494 B.7.10. Contact forces 494 Friction 495 Viscosity 495 B.7.11. Centrifugal force 496 B.7.12. Work and potential energy 496 B.7.13. Kinetic energy 496 B.7.14. Conservation of energy 497 B.7.15. Conservation of momentum 497 B.7.16. Oscillatory motion 497 B.7.17. Damping 498 B.7.18. Angular momentum 498 B.7.19. Inertia tensors 498 B.8. Numerical integration techniques 499 B.8.1. Function integration for arc length computation 500 B.8.2. Updating function values 501 The (explicit) Euler method 502 Runge-Kutta 502 The implicit Euler method 504 The semi-implicit Euler method 504 B.8.3. Updating position 504 The Heun method 504 The Verlet method 505 The Leapfrog method 505 B.9. Optimization 505 B.9.1. Analytic Solution 507 B.9.2. Numerical methods 507 Hard and soft constraints, equality constraints, and inequality constraints 508 B.10. Standards for moving pictures 509 B.10.1. In the beginning, there was analog 509 Broadcast video standard 510 Black-and-white signal 511 Incorporating color into the black-and-white signal 511 Videotape formats 512 B.10.2. In the digital world 513 Compression/decompression 513 Digital video formats 515 Digital television formats 515 High-definition television and wide-screen format 516 B.11. Camera calibration 516 References 520 Index 522 Color Plates 536