Table of Contents

• Preface
• 
  
• About the Author
• 
  
• About the CD-ROM
  
  • 1 Introduction
    
    • 1.1 What is Game Physics
    • 
      
    • 1.2 What is a Physics Engine
      
      • 1.2.1 Advantages of a Physics Engine
      • 
        
      • 1.2.2 Weaknessess of a Physics Engine
    • 
      
    • 1.3 Approaches to Physics Engines
      
      • 1.3.1 Types of Object
      • 
        
      • 1.3.2 Contact Resolution
      • 
        
      • 1.3.3 Impulses and Forces
      • 
        
      • 1.3.4 What We're Building
    • 
      
    • 1.4 The Mathematics of Physics Engines
      
      • 1.4.1 The Math You Need to Know
      • 
        
      • 1.4.2 The Math We'll Review
      • 
        
      • 1.4.3 The Mathematics We'll Introduce
    • 
      
    • 1.5 The Source Code in the Book
    • 
      
    • 1.6 How the Book is Structured
• 
  
• I Particle Physics
  
  • 2 The Mathematics of Particles
    
    • 2.1 Vectors
      
      • 2.1.1 The Handedness of Space
      • 
        
      • 2.1.2 Vectors and Directions
      • 
        
      • 2.1.3 Scalar and Vector Multiplication
      • 
        
      • 2.1.4 Vector Addition and Subtraction
      • 
        
      • 2.1.5 Multiplying Vectors
      • 
        
      • 2.1.6 The Component Product
      • 
        
      • 2.1.7 The Scalar Product
      • 
        
      • 2.1.8 The Vector Product
      • 
        
      • 2.1.9 The Orthonormal Basis
    • 
      
    • 2.2 Calculus
      
      • 2.2.1 Differential Calculus
      • 
        
      • 2.2.2 Integral Calculus
  
  
  • 3 The Laws of Motion
    
    • 3.1 A Particle
    • 
      
    • 3.2 The First Two Laws
      
      • 3.2.1 The Force Equations
      • 
        
      • 3.2.2 Adding Mass to Particles
      • 
        
      • 3.2.3 Momentum and Velocity
      • 
        
      • 3.2.4 The Force of Gravity
    • 
      
    • 3.3 The Integrator
      
      • 3.3.1 The Update Equations
      • 
        
      • 3.3.2 The Complete Integrator
  
  
  • 4 The Particle Physics Engine
    
    • 4.1 Ballistics
      
      • 4.1.1 Setting Projectile Properties
      • 
        
      • 4.1.2 Implementation
    • 
      
    • 4.2 Fireworks
      
      • 4.2.1 The Firework Data
      • 
        
      • 4.2.2 Firework Rules
      • 
        
      • 4.2.3 The Implementation
• 
  
• II Mass Aggregate Physics
  
  • 5 Adding General Forces
    
    • 5.1 D'Alembert's Principle
    • 
      
    • 5.2 Force Generators
      
      • 5.2.1 Interfaces and Polymorphism
      • 
        
      • 5.2.2 Implementation
      • 
        
      • 5.2.3 A Gravity Force Generator
      • 
        
      • 5.2.4 A Drag Force Generator
    • 
      
    • 5.3 Built-In Gravity and Damping
  
  
  • 6 Springs and Spring-like Things
    
    • 6.1 Hook's Law
    • 
      
    • 6.2 Spring-Like Force Generators
      
      • 6.2.1 A Basic Spring Generator
      • 
        
      • 6.2.2 An Anchored Spring Generator
      • 
        
      • 6.2.3 An Elastic Bungee Generator
      • 
        
      • 6.2.4 A Buoyancy Force Generator
    • 
      
    • 6.3 Stiff Springs
      
      • 6.3.1 The Problem of Stiff Springs
      • 
        
      • 6.3.2 Faking Stiff Springs
  
  
  • 7 Hard Constraints
    
    • 7.1 Simple Collision Resolution
      
      • 7.1.1 The Closing Velocity
      • 
        
      • 7.1.2 The Coefficient of Restitution
      • 
        
      • 7.1.3 The Collision Direction and the Contact Normal
      • 
        
      • 7.1.4 Impulses
    • 
      
    • 7.2 Collision Processing
      
      • 7.2.1 Collision Detection
      • 
        
      • 7.2.2 Resolving Interpenetration
      • 
        
      • 7.2.3 Resting Contacts
    • 
      
    • 7.3 The Contact Resolver Algorithm
      
      • 7.3.1 Resolution Order
      • 
        
      • 7.3.2 Time-Division Engines
    • 
      
    • 7.4 Collision-Like Things
      
      • 7.4.1 Cables
      • 
        
      • 7.4.2 Rods
  
  
  • 8 The Mass Aggregate Physics Engine
    
    • 8.1 Overview of the Engine
    • 
      
    • 8.2 Using the Physics Engine
      
      • 8.2.1 Rope Bridges and Cables
      • 
        
      • 8.2.2 Friction
