충돌 감지 방법론 - 실험 도서관

충돌 감지는 물리 엔진에서 매우 중요한 부분이다. 각 오브젝트 간의 충돌을 정밀하게 감지하고 처리함으로써 현실감 있는 시뮬레이션을 구현할 수 있다. 여러 가지 방법론이 존재하며 각 방법론마다 장단점이 있다.

AABB (Axis-Aligned Bounding Box)

AABB는 오브젝트를 둘러싸는 축에 정렬된 경계 박스를 이용해 충돌을 감지하는 방법이다. AABB는 충돌 감지에 있어 계산이 간단하고 빠르다는 장점이 있다.

두 개의 AABB 상자가 충돌하는지 확인하는 방법:

$\text{충돌 여부} = (A_{\min,x} \leq B_{\max,x} \quad \text{and} \quad A_{\max,x} \geq B_{\min,x}) \quad \text{and} \quad (A_{\min,y} \leq B_{\max,y} \quad \text{and} \quad A_{\max,y} \geq B_{\min,y})$

여기서 $A$ 와 $B$ 는 각각 두 오브젝트의 AABB 박스이다.

OBB (Oriented Bounding Box)

OBB는 AABB와 유사하지만 축이 물체에 고정되어 회전할 수 있는 경계 박스를 이용한다. OBB는 AABB에 비해 정확하지만, 충돌 감지 계산이 더 복잡한다.

두 OBB가 충돌하는지 확인하는 방법에는 Separation Axis Theorem (SAT)이 자주 사용된다. SAT는 한 축을 기준으로 오브젝트를 분리할 수 있는지 확인하는 방법이다.

SAT (Separating Axis Theorem)

SAT는 두 오브젝트가 충돌하지 않는 경우, 서로 분리할 수 있는 하나의 축이 존재함을 이용하는 방법이다. 이 접근법은 주로 다각형과 다면체의 충돌 감지에 사용된다.

두 오브젝트 $A$ 와 $B$ 가 충돌하는지 확인하려면 모든 후보 축에 대해 투영을 검사한다:
$A$ 의 에지와 $B$ 의 에지의 모든 조합을 검사한다.
각 축에 대해 프로젝션 U와 V의 최소값과 최대값을 비교한다.

$\max(A_{\text{proj}}) < \min(B_{\text{proj}}) \quad \text{or} \quad \max(B_{\text{proj}}) < \min(A_{\text{proj}})$

어느 하나의 분리 축이라도 충돌하지 않는다면 오브젝트는 충돌하지 않는다.

케이디 트리 (kd-Tree)

케이디 트리는 다차원 공간에서 오브젝트를 분할하는 방법으로, 분할과 정렬을 통해 효율적인 충돌 감지를 가능하게 한다. 각 노드는 공간을 두 개의 하위 공간으로 재귀적으로 분할한다.

초기화 단계에서 모든 오브젝트를 포함하는 루트 노드를 생성한다.
각 노드를 다시 두 하위 노드로 분할하는데, 만약 노드에 포함된 오브젝트의 수가 임계값 $k$ 보다 적으면 더 이상 분할하지 않는다.
충돌감지 단계에서는 탐색이 필요한 노드들만 순회한다.

쿼드 트리 (QuadTree)와 옥트리 (Octree)

쿼드 트리와 옥트리는 이차원 및 삼차원 공간을 분할하여 효율적인 충돌 감지를 제공한다.

쿼드 트리 (2D):
공간을 4개의 하위 공간으로 분할한다.
옥트리 (3D):
공간을 8개의 하위 공간으로 분할한다.
트리의 각 노드는 하위 공간을 재귀적으로 분할하며, 노드에 포함된 오브젝트의 수가 특정 임계값보다 작은 경우 더 이상 분할하지 않는다.

브로드 페이즈 (Broad Phase)와 내로우 페이즈 (Narrow Phase)

충돌 감지는 일반적으로 '브로드 페이즈'와 '내로우 페이즈'로 나뉜다:

