Particle Collision Algorithm

[SLH]

Hi all, this is more of an algorithm question than a maths question as i already have the collision/response formula working for a pair of particles and a particle with a convex polygon.

My problem is this. Lets say i have a flat object at the bottom, and drop lots of particles on it. What tends to happen is it takes ages for the particles to start spreading out. The ones on the edge only move out as the ones next to them move, and the particles in the middle of the bunch tend to just move back and forth rapidly as they continually bump.

I think one solution could be performing the collision detection/responses in a order according to how 'close' a particle is from an immovable object, or a particle that's touching an immovable object.

I have a query that will get me all particle pairs that are colliding, in no particular order.

I want an algorithm that will order something touching a wall first, then pairs with particles touching those next, then pairs with ones touching those pairs etc. If an algorithm to order the pairs like this is too expensive/complex then i'd like to just process them in that order, ideally without querying all remaining pairs each time.

Any suggestions welcome!

[jemidiah]

I think what you've said is a bit ambiguous. That is, suppose you have two particles touching opposite walls. Now suppose they're both touching two more, different particles, A, and B. Suppose A is closer to the wall than B, even though they're both just one particle away from touching the wall. Do you want A to come before B in this order? To add more complexity, say that A is also touching, in sequence, A1, A2, and A3. Suppose B is also touching, again in sequence, B1, B2, B3. Each of these sequences gets closer and closer to the center. Now delete B--the B1->B2->B3 sequence is no longer one step away from touching the wall. Where would you like B1->B2->B3 to come in the processing order? Before the As are processed? If the A and B sequences eventually touch through a series of intermediate particles, the order will matter (depending on if you process collisions in a buffer or in-place; that is, depending on if you update particle positions as you process their forces instead of remembering their positions through an entire update).

If you just want to process balls in order of distance from the outside, that would probably be an expensive operation. The fastest sorting algorithms operate in O(n log(n)) operations, though the constant out front would matter here. Even if you just wanted to find out which balls were touching the outside edge you'd have to look at every element in your results which might take a while each update pass in-and-of-itself, not even counting the processing time of distance calculations.

The distance calculations themselves could be complex, depending on the geometry of your walls. For instance, calculating the distance from a point to a plane is given here (http://mathworld.wolfram.com/Point-PlaneDistance.html) in Equation 9; other objects would be more complex.


If you knew that certain particles touched a wall, you could leap from them to the particles they touch in turn. If your collision code generated a graph of collisions, this traversal would be pretty simple and would approximate the ordering you want. You would probably want to start a "search" on every object touching a wall. You would mark each interaction you've calculated so that you don't step on your own feet. so to speak, as you expand out from each of these objects simultaneously. At each step of this "search", you would calculate the interactions you encounter. Note that if your graph isn't connected, you might have to add special cases to begin searches on connected subgraphs which don't touch walls. The overhead in this search would probably be very small compared to remotely complicated physics calculations, though I have to say I wonder about caching--you would probably be jumping around a lot in memory which might take a lot of extra time swapping out cached data. Then again, if your collision pair results are returned in an arbitrary order, you're probably already getting the same amount of this effect. (It's much more pronounced on large numbers of particles, of course, when you'd actually fill a cache.)


You might find it useful, if you're not already, to "save state" and calculate particle interactions in stages as I've implied you could. That is, on Frame 1, you copy all of the velocity and position information for each particle, figure out force interactions, apply those force interactions *using the saved velocity and position data* (the order then doesn't matter), update the frame on screen, and repeat for Frame 2 and on. This would take a little bit of extra overhead in copying and data storage, though you'd avoid an extra pass through all of your data, or an extra search, either of which would probably take at a bare minimum just about as long, or at a maximum far longer.

If you gave more specifics about the setup or the original problem and not just your guess at a possible solution I might be able to be more specific.

[SLH]

Walking the tree sounds interesting. I might give that a go since it should be too hard to code something up just to see how it runs.

The problem i'm having is that collision detection/response works fine between 2 particles, however lets say there are 3 particles in a line, A, B, C, overlapping each-other slightly, with C against a wall.

The collision pairings might be (A, B), (B, C). As a result i process (A, B) first, moving B closer to C and A away from B. Then i process (B, C), moving B back closer to A and C away from B.

Then i process the collision with C and the wall, moving C back where it started.

As a result, A has moved to the left a small amount and B has barely moved when what should really have happened is that A, B and C should be all touching but not overlapping with C still against the wall.

With more particles, in a general clump the observed effect is that the edge particles move away slowly based on the ones next to them moving into them and ones towards the center of the clump move repaidly back and forth each frame.

I'm starting to think that i need to do proper collision prevention rather than just collision detection, i.e. not letting particles overlap at all, however i'm not sure where to start with that.

My overall goal is to use many particles to simulate a liquid. The simulation doesn't need to be accurate, i just want it to look pretty! :D I've already coded rendering via iso-surfaces so i'm not particularly bothered about the locations of individual particles either.

[jemidiah]

My first thought is to forcibly move intersecting particles away from each other. This could be done easily for two spheres that overlap--take a line connecting their centers, find out how much they overlap along this line [sum of radii minus distance between centers], and move each one away from the other by half this distance. You might also want to consider such a forced motion to be the result of a collision. To make the physics more realistic, the particles should have a coefficient of elasticity which says how much they bounce off of each other when they collide [i.e. are they rubber balls or lead balls?].

On each frame you could compute standard physics effects for the whole system at once, followed by a second pass to process these fake collisions. I suppose you could also compute these at the same time as you do your standard physics. One thing I'm worried about is a whole bunch of particles very close to one another causing collisions which cause more collisions .... If something like this is a problem, I have ideas for getting around it.


It occurs to me that the math behind faking such a collision is slightly involved. If you need, I can try to figure it out for you. Then again if you're doing this physics simulation you might be fine doing it yourself.