Sign in to follow this  
Icebraker

Staggered grid

Recommended Posts

Hi everybody, I'm currently trying to implement a fluid simulator and have found out that basically all papers use staggered grids because they lead to a more stable result. However, I can't really see why the result would be more stable, because I am just shifting all velocities by 0.5 units towards the faces... Maybe someone could give me some insight on WHY it is more stable with the staggered grid. Thanks, Icebraker

Share this post


Link to post
Share on other sites
Hmmmm, I've not had any experience with staggered grids, but I do have experience with particle fluid methods. Basically, there is a particle integration scheme called the leapfrog scheme where the positions and velocities are integrated 1/2 step out of phase with each other, so slightly analogous to this staggered grids. The reason the leapfrog scheme is better is i) it is a symplectic integrator (i.e. it has better conservation properties such as conserving the total energy, and also conserves position-momentum phase-space which is important), and ii) it is time-symmetric so it can be integrated backwards in time to get the same results, which is needless to say a useful property for a stable integrator. Maybe the staggered grid has some of these properties also which make it more stable over a non-staggered grid (although the symmetry is in space rather than time perhaps??). Well, even if I'm on the wrong track, maybe that will spur someone else to give a better answer.

Share this post


Link to post
Share on other sites
HI,

thanks for your answer. I have found an article which mentions a checkerboard pattern of the pressure distribution, but I still cannot see why a staggered grid would fix that... Any insight into this is appreciated,

Icebraker

Share this post


Link to post
Share on other sites
Well, I don't have any theoretical knowledge of why, but at least to me it appears to be closer to what's actually going on. If you divide space into tiny cubes, the exchange of fluid will necessarily flow through the faces of the cubes, so why not model it there? Similarly, the pressure comes from the overall fluid in the cube, so put that in the middle.

edit: googling around I found this paper, which seems to suggest that the problem with the un-staggered grid is that the solutions for the variables becomes uncoupled. With a staggered grid, they remain coupled. Also, the effective grid length is halved.

[Edited by - Lord Crc on October 11, 2008 9:26:31 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Lord Crc
If you divide space into tiny cubes, the exchange of fluid will necessarily flow through the faces of the cubes, so why not model it there?


Actually, behind all the math, this is exactly what happens with finite volume numerical models of fluid flow (like finite difference methods, these are developed from the Eulerian viewpoint). The rate of change of a property (e.g., mass or momentum) within the volume of a cell is equal to the amount of the property leaving the fluid through the faces per unit time. This is the divergence theorem, and it is the basis for the derivation for the governing equations of fluid flow. The amount of property moving through the faces of the cell is called the "flux" of the property, e.g., mass/momentum/energy flux. When you have a uniform grid, where all cells have the same width/height/length, the math simplifies and you kind of lose the fact that the flux at the faces is represented. In that case, every face perpendicular to a given axis has the same area, so the area drops out. But, if you have an irregular grid, where the faces all have different area, the face area must be represented....if it is not, then it'll be impossible to satisfy the governing equations, which are conservation laws...there will be no hope of satisfying the divergence theorem since the flux wouldn't be consistent.

As for staggered vs. non-staggered grids...the reason for picking a particular scheme is deeply rooted in managing truncation error, necessary to achieve a stable simulation. Your numerical equations are exactly equal to the real governing equation...PLUS a truncation error due to representing only a few terms of a Taylor series expansion of the partial derivatives in the governing equation. For a simulation to be good, the integration scheme must be: a) consistent with the governing equation....which is true if the numerical approximation turns into the governing equation as cell size and time step go to zero in the limit; and, b) the truncation error must not grow over time, e.g., the amplification factor of truncation error must be <= 1. Truncation error goes to zero in the limit, but for non-infinitesimal cell size and time step, it will be nonzero and must be controlled. (Note that truncation error has nothing at all to do with roundoff error. Even if you had infinite precision, on a grid with limited points and a scheme that only uses a few points to influence each cell, you are truncating the representation of partial derivatives and truncation error is present.) So, it isn't always intuitive why one method works better than another. A staggered grid isn't the only way to ensure everything is coupled, for example. There is a technique called von Neumann stability analysis that can be used to evaluate the stability of a given scheme. Stability doesn't mean error is small, but it does mean truncation error will not grow unbounded, so the simulation won't go completely haywire.

I apologize if that is a bit too much. I gave a talk at GDC 2001 about some of this. It was on the subject of rigid body simulation, but conceptually the von Neumann stability analysis stuff is exactly the same for fluids. You can find my presentation here: GDC 2001 archives. Look for "Stable Rigid-Body Physics." There's a paper and a presentation. There is discussion of linear stability theory in there, which is very related to von Neumann stability analysis. The paper/presentation aren't necessarily easy to use, especially as it was written from the point-of-view of rigid body simulation rather than fluids, but you might find them useful anyway. My background actually is fluids, so even that paper/presentation was written by someone who started out doing fluids simulation....er.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this