# Collision Detection

## Recommended Posts

I have read alot of articles recently about collision detection detailing the concept, general implementation and specifics involving detecting collisions between various primitives. All this I (think I) understand, however I am left with one question. Most articles say extrapolate the velocity over the period of the timestep and find if there are any collisions, now if the collision occurs at say half the time step, collision response kicks in and the velocity will have changed, but what happens to the second half of the timestep? Do you remodel the objects new velocity over the remaining half of the timestep and check for collisions? This doesnt strike me as possible, because (confusing situation description follows) what if over the first iteration of collision detection SphereA and SphereB collide at 0.01 of the timestep, resulting in a change of velocity for SphereA, SphereC in the first iteration of collision detection collides with SphereD at 0.99 of the timestep. However SphereA on its new trajectory should have collided with SphereC at 0.5 of the timestep changing its trajectory so it doesnt hit SphereD, but this collision wasnt detected because we were still on the first iteration. I hope that was clear? Anyway, any help you could offer in clarifying my understanding would be greatly appreciated :) Edit: Terrible spelling

##### Share on other sites
SpaceDude    208
Its down to you how you want to do it... one solution is as follows:

first pass:

- Find the very first collision time, in the case above that would be 0.01. Don't move any of your objects yet, leave them where they are.

second pass:

- Move all objects to the first collision time. In this case, move all your objects by a time of timestep * 0.01.

- Subtract the amount of time processed from your timestep. So timestep -= 0.01 * timestep. This is the remaining amount of timestep left to process. Repeat until finished.

The thing you have to worry about here is getting yourself into infinite loops. Imagine a ball that only just fits between two surfaces, it will bounce of one surface then immediatly hit the other. So you need to put some kind of check to avoid that kind of thing happening

##### Share on other sites
I think I've solved this problem rather nicely. The way my physics is setup, I calculate the number of physics frames to run. Each physics frame has a fixed timestep blah blah blah. My physics engine has a 'fundamental unit' which is the largest amount any object can move at a time (this avoids the problem of objects passing through each other). Every physics frame, I calculate the number of fundamental movements to make, and I keep moving objects and detecting collisions during the physics frame just as long as there are objects that still need to move.

When an interaction occurs (two objects collide and their velocities are modified), I save the magnitude of the velocity before the collision, and I calculate the magnitude of the velocity after the collision. The ratio of the After velocity to the Before velocity gives a ratio between 0 and 1. I multiply the number of moves (which is stored as a floating point) by this fraction, which scales the number of moves left for the physics frame.

So, everytime an object moves, I decrement its NumMoves variable, and I keep moving objects in the physics frame just as long as there are objects that still need to move. When an object collides, I scale the NumMoves variable by the same amount that the magnitude of the velocity was scaled. This easily avoids infinite loops (because as soon as NumMoves is zero, the object stops moving, regardless of its velocity or if its been collided with).

You may be wondering what I do when the NumMoves variable is between 0 and 1...well what I do is I move it a fundamental unit, and if it hits something I back it off to its original location, else I increment its position by fundamentalunit * NumMoves (NumMoves is between 0 and 1 at this point).