- ホーム
- > 洋書
- > 英文書
- > Computer / Languages
Full 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.
Contents
1 Introduction1.1 A Brief Motivation1.2 A Summary of the Chapters1.3 Text is Not Enough2 Geometrical Methods2.1 Transformations2.1.1 Scaling2.1.2 Rotation2.1.3 Translation2.1.4 Homogeneous Transformations2.2 Coordinate Systems2.3 Quaternions2.3.1 Quaternion Algebra2.3.2 Relationship of Quaternions to Rotations2.3.3 Conversion Between Angle-Axis and Rotation Matrix2.3.4 Conversion Between Quaternion and Angle-Axis2.3.5 Conversion Between Quaternion and Rotation Matrix2.4 Euler Angles2.4.1 Factoring Rotation Matrices2.4.2 Factor Product of Two2.5 Standard 3D Objects2.5.1 Spheres2.5.2 Oriented Boxes2.5.3 Capsules2.5.4 Lozenges2.5.5 Cylinders2.5.6 Ellipsoids2.6 Distance Methods2.6.1 Point to Linear Component2.6.2 Linear Component to Linear Component2.6.3 Point to Triangle2.6.4 Linear Component to Triangle2.6.5 Point to Rectangle2.6.6 Linear Component to Rectangle2.6.7 Triangle to Triangle2.6.8 Triangle to Rectangle2.6.9 Rectangle to Rectangle2.6.10 Point to Oriented Box2.6.11 Miscellaneous3 The Graphics Pipeline3.1 Model and World Coordinates3.2 Perspective Projection3.2.1 Lines Project to Lines3.2.2 Triangles Project to Triangles3.2.3 Conics Project to Conics3.3 Camera Models3.3.1 Standard Camera Model3.3.2 General Camera Model3.3.3 Model-To-View Transformation3.3.4 Mapping to Screen Coordinates3.3.5 Screen Space Distance Measurements3.4 Culling and Clipping3.4.1 Object Culling3.4.2 Back Face Culling3.4.3 Clipping3.5 Surface and Vertex Attributes3.5.1 Depth3.5.2 Colors3.5.3 Lighting and Materials3.5.4 Textures3.5.5 Transparency and Opacity3.5.6 Fog3.5.7 Combining Attributes3.6 Rasterizing3.6.1 Lines3.6.2 Circles3.6.3 Ellipses3.6.4 Triangles3.6.5 Interpolation During Rasterization3.7 An Efficient Clipping and Lighting Pipeline3.7.1 Triangle Meshes3.7.2 Clipping a Triangle Mesh3.7.3 Computing Vertex Attributes3.8 Issues of Software, Hardware, and APIs4 Hierarchical Scene Representations4.1 Tree-Based Representations4.1.1 Transforms4.1.2 Bounding Volumes4.1.3 Renderer State4.1.4 Animation4.2 Updating a Scene Graph4.2.1 Merging Two Spheres4.2.2 Merging Two Oriented Boxes4.2.3 Merging Two Capsules4.2.4 Merging Two Lozenges4.2.5 Merging Two Cylinders4.2.6 Merging Two Ellipsoids4.2.7 Algorithm for Scene Graph Updating4.3 Rendering a Scene Graph4.3.1 Culling by Spheres4.3.2 Culling by Oriented Boxes4.3.3 Culling by Capsules4.3.4 Culling by Lozenges4.3.5 Culling by Cylinders4.3.6 Culling by Ellipsoids4.3.7 Algorithm for Scene Graph Rendering5 Picking5.1 Intersection of Linear Component and Sphere5.2 Intersection of Linear Component and Box5.2.1 Line Segment5.2.2 Ray5.2.3 Line5.3 Intersection of Linear Component and Capsule5.4 Intersection of Linear Component and Lozenge5.5 Intersection of Linear Component and Cylinder5.6 Intersection of Linear Component and Ellipsoid5.7 Intersection of Linear Component and Triangle6 Collision Detection6.1 Introduction6.2 Design Issues6.3 Intersection of Dynamic Objects and Lines6.3.1 Spheres6.3.2 Oriented Boxes6.3.3 Capsules6.3.4 Lozenges6.3.5 Cylinders6.3.6 Ellipsoids6.3.7 Triangles6.4 Intersection of Dynamic Objects and Planes6.4.1 Spheres6.4.2 Oriented Boxes6.4.3 Capsules6.4.4 Lozenges6.4.5 Cylinders6.4.6 Ellipsoids6.4.7 Triangles6.5 Static Object-Object Intersection6.5.1 Spheres, Capsules, and Lozenges6.5.2 Oriented Boxes6.5.3 Oriented Boxes and Triangles6.5.4 Triangles6.6 Dynamic Object-Object Intersection6.6.1 Spheres, Capsules, and Lozenges6.6.2 Oriented Boxes6.6.3 Oriented Boxes and Triangles6.6.4 Triangles6.7 Oriented Bounding Box Trees6.8 Processing of Rotating and Moving Objects6.8.1 Equations of Motion6.8.2 Closed-Form Algorithm6.8.3 Algorithm Based on a Numerical ODE Solver6.9 Constructing an Oriented Bounding Box Trees6.10 A Simple Dynamic Collision Detection System6.10.1 Testing for Collision6.10.2 Finding Collision Points7 Curves7.1 Definitions7.2 Reparameterization by Arc Length 7.3 Special Curves7.3.1 Bezier Curves7.3.2 Natural, Clamped, and Closed Cubic Splines7.3.3 Nonparametric B-Spline Curves7.3.4 Kochanek-Bartels Splines7.4 Subdivision7.4.1 Subdivision by Uniform Sampling7.4.2 Subdivision by Arc Length7.4.3 Subdivision by Midpoint Distance7.4.4 Subdivision by Variation7.4.5 Subdivision by Minimizing Variation7.4.6 Fast Subdivision for Cubic Curves7.5 Orientation of Objects on Curved Paths7.5.1 Orientation Using the Frenet Frame7.5.2 Orientation Using a Fixed Up Vector8 Surfaces8.1 Definitions8.2 Curvature8.2.1 Curvatures for Parametric Surfaces8.2.2 Curvatures for Implicit Surfaces8.2.3 Curvatures for Graphs8.3 Special Surfaces8.3.1 Bezier Rectangle Patches8.3.2 Bezier Triangle Patches8.3.3 Bezier Cylinder Surfaces8.3.4 Nonparametric B-Spline Rectangle Patches8.3.5 Quadric Surfaces8.3.6 Tube Surfaces8.4 Subdivision8.4.1 Subdivision of Bezier Rectangle Patches8.4.2 Subdivision of Bezier Triangle Patches8.4.3 Subdivision of Bezier Cylinder Surfaces8.4.4 Subdivision of Spheres and Ellipsoids8.4.5 Subdivision of Tube Surface9 Animation of Characters9.1 Key Frame Animation9.1.1 Quaternion Calculus9.1.2 Spherical Linear Interpolation9.1.3 Spherical Cubic Interpolation9.1.4 Spline Interpolation of Quaternions 9.1.5 Updating a Key Frame Node9.2 Inverse Kinematics9.2.1 Numerical Solution by Jacobian Methods9.2.2 Numerical Solution by Nonlinear Optimization9.2.3 Numerical Solution by Cyclic Coordinate Descent9.3 Skinning10 Geometric Level of Detail10.1 Sprites and Billboards10.2 Discrete Level of Detail10.3 Continuous Level of Detail10.3.1 Simplification Using Quadratic Error Metrics10.3.2 The Algorithm10.3.3 Construction of the Error Metric10.3.4 Simplification at Run Time10.3.5 Selecting Surface Attributes11 Terrain11.1 Terrain Topology11.2 Vertex-Based Simplification11.2.1 Vertex-Based Simplification11.2.2 Close Terrain Assumption11.2.3 No Assumption11.3 Block-Based Simplification11.3.1 Distant Terrain Assumption11.3.2 Close Terrain Assumption11.3.3 No Assumption11.4 Vertex Dependencies11.5 Block Rendering11.6 The Full Algorithm11.7 Other Issues11.7.1 Terrain pages and Memory Management11.7.2 Vertex Attributes11.7.3 Height Calculations11.8 Height Fields from Point Sets or Triangle Meshes11.8.1 Linear Interpolation11.8.2 Quadratic Interpolation12 Spatial Sorting12.1 Quadtrees and Octrees12.2 Portals 12.3 Binary Space Partitioning12.3.1 BSP Tree Construction12.3.2 Hidden Surface Removal12.3.3 Visibility Determination12.3.4 Picking and Collision Detection13 Special Effects13.1 Lens Flare13.2 Environment Mapping13.3 Bump Mapping13.4 Volumetric Fogging13.5 Projected Lights13.6 Projected Shadows13.7 Particle Systems13.8 Morphing14 Object-Oriented Infrastructure14.1 Object-Oriented Software Construction14.1.1 Software Quality14.1.2 Modularity14.1.3 Reusability14.1.4 Functions and Data14.1.5 Object-Orientation14.2 Style, Naming Conventions, and Namespaces14.3 Run-Time Type Information14.3.1 Single-Inheritance Systems14.3.2 Multiple-Inheritance Systems14.3.3 Macro Support14.4 Templates14.5 Shared Objects and Reference Counting14.6 Streaming14.6.1 Saving Data14.6.2 Loading Data14.6.3 Streaming Support14.7 Startup and Shutdown15 Numerical Methods15.1 Systems of Equations15.1.1 Linear Systems15.1.2 Polynomial Systems15.2 Eigensystems15.3 Least-Squares Fitting15.3.1 Linear Fitting of Points (x, f(x))15.3.2 Linear Fitting of Points Using Orthogonal Regression15.3.3 Planar Fitting of Points (x, y, f(x,y))15.3.4 Hyperplanar Fitting of Points Using Orthogonal Regression15.3.5 Fitting a Circle to 2D Points15.3.6 Fitting a Sphere to 3D Points15.3.7 Fitting a Quadratic Curve to 2D Points15.3.8 Fitting a Quadric Surface to 3D Points15.4 Minimization15.4.1 Methods in One Dimension15.4.2 Methods in Many Dimensions15.5 Root Finding15.5.1 Methods in One Dimension15.5.2 Methods in Many Dimensions15.6 Integration15.6.1 Romberg Integration15.6.2 Gaussian Quadrature15.7 Differential Equations15.7.1 Ordinary Differential Equations15.7.2 Partial Differential Equations15.8 Fast Function Evaluation15.8.1 Square Root and Inverse Square Root15.8.2 Sine, Cosine, and Tangent15.8.3 Inverse Tangent15.8.4 CORDIC Methods
