# Computer Animation

## 2nd Edition

### Algorithms and Techniques

**Authors:**Rick Parent Rick Parent

**Hardcover ISBN:**9780125320009

**eBook ISBN:**9780080553856

**Imprint:**Morgan Kaufmann

**Published Date:**27th September 2007

**Page Count:**624

**View all volumes in this series:**Computer Animation

## Table of Contents

- Introduction

1.1 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.2.6 Principles of Animation 1.2.7 Principles of Filmmaking 1.3 Animation Production 1.3.1 Sound 1.4 Computer Animation Production 1.4.1 Computer Animation Production Tasks 1.4.2 Digital Editing 1.4.3 Digital Video 1.4.4 Digital Audio 1.5 A Brief History of Computer Animation 1.5.1 Early Activity (pre 1980) 1.5.2 The Middle Years (The ‘80s) 1.5.3 Animation Comes of Age (The mid-80’s and beyond) 1.6 Chapter Summary References

- 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 Compound Transformation: Concatenating Transformation Matrices 2.1.4 Basic Transformations 2.1.5 Representing an Arbitrary Orientation 2.1.6 Extracting Transformations from a Matrix 2.1.7 Description of Transformations in the Display Pipeline 2.1.8 Error Considerations 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 2.2.5 Exponential Map Representation 2.3 Chapter Summary References

- Interpolation

3.1 Interpolating Values 3.1.1 The Appropriate Function 3.1.2 Summary 3.2 Controlling the Motion of a Point Along a Curve 3.2.1 Computing Arc Length 3.2.2 Speed Control 3.2.3 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 3.4.3 Smoothing a Path 3.4.4 Determining a Path along a Surface 3.4.5 Path Finding 3.4.6 Summary 3.5 Chapter Summary References

- 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 4.4 3D 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.4.6 Summary 4.5 Morphing (2D) 4.5.1 Coordinate Grid Approach 4.5.2 Feature-Based Morphing 4.6 Chapter Summary References

- Kinematic Linkages

5.1 Hierarchical Modeling 5.1.1 Data structure for hierarchical modeling 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 5.3.3 Numeric Solutions to Inverse Kinematics 5.3.4 Summary 5.4 Chapter Summary References

- Motion Capture

6.1 Motion Capture Technologies 6.2 Processing the Images 6.3 Camera Calibration 6.4 3D 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

- Physically Based Animation

7.1 Basic Physics - A Review 7.1.1 Simulating a spring-mass-damper system 7.2 Spring Meshes 7.2.1 Flexible Objects 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 7.3.7 Forces on Particles 7.3.8 Particle Life Span 7.4 Rigid Body Simulation 7.4.1 Bodies in Free Fall 7.4.2 Bodies in Collision 7.4.3 Dynamics of Linked Hierarchies 7.4.4 Summary 7.5 Enforcing Soft and Hard Constraints 7.5.1 Energy Minimization 7.5.2 Space-Time Constraints 7.6 Chapter Summary References

- Fluids: Liquids & Gases

8.1 Specific Fluid Models 8.1.1 Models of Water 8.1.2 Models of Clouds 8.1.3 Models of Fire 8.1.4 Summary 8.2 Computational Fluid Dynamics 8.2.1 General Approaches to Modeling Fluids 8.2.2 CFD Equations 8.3 Chapter Summary References

- Modeling and Animating Human Figures

9.1 Overview of Virtual Human Representation 9.1.1 Representing Body Geometry 9.1.2 Geometry Data Acquisition 9.1.3 Geometry Deformation 9.1.4Surface Detail 9.1.5 Layered Approach to Human Figure Modeling 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 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 Getting Dressed Up 9.4.1 Cloth and Clothing 9.4.2 Simple Draping 9.4.3 Getting into Clothes 9.4.4 Hair 9.5 Chapter Summary References

- 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

- Modeling Behavior

11.1 Knowing the Environment 11.1.1 Vision 11.1.2 Memory 11.2 Aggregate Behavior 11.3 Primitive Behaviors 11.3.1 Flocking Behavior 11.3.2 Prey-Predator Behavior 11.4 Modeling Intelligent Behavior 11.4.1 Autonomous Behavior 11.4.2 Expressions and Gestures 11.4.3 Modeling Individuality: Personality and Emotions 11.5 Crowd Management 11.5.1 Emergent Behavior 11.5.2 Statistically Modeled Behavior 11.5.3 Internal structure 11.6 Chapter Summary References

