3D Game Engine Design
A Practical Approach to Real-Time Computer Graphics
1st Edition
Published on 22. September 2000
Book
Hardback
561 pages
978-1-55860-593-0 (ISBN)
Description
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.
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.
Reviews / Votes
I have been baffled by the lackluster quality of past publications targeted specifically at the interactive, real-time engineer and developer, and I am confident that Dr. Eberly's magnum opus will raise the bar for everyone who follows in his footsteps. I expect his work to become to game developers what Foley, Van Dam, et al., was to the graphics community in the late 80s and early 90s: the de facto mirror of the stae of art in research and development in the field. --Andrea Pessino, Blizzard EntertainmentThis is a great book for someone who is writing his or her first 3D engine and has a reasonable background in math. Even for people who have written game engines before, there is plenty of value in the alternative techniques that Eberaly presents for various parts of the 3D pipeline, which makes for a great reference text. I particularly like the presentation of various alternatives and their pros and cons. He clearly covers performance issues and includes all the important elements of a graphics game engine. He even includes a good introduction to animation techniques and collision detection. The book is not ashamed to delve deep into the technical details and the mathematics behind 3D graphics; I think this is good. 3D Game Engine Design would certainly find a prime place on my bookshelf. --Dominic Mallinson, Director of Technology, Research, and Development, Sony Computer Entertainment America
Virtually all the books on building 3D game engines cover the basics: here's a polygon, here's a transformation matrix, here's a perspective projection, and so on. The problem is that you can't make a professional quality game with just the basics. This leaves a large gap between you and your goal of creating a great game engine. With this book, Dave is launching a huge boulder into the gap, helping you scamper to your destination. Managing a generalized 3D environment in real-time is difficult, the book covers a complete set of high-end techniques to do the job. For example, if you want to find collisions between the swept volumes of two oriented bounding volumes as they fly through space go to page 194. I think most game companies would be lucky to come anywhere close to this level of sophistication. I loved Appendix A, "Object-Oriented Infrastructure." It covers many of the software-engineering issues we have had to solve over the years; things like objects with multiple references being managed by a reference count semaphore. --Eric Yiskis, Lead Programmer, Oddworld Inhabitants
[3D Game Engine Design] presents an incredible amount of difficult and complex information in a clear and understandable manner. --Ian Ashdown, University of British Columbia
Well done...definately a must-have reference for the budding 3D engine developer. --Peter Lipson, Mindscape
Before reading the chapters, [the table of contents] engaged me and I said to myself , "I'm going to learn a lot from this book." I'm inclined to recommend this to my undergraduates who want to have a reference for 3D graphics programming. --Jahn Laird, University of Michigan
This book will serve as a welcome resource for game programmers who wish to work at the cutting edge of their trade. It is a remarkably comprehensive and elegant guide to the construction of interactive 3D environments at a professional level. Drawing on the latest advances in real-time rendering and software engineering, Eberly astutely brings game engine development into the 21st century. --Sherry McKenna, CEO Oddworld Inhabitants
Dave Eberly has written the definitive book on real-time 3D game engine design. It's a must-have for anyone who writes real-time 3D code. --Franz Lanzinger, Actual Entertainment
In an industry where quality information is extremely difficult to come by, Dave Eberly has managed to compile a desperately needed perspective for those programming the most critical link in the game production process: the game engine. This book should be mandatory reading for all aspiring game engine designers. --Lorne Lanning, Cofounder and President, Oddworld Inhabitants
More details
Language
English
Place of publication
San Francisco
United States
Publishing group
Elsevier Science & Technology
Target group
College/higher education
Professionals or students working in game development, simulation, scientific visualization, or virtual worlds.
Dimensions
Height: 234 mm
Width: 190 mm
ISBN-13
978-1-55860-593-0 (9781558605930)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
New editions
Book
11/2006
2nd Edition
Focal Press
€129.50
Shipment within 15-20 days
Person
Dave Eberly is the president of Geometric Tools, Inc. (www.geometrictools.com), a company that specializes in software development for computer graphics, image analysis, and numerical methods. Previously, he was the director of engineering at Numerical Design Ltd. (NDL), the company responsible for the real-time 3D game engine, NetImmerse. He also worked for NDL on Gamebryo, which was the next-generation engine after NetImmerse. His background includes a BA degree in mathematics from Bloomsburg University, MS and PhD degrees in mathematics from the University of Colorado at Boulder, and MS and PhD degrees in computer science from the University of North Carolina at ChapelHill. He is the author of 3D Game Engine Design, 2nd Edition (2006), 3D Game Engine Architecture (2005), Game Physics (2004), and coauthor with Philip Schneider of Geometric Tools for Computer Graphics (2003), all published by Morgan Kaufmann. As a mathematician, Dave did research in the mathematics of combustion, signal and image processing, and length-biased distributions in statistics. He was an associate professor at the University of Texas at San Antonio with an adjunct appointment in radiology at the U.T. Health Science Center at San Antonio. In 1991, he gave up his tenured position to re-train in computer science at the University of North Carolina. After graduating in 1994, he remained for one year as a research associate professor in computer science with a joint appointment in the Department of Neurosurgery, working in medical image analysis. His next stop was the SAS Institute, working for a year on SAS/Insight, a statistical graphics package. Finally, deciding that computer graphics and geometry were his real calling, Dave went to work for NDL (which is now Emergent Game Technologies), then to Magic Software, Inc., which later became Geometric Tools, Inc. Dave's participation in the newsgroup comp.graphics.algorit
Content
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
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