충돌 감지 최적화

공간 분할 기법

충돌 감지 최적화에서 가장 중요한 요소 중 하나는 공간 분할 기법이다. 대규모 게임 환경에서 모든 객체 간의 충돌을 검사하는 것은 비효율적이기 때문에, 공간 분할 기법을 통해 이 문제를 해결할 수 있다.

사분 트리 (Quadtree)

사분 트리는 2D 공간을 네 개의 재귀적 하위 공간으로 분할하는 구조이다. 각 노드는 네 개의 자식 노드를 가지며, 이 과정은 객체가 소속된 공간의 범위가 충분히 작아질 때까지 반복된다.

$\text{여기서 각 노드는 아래와 같이 정의된다:}$

• 루트 노드는 전체 공간을 나타낸다.

• 각 내부 노드는 네 개의 자식 노드를 가지고, 각각의 자식 노드는 더 작은 사분면을 나타낸다.

옥트리 (Octree)

옥트리는 사분 트리의 3D 버전이다. 전체 공간을 여덟 개의 부분 공간으로 나누고, 각 노드는 여덟 개의 자식 노드를 갖는다. 이는 3D 충돌 감지에 더 적합한다.

Axis-Aligned Bounding Box (AABB)

AABB는 축에 정렬된 경계 상자로, 각 객체를 포함하는 최소한의 축 정렬된 붕괴 상자를 의미한다. 두 AABB가 충돌하는지를 체크하는 것은 매우 단순하면서도 효율적이다. 두 AABB가 충돌하는지 판단하기 위해서는 각 축에 대해 투영된 간격이 겹치는지를 검사하면 된다.

$\text{AABB 충돌 검사 알고리즘은 아래와 같다:}$

1. 두 AABB $A$와 $B$의 최소 점과 최대 점을 각각 $A_{min}$, $A_{max}$, $B_{min}$, $B_{max}$ 이라고 하자.

2. 각 축에 대해 $A$와 $B$가 겹치는지 확인한다:

   • $x$ 축: $A_{max}.x \geq B_{min}.x$ 그리고 $A_{min}.x \leq B_{max}.x$

   • $y$ 축: $A_{max}.y \geq B_{min}.y$ 그리고 $A_{min}.y \leq B_{max}.y$

   • $z$ 축 (3D의 경우): $A_{max}.z \geq B_{min}.z$ 그리고 $A_{min}.z \leq B_{max}.z$

3. 모든 축에 대해 겹치면 두 AABB는 충돌한다고 판단한다.

AABB의 충돌 검사 알고리즘

bool AABB::isColliding(const AABB& other) const {
    return (max.x >= other.min.x && min.x <= other.max.x) &&
           (max.y >= other.min.y && min.y <= other.max.y) &&
           (max.z >= other.min.z && min.z <= other.max.z); // 3D의 경우
}

브로드페이즈와 나로우페이즈

충돌 감지는 일반적으로 두 단계로 나뉜다: 브로드페이즈(Broad-phase)와 나로우페이즈(Narrow-phase).

브로드페이즈 (Broad-phase)

브로드페이즈에서는 좁은 범위에서 실제로 충돌할 가능성이 있는 객체들을 빠르게 필터링한다. 이를 위해 앞서 언급된 공간 분할 기법 또는 그리드 기반의 충돌 감지를 활용할 수 있다.

나로우페이즈 (Narrow-phase)

나로우페이즈에서는 브로드페이즈에서 필터링된 객체들 간의 실제 충돌을 상세히 검사한다. 나로우페이즈에서는 더욱 정밀한 충돌 검사 기법을 사용할 수 있다.

GJK (Gilbert-Johnson-Keerthi) Algorithm

GJK 알고리즘은 두 볼록한 폴리헤드에 대한 충돌 여부를 판별하는 효율적인 방법이다.

기본 아이디어

두 폴리헤드 $A$와 $B$가 충돌하는 것은 그들의 Minkowski 합집합이 원점을 포함하는지 여부로 결정된다. 이 알고리즘은 반복적 절차를 통해 이 문제를 해결한다.

