moucoulin 144 Report post Posted June 28, 2005 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? 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted June 28, 2005 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). 0 Share this post Link to post Share on other sites
moucoulin 144 Report post Posted June 29, 2005 Thanks for the answer. I will not have to tweak my code then. 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted June 29, 2005 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 tolerancevoid 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;} 0 Share this post Link to post Share on other sites