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