Table of Contents for 3D Game Engine Design (2nd Edition)

 1 Introduction
 2 The Graphics System
   2.1 The Foundation
       2.1.1 Coordinate Systems
       2.1.2 Handedness and Cross Products
       2.1.3 Points and Vectors
   2.2 Transformations
       2.2.1 Linear Transformations
       2.2.2 Affine Transformations
       2.2.3 Projective Transformations
       2.2.4 Properties of Perspective Projection
       2.2.5 Homogeneous Points and Matrices
   2.3 Cameras
       2.3.1 The Perspective Camera Model
       2.3.2 Model or Object Space
       2.3.3 World Space
       2.3.4 View, Camera, or Eye Space
       2.3.5 Clip, Projection, or Homogeneous Space
       2.3.6 Window Space
       2.3.7 Putting Them All Together
   2.4 Culling and Clipping
       2.4.1 Object Culling
       2.4.2 Back-Face Culling
       2.4.3 Clipping to the View Frustum
   2.5 Rasterizing
       2.5.1 Line Segments
       2.5.2 Circles
       2.5.3 Ellipses
       2.5.4 Triangles
   2.6 Vertex Attributes
       2.6.1 Colors
       2.6.2 Lighting and Materials
       2.6.3 Textures
       2.6.4 Transparency, Opacity, and Blending
       2.6.5 Fog
       2.6.6 Rasterizing Attributes
   2.7 Issues of Software, Hardware, and APIs
       2.7.1 A General Discussion
       2.7.2 Portability versus Performance
   2.8 API Conventions
       2.8.1 Matrix Representations and Storage
       2.8.2 Matrix Composition
       2.8.3 View Matrices
       2.8.4 Projection Matrices
       2.8.5 Window Handedness
       2.8.6 Rotations
       2.8.7 Fast Computations using the Graphics API
 3 Renderers
   3.1 Software Rendering
       3.1.1  Vertex Shaders
       3.1.2  Back-Face Culling
       3.1.3  Clipping
       3.1.4  Rasterizing
       3.1.5  Edge Buffers
       3.1.6  Scan Line Processing
       3.1.7  Pixel Shaders
       3.1.8  Stencil Buffering
       3.1.9  Depth Buffering
       3.1.10 Alpha Blending
       3.1.11 Color Masking
       3.1.12 Texture Sampling
       3.1.13 Frame Buffers
   3.2 Hardware Rendering
   3.3 An Abstract Rendering API
       3.3.1 Construction and Destruction
       3.3.2 Camera Management
       3.3.3 Global-State Management
       3.3.4 Buffer Clearing
       3.3.5 Object Drawing
       3.3.6 Text and 2D Drawing
       3.3.7 Miscellaneous
       3.3.8 Resource Management
   3.4 The Heart of the Renderer
       3.4.1 Drawing a Scene
       3.4.2 Drawing a Geometric Primitive
       3.4.3 Applying an Effect
       3.4.4 Loading and Parsing Shader Programs
       3.4.5 Validation of Shader Programs
 4 Scene Graphs
   4.1 Scene Graph Design Issues
       4.1.1 The Core Classes
       4.1.2 Spatial Hierarchy Design
       4.1.3 Sharing of Objects
   4.2 Geometric State
       4.2.1 Vertex Buffers and Index Buffers
       4.2.2 Transformations
       4.2.3 Bounding Volumes
       4.2.4 Geometric Types
   4.3 Render State
       4.3.1 Global State
       4.3.2 Lights
       4.3.3 Effects
   4.4 The Update Pass
       4.4.1 Geometric-State Updates
       4.4.2 Render-State Updates
   4.5 The Culling Pass
       4.5.1 Hierarchical Culling
       4.5.2 Sorted Culling
   4.6 The Drawing Pass
       4.6.1 Single-Pass Drawing
       4.6.2 Single-Effect, Multipass Drawing
       4.6.3 Multiple-Effect Drawing
   4.7 Scene Graph Compilers
       4.7.1 A Scene Graph as a Dynamic Expression
       4.7.2 Semantics of Compilation
 5 Controller-Based Animation
   5.1 Keyframe Animation
       5.1.1 Interpolation of Position
       5.1.2 Interpolation of Orientation
       5.1.3 Interpolation of Scale
   5.2 Keyframe Compression
       5.2.1 Fitting Points with a B-spline Curve
       5.2.2 Evaluation of a B-spline Curve
       5.2.3 Optimized Evaluation for Degree 3
   5.3 Inverse Kinematics
       5.3.1 Numerical Solution by Jacobian Methods
       5.3.2 Numerical Solution by Nonlinear Optimization
       5.3.3 Numerical Solution by Cyclic Coordinate Descent
   5.4 Skinning
   5.5 Vertex Morphing
   5.6 Particle Systems
 6 Spatial Sorting
   6.1 Binary Space Partitioning Trees
       6.1.1 BSP Tree Construction
       6.1.2 BSP Tree Usage
   6.2 Node-Based Sorting
   6.3 Portals
   6.4 User-Defined Maps
   6.5 Occlusion Culling
 7 Level of Detail
   7.1 Sprites and Billboards
   7.2 Discrete Level of Detail
   7.3 Continuous Level of Detail
       7.3.1 Simplification using Quadric Error Metrics
       7.3.2 Reordering of Vertices and Indices
       7.3.3 Terrain
   7.4 Infinite Level of Detail
 8 Collision Detection
   8.1 The Method of Separating Axes
       8.1.1 Extrema of Convex Polygons or Convex Polyhedra
       8.1.2 Stationary Objects
       8.1.3 Objects Moving with Constant Linear Velocity
       8.1.4 Oriented Bounding Boxes
   8.2 Finding Collisions Between Moving Objects
       8.2.1 Pseudodistance
       8.2.2 Contact Between Moving Intervals
       8.2.3 Computing the First Time of Contact
       8.2.4 Estimating the First Derivative
   8.3 A Dynamic Collision Detection System
       8.3.1 The Abstract Base Class
       8.3.2 Pseudodistances for Specific Pairs of Object Types
       8.3.3 Collision Culling with Axis-Aligned Bounding Boxes
   8.4 Object Picking
       8.4.1 Constructing a Pick Ray
       8.4.2 Scene Graph Support
       8.4.3 Staying on Top of Things
       8.4.4 Staying Out of Things
   8.5 Pathfinding to Avoid Collisions
       8.5.1 Environments, Levels, and Rooms
       8.5.2 Moving Between Rooms
       8.5.3 Moving Between Levels
       8.5.4 Moving Through the Outdoor Environment
       8.5.5 Blueprints
       8.5.6 Visibility Graphs
       8.5.7 Envelope Construction
       8.5.8 Basic Data Structures
       8.5.9 Efficient Calculation of the Visibility Graph
 9 Physics
   9.1 Particle Systems
   9.2 Mass-Spring Systems
       9.2.1 Curve Masses
       9.2.2 Surface Masses
       9.2.3 Volume Masses
       9.2.4 Arbitrary Configurations
   9.3 Deformable Bodies
   9.4 Rigid Bodies
       9.4.1 The Rigid Body Class
       9.4.2 Computing the Inertia Tensor
