List Of Figures

Preface To The Second Edition

Preface To The First Edition

Acknowledgments

About The Author

Chapter 1 Introduction 1

1.1 What Is Game Physics? 2

1.2 What Is A Physics Engine? 2

1.2.1 Advantages Of A Physics Engine 3

1.2.2 Weaknesses Of A Physics Engine 4

1.3 Approaches To Physics Engines 5

1.3.1 Types Of Objects 5

1.3.2 Contact Resolution 6

1.3.3 Impulses And Forces 6

1.3.4 What We're Building 7

1.4 The Mathematics Of Physics Engines 8

1.4.1 The Math You Need To Know 8

1.4.2 The Math We'll Review 9

1.4.3 The Math I'll Introduce 10

1.5 The Source Code In The Book 10

1.6 How The Book Is Structured 11

1.6.1 Exercises And Projects 12

Part I Particle Physics 15

Chapter 2 The Mathematics Of Particles 17

2.1 Vectors 17

2.1.1 The Handedness Of Space 21

2.1.2 Vectors And Directions 23

2.1.3 Scalar And Vector Multiplication 25

2.1.4 Vector Addition And Subtraction 27

2.1.5 Multiplying Vectors 29

2.1.6 The Component Product 30

2.1.7 The Scalar Product 31

2.1.8 The Vector Product 33

2.1.9 The Orthonormal Basis 37

2.2 Calculus 38

2.2.1 Differential Calculus 38

2.2.2 Integral Calculus 43

2.3 Summary 44

2.4 Exercises 45

Chapter 3 The Laws Of Motion 47

3.1 The Particle 48

3.2 The First Two Laws 49

3.2.1 The Force Equations 50

3.2.2 Adding Mass To Particles 51

3.2.3 Momentum And Velocity 52

3.2.4 The Force Of Gravity 53

3.3 The Integrator 55

3.3.1 The Update Equations 55

3.3.2 The Complete Integrator 57

3.4 Summary 58

3.5 Exercises 59

Chapter 4 The Particle Physics Engine 61

4.1 Ballistics 61

4.1.1 Setting Projectile Properties 62

4.1.2 Implementation 63

4.2 Fireworks 66

4.2.1 The Fireworks Data 66

4.2.2 Firework Rules 67

4.2.3 The Implementation 69

4.3 Summary 73

4.4 Projects 73

Part II Mass Aggregate Physics 75

Chapter 5 Adding General Forces 77

5.1 D'alembert's Principle 77

5.2 Force Generators 80

5.2.1 Interfaces And Polymorphism 81

5.2.2 Implementation 81

5.2.3 A Gravity Force Generator 84

5.2.4 A Drag Force Generator 85

5.3 Built-In Gravity And Damping 87

5.4 Summary 87

5.5 Exercises 88

Chapter 6 Springs And Spring-Like Things 89

6.1 Hook's Law 89

6.2 Spring-Like Force Generators 92

6.2.1 A Basic Spring Force Generator 92

6.2.2 An Anchored Spring Generator 94

6.2.3 An Elastic Bungee Generator 96

6.2.4 A Buoyancy Force Generator 98

6.3 Stiff Springs 101

6.3.1 The Stiff Springs Problem 102

6.3.2 Faking Stiff Springs 104

6.4 Summary 110

6.5 Exercises 110

Chapter 7 Hard Constraints 113

7.1 Simple Collision Resolution 113

7.1.1 The Closing Velocity 114

7.1.2 The Coefficient Of Restitution 115

7.1.3 The Collision Direction And The Contact Normal 115

7.1.4 Impulses 117

7.2 Collision Processing 118

7.2.1 Collision Detection 121

7.2.2 Resolving Interpenetration 123

7.2.3 Resting Contacts 126

7.3 The Contact Resolver Algorithm 130

7.3.1 Resolution Order 131

7.3.2 Time-Division Engines 135

7.4 Collision-Like Things 136

7.4.1 Cables 137

7.4.2 Rods 140

7.5 Summary 142

7.6 Exercises 142

Chapter 8 The Mass Aggregate Physics Engine 145

8.1 Overview Of The Engine 145

8.2 Using The Physics Engine 151

8.2.1 Rope Bridges And Cables 151

8.2.2 Friction 152

