Existing fluid simulations based on solving the Navier-Stokes equations or its derivatives are slow algorithms. For games, we need something faster, perhaps at the cost of quantitative realism.

Physically accurate fluid simulation entails correctly solving the Navier-Stokes equations, but finding such a solution is difficult and slow for several reasons:

• Typically the flow is treated as being incompressible, which imposes a divergence-free condition which requires a global solution (usually at each time step) to enforce that condition. Such solutions tend to be slow.
• Without care, solutions can be unstable. Making them stable requires either explicitly high viscosity or unintentionally incorporates very high "numerical" viscosity from implicit solvers.
• Satisfying boundary conditions also tends to require global solutions and often entails imposing constraints on the shape of the simulation domain. Simulations that can handle complicated boundary conditions (such as arbitrary shapes or expanding boxes) tend to employ sophisticated and computationally expensive techniques, such as dynamic regridding or level set methods.

Some mesh-free algorithms entail simulating interactions between a collection of particles. These techniques have several advantages including a lack of numerical diffusion. Exact 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. Either complexity is too slow for use in games with current hardware.

Real-time simulations have become available by using the massively parallel nature of graphics processing units (GPU's) and the embarrassingly parallel nature of the fluid simulation algorithms. 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.

The fluid simulation shall satisfy these requirements:

• Fast; The simulation runs in real-time.
• Controllable; Effects artists must be able to influence or steer flow.
• Grid-free; Fluid region can expand to any size and any shape.
• Scalable; Computational and memory complexity are both O(N).
• Plausible; Results appear qualitatively similar to real fluids.
• Simple; The implementation is simple to implement and understand.
• Robust; The implementation is easy to modify without introducing numerical instabilities.
• Interactive; The fluid interacts with other entities, moving or stationary.
• The simulation can handle multiple immiscible fluids such as water with air and combustion (fuel, plasma and exhaust).
• The simulation works with 2D or 3D flows.

My choice of simulation uses something akin to point vortices (called "vortons") that interact with their nearest neighbors.

The algorithm incidentally includes a new dynamic nearest neighbor tracking algorithm that runs in linear time.

This simulation drastically simplifies far-field interactions and puts them under artist control. Effects authors can control such flows readily with flow field primitives such as commonly occur in visual effects packages, like wind and vortex (not to be confused with the vortons in this simulation).

Vortex stretching and tilting plays an important role in the cascade from laminar to turbulent flow but for video games we can inject pseudo-turbulence a priori . Still, we include vortex stretching and tilting, but we find the results without those terms remains visually pleasing and games may elect to omit those terms.

To handle stratified fluids and multiple fluids with different densities the simulation must handle baroclinic generation of vorticity which in principle requires knowing both density and pressure gradients, which we approximate by comparing per-particle mass with that of its neighbors and computing the influence of gravity per particle, balanced by an approximate buoyancy.

Grid-free methods such as the one this simulation employs fortunately only need to have particles in regions where the flow behaves "interestingly" i.e. at vortices. Vortices represent the most interesting regions of 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 e.g. 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.

• Michael Gourlay: Fluid Simulation for Video Games, part 1: Introduction to Fluid Dynamics
• Michael Gourlay: Fluid Simulation for Video Games, part 2: Simulation Techniques
• Michael Gourlay: Fluid Simulation for Video Games, part 3: Vortex Particle Fluid Simulation
• Michael Gourlay: Fluid Simulation for Video Games, part 4: Two-Way Fluid-Body Interaction
• Michael Gourlay: Fluid Simulation for Video Games, part 5: Profiling and Optimization
• Michael Gourlay: Fluid Simulation for Video Games, part 6: Differential Velocity Solvers
• Quentin Froemke: Multi-Threaded Fluid Simulation for Games
• Mick West: Practical Fluid Mechanics
• Jos Stam: Real-time fluid dynamics for games
• Jos Stam: Stable Fluids
• . .