10 Standard Objects
   10.1 Linear Components
   10.2 Planar Components
   10.3 Boxes
   10.4 Quadrics
        10.4.1 Spheres
        10.4.2 Ellipsoids
        10.4.3 Cylinders
        10.4.4 Cones
   10.5 Sphere-Swept Volumes
        10.5.1 Capsules
        10.5.2 Lozenges
11 Curves
   11.1 Definitions
   11.2 Reparameterization by Arc Length
   11.3 Bezier Curves
        11.3.1 Definitions
        11.3.2 Evaluation
        11.3.3 Degree Elevation
        11.3.4 Degree Reduction
   11.4 Natural, Clamped, and Closed Cubic Splines
        11.4.1 Natural Splines
        11.4.2 Clamped Splines
        11.4.3 Closed Splines
   11.5 B-spline Curves
        11.5.1 Types of Knot Vectors
        11.5.2 Evaluation
        11.5.3 Local Control
        11.5.4 Closed Curves
   11.6 NURBS Curves
   11.7 Tension-Continuity-Bias Splines
   11.8 Parametric Subdivision
        11.8.1 Subdivision by Uniform Sampling
        11.8.2 Subdivision by Arc Length
        11.8.3 Subdivision by Midpoint Distance
        11.8.4 Fast Subdivision for Cubic Curves
   11.9 Orientation of Objects on Curved Paths
        11.9.1 Orientation Using the Frenent Frame
        11.9.2 Orientation Using a Fixed Up-Vector
