8 replies to this topic

[jefferytitan]

Hi all,

I've been asked whether I could do a real-time decent quality fire/smoke simulation for a contract opportunity. I've done a little research but not gotten much closer to a solution. Essentially as far as I understand it's typically a combination of a physical simulation (Navier Stokes or similar) and a shader that makes it look pretty and/or emulates finer detail.

I've seen a lot of papers that go into the maths of it (which I don't understand, having never done engineering), but I haven't seen any pseudocode on a low enough level that I could easily implement it. I managed to source a couple of source code examples that are in languages that I don't know well, and don't compile anyway because they require exotic libraries that I can't locate.

I'm hoping to code up a version for Unity. Does anybody have any idea where I could get:

• .net source code OR
• Java source code OR
• low level pseudocode?

If I have to work off the vague descriptions and mathematics I fear it would add about a week, which is far from ideal for a proof-of-concept for a project that I haven't even been accepted for yet. Also without the deep grounding in the topic I might miss easy shortcuts that would improve speed at little quality cost.

Thanks,

JT

[jouley]

I can't point you to handy ready-to-compile code, but there was a discussion about this back in February: http://www.gamedev.n...uid-simulation/

The links I point to a bit down the conversation have some code snippets that are easy to understand, and also a walkthrough of the theory of fluid simulation that is the clearest I've seen.

Since then, I've found this, which may be of use: http://www.cs.unc.ed...ject/final.html

Edit: Also, if you'll post the papers you've found which are too math-heavy, we'll know what to avoid suggesting ;)

Edited by jouley, 02 August 2012 - 05:00 PM.

[jefferytitan]

Thanks jouley. I am reading through the pages that you linked to.

I forgot to mention, if possible I'd prefer to stick to an grid-based approach because the situation I'm looking at is a house fire, so I want smoke to build up to saturation point. I assume that a particle-based approach would suffer from either lack of saturation due to particle lifetimes, or just massive slowdowns from increasing particle numbers. Additionally I want it to stay within boundaries, e.g. walls, ceilings, doors. I gather that some approaches handle that by simply zeroing out the impact of obstacle voxels.

Unfortunately the links that I looked at earlier are on another PC, so I'll get back to you on that one. My level of maths literacy at the moment is that I did vectors, calculus, etc over 10 years ago so I'm pretty rusty. I know how to do dot and cross product, I know how to multiply by a matrix (although things like inversion and diagonalisation are out of the question), my differentiation is okay, my integration is awful. ;)

Edited by jefferytitan, 02 August 2012 - 06:06 PM.

[Geometrian]

Hi,

There's some key points that I found out the hard way. Do NOT underestimate fluid simulation--if you don't know what you're doing (as I didn't) it takes a while to get right. You'll also need to be good with GPU programming if you want to do it realtime.

The GPU gems have some decent source code that I reverse engineered:
-http://http.developer.nvidia.com/GPUGems/gpugems_ch38.html
-http://http.developer.nvidia.com/GPUGems3/gpugems3_ch30.html

Summary of algorithm:
-Have several grids: density, velocity, pressure, and divergence
-You add forces to the velocity grid (f=ma). Divergence is the difference between velocity going in and velocity going out of any grid cell.
-Do Jacobi iteration. This is an iterative method that essentially calculates the new velocities that make all the divergences 0 simultaneously. Look at the links above for how to do it.
-Advect--basically move the density field by the velocity. The velocity field self-advects (i.e., advects itself). Advect backwards instead of forwards (really), as described in the articles.

So, for example, suppose you're in 2D, and you apply an upward force in the middle of the fluid. You add this force to the velocity grid. Then, you calculate the divergence. It will be nonzero above and below where you added the force. The Jacobi iteration changes the velocity field. The velocities now arc up from the point you added force, then over and back the other way down the sides. They then loop back around, forming two continuous loops. If you calculate the divergence now, it should be zero everywhere. Then, you advect the density, so smoke moves along the velocities. Then, you advect the velocities, so the velocities travel with themselves.

-G

[jefferytitan]

Thanks Geometrian. I have a few follow up questions:

• When you talk about adding forces to the grid, are you talking about external sources of force (e.g. moving objects, sources of smoke etc), or does that also include forces due to pressure differentials?
• When applying a force to the velocity grid, you do just get the acceleration from f=ma and multiply by delta time?
• Is the Jacobi iteration only required if forces have been applied?
• I heard reference to applying something backwards. Something about applying it forward makes the system gain energy and blow up. Is that what you mean about advecting backwards?

[Geometrian]

When you talk about adding forces to the grid, are you talking about external sources of force (e.g. moving objects, sources of smoke etc), or does that also include forces due to pressure differentials?

