Four Ways to Find an Overlap

Goal

Judge overlap with AABB, circles and the separating axis theorem, reduce the number of checks with a broad phase, and solve the intersection of a ray and a box. When this lab is done, you can build the collision detection layer of a physics engine yourself.

Why it matters

With 200 objects there are 19,900 pairs. If you do a precise test on all of them, the frame is over before physics even starts. Yet fewer than 300 pairs actually overlap. That is why collision detection is split into two layers — a broad phase that very cheaply filters out pairs that cannot even overlap, and a narrow phase that looks exactly at the remaining pairs.

The general solution for the narrow phase is the separating axis theorem. If two convex shapes are apart, a line that separates them must exist, and its direction is parallel to one of the edges of the two shapes. So you only need to project along the edge normal directions. And when they overlap, the axis that gave the smallest overlap is the direction that pushes them apart the shortest distance, so detection and response come from the same computation.

Steps

Put the toolbox in /root/collide.
/root/collide/aabb.py — axis-aligned bounding box.
/root/collide/circle.py — circle and circle.
/root/collide/sat.py — separating axis theorem.
/root/collide/out/sat.png — the overlapping shapes and the minimum translation vector.
/root/collide/boxes.txt and /root/collide/out/06-broad.txt — brute-force check versus sweep and prune.
/root/collide/ray.py and /root/collide/out/07-ray.txt, ray.png — a ray and a box.

Notes

Start a server with nohup python3 -m http.server 8080 -d /root/collide/out & and open http://localhost:8080/ in the Web preview.
Keep your functions inside /root/collide. The grader puts that folder on the import path and calls them directly.
Common mistake 1: the broad phase giving a different answer from the narrow phase. The broad phase does not change the answer; it gets the same answer cheaply, so if the number of pairs differs, the break condition is wrong.
Common mistake 2: leaving out the 0 in max(tmin, 0) in the ray test. Then a box behind the ray is reported as hit too.

Put the drawing toolbox in place

Save /root/collide/gfxlib.py exactly as in the example, and use /root/collide/check.py to draw a test pattern and make /root/collide/out/00-check.png. The pattern is a 64x64 black background with a white (255,255,255) diagonal line from (0,0) to (63,63), and over it a red (255,0,0) horizontal line from (0,32) to (63,32).

From this lab on, you do not rebuild the PNG encoder. We hand you the same code you built by hand in the first lab as a tool — because file formats are not what you learn here.

The lab Pod has no volume, so the files you made in the previous lab are not kept. That is why each lab starts by putting the toolbox in place again.

Create Canvas(w, h, bg), draw the two lines with line(x0, y0, x1, y1, rgb), and then save with write_png(path). Draw the horizontal line later, so that the intersection (32,32) becomes red.

In this lab you use it to draw the overlapping shapes and the minimum translation vector.

Axis-aligned bounding box

In /root/collide/aabb.py, make overlap(a, b) and penetration(a, b). A box is four real numbers (minx, miny, maxx, maxy), and the case where the boundaries exactly touch also counts as overlap. penetration returns the per-axis overlap width (dx, dy) if they overlap and (0.0, 0.0) if they do not.

It is much shorter to write the non-overlap condition first.

not (a[2] < b[0] or b[2] < a[0] or a[3] < b[1] or b[3] < a[1])

Whether to put an equals sign in the inequality is itself the decision for the "touching case". This lab treats touching as overlap, so you drop the equals sign as in the expression above.

The overlap width is min(a[2], b[2]) - max(a[0], b[0]). It is the one of the two right edges that is further left, minus the one of the two left edges that is further right.

Keep the test rule in only one place. If you decide it differently in several places, the box jitters on and off the floor.

Circle and circle

In /root/collide/circle.py, make circle_hit(c1, r1, c2, r2). Treat them as overlapping only when the distance between the centers is less than the sum of the radii and return (True, 법선, 깊이) (the placeholders are the normal and the depth), and otherwise return (False, (0.0, 0.0), 0.0). The normal is the unit vector pointing from 1 to 2, and the depth is r1 + r2 - 거리 (the placeholder is the distance). If the two centers are exactly the same, set the normal to (1.0, 0.0).

If you do not handle the case where the distance is 0 separately, you get a division by zero. Two objects being born in exactly the same place happens more often than you might think — it happens when you create them all at once from a spawner.

If you only needed to compare, you could avoid the square root, but here you have to find the depth, so you need the actual distance.

It is important to fix the direction of the normal as from 1 to 2. The impulse calculation in the next module uses this convention as is. If you reverse it, the objects pull each other together.

