AABB test does not consistently detect edge-to-edge contact when bounds are very different in size

Question

My function compares two AABBs for collision detection, and when they are around the same size it works fine, but I noticed that if I greatly decreased the size of one of them (or augmented the size of the other), then the collision wouldn't be detected correctly; I would have to have them intersect for a collision to be registered, rather than having it register when they are at least in direct contact, which is the intended behavior.

Below is my code:

local function DetectCollision(a, b) -- AABB to AABB
  local collisionX = (a.Position.X + a.Size.X) >= b.Position.X and (b.Position.X + b.Size.X) >= a.Position.X
  local collisionY = (a.Position.Y + a.Size.Y) >= b.Position.Y and (b.Position.Y + b.Size.Y) >= a.Position.Y
  local collisionZ = (a.Position.Z + a.Size.Z) >= b.Position.Z and (b.Position.Z + b.Size.Z) >= a.Position.Z
  return collisionX and collisionY and collisionZ
end

---

To be more specific, the issues start to occur when I cut the size of one of the AABBs in half. For instance, if I had two cubes where one's size is 12 on all axes and the other is 6 on all axes, then the collision will not register. Upon debugging, I noticed that only one of the collision bools will become false. This seems to depend on what axis the smaller bounding box moves from in relation to the bigger one, so if I moved the smaller AABB away from the bigger one on the y-axis, then collisionY will be false.

Answer 1

This sounds like floating point precision error when testing for exact equality.

Let's model this in decimal to make it easier to read. Let's say we're using a decimal floating point format with room for 4 digits.

We place our cube B so its left edge is at -9.008.

Next we place our cube A, 10 units in size, so that its right edge just touches B, meaning its left edge is at -19.008. This takes 5 significant digits to represent though, so our number format will round it to the closest value representable with 4 digits, -19.01.

Now when we try to do our collision test:

positionA + sizeA >= positionB ?
-19.01 + 10 = -9.010 < -9.008

We fail the >= test, because the rounded sum is less than what we'd have gotten if we could store the position with perfect precision throughout.

Note that this is actually the correct result if we take the positions stored in the variables to be the "ground truth" — it's true that a size-10 cube at -19.01 doesn't collide with one at -9.008, so the floating point math & collision check is giving us the right answer, it's just that we asked it about a different position than we meant to.

By arranging the math this way, we effectively said that the position is accurate and un-rounded, and can be trusted to have full precision as-is. But that's not the general case — most places our objects end up will not be exactly representable as floating point numbers, and we'll be rounding all the time. So we can build some awareness of rounding into the way we structure our test.

One way we can tame floating point rounding is to avoid summing wildly different values (like repeatedly adding a tiny frame delta time to a large total time counter).

Here, position and size measure very different things, and I could have a size-1 cube located at position 10000, or a size-100 cube located at 0.00001, huge gulfs in magnitude. So their sum or difference won't necessarily reflect the precision of either.

But two objects that collide will usually be close-ish together, so we can trust their positions to be in similar ranges of magnitude, and the difference between them will tell us something about the precision we have in that neighborhood. By subtracting one position from the other, we get an offset that more accurately represents the position precision we actually have available in the numeric range where our collision is occurring.

So we can rearrange our test like so:

 offset = b.Position - a.Position

 if( offset.x <= a.sizeX and offset.x >= -b.sizeX)
 ...(etc)

Using this form, our comparison looks like:

 offset = -9.008 - (-19.01)
 offset = 10.002
 (rounds to)
 offset = 10

 offset <= size
 10  <= 10
 passes the test!

This version of the collision test gets a little extra tolerance zone for rounding as we move further from the origin, to account for the fact that exact kissing contacts might not be representable numbers in those ranges.

Of course, we don't want to push this so far that this extra "collision skin thickness" becomes visible to the player, so you'll usually want to keep your physics happening no more than a few thousand units from the origin of your physics world, and re-position that origin as needed to avoid truly huge offsets that sacrifice too much precision for magnitude.