August 27th, 2009
GSOC has finally come to a close. It seems like yesterday when I was blogging on here, young and foolish about the complexity of my project. What you see above are my modest results. Pretty as it might look, this fluid is most definitely code-name O(n^2), and that’s not really a good thing! Let me explain the name in the three major aspects of my project.
It’s one thing to implement a smoothed particle hydrodynamics paper in STEP, that was basically done by the midterm, but how can you make it… well, physical? In an SPH system, there are several parameters that must be adjusted to achieve that. Namely, the temperature dependent gas constant, the rest density, the smoothing kernel length, the surface tension coefficient, the viscosity constant, and the universal bounciness of object-object interactions. With the exception of the surface tension and bounciness, I was able to determine a number of these constants for a working fluid using trial and error.
Most significant for computation was the adjustment of the smoothing kernel length. This is the radius around each fluid particle at which the effects of the particle are spread out. According to the SPH algorithm I implemented, at each time step we compute the pressures at each fluid particle based on the density of all fluid particles within the smoothing kernel radius. That being said, at each time-step I made O(n^2) distance to fluid particle comparisons, and in the limit of an infinitely large smoothing kernel there would be O(n^2) arithmetic operations. Among some other issues I will discuss, I found this to be a limiting factor for the number of fluid particles I could use.
Unfortunately, this prevented me from testing an important aspect of fluids, surface tension. By adding some additional fake surface tension forces outlined in Muller 2003, my fluid would be calmer and perhaps even support the weight of a boat at it’s surface. Additionally, the addition of bounciness would allow gravity to act realistically on the fluid and have density collect at the bottom of a jar.
So, how can one improve on this brute-force enumeration of all pairs of particles? My expert mentor Vladimir suggested a new data structure might be the best approach. Since both fluids and gases benefit from a large number of particles, it would be advantageous to implement a Axis-Aligned Bounding Box data structure. Not only would this help for collision detection between any Step objects but this would provide a way to only calculate pressure forces for neighboring fluid particles. This works because we store a sorted list of boxes about both our X an Y axes and keep track of box overlaps. Unfortunately, my mentor and I did not have enough time to implement this complex rehaul to StepCore.
Step is about education. For educational purposes, at the very least, it would be great to be able to know the average density and pressure within a region of the fluid. Despite my fluid being somewhat artificial and hacked together with strange internal values, I managed to achieve this. However, the computational complexity is, once again, not pretty.
The calculation of pressure at a particle point in the World was already used for the dynamics of the fluid. I merely had to generalize it for discrete area elements of Step’s “measurement rectangle”. By moving the rectangle and resizing it within the Fluid, each time-step I am sliced the area into a grid, calculated the pressure and density at the center of each area, and then added it all together.
The trouble with that is probably quite clear. If you have a very large measurement rectangle you may want a widely spaced grid and for a small measurement rectangle you may want a closely spaced grid. A grid dependent on the size of the rectangle and the smoothing kernel radius is also a difficult value to fine tune.
In the future, It would be ideal for the user to be able to select the precision of the pressure and density calculation at their own discretion, and have the variance values adjust accordingly. I was unable to implement variance calculations for these measurements, but that may also be an expensive calculation!
Finally, the Pièce de résistance. The jaw-dropping visuals that all fluids deserve. As you can see above, there’s lots of room for improvement. Visualization can be done in two ways. Muller 2003, the paper I was following for this SPH implementation, suggests a fancy isosurface calculation. That is, determine the normal to the fluid particle density field at every point. If this value is greater than some threshold, it’s safe to say it’s a surface particle and it could be used to draw a sexy looking surface.
However, with a deadline looming, my mentor suggested a simpler approach. I would simply calculate density at each point in a grid and then paint a particle there with opacity based on the density. As seen above, these opacity calculations weren’t quite calibrated, since we don’t see much variation in blue except at the edges of the fluid.
I had a problem though. Where should I “draw the line” for drawing the dots? I can’t very well calculate the density at each point in the observable screen area. It would take forever to get a smooth fluid. The solution is to calculate the minimum bounding box for the fluid and use a cut-off value in-case one fluid particle flies away off the screen. This ended up being quite challenging for some reason, so I decided to only render the fluid within the “measurement rectangle”.
I had an issue with converting between coordinate systems that still remains unsolved. I needed to draw my fluid about the origin of the WorldScene or else my fluid would render in the incorrect location. This is likely due to a simple mapping problem that I intend to figure out soon.
So, what’s next for Fluids, Step, and Me? The realism, measurement, and visualization issues outlined above will continue to be worked on by Vladimir and I. After some of the fundamental problems are addressed, I forsee a very liquidy Step in the near future. Me? I’m starting a MSc. in Physics at University of Waterloo this Fall, but I had a lot of fun on this project and hope to continue making Step a richly featured open-source physics simulator!