Now considered an essential reference in the game industry, 3D Game Engine Design is the first book to go beyond basic descriptions of algorithms and accurately demonstrate the complex engineering process required to design and build a real-time graphics engine to support physical realism. Faster algorithms will always win out over faster processors and assembly-language optimization techniques. Implementing those algorithms, however, can be a challenge for even experienced programmers. This book provides rigorous explanations and derivations of all the essential concepts and techniques. Ideas are revealed step by step with numerous code examples and illustrations. Source code implementations are included on the companion CD-ROM to help you understand the full progression from idea, to algorithm, to working code. Since algorithms are not used in isolation, the source code for a complete engine is provided to bring crucial context to the implementations. This book and CD-ROM offer the most comprehensive professional reference available for the development of 3D game engines. About the software: Includes a CD-ROM with C++ source code implementations of all the algorithms covered in the text as well as source code for a complete game engine. Updates for the engine, new ports (such as for the Macintosh), FAQs, and additional material on real-time graphics can be found at WildMagic http://www wild-magic.com/. The renderer layer of the engine is abstract and can work with whichever API is desired. An OpenGL-based renderer, DirectX8 (Direct3D), and a GLUT-based hardware renderer for either Windows or Linux, are included.

Table of Contents:
1 Introduction 1.1 A Brief Motivation 1.2 A Summary of the Chapters 1.3 Text is Not Enough 2 Geometrical Methods 2.1 Transformations 2.1.1 Scaling 2.1.2 Rotation 2.1.3 Translation 2.1.4 Homogeneous Transformations 2.2 Coordinate Systems 2.3 Quaternions 2.3.1 Quaternion Algebra 2.3.2 Relationship of Quaternions to Rotations 2.3.3 Conversion Between Angle-Axis and Rotation Matrix 2.3.4 Conversion Between Quaternion and Angle-Axis 2.3.5 Conversion Between Quaternion and Rotation Matrix 2.4 Euler Angles 2.4.1 Factoring Rotation Matrices 2.4.2 Factor Product of Two 2.5 Standard 3D Objects 2.5.1 Spheres 2.5.2 Oriented Boxes 2.5.3 Capsules 2.5.4 Lozenges 2.5.5 Cylinders 2.5.6 Ellipsoids 2.6 Distance Methods 2.6.1 Point to Linear Component 2.6.2 Linear Component to Linear Component 2.6.3 Point to Triangle 2.6.4 Linear Component to Triangle 2.6.5 Point to Rectangle 2.6.6 Linear Component to Rectangle 2.6.7 Triangle to Triangle 2.6.8 Triangle to Rectangle 2.6.9 Rectangle to Rectangle 2.6.10 Point to Oriented Box 2.6.11 Miscellaneous 3 The Graphics Pipeline 3.1 Model and World Coordinates 3.2 Perspective Projection 3.2.1 Lines Project to Lines 3.2.2 Triangles Project to Triangles 3.2.3 Conics Project to Conics 3.3 Camera Models 3.3.1 Standard Camera Model 3.3.2 General Camera Model 3.3.3 Model-To-View Transformation 3.3.4 Mapping to Screen Coordinates 3.3.5 Screen Space Distance Measurements 3.4 Culling and Clipping 3.4.1 Object Culling 3.4.2 Back Face Culling 3.4.3 Clipping 3.5 Surface and Vertex Attributes 3.5.1 Depth 3.5.2 Colors 3.5.3 Lighting and Materials 3.5.4 Textures 3.5.5 Transparency and Opacity 3.5.6 Fog 3.5.7 Combining Attributes 3.6 Rasterizing 3.6.1 Lines 3.6.2 Circles 3.6.3 Ellipses 3.6.4 Triangles 3.6.5 Interpolation During Rasterization 3.7 An Efficient Clipping and Lighting Pipeline 3.7.1 Triangle Meshes 3.7.2 Clipping a Triangle Mesh 3.7.3 Computing Vertex Attributes 3.8 Issues of Software, Hardware, and APIs 4 Hierarchical Scene Representations 4.1 Tree-Based Representations 4.1.1 Transforms 4.1.2 Bounding Volumes 4.1.3 Renderer State 4.1.4 Animation 4.2 Updating a Scene Graph 4.2.1 Merging Two Spheres 4.2.2 Merging Two Oriented Boxes 4.2.3 Merging Two Capsules 4.2.4 Merging Two Lozenges 4.2.5 Merging Two Cylinders 4.2.6 Merging Two Ellipsoids 4.2.7 Algorithm for Scene Graph Updating 4.3 Rendering a Scene Graph 4.3.1 Culling by Spheres 4.3.2 Culling by Oriented Boxes 4.3.3 Culling by Capsules 4.3.4 Culling by Lozenges 4.3.5 Culling by Cylinders 4.3.6 Culling by Ellipsoids 4.3.7 Algorithm for Scene Graph Rendering 5 Picking 5.1 Intersection of Linear Component and Sphere 5.2 Intersection of Linear Component and Box 5.2.1 Line Segment 5.2.2 Ray 5.2.3 Line 5.3 Intersection of Linear Component and Capsule 5.4 Intersection of Linear Component and Lozenge 5.5 Intersection of Linear Component and Cylinder 5.6 Intersection of Linear Component and Ellipsoid 5.7 Intersection of Linear Component and Triangle 6 Collision Detection 6.1 Introduction 6.2 Design Issues 6.3 Intersection of Dynamic Objects and Lines 6.3.1 Spheres 6.3.2 Oriented Boxes 6.3.3 Capsules 6.3.4 Lozenges 6.3.5 Cylinders 6.3.6 Ellipsoids 6.3.7 Triangles 6.4 Intersection of Dynamic Objects and Planes 6.4.1 Spheres 6.4.2 Oriented Boxes 6.4.3 Capsules 6.4.4 Lozenges 6.4.5 Cylinders 6.4.6 Ellipsoids 6.4.7 Triangles 6.5 Static Object-Object Intersection 6.5.1 Spheres, Capsules, and Lozenges 6.5.2 Oriented Boxes 6.5.3 Oriented Boxes and Triangles 6.5.4 Triangles 6.6 Dynamic Object-Object Intersection 6.6.1 Spheres, Capsules, and Lozenges 6.6.2 Oriented Boxes 6.6.3 Oriented Boxes and Triangles 6.6.4 Triangles 6.7 Oriented Bounding Box Trees 6.8 Processing of Rotating and Moving Objects 6.8.1 Equations of Motion 6.8.2 Closed-Form Algorithm 6.8.3 Algorithm Based on a Numerical ODE Solver 6.9 Constructing an Oriented Bounding Box Trees 6.10 A Simple Dynamic Collision Detection System 6.10.1 Testing for Collision 6.10.2 Finding Collision Points 7 Curves 7.1 Definitions 7.2 Reparameterization by Arc Length 7.3 Special Curves 7.3.1 Bezier Curves 7.3.2 Natural, Clamped, and Closed Cubic Splines 7.3.3 Nonparametric B-Spline Curves 7.3.4 Kochanek-Bartels Splines 7.4 Subdivision 7.4.1 Subdivision by Uniform Sampling 7.4.2 Subdivision by Arc Length 7.4.3 Subdivision by Midpoint Distance 7.4.4 Subdivision by Variation 7.4.5 Subdivision by Minimizing Variation 7.4.6 Fast Subdivision for Cubic Curves 7.5 Orientation of Objects on Curved Paths 7.5.1 Orientation Using the Frenet Frame 7.5.2 Orientation Using a Fixed Up Vector 8 Surfaces 8.1 Definitions 8.2 Curvature 8.2.1 Curvatures for Parametric Surfaces 8.2.2 Curvatures for Implicit Surfaces 8.2.3 Curvatures for Graphs 8.3 Special Surfaces 8.3.1 Bezier Rectangle Patches 8.3.2 Bezier Triangle Patches 8.3.3 Bezier Cylinder Surfaces 8.3.4 Nonparametric B-Spline Rectangle Patches 8.3.5 Quadric Surfaces 8.3.6 Tube Surfaces 8.4 Subdivision 8.4.1 Subdivision of Bezier Rectangle Patches 8.4.2 Subdivision of Bezier Triangle Patches 8.4.3 Subdivision of Bezier Cylinder Surfaces 8.4.4 Subdivision of Spheres and Ellipsoids 8.4.5 Subdivision of Tube Surface 9 Animation of Characters 9.1 Key Frame Animation 9.1.1 Quaternion Calculus 9.1.2 Spherical Linear Interpolation 9.1.3 Spherical Cubic Interpolation 9.1.4 Spline Interpolation of Quaternions 9.1.5 Updating a Key Frame Node 9.2 Inverse Kinematics 9.2.1 Numerical Solution by Jacobian Methods 9.2.2 Numerical Solution by Nonlinear Optimization 9.2.3 Numerical Solution by Cyclic Coordinate Descent 9.3 Skinning 10 Geometric Level of Detail 10.1 Sprites and Billboards 10.2 Discrete Level of Detail 10.3 Continuous Level of Detail 10.3.1 Simplification Using Quadratic Error Metrics 10.3.2 The Algorithm 10.3.3 Construction of the Error Metric 10.3.4 Simplification at Run Time 10.3.5 Selecting Surface Attributes 11 Terrain 11.1 Terrain Topology 11.2 Vertex-Based Simplification 11.2.1 Vertex-Based Simplification 11.2.2 Close Terrain Assumption 11.2.3 No Assumption 11.3 Block-Based Simplification 11.3.1 Distant Terrain Assumption 11.3.2 Close Terrain Assumption 11.3.3 No Assumption 11.4 Vertex Dependencies 11.5 Block Rendering 11.6 The Full Algorithm 11.7 Other Issues 11.7.1 Terrain pages and Memory Management 11.7.2 Vertex Attributes 11.7.3 Height Calculations 11.8 Height Fields from Point Sets or Triangle Meshes 11.8.1 Linear Interpolation 11.8.2 Quadratic Interpolation 12 Spatial Sorting 12.1 Quadtrees and Octrees 12.2 Portals 12.3 Binary Space Partitioning 12.3.1 BSP Tree Construction 12.3.2 Hidden Surface Removal 12.3.3 Visibility Determination 12.3.4 Picking and Collision Detection 13 Special Effects 13.1 Lens Flare 13.2 Environment Mapping 13.3 Bump Mapping 13.4 Volumetric Fogging 13.5 Projected Lights 13.6 Projected Shadows 13.7 Particle Systems 13.8 Morphing 14 Object-Oriented Infrastructure 14.1 Object-Oriented Software Construction 14.1.1 Software Quality 14.1.2 Modularity 14.1.3 Reusability 14.1.4 Functions and Data 14.1.5 Object-Orientation 14.2 Style, Naming Conventions, and Namespaces 14.3 Run-Time Type Information 14.3.1 Single-Inheritance Systems 14.3.2 Multiple-Inheritance Systems 14.3.3 Macro Support 14.4 Templates 14.5 Shared Objects and Reference Counting 14.6 Streaming 14.6.1 Saving Data 14.6.2 Loading Data 14.6.3 Streaming Support 14.7 Startup and Shutdown 15 Numerical Methods 15.1 Systems of Equations 15.1.1 Linear Systems 15.1.2 Polynomial Systems 15.2 Eigensystems 15.3 Least-Squares Fitting 15.3.1 Linear Fitting of Points (x, f(x)) 15.3.2 Linear Fitting of Points Using Orthogonal Regression 15.3.3 Planar Fitting of Points (x, y, f(x,y)) 15.3.4 Hyperplanar Fitting of Points Using Orthogonal Regression 15.3.5 Fitting a Circle to 2D Points 15.3.6 Fitting a Sphere to 3D Points 15.3.7 Fitting a Quadratic Curve to 2D Points 15.3.8 Fitting a Quadric Surface to 3D Points 15.4 Minimization 15.4.1 Methods in One Dimension 15.4.2 Methods in Many Dimensions 15.5 Root Finding 15.5.1 Methods in One Dimension 15.5.2 Methods in Many Dimensions 15.6 Integration 15.6.1 Romberg Integration 15.6.2 Gaussian Quadrature 15.7 Differential Equations 15.7.1 Ordinary Differential Equations 15.7.2 Partial Differential Equations 15.8 Fast Function Evaluation 15.8.1 Square Root and Inverse Square Root 15.8.2 Sine, Cosine, and Tangent 15.8.3 Inverse Tangent 15.8.4 CORDIC Methods