Game Physics

Game Physics is an introduction to the ideas and techniques needed to create physically realistic 3D graphic environments. As a companion volume to Dave Eberly's industry standard 3D Game Engine Design, Game Physics shares a similar practical approach and format. Dave includes simulations to introduce the key problems involved and then gradually reveals the mathematical and physical concepts needed to solve them. He then describes all the algorithmic foundations and uses code examples and working source code to show how they are implemented, culminating in a large collection of physical simulations. This book tackles the complex, challenging issues that other books avoid, including Lagrangian dynamics, rigid body dynamics, impulse methods, resting contact, linear complementarity problems, deformable bodies, mass-spring systems, friction, numerical solution of differential equations, numerical stability and its relationship to physical stability, and Verlet integration methods. Dave even describes when real physics isn't necessary-and hacked physics will do. *CD-ROM with extensive C++ source code that supports physical simulation.Operating Systems and compilers that are supported: Windows 2000/XP (Visual C++ versions 6, 7. 0, and 7.1), Linux (g++ 3.x), Macintosh OS 10.3 (Xcode, CodeWarrior 9), SGI IRIX (Mips Pro 7.x), HP-UX (aCC), and Sun Solaris (g++ 3.x). The source is compatible with many game engines-including the Wild Magic engine, for which the complete source code is included. *Contains sample applications for shader programs (OpenGL and DirectX), including deformation by vertex displacement, skin and bones for smooth object animation, rippling ocean waves with realistic lighting, refraction effects, Fresnel reflectance, and iridescence. *Covers special topics not found elsewhere, such as linear complementarity problems and Lagrangian dynamics. *Includes exercises for instructional use and a review of essential mathematics.