This is talking about external forces. Jacobi iteration adds the internal forces. If you want to do a fire simulation, you add parameters to your density (e.g., fuel, air, smoke, temperature, etc.), and advect those. You add forces from the fire (heat, etc.) as external forces as well.

When applying a force to the velocity grid, you do just get the acceleration from f=ma and multiply by delta time?

Yes.

Is the Jacobi iteration only required if forces have been applied?

No, it is always required. Imagine a smoke ring--it travels even after the initial force is provided. If it hits a wall, then it is destroyed. Purely self-advecting the velocity won't handle that.

I heard reference to applying something backwards. Something about applying it forward makes the system gain energy and blow up. Is that what you mean about advecting backwards?

Yes. Advect all quantities by looking back in time. It makes the simulation more stable. It's discussed in the articles.

[jefferytitan]

Okay, that more or less makes sense to me. The GPU Gems article made sense to me until they brought in the mystery vector calculus operator which means 3 different things. The code snippets seem more practical, although I haven't reviewed the snippets to see what's missing (if anything).

Given that the approach is intended to be calculated massively in parallel, would it be practical to perform half of the work on CPU and half on GPU, for example calculating alternating cells? The reason that I ask is I would like it to somewhat work even if their graphics card has limitations that preclude it being used for the simulation, e.g. harsh instruction limits. Also do you have any idea how one would get simulation results from the GPU back to the CPU, as fire/smoke should affect gameplay as well as graphics.

[jouley]

Okay, that more or less makes sense to me. The GPU Gems article made sense to me until they brought in the mystery vector calculus operator which means 3 different things. The code snippets seem more practical, although I haven't reviewed the snippets to see what's missing (if anything).

I assume you're talking about the del operator? It only has one meaning, though it has (more than!) three important applications, depending on the operation used. There's a quick vector calc refresher on a site associated with that last link I sent, slides linked to at the top: http://www.cs.unc.edu/~jpool/COMP768/presentation/presentation.html . These slides may also give you a different perspective on things; I'd go through them all, though the calc stuff is near the beginning.

Given that the approach is intended to be calculated massively in parallel, would it be practical to perform half of the work on CPU and half on GPU, for example calculating alternating cells? The reason that I ask is I would like it to somewhat work even if their graphics card has limitations that preclude it being used for the simulation, e.g. harsh instruction limits. Also do you have any idea how one would get simulation results from the GPU back to the CPU, as fire/smoke should affect gameplay as well as graphics.

If the GPU has limitations that keep it from being used, then it won't do much good on just half the simulation! That is, you'll need an independent CPU solution in that case. However, any recent graphics card should be able to handle it; the capabilities you need aren't all that intense. That first GPU Gems article is 8 years old, after all! The performance of a CPU solution won't be nearly the as good, but once you have the GPU solution up and running, adding a fallback path shouldn't be that hard. Are you planning on a 2D or 3D simulation?

To get the results back to the CPU, you just need to read the contents of the framebuffer holding the results you want. In OpenGL, glReadPixels is a fine place to start. I don't know the DirectX equivalent, sorry! Things may be very different in that land.

[jouley]

jefferytitan, on 02 August 2012 - 09:22 PM, said:
I heard reference to applying something backwards. Something about applying it forward makes the system gain energy and blow up. Is that what you mean about advecting backwards?
Yes. Advect all quantities by looking back in time. It makes the simulation more stable. It's discussed in the articles.

There are a couple things that you could have heard. When integrating to solve an ODE, "backwards Euler's" method is common as being the first step towards a more stable system than just using the regular Euler's method -- simple harmonic systems can blow up when using forwards Euler, but backwards is stable. This is loosely related to backwards advection, but not quite the same. Let me add a bit to what Geometrian said:

You're simulating on a grid of values. These values are moving around as time goes on. Imagine a "smoke particle" at position (x,y). At the next time step, it might be moved to position (x+1,y+1). However, it might also wind up at position (x+.9, y+.8). If that's the case, you'll have to spread the particle out to cover neighboring cells since it isn't right on the center of one. Bad news, your particle has just expanded!

Backwards advection works like this. Instead of watching where a quantity at position (x, y) goes, you look to see what winds up every position. So, you look backwards in time from position (x+1,y+1) and see that it mostly comes from, say, (x,y). However, you'll probably wind up interpolating the values from several cells, depending on where the backwards advection points (like forwards advection, it's not likely to point right at the center of a grid cell). Then, you have the value at exactly (x+1,y+1), rather than values spread out all over the place.

Like Geometrian said, this is all explained in the articles, but hopefully I've shown you that it's nothing to be scared of - keep diving in!