May 25th, 2009
I went to the Sharcnet GPU and Cell Computing Symposium at my university last week. One of the keynote speakers, Dr. Paul Woodward, pretty much blew my weak and feeble mind. He used Roadrunner, a.k.a. the faster supercomputer in the world, to compute some impressive fluid dynamics. You know your research group is on the right track when you have a Wallpapers section on your web site.
Back on planet earth, us computational plebs don’t have such luxurious resources at our finger tips. To start with, you don’t have a lot of options when you feel like simulating fluids on a computer. Things get even more depressing when you want fluid flow computed in real time. In video games, or maybe just in old video games, accurate water simulation ends up being avoided all together with some elaborate ruse to keep computation costs down. Why do fluids have such a bad rep? To paraphrase Wikipedia: “We suck at solving systems of non-linear partial differential equations, here’s a million dollars if you figure it out, good luck lol”.
I find this whole water simulation extra-depressing because the universe computes the solution to these problems instantly and literally rubs it in our face whenever the wind blows (via turbulence). Just imagine with me what life would be like if we had an exact solution for fluid flow. Picture weather forecasts that actually forecast, reliable message-in-a-bottle delivery using ocean currents, and aerodynamic everything.
Wow, nice introduction. This post is actually about my fluid simulation project for Google Summer of Code. To achieve real-time fluid simulation in Step, I intend to follow the Smoothed Particle Hydrodynamics (SPH) algorithm outlined by Muller et al. in “Particle-Based Fluid Simulation for Interactive Applications“. This method works by breaking up a large fluid body into discrete chunks and using these chunks to create smoothed out fields. In fluids, the stuff we care about are pressure, density, and velocity fields. SPH is just a fancy way of figuring out the forces that act on your fluid by taking these fields into account.
Without going into all the mathematical detail presented by Muller et al., we can begin to define our fluid particles class in StepCore, the mathematical back-end of Step. Note that all of this is pretty fuzzy right now since I haven’t started coding anything. Many important properties of FluidParticle already exist the base class Particle in Step as depicted below. Nothing too special here, just get and set methods for the particle member variables. One thing to note is that FluidParticle has a specific radius that defines the core radius of each particle. However, at this point it is unlikely that the radius of each particle will vary. I’ll talk about Errors in a separate post also.
Now that the FluidParticle is defined we can look at the collective group, the Fluid. All “bodies and forces” in Step are derived from the root class Item. A Fluid is simply a group of FluidParticle items in a handy “Item Group”. The main purpose of this group is to extract macroscopic features of our fluid particles that exists within a rectangle drawn in the GUI.
This rectangular data inquiry box was designed for use with the Gas class where determining the number of particles, the kinetic energy, and the temperature are meaningful quantities for statistical mechanics. However, I’m not really sure how well the physics of statistical mechanics translates to the mathematics of a fluid. For instance, I may know the velocities of all my fluid chunks but is it correct to use these velocities to determine the so-called “temperature” of my fluid? I suppose so… but I have to do a bit more research.
Nonetheless, for now I’ll just use the rectPressure(), rectVelocity() and rectDensity(). I’d like to be able to use these methods to not just calculate the average pressure, velocity, and density by looping over the values stored in each fluid chunk but averaging over the entire field created by the fluid chunks. I’m not sure how computationally demanding this calculation will be, but if I discretized space within the fluid into some sort of grid this may be possible.
So now we have a Fluid that is composed of individual FluidParticles. Where does the physics come in? We need to look at the FluidForce class for that. The purpose of the FluidForce class is to do the work of applying the inter-fluid forces to each particle in our item group by means of the calcForce method that allows you to calculate the variances based on a boolean flag. In the process of calculating the forces on each fluid particle, I’ll have to use the helper method calcPressureDensity() as well.
You’ll notice that the only member variable for the fluidForce is a cutoff value and FluidErrors (which I will elaborate on later). This value represents a limiting distance for which the force contribution from a distant particle would be so small that it’s not worth calculating. In the current Gas implementation in Step, calcForce requires O(n^2) comparisons, as we have to loop through all pairs of particles to determine if they have a distance less than the cutoff value. As mentioned briefly in Muller et al., a potential speed-up over this approach might be to place our fluid particles on a grid and only calculate the force contribution from particles attached to neighboring grid cells to our particle of interest. I’ll address performance issues later in my project.
I’ve already overlooked a few critical issues that may require the modification of these classes. A fundamental characteristic of a fluid is viscosity, which is defined as resistance of a fluid to shear and stress forces. Obviously, my GSOC project will not be complete unless I can simulate some delicious sticky honey. At this stage, for simplicity, I’ll probably just hard code some viscosity values. The second critical issue will be collisions. My mentor and I both agree that collision handling may get tricky. If you’ve ever been stuck in a wall or a tree when playing a video game you’ll know what I mean.
I’ll address that problem eventually but next I’ll briefly discuss the Error classes associated with the fluid objects. The calculation of errors/variances is one of the cool features that makes Step unique!
After that, I’ll explore the Qt and GUI side of Step. I’ll connect the classes I’ve defined above to user interactions. Once I do that, things should get a lot clearer in terms of how the FluidForce, Fluid and FluidParticles work in conjunction with the World.