Archived

This topic is now archived and is closed to further replies.

Modelling better explosions

This topic is 5158 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have just started up a project where I will examine how I can use Cg in modelling realtime explosions. The goal is to make a type of explosion based on particles that can handle collisions with the enviroment. (walls etc.) I need to examine ways to model flow in the exlosion. Therefore I am looking for a good practical introduction to solving the incompressible navier-stokes for a 3D grid. Any books, papers or perhaps examples would be much appreciated. TAX

Share this post


Link to post
Share on other sites
Someone posted a fleshy/putty type simulator as a flipcode IOTD (looks like a deformed hand in one pic) very recently. He has a physics page (his link) which has just what you''re looking for I guess.

-Meto

Share this post


Link to post
Share on other sites
Go to Citeseer and make a search for "Modelling of Smoke Flow Taking Obstacles into Account" by Satoru Yoshida. On Citeseer, check the linked papers, you should read "Modelling the Motion of a Hot, Turbulent Gas" and "Physically Based Modeling and Animation of Fire". Similar methods have been used by Ken Musgrave and they really look nice (but not in realtime)

http://citeseer.nj.nec.com/cs
http://www.kenmusgrave.com/animations.html

Share this post


Link to post
Share on other sites
I''m just saying this off the top of my head, but:

Could you use a spring model with very weak springs between each particle?

For added realism you could make the spring force unidirectional. ie: No pull force, only push. This would allow hot gas to push other hot gas, but not pull it.

Will

Share this post


Link to post
Share on other sites
Look for Jos Stam's work on real-time stable fluids. He has a nice, simple system. Even has a version that runs on handheld computers (with no floating point math and no 3D graphics card). The OpenGL "Superflow" demo that nVidia provides with their Cg Browser is based on Stam's code. And the code is provided.

This simulator isn't set up as is to do explosion type fluids, but can do smoke in a room reasonably well. And with some hacks you might be able to do fire with it.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

[edited by - grhodes_at_work on October 9, 2003 1:44:56 PM]

Share this post


Link to post
Share on other sites
Thank you all for your interest.

It was just inspiration and reading material directions I needed.

I will start out by collecting the papers right now!!!

THANX!!!

Share this post


Link to post
Share on other sites
There''s a good paper on the nVidia developers site ( from GDCE I think ) about proceduarly generating volumetric explosions. It seemed pretty good...

You have to remember that you''re unique, just like everybody else.

Share this post


Link to post
Share on other sites
I have studied Jos Stam''s sourcecode for the paper "Real-time fluid dynamics for games"

My ambition is to find a way to use the velocity field that the algorithm in the paper describes. It is too heavy to implement the whole algorithm in realtime, I think.

Instead I think, that if I only iterate the algorithem N times, and use the velocity field to move random particles in the enviroment.

This wont give exactly the fluid effect, but it will enable me to move "burning" particles round in the enviroment while preventing them to fly through solid objects.

Moving the particles will then only be a matter vector addition, and therefore I perhaps could implement it in a Cg program.

What do you think?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
All the visible effects of an explosion stem from its shock wave, i.e., a supersonic wave front of extremely high pressure, density, and temperature. Clearly this is *compressible* flow. You''ll have a hard time modeling this using CFD methods for incompressible flow.

If you''re comfortable with fluid dynamics and numerical methods, take a look at the Siggraph 2000 paper on animating explosions for inspiration (though be warned it''s a long, long journey from the paper to a working implementation). If not, a simple hack is to model a shock wave procedurally (spherical wave front) that triggers acceleration of particles, rigid bodies, etc. (which then undergo dynamic simulation with collisions) as well as canned destruction effects (animations, decals, and so forth).

Share this post


Link to post
Share on other sites
I have been studying Jos Stam's paper "Real-time fluid dynamics for games" and little by little I begin to understand his code.

http://www.dgp.utoronto.ca/people/stam/reality/Research/pub.html
Paper: "Real-Time Fluid Dynamics for Games"

I have no prior experience in CFD

My ambition is to create myself a 3D implementation, of Jos code, to play with. In the paper that it says : "Extending the solver to three dimensions should be straightforward to anyone who understands our code." If anyone has done that I would like to discuss the way it is done.

