Essential Mathematics for Games and Interactive Applications: A Programmer's Guide

"Even though I've worked with these systems for years, I found new ways of looking at several topics that make them easier to remember and use. For someone new to 3D programming, it is extremely useful-it gives them a solid background in pretty much every area they need to understand." -Peter Lipson, Toys for Bob, Inc. Based on the authors' popular tutorials at the Game Developers Conference, Essential Mathematics for Games and Interactive Applications presents the core mathematics necessary for sophisticated 3D graphics and interactive physical simulations. The book begins with linear algebra and matrix manipulation and expands on this foundation to cover such topics as texture filtering, interpolation, animation, and basic game physics. Essential Mathematics focuses on the issues of 3D game development important to programmers and includes optimization guidance throughout.* Covers concepts in sufficient detail for a programmer to understand the foundations of 3D without feeling overwhelmed by proofs and theory *Companion CD-ROM with code examples built around a shared code base, including a math library covering all the topics presented in the book, a core vector/matrix math engine, and libraries to support basic 3D rendering and interaction *Provides guidance for students trying to understand how games are actually developed, including optimization techniques

Table of Contents:
Preface Introduction The (Continued) Rise of 3D Games How to Read this Book Part I Core Mathematics Part II Rendering Part III Animation Part IV Simulation Appendices Interactive Demo Applications Support Libraries Math Libraries Engine and Rendering Libraries References and Further Reading Part I Core Mathematics Chapter 1 Vectors and Points 1.1 Introduction 1.2 Vectors 1.2.1 Vectors as Geometry 1.2.2 Real Vector Spaces 1.2.3 Linear Combinations and Basis Vectors 1.2.4 Basic Vector Class Implementation 1.2.5 Vector Length 1.2.6 Dot Product 1.2.7 Gram-Schmidt Orthogonalization 1.2.8 Cross Product 1.2.9 Triple Products 1.3 Points 1.3.1 Points as Geometry 1.3.2 Affine Spaces 1.3.3 Affine Combinations 1.3.4 Point Implementation 1.3.5 Polar and Spherical Coordinates 1.4 Lines 1.4.1 Definition 1.4.2 Parameterized Lines 1.4.3 Generalized Line Equation 1.4.4 Collinear Points 1.5 Planes 1.5.1 Parameterized Planes 1.5.2 Generalized Plane Equation 1.5.3 Coplanar Points 1.6 Polygons and Triangles 1.7 Chapter Summary Chapter 2 Linear Transformations and Matrices 2.1 Introduction 2.2 Linear Transformations 2.2.1 Definitions 2.2.2 Null Space and Range 2.2.3 Linear Transformations and Basis Vectors 2.3 Matrices 2.3.1 Introduction to Matrices 2.3.2 Simple Operations 2.3.3 Vector Representation 2.3.4 Block Matrices 2.3.5 Matrix Product 2.3.6 Transforming Vectors 2.3.7 Combining Linear Transformations 2.3.8 Identity Matrix 2.3.9 Performing Vector Operations with Matrices 2.3.10 Implementation 2.4 Systems of Linear Equations 2.4.1 Definition 2.4.2 Solving Linear Systems 2.4.3 Gaussian Elimination 2.5 Matrix Inverse 2.5.1 Definition 2.5.2 Simple Inverses 2.6 The Determinant 2.6.1 Definition 2.6.2 Computing the Determinant 2.6.3 Determinants and Elementary Row Operations 2.6.4 Adjoint Matrix and Inverse 2.7 Chapter Summary Chapter 3 Affine Transformations 3.1 Introduction 3.2 Affine Transformations 3.2.1 Definition 3.2.2 Representation 3.3 Standard Affine Transformations 3.3.1 Translation 3.3.2 Rotation 3.3.3 Scaling 3.3.4 Reflection 3.3.5 Shear 3.3.6 Applying an Affine Transformation Around an Arbitrary Point 3.3.7 Transforming Plane Normals 3.4 Using Affine Transformations 3.4.1 Manipulation of Game Objects 3.4.2 Matrix Decomposition 3.4.3 Avoiding Matrix Decomposition 3.5 Object Hierarchies and Scene Graphs 3.5.1 Object Hierarchies 3.5.2 Scene Graphs 3.6 Chapter Summary Chapter 4 Real-World Computer Number Representation 4.1 Introduction 4.2 Representing Integral Types on a Computer 4.2.1 Finiteness of Representation 4.2.2 Range 4.3 Representing Real Numbers 4.3.1 Approximations 4.3.2 Precision and Error 4.4 Fixed Point 4.4.1 Introduction 4.4.2 Basic Representation 4.4.3 Range and Precision 4.4.4 Addition and Subtraction 4.4.5 Multiplication 4.4.6 Division 4.4.7 Real-World Fixed Point 4.4.8 Intermediate Value Overflow and Underflow 4.4.9 Limits of Fixed Point 4.4.10 Fixed Point Summary 4.5 Floating-Point Numbers 4.5.1 Review: Scientific Notation 4.5.2 A Restricted Scientific Notation 4.6 Binary "Scientific Notation" 4.7 IEEE Floating Point Standard 4.7.1 Basic Representation 4.7.2 Range and Precision 4.7.3 Arithmetic Operations 4.7.4 Special Values 4.7.5 Very Small Values 4.7.6 Catastrophic Cancellation 4.7.7 Double Precision 4.8 Real-World Floating Point 4.8.1 Internal FPU Precision 4.8.2 Performance 4.8.3 IEEE Specification Compliance 4.9 Code 4.10 Chapter Summary Part II Rendering Chapter 5 Viewing and Projection 5.1 Introduction 5.2 The View Frame and View Transformation 5.2.1 Defining a Virtual Camera 5.2.2 Controlling the Camera 5.2.3 Constructing the View Transformation 5.3 Projective Transformation 5.3.1 Definition 5.3.2 The View Frustum 5.3.3 Normalized Device Coordinates 5.3.4 Homogeneous Coordinates 5.3.5 Perspective Projection 5.3.6 Oblique Perspective 5.3.7 Orthographic Parallel Projection 5.3.8 Oblique Parallel Projection 5.4 Culling and Clipping 5.4.1 Why Cull or Clip? 5.4.2 Culling 5.4.3 General Plane Clipping 5.4.4 Homogeneous Clipping 5.5 Screen Transformation 5.6 Picking 5.7 Management of Viewing Transformations 5.8 Chapter Summary Chapter 6 Geometry, Shading, and Texturing 6.1 Introduction 6.2 Color Representation 6.2.1 The RGB Color Model 6.2.2 Colors as "Vectors" 6.2.3 Operations on Colors 6.2.4 Color Range Limitation 6.2.5 Alpha Values 6.2.6 Color Storage Formats 6.2.7 Colors in OpenGL 6.3 Points and Vertices 6.3.1 Per-Vertex Attributes 6.4 Surface Representation 6.4.1 Vertices and Surface Ambiguity 6.4.2 Triangles 6.4.3 Triangle Attributes 6.4.4 Vertex Indices 6.4.5 OpenGL Vertex Indices 6.5 Coloring a Surface 6.6 Using Constant Colors 6.6.1 Per-Object Colors 6.6.2 Per-Triangle Colors 6.6.3 Per-Vertex Colors 6.6.4 Limitations of Basic Shading Methods 6.7 Texture Mapping 6.7.1 Introduction 6.7.2 Shading via Image Lookup 6.7.3 Texture Images 6.8 Texture Coordinates 6.8.1 Mapping Texture Coordinates 6.8.2 Generating Texture Coordinates 6.8.3 Texture Coordinate Discontinuities 6.8.4 Mapping Outside the Unit Square 6.9 Reviewing the Steps of Texturing 6.10 Limitations of Texturing 6.11 Procedural Colors and Shaders 6.12 Chapter Summary Chapter 7 Lighting 7.1 Introduction 7.2 Basics of Light Approximation 7.2.1 Measuring Light 7.2.2 Light as a Ray 7.3 Lighting Approximation (OpenGL) 7.4 Types of Light Sources 7.4.1 Directional Lights 7.4.2 Point Lights 7.4.3 Spotlights 7.4.4 Other Types of Light Sources 7.5 Surface Materials and Light Interaction 7.5.1 OpenGL Materials 7.6 Categories of Light 7.6.1 Emission 7.6.2 Ambient 7.6.3 Diffuse 7.6.4 Specular 7.7 Combined Lighting Equation 7.8 Lighting and Shading 7.8.1 Flat-Shaded Lighting 7.8.2 Per-Vertex Lighting 7.8.3 Per-Pixel Lighting (Phong Shading) 7.9 Merging Textures and Lighting 7.9.1 Specular Lighting and Textures 7.10 Lighting and Programmable Shaders 7.11 Chapter Summary Chapter 8 Rasterization 8.1 Introduction 8.2 Displays and Framebuffers 8.2.1 Framebuffer Memory Organization 8.2.2 Interlacing 8.2.3 Multiple Buffers 8.3 Conceptual Rasterization Pipeline 8.4 Determining the Pixels Contained by a Triangle 8.5 Determining Which Pixels are Visible 8.5.1 Depth Sorting 8.5.2 Depth Buffering 8.5.3 Depth Buffering in OpenGL 8.6 Computing Source Pixel Colors 8.6.1 Flat Colors 8.6.2 Gouraud Colors 8.7 Rasterizing Textures 8.7.1 Texture Coordinate Review 8.7.2 Interpolating Texture Coordinates 8.7.3 Mapping a Coordinate to a Texel 8.7.4 Mipmapping 8.8 Blending 8.8.1 Blending and Z-Buffering 8.8.2 Alternative Blending Modes 8.8.3 Blending and OpenGL 8.9 Antialiasing 8.9.1 Antialiasing in Practice 8.9.2 Antialiasing in OpenGL 8.10 Chapter Summary Part III Animation Chapter 9 Curves 9.1 Introduction 9.2 General Definitions 9.3 Linear Interpolation 9.3.1 Definition 9.3.2 Piecewise Linear Interpolation 9.4 Lagrange Polynomials 9.5 Hermite Curves 9.5.1 Definition 9.5.2 Automatic Generation of Hermite Curves 9.5.3 Natural, Cyclic, and Acyclic End Conditions 9.6 Catmull-Rom Splines 9.7 Bézier Curves 9.7.1 Definition 9.7.2 Piecewise Bézier Curves 9.8 B-Splines 9.9 Rational Curves 9.10 Rendering Curves 9.10.1 Forward Differencing 9.10.2 Midpoint Subdivision 9.10.3 Using OpenGL 9.11 Controlling Speed Along a Curve 9.11.1 Moving at Constant Speed 9.11.2 Computing Arc Length 9.11.3 Ease-In and Ease-Out 9.12 Camera Control 9.13 Chapter Summary Chapter 10 Orientation Representation 10.1 Introduction 10.2 Rotation Matrices 10.3 Fixed and Euler Angles 10.3.1 Definition 10.3.2 Format Conversion 10.3.3 Concatenation 10.3.4 Vector Rotation 10.3.5 Other Issues 10.4 Axis-Angle Representation 10.4.1 Definition 10.4.2 Format Conversion 10.4.3 Concatenation 10.4.4 Vector Rotation 10.4.5 Section Summary 10.5 Quaternions 10.5.1 Definition 10.5.2 Rotation Quaternions 10.5.3 Format Conversion 10.5.4 Addition and Scalar Multiplication 10.5.5 Negation 10.5.6 Magnitude and Normalization 10.5.7 Dot Product 10.5.8 Concatenation 10.5.9 Identity and Inverse 10.5.10 Vector Rotation 10.5.11 Quaternions and Transformations 10.6 Interpolation 10.6.1 Linear Interpolation 10.6.2 Spherical Linear Interpolation 10.6.3 Performance Improvements 10.7 Chapter Summary Part IV Simulation Chapter 11 Intersection Testing 11.1 Introduction 11.2 Closest Point and Distance Tests 11.2.1 Closest Point on Line to Point 11.2.2 Line-Point Distance 11.2.3 Closest Point on Line Segment to Point 11.2.4 Line Segment-Point Distance 11.2.5 Closest Points between Two Lines 11.2.6 Line-Line Distance 11.2.7 Closest Points between Two Line Segments 11.2.8 Line Segment-Line Segment Distance 11.2.9 General Linear Components 11.3 Object Intersection 11.3.1 Spheres 11.3.2 Axis-Aligned Bounding Boxes 11.3.3 Swept Spheres 11.3.4 Object-Oriented Boxes 11.3.5 Triangles 11.4 A Simple Collision System 11.4.1 Choosing a Base Primitive 11.4.2 Bounding Hierarchies 11.4.3 Dynamic Objects 11.4.4 Performance Improvements 11.4.5 Related Systems 11.4.6 Section Summary 11.5 Chapter Summary Chapter 12 Rigid Body Dynamics 12.1 Introduction 12.2 Linear Dynamics 12.2.1 Moving with Constant Acceleration 12.2.2 Forces 12.2.3 Linear Momentum 12.2.4 Moving with Variable Acceleration 12.3 Initial Value Problems 12.3.1 Definition 12.3.2 Euler's Method 12.3.3 Midpoint Method 12.3.4 Higher-Order Methods 12.3.5 Verlet Integration 12.3.6 Implicit Methods 12.4 Rotational Dynamics 12.4.1 Definitions 12.4.2 Orientation and Angular Velocity 12.4.3 Torque 12.4.4 Angular Momentum and Inertial Tensor 12.4.5 Integrating Rotational Quantities 12.5 Collision Response 12.5.1 Locating the Point of Collision 12.5.2 Linear Collision Response 12.5.3 Rotational Collision Response 12.5.4 Other Response Techniques 12.6 Efficiency 12.7 Chapter Summary Appendix A Trigonometry Review A.1 Basic Definitions A.1.1 Ratios on the Right Triangle A.1.2 Extending to General Angles A.2 Properties of Triangles A.3 Trigonometric Identities A.3.1 Pythagorean Identities A.3.2 Complementary Angle A.3.3 Even-Odd A.3.4 Compound Angle A.3.5 Double Angle A.3.6 Half Angle A.4 Inverses Appendix B Calculus Review B.1 Limits and Continuity B.1.1 Limits B.1.2 Continuity B.2 Derivatives B.2.1 Definition B.2.2 Basic Derivatives B.2.3 Derivatives of Transcendental Functions B.2.4 Taylor's Series B.3 Integrals B.3.1 Definition B.3.2 Evaluating Integrals B.3.3 Trapezoidal Rule B.3.4 Gaussian Quadrature B.4 Space Curves Bibliography Index Trademarks About the CD-ROM

