Mathematics for 3D Game Programming
and Computer Graphics, Third Edition

By Eric Lengyel
ISBN-13: 978-1-4354-5886-4
Hardcover · Full Color · 563 Pages
Cengage Learning © 2011

Purchase at Amazon.com


BOOK DESCRIPTION

This updated third edition illustrates the mathematical concepts that a game developer needs to develop 3D computer graphics and game engines at the professional level. It starts at a fairly basic level in areas such as vector geometry and linear algebra, and then progresses to more advanced topics in 3D programming such as illumination and visibility determination. Particular attention is given to derivations of key results, ensuring that the reader is not forced to endure gaps in the theory. The book assumes a working knowledge of trigonometry and calculus, but also includes sections that review the important tools used from these disciplines, such as trigonometric identities, differential equations, and Taylor series.

ABOUT THE AUTHOR

Eric Lengyel is a veteran of the computer games industry with over 18 years of experience writing game engines. He has a PhD in Computer Science from the University of California at Davis and an MS in Mathematics from Virginia Tech. Eric is the founder of Terathon Software, where he is currently working on a Halloweeen-themed game called The 31st.

TABLE OF CONTENTS

Preface
What's New in the Third Edition
Contents Overview
Notational Conventions

Chapter 1: The Rendering Pipeline
1.1 Graphics Processors
1.2 Vertex Transformation
1.3 Rasterization and Fragment Operations

Chapter 2: Vectors
2.1 Vector Properties
2.2 Dot Products
2.3 Cross Products
2.4 Vector Spaces

Chapter 3: Matrices
3.1 Matrix Properties
3.2 Linear Systems
3.3 Matrix Inverses
3.4 Determinants
3.5 Eigenvalues and Eigenvectors
3.6 Diagonalization

Chapter 4: Transforms
4.1 Linear Transformations
    4.1.1 Orthogonal Matrices
    4.1.2 Handedness
4.2 Scaling Transforms
4.3 Rotation Transforms
    4.3.1 Rotation About an Arbitrary Axis
4.4 Homogeneous Coordinates
    4.4.1 Four-dimensional Transforms
    4.4.2 Points and Directions
    4.4.3 Geometrical Interpretation of the w-coordinate
4.5 Transforming Normal Vectors
4.6 Quaternions
    4.6.1 Quaternion Mathematics
    4.6.2 Rotations with Quaternions
    4.6.3 Spherical Linear Interpolation

Chapter 5: Geometry for 3D Engines
5.1 Lines in 3D Space
    5.1.1 Distance Between a Point and a Line
    5.1.2 Distance Between Two Lines
5.2 Planes in 3D Space
    5.2.1 Intersection of a Line and a Plane
    5.2.2 Intersection of Three Planes
    5.2.3 Transforming Planes
5.3 The View Frustum
    5.3.1 Field of View
    5.3.2 Frustum Planes
5.4 Perspective Correct Interpolation
    5.4.1 Depth Interpolation
    5.4.2 Vertex Attribute Interpolation
5.5 Projections
    5.5.1 Perspective Projections
    5.5.2 Orthographic Projections
    5.5.3 Extracting Frustum Planes
5.6 Reflections and Oblique Clipping

Chapter 6: Ray Tracing
6.1 Root Finding
    6.1.1 Quadratic Polynomials
    6.1.2 Cubic Polynomials
    6.1.3 Quartic Polynomials
    6.1.4 Newton’s Method
    6.1.5 Refinement of Reciprocals and Square Roots
6.2 Surface Intersections
    6.2.1 Intersection of a Ray and a Triangle
    6.2.2 Intersection of a Ray and a Box
    6.2.3 Intersection of a Ray and a Sphere
    6.2.4 Intersection of a Ray and a Cylinder
    6.2.5 Intersection of a Ray and a Torus
6.3 Normal Vector Calculation
6.4 Reflection and Refraction Vectors
    6.4.1 Reflection Vector Calculation
    6.4.2 Refraction Vector Calculation

Chapter 7: Lighting and Shading
7.1 RGB Color
7.2 Light Sources
    7.2.1 Ambient Light
    7.2.2 Directional Light Sources
    7.2.3 Point Light Sources
    7.2.4 Spot Light Sources
7.3 Diffuse Reflection
7.4 Specular Reflection
7.5 Texture Mapping
    7.5.1 Standard Texture Maps
    7.5.2 Projective Texture Maps
    7.5.3 Cube Texture Maps
    7.5.4 Filtering and Mipmaps
7.6 Emission
7.7 Shading Models
    7.7.1 Calculating Normal Vectors
    7.7.2 Gouraud Shading
    7.7.3 Blinn-Phong Shading
7.8 Bump Mapping
    7.8.1 Bump Map Construction
    7.8.2 Tangent Space
    7.8.3 Calculating Tangent Vectors
    7.8.4 Implementation
7.9 A Physical Reflection Model
    7.9.1 Bidirectional Reflectance Distribution Functions
    7.9.2 Cook-Torrance Illumination
    7.9.3 The Fresnel Factor
    7.9.4 The Microfacet Distribution Function
    7.9.5 The Geometrical Attenuation Factor
    7.9.6 Implementation

Chapter 8: Visibility Determination
8.1 Bounding Volume Construction
    8.1.1 Principal Component Analysis
    8.1.2 Bounding Box Construction
    8.1.3 Bounding Sphere Construction
    8.1.4 Bounding Ellipsoid Construction
    8.1.5 Bounding Cylinder Construction
8.2 Bounding Volume Tests
    8.2.1 Bounding Sphere Test
    8.2.2 Bounding Ellipsoid Test
    8.2.3 Bounding Cylinder Test
    8.2.4 Bounding Box Test
