Abstract

Our project is FluidPong, a classic two-player game with a twist. In addition to moving the paddles, players can also manipulate the fluid on the board. We offer two different kinds of fluids, 1) SPH (particle-based) rendered with a metaball shader, and 2) Navier-Stokes (grid-based) rendered using bilinear filter shader.

Technical Approach

Rust & Bevy

We wrote FluidPong entirely in Rust. We used Bevy, a minimal game engine which provides an Entity-Component-System software pattern with a renderer, but no physics. We wanted to try using Rust after hearing many exciting things about its memory and type safety. Furthermore, Bevy provides a cross-platform renderer, which enables us to focus solely on the fluid simulation portion of our project, rather than having to wrangle OpenGL (or co.).

Smoothed Particle Hydrodynamics

One of the two approaches to fluid simulation that we tried out was a technique called Smoothed Particle Hydrodynamics (SPH). Fundamentally, fluids and the laws that describe them are continuous, and we can only approximate them with numerical methods. Different techniques for simulating fluids discretize them in different ways. SPH chooses to discretize the fluid using a collection of particles, each particle representing a small portion of the fluid.

Although it’s easy to think of each particle in an SPH simulation as representing molecules or water droplets, they do not directly represent such physical quantities. Rather, these particles are simply points in space at which the properties of the fluid, such as the mass and velocity, are known and stored. From these known points, we can derive the values of these properties at every other point in the fluid by continuously interpolating between them.

We interpolate these values based on a kernel function W, which describes the degree of influence each particle should have on a point in space depending on that point’s distance from the particle in question. Intuitively, it makes sense that the stored properties of a particle very far away should be weighted less. The interpolation equation is thus as follows:

With these foundations, we can interpolate any property A of the fluid based on the known values Aj at each particle position. Notice that the formula depends on the density ρ.

(For the sake of brevity, we omit discussion about the choice of W, but know that a “nice” choice for a kernel function typically tapers off to 0 after some kernel radius h. This property also enables a variety of optimizations to be made!)

To progress the simulation, our first step is to compute this density value. Plugging in ρ for A conveniently cancels out that factor in our formula, so we can compute ρ as a weighted sum of mass. We also compute a pressure p at each particle.

Now that we have computed the density and pressure in addition to the stored values of mass and velocity, we can compute the force density acting on each particle. In our model, this is

which is based on the Navier-Stokes equations for the motion of fluids.

The different contributions to this total force density are:

Pressure force fipressure = −∇p(r) — This component keeps particles from staying too close together. This is computed by differentiating the equation for A(r) shown above, which can be done quickly if the gradient of W is known.
Viscosity force fiviscosity = μ∇2v — This component speeds up slow-moving particles near fast-moving ones, and vice versa. This is computed using the Laplacian of A(r) shown above, which can also be done quickly if ∇2W is known.
Gravity force — This component is self-explanatory and only enabled if desired.
External forces — This component allows for user interaction, such as being able to grab fluid and flick it around the screen, or, in FluidPong, the paddles.

After computing this force density, an acceleration can be derived based on Newton’s second law, and, finally, we can use an integrator such as Euler’s method in order to update the positions and velocities of the particles before repeating the process over again.

This technique for simulating fluids performs remarkably well, for how simple the computations it requires are. SPH’s meshless, particle-based nature enables a high level of data parallelism, since each particle’s future state is only dependent on the states of the few particles around it. This made it a great candidate for FluidPong’s simulation backing, where we need an algorithm that is fast enough to simulate in real time.

The amount of calculation required for SPH for N particles is technically O(N2), but it can be reduced to near O(N) using acceleration structures. We used a uniform spatial partition, so that we can look up neighboring particles when doing local calculations for each particle.

Compared to grid-based methods, SPH is great at simulating scenarios where the volume occupied by the fluid at any particular point in time is much smaller than the possible range of the fluid in space, since it places the resolution (particles) where the mass currently is. However, certain properties such as boundary conditions are more difficult to model with SPH than with grid-based methods. Additionally, the performance of our implementation was heavily dependent on the parameters, and required significant fine tuning to be satisfactory.

Grid-based Navier-Stokes

The second approach we used to simulate fluid dynamics within a two-dimensional game environment was utilizing the Navier-Stokes model. The Navier-Stokes equations describe the motion of fluid substances and are expressed as:

Where u is the velocity field, p is the pressure field, v represents kinematic viscosity, and g denotes external forces like gravity. These equations, which describe the motion of fluid substances, were adapted to calculate the interactions and movements of fluid particles on a grid. Each grid represented a portion of the fluid with distinct properties such as velocity and pressure. To achieve real-time simulation suitable for interactive gameplay, we implemented a semi-Lagrangian method for advection, providing stable and accurate particle movement based on velocity fields by combining elements of both Lagrangian particle tracking and Eulerian grid-based calculation.

The functions implemented addressed diffusion, advection, and projection, each corresponding to critical components of Naiver-Stokes equations. Diffusion in the simulation is handled through a function that applies the diffusion process to a given velocity or scalar field, using a linear solver. This process simulates the physical phenomenon where particles spread out over time due to molecular motion, even in the absence of bulk motion. This diffusion is a discrete approximation to the heat equation part of the Navier-Stokes equation. Meanwhile, the advection is implemented through effectively capturing the derivative-free characteristic of incompressible flow. The implementation involves tracing fluid elements back to their origins over the timestep using bilinear interpolation to estimate new values from old positions. We also ended up utilizing Chorin’s projection method to maintain the incompressibility of the fluid for not only physical accuracy but also to separate the pressure calculation from the main velocity and density updates to reduce complexity per timestep.

Shaders

Metaball Shader

Metaballs are organic, blob-like objects that merge and blend into each other smoothly when they come close. Metaballs are commonly used to simulate fluid and gelatinous substances in graphics and animations, such as gel in Portal 2.

The concept behind a metaball shader involves using a function to define the influence or "field" of each metaball at any point in space. The field typically decreases with distance from the metaball's center. When multiple metaballs are near each other, their fields add together. The shader computes the total field at each point and uses a threshold to determine whether the point is inside or outside the metaballs.

For our particular metaball shader, we also calculated the relative speed and density using the metaball method to render color and opacity respectively.

Grid with Bilinear Interpolation Shader

We rendered the grid with the speed at each grid cell represented by color and density by its opacity. The game screen is 640 by 480 pixels and the grid resolution is 96 by 72 cells, which means the result is quite blocky. To resolve this, we used bilinear filtering which we learned in class during the texture sampling unit. Interpolating the values between cells resulted in the final smooth look.

Challenges

When we first implemented SPH, we were unsure if it actually worked because we did not tune the parameters. So we rewrote SPH, along with a custom simulation variable system that would allow us to tune the parameters as the simulation was running. This took a while to set up but helped significantly. This allowed us to verify and tune NS fluid quickly.

Results

References

Bridson, Robert, and Matthias Müller-Fischer. "Fluid simulation: SIGGRAPH 2007 Course Notes." ACM SIGGRAPH 2007 courses. 2007. 1-81. https://www.cs.ubc.ca/~rbridson/fluidsimulation/fluids_notes.pdf

Contributions

Trinity Chung - Navier-Stokes implementation

Anna Dymchenko - Pong implementation and integration with fluid

Oliver Ni - SPH implementation

Tiffany Sun - Shader implementation