Fluid simulations in Computer Graphics seek to provide an approximate solution to the Navier-Stokes equations (NSE) which represent the motion of a fluid. These equations can have different formulations, in the general form, they express the total time derivative of the velocity of a single particle of fluid i as:
where represents the density of the particle, is pressure, is mass, and is the kinematic viscosity. The term accounts for the acceleration of the particle due to pressure differences inside the fluid, which generally
dominate all other forces. The term represents the acceleration due to friction forces between particles with different velocities, where is usually determined empirically to provide a realistic behavior. Finally, F represents external forces pushing the fluid, e.g. gravity. Existing particle-based methods have to cope with several problems when solving NSE. The first is the nearest neighbor’s search, since at each iteration, we must determine the interactions of each particle with its closest neighbors. Collision detection and handling are also important to prevent particles to cross boundaries or to simulate two-way coupling with rigid objects immersed in the fluid. Finally, for incompressible fluids such as water, extra care must be taken to guarantee that the overall volume stays approximately constant during the simulation. Stochastic Rotation Dynamics     is known to provide a generally good approximation to Equation (1) under certain conditions. It relies on a particle-based representation and a grid of regular square cells containing the particles. At each time step, particles are stored into a single cell, and particles in the same cell contribute to the center of mass velocity of this cell. The velocity of a particle at the next time step is updated by combining the center of mass velocity of its associated cell and a random rotation. However, this model is generally not able to reproduce the behavior of incompressible fluids, as the number of particles inside a cell does not stay constant.
After presenting existing particle-based methods in the next section, we present in Section 3 a generalization of the SRD model introducing additional computation steps, called local repulsion and cell pressure steps, in order to handle incompressibility. We also present a two-way coupling method that process collisions between the fluid and immersed objects. The implementation of our method on the CPU and the results we obtained are discussed in Section 4, including different types of simulations such as dam-break flood, falling droplets and mixing of two fluids.
2. Particle-Based Fluid Simulations
The Smooth Particle Hydrodynamics model (SPH) was proposed for water simulation by Muller et al. in 2003 , and is now one of the most popular methods in Computer Graphics. A complete survey of this approach can be found in . The main idea is that each quantity associated to particle i (i.e. viscosity, density, etc.) can be approximated by interpolating quantities at neighboring particles j with a kernel function W which depends on the distance between i and j:
The nearest neighbors’ search usually relies on a grid with fixed-size cells and represents approximately 80% of the total computation time. The algorithm then runs as follows at each time step and for each particle: compute density, then compute pressure, viscosity and external forces, and finally apply these forces to update velocity and position. To handle collisions with fixed or moving objects, most existing works make use of additional particles located at boundaries, which contribute to density and pressure computations and prevent penetration of fluid particles inside solid objects. Different methods were also proposed to guarantee incompressibility, where the main idea is to constrain density computation to reach a desired target value before pressure forces are applied.
Particle-In-Cell (PIC)  and Fluid-Implicit-Particle (FLIP)  are hybrid models that rely both on a particle system and on a grid with fixed-size cells (see  for a complete survey). As with SPH, particles are used to represent the fluid with their own position and velocity, but density, pressure and viscosity forces are computed at fixed positions in cells. These positions are usually defined at the midpoint of each edge (staggered Marker and Cell, or MAC). At each time step, velocities must be interpolated from particles to cells, and forces from cells back to particles. PIC and FLIP approaches essentially differ in the interpolation scheme, which can introduce dissipation, artificial viscosity and/or visible noise at the interface. Both approaches are combined in  to alleviate these problems and enforce incompressibility, which can be more easily achieved than with SPH. However, pressure computations now require to solve a large linear equations system on the grid, representing usually more than 1/3 of the total simulation time. Collision handling with boundaries can be achieved directly using the grid by marking cells as empty (or air), fluid or solid; for moving objects boundary particles can be used as with SPH.
A specific type of particle-based models can be found in the field of human crowds simulations   . Here two-dimensional particles represent individuals whose goal is to reach a specific destination, but at the same time must also avoid collisions with obstacles or other individuals. These approaches rely on concepts very similar to those found in PIC/FLIP methods mentioned above to handle density, friction, incompressibility, collision detection, etc. Such systems can be used for example to simulate the behavior of large, dense crowds evacuating a building, which indeed closely resembles to particle dynamics in a fluid.
The Stochastic Rotation Dynamics model (SRD), also known as Multi Particle Collision Dynamics (MPCD), was first introduced in  for fluid simulation at mesoscopic scale (for material larger than the nanoscale size in condensed matter physics). As in SPH or PIC/FLIP methods, fluid particles are defined by their position and their velocity , and are distributed in a regular cubic grid. We note the linear size of each grid cell (or SRD cell), and the desired average number of fluid particles inside a cell. At each iteration, a collision step and a streaming step are successively applied.
During the collision step and for each SRD cell, a rotation is applied to the velocities of each particle i inside this cell:
where is the time step between two iterations, v is the center of mass velocity for this cell, and represents a two-dimensional rotation of angle . This angle can be chosen randomly within a given interval, hence the name “stochastic”. Figure 1 shows the decomposition of this computation for a single cell. Before the collision step, a translation can be applied to all particles with a random vector within the interval . This extra computation forbids particles to always interact with the same neighbors in order to restore the Galilean invariance assumption , but was not found to have a significant impact in our work where the neighborhood of a particle changes rapidly.
During the streaming step, particles are simply advected by:
Finally, some extra steps are needed to compute collisions and interactions between particles and solid objects immersed in the fluid. For example, repulsive interaction forces are explicitly computed between particles and solid grains to avoid inter-penetration in .
The SRD approach is designed for applications in condensed matter physics, and it provides a good approximation to Equation (1) if sufficiently small values are chosen for the grid resolution and the time step . Its major advantage over the methods presented above is its very simple formulation, and also the fact that it does not need an expensive nearest neighbor search. However, it also suffers several weaknesses for applications in Computer Graphics. The main issue is that the number of particles inside an SRD cell can be very different from the desired value , leading to compressibility effects when adding gravity. As a result, it is hardly possible with SRD to achieve regular fluid simulations such as water jets, falling droplets, dam-break flood, etc.
To overcome these problems, our approach combines the simplicity of the SRD model with specific modifications designed to take other phenomena into account. These modifications, inspired by PIC/FLIP methods, are presented in the next section.
3. 2D SRD for Fluid Simulation: Our Approach
Figure 2 summarizes the computation of a complete-time step with our approach,
Figure 1. Collision step inside an SRD cell described by Equation (3): (a) Initial velocities at time t; (b) Average velocity v assigned to each particle; (c) Rotation of by a random angle ; (d) Final velocities at time .
Figure 2. Summary of our algorithm: (a) Initial positions and velocities; (b) Local repulsion; (c) SRD collision step; (d) Computation of pressure gradient at the center of each cell; (e) Modification of velocities based on pressure; (f) Final positions.
starting with positions and velocities for the particles at time t (2a). First a local repulsion step is used to avoid particle clustering (2b), then we apply the SRD collision step described earlier (2c). To handle pressure effects, a pressure gradient is computed for each cell (2d) and is used to modify the local velocity of each particle (2e). Finally, we use this velocity to advect particles to their next position at time (2f). The following paragraphs focus on the computation of local repulsion and pressure forces, which are the key modifications we add to the original SRD method. We also describe how to handle collisions with fixed or moving objects.
3.1. Local Repulsion
The original SRD model does not prevent particles to lie too close to each other, which can generate particle clustering. The purpose of our local repulsion step is to displace particles such that they keep a minimal distance between them. This parameter can be computed from the size of a cell and the desired average number of particles inside a cell :
For each particle i, we first need to find which are its closest neighbors, thanks to a classical nearest neighbor search . As this search is limited within radius , which is lower than , we only consider particles located inside the same cell and its 8 neighboring cells. Let denote the vector from i to another particle j. If the distance between i and j is lower than , then we add a displacement vector d to particle j, whereas i is displaced by −d:
The velocities of i and j are also modified, using and respectively, where is a user-defined parameter (set to 0.1 in our implementation). The whole process can be repeated multiple times to ensure that all particles will eventually reach their correct position, as illustrated in Figure 2(b). In practice, our experiments showed that this simple approach converges very quickly, generally with only 3 runs.
3.2. Cell Pressure
Once the local repulsion completes, the velocity of each particle is updated using the SRD collision step (Equation (3)). However advecting particles at this stage is not sufficient to handle pressure differences inside the fluid, for example, if we apply a gravity force. As shown in Figure 3 (top) many particles can still enter a single cell, hence volume conservation is not guaranteed. To tackle this problem our cell pressure step defines a velocity field on the cell grid from the center of mass velocity v, which should stay divergence-free, i.e. . First, we compute the divergence at each grid cell:
Figure 3. Top row: dam-break simulation using cell pressure computation, captured at frames 250 (a), 350 (b), 450 (c) and 650 (d). Bottom row (e-h): dam-break simulation using only local repulsion, captured for the same frames, where the loss of volume becomes visible.
where represents the density ratio between the number of particles located inside the cell and the desired number . The pressure in each cell can be found by solving a linear equations system on the grid, as in PIC/FLIP methods. Our implementation uses the Jacobi method  and starts by setting . The following recurrence formula is applied during k iterations:
In practice, if a cell does not contain any particle, we set its pressure at each iteration. From the scalar pressure values, we can then compute the pressure gradient in each cell by:
Finally, the velocity of each particle is linearly interpolated with the pressure gradient using the density ratio of its associated cell:
The number of iterations k for the Jacobi method can be chosen between 5 and 40, depending on the desired compromise between computation time and precision. In all our experiments, the value was sufficient to ensure volume conservation, as shown in Figure 3 (bottom).
3.3. Collision Handling
As noted previously, most existing works in fluid simulation use additional particles to handle collisions with objects. We apply the same technique for fixed boundaries, for example on the walls of the simulation box (see Figure 4(a)). These solid particles do not move but are considered during the local repulsion step to prevent fluid particles to cross a wall. However, it may still happen that a fluid particle flows out of the simulation box: in this case, we simply displace it back inside. We can also reduce its velocity in order to generate an adhesion
Figure 4. (a) Solid particles covering the bottom wall of the simulation box. (b and c) Ball falling inside the fluid at rest. (d) Ball flying up with the flow.
effect on the surface, or mirror its velocity in the opposite direction to generate a bouncing effect.
In the case of a moving object, we also have to create a set of solid particles on its boundaries at the beginning of the simulation. In the following, we take the example of a simple ball represented by a circle, coated with solid particles on its perimeter. We also store its position and its velocity , used to advect the ball at each iteration. If a fluid particle enters the object during the local repulsion step, it will bounce or adhere to the surface as in the fixed case. Solid particles are marked with a boolean value if they interact with at least one fluid particle, i.e. if they are within distance (represented in red in Figure 4(c)). At the end of this step, a fraction of the velocity of each marked particle is added to the velocity , again using a user-defined parameter set to 0.1 in our implementation. This generates a two-way coupling between the fluid and the object. During the cell pressure stage, solid particles are considered when computing divergence and pressure. This is especially important for the cells where a void is induced by the presence of the ball (represented in green in Figure 4(c)), which would otherwise lead to incorrect results. Finally, we can also simulate a buoyancy effect by reducing the gravity force applied to the ball depending on the number of marked particles on its boundary, roughly approximating the area of the fluid displaced by the ball.
Figure 4(b) and Figure 4(d) show two examples of our results. More complicated objects can also be handled with this approach, as long as their boundary can be discretized with solid particles. However, if the shape is not circular its orientation must also be taken into account, and the two-way coupling in this case should include a rotation matrix.
4. Results and Discussion
The fully animated version of the examples presented in this paper is available on video: https://bit.ly/336hb8R. Our CPU implementation running with Processing  contains approximately 500 lines of code, and can be downloaded here: https://bit.ly/31v8dk5. The code is structured into three basic classes:
· In the main class we define all the parameters, initialize the objects corresponding to particles and cells, then run the simulation iterations in an infinite loop. This loop also includes the interactions with the user (keyboard or mouse) and the rendering.
· The Particle class first declares the attributes of a particle such as its position, velocity, the index of its associated cell, etc. The computation of the local repulsion and SRD collision steps is defined here, as well as the application of the gravity and the pressure force, and finally the advection of a particle before the next iteration.
· The Cell class declares the attribute of a cell, including its position and a list of the particles it contains. All the code needed for cell pressure computation is defined here, such as average velocity, divergence, pressure, pressure gradient and density ratio. An integer value is also used to characterize if the cell is empty, has an empty cell neighbor, or is surrounded by non-empty cells.
· An additional Ball class defines the behavior of the moving ball discussed in Section 1.
The two main parameters in our model are the size of a cell and the desired average number of particles inside a cell , even if other parameters can be tweaked. As an example in Figure 5 shows different configurations for the dam break simulation with varying values for and , that can be compared with Figure 3 where and . If is very low, as in the first and third images, the simulation loses precision but the overall behavior is conserved. In all our experiments the other parameters are set as follows: the unit size is 1 pixel, the simulation box has size 640 by 640, the time step , the gravity is set to 9.81, the number of iterations for the local repulsion step to 3, and the number of Jacobi iterations for the cell pressure step .
Table 1 gives the computation time per iteration measured for the dam break simulation with different and values, as well as the percentage of time spent to compute local repulsion and cell pressure. As can be observed the repulsion step represents the main bottleneck for our CPU implementation, with more than 75% of the computation time. This can be explained by the fact that this step depends on the number of particles and makes use of an expensive nearest neighbor search. It is worth noticing that this percentage looks similar in SPH-based simulations, where the same bottleneck influences the simulation.
Figure 5. Dam-break simulation with different input parameters. From left to right: .
Table 1. Computation times with different and values.
On the contrary, the cell pressure step mostly depends on the number of cells and only has a limited impact on the total computation.
Different problems with our method are noticeable in some of the pictures presented in this paper. For example, the resolution of the grid can become visible at the interface between the fluid and the empty space, creating an aliasing effect as in the right image of Figure 5. Small bumps can also be observed on this interface, as in the left image of Figure 6 where the surface at rest is not perfectly flat. Another issue is that, due to the stochastic nature of the SRD method, our simulations exhibit non-symmetric behaviors, e.g. in Figure 6 where the droplet falling exactly at the center of the box generates different patterns on each side. In this case, the non-uniform distribution of particles inside the droplet also plays a part. One final issue is our local repulsion step which creates a rather rigid behavior in high pressure regions deep inside the fluid, where particles tend to wriggle to resist gravity.
On the other hand, despite its inherent approximations, our method succeeds at reproducing some interesting effects observed in fluid dynamics with dam-break flood or a falling droplet simulations. For example, realistic liquid sheets, i.e. particles in the air appearing linked by a cohesive force, are visible in Figure 4 and Figure 6. This behavior is rather surprising since our method does not specifically address the surface tension phenomenon that drives this type of effect. Figure 7 shows how our method is also able to generate vortices. Here the gravity is set to 0 and the fluid is separated into two populations of green and blue particles, depending on their initial position in the box. After the green particles
Figure 6. Droplet falling inside a volume of fluid, repelling particles on both sides and generating liquid sheets in the air.
Figure 7. Vortex created at the interface between colored particles. Here gravity is set to 0 and the fluid is separated into two populations of green and blue particles. After the green particles are slowly pushed downwards, two vortices appear.
are slowly pushed downwards, two typical vortices start to appear.
The approach presented in this paper is based on the Stochastic Rotation Dynamics model, which by nature leads to instabilities because of the random rotation used in Equation (3). However, by extending this simple approach with additional steps related to pressure and collision handling, it is possible to obtain convincing results that faithfully reproduce the behavior of incompressible fluids. As a proof of concept, our method was implemented on the CPU to create different types of simulations such as dam-break flood, falling droplets and mixing of two fluids.
In future work, we would like to investigate further how our approach could be used to simulate viscous fluids, by modifying the angle parameter in Equation (3) to damp the velocity of particles colliding inside a cell. The time step parameter could also play a part here since it directly impacts the overall number of SRD collisions.
We also wish to address the problems described in Section 4. The main improvement concerns the local repulsion step, which currently represents more than 75% of the total computation time and leads to instabilities in high pressure regions. This goal could be achieved through a parallelized GPU implementation, which is already available for compressible fluids . This would reduce the cost of the nearest neighbor search and allow an increased number of particles in our simulations.
This work is supported by institutional grants from the LabEX SigmaLim (ANR10-LABX-0074-01) and by the MIRES Federation.
 Ihle, T. and Kroll, D.M. (2001) Stochastic Rotation Dynamics: A Galilean-Invariant Mesoscopic Model for Fluid Flow. Physical Review E, 63, Article ID: 020201.
 Padding, J.T. and Louis, A.A. (2006) Hydrodynamic Interactions and Brownian Forces in Colloidal Suspensions: Coarse-Graining over Time and Length Scales. Physical Review E, 74, Article ID: 031402.
 Shakeri, A., Lee, K.-W. and Pschel, T. (2018) Limitation of Stochastic Rotation Dynamics to Represent Hydrodynamic Interaction between Colloidal Particles. Physics of Fluids, 30, Article ID: 013603.
 Brackbill, J.U., Kothe, D.B. and Ruppel, H.M. (1988) Flip: A Low-Dissipation, Particle-in-Cell Method for Fluid Flow. Computer Physics Communications, 48, 25-38.
 Tran, C.T., Crespin, B., Cerbelaud, M. and Videcoq, A. (2018) Colloidal Suspension by SRD-MD Simulation on GPU. Computer Physics Communications, 232, 35-45.