Along with mentioning a strange rash, a sure way to kill a conversation is to bring up the topic of Computational Fluid Dynamics (CFD). But for those who wish to create fantastic-looking clouds, explosions, smoke, and other game effects, nothing could be more exciting!

CFD is the section of fluid mechanics that finds numerical solutions to the equations describing the behavior of fluids, both liquid and gaseous, and their interaction with various forces. Until recent hardware advances, even approximating a solution was too computationally intense for real-time applications.

However, the last year or two has shown a small but increasing amount of research and articles, as well as the release of some commercial products that deal with simulating fluids, not only in real time but in a video game environment.

With the Kaboom project, we've created a modular, threaded CFD simulation that can be dropped into an existing project, hooked up to a rendering engine, and used to generate realistic, real-time fluid dynamics simulations, suitable for smoke or water.

We observed that many games are not reaching their full potential because they're unable to use all of the available CPU resources. Frequently, this is because they are not properly threaded for multi-core architectures.

Rather than run the simulation on the GPU, we decided to use those extra cycles to produce a basic, real-time fluid simulation. By performing the simulation on the CPU as opposed to the GPU, the simulation has fast and easy access to all game resources (such as mesh information) and the game has access to the simulation results. This also leaves the GPU free to handle the graphics.

As we continued our research we found that although interest in fluid simulations was high, little concrete material was available, especially in the way of code and examples. We were unable to find examples of 3D or multi-threaded solvers. Most of the articles described ways to solve the equations but did not use a multi-threaded approach.

Despite this, there seemed to be a lot of interest in the topic, so we decided that another goal of the project would be to make the resulting code modular and thereby fairly simple for someone to integrate into their own project. Developers can also use and expand upon the set of threaded, modular routines that we created for 3D CFD.

Simulation

The code is based on an article series and sample code written by Mick West that was recently posted on Gamasutra.^1,2 Since one of our goals was to produce a modular, reusable code base, the first thing we did was to convert the existing sample to C++ and separate the simulation from the rest of the application, specifically from the rendering.

This separation allows the simulation code to be easily added to an existing code base and rendering engine.

Next, we extended the code into three dimensions, which turned out to be a fairly straightforward exercise because none of the algorithms changed appreciably with the addition of another dimension.

For example, the 2D diffusion step is solved by applying the diffusion operation to move values from a cell to its neighbors (Figures 1 and 2). This approach is extended in the 3D case so that instead of inspecting four neighboring cells we look at six neighbors (Figures 1 and 3). Other cases used the same principle as well.

Figure 1. Transitioning code from 2D to 3D.

The following two code samples (Figures 2 and 3) show the code that performs the diffusion operation for non-border case cells in both the 2D and 3D cases. The border cells are those cells at the very edge of the grid that are missing one or more neighbors.

These cells are handled separately as special cases. The transition to 3D is accomplished by adding in consideration for the z-axis. Apart from that, the algorithm remains essentially the same.

Figure 2. A code sample that shows 2D diffusion.

Figure 3. A code sample that shows 3D diffusion.

After transitioning the simulation into 3D, we began investigating how to break the work up for parallel processing. As a base for our multi-core work we used the Intel Threading Building Blocks (TBB) package.

We found TBB to be very competitive in performance with other threading APIs. Additionally, it has a lot of built-in functionality and structures, such as a thread pool, task manager, and multi-threaded memory management.

The idea behind threading the simulation is data decomposition: take the grid and break it into smaller portions. These smaller portions are submitted as tasks to the task queue and processed by the worker threads, independently of each other.

The grid is broken up evenly until a small-enough granularity is reached, at which point further reductions become ineffective, or worse, inefficient due to thread management overhead. Figure 4 shows an example of how a 2D grid is broken into four tasks.

¹ West, Mick. "Practical Fluid Dynamics: Part 1" Gamasutra, 26 June 2008. http://www.gamasutra.com/view/feature/1549/practical_fluid_dynamics_part_1.php

² West, Mick. "Practical Fluid Dynamics: Part 2" Gamasutra, 23 July 2008. http://www.gamasutra.com/view/feature/1615/practical_fluid_dynamics__part_ii.php