Table of Contents:
Trademarks Figures Tables Preface About the CD-ROM 1 Introduction 1.1 A Brief History of the World 1.2 A Summary of the Topics 1.3 Examples and Exercises 2 Basic Concepts from Physics 2.1 Rigid Body Classification 2.2 Rigid Body Kinematics 2.2.1 Single Particle 2.2.2 Particle Systems and Continuous Materials 2.3 Newton's Laws 2.4 Forces 2.4.1 Gravitational Forces 2.4.2 Spring Forces 2.4.3 Friction and Other Dissipative Forces 2.4.4 Torque 2.4.5 Equilibrium 2.5 Momenta 2.5.1 Linear Momentum 2.5.2 Angular Momentum 2.5.3 Center of Mass 2.5.4 Moments and Products of Inertia 2.5.5 Mass and Inertia Tensor of a Solid Polyhedron 2.6 Energy 2.6.1 Work and Kinetic Energy 2.6.2 Conservative Forces and Potential Energy 3 Rigid Body Motion 3.1 Newtonian Dynamics 3.2 Lagrangian Dynamics 3.2.1 Equations of Motion for a Particle 3.2.2 Time-Varying Frames or Constraints 3.2.3 Interpretation of the Equations of Motion 3.2.4 Equations of Motion for a System of Particles 3.2.5 Equations of Motion for a Continuum of Mass 3.2.6 Examples with Conservative Forces 3.2.7 Examples with Dissipative Forces 3.3 Euler's Equations of Motion 4 Deformable Bodies 4.1 Elasticity, Stress, and Strain 4.2 Mass-Spring Systems 4.2.1 One-Dimensional Array of Masses 4.2.2 Two-Dimensional Array of Masses 4.2.3 Three-Dimensional Array of Masses 4.2.4 Arbitrary Configurations 4.3 Control Point Deformation 4.3.1 B-Spline Curves 4.3.2 NURBS Curves 4.3.3 B-Spline Surfaces 4.3.4 NURBS Surfaces 4.3.5 Surfaces Built from Curves 4.4 Free-Form Deformation 4.5 Implicit Surface Deformation 4.5.1 Level Set Extraction 4.5.2 Isocurve Extraction in 2D Images 4.5.3 Isosurface Extraction in 3D Images 5 Physics Engines 5.1 Unconstrained Motion 5.1.1 An Illustrative Implementation 5.1.2 A Practical Implementation 5.2 Constrained Motion 5.2.1 Collision Points 5.2.2 Collision Response for Colliding Contact 5.2.3 Collision Response for Resting Contact 5.2.4 An Illustrative Implementation 5.2.5 Lagrangian Dynamics 5.3 Collision Detection with Convex Polyhedra 5.3.1 The Method of Separating Axes 5.3.2 Stationary Objects 5.3.3 Objects Moving with Constant Linear Velocity 5.3.4 Oriented Bounding Boxes 5.3.5 Boxes Moving with Constant Linear and Angular Velocity 5.4 Collision Culling: Spatial and Temporal Coherence 5.4.1 Culling with Bounding Spheres 5.4.2 Culling with Axis-Aligned Bounding Boxes 5.5 Variations 6 Physics and Shader Programs 6.1 Introduction 6.2 Vertex and Pixel Shaders 6.3 Deformation by Vertex Displacement 6.4 Skin-and-Bones Animation 6.5 Rippling Ocean Waves 6.6 Refraction 6.7 Fresnel Reflectance 6.8 Iridescence 7 Linear Complementarity and Mathematical Programming 7.1 Linear Programming 7.1.1 A Two-Dimensional Example 7.1.2 Solution by Pairwise Intersections 7.1.3 Statement of the General Problem 7.1.4 The Dual Problem 7.2 The Linear Complementarity Problem 7.2.1 The Lemke-Howson Algorithm 7.2.2 Zero Constant Terms 7.2.3 The Complementary Variable Cannot Leave the Diction 7.3 Mathematical Programming 7.3.1 Karush-Kuhn-Tucker Conditions 7.3.2 Convex Quadratic Programming 7.3.3 General Duality Theory 7.4 Applications 7.4.1 Distance Calculations 7.4.2 Contact Forces 8 Differential Equations 8.1 First-Order Equations 8.2 Existence, Uniqueness, and Continuous Dependence 8.3 Second-Order Equations 8.4 General-Order Differential Equations 8.5 Systems of Linear Differential Equations 8.6 Equilibria and Stability 8.6.1 Stability for Constant-Coefficient Linear Systems 8.6.2 Stability for General Autonomous Systems 9 Numerical Methods 9.1 Euler's Method 9.2 Higher-Order Taylor Methods 9.3 Methods Via an Integral Formulation 9.4 Runge-Kutta Methods 9.4.1 Second-Order Methods 9.4.2 Third-Order Methods 9.4.3 Fourth-Order Method 9.5 Multistep Methods 9.6 Predictor-Corrector Methods 9.7 Extrapolation Methods 9.7.1 Richardson Extrapolation 9.7.2 Application to Differential Equations 9.7.3 Polynomial Interpolation and Extrapolation 9.7.4 Rational Polynomial Interpolation and Extrapolation 9.7.5 Modified Midpoint Method 9.7.6 Bulirsch-Stoer Method 9.8 Verlet Integration 9.8.1 Forces without a Velocity Component 9.8.2 Forces with a Velocity Component 9.8.3 Simulating Drag in the System 9.8.4 Leap Frog Method 9.8.5 Velocity Verlet Method 9.8.6 Gear's Fifth-Order Predictor-Corrector Method 9.9 Numerical Stability and its Relationship to Physical Stability 9.9.1 Stability for Single-Step Methods 9.9.2 Stability for Multistep Methods 9.9.3 Choosing a Stable Step Size 9.10 Stiff Equations 10 Quaternions 10.1 Rotation Matrices 10.2 The Classical Approach 10.2.1 Algebraic Operations 10.2.2 Relationship of Quaternions to Rotations 10.3 A Linear Algebraic Approach 10.4 From Rotation Matrices to Quaternions Contributed by Ken Shoemake 10.4.1 2D Rotations 10.4.2 Linearity 10.4.3 3D Rotations: Geometry 10.4.4 4D Rotations 10.4.5 3D Rotations: Algebra 10.4.6 4D Matrix 10.4.7 Retrospect, Prospect 10.5 Interpolation of Quaternions 10.5.1 Spherical Linear Interpolation 10.5.2 Spherical Quadratic Interpolation 10.6 Derivatives of Time-Varying Quaternions A Linear Algebra A.1 A Review of Number Systems A.1.1 The Integers A.1.2 The Rational Numbers A.1.3 The Real Numbers A.1.4 The Complex Numbers A.1.5 Fields A.2 Systems of Linear Equations A.2.1 A Closer Look at Two Equations in Two Unknowns A.2.2 Gaussian Elimination and Elementary Row Operations A.2.3 Nonsquare Systems of Equations A.2.4 The Geometry of Linear Systems A.2.5 Numerical Issues A.2.6 Iterative Methods for Solving Linear Systems A.3 Matrices A.3.1 Some Special Matrices A.3.2 Elementary Row Matrices A.3.3 Inverse Matrices A.3.4 Properties of Inverses A.3.5 Construction of Inverses A.3.6 LU Decomposition A.4 Vector Spaces A.4.1 Definition of a Vector Space A.4.2 Linear Combinations, Spans, and Subspaces A.4.3 Linear Independence and Bases A.4.4 Inner Products, Length, Orthogonality, and Projection A.4.5 Dot Product, Cross Product, and Triple Products A.4.6 Orthogonal Subspaces A.4.7 The Fundamental Theorem of Linear Algebra A.4.8 Projection and Least Squares A.4.9 Linear Transformations A.5 Advanced Topics A.5.1 Determinants A.5.2 Eigenvalues and Eigenvectors A.5.3 Eigendecomposition for Symmetric Matrices A.5.4 S + N Decomposition A.5.5 Applications B Affine Algebra B.1 Introduction B.2 Coordinate Systems B.3 Subspaces B.4 Transformations B.5 Barycentric Coordinates B.5.1 Triangles B.5.2 Tetrahedra B.5.3 Simplices B.5.4 Length, Area, Volume, and Hypervolume C Calculus C.1 Univariate Calculus C.1.1 Limits C.1.2 Limits of a Sequence C.1.3 Continuity C.1.4 Differentiation C.1.5 L'Hôpital's Rule C.1.6 Integration C.2 Multivariate Calculus C.2.1 Limits and Continuity C.2.2 Differentiation C.2.3 Integration C.3 Applications C.3.1 Optimization C.3.2 Constrained Optimization C.3.3 Derivative Approximations by Finite Differences D Ordinary Difference Equations D.1 Definitions D.2 Linear Equations D.2.1 First-Order Linear Equations D.2.2 Second-Order Linear Equations D.3 Constant Coefficient Equations D.4 Systems of Equations Bibliography Index

