Essential Mathematics for Games and Interactive Applications

Description

Expert Guidance on the Math Needed for 3D Game Programming Developed from the authors’ popular Game Developers Conference (GDC) tutorial, Essential Mathematics for Games and Interactive Applications, Third Edition illustrates the importance of mathematics in 3D programming. It shows you how to properly animate, simulate, and render scenes and discusses the mathematics behind the processes. New to the Third Edition Completely revised to fix errors and make the content flow better, this third edition reflects the increased use of shader graphics pipelines, such as in DirectX 11, OpenGL ES (GLES), and the OpenGL Core Profile. It also updates the material on real-time graphics with coverage of more realistic materials and lighting. The Foundation for Successful 3D Programming The book covers the low-level mathematical and geometric representations and algorithms that are the core of any game engine. It also explores all the stages of the rendering pipeline. The authors explain how to represent, transform, view, and animate geometry. They then focus on visual matters, specifically the representation, computation, and use of color. They also address randomness, intersecting geometric entities, and physical simulation. An Introduction to Creating Real and Active Virtual Worlds This updated book provides you with a conceptual understanding of the mathematics needed to create 3D games as well as a practical understanding of how these mathematical bases actually apply to games and graphics. It not only includes the theoretical mathematical background but also incorporates many examples of how the concepts are used to affect how a game looks and plays. Web Resource A supplementary website contains a collection of source code, supporting libraries, and interactive demonstrations that illustrate the concepts and enable you to experiment with animation and simulation applications. The site also includes slides and notes from the authors’ GDC tutorials. Front Cover Dedication Contents Preface The Adventure Begins The Adventure Continues The Adventurers Resume the Quest Those Who Helped Us along the Road Authors Introduction The (Continued) Rise of 3D Games How to Read This Book Interactive Demo Applications and Support Libraries Supplementary Material References and Further Reading Chapter 1. Representing Real Numbers 1.1 Introduction 1.2 Preliminary Concepts 1.2.1 Fixed-Point Numbers 1.2.2 Approximations 1.2.3 Precision and Error 1.3 Floating-Point Numbers 1.3.1 Review: Scientific Notation 1.3.2 Restricted Scientific Notation 1.3.3 Binary Scientific Notation 1.4 IEEE 754 Floating-Point Standard 1.4.1 Basic Representation 1.4.2 Range and Precision 1.4.3 Arithmetic Operations 1.4.4 Special Values 1.4.5 Very Small Values 1.4.6 Catastrophic Cancelation 1.4.7 Comparing Floating-Point Numbers 1.4.8 Double Precision 1.4.9 Half Precision 1.5 Real-World Floating Point 1.5.1 Internal FPU Precision 1.5.2 Performance 1.5.3 IEEE Specification Compliance 1.5.4 Precision in Graphics Processing Units 1.6 Code 1.7 Chapter Summary Chapter 2. Vectors and Points 2.1 Introduction 2.2 Vectors 2.2.1 Geometric Vectors 2.2.2 Real Vector Spaces 2.2.3 Linear Combinations and Basis Vectors 2.2.4 Basic Vector Class Implementation 2.2.5 Vector Length 2.2.6 Dot Product 2.2.7 Gram–Schmidt Orthogonalization 2.2.8 Cross Product 2.2.9 Triple Products 2.2.10 Grassman Algebra 2.3 Points 2.3.1 Points as Geometry 2.3.2 Affine Spaces 2.3.3 Affine Combinations 2.3.4 Point Implementation 2.3.5 Polar and Spherical Coordinates 2.4 Lines 2.4.1 Definition 2.4.2 Parameterized Lines 2.4.3 Generalized Line Equation 2.4.4 Collinear Points 2.5 Planes 2.5.1 Parameterized Planes 2.5.2 Generalized Plane Equation 2.5.3 Coplanar Points 2.6 Polygons and Triangles 2.7 Chapter Summary Chapter 3. Linear Transformations and Matrices 3.1 Introduction 3.2 Linear Transformations 3.2.1 Definitions 3.2.2 Linear Transformations and Basis Vectors 3.2.3 Range and Null Space 3.3 Matrices 3.3.1 Introduction to Matrices 3.3.2 Simple Operations 3.3.3 Vector Representation 3.3.4 Block Matrices 3.3.5 Matrix Product 3.3.6 Transforming Vectors 3.3.7 Combining Linear Transformations 3.3.8 Identity Matrix 3.3.9 Performing Vector Operations with Matrices 3.3.10 Implementation 3.4 Systems of Linear Equations 3.4.1 Definition 3.4.2 Solving Linear Systems 3.4.3 Gaussian Elimination 3.5 Matrix Inverse 3.5.1 Definition 3.5.2 Simple Inverses 3.6 Determinant 3.6.1 Definition 3.6.2 Computing the Determinant 3.6.3 Determinants and Elementary Row Operations 3.6.4 Adjoint Matrix and Inverse 3.7 Eigenvalues and Eigenvectors 3.8 Chapter Summary Chapter 4. Affine Transformations 4.1 Introduction 4.2 Affine Transformations 4.2.1 Matrix Definition 4.2.2 Formal Definition 4.2.3 Formal Representation 4.3 Standard Affine Transformations 4.3.1 Translation 4.3.2 Rotation 4.3.3 Scaling 4.3.4 Reflection 4.3.5 Shear 4.3.6 Applying an Affine Transformation around an Arbitrary Point 4.3.7 Transforming Plane Normals 4.4 Using Affine Transformations 4.4.1 Manipulation of Game Objects 4.4.2 Matrix Decomposition 4.4.3 Avoiding Matrix Decomposition 4.5 Object Hierarchies 4.6 Chapter Summary Chapter 5. Orientation Representation 5.1 Introduction 5.2 Rotation Matrices 5.3 Euler Angles 5.3.1 Definition 5.3.2 Format Conversion 5.3.3 Concatenation 5.3.4 Vector Rotation 5.3.5 Other Issues 5.4 Axis–Angle Representation 5.4.1 Definition 5.4.2 Format Conversion 5.4.3 Concatenation 5.4.4 Vector Rotation 5.4.5 Axis–Angle Summary 5.5 Quaternions 5.5.1 Definition 5.5.2 Quaternions as Rotations 5.5.3 Addition and Scalar Multiplication 5.5.4 Negation 5.5.5 Magnitude and Normalization 5.5.6 Dot Product 5.5.7 Format Conversion 5.5.8 Concatenation 5.5.9 Identity and Inverse 5.5.10 Vector Rotation 5.5.11 Shortest Path of Rotation 5.5.12 Quaternions and Transformations 5.6 Chapter Summary Chapter 6. Interpolation 6.1 Introduction 6.2 Interpolation of Position 6.2.1 General Definitions 6.2.2 Linear Interpolation 6.2.3 Hermite Curves 6.2.4 Catmull–Rom Splines 6.2.5 Kochanek–Bartels Splines 6.2.6 Bézier Curves S 6.2.7 Other Curve Types 6.3 Interpolation of Orientation 6.3.1 General Discussion 6.3.2 Linear Interpolation 6.3.3 Spherical Linear Interpolation 6.3.4 Performance Improvements 6.4 Sampling Curves 6.4.1 Forward Differencing 6.4.2 Midpoint Subdivision 6.4.3 Computing Arc Length 6.5 Controlling Speed along a Curve 6.5.1 Moving at Constant Speed 6.5.2 Moving at Variable Speed 6.6 Camera Control 6.7 Chapter Summary Chapter 7, Viewing and Projection 7.1 Introduction 7.2 View Frame and View Transformation 7.2.1 Defining a Virtual Camera 7.2.2 Constructing the View-to-World Transformation 7.2.3 Controlling the Camera 7.2.4 Constructing the World-to-View Transformation 7.3 Projective Transformation 7.3.1 Definition 7.3.2 Normalized Device Coordinates 7.3.3 View Frustum 7.3.4 Homogeneous Coordinates 7.3.5 Perspective Projection 7.3.6 Oblique Perspective 7.3.7 Orthographic Parallel Projection 7.3.8 Oblique Parallel Projection 7.4 Culling and Clipping 7.4.1 Why Cull or Clip? 7.4.2 Culling 7.4.3 General Plane Clipping 7.4.4 Homogeneous Clipping 7.4.5 Extracting Clip Planes 7.5 Screen Transformation 7.5.1 Pixel Aspect Ratio 7.6 Picking 7.7 Management of Viewing Transformations 7.8 Chapter Summary Chapter 8. Geometry and Programmable Shading 8.1 Introduction 8.2 Color Representation 8.2.1 RGB Color Model 8.2.2 Colors as “Points” 8.2.3 Color-Range Limitation 8.2.4 Operations on Colors 8.2.5 Alpha Values 8.2.6 Remapping Colors into the Unit Cube 8.2.7 Color Storage Formats 8.2.8 Nonlinear Color 8.3 Points and Vertices 8.3.1 Per-Vertex Attributes 8.3.2 An Object's Vertices 8.4 Surface Representation 8.4.1 Vertices and Surface Ambiguity 8.4.2 Triangles 8.4.3 Connecting Vertices into Triangles 8.4.4 Drawing Geometry 8.5 Rendering Pipeline 8.5.1 Fixed-Function versus Programmable Pipelines 8.6 Shaders 8.6.1 Using Shaders to Move from Vertex to Triangle to Fragment 8.6.2 Shader Input and Output Values 8.6.3 Shader Operations and Language Constructs 8.6.4 Other Shader Types 8.7 Vertex Shaders 8.7.1 Vertex Shader Inputs 8.7.2 Vertex Shader Outputs 8.7.3 Basic Vertex Shaders 8.8 Fragment Shaders 8.8.1 Fragment Shader Inputs 8.8.2 Fragment Shader Outputs 8.8.3 Linking Vertex and Fragment Shaders 8.8.4 Compiling, Linking, and Using Shaders 8.8.5 Setting Uniform Values 8.9 Basic Coloring Methods 8.9.1 Per-Object Colors 8.9.2 Per-Triangle Colors 8.9.3 Per-Vertex Colors 8.9.4 Sharp Edges and Vertex Colors 8.9.5 Limitations of Basic Shading Methods 8.10 Texture Mapping 8.10.1 Introduction 8.10.2 Shading via Image Lookup 8.10.3 Texture Images 8.10.4 Texture Samplers 8.11 Texture Coordinates 8.11.1 Mapping Texture Coordinates onto Objects 8.11.2 Generating Texture Coordinates 8.11.3 Texture Coordinate Discontinuities 8.11.4 Mapping Outside the Unit Square 8.11.5 Texture Samplers in Shader Code 8.12 Steps of Texturing 8.12.1 Other Forms of Texture Coordinates 8.12.2 From Texture Coordinates to a Texture Sample Color 8.13 Limitations of Static Shading 8.14 Chapter Summary Chapter 9. Lighting 9.1 Introduction 9.2 Basics of Light Approximation 9.3 Measuring Light 9.4 Types of Light Sources 9.4.1 Point Lights 9.4.2 Spotlights 9.4.3 Directional Lights 9.4.4 Ambient Lights 9.4.5 Other Types of Light Sources 9.5 Surface Materials and Light Interaction 9.5.1 Diffuse 9.5.2 Specular 9.5.3 Emission 9.5.4 Ambient 9.5.5 Combined Lighting Equation 9.6 Lighting and Shading 9.6.1 Flat-Shaded Lighting 9.6.2 Per-Vertex Lighting 9.6.3 Per-Fragment Lighting 9.7 Textures and Lighting 9.7.1 Basic Modulation 9.7.2 Specular Lighting and Textures 9.7.3 Textures as Materials 9.8 Advanced Lighting 9.8.1 Normal Mapping 9.8.2 Reflective Objects 9.8.3 Transparent Objects 9.8.4 Area Lights 9.8.5 Physically Based Lighting 9.8.6 High Dynamic Range Lighting 9.8.7 Deferred Lighting and Shading 9.8.8 Shadows 9.9 Chapter Summary 10.1 Introduction 10.2 Displays and Framebuffers 10.3 Conceptual Rasterization Pipeline 10.3.1 Rasterization Stages 10.4 Determining the Fragments: Pixels Covered by a Triangle 10.4.1 Fragments 10.4.2 Depth Complexity 10.4.3 Converting Triangles to Fragments 10.4.4 Handling Partial Fragments 10.5 Determining Visible Geometry 10.5.1 Depth Buffering 10.5.2 Depth Buffering in Practice 10.6 Computing Fragment Shader Inputs 10.6.1 Uniform Values 10.6.2 Per-Vertex Attributes 10.6.3 Indirect Per-Fragment Values 10.7 Rasterizing Textures 10.7.1 Texture Coordinate Review 10.7.2 Mapping a Coordinate to a Texel 10.7.3 Mipmapping 10.8 From Fragments to Pixels 10.8.1 Pixel Blending 10.8.2 Antialiasing 10.8.3 Antialiasing in Practice 10.9 Chapter Summary 11.1 Introduction 11.2 Probability 11.2.1 Basic Probability 11.2.2 Random Variables 11.2.3 Mean and Standard Deviation 11.2.4 Special Probability Distributions 11.3 Determining Randomness 11.3.1 Chi-Square Test 11.3.2 Spectral Test 11.4 Random Number Generators 11.4.1 Linear Congruential Methods 11.4.2 Lagged Fibonacci Methods 11.4.3 Carry Methods 11.4.4 Xorshift 11.4.5 Other Alternatives 11.4.6 Setting Initial State 11.4.7 Conclusions 11.5 Special Applications 11.5.1 Integers and Ranges of Integers 11.5.2 Floating-Point Numbers 11.5.3 Shuffling 11.5.4 Nonuniform Distributions 11.5.5 Spherical Sampling 11.5.6 Disc Sampling 11.5.7 Noise and Turbulence 11.6 Chapter Summary 12.1 Introduction 12.2 Closest Point and Distance Tests 12.2.1 Closest Point on Line to Point 12.2.2 Line–Point Distance 12.2.3 Closest Point on Line Segment to Point 12.2.4 Line Segment–Point Distance 12.2.5 Closest Points between Two Lines 12.2.6 Line–Line Distance 12.2.7 Closest Points between Two Line Segments 12.2.8 Line Segment–Line Segment Distance 12.2.9 General Linear Components 12.3 Object Intersection 12.3.1 Spheres 12.3.2 Axis-Aligned Bounding Boxes 12.3.3 Swept Spheres 12.3.4 Object-Oriented Boxes 12.3.5 Triangles 12.4 A Simple Collision System 12.4.1 Choosing a Base Primitive 12.4.2 Bounding Hierarchies 12.4.3 Dynamic Objects 12.4.4 Performance Improvements 12.4.5 Related Systems 12.4.6 Section Summary 12.5 Chapter Summary 13.1 Introduction 13.2 Linear Dynamics 13.2.1 Moving with Constant Acceleration 13.2.2 Forces 13.2.3 Linear Momentum 13.2.4 Moving with Variable Acceleration 13.3 Numerical Integration 13.3.1 Definition 13.3.2 Euler's Method 13.3.3 Runge–Kutta Methods 13.3.4 Verlet Integration 13.3.5 Implicit Methods 13.3.6 Semi-Implicit Methods 13.4 Rotational Dynamics 13.4.1 Definition 13.4.2 Orientation and Angular Velocity 13.4.3 Torque 13.4.4 Angular Momentum and Inertia Tensor 13.4.5 Integrating Rotational Quantities 13.5 Collision Response 13.5.1 Contact Generation 13.5.2 Linear Collision Response 13.5.3 Rotational Collision Response 13.5.4 Extending the System 13.6 Efficiency 13.7 Chapter Summary Chapter 10. Rasterization 10.1 Introduction 10.2 Displays and Framebuffers 10.3 Conceptual Rasterization Pipeline 10.3.1 Rasterization Stages 10.4 Determining the Fragments: Pixels Covered by a Triangle 10.4.1 Fragments 10.4.2 Depth Complexity 10.4.3 Converting Triangles to Fragments 10.4.4 Handling Partial Fragments 10.5 Determining Visible Geometry 10.5.1 Depth Buffering 10.5.2 Depth Buffering in Practice 10.6 Computing Fragment Shader Inputs 10.6.1 Uniform Values 10.6.2 Per-Vertex Attributes 10.6.3 Indirect Per-Fragment Values 10.7 Rasterizing Textures 10.7.1 Texture Coordinate Review 10.7.2 Mapping a Coordinate to a Texel 10.7.3 Mipmapping 10.8 From Fragments to Pixels 10.8.1 Pixel Blending 10.8.2 Antialiasing 10.8.3 Antialiasing in Practice 10.9 Chapter Summary Chapter 11. Random Numbers 11.1 Introduction 11.2 Probability 11.2.1 Basic Probability 11.2.2 Random Variables 11.2.3 Mean and Standard Deviation 11.2.4 Special Probability Distributions 11.3 Determining Randomness 11.3.1 Chi-Square Test 11.3.2 Spectral Test 11.4 Random Number Generators 11.4.1 Linear Congruential Methods 11.4.2 Lagged Fibonacci Methods 11.4.3 Carry Methods 11.4.4 Xorshift 11.4.5 Other Alternatives 11.4.6 Setting Initial State 11.4.7 Conclusions 11.5 Special Applications 11.5.1 Integers and Ranges of Integers 11.5.2 Floating-Point Numbers 11.5.3 Shuffling 11.5.4 Nonuniform Distributions 11.5.5 Spherical Sampling 11.5.6 Disc Sampling 11.5.7 Noise and Turbulence 11.6 Chapter Summary Chapter 12. Intersection Testing 12.1 Introduction 12.2 Closest Point and Distance Tests 12.2.1 Closest Point on Line to Point 12.2.2 Line–Point Distance 12.2.3 Closest Point on Line Segment to Point 12.2.4 Line Segment–Point Distance 12.2.5 Closest Points between Two Lines 12.2.6 Line–Line Distance 12.2.7 Closest Points between Two Line Segments 12.2.8 Line Segment–Line Segment Distance 12.2.9 General Linear Components 12.3 Object Intersection 12.3.1 Spheres 12.3.2 Axis-Aligned Bounding Boxes 12.3.3 Swept Spheres 12.3.4 Object-Oriented Boxes 12.3.5 Triangles 12.4 A Simple Collision System 12.4.1 Choosing a Base Primitive 12.4.2 Bounding Hierarchies 12.4.3 Dynamic Objects 12.4.4 Performance Improvements 12.4.5 Related Systems 12.4.6 Section Summary 12.5 Chapter Summary Chapter 13. Rigid-Body Dynamics 13.1 Introduction 13.2 Linear Dynamics 13.2.1 Moving with Constant Acceleration 13.2.2 Forces 13.2.3 Linear Momentum 13.2.4 Moving with Variable Acceleration 13.3 Numerical Integration 13.3.1 Definition 13.3.2 Euler's Method 13.3.3 Runge–Kutta Methods 13.3.4 Verlet Integration 13.3.5 Implicit Methods 13.3.6 Semi-Implicit Methods 13.4 Rotational Dynamics 13.4.1 Definition 13.4.2 Orientation and Angular Velocity 13.4.3 Torque 13.4.4 Angular Momentum and Inertia Tensor 13.4.5 Integrating Rotational Quantities 13.5 Collision Response 13.5.1 Contact Generation 13.5.2 Linear Collision Response 13.5.3 Rotational Collision Response 13.5.4 Extending the System 13.6 Efficiency 13.7 Chapter Summary References Back Cover