Fluid Dynamics

Game Mechanics
#1

Hi all,
Ive lately been working on a real time fluid dynamics solver, and its mostly been fun and easy to code. However, ive come up against a problem in the diffusion step of the equation.

Originally, i faked the diffusion of the velocity field by using Oddlab’s algorithm for Thermal Decomposition, which is basically this:

For every pixel, find the von-neumann neighbourhood
For every neighbour, find the difference between the neighbour and the current pixel
Find the biggest difference among the neighbours
Divide that difference by 2
Add the new divided difference to the lowest point of the neighbours (the one you obtained the difference from)
Subtract the divided difference from the current pixel

And that has worked fine so far. However, as you can see, the sampling of the neighbours (i.e. extend the setting of the current pixel out to include not just the von-neumann, but also the neighbours’ neighbours) or the difference, does not take into account the dt of that frame, and as such, the algorithm becomes extremely unstable and the simulation blows up when dt is high.

So, anybody has any ideas on how to extend that algorithm further to include dt ?

DP

#2

Hmmm. I for one have no particular knowledge about fluid dynamics. In general, however, when solving differential equations there is the easy way, i.e. Euler’s method, and then there is a number of more sophisticated methods that are somewhat more reliable what with the blowing up and so on. Are you familiar with Heun’s method and - more generally - Runge-Kutta methods? Unfortunately I do not have any idea how to implement these in terms of partial differential equations such as the Navier-Stokes equations which you are most likely using. In a related matter you may wish to specify which kind of physical problem you are solving in greater detail.

The funny thing is that Oddlab algorithm generates exactly one google result, which leads me to believe that there is a more common term for this, supposing that it is indeed a well-known algorithm.

The common way of solving such problems would - I believe - involve some kind of finite element method which might not be feasible in realtime. So I guess I know no real solution here. But if some of the terms above are not known to you, you may wish to investigate them further.

#3

The Euler’s method (and all the other methods you’ve said) are used to solve first order differential equations. The problem with solving Naiver-Stoke equations is that they are partial differential equations of the second order (!!!) which is a real killer. PDE’s alone are bad, but second order, that just bad luck :slight_smile:

The alogrithm I quoted is made by Oddlabs (the people how made Tribal Trouble) and is not the algorithm’s name. Anyway, a link to it is: http://www.oddlabs.com/download/terrain_generation.pdf

Coincidently, i met my old maths teacher today, and he is now doing research into numerical fluid dynamics and more specifically, how "swirls" arise in real life and not in numerical and accurate solutions of the Naiver-Stoke equations, and that led him down elliptical partial differential equations, which by the name alone sound horrible.

DP

#4

You know about Jos Stam’s work in this field right?

http://www.dgp.toronto.edu/people/stam/reality/index.html
http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/GDC03.pdf
http://www.dgp.toronto.edu/people/stam/reality/Talks/FluidsTalk/FluidsTalk_files/frame.htm

Thijs

#5

I didn’t know about it no, but now that i’ve read it, the ideas presented in it are very interesting. However, its patented, and I just realised my velocity movement step is very very similar to his. Boo Hisss!

Im looking at simulating fluids using the particle approach now rather than the conventional velocity grid now, it seems to make much more sense. If you are interested, Im working from a paper titled “Smoothed Particle Hydrodynamics”. Seems to be the business for real-time applications…

I’ll post back if I have anything working at decent speeds

DP

#6

Ah ok, wasn’t sure if you where expirimenting on your own or you where referring to problems implementing his work… :slight_smile:

I would be very surprised if you wouldn’t be allowed to use his work because he patented it. Im not sure about this, but I remember researchers can also patent work to prevent others from exploiting their idea commercially… it might be worth checking out if thats the case…

BTW, a very cool game that uses Stam’s fluidsolver can be found here: http://www.plasmapong.com/

Anything like this guy is doing? : http://www.ss.iij4u.or.jp/~amada/fluid/

Also related to fluids, I found this project very interesting:
http://rtfss.sourceforge.net/

Good luck and I’d be very interested to read about any progress you make here! :slight_smile:

Thijs

#7

Thanks for the links, ive managed to hack together a Fast Fourier Transform thingy and ported over the code for that at the end of his paper and it looks nice, that fluid is running around advocating itself and all sorts, well pleased.

So the next challenge I set myself was volumetric, animatable clouds and after having read two of the papers, i ditched all the techniques and decided to do it on my own, the DP way :stuck_out_tongue:

I’ll post in another thread how I did it (it needed fluid dynamics too!)

DP