GAME PHYSICS ENGINE DEVELOPMENT
CONTENTS CHAPTER INTRODUCTION WHAT IS GAME PHYSICS? WHAT IS A PHYSICS ENGINE? ADVANTAGES OF A PHYSICS ENGINE WEAKNESSES OF A PHYSICS ENGINE APPROACHES TO PHYSICS ENGINES TYPES OF OBJECT CONTACT RESOLUTION IMPULSES AND FORCES WHAT WE’RE BUILDING THE MATHEMATICS OF PHYSICS ENGINES THE MATH YOU NEED TO KNOW THE MATH WE’LL REVIEW THE MATH WE’LL INTRODUCE THE SOURCE CODE IN THIS BOOK HOW THIS BOOK IS STRUCTURED PART I PARTICLE PHYSICS CHAPTER THE MATHEMATICS OF PARTICLES VECTORS THE HANDEDNESS OF SPACE VECTORS AND DIRECTIONS SCALAR AND VECTOR MULTIPLICATION VECTOR ADDITION AND SUBTRACTION MULTIPLYING VECTORS THE COMPONENT PRODUCT THE SCALAR PRODUCT THE VECTOR PRODUCT THE ORTHONORMAL BASIS CALCULUS DIFFERENTIAL CALCULUS INTEGRAL CALCULUS SUMMARY THE LAWS OF MOTION A PARTICLE THE FIRST TWO LAWS THE FIRST LAW THE SECOND LAW THE FORCE EQUATIONS ADDING MASS TO PARTICLES MOMENTUM AND VELOCITY THE FORCE OF GRAVITY THE INTEGRATOR THE UPDATE EQUATIONS THE COMPLETE INTEGRATOR THE PARTICLE PHYSICS ENGINE BALLISTICS SETTING PROJECTILE PROPERTIES IMPLEMENTATION FIREWORKS THE FIREWORKS DATA THE FIREWORKS RULES THE IMPLEMENTATION PART II MASS-AGGREGATE PHYSICS ADDING GENERAL FORCES D’ALEMBERT’S PRINCIPLE FORCE GENERATORS INTERFACES AND POLYMORPHISM A GRAVITY FORCE GENERATOR A DRAG FORCE GENERATOR BUILT-IN GRAVITY AND DAMPING SPRINGS AND SPRINGLIKE THINGS HOOK’S LAW THE LIMIT OF ELASTICITY SPRINGLIKE THINGS SPRINGLIKE FORCE GENERATORS A BASIC SPRING GENERATOR AN ANCHORED SPRING GENERATOR AN ELASTIC BUNGEE GENERATOR A BUOYANCY FORCE GENERATOR STIFF SPRINGS THE PROBLEM OF STIFF SPRINGS FAKING STIFF SPRINGS HARD CONSTRAINTS SIMPLE COLLISION RESOLUTION THE CLOSING VELOCITY THE COEF?CIENT OF RESTITUTION THE COLLISION DIRECTION AND THE CONTACT NORMAL IMPULSES COLLISION PROCESSING COLLISION DETECTION RESOLVING INTERPENETRATION RESTING CONTACTS THE CONTACT RESOLVER ALGORITHM RESOLUTION ORDER TIME-DIVISION ENGINES COLLISIONLIKE THINGS CABLES RODS THE MASS-AGGREGATE PHYSICS ENGINE OVERVIEW OF THE ENGINE USING THE PHYSICS ENGINE ROPE-BRIDGES AND CABLES FRICTION BLOB GAMES PART III RIGID-BODY PHYSICS THE MATHEMATICS OF ROTATIONS ROTATING OBJECTS IN TWO DIMENSIONS THE MATHEMATICS OF ANGLES ANGULAR SPEED THE ORIGIN AND THE CENTER OF MASS ORIENTATION IN THREE DIMENSIONS EULER ANGLES AXIS–ANGLE ROTATION MATRICES QUATERNIONS ANGULAR VELOCITY AND ACCELERATION THE VELOCITY OF A POINT ANGULAR ACCELERATION IMPLEMENTING THE MATHEMATICS THE MATRIX CLASSES MATRIX MULTIPLICATION THE MATRIX INVERSE AND TRANSPOSE CONVERTING A QUATERNION TO A MATRIX TRANSFORMING VECTORS CHANGING THE BASIS OF A MATRIX THE QUATERNION CLASS NORMALIZING QUATERNIONS COMBINING QUATERNIONS 9 4 10 ROTATING 9 4 11 UPDATING BY THE ANGULAR VELOCITY 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 THE INERTIA TENSOR IN WORLD COORDINATES 10 3 D’ALEMBERT FOR ROTATION 10 3 1 FORCE GENERATORS 10 4 THE RIGID-BODY INTEGRATION 10 5 SUMMARY 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 11 3 SUMMARY PART IV COLLISION DETECTION 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 12 4 2 OCT-TREES AND QUAD-TREES 12 4 3 GRIDS 12 4 4 MULTI-RESOLUTION MAPS 12 5 SUMMARY 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 3 6 EF?CIENCY AND GENERAL POLYHEDRA 13 4 SUMMARY PART V CONTACT PHYSICS COLLISION RESOLUTION 14 1 IMPULSES AND IMPULSIVE TORQUES 14 1 1 IMPULSIVE TORQUE 14 1 2 ROTATING COLLISIONS 14 1 3 HANDLING ROTATING COLLISIONS 14 2 COLLISION IMPULSES 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 NONLINEAR PROJECTION 14 3 3 AVOIDING EXCESSIVE 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 5 SUMMARY 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 6 SUMMARY 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 BENE?T 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 OPTIMIZATIONS 16 3 SUMMARY 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 17 4 SUMMARY PART VI WHAT COMES NEXT? OTHER TYPES OF PHYSICS 18 1 SIMULTANEOUS CONTACT RESOLUTION 18 1 1 THE JACOBIAN 18 1 2 THE LINEAR COMPLEMENTARY PROBLEM 18 2 REDUCED COORDINATE APPROACHES 18 3 SUMMARY