$\text{Minkowski 합집합:}$

$$A \oplus (-B) = \{ \mathbf{a} - \mathbf{b} \mid \mathbf{a} \in A, \mathbf{b} \in B \}$$

GJK 알고리즘은 이 구성요소를 바탕으로 함정된다.

해싱 기법

해싱 기법은 충돌 감지 최적화에 사용되는 또 다른 방법이다. 해싱 기법에서는 객체를 공간 상의 특정 셀에 매핑하여, 해당 셀 내에서만 충돌 검사를 수행한다. 이는 브로드페이즈의 일종으로 볼 수 있다.

클러스터 기법

클러스터링 기법은 비슷한 특성을 지닌 객체들을 그룹으로 묶어 충돌 감지를 최적화하는 방법이다. 이는 객체들이 보통 일정한 영역 내에서 함께 이동하거나 상호작용할 가능성이 높은 경우에 유용하다.

K-means 클러스터링

K-means 클러스터링은 객체들을 K개의 클러스터로 분할하는 기법이다. 초기 클러스터 중심을 임의로 선택한 후, 각 객체를 가장 가까운 중심으로 배정하고, 배정된 객체의 중심을 다시 계산하여 반복한다.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN은 밀도 기반 클러스터링 기법으로, 밀도가 높은 영역을 클러스터로 정의한다. 특이점은, 임의의 두 점 사이의 최소 거리와 밀도 기준을 통해 클러스터를 형성하는 방식이다. 밀도 기반 방법을 통해 노이즈와 이상치를 무시할 수 있다.

충돌 반응 처리

충돌 감지 후에는 충돌 반응을 처리하는 것이 중요하다. 이는 게임이나 시뮬레이션에서 객체가 물리적으로 어떻게 반응해야 하는지를 결정한다.

반사 법칙

반사 법칙은 충돌 후에도 에너지와 운동량이 보존되도록 하는 기법이다. 예를 들어, 두 공이 충돌할 때, 반사각은 입사각과 동일하게 설정할 수 있다.

충돌 반응 알고리즘

void resolveCollision(Circle& a, Circle& b) {
    Vector2d normal = b.position - a.position;
    normal.normalize();

    float relativeVelocity = Vector2d::dotProduct(b.velocity - a.velocity, normal);
    if (relativeVelocity > 0) return;

    float e = std::min(a.restitution, b.restitution);
    float j = -(1 + e) * relativeVelocity;
    j /= a.inverseMass + b.inverseMass;

    Vector2d impulse = j * normal;
    a.velocity -= a.inverseMass * impulse;
    b.velocity += b.inverseMass * impulse;
}

최적화 기법 종합

충돌 감지는 각 상황에 맞는 다양한 기법을 이용해 최적화할 수 있다. 모든 기법은 각각의 장단점을 가지고 있으며, 상황에 따라 적절히 조합하여 사용함으로써 성능을 극대화할 수 있다.

예제 시나리오

1. 대규모 3D 게임 월드의 충돌 감지

   • 옥트리를 사용하여 초기 넓은 영역을 분할

   • AABB를 활용한 빠른 충돌 체크

   • 나로우페이즈에서 GJK 알고리즘으로 정밀 검사

   • 충돌 반응은 반사 법칙을 적용

2. 밀도가 높은 객체 군집의 충돌 감지

   • DBSCAN을 통해 객체를 클러스터링

   • 각 클러스터 내부에서만 충돌 검사 수행

   • 클러스터 간의 충돌은 간단한 AABB로 필터링 후 정밀 검사

이 책에서는 충돌 감지 최적화와 관련된 다양한 이론과 기법, 그리고 이들을 실제로 구현하고 적용하는 방법에 대해 다루었다. 이제 이러한 기법들을 프로젝트에 적용하여 보다 효율적인 충돌 감지 시스템을 구축할 수 있다.