About the Author :
James M. Van Verth is a founding member of Red Storm Entertainment, a division of Ubisoft, where he has been a lead engineer for nine years. For the past eight years he has also been a regular speaker at the Game Developers Conferences, teaching the all-day tutorial "Math for Game Programmers,” on which this book is based. He has a B.A. in mathematics and computer science from Dartmouth College and M.S. degrees in computer science from the State University of New York at Buffalo and the University of North Carolina at Chapel Hill. Lars M. Bishop is an engineer in the Handheld Developer Technologies group at NVIDIA. Prior to joining NVIDIA, Lars was the Chief Technology Officer at Numerical Design Limited, leading the development of the Gamebryo3D cross-platform game engine. He received a BS in Math/Computer Science from Brown University and an MS in Computer Science from the University of North Carolina at Chapel Hill. His outside interests include photography, drumming, and playing bass guitar.

Review :
"Not only is it an excellent introduction for someone who needs to come up-to-speed on the math behind games and graphics, it's a well-organized reference for anyone in the field. Short version: If you program graphics, let alone games, you need this book. Shelve it near your desk, next to your Foley and your Knuth. Highly Recommended." -Rick Wayne from a review in Software Development Magazine "This excellent volume is unique in that it covers not only the basic techniques of computer graphics and game development, but also provides a thorough and rigorous--yet very readable--treatment of the underlying mathematics. Fledgling graphics and games developers will find it a valuable introduction; experienced developers will find it an invaluable reference. Everything is here, from the detailed numeric issues of IEEE floating point notation, to the correct way to use quaternions and spherical linear interpolation to represent orientation, to the mathematics of collision detection and rigid-body dynamics." -David Luebke, University of Virginia, co-author of Level of Detail for 3D Graphics "When it comes to software development for games or virtual reality, you cannot escape the mathematics. The best performance comes not from superfast processors and terabytes of memory, but from well-chosen algorithms. With this in mind, the techniques most useful for developing production-quality computer graphics for Hollywood blockbusters are not the best choice for interactive applications. When rendering times are measured in milliseconds rather than hours, you need an entirely different perspective. Essential Mathematics for Games and Interactive Applications provides this perspective. While the mathematics are rigorous and perhaps challenging at times, Van Verth and Bishop provide the context for understanding the algorithms and data structures needed to bring games and VR applications to life. This may not be the only book you will ever need for games and VR software development, but it will certainly provide an excellent framework for developing robust and fast applications." -Ian Ashdown, President, ByHeart Consultants Limited "With Essential Mathematics for Games and Interactive Applications, Van Verth and Bishop have provided invaluable assistance for professional game developers looking to shore up weaknesses in their mathematical training. Even if you never intend to write a renderer or tune a physics engine, this book provides the mathematical and conceptual grounding needed to understand many of the key concepts in rendering, simulation, and animation." -Dave Weinstein, Red Storm Entertainment "Geometry, trigonometry, linear algebra, and calculus are all essential tools for 3D graphics. Mathematics courses in these subjects cover too much ground, while at the same time glossing over the bread-and-butter essentials for 3D graphics programmers. In Essential Mathematics for Games and Interactive Applications, Van Verth and Bishop bring just the right level of mathematics out of the trenches of professional game development. This book provides an accessible and solid mathematical foundation for interactive graphics programmers. If you are working in the area of 3D games, this book is a 'must have.'" -Jonathan Cohen, Department of Computer Science, Johns Hopkins University, co-author of Level of Detail for 3D Graphics