# GPU Gems 3

**GPU Gems 3**is now available for free online!

The CD content, including demos and content, is available on the web and for download.

You can also subscribe to our Developer News Feed to get notifications of new material on the site.

# Part V: Physics Simulation

Physics simulation presents a high degree of data parallelism and is computationally intensive, making it a good candidate for execution on the GPU. What's more, the outcome of the simulation is often consumed by the GPU for visualization, so it makes sense to have it produced directly in graphics memory by the GPU too. This section assembles a few successful GPU implementations of various algorithms used in physics simulation. There are bound to be an increasing number of them in the future as GPUs become more versatile and powerful.

Video games, virtual reality systems, and computer-generated movies make heavy use of physically based simulations to increase the realism of their worlds. The first fundamental method used by physics engines to give life to the majority of the objects populating these worlds is

rigid body dynamics. InChapter 29, "Real-Time Rigid Body Simulation on GPUs," Takahiro Haradafrom the University of Tokyo proposes an implementation of rigid body dynamics on the GPU that represents a rigid body as a set of particles. This approach builds on the tremendous floating-point processing power of the GPU to provide a straight forward way of trading accuracy for speed. In addition, it extends naturally to nonrigid bodies, such as fluids, and allows rigid and nonrigid bodies to both move and interact in the same unified framework.Water, fire, and smoke are other key elements that contribute to the vividness of virtual worlds, and fluid simulation is the best technique to achieve a high-quality implementation of these effects. In

Chapter 30, "Real-Time Simulation and Rendering of 3D Fluids," Keenan Cranefrom the University of Illinois at Urbana-Champaign andIgnacio LlamasandSarah Tariqfrom NVIDIA Corporation demonstrate that volumetric fluid simulation is a practical solution for today's games. The authors give a complete description, from GPU simulation to rendering, of how they used this approach in an actual game to achieve compelling visuals that blend and interact with the dynamic environment.Of course, physics simulation is found in many domains other than computer graphics. In particular, the N-body problem—simulating a system of N bodies where each body exerts a force on all the other bodies—arises in areas as diverse as astrophysics, molecular dynamics, plasma physics, as well as radiosity rendering. In

Chapter 31, "Fast N-Body Simulation with CUDA," Lars NylandandMark Harrisfrom NVIDIA andJan Prinsfrom the University of North Carolina at Chapel Hill show how to best map this problem to the CUDA programming model. Not only that, they solve the problem so efficiently that their implementation outperforms an optimized CPU implementation many times over.A very time-consuming step in most physics simulations is

collision detection, so this undertaking is a primary target for optimization. Two chapters in our section take up this task and leverage CUDA to achieve significant speedups. InChapter 32, "Broad Phase Collision Detection with CUDA," Scott Le Grandfrom NVIDIA focuses on the broad phase of collision detection, where pairs of objects that cannot possibly collide are quickly culled away. He presents a CUDA implementation of it based on parallel spatial subdivision. In particular, Le Grand exposes how to combine basic parallel programming techniques, such as parallel reduction and prefix sum, to come up with a CUDA implementation of radix sort—a key step of the overall algorithm. Next, inChapter 33, "LCP Algorithms for Collision Detection Using CUDA," Peter Kipferfrom Havok focuses on the narrow phase of collision detection, where exact collision detection is performed for each remaining pair of objects after the broad phase. Computing the distance between two convex polyhedra can be translated into a linear complementarity problem that he resolves through a parallel algorithm with a suitable implementation in CUDA.The GPU can also accelerate data preprocessing, as illustrated by

Kenny Erlebenfrom the University of Copenhagen andHenrik Dohlmannfrom 3Dfacto R&D inChapter 34, "Signed Distance Fields Using Single-Pass GPU Scan Conversion of Tetrahedra."Distance fields, which provide the distance from any point in space to the surface of an object, have applications in collision detection—in particular, between rigid and deformable bodies—but in many other fields as well, such as modeling, ray tracing, and path planning. In this chapter the authors describe an algorithm for computing distance fields that is amenable to a GPU implementation. They show how any programmable GPU can be used in a straightforward way to significantly speed it up. The latest generation of GPUs comes packed with new features that enable even more of the algorithm to be ported over.

Cyril Zeller, NVIDIA Corporation

- Contributors
- Foreword
- Part I: Geometry
- Chapter 1. Generating Complex Procedural Terrains Using the GPU
- Chapter 2. Animated Crowd Rendering
- Chapter 3. DirectX 10 Blend Shapes: Breaking the Limits
- Chapter 4. Next-Generation SpeedTree Rendering
- Chapter 5. Generic Adaptive Mesh Refinement
- Chapter 6. GPU-Generated Procedural Wind Animations for Trees
- Chapter 7. Point-Based Visualization of Metaballs on a GPU

- Part II: Light and Shadows
- Chapter 10. Parallel-Split Shadow Maps on Programmable GPUs
- Chapter 11. Efficient and Robust Shadow Volumes Using Hierarchical Occlusion Culling and Geometry Shaders
- Chapter 12. High-Quality Ambient Occlusion
- Chapter 13. Volumetric Light Scattering as a Post-Process
- Chapter 8. Summed-Area Variance Shadow Maps
- Chapter 9. Interactive Cinematic Relighting with Global Illumination

- Part III: Rendering
- Chapter 14. Advanced Techniques for Realistic Real-Time Skin Rendering
- Chapter 15. Playable Universal Capture
- Chapter 16. Vegetation Procedural Animation and Shading in Crysis
- Chapter 17. Robust Multiple Specular Reflections and Refractions
- Chapter 18. Relaxed Cone Stepping for Relief Mapping
- Chapter 19. Deferred Shading in Tabula Rasa
- Chapter 20. GPU-Based Importance Sampling

- Part IV: Image Effects
- Chapter 21. True Impostors
- Chapter 22. Baking Normal Maps on the GPU
- Chapter 23. High-Speed, Off-Screen Particles
- Chapter 24. The Importance of Being Linear
- Chapter 25. Rendering Vector Art on the GPU
- Chapter 26. Object Detection by Color: Using the GPU for Real-Time Video Image Processing
- Chapter 27. Motion Blur as a Post-Processing Effect
- Chapter 28. Practical Post-Process Depth of Field

- Part V: Physics Simulation
- Chapter 29. Real-Time Rigid Body Simulation on GPUs
- Chapter 30. Real-Time Simulation and Rendering of 3D Fluids
- Chapter 31. Fast N-Body Simulation with CUDA
- Chapter 32. Broad-Phase Collision Detection with CUDA
- Chapter 33. LCP Algorithms for Collision Detection Using CUDA
- Chapter 34. Signed Distance Fields Using Single-Pass GPU Scan Conversion of Tetrahedra
- Chapter 35. Fast Virus Signature Matching on the GPU

- Part VI: GPU Computing
- Chapter 36. AES Encryption and Decryption on the GPU
- Chapter 37. Efficient Random Number Generation and Application Using CUDA
- Chapter 38. Imaging Earth's Subsurface Using CUDA
- Chapter 39. Parallel Prefix Sum (Scan) with CUDA
- Chapter 40. Incremental Computation of the Gaussian
- Chapter 41. Using the Geometry Shader for Compact and Variable-Length GPU Feedback

- Preface