GPU Gems 2, w. CD-ROM

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 World 9.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 Corporation 10.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 Technology 11.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 Corporation 12.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 images 13.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 Corporation 14.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 Dollner, University of Potsdam, Hasso-Plattner-Institute 15.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'Neil 16.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 Corporation 17.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 Games 18.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 Center 20.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 Corporation 21.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 Technology 22.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 Corporation 23.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 Imageworks 24.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 Computer 25.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 Corporation 26.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, discreet 27.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 Entertainment 28.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, Davis 29.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 Corporation 30.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 Corporation 31.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 University 32.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, Davis 33.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 University 34.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 Virginia 35.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 University 36.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-INRIA 37.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 Tokyo 38.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 Corporation 39.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 Toronto 40.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, Davis 41.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-Moller, Lund University Lennart Ohlsson, Lund University 42.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 University 43.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 Munchen 44.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 Corporation 45.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 Munchen 46.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 University 47.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 USA 48.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