About the Author :
Dave Eberly is the president of Geometric Tools, Inc. (www.geometrictools.com), a company that specializes in software development for computer graphics, image analysis, and numerical methods. Previously, he was the director of engineering at Numerical Design Ltd. (NDL), the company responsible for the real-time 3D game engine, NetImmerse. He also worked for NDL on Gamebryo, which was the next-generation engine after NetImmerse. His background includes a BA degree in mathematics from Bloomsburg University, MS and PhD degrees in mathematics from the University of Colorado at Boulder, and MS and PhD degrees in computer science from the University of North Carolina at ChapelHill. He is the author of 3D Game Engine Design, 2nd Edition (2006), 3D Game Engine Architecture (2005), Game Physics (2004), and coauthor with Philip Schneider of Geometric Tools for Computer Graphics (2003), all published by Morgan Kaufmann. As a mathematician, Dave did research in the mathematics of combustion, signal and image processing, and length-biased distributions in statistics. He was an associate professor at the University of Texas at San Antonio with an adjunct appointment in radiology at the U.T. Health Science Center at San Antonio. In 1991, he gave up his tenured position to re-train in computer science at the University of North Carolina. After graduating in 1994, he remained for one year as a research associate professor in computer science with a joint appointment in the Department of Neurosurgery, working in medical image analysis. His next stop was the SAS Institute, working for a year on SAS/Insight, a statistical graphics package. Finally, deciding that computer graphics and geometry were his real calling, Dave went to work for NDL (which is now Emergent Game Technologies), then to Magic Software, Inc., which later became Geometric Tools, Inc. Dave's participation in the newsgroup comp.graphics.algorit

Review :
"I keep at most a dozen reference texts within easy reach of my workstation computer. This book will replace two of them."-Ian Ashdown, President, byHeart Consultants Limited "Implementing physical simulations for real-time games is a complex task that requires a solid understanding of a wide range of concepts from the fields of mathematics and physics. Previously, the relevant information could only be gleaned through obscure research papers. Thanks to Game Physics, all this information is now available in a single, easily accessible volume. Dave has yet again produced a must-have book for game technology programmers everywhere." -Christer Ericson, Technology Lead, Sony Computer Entertainment "Game Physics is a comprehensive reference of physical simulation techniques relevant to games and also contains a clear presentation of the mathematical background concepts fundamental to most types of game programming. I wish I had this book years ago." -Naty Hoffman, Senior Software Engineer, Naughty Dog, Inc. "Eppur si muove . . . and yet it moves. From Galileo to game development, this book will surely become a standard reference for modeling movement." -Ian Ashdown, President, byHeart Consultants Limited "This is an excellent companion volume to Dave's earlier 3D Game Engine Design. It shares the approach and strengths of his previous book. He doesn't try to pare down to the minimum necessary information that would allow you to build something with no more than basic functionality. Instead, he gives you all you need to begin working on a professional-caliber system. He puts the concepts firmly in context with current, ongoing research, so you have plenty of guidance on where to go if you are inclined to add even more features on your own. This is not a cookbook-it's a concise presentation of all the basic concepts needed to understand and use physics in a modern game engine. It gives you a firm foundation you can use either to build a complete engine of your own or to understand what's going on inside the new powerful middleware physics engines available today. This book, especially when coupled with Dave's 3D Game Engine Design, provides the most complete resource of the mathematics relevant to modern 3D games that I can imagine. Along with clear descriptions of the mathematics and algorithms needed to create a powerful physics engine are sections covering pretty much all of the math you will encounter anywhere in the game-quaternions, linear algebra, and calculus." -Peter Lipson, Senior Programmer, Toys For Bob "This comprehensive introduction to the field of game physics will be invaluable to anyone interested in the increasingly more important aspect of video game production, namely, striving to achieve realism. Drawing from areas such as robotics, dynamic simulation, mathematical modeling, and control theory, this book succeeds in presenting the material in a concise and cohesive way. As a matter of fact, it can be recommended not only to video game professionals but also to students and practitioners of the above-mentioned disciplines." -Pål-Kristian Engstad, Senior Software Engineer, Naughty Dog, Inc. "Increases in processor power now make it feasible to run complex physical simulations in real time, which greatly increases their practical importance. Thus there is an increasing need for books like David Eberly's Game Physics that can give graphics programmers a grounding in the physical principles that underlie realistic computer animation." - W.Lewis Johnson --Physics Today