Foreword xxixPreface xxxiContributors xxxvPART I: GEOMETRIC COMPLEXITY 1Chapter 1: Toward Photorealism in Virtual Botany 7
David Whatley, Simutronics Corporation1.1 Scene Management 7
1.2 The Grass Layer 11
1.3 The Ground Clutter Layer 17
1.4 The Tree and Shrub Layers 18
1.5 Shadowing 20
1.6 Post-Processing 22
1.7 Conclusion 24
1.8 References 24
Chapter 2: Terrain Rendering Using GPU-Based Geometry Clipmaps 27
Arul Asirvatham, Microsoft Research
Hugues Hoppe, Microsoft Research2.1 Review of Geometry Clipmaps 27
2.2 Overview of GPU Implementation 30
2.3 Rendering 32
2.4 Update 39
2.5 Results and Discussion 43
2.6 Summary and Improvements 43
2.7 References 44
Chapter 3: Inside Geometry Instancing 47
Francesco Carucci, Lionhead Studios3.1 Why Geometry Instancing? 48
3.2 Definitions 49
3.3 Implementation 53
3.4 Conclusion 65
3.5 References 67
Chapter 4: Segment Buffering 69
Jon Olick, 20154.1 The Problem Space 69
4.2 The Solution 70
4.3 The Method 71
4.4 Improving the Technique 72
4.5 Conclusion 72
4.6 References 73
Chapter 5: Optimizing Resource Management with Multistreaming. 75
Oliver Hoeller, Piranha Bytes
Kurt Pelzer, Piranha Bytes5.1 Overview 76
5.2 Implementation 77
5.3 Conclusion 89
5.4 References 90
Chapter 6: Hardware Occlusion Queries Made Useful 91
Michael Wimmer, Vienna University of Technology
Jiri Bittner, Vienna University of Technology6.1 Introduction 91
6.2 For Which Scenes Are Occlusion Queries Effective? 92
6.3 What Is Occlusion Culling? 93
6.4 Hierarchical Stop-and-Wait Method 94
6.5 Coherent Hierarchical Culling 97
6.6 Optimizations 105
6.7 Conclusion 106
6.8 References 108
Chapter 7: Adaptive Tessellation of Subdivision Surfaces withDisplacement Mapping 109
Michael Bunnell, NVIDIA Corporation7.1 Subdivision Surfaces 109
7.2 Displacement Mapping 119
7.3 Conclusion 122
7.4 References 122
Chapter 8: Per-Pixel Displacement Mapping with Distance Functions 123
William Donnelly, University of Waterloo8.1 Introduction 123
8.2 Previous Work 125
8.3 The Distance-Mapping Algorithm 126
8.4 Computing the Distance Map 130
8.5 The Shaders 130
8.6 Results 132
8.7 Conclusion 134
8.8 References 135
PART II: SHADING, LIGHTING, AND SHADOWS 137Chapter 9: Deferred Shading in S.T.A.L.K.E.R. 143
Oles Shishkovtsov, GSC Game World9.1 Introduction 143
9.2 The Myths 145
9.3 Optimizations 147
9.4 Improving Quality 154
9.5 Antialiasing 158
9.6 Things We Tried but Did Not Include in the Final Code 162
9.7 Conclusion 164
9.8 References 165
Chapter 10: Real-Time Computation of Dynamic Irradiance Environment Maps 167
Gary King, NVIDIA Corporation10.1 Irradiance Environment Maps 167
10.2 Spherical Harmonic Convolution 170
10.3 Mapping to the GPU 172
10.4 Further Work 175
10.5 Conclusion 176
10.6 References 176
Chapter 11: Approximate Bidirectional Texture Functions 177
Jan Kautz, Massachusetts Institute of Technology11.1 Introduction 177
11.2 Acquisition 179
11.3 Rendering 181
11.4 Results 184
11.5 Conclusion 187
11.6 References 187
Chapter 12: Tile-Based Texture Mapping 189
Li-Yi Wei, NVIDIA Corporation12.1 Our Approach 191
12.2 Texture Tile Construction 191
12.3 Texture Tile Packing 192
12.4 Texture Tile Mapping 195
12.5 Mipmap Issues 197
12.6 Conclusion 198
12.7 References 199
Chapter 13: Implementing the mental images Phenomena Renderer on the GPU 201
Martin-Karl Lefrancois, mental images13.1 Introduction 201
13.2 Shaders and Phenomena 202
13.3 Implementing Phenomena Using Cg 205
13.4 Conclusion 221
13.5 References 222
Chapter 14: Dynamic Ambient Occlusion and Indirect Lighting 223
Michael Bunnell, NVIDIA Corporation14.1 Surface Elements 223
14.2 Ambient Occlusion 225
14.3 Indirect Lighting and Area Lights 231
14.4 Conclusion 232
14.5 References 233
Chapter 15: Blueprint Rendering and Sketchy Drawings 235
Marc Nienhaus, University of Potsdam, Hasso-Plattner-Institute
Jurgen Doellner, University of Potsdam, Hasso-Plattner-Institute15.1 Basic Principles 236
15.2 Blueprint Rendering 238
15.3 Sketchy Rendering 244
15.4 Conclusion 251
15.5 References 252
Chapter 16: Accurate Atmospheric Scattering 253
Sean O'Neil16.1 Introduction 253
16.2 Solving the Scattering Equations 254
16.3 Making It Real-Time 258
16.4 Squeezing It into a Shader 260
16.5 Implementing the Scattering Shaders 262
16.6 Adding High-Dynamic-Range Rendering 265
16.7 Conclusion 266
16.8 References 267
Chapter 17: Efficient Soft-Edged Shadows Using Pixel Shader Branching 269
Yury Uralsky, NVIDIA Corporation17.1 Current Shadowing Techniques 270
17.2 Soft Shadows with a Single Shadow Map 271
17.3 Conclusion 281
17.4 References 282
Chapter 18: Using Vertex Texture Displacement for Realistic Water Rendering 283
Yuri Kryachko, 1C:Maddox Games18.1 Water Models 283
18.2 Implementation 284
18.3 Conclusion 294
18.4 References 294
Chapter 19: Generic Refraction Simulation 295
Tiago Sousa, Crytek19.1 Basic Technique 296
19.2 Refraction Mask 297
19.3 Examples 300
19.4 Conclusion 305
19.5 References 305
PART III: HIGH-QUALITY RENDERING 307Chapter 20: Fast Third-Order Texture Filtering 313
Christian Sigg, ETH Zurich
Markus Hadwiger, VRVis Research Center20.1 Higher-Order Filtering 314
20.2 Fast Recursive Cubic Convolution 315
20.3 Mipmapping 320
20.4 Derivative Reconstruction 324
20.5 Conclusion 327
20.6 References 328
Chapter 21: High-Quality Antialiased Rasterization 331
Dan Wexler, NVIDIA Corporation
Eric Enderton, NVIDIA Corporation21.1 Overview 331
21.2 Downsampling 334
21.3 Padding 336
21.4 Filter Details 337
21.5 Two-Pass Separable Filtering 338
21.6 Tiling and Accumulation 339
21.7 The Code 339
21.8 Conclusion 344
21.9 References 344
Chapter 22: Fast Prefiltered Lines 345
Eric Chan, Massachusetts Institute of Technology
Fredo Durand, Massachusetts Institute of Technology22.1 Why Sharp Lines Look Bad 345
22.2 Bandlimiting the Signal 347
22.3 The Preprocess 349
22.4 Runtime 351
22.5 Implementation Issues 355
22.6 Examples 356
22.7 Conclusion 358
22.8 References 359
Chapter 23: Hair Animation and Rendering in the Nalu Demo 361
Hubert Nguyen, NVIDIA Corporation
William Donnelly, NVIDIA Corporation23.1 Hair Geometry 362
23.2 Dynamics and Collisions 366
23.3 Hair Shading 369
23.4 Conclusion and Future Work 378
23.5 References 380
Chapter 24: Using Lookup Tables to Accelerate Color Transformations 381
Jeremy Selan, Sony Pictures Imageworks24.1 Lookup Table Basics 381
24.2 Implementation 386
24.3 Conclusion 392
24.4 References 392
Chapter 25: GPU Image Processing in Apple's Motion 393
Pete Warden, Apple Computer25.1 Design 393
25.2 Implementation 397
25.3 Debugging 406
25.4 Conclusion 407
25.5 References 408
Chapter 26: Implementing Improved Perlin Noise 409
Simon Green, NVIDIA Corporation26.1 Random but Smooth 409
26.2 Storage vs. Computation 410
26.3 Implementation Details 411
26.4 Conclusion 415
26.5 References 416
Chapter 27: Advanced High-Quality Filtering 417
Justin Novosad, discreet27.1 Implementing Filters on GPUs 417
27.2 The Problem of Digital Image Resampling 422
27.3 Shock Filtering: A Method for Deblurring Images 430
27.4 Filter Implementation Tips 433
27.5 Advanced Applications 433
27.6 Conclusion 434
27.7 References 435
Chapter 28: Mipmap-Level Measurement 437
Iain Cantlay, Climax Entertainment28.1 Which Mipmap Level Is Visible? 438
28.2 GPU to the Rescue 439
28.3 Sample Results 447
28.4 Conclusion 448
28.5 References 449
PART IV: GENERAL-PURPOSE COMPUTATION ON GPUS: A PRIMER 451Chapter 29: Streaming Architectures and Technology Trends 457
John Owens, University of California, Davis29.1 Technology Trends 457
29.2 Keys to High-Performance Computing 461
29.3 Stream Computation 464
29.4 The Future and Challenges 468
29.5 References 470
Chapter 30: The GeForce 6 Series GPU Architecture 471
Emmett Kilgariff, NVIDIA Corporation
Randima Fernando, NVIDIA Corporation30.1 How the GPU Fits into the Overall Computer System 471
30.2 Overall System Architecture 473
30.3 GPU Features 481
30.4 Performance 488
30.5 Achieving Optimal Performance 490
30.6 Conclusion 491
Chapter 31: Mapping Computational Concepts to GPUs 493
Mark Harris, NVIDIA Corporation31.1 The Importance of Data Parallelism 493
31.2 An Inventory of GPU Computational Resources 497
31.3 CPU-GPU Analogies 500
31.4 From Analogies to Implementation 503
31.5 A Simple Example 505
31.6 Conclusion 508
31.7 References 508
Chapter 32: Taking the Plunge into GPU Computing 509
Ian Buck, Stanford University32.1 Choosing a Fast Algorithm 509
32.2 Understanding Floating Point 513
32.3 Implementing Scatter 515
32.4 Conclusion 518
32.5 References 519
Chapter 33: Implementing Efficient Parallel Data Structures on GPUs 521
Aaron Lefohn, University of California, Davis
Joe Kniss, University of Utah
John Owens, University of California, Davis33.1 Programming with Streams 521
33.2 The GPU Memory Model 524
33.3 GPU-Based Data Structures 528
33.4 Performance Considerations 540
33.5 Conclusion 543
33.6 References 544
Chapter 34: GPU Flow-Control Idioms 547
Mark Harris, NVIDIA Corporation
Ian Buck, Stanford University34.1 Flow-Control Challenges 547
34.2 Basic Flow-Control Strategies 549
34.3 Data-Dependent Looping with Occlusion Queries 554
34.4 Conclusion 555
Chapter 35: GPU Program Optimization 557
Cliff Woolley, University of Virginia35.1 Data-Parallel Computing 557
35.2 Computational Frequency 561
35.3 Profiling and Load Balancing 568
35.4 Conclusion 570
35.5 References 570
Chapter 36: Stream Reduction Operations for GPGPU Applications 573
Daniel Horn, Stanford University36.1 Filtering Through Compaction 574
36.2 Motivation: Collision Detection 579
36.3 Filtering for Subdivision Surfaces 583
36.4 Conclusion 587
36.5 References 587
PART V: IMAGE-ORIENTED COMPUTING 591Chapter 37: Octree Textures on the GPU 595
Sylvain Lefebvre, GRAVIR/IMAG-INRIA
Samuel Hornus, GRAVIR/IMAG-INRIA
Fabrice Neyret, GRAVIR/IMAG-INRIA37.1 A GPU-Accelerated Hierarchical Structure: The N3-Tree 597
37.2 Application 1: Painting on Meshes 602
37.3 Application 2: Surface Simulation 611
37.4 Conclusion 612
37.5 References 613
Chapter 38: High-Quality Global Illumination Rendering Using Rasterization 615
Toshiya Hachisuka, The University of Tokyo38.1 Global Illumination via Rasterization 616
38.2 Overview of Final Gathering 617
38.3 Final Gathering via Rasterization 621
38.4 Implementation Details 625
38.5 A Global Illumination Renderer on the GPU 627
38.6 Conclusion 632
38.7 References 632
Chapter 39: Global Illumination Using Progressive Refinement Radiosity 635
Greg Coombe, University of North Carolina at Chapel Hill
Mark Harris, NVIDIA Corporation39.1 Radiosity Foundations 636
39.2 GPU Implementation 638
39.3 Adaptive Subdivision 643
39.4 Performance 645
39.5 Conclusion 645
39.6 References 647
Chapter 40: Computer Vision on the GPU 649
James Fung, University of Toronto40.1 Introduction 649
40.2 Implementation Framework 650
40.3 Application Examples 651
40.4 Parallel Computer Vision Processing 664
40.5 Conclusion 664
40.6 References 665
Chapter 41: Deferred Filtering: Rendering from Difficult Data Formats 667
Joe Kniss, University of Utah
Aaron Lefohn, University of California, Davis
Nathaniel Fout, University of California, Davis41.1 Introduction 667
41.2 Why Defer? 668
41.3 Deferred Filtering Algorithm 669
41.4 Why It Works 673
41.5 Conclusions: When to Defer 673
41.6 References 674
Chapter 42: Conservative Rasterization 677
Jon Hasselgren, Lund University
Tomas Akenine-Moeller, Lund University
Lennart Ohlsson, Lund University42.1 Problem Definition 678
42.2 Two Conservative Algorithms 679
42.3 Robustness Issues 686
42.4 Conservative Depth 687
42.5 Results and Conclusions 689
42.6 References 690
PART VI: SIMULATION AND NUMERICAL ALGORITHMS 691Chapter 43: GPU Computing for Protein Structure Prediction 695
Paulius Micikevicius, Armstrong Atlantic State University43.1 Introduction 695
43.2 The Floyd-Warshall Algorithm and Distance-Bound Smoothing 697
43.3 GPU Implementation 698
43.4 Experimental Results 701
43.5 Conclusions and Further Work 701
43.6 References 702
Chapter 44: A GPU Framework for Solving Systems of Linear Equations 703
Jens Kruger, Technische Universitat Munchen
Rudiger Westermann, Technische Universitat Munchen44.1 Overview 703
44.2 Representation 704
44.3 Operations 708
44.4 A Sample Partial Differential Equation 714
44.5 Conclusion 718
44.6 References 718
Chapter 45: Options Pricing on the GPU 719
Craig Kolb, NVIDIA Corporation
Matt Pharr, NVIDIA Corporation45.1 What Are Options? 719
45.2 The Black-Scholes Model 721
45.3 Lattice Models 725
45.4 Conclusion 730
45.5 References 731
Chapter 46: Improved GPU Sorting 733
Peter Kipfer, Technische Universitat Munchen
Rudiger Westermann, Technische Universitat Munchen46.1 Sorting Algorithms 733
46.2 A Simple First Approach 734
46.3 Fast Sorting 735
46.4 Using All GPU Resources 738
46.5 Conclusion 745
46.6 References 746
Chapter 47: Flow Simulation with Complex Boundaries 747
Wei Li, Siemens Corporate Research
Zhe Fan, Stony Brook University
Xiaoming Wei, Stony Brook University
Arie Kaufman, Stony Brook University47.1 Introduction 747
47.2 The Lattice Boltzmann Method 748
47.3 GPU-Based LBM 749
47.4 GPU-Based Boundary Handling 753
47.5 Visualization 759
47.6 Experimental Results 760
47.7 Conclusion 761
47.8 References 763
Chapter 48: Medical Image Reconstruction with the FFT 765
Thilaka Sumanaweera, Siemens Medical Solutions USA
Donald Liu, Siemens Medical Solutions USA48.1 Background 765
48.2 The Fourier Transform 766
48.3 The FFT Algorithm 767
48.4 Implementation on the GPU 768
48.5 The FFT in Medical Imaging 776
48.6 Conclusion 783
48.7 References 784
Index 785 