• 
  
• III Rigid Body Physics
  
  
  • 9 The Mathematics of Rotations
    
    • 9.1 Rotating Objects in 2D
      
      • 9.1.1 The Mathematics of Angles
      • 
        
      • 9.1.2 Angular Speed
      • 
        
      • 9.1.3 The Origin and the Centre of Mass
    • 
      
    • 9.2 Orientation in 3D
      
      • 9.2.1 Euler Angles
      • 
        
      • 9.2.2 Axis-Angle
      • 
        
      • 9.2.3 Rotation Matrices
      • 
        
      • 9.2.4 Quaternions
    • 
      
    • 9.3 Angular Velocity and Acceleration
      
      • 9.3.1 Velocity of a Point
      • 
        
      • 9.3.2 Angular Acceleration
    • 
      
    • 9.4 Implementing the Mathematics
      
      • 9.4.1 The Matrix Classes
      • 
        
      • 9.4.2 Matrix Multiplication
      • 
        
      • 9.4.3 Matrix Inverse and Transpose
      • 
        
      • 9.4.4 Converting a Quaternion to a Matrix
      • 
        
      • 9.4.5 Transforming Vectors
      • 
        
      • 9.4.6 Changing the Basis of a Matrix
      • 
        
      • 9.4.7 The Quaternion Class
      • 
        
      • 9.4.8 Normalising Quaternions
      • 
        
      • 9.4.9 Combining Quaternions
      • 
        
      • 9.4.10 Rotating
      • 
        
      • 9.4.11 Updating by The Angular Velocity
  
  
  • 10 Laws of Motion for Rigid Bodies
    
    • 10.1 The Rigid Body
    • 
      
    • 10.2 Newton 2 for Rotation
      
      • 10.2.1 Torque
      • 
        
      • 10.2.2 The Moment of Inertia
      • 
        
      • 10.2.3 Inertia Tensor in World-Coordinates
    • 
      
    • 10.3 D'Alembert for Rotation
      
      • 10.3.1 Force Generators
    • 
      
    • 10.4 The Rigid Body Integration
  
  
  • 11 The Rigid Body Physics Engine
    
    • 11.1 Overview of the Engine
    • 
      
    • 11.2 Using the Physics Engine
      
      • 11.2.1 A Flight Simulator
      • 
        
      • 11.2.2 A Sailing Simulator
• 
  
• IV Collision Detection
  
  • 12 Collision Detection
    
    • 12.1 Collision Detection Pipeline
    • 
      
    • 12.2 Coarse Collision Detection
    • 
      
    • 12.3 Bounding Volumes
      
      • 12.3.1 Hierarchies
      • 
        
      • 12.3.2 Building the Hierarchy
      • 
        
      • 12.3.3 Sub-object Hierarchies
    • 
      
    • 12.4 Spatial Data Structures
      
      • 12.4.1 Binary Space Partitioning (BSP)
      • 
        
      • 12.4.2 Oct-Trees and Quad-Trees
      • 
        
      • 12.4.3 Grids
      • 
        
      • 12.4.4 Multi-Resolution Maps
    • 
      
    • 12.5 Summary
  
  
  • 13 Generating Contacts
    
    • 13.1 Collision Geometry
      
      • 13.1.1 Primitive Assemblies
      • 
        
      • 13.1.2 Generating Collision Geometry
    • 
      
    • 13.2 Contact Generation
      
      • 13.2.1 Contact Data
      • 
        
      • 13.2.2 Point-Face Contacts
      • 
        
      • 13.2.3 Edge-Edge Contacts
      • 
        
      • 13.2.4 Edge-Face Contacts
      • 
        
      • 13.2.5 Face-Face Contacts
      • 
        
      • 13.2.6 Early Outs
    • 
      
    • 13.3 Primitive Collision Algorithms
      
      • 13.3.1 Colliding two Spheres
      • 
        
      • 13.3.2 Colliding a Sphere and a Plane
      • 
        
      • 13.3.3 Colliding a Box and a Plane
      • 
        
      • 13.3.4 Colliding a Sphere and a Box
      • 
        
      • 13.3.5 Colliding two Boxes
