How do I deal with AABB sweep ghost collisions?

Question

I've been trying to wrap my head around this for some time now.

I wrote an implementation of AABB sweep collision detection. I though I understood the idea but it didn't work as expected. I rewrote it from scratch following the first part of this article but adapting for two moving objects (relative velocity instead of velocity of one of them) and normalized time (divide time by dt to know if collisions happen on this frame) but it still detects collisions wrong.

A similar question was asked on Stack Overflow last year but went without answers.

¿How wrong?

This is a stationary state of the simulation. Red rectangles represent hitboxes. What's happening here is that the green cube is "resting on top" of the black pillar to its right after a vertical fall. If the pillar was right under the green block, it would detect it anyway and all would be allright but, as it is, it's giving a false positive.

I believe my last if condition might be responsible for this but still I don't think I'm fully grasping the meaning of AABB sweeping.

if (entryTime > exitTime
      || (xEntry < 0.0
      && yEntry < 0.0)
      || xEntry > 1.0
      || yEntry > 1.0) {
  // there's no collision
  return false;
}

So... As I understand, I'm checking that:

1. The entry happens before the exit. (this is not supposed to ever happen)
2. xEntry and yEntry haven't both happened yet (time left for them isn't negative)
3. Neither xEntry nor yEntry are going to happen after the frame is over. (?)

That said, here are some proper questions (in descendant priority):

• Is the lack of horizontal velocity the problem? Should I add an explicit check if I know some axis collision is not going to happen, to see if the object is in collision range in that axis or not? This sounds like the way to go but I would like to avoid unnecesary special cases. (It's also very surprising to me that such an obvious problem wouldn't be taken into account).
• Else, how is AABB sweep supposed to detect A is hitting B and not just passing by as it's the case?
• Is the problem caused by any of my two "fixes" (namely, relative velocity and normalized time?)

Here's the relevant code:

function aabb_sweep(e1, e2, dt) {
  var p1 = e1.pos;
  var size1 = e1.hitbox;
  var p2 = e2.pos;
  var size2 = e2.hitbox;
  // DEVIATION ONE: RELATIVE VELOCITY
  var rel_vel = e1.vel.add(e2.vel.scale(-1));
  var xInvEntry, xInvExit; // distance between edges
  var yInvEntry, yInvExit;

  if (rel_vel.x() > 0.0) {
    xInvEntry = (p2.x() - size2.x()) - (p1.x() + size1.x());
    xInvExit = (p2.x() + size2.x()) - (p1.x() - size1.x());
  } else {
    xInvEntry = (p2.x() + size2.x()) - (p1.x() - size1.x());
    xInvExit = (p2.x() - size2.x()) - (p1.x() + size1.x());
  };

  if (rel_vel.y() > 0.0) {
    yInvEntry = (p2.y() - size2.y()) - (p1.y() + size1.y());
    yInvExit = (p2.y() + size2.y()) - (p1.y() - size1.y());
  } else {
    yInvEntry = (p2.y() + size2.y()) - (p1.y() - size1.y());
    yInvExit = (p2.y() - size2.y()) - (p1.y() + size1.y());
  };

  var xEntry, xExit; // entry time
  var yEntry, yExit;

  // in case edge distance is 0, to avoid NaN.
  if (rel_vel.x() == 0.0) {
    xEntry = -Infinity;
    xExit = Infinity;
  } else {
    // DEVIATION TWO: NORMALIZED TIME
    xEntry = xInvEntry / rel_vel.x() / dt; // divide by amount of time in the frame
    xExit = xInvExit / rel_vel.x() / dt; // to know if it happens this frame
  };

  if (rel_vel.y() == 0.0) {
    yEntry = -Infinity;
    yExit = Infinity;
  } else {
    yEntry = yInvEntry / rel_vel.y() / dt;
    yExit = yInvExit / rel_vel.y() / dt;
  };

  // erliest collision time
  var entryTime = Math.max(xEntry, yEntry);
  var exitTime = Math.min(xExit, yExit);

  if (entryTime > exitTime ||
    (xEntry < 0.0 &&
      yEntry < 0.0) ||
    xEntry > 1.0 ||
    yEntry > 1.0) {
    // there's no collision
    return false;

  } else {
    // there's a collision
    var normalx = (xEntry < 1.0) && (xEntry >= yEntry) ? 1 : 0;
    if (rel_vel.x() > 0.0) normalx *= -1;
    var normaly = (yEntry < 1.0) && (yEntry >= xEntry) ? 1 : 0;
    if (rel_vel.y() > 0.0) normaly *= -1;
    var normal = V(normalx, normaly);

    var time = entryTime;
    var distance = (xEntry > yEntry) ? xInvEntry : yInvEntry;

    console.log(e1.name + ' collided with ' + e2.name);
    console.log('e1.pos' + String(e1.pos));
    console.log('e2.pos' + String(e2.pos));
    console.log('e1.hitbox' + String(e1.hitbox));
    console.log('e2.hitbox' + String(e2.hitbox));
    console.log('xEntry ' + xEntry);
    console.log('yEntry ' + yEntry);
    console.log('normal ' + normal);
    console.log('time ' + time);
    console.log('distance ' + distance);
    console.log('velocity ' + rel_vel);

    e1.collisions.push({
      against: e2,
      normal: normal,
      time: time,
      distance: distance,
      rel_vel: rel_vel,
    });

    return true;
  };
};

