# 충돌 감지 시스템

충돌 감지 시스템은 물리 엔진의 필수 구성 요소 중 하나로, 객체 간의 물리적 상호작용을 처리하기 위해 두 객체가 충돌했는지를 탐지하고 적절한 대응을 가능하게 한다. 이 시스템은 다양한 알고리즘과 데이터 구조를 사용하여 효율적이고 정확한 충돌 감지를 수행한다. 다음은 충돌 감지 시스템의 주요 구성 요소와 이를 구현하기 위한 기본 개념들이다.

#### AABB (Axis-Aligned Bounding Box)

AABB는 객체를 감싸는 가장 작은 직육면체로 축에 평행하게 정렬된다. 충돌 검출의 첫 단계로, 이 박스를 두 객체에 대해 비교하여 빠르게 충돌 여부를 판단할 수 있다.

**AABB 정의**

AABB는 두 개의 점 $\mathbf{min}$과 $\mathbf{max}$로 정의된다.

* $\mathbf{min} = (\mathbf{min}\_x, \mathbf{min}\_y, \mathbf{min}\_z)$
* $\mathbf{max} = (\mathbf{max}\_x, \mathbf{max}\_y, \mathbf{max}\_z)$

두 AABB가 충돌하는지를 판단하기 위한 조건은 다음과 같다:

$$
\begin{align\*} \mathbf{min}\_A.x &\leq \mathbf{max}\_B.x \ \mathbf{max}\_A.x &\geq \mathbf{min}\_B.x \ \mathbf{min}\_A.y &\leq \mathbf{max}\_B.y \ \mathbf{max}\_A.y &\geq \mathbf{min}\_B.y \ \mathbf{min}\_A.z &\leq \mathbf{max}\_B.z \ \mathbf{max}\_A.z &\geq \mathbf{min}\_B.z \end{align\*}
$$

이 조건을 모두 만족하면, 두 AABB가 충돌한 것이다.

#### OBB (Oriented Bounding Box)

OBB는 축에 평행하지 않고 임의의 방향으로 정렬된 박스로, AABB보다 더 정확한 충돌 감지를 제공한다.

**OBB 정의**

OBB는 중심점 $\mathbf{c}$, 반쪽 길이 벡터 $\mathbf{e}$, 그리고 회전 행렬 $\mathbf{R}$로 정의된다.

OBB 충돌 검출은 Separating Axis Theorem (SAT) 을 이용하여 수행할 수 있다. SAT에 따르면, 두 개의 OBB가 충돌하지 않는 조건은 적어도 하나의 축에 대해 투영된 영역이 겹치지 않는 경우이다.

#### Separating Axis Theorem (SAT)

SAT는 두 개의 다면체가 충돌하지 않는다면, 그 둘을 분리할 수 있는 평면이 적어도 하나가 존재한다는 원리이다. 이 평면을 분리 축이라 하며, SAT를 통해 충돌 여부를 판단할 수 있다.

**SAT 적용하기**

SAT를 적용하기 위해 다음 단계를 따른다:

1. 후보 축을 정의한다.
2. 각 후보 축에 대해 두 객체를 투영한다.
3. 투영된 범위가 겹치는지 확인한다.
4. 모든 후보 축에서 범위가 겹치지 않는 경우 충돌하지 않는다고 판단한다.

#### 공간 분할 기법

공간 분할 기법은 많은 객체들이 있는 경우 충돌 검출을 효율적으로 하기 위해 사용된다. 대표적인 공간 분할 기법에는 Uniform Grid, QuadTree, OcTree 등이 있다.

**Uniform Grid**

* 공간을 고정된 크기의 그리드로 나눈다.
* 각 객체를 해당하는 그리드 셀에 넣고, 같은 셀에 있는 객체들만 충돌 여부를 검사한다.

**QuadTree & OcTree**

* QuadTree: 2차원 공간을 재귀적으로 4개의 하위 노드로 분할하는 구조.
* OcTree: 3차원 공간을 재귀적으로 8개의 하위 노드로 분할하는 구조.

#### 충돌 응답

충돌 감지 후에는 충돌 응답이 필요하다. 충돌 응답은 객체들의 속도와 방향을 새롭게 설정하여 현실감 있는 상호작용을 구현한다.

**반사 벡터 계산**

반사 벡터 $\mathbf{R}$는 입사 벡터 $\mathbf{I}$와 표면 법선 벡터 $\mathbf{N}$를 이용해 다음과 같이 계산된다:

$$
\mathbf{R} = \mathbf{I} - 2 (\mathbf{I} \cdot \mathbf{N}) \mathbf{N}
$$

