겹쳤는지 어떻게 아는가

한 줄 요약

충돌 감지는 두 단계로 나뉩니다. 넓은 단계에서 "겹칠 수도 없는" 쌍을 싸게 걸러 내고, 좁은 단계에서 남은 쌍만 정확히 판정합니다. 볼록 도형의 정확한 판정은 분리축 정리 하나로 끝납니다.

왜 이게 필요했나

물체가 n 개면 쌍은 n(n-1)/2 개입니다. 200개면 19,900 쌍이고 2,000개면 200만 쌍입니다. 매 걸음마다 이것을 전부 정밀하게 검사하면 물리 계산이 시작되기도 전에 프레임이 끝납니다.

그런데 실제로 겹치는 쌍은 대개 아주 적습니다. 위의 200개 예에서 실제로 겹치는 쌍은 300개가 안 됩니다. 나머지 19,600 쌍은 "굳이 정밀하게 볼 필요가 없다" 는 것을 훨씬 싸게 알 수 있습니다. 이 구조가 넓은 단계와 좁은 단계로 나뉜 이유입니다.

어떻게 동작하나

AABB(축 정렬 경계 상자) 는 가장 싼 판정입니다. 상자 두 개가 겹치는지는 축마다 구간이 겹치는지만 보면 됩니다.

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

축마다 한 번씩, 비교 네 번이면 끝납니다. 겹침의 깊이도 같은 식에서 나옵니다. 축별로 min(maxs) - max(mins) 가 그 축의 겹침 폭이고, 더 얕은 축이 실제로 밀어낼 방향입니다.

원과 구는 그다음으로 쌉니다. 중심 사이 거리가 반지름의 합보다 작으면 겹친 것이고, 법선은 중심을 잇는 방향, 파고든 깊이는 r1 + r2 - 거리 입니다. 여기서 조심할 것은 두 중심이 정확히 같을 때입니다. 거리가 0 이면 방향을 정할 수 없으므로 임의의 방향을 정해 주어야 하고, 그러지 않으면 0으로 나누기가 납니다.

분리축 정리(SAT) 는 볼록 도형 일반에 쓰는 방법입니다. 두 볼록 도형이 겹치지 않는다면, 두 도형을 완전히 갈라 놓는 직선이 반드시 존재합니다. 그리고 그 직선의 방향은 두 도형의 변 중 하나와 나란합니다. 그래서 각 변의 법선 방향으로 두 도형을 투영해 구간이 떨어지는 축을 하나라도 찾으면 겹치지 않은 것입니다.

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

떨어지는 축을 못 찾으면 겹친 것이고, 이때 가장 작은 겹침을 준 축이 가장 짧게 밀어내는 방향입니다. 이것을 최소 이동 벡터(MTV)라고 하고, 다음 모듈의 충돌 반응이 이 방향을 씁니다.

넓은 단계의 고전적인 방법은 정렬과 훑기(sweep and prune)입니다. 상자들을 x 축의 최솟값으로 정렬해 두면, 어떤 상자와 겹칠 수 있는 상자는 정렬 순서에서 뒤에 이어지는 것 중 minx 가 이 상자의 maxx 를 넘지 않는 것들뿐입니다. 그 지점에서 멈추면 됩니다.

넓은 단계에는 정렬-훑기 말고도 몇 가지가 더 있습니다. 격자(spatial hash) 는 공간을 일정한 크기의 칸으로 나누고 각 물체를 자기가 걸친 칸에 등록해 두는 방법입니다. 물체 크기가 고만고만하고 고르게 퍼져 있을 때 가장 빠릅니다. 동적 경계 상자 트리(dynamic AABB tree) 는 상자들을 이진 트리로 묶어 두고 가지 단위로 건너뛰는 방법이라, 크기 차이가 큰 물체가 섞여 있어도 잘 버팁니다. Box2D 와 Bullet 이 이 트리를 씁니다.

어느 방법이든 공통점이 하나 있습니다. 넓은 단계는 실제로 겹치는 쌍을 절대 놓치면 안 되지만, 겹치지 않는 쌍을 넘겨주는 것은 괜찮다는 것입니다. 놓치면 물체가 서로 통과하지만, 여분을 넘기면 좁은 단계가 걸러 내 줄 뿐 결과는 같습니다. 그래서 넓은 단계의 판정은 언제나 넉넉한 쪽으로 만듭니다.

현장에서 만나는 모습

빠른 물체가 얇은 벽을 통과하는 문제(터널링)는 감지의 한계에서 옵니다. 걸음의 시작과 끝에서만 겹침을 보기 때문에, 한 걸음 안에 벽을 완전히 지나가 버리면 어느 시점에도 겹침이 없습니다. 해법은 이동 경로를 훑는 연속 충돌 감지이거나, 걸음을 잘게 쪼개는 것입니다.

또 하나는 경계값의 일관성입니다. 정확히 맞닿은 경우를 겹침으로 볼지 아닐지를 코드 여러 곳에서 다르게 정하면, 상자가 바닥에 닿았다 떨어졌다를 반복하며 떨립니다. 판정 규칙은 한 곳에 두고 모두가 그것을 부르게 해야 합니다.

마지막으로 좁은 단계의 출력이 무엇이어야 하는지를 정해 두는 것이 중요합니다. 겹쳤다는 참·거짓만으로는 다음 단계가 아무것도 할 수 없습니다. 충돌 반응이 필요로 하는 것은 셋입니다 — 밀어낼 방향(법선), 얼마나 파고들었는지(깊이), 그리고 어디서 닿았는지(접촉점)입니다. 이 실습은 앞의 둘까지 만들고 접촉점은 다루지 않는데, 접촉점은 회전을 계산할 때 필요하고 그것만으로도 별도의 주제가 되기 때문입니다.

다음 실습에서 할 것

AABB, 원, 분리축 정리를 차례로 만들고, 겹친 두 다각형과 최소 이동 벡터를 그림으로 그립니다. 그다음 상자 200개에 대해 전수 검사와 정렬-훑기를 각각 돌려 같은 결과를 훨씬 적은 검사로 얻는 것을 숫자로 확인하고, 마지막에는 광선과 상자의 교차를 슬랩 방법으로 풀어 그림에 그립니다.