Foreword xxviiPreface xxixContributors xxxiiiPART I: GEOMETRY 3Chapter 1: Generating Complex Procedural Terrains Using the GPU 7
Ryan Geiss, NVIDIA Corporation1.1 Introduction 7
1.2 Marching Cubes and the Density Function 7
1.3 An Overview of the Terrain Generation System 12
1.4 Generating the Polygons Within a Block of Terrain 20
1.5 Texturing and Shading 29
1.6 Considerations for Real-World Applications 35
1.7 Conclusion 37
1.8 References 37
Chapter 2: Animated Crowd Rendering 39
Bryan Dudash, NVIDIA Corporation2.1 Motivation 39
2.2 A Brief Review of Instancing 40
2.3 Details of the Technique 42
2.4 Other Considerations 50
2.5 Conclusion 51
2.6 References 52
Chapter 3: DirectX 10 Blend Shapes: Breaking the Limits 53
Tristan Lorach, NVIDIA Corporation3.1 Introduction 53
3.2 How Does It Work? 56
3.3 Running the Sample 66
3.4 Performance 66
3.5 References 67
Chapter 4: Next-Generation SpeedTree Rendering 69
Alexander Kharlamov, NVIDIA Corporation
Iain Cantlay, NVIDIA Corporation
Yury Stepanenko, NVIDIA Corporation4.1 Introduction 69
4.2 Silhouette Clipping 69
4.3 Shadows 76
4.4 Leaf Lighting 81
4.5 High Dynamic Range and Antialiasing 85
4.6 Alpha to Coverage 85
4.7 Conclusion 88
4.8 References 91
Chapter 5: Generic Adaptive Mesh Refinement 93
Tamy Boubekeur, LaBRI-INRIA, University of Bordeaux
Christophe Schlick, LaBRI-INRIA, University of Bordeaux5.1 Introduction 94
5.2 Overview 95
5.3 Adaptive Refinement Patterns 96
5.4 Rendering Workflow 98
5.5 Results 100
5.6 Conclusion and Improvements 103
5.7 References 104
Chapter 6: GPU-Generated Procedural Wind Animations for Trees 105
Renaldas Zioma, Electronic Arts/Digital Illusions CE6.1 Introduction 105
6.2 Procedural Animations on the GPU 106
6.3 A Phenomenological Approach 106
6.4 The Simulation Step 113
6.5 Rendering the Tree 117
6.6 Analysis and Comparison 118
6.7 Summary 119
6.8 References 120
Chapter 7: Point-Based Visualization of Metaballs on a GPU 123
Kees van Kooten, Playlogic Game Factory
Gino van den Bergen, Playlogic Game Factory
Alex Telea, Eindhoven University of Technology7.1 Metaballs, Smoothed Particle Hydrodynamics, and Surface Particles 124
7.2 Constraining Particles 127
7.3 Local Particle Repulsion 135
7.4 Global Particle Dispersion 140
7.5 Performance 145
7.6 Rendering 146
7.7 Conclusion 147
7.8 References 148
PART II: LIGHT AND SHADOWS 151Chapter 8: Summed-Area Variance Shadow Maps 157
Andrew Lauritzen, University of Waterloo8.1 Introduction 157
8.2 Related Work 158
8.3 Percentage-Closer Filtering 159
8.4 Variance Shadow Maps 161
8.5 Summed-Area Variance Shadow Maps 174
8.6 Percentage-Closer Soft Shadows 178
8.7 Conclusion 181
8.8 References 181
Chapter 9: Interactive Cinematic Relighting with Global Illumination 183
Fabio Pellacini, Dartmouth College
Milos Hasan, Cornell University
Kavita Bala, Cornell University9.1 Introduction 183
9.2 An Overview of the Algorithm 184
9.3 Gather Samples 186
9.4 One-Bounce Indirect Illumination 188
9.5 Wavelets for Compression 189
9.6 Adding Multiple Bounces 192
9.7 Packing Sparse Matrix Data 193
9.8 A GPU-Based Relighting Engine 195
9.9 Results 200
9.10 Conclusion 201
9.11 References 201
Chapter 10: Parallel-Split Shadow Maps on Programmable GPUs 203
Fan Zhang, The Chinese University of Hong Kong
Hanqiu Sun, The Chinese University of Hong Kong
Oskari Nyman, Helsinki University of Technology10.1 Introduction 203
10.2 The Algorithm 205
10.3 Hardware-Specific Implementations 214
10.4 Further Optimizations 232
10.5 Results 233
10.6 Conclusion 233
10.7 References 235
Chapter 11: Efficient and Robust Shadow Volumes Using Hierarchical Occlusion Culling and Geometry Shaders 239
Martin Stich, mental images
Carsten Waechter, Ulm University
Alexander Keller, Ulm University11.1 Introduction 239
11.2 An Overview of Shadow Volumes 240
11.3 Our Implementation 244
11.4 Conclusion 254
11.5 References 254
Chapter 12: High-Quality Ambient Occlusion 257
Jared Hoberock, University of Illinois at Urbana-Champaign
Yuntao Jia, University of Illinois at Urbana-Champaign12.1 Review 257
12.2 Problems 258
12.3 A Robust Solution 261
12.4 Results 267
12.5 Performance 269
12.6 Caveats 270
12.7 Future Work 273
12.8 References 274
Chapter 13: Volumetric Light Scattering as a Post-Process 275
Kenny Mitchell, Electronic Arts13.1 Introduction 275
13.2 Crepuscular Rays 276
13.3 Volumetric Light Scattering 277
13.4 The Post-Process Pixel Shader 279
13.5 Screen-Space Occlusion Methods 281
13.6 Caveats 282
13.7 The Demo 283
13.8 Extensions 284
13.9 Summary 284
13.10 References 284
PART III: RENDERING 287Chapter 14: Advanced Techniques for Realistic Real-Time Skin Rendering 293
Eugene d'Eon, NVIDIA Corporation
David Luebke, NVIDIA Corporation14.1 The Appearance of Skin 293
14.2 An Overview of the Skin-Rendering System 297
14.3 Specular Surface Reflectance 299
14.4 Scattering Theory 305
14.5 Advanced Subsurface Scattering 314
14.6 A Fast Bloom Filter 342
14.7 Conclusion 342
14.8 References 345
Chapter 15: Playable Universal Capture 349
George Borshukov, Electronic Arts
Jefferson Montgomery, Electronic Arts
John Hable, Electronic Arts15.1 Introduction 349
15.2 The Data Acquisition Pipeline 350
15.3 Compression and Decompression of the Animated Textures 352
15.4 Sequencing Performances 363
15.5 Conclusion 363
15.6 References 370
Chapter 16: Vegetation Procedural Animation and Shading in Crysis 373
Tiago Sousa, Crytek16.1 Procedural Animation 373
16.2 Vegetation Shading 378
16.3 Conclusion 384
16.4 References 384
Chapter 17: Robust Multiple Specular Reflections and Refractions 387
Tamas Umenhoffer, Budapest University of Technology and Economics
Gustavo Patow, University of Girona
Laszlo Szirmay-Kalos, Budapest University of Technology and Economics17.1 Introduction 388
17.2 Tracing Secondary Rays 389
17.3 Reflections and Refractions 396
17.4 Results 400
17.5 Conclusion 402
17.6 References 406
Chapter 18: Relaxed Cone Stepping for Relief Mapping 409
Fabio Policarpo, Perpetual Entertainment
Manuel M. Oliveira, Instituto de Informatica-UFRGS18.1 Introduction 409
18.2 A Brief Review of Relief Mapping 411
18.3 Cone Step Mapping 415
18.4 Relaxed Cone Stepping 416
18.5 Conclusion 425
18.6 References 427
Chapter 19: Deferred Shading in Tabula Rasa 429
Rusty Koonce, NCsoft Corporation19.1 Introduction 429
19.2 Some Background 430
19.3 Forward Shading Support 431
19.4 Advanced Lighting Features 434
19.5 Benefits of a Readable Depth and Normal Buffer 440
19.6 Caveats 445
19.7 Optimizations 448
19.8 Issues 450
19.9 Results 454
19.10 Conclusion 454
19.11 References 457
Chapter 20: GPU-Based Importance Sampling 459
Mark Colbert, University of Central Florida
Jaroslav Krivanek, Czech Technical University in Prague20.1 Introduction 459
20.2 Rendering Formulation 459
20.3 Quasirandom Low-Discrepancy Sequences 465
20.4 Mipmap Filtered Samples 466
20.5 Performance 470
20.6 Conclusion 471
20.7 Further Reading and References 474
PART IV: IMAGE EFFECTS 477Chapter 21: True Impostors 481
Eric Risser, University of Central Florida21.1 Introduction 481
21.2 Algorithm and Implementation Details 482
21.3 Results 487
21.4 Conclusion 489
21.5 References 489
Chapter 22: Baking Normal Maps on the GPU 491
Diogo Teixeira, Move Interactive22.1 The Traditional Implementation 492
22.2 Acceleration Structures 493
22.3 Feeding the GPU 496
22.4 Implementation 498
22.5 Results 508
22.6 Conclusion 511
22.7 References 511
Chapter 23: High-Speed, Off-Screen Particles 513
Iain Cantlay, NVIDIA Corporation23.1 Motivation 513
23.2 Off-Screen Rendering 514
23.3 Downsampling Depth 517
23.4 Depth Testing and Soft Particles 519
23.5 Alpha Blending 520
23.6 Mixed-Resolution Rendering 522
23.7 Results 525
23.8 Conclusion 527
23.9 References 528
Chapter 24: The Importance of Being Linear 529
Larry Gritz, NVIDIA Corporation
Eugene d'Eon, NVIDIA Corporation24.1 Introduction 529
24.2 Light, Displays, and Color Spaces 529
24.3 The Symptoms 533
24.4 The Cure 538
24.5 Conclusion 541
24.6 Further Reading 542
Chapter 25: Rendering Vector Art on the GPU 543
Charles Loop, Microsoft Research
Jim Blinn, Microsoft Research25.1 Introduction 543
25.2 Quadratic Splines 544
25.3 Cubic Splines 546
25.4 Triangulation 555
25.5 Antialiasing 556
25.6 Code 558
25.7 Conclusion 559
25.8 References 560
Chapter 26: Object Detection by Color: Using the GPU for Real-Time Video Image Processing 563
Ralph Brunner, Apple
Frank Doepke, Apple
Bunny Laden, Apple26.1 Image Processing Abstracted 564
26.2 Object Detection by Color 567
26.3 Conclusion 574
26.4 Further Reading 574
Chapter 27: Motion Blur as a Post-Processing Effect 575
Gilberto Rosado, Rainbow Studios27.1 Introduction 575
27.2 Extracting Object Positions from the Depth Buffer 576
27.3 Performing the Motion Blur 579
27.4 Handling Dynamic Objects 580
27.5 Masking Off Objects 580
27.6 Additional Work 581
27.7 Conclusion 581
27.8 References 581
Chapter 28: Practical Post-Process Depth of Field 583
Earl Hammon, Jr., Infinity Ward28.1 Introduction 583
28.2 Related Work 583
28.3 Depth of Field 585
28.4 Evolution of the Algorithm 587
28.5 The Complete Algorithm 592
28.6 Conclusion 602
28.7 Limitations and Future Work 603
28.8 References 605
PART V: PHYSICS SIMULATION 607Chapter 29: Real-Time Rigid Body Simulation on GPUs 611
Takahiro Harada, University of Tokyo29.1 Introduction 613
29.2 Rigid Body Simulation on the GPU 618
29.3 Applications 627
29.4 Conclusion 629
29.5 Appendix 631
29.6 References 631
Chapter 30: Real-Time Simulation and Rendering of 3D Fluids 633
Keenan Crane, University of Illinois at Urbana-Champaign
Ignacio Llamas, NVIDIA Corporation
Sarah Tariq, NVIDIA Corporation30.1 Introduction 633
30.2 Simulation 634
30.3 Rendering 665
30.4 Conclusion 672
30.5 References 673
Chapter 31: Fast N-Body Simulation with CUDA 677
Lars Nyland, NVIDIA Corporation
Mark Harris, NVIDIA Corporation
Jan Prins, University of North Carolina at Chapel Hill31.1 Introduction 677
31.2 All-Pairs N-Body Simulation 679
31.3 A CUDA Implementation of the All-Pairs N-Body Algorithm 680
31.4 Performance Results 686
31.5 Previous Methods Using GPUs for N-Body Simulation 691
31.6 Hierarchical N-Body Methods 692
31.7 Conclusion 693
31.8 References 694
Chapter 32: Broad-Phase Collision Detection with CUDA 697
Scott Le Grand, NVIDIA Corporation32.1 Broad-Phase Algorithms 697
32.2 A CUDA Implementation of Spatial Subdivision 702
32.3 Performance Results 719
32.4 Conclusion 721
32.5 References 721
Chapter 33: LCP Algorithms for Collision Detection Using CUDA 723
Peter Kipfer, Havok33.1 Parallel Processing 724
33.2 The Physics Pipeline 724
33.3 Determining Contact Points 726
33.4 Mathematical Optimization 728
33.5 The Convex Distance Calculation 731
33.6 The Parallel LCP Solution Using CUDA 732
33.7 Results 738
33.8 References 739
Chapter 34: Signed Distance Fields Using Single-Pass GPU Scan Conversion of Tetrahedra 741
Kenny Erleben, University of Copenhagen
Henrik Dohlmann, 3Dfacto R&D34.1 Introduction 741
34.2 Leaking Artifacts in Scan Methods 742
34.3 Our Tetrahedra GPU Scan Method 747
34.4 Results 756
34.5 Conclusion 758
34.6 Future Work 759
34.7 Further Reading 760
34.8 References 762
PART VI: GPU COMPUTING 765Chapter 35: Fast Virus Signature Matching on the GPU 771
Elizabeth Seamans, Juniper Networks
Thomas Alexander, Polytime35.1 Introduction 771
35.2 Pattern Matching 773
35.3 The GPU Implementation 775
35.4 Results 779
35.5 Conclusions and Future Work 782
35.6 References 783
Chapter 36: AES Encryption and Decryption on the GPU 785
Takeshi Yamanouchi, SEGA Corporation36.1 New Functions for Integer Stream Processing 786
36.2 An Overview of the AES Algorithm 788
36.3 The AES Implementation on the GPU 790
36.4 Performance 797
36.5 Considerations for Parallelism 799
36.6 Conclusion and Future Work 802
36.7 References 802
Chapter 37: Efficient Random Number Generation and Application Using CUDA 805
Lee Howes, Imperial College London
David Thomas, Imperial College London37.1 Monte Carlo Simulations 806
37.2 Random Number Generators 809
37.3 Example Applications 821
37.4 Conclusion 829
37.5 References 829
Chapter 38: Imaging Earth's Subsurface Using CUDA 831
Bernard Deschizeaux, CGGVeritas
Jean-Yves Blanc, CGGVeritas38.1 Introduction 831
38.2 Seismic Data 832
38.3 Seismic Processing 834
38.4 The GPU Implementation 841
38.5 Performance 849
38.6 Conclusion 849
38.7 References 850
Chapter 39: Parallel Prefix Sum (Scan) with CUDA 851
Mark Harris, NVIDIA Corporation
Shubhabrata Sengupta, University of California, Davis
John D. Owens, University of California, Davis39.1 Introduction 851
39.2 Implementation 853
39.3 Applications of Scan 866
39.4 Conclusion 875
39.5 References 875
Chapter 40: Incremental Computation of the Gaussian 877
Ken Turkowski, Adobe Systems40.1 Introduction and Related Work 877
40.2 Polynomial Forward Differencing 879
40.3 The Incremental Gaussian Algorithm 882
40.4 Error Analysis 885
40.5 Performance 887
40.6 Conclusion 888
40.7 References 888
Chapter 41: Using the Geometry Shader for Compact and Variable-Length GPU Feedback 891
Franck Diard, NVIDIA Corporation41.1 Introduction 891
41.2 Why Use the Geometry Shader? 892
41.3 Dynamic Output with the Geometry Shader 893
41.4 Algorithms and Applications 895
41.5 Benefits: GPU Locality and SLI 903
41.6 Performance and Limits 905
41.7 Conclusion 907
41.8 References 907
Index 909