I know it is ambitious, to get voxel based CFD working in realtime games, but I want to examine if it is possible to simplify parts of it and make use of it in realtiem games.

A huge benefit of the method is that I after only a few iterations of the method get a vector field i can use to move particles without colliding with the walls!? Its not physically correct, but I think it can be tweaked into something usefull.

As mentioned in a previous comment: Modelling explosions involve compressible CFD. But I feel anyway, that it might be worth to examine incompressible CFD for use with explosions. Anyways i think it is a good introduction to CFD.

To make it run in realtime there are several problems that I have to face. Feel free to suggest other problems/soultions

1) Voxel representations are huge.

As far as i can see in Jos code each voxel only "communicates" with its neighbours. Therefore I think it would be usefull to compress the voxels and unpack subparts of it when working on it. Does it sound stupid? -And do anyone know any obvious methods for that.

I guess that my memory limit will be ~1MB. By avoiding floating point variables (Jos mentions in his paper that it is possible.) I can represent each voxel in ~16 bytes. That will allow a 3D voxel with a sidelenghth ~40.

I have thourght about working with a sort of tree dividing the voxelspace 8 times at each level. And only subdividing into small voxels at the outer edges of an explosion. Would it be possible? Has anyone done that?

2) To make It work in a game, I also need a method to voxelize polygons fast. Perhaps a more simple model of the enviroment will be nescesary?

Any comments ideas are very welcome!

Jos code is implemented in pure C, which makes it a bit tricky to understand. It has taken me alot of time untill now to just unwrapping the code. Now I am stuck at the point in the code where it says that it solves a Poisson to maintain incompressibility?

In the sourcecode provided by Jos Stam I am having trouble converting the function project() from 2D to 3D. How is that done?

Has anyone experience with this?

I know this was alot of brainstorming, and YOU must be very patient to be reading this. But I am a newbie in this area and therefore i appreciate comments and Ideas very much.

Thanx!


[edited by - TAX on October 16, 2003 6:19:14 AM]

[edited by - TAX on October 16, 2003 6:20:02 AM]

[edited by - TAX on October 16, 2003 6:22:27 AM]

[edited by - TAX on October 16, 2003 7:25:52 AM]

[edited by - TAX on October 16, 2003 9:16:49 AM]

[edited by - TAX on October 16, 2003 9:23:39 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by TAX
As mentioned in a previous comment: Modelling explosions involve compressible CFD. But I feel anyway, that it might be worth to examine incompressible CFD for use with explosions. Anyways i think it is a good introduction to CFD.


Note that Jos' implementation is compressible; however, his method does not satisfy the Rankine-Hugoniot jump condition, which basically means you'll never see the shock front of the explosion. So-called "upwind" methods are required to capture shocks.

quote:
Original post by TAX
1) Voxel representations are huge.

As far as i can see in Jos code each voxel only "communicates" with its neighbours. Therefore I think it would be usefull to compress the voxels and unpack subparts of it when working on it. Does it sound stupid? -And do anyone know any obvious methods for that.



This will possibly save you on memory, but it will absolutely kill you on time. Voxel already will be expensive since you have to update every cell in the voxel each time you update the physics (one or more times each frame?). The only way you're going to get voxel CFD to work in real-time on reasonable hardware is if you make the voxel grid extremely coarse. I'm talking perhaps on the order of 10x10x10 cells. And even that will be limiting your frame rate just due to calcs. Now, using the hybrid method that Jos presents, where your flow properties are carried by particles that are not constrained to the voxel boundaries, you can still get decent looking smoke/clouds (maybe or maybe not fire/explosions) using a coarse grid.

Also, I believe that there are two steps to Jos's method, one being a marching solution. This is the part that allows you to solve each cell update using just its neighbors. But the other part requires solving a system of equations, with as many equations as cells (10 x 10 x 10 = 1000 equations) for every update. I think Jos uses successive relaxation with Gauss-Siedel, but at one time he was going to try Conjugate Gradient. You could use Conjugate-Gradient or multigrid to solve those equations quite quickly, but coding these methods is tricky. And not conducive to only have part of the grid unpacked at once.

