Simulating grid-based fluids
other posts

algorithm

One way to model fluid flow in a computer.

Fluid dynamics are used in large numbers of physics simulations. This is partly because fluids look cool, partly because they are common, and partly because other actions can be simplified if the conservation of mass is handled by a fluid simulation.

Consider a small, fixed rectangular grid, like this:

Suppose this whole grid is filled with a fluid, such as water or air. Because most fluids can be treated as incompressible, we won’t model how much fluid is in each cell, but we will model how the fluid is flowing between cells and something we can use to visualize the situation, the amount of something (such as dye or smoke) in each cell. We’ll label the flows x1, y4, etc, based on their direction as follows:

Incompressibility provides the following constraint:

• x1y1 = 0 (no net flow into or out of c1)
• x1y2x2 = 0 (no net flow into or out of c2)
• x5 + y3y7x6 = 0 (no net flow into or out of c7)
• x9 + y8 = 0 (no net flow into or out of c12)

Note that these are 12 equations in 17 unknowns. The remaining 5 degrees of freedom represent the space of incompressible flows. When we write the constraints as a matrix equation, we end up with a 12-row 17-column matrix A times a 17-row vector f equaling a zero vector. Given a candidate 17-column vector f of flow rates, the basic incompressibility step is to find a new g such that A g = 0 that minimizes |gf| for some norm |.|. Many different norms and resulting solution techniques exist. For the common 𝓁2 norm, g = f - A+ (A f), where A+ is the pseudo-inverse of A. Efficient algorithms for finding A+ (A f) without computing the full pseudo-inverse exist.

In addition to solving for incompressibility, the main other action taken in fluid simulation is advection: updating the fluid based on its flow. Given, for example, the following flow field:

how do we decide how the cell contents and velocities change over time? If the flow was fixed this would be pretty straightforward, but the trick with fluids is the flow moves itself. For example, in cell 2 the fluid is moving mostly to the right; this, the “‍moving to the right‍” aspect of that cell is also moving to the right: in the next frame we’d expect cell 3 to have a stronger rightward velocity.

The basic idea of advection is that we compute the “‍velocity‍” of each point of interest as the average of is surrounding flows. For cell contents, the point of interest is a cell center; for flows, it is the center of a cell border. We then travel backwards in time along that velocity for the given frame time step size dt and compute the value from that cell. The following image shows the velocity at the point where x5 is defined and where the new x5 would come from.

This approach, called “‍back advection‍”, was designed by Jos Stam and published in 1999. It has the nice property that it is stable: that is, each new time step is guaranteed not to increase the energy in the fluid. On the flip-side, it can introduce artificial numerical damping, making the fluid appear more viscous than it should be.

There are many other approaches to grid-based fluids. Some use multiple advection steps. Some track the “‍vorticity‍” or “‍circulation‍” at each point as well as or instead of the fluid flow and use that to reduce the energy loss over time. Some store the flow in the center of the cells instead of on the edges. Some add in some particles inside the fluid that help track boundaries. Some don’t solve the equation for incompressibility, instead storing the pressure inside each cell and using that to cause what was compressed to spring back later. And there are many models that do not use grids at all.

This little write-up is just a first step into the complex and evolving field of fluid simulation. Hopefully, it will make the entry a bit easier for you.