물리 엔진 궁금증 4 - 충돌 검출

발생

이번에는 충돌에 대해 알아보았다.

충돌을 처리하기 위한 과정 3가지

충돌을 처리하기 위해선 3가지 과정이 필요하다 그 과정은 아래와 같다.

  1. 충돌 검출 (Collision Detection)
  2. 접촉 생성 (Contact generation, manifold)
  3. 충돌 응답 (Collision Response)

각 과정들은 최적화된 알고리즘으로 구현을 하게되고 하나하나 이론적인 배경이 없다면 이해가 힘들것이다. 내가 그랬기 때문이다.

충돌 검출 (Collision Detection)

충돌 검출도 과정이 나눠진다. 두 가지로 나눠지며 각 단계는 아래와 같다.

  1. Broad Phase -> 충돌 후보 추림
  2. Narrow Phase -> 실제 충돌 판정

두 단계로 나눠진 이유에 대해 찾아보니 초창기에는 충돌 처리를 할 요소의 양 자체가 적어서 모든 요소 전체에 대해 브루트 포스로 충돌 연산을 진행했었다. 그러나 이후 한 프로그램에서 처리해야 할 요소들의 절대적인 양이 많아졌고 요소 전체를 검사하는 브루트 포스로는 시간 복잡도가 $O(n^2)$ 인 상태가 되어버린다.

실시간 시뮬레이션을 위해서는 최소한의 연산으로 충돌 검출을 할 수 있어야 했고 이를 해결하기 위한 방법으로 충돌이 일어날 확률이 있는 요소들만 추려 그 요소들만 실제 충돌 연산을 진행하는 아이디어가 나오게 되었다.

앞선 과정들을 통해 충돌 검출은 Broad Phase와 Narrow Phase 두 단계로 처리하는 방법이 보편화 되었고 두 단계로 충돌 검출을 연산하여 시간 복잡도를 $O(n \log n)$ 상태까지 만들 수 있게 되었다.

Broad Phase

충돌 후보를 추리는 단계이다.

이 Broad Phase 에 대해 알기 위해선 우선 AABB에 대해 알아야 한다. 링크를 클릭해서 알아보고 오는걸 추천한다. AABB 란?

이 단계에서 사용되는 주요 알고리즘들은 아래와 같다.

  1. Uniform Grid (Spatial Hashing)
    • 공간을 격자(grid)로 나누고 각 물체의 AABB가 걸치는 셀에 등록
    • 같은 셀 또는 인접 셀에 속한 물체들만 충돌 후보로 지정
    • 장점: 구현이 간단하고 빠르다.
      • 동적 씬에 적합하다.
    • 단점: 셀 크기 설정이 중요한다.
      • 너무 작으면 비효율 너무 크면 충돌 후보가 많아지게 된다.
  2. Sweep and Prune (Sort and Sweep)
    • x, y, z 중 한 축에 대해 AABB의 시작, 끝점을 정렬
    • 겹치는 구간이 있는 물체 쌍만 후보로 지정
    • 장점: 동적 물체에 효율적이고 구현이 쉽다.
      • 매 프레임마다 정렬을 약간만 수정하면 되므로 갱신 비용이 낮다.
    • 단점: 한 축 정렬만으로는 복잡한 3D 장면에서는 오검출이 증가한다.
  3. Bounding Volume Hierarchy (BVH)
    • 물체 또는 삼각형들을 계층적 볼륨(Bounding Volume) 트리로 감싼다.
      • (e.g., AABB Tree, OBB Tree, Sphere Tree)
    • 루트에서 리프까지 내려가며 충돌 가능성 검사한다.
    • 장점: 정적 장면에 매우 효율적이고 정확도가 높다.
    • 단점: 트리 업데이트가 필요하며 동적 물체에는 추가 비용이 발생한다.
  4. QuadTree, Octree
    • 2D -> QuadTree, 3D -> Octree.
    • 공간을 재귀적으로 분할하여 각 노드가 포함하는 물체를 관리한다.
    • 장점: 공간 밀도 가 비균일한 분포에 강하다.
    • 단점: 구현이 복잡하고 동적 업데이트 시에는 비용이 발생한다.

Narrow Phase

걸러진 후보들에 대해 실제로 충돌했는지 정확히 판정하고 접촉점(Contact Point), 법선(Normal), 침투 깊이(Penetration Depth) 등을 계산하는 단계이다.

사용되는 주요 알고리즘들은 아래와 같다.

  1. Separating Axis Theorem (SAT)
    • 정확하고 간단하다. 볼록 다각형, 다면체에 효율적.
  2. GJK (Gilbert–Johnson–Keerthi) 알고리즘
    • 실제 엔진에서 가장 많이 사용됨(Box2D, Bullet 등)
  3. EPA (Expanding Polytope Algorithm)
    • GJK와 궁합이 좋아 세트로 자주 사용된다고 한다.
  4. SDF (Signed Distance Field)
    • GPU 기반 시뮬레이션이나 deformable body에 활용된다고 한다.

Narrow Phase 단계의 알고리즘들은 좀 더 정확한 결과를 알아내기 위해선지 모두 복잡하고 하나하나마다 깊은 이해가 필요한 것 같다.

결론

오늘은 충돌에서도 충돌 검출 단계에 대해서만 조금 알아보았다.

충돌에 대해서만 알려고 해도 이렇게나 많은 정보들이 존재한다.

물리 엔진에 대해 알아갈수록 점점 다양한 지식들이 나와서 재미가 느껴진다.

계속 알아가보자.

Day-44

tech 2025-10-25-AABB