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. In Chapter 29, "Real-Time Rigid Body Simulation on GPUs," Takahiro Harada from 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 Crane from the University of Illinois at Urbana-Champaign and Ignacio Llamas and Sarah Tariq from 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 Nyland and Mark Harris from NVIDIA and Jan Prins from 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. In Chapter 32, "Broad Phase Collision Detection with CUDA," Scott Le Grand from 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, in Chapter 33, "LCP Algorithms for Collision Detection Using CUDA," Peter Kipfer from 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 Erleben from the University of Copenhagen and Henrik Dohlmann from 3Dfacto R&D in Chapter 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