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

AABB (Axis-Aligned Bounding Box)

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

AABB 정의

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

두 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

충돌 응답

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

반사 벡터 계산

반사 벡터 \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에서 병렬 처리를 구현하면 충돌 검출 속도를 크게 향상시킬 수 있다.

머신 러닝

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

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