Contents
Preface xiii
1 Introduction 1
1.1 Contents Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Notation and De»nitions . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Mathematical Notation . . . . . . . . . . . . . . . . . . . 4
1.2.2 Geometrical De»nitions . . . . . . . . . . . . . . . . . . . 7
2 The Graphics Rendering Pipeline 9
2.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 The Application Stage . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 The Geometry Stage . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Model and View Transform . . . . . . . . . . . . . . . . . 13
2.3.2 Vertex Shading . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.3 Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.4 Clipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.5 Screen Mapping . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 The Rasterizer Stage . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Triangle Setup . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 Triangle Traversal . . . . . . . . . . . . . . . . . . . . . . 20
2.4.3 Pixel Shading . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.4 Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Through the Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 The Graphics Processing Unit 25
3.1 GPU Pipeline Overview . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 The Programmable Shader Stage . . . . . . . . . . . . . . . . . . 26
3.3 The Evolution of Programmable Shading . . . . . . . . . . . . . 29
3.3.1 Comparison of Shader Models . . . . . . . . . . . . . . . . 32
3.4 The Vertex Shader . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5 The Geometry Shader . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5.1 Stream Output . . . . . . . . . . . . . . . . . . . . . . . . 37
3.6 The Pixel Shader . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.7 The Merging Stage . . . . . . . . . . . . . . . . . . . . . . . . . . 39
iii
iv CONTENTS
3.8 E«ects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4 Transforms 47
4.1 Basic Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.1 Translation . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.1.2 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.1.3 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.1.4 Shearing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1.5 Concatenation of Transforms . . . . . . . . . . . . . . . . 55
4.1.6 The Rigid-Body Transform . . . . . . . . . . . . . . . . . 56
4.1.7 Normal Transform . . . . . . . . . . . . . . . . . . . . . . 57
4.1.8 Computation of Inverses . . . . . . . . . . . . . . . . . . . 58
4.2 Special Matrix Transforms and Operations . . . . . . . . . . . . . 59
4.2.1 The Euler Transform . . . . . . . . . . . . . . . . . . . . . 59
4.2.2 Extracting Parameters from the Euler Transform . . . . . 61
4.2.3 Matrix Decomposition . . . . . . . . . . . . . . . . . . . . 62
4.2.4 Rotation about an Arbitrary Axis . . . . . . . . . . . . . 63
4.3 Quaternions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.1 Mathematical Background . . . . . . . . . . . . . . . . . . 65
4.3.2 Quaternion Transforms . . . . . . . . . . . . . . . . . . . 67
4.4 Vertex Blending . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.5 Morphing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.6 Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.6.1 Orthographic Projection . . . . . . . . . . . . . . . . . . . 80
4.6.2 Perspective Projection . . . . . . . . . . . . . . . . . . . . 84
5 Visual Appearance 91
5.1 Visual Phenomena . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2 Light Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.3 Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4 Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.5 Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.5.1 Implementing the Shading Equation . . . . . . . . . . . . 105
5.6 Aliasing and Antialiasing . . . . . . . . . . . . . . . . . . . . . . 109
5.6.1 Sampling and Filtering Theory . . . . . . . . . . . . . . . 109
5.6.2 Screen-Based Antialiasing . . . . . . . . . . . . . . . . . . 117
5.7 Transparency, Alpha, and Compositing . . . . . . . . . . . . . . . 126
5.8 Gamma Correction . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6 Texturing 139
6.1 The Texturing Pipeline . . . . . . . . . . . . . . . . . . . . . . . 140
6.1.1 The Projector Function . . . . . . . . . . . . . . . . . . . 142
6.1.2 The Corresponder Function . . . . . . . . . . . . . . . . . 146
6.1.3 Texture Values . . . . . . . . . . . . . . . . . . . . . . . . 148
6.2 Image Texturing . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.2.1 Magni»cation . . . . . . . . . . . . . . . . . . . . . . . . . 149
CONTENTS v
6.2.2 Mini»cation . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.2.3 Volume Textures . . . . . . . . . . . . . . . . . . . . . . . 161
6.2.4 Cube Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.2.5 Texture Caching . . . . . . . . . . . . . . . . . . . . . . . 163
6.2.6 Texture Compression . . . . . . . . . . . . . . . . . . . . . 164
6.3 Procedural Texturing . . . . . . . . . . . . . . . . . . . . . . . . . 169
6.4 Texture Animation . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.5 Material Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . 172
6.6 Alpha Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
6.7 Bump Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.7.1 Blinn's Methods . . . . . . . . . . . . . . . . . . . . . . . 177
6.7.2 Normal Mapping . . . . . . . . . . . . . . . . . . . . . . . 178
6.7.3 Parallax Mapping . . . . . . . . . . . . . . . . . . . . . . 181
6.7.4 Relief Mapping . . . . . . . . . . . . . . . . . . . . . . . . 182
6.7.5 Height»eld Texturing . . . . . . . . . . . . . . . . . . . . 187
7 Advanced Shading 191
7.1 Radiometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
7.2 Photometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.3 Colorimetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
7.4 Light Source Types . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.4.1 Omni Lights . . . . . . . . . . . . . . . . . . . . . . . . . 208
7.4.2 Spotlights . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.4.3 Textured Lights . . . . . . . . . . . . . . . . . . . . . . . . 211
7.4.4 Other Light Sources . . . . . . . . . . . . . . . . . . . . . 212
7.5 BRDF Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7.5.1 The BRDF . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7.5.2 Surface and Body Re°ectance . . . . . . . . . . . . . . . . 219
7.5.3 Fresnel Re°ectance . . . . . . . . . . . . . . . . . . . . . . 219
7.5.4 Local Sub-Surface Scattering . . . . . . . . . . . . . . . . 228
7.5.5 Microgeometry . . . . . . . . . . . . . . . . . . . . . . . . 230
7.5.6 Microfacet Theory . . . . . . . . . . . . . . . . . . . . . . 235
7.5.7 Half Vector vs. Re°ection Vector . . . . . . . . . . . . . . 239
7.6 BRDF Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
7.7 BRDF Acquisition and Representation . . . . . . . . . . . . . . . 254
7.7.1 Acquiring BRDFs . . . . . . . . . . . . . . . . . . . . . . 254
7.7.2 Representations for Measured BRDFs . . . . . . . . . . . 254
7.8 Implementing BRDFs . . . . . . . . . . . . . . . . . . . . . . . . 258
7.8.1 Mipmapping BRDF and Normal Maps . . . . . . . . . . . 259
7.9 Combining Lights and Materials . . . . . . . . . . . . . . . . . . 264
7.9.1 Multipass Lighting . . . . . . . . . . . . . . . . . . . . . . 265
7.9.2 Deferred Shading . . . . . . . . . . . . . . . . . . . . . . . 267
vi CONTENTS
8 Area and Environmental Lighting 273
8.1 Radiometry for Arbitrary Lighting . . . . . . . . . . . . . . . . . 275
8.2 Area Light Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 276
8.3 Ambient Light . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
8.4 Environment Mapping . . . . . . . . . . . . . . . . . . . . . . . . 284
8.4.1 Blinn and Newell's Method . . . . . . . . . . . . . . . . . 288
8.4.2 Sphere Mapping . . . . . . . . . . . . . . . . . . . . . . . 289
8.4.3 Cubic Environment Mapping . . . . . . . . . . . . . . . . 292
8.4.4 Parabolic Mapping . . . . . . . . . . . . . . . . . . . . . . 296
8.5 Glossy Re°ections from Environment Maps . . . . . . . . . . . . 297
8.5.1 View-Dependent Re°ection Maps . . . . . . . . . . . . . . 301
8.6 Irradiance Environment Mapping . . . . . . . . . . . . . . . . . . 302
8.6.1 Spherical Harmonics Irradiance . . . . . . . . . . . . . . . 305
8.6.2 Fill Lights . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
8.6.3 Other Irradiance Representations . . . . . . . . . . . . . . 312
9 Global Illumination 315
9.1 Shadows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
9.1.1 Planar Shadows . . . . . . . . . . . . . . . . . . . . . . . . 320
9.1.2 Shadows on Curved Surfaces . . . . . . . . . . . . . . . . 326
9.1.3 Shadow Volumes . . . . . . . . . . . . . . . . . . . . . . . 328
9.1.4 Shadow Map . . . . . . . . . . . . . . . . . . . . . . . . . 335
9.1.5 Shadow Optimizations . . . . . . . . . . . . . . . . . . . . 360
9.2 Ambient Occlusion . . . . . . . . . . . . . . . . . . . . . . . . . . 361
9.2.1 Ambient Occlusion Theory . . . . . . . . . . . . . . . . . 361
9.2.2 Shading with Ambient Occlusion . . . . . . . . . . . . . . 363
9.2.3 Visibility and Obscurance . . . . . . . . . . . . . . . . . . 365
9.2.4 Accounting for Interre°ections . . . . . . . . . . . . . . . 366
9.2.5 Dynamic Computation of Ambient Occlusion . . . . . . . 367
9.3 Re°ections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
9.3.1 Planar Re°ections . . . . . . . . . . . . . . . . . . . . . . 372
9.3.2 Re°ections from Curved Re°ectors . . . . . . . . . . . . . 378
9.4 Transmittance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
9.5 Refractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
9.6 Caustics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
9.7 Global Sub-Surface Scattering . . . . . . . . . . . . . . . . . . . . 388
9.8 Full Global Illumination . . . . . . . . . . . . . . . . . . . . . . . 388
9.8.1 Radiosity . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
9.8.2 Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . 393
9.8.3 Other Global Illumination Techniques . . . . . . . . . . . 395
9.9 Precomputed Lighting . . . . . . . . . . . . . . . . . . . . . . . . 395
9.9.1 Simple Surface Prelighting . . . . . . . . . . . . . . . . . . 397
9.9.2 Directional Surface Prelighting . . . . . . . . . . . . . . . 398
9.9.3 Volume Prelighting . . . . . . . . . . . . . . . . . . . . . . 402
9.10 Precomputed Occlusion . . . . . . . . . . . . . . . . . . . . . . . 403
9.10.1 Precomputed Ambient Occlusion . . . . . . . . . . . . . . 403
CONTENTS vii
9.10.2 Precomputed Directional Occlusion . . . . . . . . . . . . . 403
9.11 Precomputed Radiance Transfer . . . . . . . . . . . . . . . . . . 403
10 Image-Based E«ects 407
10.1 The Rendering Spectrum . . . . . . . . . . . . . . . . . . . . . . 407
10.2 Fixed-View E«ects . . . . . . . . . . . . . . . . . . . . . . . . . . 408
10.3 Skyboxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
10.4 Light Field Rendering . . . . . . . . . . . . . . . . . . . . . . . . 411
10.5 Sprites and Layers . . . . . . . . . . . . . . . . . . . . . . . . . . 412
10.6 Billboarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
10.6.1 Screen-Aligned Billboard . . . . . . . . . . . . . . . . . . 415
10.6.2 World-Oriented Billboard . . . . . . . . . . . . . . . . . . 416
10.6.3 Axial Billboard . . . . . . . . . . . . . . . . . . . . . . . . 421
10.7 Particle Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
10.7.1 Impostors . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
10.7.2 Billboard Clouds . . . . . . . . . . . . . . . . . . . . . . . 429
10.8 Displacement Techniques . . . . . . . . . . . . . . . . . . . . . . 429
10.9 Image Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
10.10Color Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
10.11Tone Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
10.11.1 High Dynamic Range Imaging and Lighting . . . . . . . . 446
10.12Lens Flare and Bloom . . . . . . . . . . . . . . . . . . . . . . . . 448
10.13Depth of Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
10.14Motion Blur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
10.15Fog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
10.16Volume Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . 467
10.16.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 469
11 Non-Photorealistic Rendering 473
11.1 Toon Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
11.2 Silhouette Edge Rendering . . . . . . . . . . . . . . . . . . . . . . 477
11.2.1 Surface Angle Silhouetting . . . . . . . . . . . . . . . . . 478
11.2.2 Procedural Geometry Silhouetting . . . . . . . . . . . . . 480
11.2.3 Silhouetting by Image Processing . . . . . . . . . . . . . . 484
11.2.4 Silhouette Edge Detection . . . . . . . . . . . . . . . . . . 485
11.2.5 Hybrid Silhouetting . . . . . . . . . . . . . . . . . . . . . 488
11.3 Other Styles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
11.4 Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
11.4.1 Edge Highlighting . . . . . . . . . . . . . . . . . . . . . . 493
11.4.2 Polygon Edge Rendering . . . . . . . . . . . . . . . . . . . 493
11.4.3 Hidden-Line Rendering . . . . . . . . . . . . . . . . . . . 494
11.4.4 Haloing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
viii CONTENTS
12 Polygonal Techniques 497
12.1 Sources of Three-Dimensional Data . . . . . . . . . . . . . . . . . 498
12.2 Tessellation and Triangulation . . . . . . . . . . . . . . . . . . . . 500
12.2.1 Shading Problems . . . . . . . . . . . . . . . . . . . . . . 503
12.2.2 Edge Cracking and T-Vertices . . . . . . . . . . . . . . . . 505
12.3 Consolidation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
12.3.1 Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
12.3.2 Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . 508
12.3.3 Solidity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
12.3.4 Normal Smoothing and Crease Edges . . . . . . . . . . . 510
12.4 Triangle Fans, Strips, and Meshes . . . . . . . . . . . . . . . . . . 513
12.4.1 Fans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
12.4.2 Strips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
12.4.3 Creating Strips . . . . . . . . . . . . . . . . . . . . . . . . 516
12.4.4 Triangle Meshes . . . . . . . . . . . . . . . . . . . . . . . 519
12.4.5 Vertex and Index Bu«ers/Arrays . . . . . . . . . . . . . . 522
12.5 Simpli»cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
12.5.1 Dynamic Simpli»cation . . . . . . . . . . . . . . . . . . . 527
12.5.2 View-Dependent Simpli»cation . . . . . . . . . . . . . . . 533
13 Curves and Curved Surfaces 539
13.1 Parametric Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 540
13.1.1 B¶ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . 541
13.1.2 Bounded B¶ezier Curves on the GPU . . . . . . . . . . . . 547
13.1.3 Continuity and Piecewise B¶ezier Curves . . . . . . . . . . 548
13.1.4 Cubic Hermite Interpolation . . . . . . . . . . . . . . . . 551
13.1.5 Kochanek-Bartels Curves . . . . . . . . . . . . . . . . . . 553
13.2 Parametric Curved Surfaces . . . . . . . . . . . . . . . . . . . . . 555
13.2.1 B¶ezier Patches . . . . . . . . . . . . . . . . . . . . . . . . 555
13.2.2 B¶ezier Triangles . . . . . . . . . . . . . . . . . . . . . . . 559
13.2.3 N-Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
13.2.4 Continuity . . . . . . . . . . . . . . . . . . . . . . . . . . 566
13.3 Implicit Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
13.4 Subdivision Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 570
13.5 Subdivision Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . 573
13.5.1 Loop Subdivision . . . . . . . . . . . . . . . . . . . . . . . 575
13.5.2 Modi»ed Butter°y Subdivision . . . . . . . . . . . . . . . 579
13.5.3 p3-Subdivision . . . . . . . . . . . . . . . . . . . . . . . . 584
13.5.4 Catmull-Clark Subdivision . . . . . . . . . . . . . . . . . 586
13.5.5 Piecewise Smooth Subdivision . . . . . . . . . . . . . . . . 587
13.5.6 Displaced Subdivision . . . . . . . . . . . . . . . . . . . . 589
13.5.7 Normal, Texture, and Color Interpolation . . . . . . . . . 591
13.6 E±cient Tessellation . . . . . . . . . . . . . . . . . . . . . . . . . 592
13.6.1 Hardware Tessellation Pipeline . . . . . . . . . . . . . . . 592
13.6.2 Fractional Tessellation . . . . . . . . . . . . . . . . . . . . 593
13.6.3 Vertex + Evaluation Shader . . . . . . . . . . . . . . . . . 596
CONTENTS ix
13.6.4 Adaptive Tessellation . . . . . . . . . . . . . . . . . . . . 597
13.6.5 Catmull-Clark Surfaces with Hardware Tessellation . . . . 601
14 Acceleration Algorithms 607
14.1 Spatial Data Structures . . . . . . . . . . . . . . . . . . . . . . . 608
14.1.1 Bounding Volume Hierarchies . . . . . . . . . . . . . . . . 609
14.1.2 BSP Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
14.1.3 Octrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615
14.1.4 Cache-Oblivious and Cache-Aware Representations . . . . 618
14.1.5 Scene Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 619
14.2 Culling Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 621
14.2.1 Backface Culling . . . . . . . . . . . . . . . . . . . . . . . 622
14.3 Hierarchical View Frustum Culling . . . . . . . . . . . . . . . . . 625
14.4 Portal Culling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
14.5 Detail Culling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
14.6 Occlusion Culling . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
14.6.1 Hardware Occlusion Queries . . . . . . . . . . . . . . . . . 634
14.6.2 Hierarchical Z-Bu«ering . . . . . . . . . . . . . . . . . . . 637
14.6.3 Other Occlusion Culling Techniques . . . . . . . . . . . . 639
14.7 Level of Detail . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640
14.7.1 LOD Switching . . . . . . . . . . . . . . . . . . . . . . . . 641
14.7.2 LOD Selection . . . . . . . . . . . . . . . . . . . . . . . . 648
14.7.3 Time-Critical LOD Rendering . . . . . . . . . . . . . . . . 651
14.8 Large Model Rendering . . . . . . . . . . . . . . . . . . . . . . . 653
14.9 Point Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
15 Pipeline Optimization 657
15.1 Pro»ling Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
15.2 Locating the Bottleneck . . . . . . . . . . . . . . . . . . . . . . . 658
15.2.1 Testing the Application Stage . . . . . . . . . . . . . . . . 660
15.2.2 Testing the Geometry Stage . . . . . . . . . . . . . . . . . 661
15.2.3 Testing the Rasterizer Stage . . . . . . . . . . . . . . . . . 661
15.3 Performance Measurements . . . . . . . . . . . . . . . . . . . . . 662
15.4 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663
15.4.1 Application Stage . . . . . . . . . . . . . . . . . . . . . . 663
15.4.2 API Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
15.4.3 Geometry Stage . . . . . . . . . . . . . . . . . . . . . . . 672
15.4.4 Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
15.4.5 Rasterizer Stage . . . . . . . . . . . . . . . . . . . . . . . 673
15.5 Multiprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676
15.5.1 Multiprocessor Pipelining . . . . . . . . . . . . . . . . . . 676
15.5.2 Parallel Processing . . . . . . . . . . . . . . . . . . . . . . 679
x CONTENTS
16 Intersection Test Methods 683
16.1 Hardware-Accelerated Picking . . . . . . . . . . . . . . . . . . . . 684
16.2 De»nitions and Tools . . . . . . . . . . . . . . . . . . . . . . . . . 685
16.3 Bounding Volume Creation . . . . . . . . . . . . . . . . . . . . . 689
16.4 Geometric Probability . . . . . . . . . . . . . . . . . . . . . . . . 692
16.5 Rules of Thumb . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
16.6 Ray/Sphere Intersection . . . . . . . . . . . . . . . . . . . . . . . 695
16.6.1 Mathematical Solution . . . . . . . . . . . . . . . . . . . . 695
16.6.2 Optimized Solution . . . . . . . . . . . . . . . . . . . . . . 696
16.7 Ray/Box Intersection . . . . . . . . . . . . . . . . . . . . . . . . . 698
16.7.1 Slabs Method . . . . . . . . . . . . . . . . . . . . . . . . . 698
16.7.2 Line Segment/Box Overlap Test . . . . . . . . . . . . . . 701
16.7.3 Ray Slope Method . . . . . . . . . . . . . . . . . . . . . . 702
16.8 Ray/Triangle Intersection . . . . . . . . . . . . . . . . . . . . . . 703
16.8.1 Intersection Algorithm . . . . . . . . . . . . . . . . . . . . 703
16.8.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . 706
16.9 Ray/Polygon Intersection . . . . . . . . . . . . . . . . . . . . . . 707
16.9.1 The Crossings Test . . . . . . . . . . . . . . . . . . . . . . 708
16.10Plane/Box Intersection Detection . . . . . . . . . . . . . . . . . . 711
16.10.1AABB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711
16.10.2OBB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712
16.11Triangle/Triangle Intersection . . . . . . . . . . . . . . . . . . . . 713
16.12Triangle/Box Overlap . . . . . . . . . . . . . . . . . . . . . . . . 716
16.13BV/BV Intersection Tests . . . . . . . . . . . . . . . . . . . . . . 717
16.13.1 Sphere/Sphere Intersection . . . . . . . . . . . . . . . . . 718
16.13.2 Sphere/Box Intersection . . . . . . . . . . . . . . . . . . . 718
16.13.3AABB/AABB Intersection . . . . . . . . . . . . . . . . . 720
16.13.4 k-DOP/k-DOP Intersection . . . . . . . . . . . . . . . . . 720
16.13.5OBB/OBB Intersection . . . . . . . . . . . . . . . . . . . 721
16.14View Frustum Intersection . . . . . . . . . . . . . . . . . . . . . . 725
16.14.1Frustum Plane Extraction . . . . . . . . . . . . . . . . . . 728
16.14.2Frustum/Sphere Intersection . . . . . . . . . . . . . . . . 729
16.14.3Frustum/Box Intersection . . . . . . . . . . . . . . . . . . 731
16.15Shaft/Box and Shaft/Sphere Intersection . . . . . . . . . . . . . 732
16.16Line/Line Intersection Tests . . . . . . . . . . . . . . . . . . . . . 734
16.16.1Two Dimensions . . . . . . . . . . . . . . . . . . . . . . . 734
16.16.2 Three Dimensions . . . . . . . . . . . . . . . . . . . . . . 735
16.17Intersection Between Three Planes . . . . . . . . . . . . . . . . . 736
16.18Dynamic Intersection Testing . . . . . . . . . . . . . . . . . . . . 737
16.18.1 Sphere/Plane . . . . . . . . . . . . . . . . . . . . . . . . . 738
16.18.2 Sphere/Sphere . . . . . . . . . . . . . . . . . . . . . . . . 739
16.18.3 Sphere/Polygon . . . . . . . . . . . . . . . . . . . . . . . . 740
16.18.4 Dynamic Separating Axis Method . . . . . . . . . . . . . 744
CONTENTS xi
17 Collision Detection 747
17.1 Collision Detection with Rays . . . . . . . . . . . . . . . . . . . . 749
17.2 Dynamic CD using BSP Trees . . . . . . . . . . . . . . . . . . . . 750
17.3 General Hierarchical Collision Detection . . . . . . . . . . . . . . 755
17.3.1 Hierarchy Building . . . . . . . . . . . . . . . . . . . . . . 756
17.3.2 Collision Testing between Hierarchies . . . . . . . . . . . 758
17.3.3 Cost Function . . . . . . . . . . . . . . . . . . . . . . . . . 759
17.4 OBBTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760
17.5 A Multiple Objects CD System . . . . . . . . . . . . . . . . . . . 764
17.5.1 Broad Phase Collision Detection . . . . . . . . . . . . . . 764
17.5.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
17.6 Miscellaneous Topics . . . . . . . . . . . . . . . . . . . . . . . . . 769
17.6.1 Time-Critical Collision Detection . . . . . . . . . . . . . . 769
17.6.2 Distance Queries . . . . . . . . . . . . . . . . . . . . . . . 770
17.6.3 Deformable Models . . . . . . . . . . . . . . . . . . . . . . 771
17.6.4 Collision Response . . . . . . . . . . . . . . . . . . . . . . 775
17.6.5 GPU-based Collision Detection . . . . . . . . . . . . . . . 776
17.7 Other Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778
18 Graphics Hardware 781
18.1 Bu«ers and Bu«ering . . . . . . . . . . . . . . . . . . . . . . . . . 781
18.1.1 A Simple Display System . . . . . . . . . . . . . . . . . . 781
18.1.2 The Color Bu«er . . . . . . . . . . . . . . . . . . . . . . . 783
18.1.3 Z-bu«ering . . . . . . . . . . . . . . . . . . . . . . . . . . 784
18.1.4 Single, Double, and Triple Bu«ering . . . . . . . . . . . . 785
18.1.5 Stereo and Multi-View Graphics . . . . . . . . . . . . . . 787
18.1.6 Bu«er Memory . . . . . . . . . . . . . . . . . . . . . . . . 789
18.2 Perspective-Correct Interpolation . . . . . . . . . . . . . . . . . . 789
18.3 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
18.3.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
18.3.2 Memory Architecture . . . . . . . . . . . . . . . . . . . . 799
18.3.3 Ports and Buses . . . . . . . . . . . . . . . . . . . . . . . 801
18.3.4 Memory Bandwidth . . . . . . . . . . . . . . . . . . . . . 801
18.3.5 Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804
18.3.6 Bu«er Compression . . . . . . . . . . . . . . . . . . . . . 804
18.3.7 Z-Culling and Early-Z . . . . . . . . . . . . . . . . . . . . 806
18.3.8 PCU: Programmable Culling Unit . . . . . . . . . . . . . 808
18.4 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810
18.4.1 Case Study: Xbox 360 . . . . . . . . . . . . . . . . . . . . 810
18.4.2 Case Study: The PLAYSTATION R° 3 system . . . . . . . 813
18.4.3 Case Study: Mali 200 . . . . . . . . . . . . . . . . . . . . 820
18.4.4 Other Architectures . . . . . . . . . . . . . . . . . . . . . 825
19 The Future 827
19.1 Everything Else . . . . . . . . . . . . . . . . . . . . . . . . . . . . 827
19.2 You . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832
xii CONTENTS
A Some Linear Algebra 837
A.1 Euclidean Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 837
A.2 Geometrical Interpretation . . . . . . . . . . . . . . . . . . . . . . 840
A.3 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844
A.3.1 De»nitions and Operations . . . . . . . . . . . . . . . . . 845
A.3.2 Change of Base . . . . . . . . . . . . . . . . . . . . . . . . 851
A.4 Homogeneous Notation . . . . . . . . . . . . . . . . . . . . . . . . 852
A.5 Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853
A.5.1 Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853
A.5.2 Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855
A.5.3 Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . 856
A.5.4 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . 856
B Trigonometry 859
B.1 De»nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859
B.2 Trigonometric Laws and Formulae . . . . . . . . . . . . . . . . . 861
References 866
Index 944