8.2.3 Blob Games 153

8.3 Summary 153

8.4 Projects 154

Part III Rigid-Body Physics 155

Chapter 9 The Mathematics Of Rotations 157

9.1 Rotating Objects In 2d 158

9.1.1 The Mathematics Of Angles 158

9.1.2 Angular Speed 159

9.1.3 The Origin And The Center Of Mass 160

9.2 Orientation In 3d 165

9.2.1 Euler Angles 165

9.2.2 Axis-Angle 167

9.2.3 Rotation Matrices 168

9.2.4 Quaternions 169

9.3 Angular Velocity And Acceleration 172

9.3.1 Velocity Of A Point 173

9.3.2 Angular Acceleration 173

9.4 Implementing The Mathematics 173

9.4.1 The Matrix Classes 174

9.4.2 Matrix Multiplication 175

9.4.3 Matrix Inverse And Transpose 184

9.4.4 Converting A Quaternion To A Matrix 191

9.4.5 Transforming Vectors 193

9.4.6 Changing The Basis Of A Matrix 197

9.4.7 The Quaternion Class 198

9.4.8 Normalizing Quaternions 200

9.4.9 Combining Quaternions 200

9.4.10 Rotating 201

9.4.11 Updating By The Angular Velocity 202

9.5 Summary 203

9.6 Exercises 203

Chapter 10 Laws Of Motion For Rigid Bodies 207

10.1 The Rigid Body 207

10.2 Newton-2 For Rotation 211

10.2.1 Torque 211

10.2.2 The Moment Of Inertia 213

10.2.3 Inertia Tensor In World Coordinates 216

10.3 D'alembert For Rotation 220

10.3.1 Force Generators 223

10.4 The Rigid-Body Integration 226

10.5 Summary 228

10.6 Exercises 228

Chapter 11 The Rigid-Body Physics Engine 231

11.1 Overview Of The Engine 231

11.2 Using The Physics Engine 234

11.2.1 A Flight Simulator 234

11.2.2 A Sailing Simulator 242

11.3 Summary 247

11.4 Projects 248

Part IV Collision Detection 251

Chapter 12 Collision Detection 253

12.1 The Collision Detection Pipeline 254

12.2 Broad-Phase Collision Detection 255

12.2.1 Requirements 256

12.3 Bounding Volume Hierarchies 257

12.3.1 Hierarchies 259

12.3.2 Building The Hierarchy 266

12.3.3 Subobject Hierarchies 275

12.4 Spatial Partitioning 276

12.4.1 Binary Space Partitioning 276

12.4.2 Oct-Trees And Quad-Trees 281

12.4.3 Grids 283

12.4.4 Multiresolution Maps 287

12.5 Summary 288

12.6 Exercises 288

Chapter 13 Generating Contacts 291

13.1 Collision Geometry 292

13.1.1 Primitive Assemblies 293

13.2 Contact Generation 294

13.2.1 Contact Types 295

13.2.2 Contact Data 298

13.2.3 Vertex face Contacts 300

13.2.4 Edge -Edge Contacts 301

13.2.5 Edge face Contacts 301

13.2.6 Face face Contacts 302

13.2.7 Testing Before Generating Contacts 303

13.3 Simple Collision Algorithms 304

13.3.1 Colliding Two Spheres 305

13.3.2 Colliding A Sphere And A Plane 307

13.3.3 Colliding A Box And A Plane 310

13.3.4 Colliding A Box And A Sphere 315

13.4 Separating Axis Tests 319

13.4.1 Generating Contact Data With SATS 320

13.4.2 Colliding Two Boxes 322

13.4.3 Colliding Convex Polyhedra 326

13.5 Coherence 328

13.6 Summary 331

13.7 Exercises 331

Part V Contact Physics 333

Chapter 14 Collision Resolution 335

14.1 Impulse And Impulsive Torque 335

14.1.1 Impulsive Torque 336

14.1.2 Rotating Collisions 338

14.1.3 Handling Rotating Collisions 339

14.2 Collision Impulses 340

14.2.1 Change To Contact Coordinates 340

14.2.2 Velocity Change By Impulse 347

14.2.3 Impulse Change By Velocity 351

14.2.4 Calculating The Desired Velocity Change 351