12 Surfaces
   12.1 Introduction
   12.2 Bezier Rectangle Patches
        12.2.1 Definitions
        12.2.2 Evaluation
        12.2.3 Degree Elevation
        12.2.4 Degree Reduction
   12.3 Bezier Triangle Patches
        12.3.1 Definitions
        12.3.2 Evaluation
        12.3.3 Degree Elevation
        12.3.4 Degree Reduction
   12.4 B-spline Rectange Patches
   12.5 NURBS Rectangle Patches
   12.6 Surfaces Built from Curves
        12.6.1 Cylinder Surfaces
        12.6.2 Generalized Cylinder Surfaces
        12.6.3 Revolution Surfaces
        12.6.4 Tube Surfaces
   12.7 Parametric Subdivision
        12.7.1 Subdivision of Rectangle Patches
        12.7.2 Subdivision of Triangle Patches
13 Containment Methods
   13.1 Spheres
        13.1.1 Point in Sphere
        13.1.2 Sphere Containing Points
        13.1.3 Merging Spheres
   13.2 Boxes
        13.2.1 Point in Box
        13.2.2 Box Containing Points
        13.2.3 Merging Boxes
   13.3 Capsules
        13.3.1 Point in Capsule
        13.3.2 Capsule Containing Points
        13.3.3 Merging Capsules
   13.4 Lozenges
        13.4.1 Point in Lozenge
        13.4.2 Lozenge Containing Points
        13.4.3 Merging Lozenges
   13.5 Cylinders
        13.5.1 Point in Cylinder
        13.5.2 Cylinder Containing Points
        13.5.3 Merging Cylinders
   13.6 Ellipsoids
        13.6.1 Point in Ellipsoid
        13.6.2 Ellipsoid Containing Points
        13.6.3 Merging Ellipsoids
14 Distance Methods
   14.1  Point to Linear Component
         14.1.1 Point to Line
         14.1.2 Point to Ray
         14.1.3 Point to Segment
   14.2  Linear Component to Linear Component
         14.2.1 Line to Line
         14.2.2 Line to Ray
         14.2.3 Line to Segment
         14.2.4 Ray to Ray
         14.2.5 Ray to Segment
         14.2.6 Segment to Segment
   14.3  Point to Triangle
   14.4  Linear Component to Triangle
         14.4.1 Line to Triangle
         14.4.2 Ray to Triangle
         14.4.3 Segment to Triangle
   14.5  Point to Rectangle
   14.6  Linear Component to Rectangle
         14.6.1 Line to Rectangle
         14.6.2 Ray to Rectangle
         14.6.3 Segment to Rectangle
   14.7  Triangle or Rectangle to Triangle or Rectangle
   14.8  Point to Oriented Box
   14.9  Linear Component to Oriented Box
         14.9.1 Line to Oriented Box
         14.9.1 Ray to Oriented Box
         14.9.1 Segment to Oriented Box
   14.10 Triangle to Oriented Box
   14.11 Rectangle to Oriented Box
   14.12 Oriented Box to Oriented Box
   14.13 Miscellaneous
         14.13.1 Point to Ellipse
         14.13.2 Point to Ellipsoid
         14.13.3 Point to Quadratic Curve or Quadric Surface
         14.13.4 Point to Circle in 3D
         14.13.5 Circle to Circle in 3D
15 Intersection Methods
   15.1 Linear Components and Convex Objects
   15.2 Linear Components and Planar Component
   15.3 Linear Component and Oriented Box
        15.3.1 Test-Intersection Query
        15.3.2 Find-Intersection Query
   15.4 Linear Component and Sphere
        15.4.1 Line and Sphere
        15.4.2 Ray and Sphere
        15.4.3 Segment and Sphere
   15.5 Line and Sphere-Swept Volume
        15.5.1 Line and Capsule
        15.5.2 Line and Lozenge
   15.6 Line and Quadric Surface
        15.6.1 Line and Ellipsoid
        15.6.2 Line and Cylinder
        15.6.3 Line and Cone
   15.7 Culling Objects by Planes
        15.7.1 Oriented Boxes
        15.7.2 Spheres
        15.7.3 Capsules
        15.7.4 Lozenges
        15.7.5 Ellipsoids
        15.7.6 Cylinders
        15.7.7 Cones
        15.7.8 Convex Polygons or Convex Polyhedra