quote:
Original post by TAX
I guess that my memory limit will be ~1MB. By avoiding floating point variables (Jos mentions in his paper that it is possible.) I can represent each voxel in ~16 bytes. That will allow a 3D voxel with a sidelenghth ~40.



Yes, floats should work well enough for Jos' method. They are not sufficient for more advanced CFD techniques.

But 40 x 40 x 40 = 64 thousand equations for the Poisson solve (see below) and that is prohibitive. No way in hell this will run even at 1 fps on current desktop hardware.

quote:
Original post by TAX
I have thourght about working with a sort of tree dividing the voxelspace 8 times at each level. And only subdividing into small voxels at the outer edges of an explosion. Would it be possible? Has anyone done that?


That's a really clever idea! You could have sort of an octree CFD grid. Now, getting the physics of the CFD to work properly a the boundaries of the octree grid will be tricky, and frustrating to implement. But possible. (In the CFD world, there are the concept of multizonal and Chimera grids, which involves using multiple grids of different density to get more accurate results where you need them.)

http://www50.dt.navy.mil/reports/chimera/generation.html

quote:
Original post by TAX
2) To make It work in a game, I also need a method to voxelize polygons fast. Perhaps a more simple model of the enviroment will be nescesary?


Yes, I think this would be helpful. Doesn't have to be just boxes, though. Cylinders, cones, things like that can be fast to voxelize.

quote:
Original post by TAX
Jos code is implemented in pure C, which makes it a bit tricky to understand. It has taken me alot of time untill now to just unwrapping the code. Now I am stuck at the point in the code where it says that it solves a Poisson to maintain incompressibility?


I'll have to look at that statement. One of his basic flow properties is density, which if it changes means the flow is compressible. And density does change because that is how he drives his flow. So, I wonder what he meant by that. But....

...actually, the Poisson equation is a representation of the so-called "Continuity Equation" which is the equation of conservation of mass. So, that basically makes sure that total mass is constant across the flow field. (Even with density changing, unless you're doing nuclear reactions that convert mass to energy or letting mass leak out of a hole, the total mass inside the container must remain constant and that's what this equation deals with.)

quote:
Original post by TAX
In the sourcecode provided by Jos Stam I am having trouble converting the function project() from 2D to 3D. How is that done?

Has anyone experience with this?


I finished all the coursework for a Ph.D in computational aerodynamics, and have experience with this. But that's a big question and I just don't have time to give you a satisfying answer here.

I will say that at some point Jos iterates through the horizontal and vertical cells of his grid, probably in a nested loop. (I haven't looked at his code so I can't say for sure.) This is one place where you'd have to add a third loop for the 3rd direction. The trickiest bit will be to update the Poisson solve. For 2D, the matrix of coefficients for the Poisson solve is a tridiagonal matrix, e.g., only the diagonal and two immediate off-diagonal terms have non-zero members. This means some handy optimizations can be done to the solver. For 3D, the Poisson coefficient matrix will be pentadiagonal, e.g., you'll have the three middle diagonals plus an additional diagonal on top and bottom. And the optimizations aren't really there. But, if Jos is using Conjugage Gradient or Gauss-Siedel with relaxation then he isn't using the tridiagonal optimized method anyway so at least on the solver side you are good. And you'd just have to figure out how to populate the additional 2 diagonals for the coefficient matrix.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

[edited by - grhodes_at_work on October 16, 2003 1:06:24 PM]

[edited by - grhodes_at_work on October 16, 2003 1:06:36 PM]

[edited by - grhodes_at_work on October 16, 2003 1:08:17 PM]

Share this post


Link to post
Share on other sites
>I have thourght about working with a sort of tree dividing the >voxelspace 8 times at each level. And only subdividing into >small voxels at the outer edges of an explosion. Would it be >possible? Has anyone done that?

Yup. Ronald Fedkiw and his co-workers have been studying the use of adaptive tree depth with semi-Lagrangian (ie. "stable fluids" method of Stam) advection. The results are good, because the implementation is much, much easier with semi-Lagrangian advection than with normal discretization methods.