Separating axis theorem

In /root/collide/sat.py, make sat_hit(a, b). a and b are convex polygons written counterclockwise (lists of vertices), and it returns (True, 축, 깊이) (the placeholders are the axis and the depth) if they overlap and (False, (0.0,0.0), 0.0) if not. The axis is the one with the smallest overlap among all the edge normals of both shapes, with its sign set so that it points from a's centroid to b's centroid.

The normal of edge (x0,y0) -> (x1,y1) is (ey, -ex) normalized (ex = x1-x0, ey = y1-y0).

The overlap on one axis is min(a1, b1) - max(a0, b0), and if this value is 0 or less, that axis separates the two shapes, so you can finish immediately. You do not need to look at the remaining axes.

The reason you set the sign of the axis at the end is that, depending on which shape the edge normal belongs to, the direction can come out opposite. If dot(축, 무게중심b - 무게중심a) < 0, flip it (the placeholders are the axis and the two centroids).

If two squares are 1.5 apart in the x direction, the axis should be (1,0) and the depth 0.5.

Draw the overlap and the direction to push out

Use /root/collide/draw.py to make /root/collide/out/sat.png (256x256, black background). Draw polygon A, [(-1,-1),(1,-1),(1,1),(-1,1)], with a white (255,255,255) outline, and B, which is A shifted by (1.5, 0.5), with a yellow (255,220,60) outline, and draw the minimum translation vector that extends from B's centroid by 축 * 깊이 (the placeholders are the axis and the depth) as a red (255,60,60) line. The screen coordinates are sx = 128 + 40*x and sy = 128 - 40*y.

A polygon outline is the line segments that join the vertices in order and return from the last to the first point. Use the line of gfxlib.Canvas.

The minimum translation vector is the axis returned by sat_hit(A, B) multiplied by the depth. If you push B by this much, the two shapes separate exactly — that is what "minimum" means.

The drawing order is A, B, the arrow. Where they overlap, whatever is drawn later wins.

In the picture you can see the two squares overlapping only slightly in the x direction and the arrow pointing right. The reason x is chosen even though the y overlap is deeper is that it is "the direction that pushes out the shortest distance".

Sort first and then sweep

If you save /root/collide/gen_boxes.py exactly as in the example and run it, 200 boxes are created in /root/collide/boxes.txt. On those boxes, run a brute-force check and sweep and prune, and write four lines to /root/collide/out/06-broad.txt: pairs_brute=, pairs_sweep=, checks_brute= and checks_sweep=.

The brute-force check looks at every pair with i < j, and the number of checks is 200*199/2 = 19,900.

Sweep and prune works like this. If you sort the boxes by minx, the ones that can overlap a given box are only those following it in sorted order whose minx does not exceed this box's maxx. break the inner loop at that point.

checks_sweep is the number of times the overlap test was actually called in the inner loop (do not count the ones you exited with break).

The number of pairs found by the two methods must be exactly the same. The broad phase does not change the answer; it gets the same answer cheaply. If they differ, the break condition is wrong.

A ray and a box — the slab method

In /root/collide/ray.py, make ray_aabb(o, d, box), shoot five rays at the box (-1,-1,1,1), and write the results to /root/collide/out/07-ray.txt as five lines in the form r1=hit,t or r1=miss,0.000000. Then, on /root/collide/out/ray.png (256x256), draw the box in white, the rays that hit in green (60,255,120) up to the hit point, and the rays that missed in red (255,80,80) for a length of 6. The screen coordinates are sx = 128 + 30*x and sy = 128 - 30*y. The rays, in order, are o=(-3,0) d=(1,0), o=(-3,3) d=(1,0), o=(0,0) d=(1,0), o=(-3,-3) d=(0.7071067811865476, 0.7071067811865476) and o=(3,0) d=(1,0).

The slab method finds, for each axis, the interval [t1, t2] in which the ray is between the two planes of that axis, and narrows down by intersecting the intervals of all the axes.

t1 = (box.min - o) / d      # 방향이 음수면 t1 과 t2 가 뒤바뀐다
t2 = (box.max - o) / d
tmin = max(tmin, min(t1, t2))
tmax = min(tmax, max(t1, t2))

If a direction component is 0, the division blows up. In that case, only check whether the origin is inside that axis's interval, and if it is outside, it is a miss.

The final test is tmax >= max(tmin, 0). The reason for putting in 0 is that the ray does not extend backward. If you leave this out, a box behind the ray is reported as hit too. The fifth ray is exactly that case.

If the ray's starting point is inside the box, t is 0 (the third ray).