Contents
Preface xix
Introduction xxiii
Chapter 1
Real-World Computer Number Representation 1
1.1 Introduction 1
1.2 Representing Real Numbers 2
1.2.1 Approximations 2
1.2.2 Precision and Error 3
1.3 Floating-Point Numbers 4
1.3.1 Review: Scientific Notation 4
1.3.2 A Restricted Scientific Notation 5
1.4 Binary “Scientific Notation” 6
1.5 IEEE 754 Floating-Point Standard 9
1.5.1 Basic Representation 9
1.5.2 Range and Precision 11
1.5.3 Arithmetic Operations 13
1.5.4 Special Values 16
1.5.5 Very Small Values 19
1.5.6 Catastrophic Cancelation 22
1.5.7 Double Precision 24
1.6 Real-World Floating-Point 25
1.6.1 Internal FPU Precision 25
1.6.2 Performance 26
1.6.3 IEEE Specification Compliance 29
1.6.4 Graphics Processing Units and Half-Precision
Floating-Point Formats 31
1.7 Code 32
1.8 Chapter Summary 33
Chapter 2
Vectors and Points 35
2.1 Introduction 35
2.2 Vectors 36
2.2.1 Geometric Vectors 36
2.2.2 Linear Combinations 39
2.2.3 Vector Representation 40
2.2.4 Basic Vector Class Implementation 42
2.2.5 Vector Length 44
2.2.6 Dot Product 47
2.2.7 Gram-Schmidt Orthogonalization 51
2.2.8 Cross Product 53
2.2.9 Triple Products 56
2.2.10 Real Vector Spaces 59
2.2.11 Basis Vectors 62
2.3 Points 63
2.3.1 Points as Geometry 64
2.3.2 Affine Spaces 66
2.3.3 Affine Combinations 68
2.3.4 Point Implementation 70
2.3.5 Polar and Spherical Coordinates 72
2.4 Lines 75
2.4.1 Definition 75
2.4.2 Parameterized Lines 76
2.4.3 Generalized Line Equation 77
2.4.4 Collinear Points 79
2.5 Planes 80
2.5.1 Parameterized Planes 80
2.5.2 Generalized Plane Equation 80
2.5.3 Coplanar Points 82
2.6 Polygons and Triangles 82
2.7 Chapter Summary 86
Chapter 3
Matrices and Linear Transformations 87
3.1 Introduction 87
3.2 Matrices 88
3.2.1 Introduction to Matrices 88
3.2.2 Simple Operations 90
3.2.3 Vector Representation 92
3.2.4 Block Matrices 92
3.2.5 Matrix Product 94
3.2.6 Identity Matrix 96
3.2.7 Performing Vector Operations with Matrices 97
3.2.8 Implementation 98
3.3 Linear Transformations 101
3.3.1 Definitions 101
3.3.2 Null Space and Range 103
3.3.3 Linear Transformations and Basis Vectors 104
3.3.4 Matrices and Linear Transformations 106
3.3.5 Combining Linear Transformations 108
3.4 Systems of Linear Equations 110
3.4.1 Definition 110
3.4.2 Solving Linear Systems 112
3.4.3 Gaussian Elimination 113
3.5 Matrix Inverse 117
3.5.1 Definition 117
3.5.2 Simple Inverses 120
3.6 Determinant 121
3.6.1 Definition 121
3.6.2 Computing the Determinant 123
3.6.3 Determinants and Elementary Row Operations 126
3.6.4 Adjoint Matrix and Inverse 128
3.7 Eigenvalues and Eigenvectors 129
3.8 Chapter Summary 130
Chapter 4
Affine Transformations 133
4.1 Introduction 133
4.2 Affine Transformations 134
4.2.1 Matrix Definition 134
4.2.2 Formal Definition 136
4.2.3 Formal Representation 138
4.3 Standard Affine Transformations 139
4.3.1 Translation 139
4.3.2 Rotation 141
4.3.3 Scaling 150
4.3.4 Reflection 151
4.3.5 Shear 154
4.3.6 Applying an Affine Transformation Around an
Arbitrary Point 156
4.3.7 Transforming Plane Normals 158
4.4 Using Affine Transformations 159
4.4.1 Manipulation of Game Objects 159
4.4.2 Matrix Decomposition 164
4.4.3 Avoiding Matrix Decomposition 166
6.3 Projective Transformation 212
6.3.1 Definition 212
6.3.2 Normalized Device Coordinates 216
6.3.3 View Frustum 216
6.3.4 Homogeneous Coordinates 220
6.3.5 Perspective Projection 221
6.3.6 Oblique Perspective 228
6.3.7 Orthographic Parallel Projection 231
6.3.8 Oblique Parallel Projection 232
6.4 Culling and Clipping 235
6.4.1 Why Cull or Clip? 235
6.4.2 Culling 238
6.4.3 General Plane Clipping 239
6.4.4 Homogeneous Clipping 244
6.5 Screen Transformation 246
6.5.1 Pixel Aspect Ratio 248
6.6 Picking 249
6.7 Management of Viewing Transformations 252
6.8 Chapter Summary 254
Chapter 7
Geometry and Programmable Shading 255
7.1 Introduction 255
7.2 Color Representation 257
7.2.1 RGB Color Model 257
7.2.2 Colors as “Vectors” 257
7.2.3 Color Range Limitation 258
7.2.4 Operations on Colors 259
7.2.5 Alpha Values 260
7.2.6 Color Storage Formats 264
7.3 Points and Vertices 266
7.3.1 Per-Vertex Attributes 266
7.3.2 An Object’s Vertices 267
7.4 Surface Representation 270
7.4.1 Vertices and Surface Ambiguity 270
7.4.2 Triangles 271
7.4.3 Connecting Vertices into Triangles 271
7.4.4 Drawing Geometry 274
7.5 Rendering Pipeline 275
7.5.1 Fixed-Function versus Programmable Pipelines 277
7.6 Shaders 278
7.6.1 Using Shaders to Move from Vertex to Triangle
to Fragment 278
7.6.2 Shader Input and Output Values 279
7.6.3 Shader Operations and Language Constructs 280
7.7 Vertex Shaders 280
7.7.1 Vertex Shader Inputs 280
7.7.2 Vertex Shader Outputs 281
7.7.3 Basic Vertex Shaders 282
7.7.4 Linking Vertex and Fragment Shaders 282
7.8 Fragment Shaders 283
7.8.1 Fragment Shader Inputs 283
7.8.2 Fragment Shader Outputs 284
7.8.3 Compiling, Linking, and Using Shaders 284
7.8.4 Setting Uniform Values 286
7.9 Basic Coloring Methods 287
7.9.1 Per-Object Colors 288
7.9.2 Per-Vertex Colors 288
7.9.3 Per-Triangle Colors 290
7.9.4 Sharp Edges and Vertex Colors 290
7.9.5 More about Basic Shading 291
7.9.6 Limitations of Basic Shading Methods 292
7.10 Texture Mapping 292
7.10.1 Introduction 292
7.10.2 Shading via Image Lookup 293
7.10.3 Texture Images 294
7.10.4 Texture Samplers 297
7.11 Texture Coordinates 297
7.11.1 Mapping Texture Coordinates onto Objects 298
7.11.2 Generating Texture Coordinates 300
7.11.3 Texture Coordinate Discontinuities 301
7.11.4 Mapping Outside the Unit Square 302
7.11.5 Texture Samplers in Shader Code 309
7.12 The Steps of Texturing 309
7.12.1 Other Forms of Texture Coordinates 310
7.12.2 From Texture Coordinates to a Texture Sample Color 311
7.13 Limitations of Static Shading 312
7.14 Chapter Summary 313
Chapter 8
Lighting 315
8.1 Introduction 315
8.2 Basics of Light Approximation 316
8.2.1 Measuring Light 317
8.2.2 Light as a Ray 318
8.3 A Simple Approximation of Lighting 318
8.4 Types of Light Sources 319
8.4.1 Directional Lights 320
8.4.2 Point Lights 321
8.4.3 Spotlights 327
8.4.4 Other Types of Light Sources 330
8.5 Surface Materials and Light Interaction 331
8.6 Categories of Light 332
8.6.1 Emission 332
8.6.2 Ambient 332
8.6.3 Diffuse 334
8.6.4 Specular 338
8.7 Combined Lighting Equation 343
8.8 Lighting and Shading 348
8.8.1 Flat-Shaded Lighting 349
8.8.2 Per-Vertex Lighting 350
8.8.3 Per-Fragment Lighting 354
8.9 Textures and Lighting 358
8.9.1 Basic Modulation 359
8.9.2 Specular Lighting and Textures 360
8.9.3 Textures as Materials 362
8.10 Advanced Lighting 363
8.10.1 Normal Mapping 363
8.11 Reflective Objects 366
8.12 Shadows 367
8.13 Chapter Summary 368
Chapter 9
Rasterization 369
9.1 Introduction 369
9.2 Displays and Framebuffers 370
9.3 Conceptual Rasterization Pipeline 371
9.3.1 Rasterization Stages 372
9.4 Determining the Fragments: Pixels Covered by a Triangle 373
9.4.1 Fragments 373
9.4.2 Depth Complexity 373
9.4.3 Converting Triangles to Fragments 375
9.4.4 Handling Partial Fragments 376
9.5 Determining Visible Geometry 378
9.5.1 Depth Buffering 378
9.5.2 Depth Buffering in Practice 387
9.6 Computing Fragment Shader Inputs 388
9.6.1 Uniform Values 389
9.6.2 Per-Vertex Attributes 389
11.2 Probability 493
11.2.1 Basic Probability 494
11.2.2 Random Variables 497
11.2.3 Mean and Standard Deviation 501
11.2.4 Special Probability Distributions 502
11.3 Determining Randomness 505
11.3.1 Chi-Square Test 506
11.3.2 Spectral Test 512
11.4 Random Number Generators 513
11.4.1 Linear Congruential Methods 516
11.4.2 Lagged Fibonacci Methods 520
11.4.3 Carry Methods 521
11.4.4 Mersenne Twister 523
11.4.5 Conclusions 526
11.5 Special Applications 527
11.5.1 Integers and Ranges of Integers 527
11.5.2 Floating-Point Numbers 528
11.5.3 Nonuniform Distributions 528
11.5.4 Spherical Sampling 530
11.5.5 Disc Sampling 532
11.5.6 Noise and Turbulence 534
11.6 Chapter Summary 538
Chapter 12
Intersection Testing 541
12.1 Introduction 541
12.2 Closest Point and Distance Tests 542
12.2.1 Closest Point on Line to Point 542
12.2.2 Line–Point Distance 544
12.2.3 Closest Point on Line Segment to Point 545
12.2.4 Line Segment–Point Distance 546
12.2.5 Closest Points Between Two Lines 548
12.2.6 Line–Line Distance 550
12.2.7 Closest Points Between Two Line Segments 551
12.2.8 Line Segment–Line Segment Distance 553
12.2.9 General Linear Components 554
12.3 Object Intersection 554
12.3.1 Spheres 556
12.3.2 Axis-Aligned Bounding Boxes 563
12.3.3 Swept Spheres 571
12.3.4 Object-Oriented Boxes 576
12.3.5 Triangles 583
12.4 A Simple Collision System 588
12.4.1 Choosing a Base Primitive 589
12.4.2 Bounding Hierarchies 590
12.4.3 Dynamic Objects 591
12.4.4 Performance Improvements 593
12.4.5 Related Systems 596
12.4.6 Section Summary 599
12.5 Chapter Summary 599
Chapter 13
Rigid Body Dynamics 601
13.1 Introduction 601
13.2 Linear Dynamics 602
13.2.1 Moving with Constant Acceleration 602
13.2.2 Forces 605
13.2.3 Linear Momentum 606
13.2.4 Moving with Variable Acceleration 607
13.3 Numerical Integration 609
13.3.1 Definition 609
13.3.2 Euler’s Method 611
13.3.3 Runge-Kutta Methods 614
13.3.4 Verlet Integration 616
13.3.5 Implicit Methods 619
13.3.6 Semi-Implicit Methods 621
13.4 Rotational Dynamics 622
13.4.1 Definition 622
13.4.2 Orientation and Angular Velocity 622
13.4.3 Torque 625
13.4.4 Angular Momentum and Inertia Tensor 626
13.4.5 Integrating Rotational Quantities 628
13.5 Collision Response 630
13.5.1 Contact Generation 630
13.5.2 Linear Collision Response 634
13.5.3 Rotational Collision Response 638
13.5.4 Extending the System 640
13.6 Efficiency 643
13.7 Chapter Summary 645
Bibliography 647
Index 655
Trademarks 671
About the CD-Rom 672
Another Game Programming Books
Download
No comments:
Post a Comment