>As far as i can see in Jos code each voxel only
>"communicates" with its neighbours. Therefore I think it
>would be usefull to compress the voxels and unpack subparts
>of it when working on it. Does it sound stupid? -And do
>anyone know any obvious methods for that.

The method you''re proposing sounds a bit like the multigrid method, where the equation is solved on multiple scales and then combined into a final solution. The idea is intuitive, which is nice, but the implementation is generally accepted to be hell on earth, I think. Conjugate gradient should give very good results more easily (also, the theoretically linear time of multigrid is good only with very huge datasets, or so I''ve heard).

>But 40 x 40 x 40 = 64 thousand equations for the Poisson
>solve (see below) and that is prohibitive. No way in hell
>this will run even at 1 fps on current desktop hardware.

I''m having 61 thousand equations running at 2.7fps on my XP1700+ on Win98 All other simulation (advection and things) included (Poisson takes 70% of the time). I''ll do a Win2k test later...

>I''ll have to look at that statement. One of his basic
>flow properties is density, which if it changes means the
>flow is compressible. And density does change because that
>is how he drives his flow. So, I wonder what he meant by
>that. But....

Hmm. As long as I''ve seen, Stam does use incompressible, constant-density fluid.

The smoke flows in his method are modelled by letting the constant-density air advect smoke density. Dunno if this is physically 100% correct, but it gives pretty nice results =)

In SIGGRAPH2003 there was a paper on modelling special kinds of explosions using incompressible equations, btw...

- Mikko Kauppila

Share this post


Link to post
Share on other sites
quote:
Original post by uutee
>>
>> from grhodes_at_work
>>But 40 x 40 x 40 = 64 thousand equations for the Poisson
>>solve (see below) and that is prohibitive. No way in hell
>>this will run even at 1 fps on current desktop hardware.

I''m having 61 thousand equations running at 2.7fps on my XP1700+ on Win98 All other simulation (advection and things) included (Poisson takes 70% of the time). I''ll do a Win2k test later...



Heh heh! So you proved me wrong, . That''s cool. Still, I don''t thin 2.7fps is acceptable for real-time games!

By the way, I wrote a multigrid solver for the Poission equation several years ago. It ran darned fast on my old computer, which was, I think, a 233-ish MHz Pentium. For a 2D, 100 x 100 grid, I think it was taking a second or two at most even then. That''s 10000 cells, but it was a full Euler solve so 2 momentum equations per cell, plus mass conservation plus a state equation, 4 equations per cell total, or 40,000 total equations. I''ll have to pull that code out and see how fast it runs on my 3GHz machine at work... Maybe I''ll have to rethink real-time fluids!

quote:
Original post by uutee
>> from grhodes_at_work
>>I''ll have to look at that statement. One of his basic
>>flow properties is density, which if it changes means the
>>flow is compressible. And density does change because that
>>is how he drives his flow. So, I wonder what he meant by
>>that. But....

Hmm. As long as I''ve seen, Stam does use incompressible, constant-density fluid.

The smoke flows in his method are modelled by letting the constant-density air advect smoke density. Dunno if this is physically 100% correct, but it gives pretty nice results =)



OK, I see what you''re saying, but my interpretation is different. You see, if you look at his equations (for example the top-right slide on page 2 of the presentation linked below), he actually is coupling the equation for velocity with the equation for density, e.g., the u in both equations is the same u. This means that smoke density variations create the velocity and therefore cause the smoke to advect itself. The Poisson equation is used to calculate velocity throughout the field in a mass conserving manner. Now, that Poisson equation for mass conservation IS an incompressible flow equation since it ignores density, which makes this sort of a hybrid technique. It appears Stam is using the Poisson equation to correct the fact that he is not conserving mass properly when he updates his density to begin with. More accurate boundary condition representations and time marching techniques could make his original density update more conservative, but would also introduce instabilities that require a limitation of the time step. But if you think about it, although he''s updating his velocity using a constant density mass conservation equation, he isn''t really achieving mass conservation since he''s applying those calculated velocities to variable smoke density, thus making the velocities non-mass conserving for the smoke mass.

