Sign in to follow this  
moucoulin

Handling near collision times

Recommended Posts

How is this usually done? Currently I'm implementing a light collision test engine which, within a certain distance to another item, predicts the time of collision and then integrate the movement equation up to the predicted time. Sometimes it happens that the time step is nearly the time of the collision, returning a nearly equal to zero time. Since the time prediction is based on finding the roots of 0.5 a*t^2+v*t=x, one root is nearly zero. With rounding errors, it might also come as being inferior to zero etc... How is this kind of cases are usually handled?

Share this post


Link to post
Share on other sites
tolerances. You don't stop at zero, but allow for a small margin of error. Ultimately, this would possibly lead to a negligeable enery loss, and things like that. It's unnavoidable with floating point maths (maths innacuracies near zero).

Share this post


Link to post
Share on other sites
just a note. "Predicting the time of collision then integrate".

Usually, for collision detection purposes, the movement, within a collision timestep, is considered linear. For example, to detect two balls colliding, you only consider their displacement (or linear velocity) for collision. Else, you end up with very complicated equations.

Therefore, when you find a time of collision, it becomes an approximation.

And so, if objects collide at time t, you don;t integrate per-se (calculate new velocity, calculate new position, ...), you simply move the balls in a linear fashion to the time of collision. You don't do a full integration since the time of collision found isn't considering things like acceleration and rotations.

Once you moved the ball to the time of collision, you generate collision impulses that will modify your velocity (and possibly angular velocity). Then the velocity vector will make the balls move away from the collision and you can start another collision test.

for tolerances, it's quite a tricky subject, and can make your collision fail if you're not careful.

for example, imagine a ball falling on a wedge, and hitting two planes at the exact same time (or very very very close). If you process collisions one at a time, then tolerances could give you problems, as when you process the collision or move the ball to the closest contact, that could possibly make the ball intersect the otherplane ever so slightly, and your collision test may or may not be able to handle that case.

For your second order root solver, like in the case of two balls, if you have a negative root and a positive one, it usually means that the balls have intersected. If you have two negatives, it means that the balls are "behind each other" in time, and will not collide this frame. If you have two positive roots, you only consider the smallest one. If both roots are greater than the timestep, it means that the balls are too far from each other to collide this frame. ect... Negative roots are usually ignored.

All that could make the light collision engine not so light anymore :) THere is never something simple in collisions, and always little gotchas due to numerical innacuracies and special cases.

Here is an example of a collision loop.


class CCollisionResult
{
public:
CObject* m_apxCollidedObjects[2];
float m_fTImeOfCollision;
Vector m_xCollisionNormal;
Vector m_xCollisionPoint;
};

const float fTolerance = 1 / 1000.0f; // 1 / 1000th of a second tolerance

void Collide(CObject** apxObjects, int iNumObjects, float fTimeStep)
{
float fTimeLeft = fTimeStep;

while(fTimeLeft > fTolerance)
{
CCollisionResult xCollisionResult;

// find the very first collision withing timestep [0, fTimeLeft].
bool bCollision = FindEarliestCollision(apxObjects, iNumObjects, fTimeLeft, xCollisionResult);

// no collisions left, bugger off
if (!bCollision)
{
break;
}

// move ALL objects to time of collision
TranslateObjects(apxObjects, iNumObjects, xCollisionResult.m_fTImeOfCollision);

// change colliding object's momentum
ProcessCollision(xCollisionResult);

// reduce the time left to find collisions
fTimeLeft -= xCollisionResult.m_fTimeOfCollision;
}

// finished finding collisions, move all objects to the end of the frame.
TranslateObjects(apxObjects, iNumObjects, fTimeLeft);
}

bool FindEarliestCollision(CObject** apxObjects, int iNumObjects, fMaxTime, CCollisionResult& xCollisionResult)
{
bool bCollisionFound = false;

// test all objects against each other
for(int i = 0; i < iNumObjects; i ++)
{
for(int j = i+1; j < iNumObjects; j ++)
{
// two objects collided with the timeframe [0, fMaxTime].
if(ObjectsCollided(apxObjects[i], apxObjects[j], fMaxTime, xCollisionResult))
{
// change max time to find other collisions
// that could be earlier still.
fMaxTime = xCollisionResult.m_fTimeOfCollision;
bCollisionFound = true;
}

}
}
return bCollisionFound;
}


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