한양과기고 에듀테크 수업도구 대시보드

충돌 감지 (Collision Detection)

게임·물리 엔진은 매 프레임마다 "두 물체가 겹쳤는가?"를 수없이 판정한다. 모양을 단순하게 볼수록 판정은 빨라진다 — 축 정렬 사각형(AABB)은 부등식 4개, 원은 거리 비교 1번. 하지만 회전한 도형은 이 방법으로 못 잡는다. 임의의 볼록 다각형은 분리축 정리(SAT, Separating Axis Theorem)로 정확히 판정한다: 두 볼록 도형이 겹치지 않으면, 둘을 완전히 갈라놓는 직선(축)이 반드시 하나 존재한다. 그 축은 각 도형의 변에 수직인 방향들 중에 있다. 아래에서 도형을 끌어 보며 확인하자.

1. 도형을 드래그해 겹쳐 보기

■ 도형 A · ■ 도형 B · 초록 테두리 = 분리됨 · 빨강 테두리 = 충돌 · 도형 중앙을 잡고 드래그, 회전 버튼으로 돌려서 SAT의 위력을 확인하세요.

모드를 고르고 도형을 움직여 보세요.

2. 단계별로 비싸지는 판정

AABB — O(1), 부등식 4개

A.minX ≤ B.maxX 그리고 B.minX ≤ A.maxX (x축), y축도 동일. 네 조건이 모두 참이면 겹침. 가장 빠르지만 회전 불가, 도형이 헐렁하게 감싸진다.

원 — O(1), 거리 1번

중심 거리의 제곱 (dx²+dy²) 를 (r₁+r₂)² 와 비교. 제곱근을 피해 더 빠르다. 회전에 영향받지 않아 캐릭터 히트박스로 자주 쓰인다.

SAT — O(n+m) 축, 정확

두 볼록 다각형의 모든 변 법선을 축으로, 각 축에 두 도형을 투영해 구간 겹침을 검사. 한 축이라도 분리되면 조기 종료. 겹침 최소 축 × 겹침량 = MTV(밀어낼 벡터).

브로드 페이즈 → 내로 페이즈

물체가 많으면 먼저 AABB·공간 분할(쿼드트리·격자)로 후보 쌍을 추린 뒤(브로드), 살아남은 쌍만 SAT 같은 정밀 검사(내로)를 돌려 비용을 아낀다.

3. SAT 구현 (2D 볼록 다각형)

def axes(poly):                       # 각 변에 수직인 단위벡터(법선)
    out = []
    for i in range(len(poly)):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % len(poly)]
        ex, ey = x2 - x1, y2 - y1        # 변 벡터
        nx, ny = -ey, ex                 # 90도 회전 → 법선
        L = (nx * nx + ny * ny) ** 0.5
        out.append((nx / L, ny / L))
    return out

def project(poly, ax):                  # 축에 정사영한 [min, max] 구간
    ds = [px * ax[0] + py * ax[1] for px, py in poly]
    return min(ds), max(ds)

def sat(A, B):
    push = None; best = float("inf")
    for ax in axes(A) + axes(B):
        amin, amax = project(A, ax)
        bmin, bmax = project(B, ax)
        overlap = min(amax, bmax) - max(amin, bmin)
        if overlap <= 0:
            return False, None            # 분리축 발견 → 즉시 종료
        if overlap < best:
            best = overlap; push = ax
    # 모든 축에서 겹침 → 충돌. best 만큼 push 방향으로 밀면 분리됨
    return True, (push[0] * best, push[1] * best)

SAT는 볼록(convex) 도형에서만 성립한다. 오목 도형은 여러 개의 볼록 조각으로 나누거나(볼록 분해), GJK·민코프스키 차 같은 다른 알고리즘을 쓴다. 원 대 다각형은 "가장 가까운 꼭짓점 방향"을 축에 추가한다.