- 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 12.2.3 Animating Plant Growth 12.2.4 Summary 12.3 Subdivision Surfaces 12.4 Chapter Summary References

App 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

App B. Background Information and Techniques

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 B.2.6Closest Point between Two Lines in Three-Space B.2.7 Area Calculations B.2.8 The Cosine Rule B.2.9 Barycentric Coordinates B.2.10 Computing Bounding Shapes 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 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 B.7.11 Centrifugal Force B.7.12 Work and Potential Energy B.7.13 Kinetic Energy B.7.14Conservation 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 B.8.3 Updating Position B.9 Standards for Moving Pictures B.9.1 In the Beginning, There Was Analog B.9.2 In the Digital World B.10 Camera Calibration References

## Description

- Introduction

1.1 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.2.6 Principles of Animation 1.2.7 Principles of Filmmaking 1.3 Animation Production 1.3.1 Sound 1.4 Computer Animation Production 1.4.1 Computer Animation Production Tasks 1.4.2 Digital Editing 1.4.3 Digital Video 1.4.4 Digital Audio 1.5 A Brief History of Computer Animation 1.5.1 Early Activity (pre 1980) 1.5.2 The Middle Years (The ‘80s) 1.5.3 Animation Comes of Age (The mid-80’s and beyond) 1.6 Chapter Summary References

- 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 Compound Transformation: Concatenating Transformation Matrices 2.1.4 Basic Transformations 2.1.5 Representing an Arbitrary Orientation 2.1.6 Extracting Transformations from a Matrix 2.1.7 Description of Transformations in the Display Pipeline 2.1.8 Error Considerations 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 2.2.5 Exponential Map Representation 2.3 Chapter Summary References

- Interpolation

3.1 Interpolating Values 3.1.1 The Appropriate Function 3.1.2 Summary 3.2 Controlling the Motion of a Point Along a Curve 3.2.1 Computing Arc Length 3.2.2 Speed Control 3.2.3 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 3.4.3 Smoothing a Path 3.4.4 Determining a Path along a Surface 3.4.5 Path Finding 3.4.6 Summary 3.5 Chapter Summary References

- 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 4.4 3D 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.4.6 Summary 4.5 Morphing (2D) 4.5.1 Coordinate Grid Approach 4.5.2 Feature-Based Morphing 4.6 Chapter Summary References

- Kinematic Linkages

5.1 Hierarchical Modeling 5.1.1 Data structure for hierarchical modeling 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 5.3.3 Numeric Solutions to Inverse Kinematics 5.3.4 Summary 5.4 Chapter Summary References

- Motion Capture

6.1 Motion Capture Technologies 6.2 Processing the Images 6.3 Camera Calibration 6.4 3D 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

- Physically Based Animation

7.1 Basic Physics - A Review 7.1.1 Simulating a spring-mass-damper system 7.2 Spring Meshes 7.2.1 Flexible Objects 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 7.3.7 Forces on Particles 7.3.8 Particle Life Span 7.4 Rigid Body Simulation 7.4.1 Bodies in Free Fall 7.4.2 Bodies in Collision 7.4.3 Dynamics of Linked Hierarchies 7.4.4 Summary 7.5 Enforcing Soft and Hard Constraints 7.5.1 Energy Minimization 7.5.2 Space-Time Constraints 7.6 Chapter Summary References

- Fluids: Liquids & Gases

8.1 Specific Fluid Models 8.1.1 Models of Water 8.1.2 Models of Clouds 8.1.3 Models of Fire 8.1.4 Summary 8.2 Computational Fluid Dynamics 8.2.1 General Approaches to Modeling Fluids 8.2.2 CFD Equations 8.3 Chapter Summary References

- Modeling and Animating Human Figures

9.1 Overview of Virtual Human Representation 9.1.1 Representing Body Geometry 9.1.2 Geometry Data Acquisition 9.1.3 Geometry Deformation 9.1.4Surface Detail 9.1.5 Layered Approach to Human Figure Modeling 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 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 Getting Dressed Up 9.4.1 Cloth and Clothing 9.4.2 Simple Draping 9.4.3 Getting into Clothes 9.4.4 Hair 9.5 Chapter Summary References

