Essential Mathematics for Games and Interactive Applications

Front Cover
Dedication
Contents
Preface
The Adventure Begins
The Adventure Continues
The Adventurers Resume the Quest
Those Who Helped Us along the Road
Authors
Introduction
The (Continued) Rise of 3D Games
How to Read This Book
Interactive Demo Applications and Support Libraries
Supplementary Material
References and Further Reading
Chapter 1. Representing Real Numbers
1.1 Introduction
1.2 Preliminary Concepts
1.2.1 Fixed-Point Numbers
1.2.2 Approximations
1.2.3 Precision and Error
1.3 Floating-Point Numbers
1.3.1 Review: Scientific Notation
1.3.2 Restricted Scientific Notation
1.3.3 Binary Scientific Notation
1.4 IEEE 754 Floating-Point Standard
1.4.1 Basic Representation
1.4.2 Range and Precision
1.4.3 Arithmetic Operations
1.4.4 Special Values
1.4.5 Very Small Values
1.4.6 Catastrophic Cancelation
1.4.7 Comparing Floating-Point Numbers
1.4.8 Double Precision
1.4.9 Half Precision
1.5 Real-World Floating Point
1.5.1 Internal FPU Precision
1.5.2 Performance
1.5.3 IEEE Specification Compliance
1.5.4 Precision in Graphics Processing Units
1.6 Code
1.7 Chapter Summary
Chapter 2. Vectors and Points
2.1 Introduction
2.2 Vectors
2.2.1 Geometric Vectors
2.2.2 Real Vector Spaces
2.2.3 Linear Combinations and Basis Vectors
2.2.4 Basic Vector Class Implementation
2.2.5 Vector Length
2.2.6 Dot Product
2.2.7 Gram–Schmidt Orthogonalization
2.2.8 Cross Product
2.2.9 Triple Products
2.2.10 Grassman Algebra
2.3 Points
2.3.1 Points as Geometry
2.3.2 Affine Spaces
2.3.3 Affine Combinations
2.3.4 Point Implementation
2.3.5 Polar and Spherical Coordinates
2.4 Lines
2.4.1 Definition
2.4.2 Parameterized Lines
2.4.3 Generalized Line Equation
2.4.4 Collinear Points
2.5 Planes
2.5.1 Parameterized Planes
2.5.2 Generalized Plane Equation
2.5.3 Coplanar Points
2.6 Polygons and Triangles
2.7 Chapter Summary
Chapter 3. Linear Transformations and Matrices
3.1 Introduction
3.2 Linear Transformations
3.2.1 Definitions
3.2.2 Linear Transformations and Basis Vectors
3.2.3 Range and Null Space
3.3 Matrices
3.3.1 Introduction to Matrices
3.3.2 Simple Operations
3.3.3 Vector Representation
3.3.4 Block Matrices
3.3.5 Matrix Product
3.3.6 Transforming Vectors
3.3.7 Combining Linear Transformations
3.3.8 Identity Matrix
3.3.9 Performing Vector Operations with Matrices
3.3.10 Implementation
3.4 Systems of Linear Equations
3.4.1 Definition
3.4.2 Solving Linear Systems
3.4.3 Gaussian Elimination
3.5 Matrix Inverse
3.5.1 Definition
3.5.2 Simple Inverses
3.6 Determinant
3.6.1 Definition
3.6.2 Computing the Determinant
3.6.3 Determinants and Elementary Row Operations
3.6.4 Adjoint Matrix and Inverse
3.7 Eigenvalues and Eigenvectors
3.8 Chapter Summary
Chapter 4. Affine Transformations
4.1 Introduction
4.2 Affine Transformations
4.2.1 Matrix Definition
4.2.2 Formal Definition
4.2.3 Formal Representation
4.3 Standard Affine Transformations
4.3.1 Translation
4.3.2 Rotation
4.3.3 Scaling
4.3.4 Reflection
4.3.5 Shear
4.3.6 Applying an Affine Transformation around an Arbitrary Point
4.3.7 Transforming Plane Normals
4.4 Using Affine Transformations
4.4.1 Manipulation of Game Objects
4.4.2 Matrix Decomposition
4.4.3 Avoiding Matrix Decomposition
4.5 Object Hierarchies
4.6 Chapter Summary
Chapter 5. Orientation Representation
5.1 Introduction
5.2 Rotation Matrices
5.3 Euler Angles
5.3.1 Definition
5.3.2 Format Conversion
5.3.3 Concatenation
5.3.4 Vector Rotation
5.3.5 Other Issues
5.4 Axis–Angle Representation
5.4.1 Definition
5.4.2 Format Conversion
5.4.3 Concatenation
5.4.4 Vector Rotation
5.4.5 Axis–Angle Summary
5.5 Quaternions
5.5.1 Definition
5.5.2 Quaternions as Rotations
5.5.3 Addition and Scalar Multiplication
5.5.4 Negation
5.5.5 Magnitude and Normalization
5.5.6 Dot Product
5.5.7 Format Conversion
5.5.8 Concatenation
5.5.9 Identity and Inverse
5.5.10 Vector Rotation
5.5.11 Shortest Path of Rotation
5.5.12 Quaternions and Transformations
5.6 Chapter Summary
Chapter 6. Interpolation
6.1 Introduction
6.2 Interpolation of Position
6.2.1 General Definitions
6.2.2 Linear Interpolation
6.2.3 Hermite Curves
6.2.4 Catmull–Rom Splines
6.2.5 Kochanek–Bartels Splines
6.2.6 Bézier Curves
S
6.2.7 Other Curve Types
6.3 Interpolation of Orientation
6.3.1 General Discussion
6.3.2 Linear Interpolation
6.3.3 Spherical Linear Interpolation
6.3.4 Performance Improvements
6.4 Sampling Curves
6.4.1 Forward Differencing
6.4.2 Midpoint Subdivision
6.4.3 Computing Arc Length
6.5 Controlling Speed along a Curve
6.5.1 Moving at Constant Speed
6.5.2 Moving at Variable Speed
6.6 Camera Control
6.7 Chapter Summary
Chapter 7, Viewing and Projection
7.1 Introduction
7.2 View Frame and View Transformation
7.2.1 Defining a Virtual Camera
7.2.2 Constructing the View-to-World Transformation
7.2.3 Controlling the Camera
7.2.4 Constructing the World-to-View Transformation
7.3 Projective Transformation
7.3.1 Definition
7.3.2 Normalized Device Coordinates
7.3.3 View Frustum
7.3.4 Homogeneous Coordinates
7.3.5 Perspective Projection
7.3.6 Oblique Perspective
7.3.7 Orthographic Parallel Projection
7.3.8 Oblique Parallel Projection
7.4 Culling and Clipping
7.4.1 Why Cull or Clip?
7.4.2 Culling
7.4.3 General Plane Clipping
7.4.4 Homogeneous Clipping
7.4.5 Extracting Clip Planes
7.5 Screen Transformation
7.5.1 Pixel Aspect Ratio
7.6 Picking
7.7 Management of Viewing Transformations
7.8 Chapter Summary
Chapter 8. Geometry and Programmable Shading
8.1 Introduction
8.2 Color Representation
8.2.1 RGB Color Model
8.2.2 Colors as “Points”
8.2.3 Color-Range Limitation
8.2.4 Operations on Colors
8.2.5 Alpha Values
8.2.6 Remapping Colors into the Unit Cube
8.2.7 Color Storage Formats
8.2.8 Nonlinear Color
8.3 Points and Vertices
8.3.1 Per-Vertex Attributes
8.3.2 An Object's Vertices
8.4 Surface Representation
8.4.1 Vertices and Surface Ambiguity
8.4.2 Triangles
8.4.3 Connecting Vertices into Triangles
8.4.4 Drawing Geometry
8.5 Rendering Pipeline
8.5.1 Fixed-Function versus Programmable Pipelines
8.6 Shaders
8.6.1 Using Shaders to Move from Vertex to Triangle to Fragment
8.6.2 Shader Input and Output Values
8.6.3 Shader Operations and Language Constructs
8.6.4 Other Shader Types
8.7 Vertex Shaders
8.7.1 Vertex Shader Inputs
8.7.2 Vertex Shader Outputs
8.7.3 Basic Vertex Shaders
8.8 Fragment Shaders
8.8.1 Fragment Shader Inputs
8.8.2 Fragment Shader Outputs
8.8.3 Linking Vertex and Fragment Shaders
8.8.4 Compiling, Linking, and Using Shaders
8.8.5 Setting Uniform Values
8.9 Basic Coloring Methods
8.9.1 Per-Object Colors
8.9.2 Per-Triangle Colors
8.9.3 Per-Vertex Colors
8.9.4 Sharp Edges and Vertex Colors
8.9.5 Limitations of Basic Shading Methods
8.10 Texture Mapping
8.10.1 Introduction
8.10.2 Shading via Image Lookup
8.10.3 Texture Images
8.10.4 Texture Samplers
8.11 Texture Coordinates
8.11.1 Mapping Texture Coordinates onto Objects
8.11.2 Generating Texture Coordinates
8.11.3 Texture Coordinate Discontinuities
8.11.4 Mapping Outside the Unit Square
8.11.5 Texture Samplers in Shader Code
8.12 Steps of Texturing
8.12.1 Other Forms of Texture Coordinates
8.12.2 From Texture Coordinates to a Texture Sample Color
8.13 Limitations of Static Shading
8.14 Chapter Summary
Chapter 9. Lighting
9.1 Introduction
9.2 Basics of Light Approximation
9.3 Measuring Light
9.4 Types of Light Sources
9.4.1 Point Lights
9.4.2 Spotlights
9.4.3 Directional Lights
9.4.4 Ambient Lights
9.4.5 Other Types of Light Sources
9.5 Surface Materials and Light Interaction
9.5.1 Diffuse
9.5.2 Specular
9.5.3 Emission
9.5.4 Ambient
9.5.5 Combined Lighting Equation
9.6 Lighting and Shading
9.6.1 Flat-Shaded Lighting
9.6.2 Per-Vertex Lighting
9.6.3 Per-Fragment Lighting
9.7 Textures and Lighting
9.7.1 Basic Modulation
9.7.2 Specular Lighting and Textures
9.7.3 Textures as Materials
9.8 Advanced Lighting
9.8.1 Normal Mapping
9.8.2 Reflective Objects
9.8.3 Transparent Objects
9.8.4 Area Lights
9.8.5 Physically Based Lighting
9.8.6 High Dynamic Range Lighting
9.8.7 Deferred Lighting and Shading
9.8.8 Shadows
9.9 Chapter Summary
10.1 Introduction
10.2 Displays and Framebuffers
10.3 Conceptual Rasterization Pipeline
10.3.1 Rasterization Stages
10.4 Determining the Fragments: Pixels Covered
by a Triangle
10.4.1 Fragments
10.4.2 Depth Complexity
10.4.3 Converting Triangles to Fragments
10.4.4 Handling Partial Fragments
10.5 Determining Visible Geometry
10.5.1 Depth Buffering
10.5.2 Depth Buffering in Practice
10.6 Computing Fragment Shader Inputs
10.6.1 Uniform Values
10.6.2 Per-Vertex Attributes
10.6.3 Indirect Per-Fragment Values
10.7 Rasterizing Textures
10.7.1 Texture Coordinate Review
10.7.2 Mapping a Coordinate to a Texel
10.7.3 Mipmapping
10.8 From Fragments to Pixels
10.8.1 Pixel Blending
10.8.2 Antialiasing
10.8.3 Antialiasing in Practice
10.9 Chapter Summary
11.1 Introduction
11.2 Probability
11.2.1 Basic Probability
11.2.2 Random Variables
11.2.3 Mean and Standard Deviation
11.2.4 Special Probability Distributions
11.3 Determining Randomness
11.3.1 Chi-Square Test
11.3.2 Spectral Test
11.4 Random Number Generators
11.4.1 Linear Congruential Methods
11.4.2 Lagged Fibonacci Methods
11.4.3 Carry Methods
11.4.4 Xorshift
11.4.5 Other Alternatives
11.4.6 Setting Initial State
11.4.7 Conclusions
11.5 Special Applications
11.5.1 Integers and Ranges of Integers
11.5.2 Floating-Point Numbers
11.5.3 Shuffling
11.5.4 Nonuniform Distributions
11.5.5 Spherical Sampling
11.5.6 Disc Sampling
11.5.7 Noise and Turbulence
11.6 Chapter Summary
12.1 Introduction
12.2 Closest Point and Distance Tests
12.2.1 Closest Point on Line to Point
12.2.2 Line–Point Distance
12.2.3 Closest Point on Line Segment to Point
12.2.4 Line Segment–Point Distance
12.2.5 Closest Points between Two Lines
12.2.6 Line–Line Distance
12.2.7 Closest Points between Two Line Segments
12.2.8 Line Segment–Line Segment Distance
12.2.9 General Linear Components
12.3 Object Intersection
12.3.1 Spheres
12.3.2 Axis-Aligned Bounding Boxes
12.3.3 Swept Spheres
12.3.4 Object-Oriented Boxes
12.3.5 Triangles
12.4 A Simple Collision System
12.4.1 Choosing a Base Primitive
12.4.2 Bounding Hierarchies
12.4.3 Dynamic Objects
12.4.4 Performance Improvements
12.4.5 Related Systems
12.4.6 Section Summary
12.5 Chapter Summary
13.1 Introduction
13.2 Linear Dynamics
13.2.1 Moving with Constant Acceleration
13.2.2 Forces
13.2.3 Linear Momentum
13.2.4 Moving with Variable Acceleration
13.3 Numerical Integration
13.3.1 Definition
13.3.2 Euler's Method
13.3.3 Runge–Kutta Methods
13.3.4 Verlet Integration
13.3.5 Implicit Methods
13.3.6 Semi-Implicit Methods
13.4 Rotational Dynamics
13.4.1 Definition
13.4.2 Orientation and Angular Velocity
13.4.3 Torque
13.4.4 Angular Momentum and Inertia Tensor
13.4.5 Integrating Rotational Quantities
13.5 Collision Response
13.5.1 Contact Generation
13.5.2 Linear Collision Response
13.5.3 Rotational Collision Response
13.5.4 Extending the System
13.6 Efficiency
13.7 Chapter Summary
Chapter 10. Rasterization
10.1 Introduction
10.2 Displays and Framebuffers
10.3 Conceptual Rasterization Pipeline
10.3.1 Rasterization Stages
10.4 Determining the Fragments: Pixels Covered
by a Triangle
10.4.1 Fragments
10.4.2 Depth Complexity
10.4.3 Converting Triangles to Fragments
10.4.4 Handling Partial Fragments
10.5 Determining Visible Geometry
10.5.1 Depth Buffering
10.5.2 Depth Buffering in Practice
10.6 Computing Fragment Shader Inputs
10.6.1 Uniform Values
10.6.2 Per-Vertex Attributes
10.6.3 Indirect Per-Fragment Values
10.7 Rasterizing Textures
10.7.1 Texture Coordinate Review
10.7.2 Mapping a Coordinate to a Texel
10.7.3 Mipmapping
10.8 From Fragments to Pixels
10.8.1 Pixel Blending
10.8.2 Antialiasing
10.8.3 Antialiasing in Practice
10.9 Chapter Summary
Chapter 11. Random Numbers
11.1 Introduction
11.2 Probability
11.2.1 Basic Probability
11.2.2 Random Variables
11.2.3 Mean and Standard Deviation
11.2.4 Special Probability Distributions
11.3 Determining Randomness
11.3.1 Chi-Square Test
11.3.2 Spectral Test
11.4 Random Number Generators
11.4.1 Linear Congruential Methods
11.4.2 Lagged Fibonacci Methods
11.4.3 Carry Methods
11.4.4 Xorshift
11.4.5 Other Alternatives
11.4.6 Setting Initial State
11.4.7 Conclusions
11.5 Special Applications
11.5.1 Integers and Ranges of Integers
11.5.2 Floating-Point Numbers
11.5.3 Shuffling
11.5.4 Nonuniform Distributions
11.5.5 Spherical Sampling
11.5.6 Disc Sampling
11.5.7 Noise and Turbulence
11.6 Chapter Summary
Chapter 12. Intersection Testing
12.1 Introduction
12.2 Closest Point and Distance Tests
12.2.1 Closest Point on Line to Point
12.2.2 Line–Point Distance
12.2.3 Closest Point on Line Segment to Point
12.2.4 Line Segment–Point Distance
12.2.5 Closest Points between Two Lines
12.2.6 Line–Line Distance
12.2.7 Closest Points between Two Line Segments
12.2.8 Line Segment–Line Segment Distance
12.2.9 General Linear Components
12.3 Object Intersection
12.3.1 Spheres
12.3.2 Axis-Aligned Bounding Boxes
12.3.3 Swept Spheres
12.3.4 Object-Oriented Boxes
12.3.5 Triangles
12.4 A Simple Collision System
12.4.1 Choosing a Base Primitive
12.4.2 Bounding Hierarchies
12.4.3 Dynamic Objects
12.4.4 Performance Improvements
12.4.5 Related Systems
12.4.6 Section Summary
12.5 Chapter Summary
Chapter 13. Rigid-Body Dynamics
13.1 Introduction
13.2 Linear Dynamics
13.2.1 Moving with Constant Acceleration
13.2.2 Forces
13.2.3 Linear Momentum
13.2.4 Moving with Variable Acceleration
13.3 Numerical Integration
13.3.1 Definition
13.3.2 Euler's Method
13.3.3 Runge–Kutta Methods
13.3.4 Verlet Integration
13.3.5 Implicit Methods
13.3.6 Semi-Implicit Methods
13.4 Rotational Dynamics
13.4.1 Definition
13.4.2 Orientation and Angular Velocity
13.4.3 Torque
13.4.4 Angular Momentum and Inertia Tensor
13.4.5 Integrating Rotational Quantities
13.5 Collision Response
13.5.1 Contact Generation
13.5.2 Linear Collision Response
13.5.3 Rotational Collision Response
13.5.4 Extending the System
13.6 Efficiency
13.7 Chapter Summary
References
Back Cover