Solving 2D Collision Detection Issues with Relative Velocities

Question

Imagine you have a situation where two objects are moving parallel to one-another and are both within range to collide with a static wall, like this:

  => 20m/s     => 40m/s
+==========+ +==========+          +======+
| Object A | | Object B |          | Wall |
+==========+ +==========+          +======+

 |-- 1m --|   |-- 1m --|  |- 1m -|

A common method used in dynamic collision detection is to loop through all objects in arbitrary order, solve for pair-wise collision detection using relative velocities, and then move the object to the nearest collision, if any.

However, in this case, if object A is checked first against B, it would see that the relative velocity to object B is -20 m/s (and would thereby not collide this time frame). Then it would see that the object A would collide with the static wall, and the solution would be:

+==========++==========++======+
| Object B || Object A || Wall |
+==========++==========++======+

And the red object passes through the blue one. So it appears to be a matter of choosing the right order in which you check collisions; but how can you determine which order is correct? How can this passing through of objects be avoided? Is ignoring relative velocity and considering every object as static during pair-wise checks a better idea for this reason?

Answer 1

This is a very complicated problem, and is better known as the "box stacking" problem. Even without moving objects, a stack of boxes will jitter and collapse in all simple physics engines.

There are a number of steps to a proper solution. The most important is to use an iterative solver.

That means that you don't just resolve the collisions in single pass. You do multiple passes, accumulating the impulses necessary to push the boxes apart. The end result will still be imperfect, but the amount of error will be much smaller, possibly unnoticeable.

The math is a bit trickier as you do need to deal with impulses and forces rather than just pushing the boxes apart and adjusting velocity. You can do it by just adjusting the values, but it's unlikely to work satisfactorily for any cases but the simplest.

Erin Catto has done a number of talks and papers on the basic techniques, which i believe are available on the Box2D website (http://box2d.org/) if you dig around enough.

Answer 2

this is really 2 different conditions that you are asking about:

"how do I know if a collision was supposed to happen, but didn't"

and

"how do I resolve multiple collisions on the same object from different sources"

for bother there are 2 different approaches that come to mind to either avoid, or mitigate the situation: adding a pre-collision raycast system, and grouping collisions together.

for the pre-collision raycast this basically uses the objects current velocity, and uses that as a ray-length, and if another object touches that ray then next frame there "might" be a collision between them. I say might because if both objects are movable then there is a chance that the object will move out of the way, but this should be a trivial concern if have a multipass collision handling system.

for the grouping of collision this can either be used independently, or in conjunction with the pre-collision raycasting, or can be taken from a spacial-partitioning/hierarchy system. where if there is at least one collision then the objects that are around that collision by a determined value (this could be found statistically, or by trial, and error), and they are included in the collision system, and the entire system is solved (or attempted to be solved) all at once.

on the immediate situation I would say that the pre-collision raycasting would be most beneficial.

Though if your completely convinced that pre-collision raycasting is unusable, or to much overhead, and the case of objects passing each other is of great concern then you could log the position of each object the frame before, and then determine if a collision happened somewhere in the middle. though what I have found is that this in the long run is more costly, and only works a fraction of the time. not to mention having the problem that you are making your collision resolution system do a "lot" of guess work on how to resolve the collision that it does not have solid data on.

Answer 3

A common method used in dynamic collision detection is to loop through all objects in arbitrary order, solve for pair-wise collision detection using relative velocities, and then move the object to the nearest collision, if any.

An alternative solution I employ in a game I am working on, is having a sorted event queue (sorted according to time). When calculating the next frame, I simply fast-forward the game-time to the first event in the queue, handle the event, and add any new events resulting from this event to the queue. This is repeated until the time is equal to the current frame time.

If the event is a 'collision' event, I find the first intersection time between the colliding object and any other object, and return this new event. This event then gets added to the queue, and this event will be evaluated first, instead of the event that was invalidated.

I then allow objects to keep track of collision events involving themselves, and when they collide, all of these events are marked as 'invalid' (e.g. removed from the queue, or ignored when they are evaluated in the key).

This creates a deterministic system in which events will always happen as expected.