Thank you for your attention.

Answer 1

I asked just this question on SO a while ago, same language aswell, and no one didn't really care, so when I found the solution I didn't really bother to put it up there, but now more people are interested and I am glad for that, so now I will post the answer here.

Here's my original code, it's the exact same thing as yours, just a bit more clear of what it's about, since it checks for every axis in a loop (You can even add one more loop and boom, it's 3D if you want):

var fTime = 0;
var lTime = 1;
var oTime = new Vec();

for (var i = 0; i < 2; i++) {
    var d = "xy".charAt(i);

    if (vel[d] < 0) {
        if (bMax[d] < aMin[d]) return false;
        if (aMax[d] < bMin[d]) fTime = Math.max((aMax[d] - bMin[d]) / vel[d], fTime);
        if (bMax[d] > aMin[d]) {
            oTime[d] = (aMin[d] - bMax[d]) / vel[d];
            lTime = Math.min(oTime[d], lTime);
        }
    } else if (vel[d] > 0) {
        if (bMin[d] > aMax[d]) return false;
        if (bMax[d] < aMin[d]) fTime = Math.max((aMin[d] - bMax[d]) / vel[d], fTime);
        if (aMax[d] > bMin[d]) {
            oTime[d] = (aMax[d] - bMin[d]) / vel[d];
            lTime = Math.min(oTime[d], lTime);
        }
    }

    if (fTime > lTime) return false;
}

So, vel is the relative velocity (divided by dt), a/b Min/Max is the upper left / lower right bounds of each object, fTime is the first (entry) time, and lTime is the last (out) time of intersection.

EDIT: The oTime (o = overlap) might be a bit confusing for you, you can remove it if you want, but it's really good to have, because after that code, if you have the oTime, you can calculate the hit normal very easy, which is necessary in order for collision response, simply:

if (oTime.x > oTime.y) {
    hitNormal = new Vec(signum(v.x), 0);
} else {
    hitNormal = new Vec(0, signum(v.y));
}

Where signum is a function that simply looks like this:

function signum(x) {
    return x > 0 ? 1 : x < 0 ? -1 : 0;
}

Here's also a video of it: https://vid.me/FZwL

These ghost collisions occur when there is no velocity on for example the x axis, but there is velocity on one, the y axis in this case.

They occur because we know that there only is velocity on that axis, and therefore we only check that axis, there is one very easy and very good way to fix this.

This fix will only not fix this problem, but it will also improve the performance. So, what you want to do is this:

Let's say your checking collision between A (blue) and B (red), before you perform the sweep/continouos collision test to get the time of impact, check if they even can collide during that frame, to do so, wrap them into these green boxes, which are created by using the Math.min and Math.max of both A's and B's position (min and max corners) in this frame and in the next frame. If these green boxes intersect, do the sweep test, otherwise, just move on to the next two objects. This will not only fix the problem, but also as I said, improve the perfomance drastically, since you dont need to run unnecessary code.

This took me a while to figure out, but it's rather easy to implement and it works nice and smooth.

That article you found is good, but not really when it comes to collision response, which I think is horrible. I know it is very hard to find information about sweep testing, since only a few even know what it is, but if you get the concept, you can kinda play around with it and find your own solutions. There is almost no information about collision response for sweep testing either, which is kind of annoying, but you can ask me if you want.

Also I am quite curious what kind of project you need this is for, not many use sweep testing in their games/apps but I think people should, because it's much more accurate and smooth imo.