Abstract

The current state of the art in fluid simulation on resource-constrained devices is quite far behind what exists on more powerful machines with multiple processors and GPUs. There are existing applications which feature fluids in some way, and they fall into three different categories: 1) Simple particle systems, 2) Coarse grid-based simulations, and 3) SPH-based approaches (for water and other liquids). While I do not have any delusions about competing with a full-featured 3D GPU-based fluid solver, I believe my results are very promising and can give more believeable large-scale results. I have implemented a basic solver which achieves 30 frames per second with a simulation grid of 40 by 40 units and a display texture of 64 by 64 texels. On top of this, I applied the property of Galilean Invariance to enable moving the grid, scaled or unmodified, around to follow an area of interest. Finally, I implemented a very controllable particle system optimized for the iPhone CPU which can be advected by the simulated grid, basic Newtonian mechanics, or both. This hybrid approach of near-field simulation and far-field rendering works very well to create the illusion of complexity while still maintaining interactive framerates. I have also built a simple game to prove the utility of my design.

Background

State of the Art

Here, I will briefly describe the status of current fluid solvers. I do this not to give an idea of where my project is headed, but rather to show how far behind mobile devices are from a top-of-the-line solution.

GPU-based solvers

Here are NVIDIA's most recent fluid simulations running on their fanciest GPUs. The first is a volumetric smoke/fog simulation, the second is a multigrid heightfield simulation of near-shore waves, and the third exhibits their translating eulerian grid technique, simulating a small area around the car that drives particles through a much larger domain.





Mobile solvers

As mentioned above, mobile devices typically have not been used to simulate fluids, mostly because traditional methods of simulating and rendering are very computationally intensive. So, representations of smoke and other fluids on, for example, the iPhone, has been limited to basic particle systems, prerendered video sequences (left), coarse simulations (middle), and SPH-based approaches with very few particles (right).


Approach

In this section I will describe the different parts of my overall solution: the basic solver, translating the grid, and the particle system. In all cases, I used a similar demo scene, similar to the last video, above, to test the results: a car is directed around the screen and made to drive through checkpoints (green is the current target; blue is the next target). Smoke (density) is spawned and injected into the simulation when the car accelerates, and the car's velocity imparts velocity in the simulation, which advects the smoke in turn. I also created a settings screen that allows me to vary several things at runtime to show me the effects of different parameters:

Basic Solver

I began with a CPU implementation of a basic grid-based fluid solver, largely derived from Jos Stam's work [1][2]. I also found Bridson and Muller-Fischer's course notes invaluable in furthering my understanding and getting everything to work correctly [3]. The solver is a staggered grid that advects a density through a simulated velocity field. This density can optionally drive a buoyancy force, and a vorticity confinement force can be derived from and applied to the velocity field if desired. I chose open boundary conditions to simulate open air outside of the domain; velocity and the boundaries is set to be equal to the velocity just inside and normal to the boundary, so that any advection will "keep going" past the edge.

In order to make the runtime more reasonable, I had to make some changes. First, I limited the number of Jacobi iterations in the incompressibility solver to half of what it was. This did not seem to introduce any artifacts in these small simulations, especially when there are nevery any huge velocities being imparted at a single time step. Second, vorticity confinement and buoyancy are optional to the solver, as not every scenario will require these effects. Third, when computing the buoyancy force, I use a strided approach to summing the total temperature, rather than add every grid square, which still results in an accurate estimate.

I explored a few options for increasing the quality and speed of this basic solver and ended up enabling a few tradeoffs. First, and perhaps most dissapointingly, the Accelerate framework for the iPhone did not make any difference in the speed of the linear algebra; likely because they are already so simple. However, other areas gave more promising results. I implemented a couple interpolation/upsampling schemes to be used for both advection and image reconstruction. Linear is the fastest, but lowest quality. Cosine interpolation is much better quality, and not much slower. Cubic interpolation is only a step above the cosine scheme and much slower than both. So, I settled on cosine interpolation for the final code since it led to smoother gradients with fewer blocky artifacts and less numerical dissipation at little cost. The difference between upsampling the 32x32 density field to a 256x256 texture in hardware with linear interpolation (left) and in software with cosine interpolation (right) can be seen below:

After this, I exlpored the separation between simulation and rendering quality more in-depth. Textures in OpenGL ES 1.1 have to be powers of two in either dimension, which makes a 32x32 grid a natural choice. However, a larger grid could still be simulated within my given time budget of 0.033 seconds per frame. First I tried upsampling in software to the next higher power-of-two and then letting the graphics hardware handle that. This works just fine, but with an unnecessary upsampling stage in software: using a smaller portion of a larger texture also works just fine, the texture coordinates used on the final full-screen quad simply have to be adjusted. However, I then lose everything I gained from the cosine interpolation when upsampling the density texture, which is perhaps the most important use of the better interpolation. So, this is just another tradeoff to take into account when designing a final product.

Translating Grid