8.3 Spatial Partitioning
    8.3.1 Octrees
    8.3.2 Binary Space Partitioning Trees
8.4 Portal Systems
    8.4.1 Portal Clipping
    8.4.2 Reduced View Frustums

 Chapter 9: Polygonal Techniques
9.1 Depth Value Offset
    9.1.1 Projection Matrix Modification
    9.1.2 Offset Value Selection
    9.1.3 Implementation
9.2 Decal Application
    9.2.1 Decal Mesh Construction
    9.2.2 Polygon Clipping
9.3 Billboarding
    9.3.1 Unconstrained Quads
    9.3.2 Constrained Quads
    9.3.3 Polyboards
9.4 Polygon Reduction
9.5 T-Junction Elimination
9.6 Triangulation

Chapter 10: Shadows
10.1 Shadow Casting Set
10.2 Shadow Mapping
    10.2.1 Rendering the Shadow Map
    10.2.2 Rendering the Main Scene
    10.2.3 Self-Shadowing
10.3 Stencil Shadows
    10.3.1 Algorithm Overview
    10.3.2 Infinite View Frustums
    10.3.3 Silhouette Determination
    10.3.4 Shadow Volume Construction
    10.3.5 Determining Cap Necessity
    10.3.6 Rendering Shadow Volumes
    10.3.7 Scissor Optimization

Chapter 11: Curves and Surfaces
11.1 Cubic Curves
11.2 Hermite Curves
11.3 Bézier Curves
    11.3.1 Cubic Bézier Curves
    11.3.2 Bézier Curve Truncation
    11.3.3 The de Casteljau Algorithm
11.4 Catmull-Rom Splines
11.5 Cubic Splines
11.6 B-Splines
    11.6.1 Uniform B-Splines
    11.6.2 B-Spline Globalization
    11.6.3 Nonuniform B-Splines
    11.6.4 NURBS
11.7 Bicubic Surfaces
11.8 Curvature and Torsion

Chapter 12: Collision Detection
12.1 Plane Collisions
    12.1.1 Collision of a Sphere and a Plane
    12.1.2 Collision of a Box and a Plane
    12.1.3 Spatial Partitioning
12.2 General Sphere Collisions
12.3 Sliding
12.4 Collision of Two Spheres

Chapter 13: Linear Physics
13.1 Position Functions
13.2 Second-Order Differential Equations
    13.2.1 Homogeneous Equations
    13.2.2 Nonhomogeneous Equations
    13.2.3 Initial Conditions
13.3 Projectile Motion
13.4 Resisted Motion
13.5 Friction

Chapter 14: Rotational Physics
14.1 Rotating Environments
    14.1.1 Angular Velocity
    14.1.2 The Centrifugal Force
    14.1.3 The Coriolis Force
14.2 Rigid Body Motion
    14.2.1 Center of Mass
    14.2.2 Angular Momentum and Torque
    14.2.3 The Inertia Tensor
    14.2.4 Principal Axes of Inertia
    14.2.5 Transforming the Inertia Tensor
14.3 Oscillatory Motion
    14.3.1 Spring Motion
    14.3.2 Pendulum Motion

Chapter 15: Fluid and Cloth Simulation
15.1 Fluid Simulation
    15.1.1 The Wave Equation
    15.1.2 Approximating Derivatives
    15.1.3 Evaluating Surface Displacement
    15.1.4 Implementation
15.2 Cloth Simulation
    15.2.1 The Spring System
    15.2.2 External Forces
    15.2.3 Implementation

Chapter 16: Numerical Methods
16.1 Trigonometric Functions
16.2 Linear Systems
    16.2.1 Triangular Systems
    16.2.2 Gaussian Elimination
    16.2.3 LU Decomposition
    16.2.4 Error Reduction
    16.2.5 Tridiagonal Systems
16.3 Eigenvalues and Eigenvectors
16.4 Ordinary Differential Equations
    16.4.1 Euler’s Method
    16.4.2 Taylor Series Method
    16.4.3 Runge-Kutta Method
    16.4.4 Higher-Order Differential Equations

Appendix A: Complex Numbers
A.1 Definition
A.2 Addition and Multiplication
A.3 Conjugates and Inverses
A.4 The Euler Formula

Appendix B: Trigonometry Reference
B.1 Function Definitions
B.2 Symmetry and Phase Shifts
B.3 Pythagorean Identities
B.4 Exponential Identities
B.5 Inverse Functions
B.6 Laws of Sines and Cosines

Appendix C: Coordinate Systems
C.1 Cartesian Coordinates
C.2 Cylindrical Coordinates
C.3 Spherical Coordinates
C.4 Generalized Coordinates

Appendix D: Taylor Series
D.1 Derivation
D.2 Power Series
D.3 The Euler Formula

Appendix E: Answers to Exercises

Index

CODE LISTINGS

ERRATA

  • Page 6. In the second paragraph, the vertical bars for the intervals are cut off. They should be square brackets that look like [−1,1] and [0,1].
  • Page 50. On the first line following Equation (3.61), the upper limit of the summation should be n, not k.
  • Page 160. On line 2, the reference to Section 10.4.7 should be to Section 10.3.7.
  • Page 239. In Equation (8.58), the value of B should be normalized by dividing it by ‖N1 × N2‖.
  • Page 241. The first displayed equation on the page, giving the effective radius of a box with respect to a plane, should match Equation (8.47) and read reff = ½(|R · N| + |S · N| + |T · N|).
  • Page 321. In Figure 11.1, the bottom-most curve should be labeled t2(t − 1).
  • Page 338. The first line of Equation (11.73) should read Q1(t) = B0(t)P0 + B1(t)P1 + B2(t)P2 + B3(t)P3

Copyright © 2011 by Eric Lengyel