충돌 감지 최적화 - 소프트웨어 융합

공간 분할 기법

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

사분 트리 (Quadtree)

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

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

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

옥트리 (Octree)

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

Axis-Aligned Bounding Box (AABB)

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

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

두 AABB $A$ 와 $B$ 의 최소 점과 최대 점을 각각 $A_{min}$ , $A_{max}$ , $B_{min}$ , $B_{max}$ 이라고 하자.
각 축에 대해 $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$
모든 축에 대해 겹치면 두 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;
}

최적화 기법 종합

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

예제 시나리오

대규모 3D 게임 월드의 충돌 감지
옥트리를 사용하여 초기 넓은 영역을 분할
AABB를 활용한 빠른 충돌 체크
나로우페이즈에서 GJK 알고리즘으로 정밀 검사
충돌 반응은 반사 법칙을 적용
밀도가 높은 객체 군집의 충돌 감지
DBSCAN을 통해 객체를 클러스터링
각 클러스터 내부에서만 충돌 검사 수행
클러스터 간의 충돌은 간단한 AABB로 필터링 후 정밀 검사

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