Trying to spread a single simulation over such a large domain inevitably leads to artifacts, and blurring would be a hacky solution. It would smooth out the artifacts, but it would also smooth out any small-scale features that a successful smoke simulation relies on for realism. So, I decided to implement a technique that allows the simulation to move around the domain, following an area of interest [4][5]. In my demo (as in [5]), this area is the car, which makes it very easy to use the car's state to inject smoke and velocity, as before. For non-rotational inertial frames, a property known as Galilean Invariance can be used to move the frame of reference around. In order to do so, the contents of the frame are simply subject to a velocity opposite to that the frame itself sees. Moving the frame right with a speed of 3 units per time step means that the contents must be moved left 3 units per time step in order to stay fixed in the global coordinate frame. For my smoke simulation, this can be accomplished by adding a uniform velocity throughout the velocity field, then advecting the velocities and density as usual. So, the overhead for this technique is minimal, but it allows for the work to be put to better use.

There were two keys to getting this technique to work. The first is that boundary conditions are extremely important. If an open condition isn't properly enforced, then the uniform velocities could end up becoming part of the velocity field, rather than just moving it. Second, shifting the grid by a fractional amount introduces dissipation immediately, both in the density and velocity. So, I found it helpful to keep track of all the fractional offsets and only apply them when they were greater than one, keeping the remainder for the next time step.

Particle System

As in [5], I decided to expand the visualized results to outside of the simulation domain with a particle system. The particle system itself is reasonably complex - each particle has an age-based position, size, and color. The particles are spawned from sources with a set number of particles to spawn, a general position, initial velocity, and particle spawn rate. The simulation and the particle system are only coupled in one direction at the moment - I briefly looked into influecing the velocity field at the edges of the grid whenever a particle wanders into the simulation, but this caused instabilities, and I'm not sure that an extra incompressibility step is worth the effort. Instead, one-way coupling is enough for now. Particles inside the simulation grid are advected by the velocity field, while particles outside the simulation grid behave under regular Newtonian forces - momentum, wind, drag, etc. Particles near the edge of the simulation broundary are blended by both "inside" and "outside" velocities so that the boundaries are somewhat obscured.

Several techniques I thought of, tried, or otherwise stumbled upon turned out to be very important for the overall efectiveness of this approach. Firstly, shapes other than squares work much better and blend more naturally. I settled on hexagons, with one point in the middle with an age-based opacity, while the perimeter vertices have zero opacity for a smoothly-fading effect. The age-based size was also important to approximate the smoke's dissipation. Finally, randomly applying an offset to the spawn position of the particles was key in better filling the space.

I also added support for a couple features that I ended up not using due to lack of bang for the buck - they just weren't noticeable enough to justify the extra work. The first is texture-mapping the particles. I tried both Perlin noise and a smoke-like texture, but neither was worth the extra processing necessary to make it happen. With better graphics hardware, I'd put this feature back in first. The other feature is per-particle angular velocity and momentum determined by the curl of the velocity field in the simulation. Given nearly round particles, this was completely unnecessary. However, with textures, the rotations could be more visible and visually appealing.

Results

Unless otherwise stated, all the results shown here run at 30fps on the iPhone 3G.

Basic Solver

To get an idea of how (not) powerful the device is, here is a chart of frame time vs. grid size. The results of the simulation were visualized by hardware resampling using a texture of the next-larger power-of-two.

On the left is a 16x16 grid, which gives a framerate of 60fps. However, it is unacceptably ugly. The 40x40 grid on the right gives much better results at a reasonable 30fps.

Translating Grid

On the left is a 40x40 grid, scaled by a factor of 7, following the car around on its mission. The right is a similar scene, but the extents of the simulation are shown rather than the results.

Particle System

I started with 4000 maximum particles in the system, but this was clearly too many. 1000 seemed more reasonable, but I finally settled on 700 as a nice mix that will reliably yield 30fps results. The results can be seen below; the first video shows the particles only as they are advected by a close grid, while the second video also includes a visualization of the extents of the simulation grid.

Further Work

There are a couple immediate changes I plan on making:

I also have some long-term enhancements that may or may not happen:

References

  1. Jos Stam, "Real-Time Fluid Dynamics for Games". Proceedings of the Game Developer Conference, March 2003.
  2. Ronald Fedkiw, Jos Stam and Henrik Wann Jensen, "Visual Simulation of Smoke", In SIGGRAPH 2001 Conference Proceedings, Annual Conference Series, August 2001, 15-22.
  3. Robert Bridson and Matthias Muller-Fischer's 2007 SIGGRAPH course on fluid simulation for computer animation.
  4. Maurya Shah, Jonathan M. Cohen, Sanjit Patel, Penne Lee, Frédéric Pighin, Extended Galilean invariance for adaptive fluid simulation. 2004 Symposium on Computer Animation.
  5. Jonathan M. Cohen, Sarah Tariq, and Simon Green, Interactive Fluid-Particle Simulation using Translating Eulerian Grids. Interactive 3D Graphics and Games (I3D) 2010.

Code

Since this is an iPhone project, putting a demo up would be nearly useless. So, I've included just the relevant code necessary to use the fluid solvers, smoke classes, and particle system in any project. Also included are some various other classes I developed, such as a Sound Manager, that don't have anything to do with smoke simulations. With the exception of the Perlin noise (found on Perlin's website), all the included code is mine, though the basic fluid solver was based on a modified version of [1]. It was, however, nontrivial to make it work in a full project and then port to the iPhone environment. This code can be found here.