# Filling a scene with cubes

I am trying to design a solution for simulating gaseous fluids in confined areas, I am using naiver-stokes equations for fluid dynamics but since it only covers incompressible fluids like liquid, i needed to find a way to simulate compression

Recently, I came up with the solution which is, creating a field storing pressure data for each volumetric partition and I thought it would be a good idea to construct this field as a composition of cubes where each cube has homogeneous pressure value within itself.

I tried to inflate a cube from a point and create other cubes from its surfaces recursively minding the collision with surfaces inside that scene, but this algorithm fails because there are lots of detailed cases involving complex holes and notches on the object. Is there a better way to construct this field?

• Are you programming on paper or are you using specific tools / languages? By the way, this question belongs on SO (after a revision). – Job Dec 12 '11 at 19:16
• Paper oriented mostly, although i need to make a demo. Development environment is rather trivial. I just want some algorithms to solve the problem. SO is mostly about specific problems on specific prog. languages and tools. – Hgeg Dec 12 '11 at 20:47
• What's the paper you are reading and what's the name of the algorithm? – PhD Dec 13 '11 at 1:13
• My work is derived from the paper "Physically Based Modeling and Animation of Fire",Fedkiw et al, 2001. However there aren't any algorithms i took directly. That paper and most of the others use a fixed grids or voxels for pressure fields. However in my case these voxels need to be constructed according to the objects in the scene. – Hgeg Dec 13 '11 at 10:47

First off, the Navier-Stokes Equations don't assume incompressibility in general. You can simplify the equations if you assume incompressibility, but it's not necessary.

Second, I have to ask: Do you have a really good reason not to be using off-the-shelf computational fluid dynamics software? Finite element analysis in general is not for the faint of heart.

To address your actual question: Dividing the fluid volume into cubes should be straightforward. Personally, I would just divide the entire volume into cubes, then find the ones which are in the fluid. You can speed things up with a proper recursive fill (as suggested by Tydus), but you can also just check every single cube, if you don't mind trading a bit of CPU heat for some typing.

Another aside, addressing your proposed solution: Assuming homogeneity within the cube (element) is an odd choice. It would be much more typical to use first order interpolation. If you're hoping to use a left-hand approximation to try to solve the differential equation for each element independently, beware: numerical instability looms, and your results may well be totally wrong. (In general, you should be thinking 'these results are probably wrong' whenever using numerical methods, but this probably is particularly probable).

Typically, for this sort of problem, you need to assemble the full system of equations and solve simultaneously. (Like I said, not for the faint of heart).

• The thing is, I am not trying to fit cubes into fluid volume. The system that contains the cube simulates the pressure field of the air, so that the gaseous fluid particles tend to move to the cube with the least pressure. Calculating the pressure value and particle velocity inside each cube, as you said, is straight forward. My question is to fill all the scene with cubes. As I said I couldn't find a solution that works for all(or at least most) of the cases. – Hgeg Dec 13 '11 at 10:54
• "I am not trying to fit cubes into fluid volume" and "My question is to fill all the scene with cubes." seem to be a direct contradiction. Please explain. "Calculating the pressure value and particle velocity inside each cube, as you said, is straight forward." Only if you have deep knowledge of the fundamentals of CFD - if you don't, be careful. – ipeet Dec 17 '11 at 3:21

A recursive "fill" should work for any shape no matter how complex. Unless a single cube is to big to fit in the hole.

What are the cases where it fails?

• I actually use some kind of recursive fill. The problem mostly caused by the fact that there is no specified minimum size of holes or shapes. For example, when inflation of a cube stops because of collision with a surface, next recursive calls are made on the each surface of the cube as you expected. However, the question is, how can I decide the initial position of the new cube on the surface of the old cube? I need to trace the holes by iterating over the surface, but the resolution is infinite, since there is no minimum limit for hole size. – Hgeg Dec 13 '11 at 11:01
• On collisions you can use smaller and smaller cubes. Filling in smaller and smaller holes. Like in calculus you get closer and closer to a limit, at smaller and smaller intervals. If the size of the cube is important in some way you could express the pressure relative to the cubes size to keep things proportional. It will not be easy if the shape is random and irregular because there will be all sorts of different curves. I might go for an imperfect solution where you just start off with "small" cubes and hope it gives a answer close to the truth. – Lord Tydus Dec 17 '11 at 4:00

I've seen an implementation of fluids using cellular automata, you could representate them with the minimum size that's meaningful to you. Cubes, spheres, whatever. The shape of the container shouldn't really matter with this method, just add the rules that generate new cells to "fill" complex shapes.