Sign in to follow this  
ghostd0g

realtime fluid dynamics

Recommended Posts

ghostd0g    130
hi all. for my new project (some kind of virtual guidance system based on the concept of water flow) i need to implement a fluid solver with the following features: * stable * real-time and scalable for big covered fluid areas with reasonable resolution * insertable obstacles * controllable flow (via placeable drains/sinks) * more or less continous flow through the system, so that the dynamic system does not dampen too fast * 2d simulation might be enough, although extension to 3d would be nice i looked through a lot of papers (seems to be a real huge field of research), especially those of Jos Stam. his method/demo works quite fine, although the math is a bit heavy and i don't like the c-style code. somehow i failed at "porting" it to c++ because now the simulation doesn't dampen like the original. a GPU version (i.e. the version in the GPU Gems book) might be worth a shot too. anyhow, the things i am still wondering about are the scalability + performance (cpu- and memoryusage of Stam's version is proportional to the gridresolution), handling of obstacles (not implemented in Stam's version), the controlling of the fluid and the rendering of flow. controlling: seems to be implemented in Nick Foster's paper (in- and outfow gridcells), but i don't know if it really works out with Stam's stable solver. rendering: of course is the hardest part because it is not really defined yet. it should be more abstract/artistic. i don't want real-time caustics and realistic water surface rendering. it should be more of an blueish underwater view. so maybe some volumetric lighting + fog (like in submarine games) would help. i'm also thinking about some simple texture wobbling (like in quake). in many of the demos either ink/dye advection or texture advection is used to visualize the flow but maybe someone has another better idea ... ?! so, hopefully somebody can point me into a proper direction or provide some helpful resources. any help is appreciated. thx!

Share this post


Link to post
Share on other sites
ghostd0g    130
yes. i don't want to render realistic reflections on the water surface (like in the most shader tutorials out there). it would be cool though to have some sort of underwater caustics (light beams coming through the surface) ...

i think that it is important that you see the dynamic behavior of the fluid, but i'm not sure how to visualize that.

Share this post


Link to post
Share on other sites
erissian    727
I think an interesting effect would be seeing dust, sand, and other debris moving through the beams of light (be it sunlight or lamp). Fluid dynamics is a somewhat intensive problem to approach just for the visual effect of light scattering through the surface of the water. I would use a plasma style light map with a varying periodicity for that. As far as how the water moves beneath the surface, it may be helpful to break the water into cells of pressure and temperature. The temperature would affect the pressure of the cell, while imparting heat to adjacent cells. The pressure of a cell would exert force on adjacent cells and affect the rate at which the cell can take on heat. I've used this method before for wind, and it works quite nicely.

Share this post


Link to post
Share on other sites
taby    1265
The first thing that popped into mind when I saw your list of must-haves was "Stable Fluids" by Jos Stam. :)

Stam's paper Real-Time Fluid Dynamics for Games is a much better paper to read in order to really see how the math behind it works. Any elementary Linear Algebra book should also cover the topic of relaxation, and would be worth a look.

Fast Fluid Dynamics Simulation on the GPU by Mark Harris (GPU Gems), and Flow Simulation with Complex Boundaries by Wei Le, Zhe Fan, Xiaoming Wei and Arie Kaufman (GPU Gems 2) are also really good papers for understanding the math.

Altogether, I think that pretty much covers your list.

As for emitters and drains, simply increase or decrease a cell's fluid amount after the entire timestep. The rest will happen automatically.

For the boundaries, it's similar to the boundary cells of Stam's paper, except that one must consider that the surface normal may not (most likely will not) be perpendicular to the grid. To calculate the surface normal, you just check all neighbouring cells to see if they're boundary cells too. Then when it comes time to reflect the fluid, you don't perform the simple fudge of reversing the fluid's velocity vector, but compute the reflection based on two vectors like in the real world.

Share this post


Link to post
Share on other sites
ghostd0g    130
thx erissian, your approach sounds interesting. got any screenies and or resources of the plasma style light map thing?

just to clarify: the fluid dynamics simulation is not for the rendering - there are animals swimming inside the flow and they are affected by the flow (so i use the velocity field of the flow).
but i want to visualize the movement of the flow too, somehow. because otherwise spots without animals would look stale and boring.

Share this post


Link to post
Share on other sites
taby    1265
To visualize the flow direction, you could render a small cone in each cell, aligning its pointy end with the direction component of the fluid's velocity vector. You can also set the RGB colour of the cone to the same values as the XYZ component of the fluid velocity vector, giving you another level of visual clarification.

As for the speed component, you can always scale the cone accordingly.

Advanced Graphics Programming with OpenGL by McReynolds and Blythe details several other methods of flow visualization, from field lines to streamlines, to ... you name it, it's in there.

Share this post


Link to post
Share on other sites
Eelco    301
as for visualizing the flowfield: id suggest spawning air bubbles at low pressure areas of the fluid, which should give a fairly realistic effect.

Share this post


