How Do You Know They Overlap

In one line

Collision detection is split into two phases. The broad phase cheaply filters out pairs that "cannot even overlap", and the narrow phase judges only the remaining pairs exactly. Exact judgment for convex shapes comes down to a single theorem, the separating axis theorem.

Why this was needed

With n objects, there are n(n-1)/2 pairs. 200 objects make 19,900 pairs, and 2,000 objects make 2 million pairs. If you check all of them precisely at every step, the frame is over before physics even starts.

Yet the pairs that actually overlap are usually very few. In the 200-object example above, fewer than 300 pairs actually overlap. For the other 19,600 pairs, you can learn much more cheaply that "there is no need to look precisely". This is why the structure is split into a broad phase and a narrow phase.

How it works

AABB (axis-aligned bounding box) is the cheapest test. Whether two boxes overlap is decided by looking only at whether the intervals overlap on each axis.

겹친다  ⟺  a.maxx >= b.minx  그리고  b.maxx >= a.minx
           그리고  a.maxy >= b.miny  그리고  b.maxy >= a.miny

One check per axis, four comparisons, and you are done. The depth of the overlap comes from the same expression. Per axis, min(maxs) - max(mins) is the overlap width on that axis, and the shallower axis is the direction you would actually push out along.

Circles and spheres are the next cheapest. If the distance between the centers is less than the sum of the radii, they overlap; the normal is the direction joining the centers, and the penetration depth is r1 + r2 - 거리 (the placeholder is the distance). The thing to watch out for here is when the two centers are exactly the same. If the distance is 0, the direction cannot be determined, so you must pick an arbitrary direction, or you get a division by zero.

The separating axis theorem (SAT) is the method used for convex shapes in general. If two convex shapes do not overlap, there must exist a line that separates them completely. And the direction of that line is parallel to one of the edges of the two shapes. So if you project the two shapes along the normal direction of each edge and find even one axis where the intervals are apart, they do not overlap.

for 축 in A의 변 법선들 + B의 변 법선들:
    A 를 축에 투영 → [a0, a1]
    B 를 축에 투영 → [b0, b1]
    겹침 = min(a1, b1) - max(a0, b0)
    if 겹침 <= 0: 떨어져 있다 (여기서 즉시 끝낸다)
    가장 작은 겹침과 그 축을 기억해 둔다

If you cannot find a separating axis, they overlap, and then the axis that gave the smallest overlap is the direction that pushes them apart the shortest distance. This is called the minimum translation vector (MTV), and the collision response in the next module uses this direction.

The classic method for the broad phase is sweep and prune. If you sort the boxes by their minimum on the x axis, the boxes that can overlap a given box are only those following it in sorted order whose minx does not exceed this box's maxx. You just stop at that point.

The broad phase has a few more methods besides sweep and prune. A grid (spatial hash) divides space into cells of a fixed size and registers each object in the cells it spans. It is fastest when objects are of similar size and spread evenly. A dynamic AABB tree groups the boxes into a binary tree and skips branch by branch, so it holds up well even when objects of very different sizes are mixed. Box2D and Bullet use this tree.

All of these methods share one thing. The broad phase must never miss a pair that actually overlaps, but passing on pairs that do not overlap is fine. If it misses one, objects pass through each other, but if it passes on extras, the narrow phase just filters them out and the result is the same. That is why the broad phase's test is always made generous.

What it looks like in the field

The problem of a fast object passing through a thin wall (tunneling) comes from a limit of detection. Because overlap is checked only at the start and end of a step, if the object passes completely through the wall within one step, there is no overlap at any moment. The fix is continuous collision detection that sweeps the movement path, or cutting the steps into smaller pieces.

Another is consistency of boundary values. If you decide in several places in the code differently whether exactly touching counts as overlap, a box repeats touching and leaving the floor and jitters. Put the test rule in one place and have everyone call it.

Finally, it is important to decide what the narrow phase's output should be. A true or false for "overlapped" alone gives the next stage nothing to work with. What the collision response needs is three things — the direction to push apart (the normal), how deep the penetration is (the depth), and where they touched (the contact point). This lab builds the first two and does not cover the contact point, because the contact point is needed when computing rotation, and that by itself is a separate topic.

What you will do in the next lab

You build AABB, circles and the separating axis theorem in turn, and draw two overlapping polygons and the minimum translation vector in a picture. Next, you run a brute-force check and sweep and prune on 200 boxes and confirm in numbers that you get the same result with far fewer checks, and finally you solve the intersection of a ray and a box with the slab method and draw it in a picture.