• 
  
• V Contact Physics
  
  • 14 Collision Resolution
    
    • 14.1 Impulses and Implusive Torques
      
      • 14.1.1 Impulsive Torque
      • 
        
      • 14.1.2 Rotating Collisions
      • 
        
      • 14.1.3 Handling Rotating Collisions
    • 
      
    • 14.2 Collision Impluses
      
      • 14.2.1 Change to Contact-coordinates
      • 
        
      • 14.2.2 Velocity change by Impulse
      • 
        
      • 14.2.3 Impulse change by Velocity
      • 
        
      • 14.2.4 Calculating the Desired Velocity Change
      • 
        
      • 14.2.5 Calculating the Impulse
      • 
        
      • 14.2.6 Applying the Impulse
    • 
      
    • 14.3 Resolving Interpenetration
      
      • 14.3.1 Choosing a Resolution Method
      • 
        
      • 14.3.2 Implementing Non-linear Projection
      • 
        
      • 14.3.3 Avoiding Over-Rotation
    • 
      
    • 14.4 The Collision Resolution Process
      
      • 14.4.1 The Collision Resolution Pipeline
      • 
        
      • 14.4.2 Preparing Contact Data
      • 
        
      • 14.4.3 Resolving Penetration
      • 
        
      • 14.4.4 Resolving Velocity
      • 
        
      • 14.4.5 Alternative Update Algorithms
      • 
        
      • 14.4.6 Summary
  
  
  • 15 Resting Contacts and Friction
    
    • 15.1 Resting Forces
      
      • 15.1.1 Force Calculations
    • 
      
    • 15.2 Micro-Collisions
      
      • 15.2.1 Removing Accelerated Velocity
      • 
        
      • 15.2.2 Lowering the Restitution
      • 
        
      • 15.2.3 The New Velocity Calculation
    • 
      
    • 15.3 Types of Friction
      
      • 15.3.1 Static and Dynamic Friction
      • 
        
      • 15.3.2 Isotropic and Anisotropic Friction
    • 
      
    • 15.4 Implementing Friction
      
      • 15.4.1 Friction as Impulses
      • 
        
      • 15.4.2 Modifying the Velocity Resolution Algorithm
      • 
        
      • 15.4.3 Putting it All Together
    • 
      
    • 15.5 Friction and Sequential Contact Resolution
  
  
  • 16 Stability and Optimization
    
    • 16.1 Stability
      
      • 16.1.1 Quaternion Drift
      • 
        
      • 16.1.2 Interpenetration on Slopes
      • 
        
      • 16.1.3 Integration Stability
      • 
        
      • 16.1.4 The Benefit of Pessimistic Collision Detection
      • 
        
      • 16.1.5 Changing Mathematical Accuracy
    • 
      
    • 16.2 Optimizations
      
      • 16.2.1 Sleep
      • 
        
      • 16.2.2 Margins of Error for Penetration and Velocity
      • 
        
      • 16.2.3 Contact Grouping
      • 
        
      • 16.2.4 Code Optimisations
      • 
        
      • 16.2.5 Optimisation Summary
  
  
  • 17 Putting It All Together
    
    • 17.1 Overview of the Engine
    • 
      
    • 17.2 Using the Physics Engine
      
      • 17.2.1 Ragdolls
      • 
        
      • 17.2.2 Fracture Physics
      • 
        
      • 17.2.3 Explosive Physics
    • 
      
    • 17.3 Limitations of the Engine
      
      • 17.3.1 Stacks
      • 
        
      • 17.3.2 Reaction Force Friction
      • 
        
      • 17.3.3 Joint Assemblies
      • 
        
      • 17.3.4 Stiff Springs
• 
  
• VI Horizons
  
  • 18 Other Types of Physics
    
    • 18.1 Simultaneous Contact Resolution
      
      • 18.1.1 The Jacobian
      • 
        
      • 18.1.2 The Linear Complimentary Problem
    • 
      
    • 18.2 Reduced Coordinate Approaches
    • 
      
    • 18.3 Where to Look for More Information
• 
  
• Index

About the Author

Ian Millington is a partner of IPR Ventures, a consulting company developing next-generation AI technologies for entertainment, modeling, and simulation. Previously he founded Mindlathe Ltd, the largest specialist AI middleware company in computer games, working with on a huge range of game genres and technologies. He has a long background in AI, including PhD research in complexity theory and natural computing. He has published academic and professional papers and articles on topics ranging from paleontology to hypertext.