14.2.5 Calculating The Impulse 353

14.2.6 Applying The Impulse 353

14.3 Resolving Interpenetration 355

14.3.1 Choosing A Resolution Method 355

14.3.2 Implementing Nonlinear Projection 359

14.3.3 Avoiding Overrotation 362

14.4 The Collision Resolution Process 364

14.4.1 The Collision Resolution Pipeline 365

14.4.2 Preparing Contact Data 367

14.4.3 Resolving Penetration 372

14.4.4 Resolving Velocity 379

14.4.5 Alternative Update Algorithms 381

14.5 Summary 384

14.6 Exercises 385

Chapter 15 Resting Contacts And Friction 387

15.1 Resting Forces 388

15.1.1 Force Calculations 389

15.2 Microcollisions 390

15.2.1 Removing Accelerated Velocity 392

15.2.2 Lowering The Restitution 393

15.2.3 The New Velocity Calculation 394

15.3 Types Of Friction 395

15.3.1 Static And Dynamic Friction 395

15.3.2 Isotropic And Anisotropic Friction 398

15.4 Implementing Friction 399

15.4.1 Friction As Impulses 400

15.4.2 Modifying The Velocity Resolution Algorithm 402

15.4.3 Putting It All Together 407

15.5 Friction And Sequential Contact Resolution 410

15.6 Summary 411

15.7 Exercises 412

Chapter 16 Stability And Optimization 413

16.1 Stability 413

16.1.1 Quaternion Drift 414

16.1.2 Interpenetration On Slopes 415

16.1.3 Integration Stability 417

16.1.4 The Benefit Of Pessimistic Collision Detection 419

16.1.5 Changing Mathematical Accuracy 420

16.2 Optimizations 421

16.2.1 Sleep 422

16.2.2 Margins Of Error For Penetration And Velocity 430

16.2.3 Contact Grouping 432

16.2.4 Code Optimizations 434

16.3 Summary 436

Chapter 17 Putting It All Together 437

17.1 Overview Of The Engine 437

17.2 Using The Physics Engine 439

17.2.1 Ragdolls 440

17.2.2 Fracture Physics 445

17.2.3 Explosive Physics 451

17.3 Limitations Of The Engine 458

17.3.1 Stacks 458

17.3.2 Reaction Force Friction 458

17.3.3 Joint Assemblies 459

17.3.4 Stiff Springs 459

17.4 Summary 459

17.5 Projects 459

Part VI Further Topics In Physics 461

Chapter 18 Physics In Two Dimensions 463

18.1 2d Or 3d? 463

18.2 Vector Mathematics 465

18.3 Particle And Mass Aggregate Physics 467

18.4 The Mathematics Of Rotation 467

18.4.1 Representing Rotation 467

18.4.2 Matrices 469

18.5 Rigid-Body Dynamics 469

18.6 Collision Detection 471

18.6.1 Vertex edge Contacts 472

18.6.2 Edge edge Contacts 472

18.6.3 Contact Generation 472

18.7 Collision Response 473

18.8 Summary 473

18.9 Projects 474

Chapter 19 Other Programming Languages 475

19.1 Actionscript 3 475

19.2 C 479

19.3 Java 480

19.4 C# 481

19.5 Other Scripting Languages 482

Chapter 20 Other Types Of Physics 483

20.1 Simultaneous Contact Resolution 483

20.1.1 The Jacobian 484

20.1.2 The Linear-Complementarity Problem 485

20.2 Reduced Coordinate Approaches 488

20.3 Summary 489

Appendix A Useful Inertia Tensors 491

A.1 Discrete Masses 492

A.2 Continuous Masses 492

A.3 Common Shapes 493

A.3.1 Cuboid 493

A.3.2 Sphere 493

A.3.3 Cylinder 494

A.3.4 Cone 494

A.3.5 Hemisphere 495

A.4 Moments Of Inertia In 2d 495

A.4.1 Common 2d Shapes 495

Appendix B Useful Friction Coefficients 497

Appendix C Mathematics Summary 499

C.1 Vectors 499

C.2 Quaternions 500

C.3 Matrices 501

C.4 Integration 502

C.5 Physics 503

C.6 Other Formulas 504

Glossary 505

Bibliography 509

Index 511