   2d particle integration
  I'm creating a 2d particle engine and came across the peculiar problem of what I think is called "integrating"; i.e. repeating an algorithm on the particles which separates them until all intersections are shallower than a threshold. Cutting straight to the point, does anyone have any gotchas, advice on where I should start, or optimisations I should attempt to use? I have no mathematical background so complex equations or concepts will be kinda useless to me, but I will try to understand if I must.So far, my textual theory looks like this:Quote:1 unit = 1 pixel.Particles are 1-unit wide, rigid circles. When two particles collide, they bounce off each other.Particles will intersect during collision due to discrete collision checking.When two particles intersect, they non-physically expel each other to a correct distance.These expulsions can introduce more intersections, which are also solved- producing a potential cascade of intersections.The algorithm which computes this cascade is an integration solver. (?)During integration, no physical reactions are evaluated.Technically, it can only fully solve when no two contacts on any particle have an obtuse angle between them. Otherwise it cannot.Therefore, it solves until all intersections are below a given level of error instead.After integration, physical contacts are evaluated as normal.INTEGRATORThe canvas used to accellerate collision checks stores multiple particles on single pixels.Paste PhaseWhen a particle is pasted from an array to the canvas, it checks for intersections around it. If one occurs, it is added to a vector<> of particle pairs that require solving. (Duplicate pairs will occur, they may be costly to process if this method has high redundancy)Integration PhaseOnce all particles are present on the canvas, the array of intersections is iterated from end to start, popping them as they are solved.After solving a pair it performs an intersection check for the two repositioned particles, any results of which are appended to a second array.When the first array is empty, they swap places.This repeats until both arrays are empty, or an iteration limit is reached.PROGRAM MECHANICSCanvas stores 2 pointers to particles per pixel allowing a maximum particle "compression" to be solved of up to 2x.If the two pointers are filled, any additional particles are simply dropped from collision detection.This keeps the integration complexity at a reasonable level, letting it continue to solve over several frames.If anyone is curious about the game project behind this, here. ^^http://www.gameblender.org/download/file.php?id=1379   
  Bump. Surely someone must know something about this?   ;  Oh, it's a falling sand game.  :)Actually, there are a lot of optimizations you can do.  The first one is probably the most major: Move your entire simulation on to the GPU.  It's basically a cellular automata, which is ideally suited to GPU programming.  You should handily be able to do absolutely crazy sized sims.Basically you have the previous state as a big texture.  Then you feed that into a pixel shader with a render-to-texture.  That new texture is your new state.  Display it to the user and repeat.All interactions are local, so it's pretty easy to write the shader code.  In math speak, the area around a cell you're updating that can affect it is called a "kernel".  Basically you can treat the CA as a big matrix that you're performing operations on.  Not that you really need to know that :)ie: A kernel looks like this:UL UC URCL CC CRLL LC LRWith CC being the center pixel.Shaders or no shaders, the primary way sand games work is to define a huge array of all possible interactions for a kernel.  Then there's no calculation, you just look up into the array.Another trick is to somehow bound where there aren't any pixels, so you don't spend most of your time determining that an empty kernel = an empty kernel.  I don't know the exact methods involved, but it can be as simple as bounding boxes around areas that are full of pixels.It should be an easy enough project even if you don't know anything about shaders.  But I would recommend using shaders.   ;  Thank you very much for your help, Numsgil.On the topic of shaders, I'm developing on a Toshiba NB100 (945 GM), which has no GLSL support. So I can't really go into that area of optimisation (although I thank you for the knowledge- I will remember it. Perhaps one day, when I have a half-decent computer..)Kernels, I've heard that word used before. I understand what Falling Sand games do, but I'm not looking for that kind of simulation. I am essentially looking for a fast way to simulate a lot of physical circles, that are each the size of a pixel. Most FSG's I know of do not technically do this, rather they use a system based around random repositions and location swaps to achieve the appearance of incompressible flow.The "kernel" is not so closely meshed with the behaviour of particles- it is merely a collision speedup for otherwise sub-pixel particles.All particles are "pasted", that is, their positions converted to integer locations, onto a 2D array of pointers. During this operation, the 'kernel' of the pixel the particle is on is checked for non-NULL pointers. If one is detected, it's sub-pixel distance is calculated (probably X+Y Hamiltonian, for speed, but w/e). Colliding particles are added to a list of collisions. Since more than one particle can end up on the same pixel, it has a storage depth of 2. If more than the limit of particles are in the same place, they are simply dropped from collision until more space is resolved.The collisions are then solved, coming to the nub of my problem, by what I believe is termed an "integrator".If I'm doing something too complex for my.. "level" (17, self-taught), say so and I will opt for something I can't get wrong as easily.A note on the performance implications: I don't need a massive simulation, I need small amounts of high-quality simulation. This isn't for an FSG as I may have said earlier- although it's almost impossible to tell, this is aiming to be a spinoff of Jetmen Revival. Generally, the most being simulated is a couple of hundred particles at a time, for debris knocked out of the terrain.   ;  Ah, okay, I think I understand what you want to do.Here's a very, very important question: do your particles need to interact in any way (like stacking)?  If not, you can leverage traditional methods for particle systems (again, access to a shader allows for some amazing leverage of GPU parallelism, so it's too bad you don't have a shader capable card :/).An "integrator" is an algorithm for determining the position of a particle in the future based on its current position, velocity, and acceleration.  As long as your particles don't have any drag, you can "integrate" them using a very familiar equation (you should learn it in a physics class in Highschool if you haven't yet): df = d0 + v0 * t + 1/2 * a * t^2 (where d is position, f means final, and 0 means the value at time 0).  You can in fact determine the position of the particle at any time in the future without any additional effort beyond just changing your "time step" (t).The trick with particle engines is to simply maintain a list of particles instead of providing a large pointer grid, since the number of particles is always << the number of pixels a particle can exist in.  You can simulate particles as dimensionless points instead of very small circles.  You lose the necessity (or ability) of colliding particles against each other, which saves a great deal of CPU time but potentially limits the sort of weapons you can use (like a wall of particles to block others).  You can improve the time it costs to collide particles against ships (say) by sorting particles into large grids, but this should only be necessary with particles on the order of about a thousand or more.If you need or want particles to interact, I would recommend a FSG approach.  You lose the ability for particles to have ballistic motion, but you can have a lot of particles.  Enough to bury a ship, for instance, which could be a fun tweak.   ;Quote:what I think is called "integrating"; i.e. repeating an algorithm on the particles which separates them until all intersections are shallower than a threshold."Integrating" is any act of summing up small quantities. In calculus it means adding small (infinitesimal) increments of an equation to find (essentially) the area under the curve. In particle systems, you're adding small increments of the velocity to find the position after a quantity of time. There is a number of schemes for doing this; for example, you can have Euler integration, Verlet or Velocity Verlet integration, and there are 'better' (i.e. more accurate and stable over time) schemes such as Runge-Kutta. All of them (when applied to particle movement) involve finding a small position change depending on a time step, but for the higher-order schemes you can often use a larger time step without compromising accuracy. Of course for a game you might not have control over the time step, as it will probably be defined by your frame drawing time.   ;  @Numsgil:Yes, I would like the particles to interact. Currently they have no awareness of other dynamic particles and are simulated as points, and I would like to change this so that they are simulated as circles. Stacking is the primary goal. I would like dynamic particles to slide over each other and demonstrate an ability to "landslide", for instance. But I would like for particles to have ballistics too...am I being overambitious?I had the definition of integration quite wrong! Thank you (and Shaolinspin) for defining it. I am using a fixed timestep, so my "integrator" is simply df = d0 + v0. I am happy with this at the moment because it is fast. If there is a reason to change it I shall.I do keep all dynamic particles in a list. As I want to collide them with each other I also intend to temporarily store them in a grid. Ships could potentially also use this stage for their collisions with dynamic particles. Organising particles into bounding boxes seems a CPU heavy task in itself, and after a box collision is identified, all it's contained pixels must be checked against the ship's particles. If the necessary memory is used (1mb for 512*512 grid, 2mb for depth of 2 pointers) to instead maintain a memory-space 2d grid, I believe checking collisions is faster.Because the pointers are temporary, and the particles are permanently tracked using the list, clearing the temporary grid each frame can use a simple memset().I think my problem is now is a stacking algorithm. Something to solve penetration in stacks.@Shaolinspin:As said my timestep is fixed; I do not need accuracy or determinism. Thank you for the information; Verlet is quite interesting..Again, I thank you all for your extensive help. Sorry to be such a bother about this. =P[Edited by - Raiderium on June 23, 2009 8:35:38 PM];Quote:Original post by Raiderium@Numsgil:Yes, I would like the particles to interact. Currently they have no awareness of other dynamic particles and are simulated as points, and I would like to change this so that they are simulated as circles. Stacking is the primary goal. I would like dynamic particles to slide over each other and demonstrate an ability to "landslide", for instance. But I would like for particles to have ballistics too...am I being overambitious?Yes. ;)Stacking is something normal physics engines which can handle circle to circle collisions are terrible at.  That's the primary strength of FSGs.  On the other hand, FSGs generally don't handle ballistic motion at all.  They just move particles from cell to adjacent cell, which is basically constant velocity.You're going to have to make compromises to get it working like you want in all probability.  Maybe some particles are ballistic and others are FSG-esque and can stack.  Or maybe you can turn ballistic particles into FSG particles at some point in their lifetime.If you're really adventurous you might try experimenting to combine FSG techniques with ballistic motion.  Not really sure how it would work, or if it's even possible, though.Given your experience level, I'd recommend abandoning ballistic motion and stickign with a FSG algorithm.  They're well known enough that it should be easy to get advice on how to handle them.  And ballistic motion isn't mandatory for the sort of gameplay you're after.  And even if you never get as far as actually finishing the game, you still have a FSG, which is impressive in and of itself.And you can always later go back in and tinker to try and add ballistics.Quote:I had the definition of integration quite wrong! Thank you (and Shaolinspin) for defining it. I am using a fixed timestep, so my "integrator" is simply df = d0 + v0. I am happy with this at the moment because it is fast. If there is a reason to change it I shall.How are you updating velocity, though?  Are you doing something like:vf = v0 + adf = d0 + vfThat would be semi-explicit euler.  If the acceleration is constant you'd be better off doing df = d0 + v0 + a / 2 (assuming time step is 1), because that's the exact equation of motion.  Semi-Explicit Euler overestimates the real motion, which may or may not be an issue.   ;  Each particle stores velocity and position. If something wants to apply a force to a particle, it adds the accelleration to the velocity. The velocity is added to the particle each frame. That's my current system.I will take your advice to use an FSG algorithm.   