Over the past few months, I have become greatly interested in environmental modeling and physical simulation. Recently, I had the opportunity to see the Pixar film The Good Dinosaur. The film, despite being one of the weakest films in the Pixar canon in terms of story and character development, set a new bar in terms of ultra-real environmental simulation and rendering. What I was particularly enamored by was the quality and realism of the river, which plays a central role in the film.
After seeing this film, I became very interested in the techniques by which fluids are simulated. After searching the internet, I discovered the Smooth Particle Hydrodynamics (SPH) algorithm. This algorithm is designed to provide a general purpose solution for simulating a variety of fluids. I found that it provides intuitive parameters for adjusting the qualities of the fluid, in particular the viscosity.
The paper describes a suite of techniques for modeling a discretized form of the Lagrange approach to the classical Navier-Stokes equations for fluids. Fundamental to this model are two concepts:
- A fluid is incompressible.
- The forces on a fluid can be expressed as the sum of convection, viscosity, and pressure terms.
Using SPH, the fluid is formulated as a set of discrete particles that move along with the fluid. Rather than being an infinitesimal point, the particles (and their mass) are thought of as being ‘smeared’ out over a radius. Each particle influences and is influenced by other particles with a radius of influence. The degree of influence a particle exerts over in its field is expressed using a kernel function, as described in the paper.
The paper describes three algorithms. I chose to implement Algorithm 1, as I found it to be the most intuitive and similar to the Lagrange approach. Each frame, the pressure, viscosity, and external forces are compute for every particle in the system. In my simulation, the only external force is gravity. The forces are summed for each particle. From each net force, the acceleration and velocity are computed and applied. Lastly, the SPH particles are rendered.
Depending on the influence radius and kernel function, it is theoretically possible that each particle can influence and/or be influenced by every other particle in the system. This causes the algorithm to be in the class of O(n2) algorithms, which is not ideal, especially for real-time rendering.
To account for this, the paper describes a variety of potential implementation specific solutions. I chose to implement the Spatial Hash Table. This versatile data structure allows one to subdivide infinite space into discrete buckets and query the membership of buckets in near-constant time. By tuning the bucket size to be a function of the influence radius, the algorithm reduces to a O(n) algorithm, a significant improvement. Due to efficiency of the hash table, my implementation can consistently stay above 40 FPS with 512 particles.
There are many other potential optimizations that could be implemented, such as taking advantage of the lack of data dependency between frames to exploit parallelism. In addition, hardware-accelerated parallelism with GPU’s is also viable.
Below is a demonstration of my implementation. As can be seen, it isn’t perfect. There are cases where a few particles explode. This is caused by some edge cases in the implementation that cause the gradient derivatives of the simulation to exponentially increase. In addition, in some cases, floating point round-off causes division by zero, wrecking the inter-particle forces.
As always, the code can found on Github here.
Made with OpenFrameworks