브로드 페이즈:
충돌 가능한 오브젝트 쌍을 빠르게 필터링한다.
AABB나 공간 분할 기법 (예: 그리드, 트리 구조)을 사용하여 후보 오브젝트 쌍을 찾는다.
내로우 페이즈:
필터링된 오브젝트 쌍에 대해 정밀한 충돌 감지를 수행한다.
SAT나 OBB 같은 복잡한 알고리즘을 사용하여 실제 충돌을 감지한다.

GPU 기반 충돌 감지

최근에는 많은 물리 엔진들이 GPU를 활용하여 충돌 감지 작업을 가속화하고 있다. GPU는 병렬 처리가 강력하므로, 많은 오브젝트 간의 충돌을 동시에 처리할 수 있다.

CUDA/OpenCL:
NVIDIA의 CUDA 또는 크로노스 그룹의 OpenCL을 사용하여 병렬 처리를 최적화한다.
각 계산을 독립적으로 처리할 수 있어 전체적인 충돌 감지 속도를 대폭 향상시킬 수 있다.
Shader 기반 충돌 감지:
그래픽 셰이더를 이용하여 충돌 감지를 수행한다.
셰이더 프로그램은 이미 그래픽 하드웨어에서 병렬로 실행되므로 이를 활용하는 방식이다.

공간 해시 (Spatial Hash)

공간 해시는 공간을 균등한 격자로 분할하고 각 격자 셀에 포함된 오브젝트들을 해시 테이블에 저장하는 기법이다.

해시 함수:
오브젝트의 위치를 입력으로 받아서 격자 셀이 해시 테이블의 인덱스로 변환된다.

$h(x, y, z) = (x \cdot p1 + y \cdot p2 + z \cdot p3) \mod n$

여기서 $p1, p2, p3$ 는 큰 소수이고 $n$ 은 해시 테이블의 크기이다. - 충돌 감지: - 오브젝트가 속한 격자 셀 내의 다른 오브젝트들과 충돌 여부를 검사한다. - 이웃하는 격자 셀들도 포함하여 충돌 감지 범위를 확장한다.

지속 충돌 감지 (Continuous Collision Detection)

일반적인 충돌 감지는 이산적인 시간 단계에서 수행되지만, 지속 충돌 감지는 두 시간 단계 사이에서 오브젝트의 충돌 여부를 감지하는 기법이다.

Swept Volumes:
시간 동안 오브젝트가 이동하는 궤적을 따라 확장된 부피 (Swept Volume)를 사용하여 충돌 감지를 수행한다.
TOI (Time of Impact):
두 오브젝트가 언제 충돌할지 정확한 시간을 계산한다.
충돌 시간 이전에 물리적 반응을 처리하여 '터널링' 문제를 방지한다.

하이브리드 접근법

많은 물리 엔진들은 위의 여러 방법론을 결합하여 최적의 성능과 정확도를 얻는다.

브로드 페이즈와 내로우 페이즈의 조합:
브로드 페이즈에서 간단하고 빠른 기법(AABB, 공간 해시 등)을 사용하여 후보 충돌 쌍을 찾고, 내로우 페이즈에서 세밀한 충돌 감지(SAT, OBB 등)를 수행한다.
Hierarchical Spatial Partitioning:
트리 구조 (예: 케이디 트리, 쿼드 트리)를 사용하여 공간을 분할하면서 중첩된 충돌 감지를 점진적으로 세밀하게 수행한다.

결론적으로, 물리 엔진의 효율성과 정확성을 높이기 위해 다양한 충돌 감지 방법론이 사용된다. 각 방법론은 그 나름의 장단점을 가지고 있으며, 대부분의 물리 엔진에서는 상황에 맞게 여러 기법을 혼합하여 사용한다.

충돌 감지 기법은 물리 엔진의 성능과 정확도를 크게 좌우하는 중요한 요소이다. 각 기법의 원리와 적용 방법을 이해하고, 상황에 맞게 최적의 방법을 선택하는 것이 중요하다. 물리 엔진의 복잡성과 성능 요구사항에 따라 다양한 기법의 조합을 통해 최상의 결과를 얻을 수 있다.