Link to post
Share on other sites
Bourbaki    122
I dont know if you have seen my videos yet but i have written a small Real time fluid solver myself.

http://video.google.de/videosearch?q=fluid+solver
http://www.gamedev.net/community/forums/topic.asp?topic_id=422299

I think that grid based approaches are too slow to be interesting.
Also Jos Stems approach is just for non compressable fluids so its quite uninteresting for water.

Extracting the surface is quite tricky though this is what i am working on atm.

My approach is quite stable though.
Its real time.
Obstacles arent much of a problem to add.
The approach is continous.

If i dont write an article about all this i might release the stuff.

Share this post


Link to post
Share on other sites
ghostd0g    130
@taby: thanks for your help.
actually i did start from stam's "stable fluids" paper and his "Real-Time Fluid Dynamics for Games" GDC2003 talk. and i'm still working on my own glsl-version of the mentioned gpu gems 1 example from harris (although i think his mathematically explainatons are far more complicated than stam's).
thanks for the hint to the gpu gems 2 chapter from wei li et al. i'll definitely look into that.

concerning your rendering suggestions i have to say that i don't want to render it like in scientific visualizations. i already have that (cones, arrows, lines, particles) for debugging and testing purposes. i want to visualize the movement inside the water (the flow), but it should still look like stylized water. maybe just lighting and distorting a nice blue seaground-texture is enough, maybe not...

Share this post


Link to post
Share on other sites
ghostd0g    130
@Bourbaki
yes, i already saw your thread. your solver looks quite impressive. congrats!

indeed, grid based approaches really are rather slow and wasteful on the memory-side. but i don't think i should use the particle-based approach either. that's more for interacting with the fluid. and i don't really care about the fluid being compressive or not compressive. i am only interested in the velocity field of a fluid, with its eddies and stuff. maybe i do not even need a whole fluid simulation ... but it seems to be the most obvious way and the only way i know.

but i'm looking forward to your article!


@Eelco:
i already thought about the airbubbles. maybe this will help with the visualization.
i'm looking for an "view into the ocean from beneath the water surface" style.
so it should be blue, somehow changing with the flow movement and a falloff to darkblue along the z-axis. i don't know how to couple the flow data to some rendering ...

Share this post


Link to post
Share on other sites
TheAdmiral    1122
You may want to take a look at Plasma Pong, which was written by one of the forum's members a few months back.
It's basically Pong inside a contained viscous fluid, but it plays and looks wonderful. As far as I know, the author modelled the Navier-Stokes equation on a uniform grid, solving it in real-time with finite-differencing.

The method sounds simple enough, and all of your conditions seem to drop straight out of the model.

Regards
Admiral

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
Quote:
Original post by ghostd0g
indeed, grid based approaches really are rather slow and wasteful on the memory-side. but i don't think i should use the particle-based approach either. that's more for interacting with the fluid. and i don't really care about the fluid being compressive or not compressive. i am only interested in the velocity field of a fluid, with its eddies and stuff. maybe i do not even need a whole fluid simulation ... but it seems to be the most obvious way and the only way i know.


I'm not sure I agree with this. When using multigrid or conjugate-gradient solvers (Which Stam did not do for his published works on stable fluids), grid-based approaches can be very damn fast. You have the advantage of being able to more easily package the cells in a CPU cache-friendly way, compared with particle methods, for an extra performance boost. (But things like multigrid do use lots of memory, like hierarchical spatial partitions of triangles used for visual occlusion culling.)

And as for particle-based fluid methods, there you have the problem of keeping track of "neighborhoods" of particles that have influence on each other. The neighborhoods are needed to compute kernel functions for, say, the SPH method of particle-based fluids simulation. The neighborhoods are typically maintained in a spatial partition, which must be dynamically updated as the particles move around. And the update of the spatial partition will slow down the particle methods.

Now, Stam's method is a hybrid. It has a gridded part and a particle part. His grid becomes the spatial partition for tying the particles back to the continuous fluid. His grid is a uniform grid. This works fine, and fast enough for a fairly small number of particles. But for a very large area of fluid, you'd potentially need a massive number of particles. And the uniform grid partition would not enable fast enough searches. You need a hierarchical spatial partition, such as an octtree or K-d tree. Hierarchical spatial partitions increase the memory needs, and dynamically updating those over time can be very challenging indeed, and quite slow.

Particle systems can be easier to implement, and work well for large areas, until you add tons of particles and need to make it fast. Particle systems do provide a more natural way to interact with other physics objects in a scene, such as rigid bodies.

For velocity fields, I agree that you probably don't want to use particles. Grids are going to give a better result. First, to generate a meaningful field, you'd end up evaluating the SPH kernel functions on a grid anyway. Second, with particles scattered in a somewhat random fashion, when you do evaluate the kernel function, you are going to have hot spots where there are particles, cold spots where there are no particles, and this will appear quite unnatural in the velocity field.

Share this post


Link to post
Share on other sites
Bourbaki    122
I dont know if my approach is very different from the usual particle based approach but its kind of a FEM which makes the overall thingy continious.
And also this allows me to model density and heat based adaptation of the fluid. Another thing i found very hard to achive with gridbased approaches in interactive speed was that the fluids are compressible. For the velocity fields i think its right that if you need information of the field at each point in the space you are better off with the grid approach but this is getting slower the bigger the grid is if you are off fine with a sparse description of the surface you could just use particles whereever you need them.

What i think is most appealing of my approach is that i can really derive the surface functions and thus not do these finite differences which have some issues with the propper distribution if i am not mistaken.

Share this post


Link to post
Share on other sites
Spoonbender    1258
Plasma Pong is based on Stam's paper (The GDC2003 one).

Keep in mind, though, that the code in his paper is *horribly* unoptimized. I'm not sure if that's because he just sucks at writing efficient code, or because he wanted to keep it simple and readable. (Or because he intentionally wanted to keep the "efficient" solution to himself), but you can get a 4x speedup without too much trouble.

At uni, I made a 6 month project of optimizing it, and got around 8x the original performance.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
All methods get slower as you add detail. Multigrid methods, when applicable, scale about linearly with problem size for gridded solutions, which is probably similar to the scalability of particle methods---assuming the spatial partition update for the particle method scales linearly (and that might or might not be true). So, my point is that gridded methods can scale very, very well, depending on implementation. Multigrid (and the other fancier, fast gridded solvers) can be tricky to implement correctly, though.

Share this post


Link to post
Share on other sites
kloffy    1318
Quote:
Original post by erissian
Just to clarify, you're not interested in rendering the surface of the water, just underneath the water?

I would love to learn about the different approaches considering these two goals. As stated before in this thread, Navier-Stokes is the way to go if you want to simulate the flow inside the fluid. What is the recommended approach if you wanted to simulate the flow of a fluid through an environment (with rigid bodies etc.)? Particles? And finally there are visual effects fluids, which are accomplished through shaders. However, my main interest are first two cases.

[Edited by - kloffy on November 11, 2006 11:27:49 AM]

Share this post


Link to post
Share on other sites
ghostd0g    130
@grhodes_at_work:
Thanks for your input. I've read about using a conjugate-gradient solver. It actually was one of the optimization suggestions in Stam's paper.

I don't understand the part of uniform grid partitions would not enable fast enough searches. What do you mean by fast searches? It's just a bunch of contiguous values in memory which need to be updated every simulation step. And to get the value at a specific point on the grid the cost is always the same.

I think particle-based approaches fit better for simulating free roaming liquids and their physical interaction with objects (as you said).
But in my project it's just two small streams and a big pool (over several screens) with a mill wheel in it. One stream for the inflow and one for the outflow. And there are Animals in the "fluid" that might be affected by the flow field.

What do you mean by Multigrid and fast gridded solvers?


I'm also thinking about flow tiles for a contiguous flow simulation. So every client could simulate and render the flow and it would not be the task of the server. But besides this paper there is not much information out there.


@djperegrine:
funny demo, but i don't think i get something really valuable for me out of it.


[Edited by - ghostd0g on November 12, 2006 11:40:11 AM]

Share this post


Link to post
Share on other sites
TerranFury    142
There's another way to solve PDEs which I haven't tried myself but which sounds interesting.

That is to represent your problem in the frequency domain and express differentiation simply as a multiplication. Then, your time derivatives are still finite-differences, but your spatial derivatives are more accurate.

I've heard that techniques like this have just begun to find their way into solid mechanics as a more accurate alternative to finite-element models. Would it be useful to apply them to fluids?

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
Quote:
Original post by ghostd0g
I don't understand the part of uniform grid partitions would not enable fast enough searches. What do you mean by fast searches? It's just a bunch of contiguous values in memory which need to be updated every simulation step. And to get the value at a specific point on the grid the cost is always the same.


That is not true for a particle-based fluid solver. The fluid particles move around over time, and so the neighbors of a given particle are different from time-step-to-time-step. You'd need a way to rapidly search the field to locate nearby neighbors, and for a very large # of particles this would require more than just a uniform grid where each grid cell remembers which particles are within its volume.

Quote:
Original post by ghostd0gI think particle-based approaches fit better for simulating free roaming liquids and their physical interaction with objects (as you said). But in my project it's just two small streams and a big pool (over several screens) with a mill wheel in it. One stream for the inflow and one for the outflow. And there are Animals in the "fluid" that might be affected by the flow field.


Yes, a simple gridded solution would probably work best. And, it would be effectively 2D. Did you see Jeff Lander's presentation, "Taming a Wild River" over at www.darwin3d.com (GDC Companion page I think)? That might be a viable starting point.

Quote:
Original post by ghostd0gWhat do you mean by Multigrid and fast gridded solvers?


Multigrid is a way of accelerating the spatial solution part of a gridded fluids simulation. Its a bit advanced, but when matched with an appropriate problem achieves very good speedup.

The flow tiles approach looks quite interesting, with a lot of potential applications. Its obviously limited, but guaranteed predictable and stable results.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this