3D Game Engine Design
A Practical Approach to Real-Time Computer Graphics
- 1st Edition - October 9, 2000
- Imprint: Morgan Kaufmann
- Author: David H. Eberly
- Language: English
- eBook ISBN:9 7 8 - 0 - 0 8 - 0 4 9 8 4 1 - 6
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 demonstra… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteNow 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. 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 offers the most comprehensive professional reference available for the development of 3D game engines.
- Designed for professionals working in game development, simulation, scientific visualization, or virtual worlds.
- Written by a respected game engineer and designer of a leading commercial game engine.
- Thoroughly describes the algorithms—fully implemented in working code—that are the key to writing the fastest, most efficient code possible.
- Provides source code for Windows 95/98/NT/2000, Linux/Unix, and Macintosh platforms.
Programmers working in game and simulation design, interactive 3D graphics and real-time 3D graphics engine
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
- Edition: 1
- Published: October 9, 2000
- Imprint: Morgan Kaufmann
- Language: English
- eBook ISBN: 9780080498416
DE
David H. Eberly
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
Affiliations and expertise
President of Geometric Tools, Inc.