| 충돌 감지 Collision Detection | |
|---|---|
| 분야 | 게임 개발 × 컴퓨터 그래픽스 × 계산기하학 |
| 상위 개념 | 물리 엔진 |
| 2단계 구조 | Broad phase → Narrow phase |
| 대표 알고리즘 | AABB, 스위프 앤 프룬, BVH, GJK, SAT |
| 숙적 | 터널링(tunneling) |
1. 개요[편집]
개 물체의 충돌을 순진하게 검사하면 이다. 그래서 우리는 대부분의 검사를 안 하기 위해 온갖 꾀를 부린다.
충돌 감지(collision detection)는 시뮬레이션 공간에서 두 개 이상의 물체가 서로 겹치거나 접촉했는지를 판정하는 과정이다. 물리 엔진 파이프라인의 심장부로, 어느 물체 쌍이 부딪혔고 어디서 얼마나 파고들었는지를 알아내야 그 뒤의 충돌 응답(밀어내기, 튕기기)이 가능해진다. 말은 간단하지만, 수천 개의 물체가 매 프레임 돌아다니는 게임에서 이걸 16.6ms 안에 끝내는 것은 결코 만만치 않다.
가장 순진한 방법은 모든 물체 쌍을 하나하나 검사하는 것인데, 물체가 개면 번의 검사가 필요하다. 물체 1000개면 약 50만 번. 그래서 실제 엔진은 검사를 broad phase(광역)와 narrow phase(정밀)의 2단계로 쪼개, 명백히 안 부딪힌 쌍을 싸게 걸러낸 뒤 살아남은 소수의 후보에만 비싼 정밀 검사를 돌린다.
2. Broad Phase: 대충 빠르게 거르기[편집]
Broad phase의 목표는 “확실히 안 부딪힌” 쌍을 최대한 싸게 쳐내고, 부딪혔을 “가능성이 있는” 후보 쌍만 추려내는 것이다. 정밀도는 포기한다 — 여기서는 false positive(사실 안 부딪혔는데 후보로 넘김)는 괜찮지만 false negative(부딪혔는데 놓침)는 절대 안 된다.
- AABB (Axis-Aligned Bounding Box) — 물체를 축에 정렬된 상자로 감싼다. 두 AABB의 겹침 판정은 축별 구간 비교 여섯 번이면 끝나는, 어처구니없이 싼 연산이다. 대부분의 broad phase가 AABB 위에서 돈다.
- 스위프 앤 프룬 (Sweep and Prune) — 각 축에서 AABB의 시작·끝 좌표를 정렬해 두고, 구간이 겹치는 쌍만 추린다. 물체들이 프레임 간에 조금씩만 움직인다는 시간적 일관성(temporal coherence)을 활용해, 정렬을 거의 갱신만 하며 유지한다.
- BVH (Bounding Volume Hierarchy) — 바운딩 볼륨을 트리로 계층화한다. 상위 노드가 안 겹치면 그 아래 전체 서브트리를 통째로 건너뛴다. 레이 트레이싱에서도 똑같은 자료구조가 광선-삼각형 교차 가속에 쓰인다.
- 공간 해싱 (Spatial Hashing) — 공간을 균일한 격자 셀로 나누고 각 물체를 해당 셀에 등록한다. 같은 셀(또는 이웃 셀)에 든 물체끼리만 검사하면 되므로, 물체가 공간에 고르게 퍼진 경우 특히 효율적이다.
3. Narrow Phase: 정밀하게 판정하기[편집]
Broad phase가 넘긴 후보 쌍에 대해, 실제로 겹쳤는지·어디서 겹쳤는지·얼마나 파고들었는지(침투 깊이와 접촉 법선)를 정밀하게 계산하는 단계다. 여기서 나오는 정보가 그대로 충돌 응답의 입력이 된다.
3.1. 볼록 vs 오목[편집]
Narrow phase 알고리즘의 대전제는 물체가 볼록(convex)하다는 것이다. 볼록 물체끼리는 강력하고 우아한 판정법이 존재하지만, 오목(concave) 물체는 다르다. 오목 형상은 대개 여러 개의 볼록 조각으로 분해(convex decomposition)하거나, 삼각형 메시로 취급해 조각마다 검사한다. “왜 내 캐릭터가 도넛 구멍을 통과 못 하지?”의 배후에는 십중팔구 볼록 근사가 있다.
3.2. GJK와 SAT[편집]
두 볼록 물체의 교차 판정에는 두 알고리즘이 쌍벽을 이룬다.
- GJK (Gilbert-Johnson-Keerthi) — 두 물체의 민코프스키 차(Minkowski difference)가 원점을 포함하는지를 검사한다. 원점을 포함하면 두 물체는 겹친 것. 실제 형상을 구성하지 않고 서포트 함수(support function)만으로 반복 접근하는 방식이라, 임의의 볼록 형상에 우아하게 일반화된다. 침투 깊이는 후속 알고리즘 EPA(Expanding Polytope Algorithm)로 뽑는다.
- SAT (Separating Axis Theorem) — “두 볼록 물체가 안 겹친다면, 둘을 완전히 갈라놓는 축이 반드시 하나 존재한다”는 정리에 기댄다. 후보 축(각 면의 법선, 모서리 외적)에 물체를 투영해, 투영 구간이 벌어지는 축이 하나라도 있으면 안 겹친 것이다. 다면체·박스 판정에서 직관적이고 빠르다.
4. 연속 충돌 감지와 터널링[편집]
지금까지의 이야기는 매 프레임 “현재 위치의 스냅샷”만 검사하는 이산 충돌 감지(Discrete Collision Detection)다. 여기엔 치명적 함정이 있다 — 터널링(tunneling).
빠르게 날아가는 총알이 얇은 벽을 만났다고 하자. 이번 프레임엔 총알이 벽 앞에 있고, 다음 프레임엔 이미 벽 뒤에 가 있다. 두 스냅샷 어디에서도 총알과 벽은 겹치지 않으므로, 이산 검사는 총알이 벽을 그냥 통과했다고 판정한다.1 플레이어 눈에는 총알이 벽을 뚫고 지나간 것으로 보인다.
이를 막는 것이 연속 충돌 감지(Continuous Collision Detection, CCD)다. CCD는 스냅샷이 아니라 이전 프레임과 현재 프레임 사이의 이동 경로 전체를 훑어(sweep) 그 사이에 벽과 만나는 최초 시각(time of impact, TOI)을 찾는다. 개념적으로는 물체를 시간축으로 쓸어 만든 형상과 장애물의 교차를 푸는 문제다.
CCD는 정답이지만 공짜가 아니다. 그래서 대부분의 엔진은 총알·발사체처럼 빠른 물체에만 CCD를 켜고, 느릿느릿한 상자들에는 값싼 이산 검사를 쓰는 선택적 CCD로 타협한다.
5. 접촉 매니폴드와 충돌 응답[편집]
Narrow phase가 “겹쳤다”고 판정하면, 그다음은 어떻게 접촉하고 있는가를 기술해야 한다. 두 물체가 한 점에서 만나는 경우는 드물고, 상자가 바닥에 놓이면 면과 면이 닿아 여러 접촉점이 생긴다. 이 접촉점들의 집합과 공통 법선을 접촉 매니폴드(contact manifold)라 부른다. 안정적인 매니폴드가 없으면 바닥에 놓인 상자가 한 점으로 지탱되다 덜덜 떨거나(jitter) 쓰러진다.
이 매니폴드가 물리 엔진의 제약 해결기로 넘어가면 충돌 응답이 시작된다. 침투 깊이만큼 물체를 밀어내고, 접촉 법선 방향으로 임펄스를 가해 튕겨내며, 마찰을 접선 방향 임펄스로 처리한다. 즉 충돌 감지는 “부딪혔다”를 알려주고, 충돌 응답은 “그래서 어떻게 반응할까”를 결정하는, 한 몸의 두 얼굴인 셈이다.