AABB Collision

Before an engine can push two bodies apart it has to know whether they overlap, which way to push, and how far. After this lesson your program will answer all three for pairs of axis-aligned boxes and pairs of circles, producing the contact a solver needs: a normal and a penetration depth.

Axis-aligned boxes

An AABB (axis-aligned bounding box) is a rectangle whose sides are parallel to the x and y axes. Two numbers per axis describe it, either as corners (min, max) or as a centre plus half-extents (c, h), where h = (max - min) / 2 and c = (min + max) / 2. The two forms carry the same information. Corners are handy for the yes/no test, centre and half-extents are handy for depth.

Do they overlap?

Two boxes overlap exactly when their shadows overlap on both axes. On one axis, intervals [a0, a1] and [b0, b1] overlap when a1 >= b0 and a0 <= b1. If either axis has a gap, the boxes are apart, however close they look on the other axis. In this course boxes that merely touch (depth 0) count as a contact.

How deep, and which way?

Pushing the boxes apart along one axis separates them. The cheapest push is along the axis where they overlap least. That push is the minimum translation vector (MTV): a unit normal n (pointing from A to B) and a depth d. Moving B by d * n ends the overlap.

On each axis, with centres ca, cb and half-extents ha, hb:

overlap = ha + hb - |cb - ca|

If the overlap is negative on either axis there is no contact. Otherwise choose the axis with the smaller overlap (the x axis on a tie); the normal points along that axis toward B, so its sign is the sign of cb - ca (use +1 when the centres coincide).

Why not use the overlap of the intervals, min(a1, b1) - max(a0, b0)? Because it is wrong when one box sits inside the other. Take A spanning 0 to 12 on x and B spanning 5 to 7. The intervals overlap by 2, yet to get B completely out of A on the right you must move it by 7, so that its left edge reaches 12. The half-extent form gives 6 + 1 - 0 = 7. This is the number a real solver needs.

Worked trace: A = (0,0)-(6,4), B = (5,1)-(9,9). A has centre (3,2) and half-extents (3,2); B has centre (7,5) and half-extents (2,4).

x: 3 + 2 - |7 - 3| = 1
y: 2 + 4 - |5 - 2| = 3

The x overlap is smaller, B lies to the right, so the contact is normal (1, 0) with depth 1. Pushing B one unit right leaves the boxes just touching.

Circles

Two circles overlap when the distance between their centres is at most the sum of their radii. Compare squared distances to skip the square root: with d = cb - ca and r = ra + rb, there is no contact when |d|^2 > r^2. If there is contact, the normal is d / |d| (from A to B) and the depth is r - |d|. Worked trace: radii 2 and 3, centres (1, 1) and (1, 5). Then d = (0, 4) and r = 5; 16 <= 25, so they touch, the normal is (0, 1) and the depth is 5 - 4 = 1.

When the centres coincide |d| = 0 and the direction is undefined. Pick any fixed normal, (1, 0) here, and use depth r. Dividing by zero would put nan into every body that touches.

A circle against a box uses the same idea with one extra step: clamp the circle's centre into the box to find the closest point on the box, then treat that point like a circle of radius 0. You will meet it again in the narrow-phase lesson.

Common mistakes

• Using the interval overlap min(a1, b1) - max(a0, b0) for depth. It under-reports containment.
• Choosing the axis with the larger overlap, which shoves bodies a long way sideways.
• Testing only one axis, or combining the axis tests with OR instead of AND.
• Forgetting the concentric-circles case and dividing by a zero distance.
• Taking the square root before comparing, then comparing against r with rounding noise; compare |d|^2 with r^2.

Your exercise

The starter parses the commands and prints the contact; you write box_hit and circle_hit, each returning either "no contact" or a normal and a depth. The most likely mistake is the depth of a box that is contained in another.