(OT: Looking through Stam''s code, in my opinion it is difficult to follow due to his poor and inconsistent choice of variable names.)

http://online.cs.nps.navy.mil/DistanceEducation/online.siggraph.org/2001/Courses/47_SimulatingNature/stam.pdf

quote:
Original post by uutee
In SIGGRAPH2003 there was a paper on modelling special kinds of explosions using incompressible equations, btw...


Hmmm. While working on my Ph.D, I wrote a full potential flow solver (e.g., incompressible, irrotational flow) and used it to calculate the supersonic flow over a 2D airfoil. I did use an upwind difference. With an upwind difference even the incompressible equations can capture shocks. They will not be physically accurate shocks, and in my case comparing to a full compressible Euler solution the shocks showed up at the wrong place. But it still looked basically correct. One risk is that this sort of approach does not satisfy the 2nd law of thermodynamics (represented by the Rankine-Hugoniot jump condition) and beyond compression shocks in the wrong place it is possible, depending on boundary condition, to get expansion shocks. These are not physically correct and would not look intuitive---so the techniques can be used to get realistic visual effects only for very limited conditions.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
First of all. Thank you for your interest.

I have the past week tried to write a 3D edition of Jos code, but until now without much luck. I cant seem to figure out how to expand the linear solver to 3D. So now I am searching the web again for more info on the subject.

I guess that I still need to study his pper deeper and catch up on the nummerical analysis I never learned.

If anyone has some information regarding going 3D more detailed than "Extending the solver to three dimensions should be straightforward to anyone who understands our code.", I would be happy to study it.

Once again Thank You for your time!

Share this post


Link to post
Share on other sites
I can recommend the following excellent book that is an intruduction to computational fluid dynamics and the associated numerical methods. With some study, this may help. It certainly is a hell of a lot better starting point than Jos'' paper.

"Computational Fluid Dynamics: The Basics with Applications," by John D. Anderson, Jr., ISBN 0070016852

Amazon.com link

This is a superb book for learning about fluid dynamics and the math behind computational methods. It still focuses on 2D, but Anderson goes into enough depth about how the equations are set up and solve that extending to 3D would be easier from the book.

Sadly, this isn''t an inexpensive book. The lowest price I''ve seen, on bookfinder.com, was around $50. I bought mine at the North Carolina State University bookstore, and you too may find copies in University bookstores if there are any nearby.

Graham

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by grhodes_at_work
Look for Jos Stam''s work on real-time stable fluids. He has a nice, simple system. Even has a version that runs on handheld computers (with no floating point math and no 3D graphics card). The OpenGL "Superflow" demo that nVidia provides with their Cg Browser is based on Stam''s code. And the code is provided.



Thanks for this pointer BTW. Frankly, I stink at math and always have, but the actual implementation is pretty straight forward and I''m starting to understand it. I hope someone can help me with a few questions though.

One of the demos included with the paper and source is a Wind Tunnel demo, and another demo that looks like blobs of paint falling to the ground. I''m trying to recreate these effects using the provided source.

Can anyone describe how to modify the solver to create these effects?

To simulate gravity to force the "paint" to fall, I changed the v_prev initialization to set all v_prev values to >0.0. I found 0.1 to work well. Seems to work OK, but doesn''t quite look the same as the demo. Is it necessary to also modify the diffusion to not diffuse "upward" against gravity?

Also, in the demos it is possible to add boundary objects that the flow goes around, especially used in the wind tunnel demo. The provided source doesn''t implement this feature. Can anyone describe how this is done?

Thanks,

Geoff

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Dang it! Noboby knows, eh? Oh well.

Has anybody been able to take the Jos Stam code and change it to fixed point? Despite the paper''s claims of how simple it is, I''ve had some trouble getting it to work right.

When I create a new velocity (force), the velocity only spreads so far, then stops, and any density that hits the point where the velocity stopped spreading disappears. In the original floating point version, the velocity continues to advect and diffuse over the entire area, which makes perfect sense since the exact same functions are used on the density and the velocity.

If anybody has it working, would you mind sharing the source, or at least some ideas.

Thanks,

Geoff

Share this post


Link to post
Share on other sites