Game Physics Engine Development

Simulating physics helps cutting-edge games distinguish themselves by making virtual objects behave as we expect them to in the real world. Physics engines are the software programs that run these simulations. Building an engine is difficult, however. There are a large number of new developers (and hobbyists) coming into this market who need help through this complex process. Current introductory books are inadequate; they don't bring enough real-world programming experience to the task. There is a need for an introductory book on game physics with solid coding guidance but which limits the math content. Ian Millington brings his extensive professional programming experience to this problem. He has developed games since 1987, has studied AI and mathematics at the PhD level, and founded Mindlathe Ltd., a company that designed and built commercial physics engines. Physics Engine Development carefully describes each step in the creation of a robust, usable physics engine. It introduces the mathematical concepts in a clear and simple manner, keeping to high school level topics and building a physics code library as it goes. Each new concept is explained in diagrams and code to make sure that even the most novice of game programmers understands. The companion CD-ROM includes the source code for a complete physics engine of commercial quality. This book will serve as a introduction to more mathematically advanced books on game physics, such as Dave Eberly's Game Physics.

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