VorteGrid:

Interactive Fluid Simulation

for Games and Movies

by Dr. Michael J. Gourlay

Many fluid simulations run slowly. Games need fast solutions, even if at the cost of accuracy.

Fluid simulations can be slow for many reasons, including these:

Flow treated as incompressible imposes a divergence-free condition which requires a global solution to enforce that condition.
Solutions can be unstable. Making them stable requires either explicitly high viscosity or unintentionally incorporates very high "numerical" viscosity from implicit solvers, which degrades details and makes the simulation look muddy.
- Techniques that try to compensate by artificially injecting detail just looks like noise instead of the beautiful filamentary wisps that characterize fluid flow.
Traditional approaches to satisfying boundary conditions require global solutions and often entail imposing constraints on the shape of the simulation domain. Simulations that can handle complicated boundary conditions (such as arbitrary shapes or expanding boxes) typically employ sophisticated and computationally expensive techniques, such as dynamic regridding or level set methods.

These problems have solutions. Mesh-free algorithms simulate interactions between particles. These techniques lack numerical diffusion and preserve detail. Naive direct computations of such interactions require a computational complexity of O(N^2). Approximate methods such as fast-multipole and treecode can consume O(N log N) operations. But games need faster techniques.

Real-time simulations exploit the embarrassingly parallel nature of the fluid simulation algorithms. Some use massively parallel graphics processing units (GPU's). While these simulations to indeed run in real time, they rob video games of an important resource, which is the ability to render complex and compelling virtual environments and characters. Games require solutions that use CPU resources for simulation and leave GPU resources for rendering.

This vortex particle simulation solves these problems.

It's used in professional software like Red Giant Trapcode Suite 15.

I explain below how it works, in 21 articles, with demo videos and source code, all free.

Objectives

A fluid simulation for video games should satisfy these requirements:

Fast; The simulation should run in real-time: 30 frames per second or faster.
Controllable; Effects artists should be able to author effects, and influence or steer flow.
Detailed; Flow should retain fine details such as wisps since they are aesthetically pleasing.
Flexible; Fluid region should be able to expand to any size and any shape, with open or closed boundaries.
Scalable; The simulation should work for large and small effects.
Plausible; Results should have the ability to appear natural and not appear distractingly artificial.
Beautiful; Results should appear aesthetically pleasing.
Accessible; The implementation should be affordable to write and easy to understand.
Robust; The implementation should be easy to modify and tune without introducing numerical instabilities.
Interactive; The fluid should interact with other entities, including user-controlled, moving or stationary.
Parallelizeable; The simulation code should exploit multiple cores when they are available.
The simulation should handle multiple immiscible fluids such as water with air, combustion (fuel, plasma and exhaust).
The simulation should work with 2D or 3D flows.

Method

My choice of simulation uses a vortex particle method: Particles representing small vortices (called "vortons") induce a velocity field which in turn moves the vortons.

Tracking vortons means the fluid lacks numerical viscosity that erodes detail in simulations that use grid-based methods. Also, a relatively small number of vortons induces a pleasingly chaotic velocity field which drives a much larger number of passive tracer particles used for rendering. Effects authors can control the number of vortons independently from the number of tracers, thereby separately controlling simulation and rendering resolution.

Grid-free particle methods such as the one these simulations employ only need particles in regions where the flow behaves "interestingly", which is near vortices. Vortices induce fluid motion. They also represent a (potentially very high resolution) velocity gradient which implies that a grid-based solution would require twice or more the resolution in each direction so for example to simulate the same flow in a grid-based simulation would require 2x2x2=8 times as many grid points -- and that assumes vortices densely populate the entire grid, which is unlikely. Furthermore, grid-free methods can conform to any shape without expensive regridding techniques.

This simulation provides multiple velocity-from-vorticity solvers: A direct solver provides a gold-standard exact (but slow) velocity calculation for comparison with other methods. Some simplify far-field interactions by using integral methods, either treecode or a novel "monopole" approach. Another uses a multigrid Poisson differential solver. Yet another uses a treecode to compute vector potential at boundaries and a Poisson solver elsewhere, yielding the best of both approaches: speed, high quality and flexibility.

In one incarnation, the algorithm exploits nearest-neighbor information, and incidentally includes a new approximate dynamic nearest neighbor tracking algorithm that runs in linear time. In the nearest-neighbor incarnation, the simulation approximates spatial gradients by comparing properties of each particle with that of its neighbors.

In another incarnation, the simulation transfers quantities from particles to a grid where spatial gradients are computed, then updates the source particles.

Vortex stretching and tilting plays a crucial role in the cascade from laminar to turbulent flow. For visual effects, authors can inject pseudo-turbulence a priori. This simulation includes vortex stretching and tilting by computing spatial gradients of velocity, but games may elect to omit those terms if they inject turbulence artificially.

To handle stratified fluids and multiple fluids with different densities the simulation must handle baroclinic generation of vorticity. In principle that requires knowing both density and pressure gradients, but this simulation assumes pressure gradients come from hydrostatic equilibrium. The simulation includes a combustion model which generates heat that feeds the baroclinic generator to create fire and smoke plumes.

A particle strength exchange (PSE) approach facilitates computing viscous and thermal diffusion, thereby avoiding a need to compute high-order spatial gradients using a grid.

Effects authors can control flows using two methods: They can tune fluid flow parameters and they can use traditional particle operations such as commonly occur in visual effects packages, like emit, wind, grow and kill.