- 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

- Modeling Behavior

11.1 Knowing the Environment 11.1.1 Vision 11.1.2 Memory 11.2 Aggregate Behavior 11.3 Primitive Behaviors 11.3.1 Flocking Behavior 11.3.2 Prey-Predator Behavior 11.4 Modeling Intelligent Behavior 11.4.1 Autonomous Behavior 11.4.2 Expressions and Gestures 11.4.3 Modeling Individuality: Personality and Emotions 11.5 Crowd Management 11.5.1 Emergent Behavior 11.5.2 Statistically Modeled Behavior 11.5.3 Internal structure 11.6 Chapter Summary References

- 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 12.2.3 Animating Plant Growth 12.2.4 Summary 12.3 Subdivision Surfaces 12.4 Chapter Summary References

App 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

App B. Background Information and Techniques

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 B.2.6Closest Point between Two Lines in Three-Space B.2.7 Area Calculations B.2.8 The Cosine Rule B.2.9 Barycentric Coordinates B.2.10 Computing Bounding Shapes 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 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 B.7.11 Centrifugal Force B.7.12 Work and Potential Energy B.7.13 Kinetic Energy B.7.14Conservation 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 B.8.3 Updating Position B.9 Standards for Moving Pictures B.9.1 In the Beginning, There Was Analog B.9.2 In the Digital World B.10 Camera Calibration References

## Key Features

- New up-to-the-moment coverage of hot topics like real-time 3D graphics, collision detection, fluid and soft-body animation and more!
- Companion site with animation clips drawn from research & entertainment and code samples
- Describes the mathematical and algorithmic foundations of animation that provide the animator with a deep understanding and control of technique

## Readership

Students studying computer animation in courses with an emphasis on understanding algorithms and programming. Technical directors, animators, artists, and game developers looking to understand the foundations of animation to improve studio work.

## Details

- No. of pages:
- 624

- Language:
- English

- Copyright:
- © Morgan Kaufmann 2008

- Published:
- 27th September 2007

- Imprint:
- Morgan Kaufmann

- eBook ISBN:
- 9780080553856

## Reviews

"An invaluable resource for anyone interested in computer animation programming or for anyone who simply wants to get under the hood of their favorite animation application." —Mike Caputo, President, Animation Bureau

## About the Authors

### Rick Parent Author

Rick Parent is an Associate Professor at Ohio State University, where he teaches computer graphics and computer animation. His research in computer animation focuses on its relation to modeling and animating the human figure, with special emphasis on geometric modeling and implicit surfaces. Rick earned a Ph.D. in computer science from Ohio State University and a Bachelor's degree in computer science from the University of Dayton. In 1977, he was awarded "Outstanding Ph.D. Thesis Award" (one of four given nationally) by the NCC. He has served on numerous SIGGRAPH committees, in addition to the Computer Graphics International 2000 Program Committee and the Computer Animation '99 Program Committee and is on the editorial board of the Visual Computer Journal.

### Affiliations and Expertise

is a Professor of Computer Science and Engineering at Ohio State University, where he teaches computer graphics and computer animation. He has taught Computer Animation for over 25 years and has worked in the field for over 35. His research interests include the modeling and animating of the human figure.

### Rick Parent Author

Rick Parent is an Associate Professor at Ohio State University, where he teaches computer graphics and computer animation. His research in computer animation focuses on its relation to modeling and animating the human figure, with special emphasis on geometric modeling and implicit surfaces. Rick earned a Ph.D. in computer science from Ohio State University and a Bachelor's degree in computer science from the University of Dayton. In 1977, he was awarded "Outstanding Ph.D. Thesis Award" (one of four given nationally) by the NCC. He has served on numerous SIGGRAPH committees, in addition to the Computer Graphics International 2000 Program Committee and the Computer Animation '99 Program Committee and is on the editorial board of the Visual Computer Journal.

### Affiliations and Expertise

is a Professor of Computer Science and Engineering at Ohio State University, where he teaches computer graphics and computer animation. He has taught Computer Animation for over 25 years and has worked in the field for over 35. His research interests include the modeling and animating of the human figure.