Essential Mathematics for Games and Interactive Applications

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.

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