16 Numerical Methods
   16.1 Systems of Equations
        16.1.1 Linear Systems
        16.1.2 Polynomial Systems
   16.2 Eigensystems
        16.2.1 Extrema of Quadratic Forms
        16.2.2 Extrema of Constrained Quadratic Forms
   16.3 Least-Squares Fitting
        16.3.1 Linear Fitting of Points (x,f(x))
        16.3.2 Linear Fitting of Points Using Orthogonal Regression
        16.3.3 Planar Fitting of Points (x,y,f(x,y))
        16.3.4 Planar Fitting of Points Using Orthogonal Regression
        16.3.5 Fitting a Circle to 2D Points
        16.3.6 Fitting a Sphere to 3D Points
        16.3.7 Fitting a Quadratic Curve to 2D Points
        16.3.8 Fitting a Quadric Surface to 3D Points
   16.4 Minimization
        16.4.1 Methods in One Dimension
        16.4.2 Methods in Many Dimensions
   16.5 Root Finding
        16.5.1 Methods in One Dimension
        16.5.2 Methods in Many Dimensions
   16.6 Integration
        16.6.1 Romberg Integration
        16.6.2 Gaussian Quadrature
   16.7 Differential Equations
        16.7.1 Ordinary Differential Equations
        16.7.2 Partial Differential Equations
   16.8 Fast Function Evaluation
        16.8.1 Square Root and Inverse Square Root
        16.8.2 Sine, Cosine, and Tangent
        16.8.3 Inverse Tangent
17 Rotations
   17.1 Rotation Matrices
        17.1.1 Axis/Angle to Matrix
        17.1.2 Matrix to Axis/Angle
        17.1.3 Interpolation
   17.2 Quaternions
        17.2.1 The Linear Algebraic View of Quaternions
        17.2.2 Rotation of a Vector
        17.2.3 Product of Rotations
        17.2.4 The Classical View of Quaternions
        17.2.5 Axis/Angle to Quaternion
        17.2.6 Quaternion to Axis/Angle
        17.2.7 Matrix to Quaternion
        17.2.8 Quaternion to Matrix
        17.2.9 Interpolation
   17.3 Euler Angles
   17.4 Performance Issues
        17.4.1 Memory Usage
        17.4.2 Conversion Time
        17.4.3 Transformation Time
        17.4.4 Composition
        17.4.5 Interpolation
   17.5 The Curse of Nonuniform Scaling
        17.5.1 Matrix Factorizations
        17.5.2 Gram-Schmidt Orthonormalization
        17.5.3 Polar Decomposition
        17.5.4 Singular Value Decomposition
18 Object-Oriented Infrastructure
   18.1 Object-Oriented Software Construction
        18.1.1 Software Quality
        18.1.2 Modularity
        18.1.3 Reusability
        18.1.4 Functions and Data
        18.1.5 Object Orientation
   18.2 Style, Naming Conventions, and Namespaces
   18.3 Run-Time Type Information
        18.3.1 Single-Inheritance Systems
        18.3.2 Multiple-Inheritance Systems
        18.3.3 Macro Support
   18.4 Templates
   18.5 Shared Objects and Reference Counting
   18.6 Streaming
        18.6.1 The Stream API
        18.6.2 The Object API
   18.7 Names and Unique Identification
        18.7.1 Name String
        18.7.2 Unique Identification
   18.8 Initialization and Termination
        18.8.1 Potential Problems
        18.8.2 A Generic Solution for Classes
   18.9 An Application Layer
        18.9.1 Processing Command Line Parameters
        18.9.2 The Application Class
        18.9.3 The ConsoleApplication Class
        18.9.4 The WindowApplication Class
        18.9.5 The WindowApplication3 Class
        18.9.6 Managing the Engines
19 Memory Management
   19.1 Memory Budgets for Game Consoles
   19.2 Leak Detection and Collecting Statistics
   19.3 General Concepts for Memory Management
        19.3.1 Allocation Using Sequential Fit Methods
        19.3.2 Allocation Using Buddy System Methods
        19.3.3 Allocation Using Segregated Storage Methods
        19.3.4 Memory Compaction
20 Special Effects Using Shaders
  20.1  Vertex Colors
  20.2  Lighting and Materials
        20.2.1 Ambient Lights
        20.2.2 Directional Lights
        20.2.3 Point Lights
        20.2.4 Spot Lights
  20.3  Textures
  20.4  Multitextures
  20.5  Bump Maps
        20.5.1 Generating Normal Maps
        20.5.2 Generating Tangent-Space Information
        20.5.3 The Shader Programs
  20.6  Gloss Maps
  20.7  Sphere Maps
  20.8  Cube Maps
  20.9  Refraction
  20.10 Planar Reflections
  20.11 Planar Shadows
  20.12 Projected Textures
  20.13 Shadow Maps
  20.14 Volumetric Fog
  20.15 Skinning
  20.16 Iridescence
  20.17 Water Effects
       
A Creating a Shader in Wild Magic
  A.1 Shader Programs for an Illustrative Application
  A.2 Creating the Geometric Data
  A.3 A Classless Shader Effect
  A.4 Creating a ShaderEffect-derived Class
  A.5 Dynamic Updates for the Shader Constants
Bibliography