Hive Assault: Computational Fluid Dynamics
Approximating Gas Flow in a Real-Time Environment
Information on the implementation of a CFD engine fast enough for 3d gaming
Scott Schaefer, 2001. Email: sschaefe@rice.edu
The fluid dynamics done in the game is very simple. We make the
assumption that we have a perfect, linear flow. This means that it cannot
have really interesting behavior like eddies. In reality, this would never
happen, however, we must make sacrifices in order to achieve real-time
performance. More specifically, we will model the flow as the gradient of a
scalar field. It's the scalar field that we'll actually model and
approximate its derivative when the flow at a certain point is needed.
We'll model the flow by doing an iterative update in with the mask 1-w
for the center coefficient and w/n for the n neighbors of this cell. "w" is
a coefficient that should be time and grid space dependent and determines
how quickly flow can move over some interval in both space and time. In
order for the system to converge we require that "w" is greater than 0 and
less than 1. So if N is the set of all neighbors of some node x, then the
update equation is now
Flow[x]=(1-w)*Flow[x]+Sum[w*Flow[n]/|N|, n is an element of N]+b[x]/|N|
In this equation "Flow" is the scalar value at the index specified, "w" and
"n" have previously been defined and "b" is the correction term. The
correction term is the value of the emission for that grid square. For most
squares, this will be 0. However, for sources, this value will be positive
and it will be negative for sinks. In order for the system to converge, we
require that the sum of all of the sources and sinks is 0 i.e. b.1=0 where 1
is the vector of all 1's. At each iteration the entire scalar field is
recalculated based on the old scalar field.
To determine the flow at a given grid point we'll calculate the flow
at the boundaries of the grid square that contains the point in question and
use linear interpolation across each dimension to determine the flow at the
given point. To determine the flow at a boundary of the grid square we'll
just take the scalar value of the adjacent square and the square in question
and subtract them in the axis-aligned direction. In one dimension we'd find
the value of the flow on both sides of a square by
right = Flow[x+1]-Flow[x]
left = Flow[x]-Flow[x-1]
We can then interpolate the two values across the square to the desired
point. This is only one dimension and needs to be repeated for all
dimensions involved (three in the game).
Walls
Walls can be incorporated very easily into this model. Essentially,
we remove the neighbor from a square if there exists a wall between the two
squares. To calculate the flow we use the value 0 for the flow across
adjacent squares if there is a wall between them. This has the property
that there is no normal flow along walls.
Making It Run Fast
There is still the question of how to implement it so that it runs
quickly. Checking for walls for every grid square on each iteration is not
the way to make it fast. We implemented a small table of masks that was
indexed by the wall configuration. There are a small number of possible
wall configurations for a given square. If all of the coefficients for all
of the neighbors and the square in question are kept in a table indexed by
the wall configuration, then those coefficients can just be multiplied by
the respective members without any if-statements. If there is a wall
between two squares, then the coefficient of the other square becomes 0.
Extraneous numerical operations are performed, but no branches occur.