# Game Physics Engine Development

**By**

- Ian Millington, Ian Millington is a consultant specializing in research and development for the games industry. He has done a good deal of work on physics engines and developing physics code. He was previously the CEO of a games technology company, and before that he ran one of the first web-based games companies. Millington's background is in artificial intelligence, and he has published academically on a range of topics. Ian Millington is author of Artificial Intelligence for Games (MK).

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.

View full description### Audience

Game developers, esp. novice developers, students of game development, and game hobbyists

### Book information

- Published: March 2007
- Imprint: MORGAN KAUFMANN
- ISBN: 978-0-12-369471-3

### 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

- 1 Introduction
**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

- 2.1 Vectors

- 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

- 4.1 Ballistics

- 2 The Mathematics of Particles
**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

- 7.1 Simple Collision Resolution

- 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

- 5 Adding General Forces
**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

- 9.1 Rotating Objects in 2D

- 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

- 9 The Mathematics of Rotations
**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

- 13.1 Collision Geometry

- 12 Collision Detection
**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

- 14.1 Impulses and Implusive Torques

- 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

- 15.1 Resting Forces

- 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

- 16.1 Stability

- 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

- 14 Collision Resolution
**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

- 18.1 Simultaneous Contact Resolution

- 18 Other Types of Physics
- Index