realtime fluid dynamics

Just to clarify, you're not interested in rendering the surface of the water, just underneath the water?

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.

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.

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.

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.

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.

as for visualizing the flowfield: id suggest spawning air bubbles at low pressure areas of the fluid, which should give a fairly realistic effect.

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.

@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...

@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 ...

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

@TheAdmiral: thanks, Plasma Pong looks awesome! i really like its render style and the performance. i am going to contact that guy ..


anyone had any experience with LBM (Lattice Boltzmann method)? AFAIR this might solve some of my "problems".

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.

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.

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.

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.

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]

http://dan-ball.jp/javagame/mc/ <-- best 2D water simulation( from the side view, top down is acctually a much easier thing to figure out) I have seen in action. Really cool way to do it, if you mess around with it you can kind of see how it works... kind of :O

@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]