Marker-and-Cell Method (MAC)

What is the MAC method?

The Marker-And-Cell (MAC) method was developed by Francis H. Harlow, J. Eddie Welch, and the T-3 team at the Los Alamos National Laboratory in 1965. This was the first successful technique that allowed incompressible fluids to flow properly without too much distortion requiring the calculations to be “reset” by hand as with the Particle-In-Cell method. In the MAC method, particles are used as markers that locate the material in a mesh which in turn defines the location of the fluid’s free surfaces.

At that time, the MAC method was considered unstable because the momentum of moving fluids would cause errors if the viscosity of the fluid was too low. This instability was resolved by Hirt in 1968, which ended up being a precursor to modern truncation error subtraction analysis. The MAC method is still in use today since it can now benefit from the use of conjugate gradient schemes which solve the Poisson equation, a method that models diffusion of a substance.

The video above shows a simulation orange and blue smoke using the MAC method.

About the MAC method

When using the Marker and Cell method, the fluid is modeled as a velocity field, which is “a vector field that defines the motion of a fluid at a set of points in space” (Cline, Cardon). In order to simulate a moving fluid with the MAC method, the velocity field is changed and evolved over time by moving marker particles through a space dictated by this velocity field. In addition to marker particles being used, a level set may be used to manipulate the velocity field.

It is impossible to store the velocity information of every possible point in a given space, the compromise of having a rigid grid with discrete points is made instead. The velocities between these points is then calculated via interpolation, creating the simulation of a fluid. Navier-Stokes equations are the basis of the rules which manipulate the velocity field in a MAC simulation . Basically, at each point of the grid there is an addition and subtraction using the values of a small neighborhood around said point.

The Navier-Stokes Equations

The Navier-Stokes equations are “a set of two differential equations that describe the velocity field of a fluid over time” (Cline, Cardon). The first equation, ∇· u = 0, is the mass conservation equation which states that the amount of fluid moving into any volume is equal to the amount moving out of the volume. In the simulation, a pressure term is used to solve the mass conservation equation.

The second Navier-Stokes equation, ^du/_dt = -(∇ · u) u - ¹/_p + v∇²u + F, governs how the vector field of the fluid changes over time. It accounts for the motion of the fluid through a given space while accounting for any internal and external forces that act on the fluid.

The left side of the equation, ^du/_dt is the derivative of the velocity of the fluid with respect to time.

The right side of the equation is made up of the following:

the convection term -(∇ · u) u which concerns the conservation of the momentum of the fluid,

the pressure term - ¹/_p which captures the forces generated by the pressure differences within the fluid,

the viscosity term v∇²u which handles the friction between the particles of the fluid that can slow down or speed up overall movement,

and the external force term F which factors in forces like gravity and contact with other objects that have an effect on the motion of the entire fluid.

Since the formula used is a derivative of the entire motion of the vector field for the fluid, it can only describe one dimension of the three dimensions in space at a time. These calculations are made essentially three times for each particle, and then the components are summed together to get the final result of the velocity of a particle in a specific cell on the grid.

The Cells in the Grid

The MAC grid method uses cells like the one shown in Figure 1, with each cell having a width h. Each cell has a pressure p and also three components for its velocity: u_x, u_y, and u_z. While the pressure is defined at the center of the cell, the three components of the velocity are placed at the centers of three of the cell faces. The u_x component is on the x-minimum face, the u_y component is on the y-minimum face, and the u_z component is on the z-minimum face. Harlow and Welch found that centering the velocity’s components on the centers of the minimum faces for each dimension produced more stable simulations as opposed to storing the components all in the center.

To display the fluid itself, a set of marker particles (the Marker in Marker-and-Cell method) are used to represent the volume of the fluid. While the simulation runs, an algorithm checks each cell to see if there is a marker particle in the cell. If there is, a sphere or the circle is rendered, which when hundreds of thousands are rendered look like a fluid.

Displaying the Grid

In the original iteration of the MAC method, rigid boundaries made up the grid for the volume of the fluid being simulated. The problem was that if the fluid did not take up the entire volume of the space that it was in (like a bucket of water not being filled all the way), many cells were being checked in the grid that were empty and might go unused for the entire simulation. This wasted space would significantly slow down the computation of the fluid to the point where in the 1960s and 1970s it was just not efficient to use the MAC method.

One of the recent ways to implement the MAC method in an efficient manner was found by Worley in 1996 and used by Steele in 2004. This new technique involved creating a dynamic grid that only makes cells in the fluid itself and then a layer around every fluid filled cell. The cells that do not contain or surround a fluid particle are then destroyed, greatly reducing the number of cells that have to be checked by the algorithm. The cells that are used are stored in a hash table that is keyed by the cell coordinates. The hash function presented by Worley is hash=541x+79y+31z.

Using a hash table-based grid as opposed to the original rigid grid that was used when the MAC method was developed greatly reduces the memory requirement when calculating the simulation and thus allows the MAC method to be relevant in modern fluid dynamics. While the number of cells is proportional to the amount of fluid being generated, there are still maximum and minimum boundaries used that define the edges of the container that the fluid is in. This prevents cell generation beyond a certain point and allows for simulation with surfaces and walls and even allows for a fluid to splash about instead of just flowing off into infinity. 

The Algorithm that Runs the Simulation

The algorithm that drives the fluid runs through these steps:

1. Calculate the simulation’s time step, t

2. Update the grid based on the presence of marker particles

3. Advance the velocity field, u

3.1 Apply convection components using a backwards particle trace

3.2 Apply external force components

3.3 Apply the viscosity components

3.4 Calculate the pressure to satisfy the conservation of mass equation

3.5 Apply the pressure

3.6 Extrapolate fluid velocities into buffer zone.

3.7 Set solid cell velocities.

4. Move the particles through the velocity field, u for ttime.

4.1 Check if t extends beyond the next displayed frame time. Advance the particles to the next displayed frame. Display the frame and repeat step 4.1

4.2 Move the particles through the velocity field, u for the remainder of t.

Creators: Jeff Dombroski, Taylor Gregory, Monique Shotande, and Eric Rackear