이 외에도 운동량 보존 법칙, 충돌 장애물 처리 등을 포함한 다양한 방법들이 있다.

#### 운동량 보존 법칙 및 충돌 후 속도 계산

충돌 후 객체의 속도를 계산할 때, 운동량 보존 법칙을 적용한다. 이 법칙은 충돌 전후의 전체 운동량이 같아야 한다는 원리이다.

**탄성 충돌**

탄성 충돌에서는 운동 에너지도 보존된다. 두 질량 $m\_1$과 $m\_2$가 충돌하여 속력 $v\_1$와 $v\_2$로 움직일 때, 충돌 후 속력 $v\_1'$와 $v\_2'$를 계산하는 공식은 다음과 같다:

$$
\begin{align\*} v\_1' &= \frac{(m\_1 - m\_2) v\_1 + 2 m\_2 v\_2}{m\_1 + m\_2} \ v\_2' &= \frac{(m\_2 - m\_1) v\_2 + 2 m\_1 v\_1}{m\_1 + m\_2} \end{align\*}
$$

**비탄성 충돌**

비탄성 충돌에서는 운동량은 보존되지만 운동 에너지는 보존되지 않는다. 일부 에너지가 열 등 다른 형태로 변환될 수 있다. 이 경우, 탄성 계수 $e$를 사용하여 충돌 후 속도를 계산할 수 있다.

$$
\begin{align\*} v\_1' &= \frac{m\_1 v\_1 + m\_2 v\_2 + m\_2 e (v\_2 - v\_1)}{m\_1 + m\_2} \ v\_2' &= \frac{m\_1 v\_1 + m\_2 v\_2 - m\_1 e (v\_2 - v\_1)}{m\_1 + m\_2} \end{align\*}
$$

여기서 $e$는 0(완전 비탄성 충돌)에서 1(완전 탄성 충돌)까지의 값을 가진다.

#### 충돌 후 회전 운동

충돌 후 객체들은 회전 운동도 경험할 수 있다. 이는 각운동량 보존법칙을 사용하여 회전 속도를 계산할 수 있다.

**각운동량 보존**

각운동량 $L$은 충돌 전후에 보존되며, 각운동량은 다음과 같이 정의된다:

$$
L = I \omega
$$

여기서 $I$는 관성 모멘트이고, $\omega$는 각속도이다.

충돌 후 각속도는 다음과 같이 계산된다:

$$
\omega' = \frac{L}{I'}
$$

여기서 $I'$는 충돌 후의 새로운 관성 모멘트이다.

#### 충돌 최적화 기법

충돌 감지 시스템을 최적화하기 위해서는 다양한 기법을 사용할 수 있다. 예를 들어, 브로드 페이즈와 내로우 페이즈로 나누어 충돌 검출을 수행할 수 있다.

**브로드 페이즈**

브로드 페이즈에서는 전체 객체 범위를 고려하여 충돌 가능성이 있는 객체들을 빠르게 필터링한다. 이 단계에서는 AABB나 OBB를 사용하여 충돌 가능성이 있는 후보군을 추린다.

**내로우 페이즈**

내로우 페이즈에서는 필터링된 객체들 간의 실제 충돌 여부를 정밀하게 검사한다. 이 단계에서 SAT나 물리 기반의 충돌 응답 알고리즘을 사용하여 정확한 충돌 감지를 수행한다.

#### 충돌 감지 시스템 구현의 미래

충돌 감지 시스템은 끊임없이 발전하고 있다. 현대의 물리 엔진들은 GPU를 활용한 병렬 연산, 머신 러닝 기반의 충돌 예측 등의 새로운 기술을 도입하고 있다.

**병렬 연산**

병렬 처리는 많은 객체들이 동시에 존재하는 복잡한 시뮬레이션에서도 효율적인 충돌 감지를 가능하게 한다. CUDA 등을 사용하여 GPU에서 병렬 처리를 구현하면 충돌 검출 속도를 크게 향상시킬 수 있다.

**머신 러닝**

머신 러닝은 충돌 예측 및 최적화를 위해 사용될 수 있다. 객체의 이동 패턴을 학습하고 이를 기반으로 충돌 가능성을 예측하여 더욱 효율적인 충돌 감지를 구현할 수 있다.

요약하자면, 충돌 감지 시스템은 물리 엔진의 핵심 구성 요소로서 다양한 알고리즘과 기법을 통해 구현된다. 이를 통해 현실감 있는 물리 시뮬레이션을 가능하게 하며, 현대 기술을 통해 지속적으로 발전하고 있다.