Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

This question already has an answer here:

My collision detection initially seemed to work well enough, but my answer to this question shows that I have went with SAT testing now instead. My goal was to find the plane at which to slide the player when a collision happens, not to implement a commonly used method that 'works well enough' such as Minimum Displacement.

A more accurate and unique question would probably be how to find the first plane of collision in a (possible) multi-object collision of 1 aabb to 1+ aabb objects. My answer below is what I've went with, but please add your own and I'll happily accept them if they provide more than my own answer.

As the picture below demonstrates, from one frame to the next, if the red square moved from bottom up as the arrow points, I need something to show that the bottom face of the black square is what was collided with (or the top face of the red square).

enter image description here

From the book "Real Time Collision Detection by Christer Ericson" I am using the following code to get the first and last contact times of an AABB to AABB collision. I iterate through all cubes around the player in the direction of their current velocity (ensuring their velocity is handled in small increments if too large) and get the first contact time, then I sort all collisions by said contact time. I've modified the code below to report which edge was collided with (if it didn't start out with a collision), and with all of these things I can get the answer I needed.

// Intersect AABBs ‘a’ and ‘b’ moving with constant velocities va and vb.
// On intersection, return time of first and last contact in tfirst and tlast
int IntersectMovingAABBAABB(AABB a, AABB b, Vector va, Vector vb,
float &tfirst, float &tlast)
{
// Exit early if ‘a’ and ‘b’ initially overlapping
if (TestAABBAABB(a, b)) {
tfirst = tlast = 0.0f;
return 1;
}
// Use relative velocity; effectively treating ’a’ as stationary
Vector v = vb - va;

// Initialize times of first and last contact
tfirst = 0.0f;
tlast = 1.0f;
// For each axis, determine times of first and last contact, if any
for (int i = 0; i < 3; i++) {
if (v[i] < 0.0f) {
if (b.max[i] < a.min[i]) return 0; // Nonintersecting and moving apart
if (a.max[i] < b.min[i]) tfirst = Max((a.max[i] - b.min[i]) / v[i], tfirst);
if (b.max[i] > a.min[i]) tlast = Min((a.min[i] - b.max[i]) / v[i], tlast);
}
if (v[i] > 0.0f) {
if (b.min[i] > a.max[i]) return 0; // Nonintersecting and moving apart
if (b.max[i] < a.min[i]) tfirst = Max((a.min[i] - b.max[i]) / v[i], tfirst);
if (a.max[i] > b.min[i]) tlast = Min((a.max[i] - b.min[i]) / v[i], tlast);
}
// No overlap possible if time of first contact occurs after time of last contact
if (tfirst > tlast) return 0;
}
return 1;
}
share|improve this question

marked as duplicate by Byte56, Nicol Bolas, Sean Middleditch, bummzack, msell Jun 5 '13 at 8:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
probably something to do with a dot product of a normal and a velocity vector –  Eric B Jun 4 '13 at 19:13

1 Answer 1

What a typical physics engine would do is identify the axis of minimum penetration. For axis-aligned shapes, this is trivial. The two possible axes are horizontal and vertical (each with possible directions).

You measure the overlap on each axis. Select the minimum. Then separate the objects by that amount. This will also tell you which of the surfaces came in contact. From which point you can apply physics simulation (i.e.: bouncing and friction).

Of course, if the object is moving fast enough, this can give the wrong answer. But at reasonable speeds, and at 60FPS, this works well enough for real-world use.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.