Fluid Dynamics Modeling with Particles

By: Tom Duerig

I wanted to use the numeric analysis methods with the scientific visualization methods I learned in class to not only create a fluid analyzer, but to make it able to simulate both air and water for interesting effects.

The Gist

Every particle has perfect collision detection and resolution with every other particle (aside from wing to wing or ocean floor to ocean floor). Particles are then sent in to do my bidding to model various fun things. Viscosity is simulated by creating a hooke style bond between every particle when a collision occurs. Right now every particle is maxed out at 10 bonds. At a given distance the particle bond breaks and the two are free to remarry.

More details than you wanted

Collision Detection:

During this project I tried 4 main styles of collision detection. There was an obviously right answer that I started with but was far too slow for my impatience and I tried everything down to the obviously fastest answer which was way way too ugly to stand. So, to list in order from ugliest to prettiest:
1) particle asks all particles in its collision domain (more to come) how close they are. If they're closer than they should be they go to appropriate distances and trade energy. This would be fine if my ocean floor didn't leak like a seive or if my wing wasn't made of swiss cheeze.
2) particle does a parametric look ahead at all particles in its collision domain to determine who it will collide with. Then it moves itself to that collision and does its energy exchange. This is problematic as the particles gain time by doing their little time warps. Also, they have a nasty tendancy to decide they're always colliding with something if they're in between two objects and they can litterally send themselves straight to my personal little particle graveyard.
3) Every time movement is called every particle reports its nearest collision if its within the time elapsed. Then those collisions reported are sorted and gone through in order. Time is advanced to the first collision in the list every particle is moved then the pair that collided get an opportunity to look ahead and add to the list again. This holds an advantage over the perfect algorithm as its order n + nlogn + c as opposed to just nc which might very well be much larger. Unfortunatly residual collisions remain unless you are willing to check each collision for validity after pulling it off the list. But to do that you have to have a seperate list of particles that have recently collided and a bunch of other nasty slow cludgy things. Those residual collisions created really amusing ameoba like emergent behavior that just wasn't what I was going for.
4) The style I eventually went with and slept thinking about every night for the last month. Everyone looks ahead and reports their next collision. Then time and particles advance to that first collision. Energy gets exchanged and everyone looks ahead again. This produces no real artifacts (aside from unrelated errors produced by me like starting particles inside of eachother and stupid things like that). Note: I started with style 4 being implemented recursively and went to an interative method with no benifit, you know you're optimizing the wrong thing when you change a function thats getting called 20000 times a tick to only get called once and it makes no noticable difference to the performace. I did however turn 12 arithmetic operations into 3 (most of the time) in a spot that was being called just as often and that helped hugely.

Collision Domains:

The universe is partitioned into tiny buckets. Each bucket larger than twice the size of a particle but no larger. Then when a particle wants to establish its collision domain it carves a little parametrically produced path through the domains looking for friends.

The collision lookahead:

Simple vector math can determine at what time particles will be at a given distance (since we're dealing with spheres that's all we'll need). Unfortunatly, this whole look ahead thing is happening a huge amount of times and a lot of the times its doing it to no avail (ie negative or irrational (NAN) solutions). To solve this I simply check ahead to see if its trying to do a sqrt of a negative and say the collision isn't going to happen. I also have to determine if their are two solutions which is better, but again thats really simple.

The collision physics:

Collisions simply change the universe into a 2 dimensional one by negating friction and realizing the velocities along the collision won't change then the energy and the momentum are conserved (except in the case of immobile particles cuz those don't really exist ;) )

Making springs faster:

Springs are expensive little things computationally to do right. They have this whole desire to know their length which requires sqrt()'s. And I don't like sqrt()'s so... I made the springs have quadratic response instead of linear, cuz they're frigging modeling viscosity anyway so who cares.

Fluid resistance in a changing political landscape:

For some of my little models I wanted the entire universe to have real fluid resistance as if it was in standing air (the wave model) and in some of the models I wanted it to actually have effective wind. So, all fluid resistance is relative to my defined fluid motion which makes wing simulations more realistic with fewer particles. (note that both wing movie simulations are done in standing air as it better demonstrated turbulent areas and whatnots)

Comet tails make the rendering usable:

I started all of my rendering with nice little quadrics (low slice count) but realized quickly that at particle counts over 100 that was quickly becoming my bottleneck. Thank you GlowCode the single best profiler I've used. So, I went to points. But unfortunatly points simply sucked for screen shots. So I did a tiny little tail on each particle to indicate its velocity. Unfortunatly this produces some artifacts for the first instant after a collision because the tail sometimes backtracks through other objects. I briefly tried sending out every particle as a pair of bonded particles with the front being the head of the comet and the back being the tail but that not only was ugly as sin but more importantly was slow and reduced the users ability to see what was going on. (especially in screen shots)

The stages of development visually:

1) I started with a simple stream of particles falling over a single immobile particle to get a feel for things like viscosity

2) Then I moved on to slightly more advanced little simulations as time progressed

3) But none of thie impresses family or friends so we needed to start actually rendering some recognizable things

And, if you don't get the subtitles imagine you're going through the air and you have a pocket with significantly less particles, that is a vacuum and that will try to be filled. So your little VW will want its tail to lift which will exagerate the nasty tendancy those things have to swing their tails out normally.

Animated GIF's:

Wave crashing
Wing showing Bernoulli
Higher Velocity 24000 particle wing
VERY large particle count wave