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]

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.

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.