Sphere-Collision 알고리즘

Sphere-Collision 알고리즘은 간단하면서도 중요하게 사용되는 충돌 감지 알고리즘의 한 종류로, 구와 구 사이의 충돌을 감지하는 데 사용된다. 이 알고리즘은 물리 엔진, 게임 개발, 시뮬레이션 등에서 많이 사용된다.

3.1. 구의 수학적 표현

구는 중심점과 반지름으로 정의된다. 이를 수학적으로 표현하면 다음과 같다.

중심점: $\mathbf{c} = (c_x, c_y, c_z)$
반지름: $r$

구 $A$ 와 $B$ 가 있다고 가정하면, 각각의 중심점과 반지름은 다음과 같이 표현된다.

구 $A$ : 중심점 $\mathbf{c}_A = (c_{Ax}, c_{Ay}, c_{Az})$ , 반지름 $r_A$
구 $B$ : 중심점 $\mathbf{c}_B = (c_{Bx}, c_{By}, c_{Bz})$ , 반지름 $r_B$

3.2. 구의 충돌 조건

두 구 $A$ 와 $B$ 가 충돌하려면 두 구의 중심점 사이의 거리가 두 구의 반지름의 합보다 작거나 같아야 한다. 이를 수식으로 표현하면 다음과 같다.

$\|\mathbf{c}_A - \mathbf{c}_B\| \leq r_A + r_B$

여기서 $\|\mathbf{c}_A - \mathbf{c}_B\|$ 는 두 구의 중심점 사이의 거리이다. 구의 중심점 사이의 거리는 유클리디언 거리로 계산할 수 있다.

두 벡터 간의 유클리디언 거리는 다음과 같이 구할 수 있다.

$\|\mathbf{c}_A - \mathbf{c}_B\| = \sqrt{(c_{Ax} - c_{Bx})^2 + (c_{Ay} - c_{By})^2 + (c_{Az} - c_{Bz})^2}$

이를 충돌 조건과 함께 사용하면 다음과 같다.

$\sqrt{(c_{Ax} - c_{Bx})^2 + (c_{Ay} - c_{By})^2 + (c_{Az} - c_{Bz})^2} \leq r_A + r_B$

3.3. 벡터를 이용한 충돌 감지

벡터를 이용해 위의 충돌 조건을 간단히 표현할 수 있다.

중심점 간의 벡터를 구한다: $$ \mathbf{d} = \mathbf{c}_A - \mathbf{c}_B $$
벡터 $\mathbf{d}$ 의 크기를 구한다: $$ |\mathbf{d}| = \sqrt{\mathbf{d} \cdot \mathbf{d}} $$
충돌 조건을 체크한다: $$ |\mathbf{d}| \leq r_A + r_B $$

이 과정을 통해 두 구의 충돌을 간단하게 감지할 수 있다.

3.4. 구현 코드

C++ 예제 코드는 다음과 같다:

struct Sphere {
    Vector3 center;
    float radius;
};

bool isColliding(const Sphere& A, const Sphere& B) {
    Vector3 d = A.center - B.center;
    float distanceSquared = d.dot(d);
    float radiusSum = A.radius + B.radius;
    return distanceSquared <= (radiusSum * radiusSum);
}

여기서 Vector3는 3차원 벡터를 나타내는 구조체 또는 클래스이다.

3.5. 최적화

충돌 감지 알고리즘을 최적화하려면 여러 건의 구체적인 최적화 기법을 사용할 수 있다.

3.5.1. 공간 분할

공간 분할 기법은 충돌 감지 연산의 수를 줄이는 데 효과적이다. 대표적인 공간 분할 방법들은 다음과 같다:

쿼드트리/옥트리 (Quadtree/Octree): 2차원에서는 쿼드트리, 3차원에서는 옥트리를 사용해 구체들을 공간에 효율적으로 배치하고 검색할 수 있다.
그리드 분할: 공간을 균등한 그리드 셀로 나누고, 각 셀에 속한 구들만 충돌 검사를 수행한다.

3.5.2. 축소 반지름 검토 (Bounding Volume Hierarchies)

구 대신 더 간단한 형태의 경계체 (예: Axis-Aligned Bounding Box, AABB)를 사용해 초기 충돌 검사를 수행한 후, 실제 구 간의 충돌을 검사할 수 있다.

3.5.3. 정렬된 리스트

충돌 검사 전에 구들의 중심 좌표를 기준으로 정렬한 리스트를 사용하면, 가까운 구들만 검사하면 되므로 효율성을 높일 수 있다.

struct BoundingVolume {
    Vector3 center;
    float radius;
};

bool isCollidingWithSortedList(const std::vector<BoundingVolume>& volumes) {
    for (size_t i = 0; i < volumes.size(); ++i) {
        for (size_t j = i + 1; j < volumes.size(); ++j) {
            if (volumes[j].center.x - volumes[i].center.x > volumes[i].radius + volumes[j].radius) {
                break;
            }
            if (isColliding(volumes[i], volumes[j])) {
                return true;
            }
        }
    }
    return false;
}

3.6. 충돌 후 처리

충돌이 발생한 경우에는 부딪힌 구들을 처리하는 방법도 중요하다. 이를 위해 물리적 반응을 계산하는 알고리즘이 필요하다. 대표적인 방법은 다음과 같다:

3.6.1. 반사 벡터 계산

충돌 시 두 구의 속도를 반사시켜 충돌 후의 속도를 계산할 수 있다.

struct Sphere {
    Vector3 center;
    Vector3 velocity;
    float radius;
    float mass;
};

void resolveCollision(Sphere& A, Sphere& B) {
    Vector3 normal = (B.center - A.center).normalize();
    float relativeVelocity = (B.velocity - A.velocity).dot(normal);

    if (relativeVelocity > 0) return;

    float e = 1.0f; // 반사 계수 (탄성 충돌)
    float j = -(1 + e) * relativeVelocity / (1 / A.mass + 1 / B.mass);

    Vector3 impulse = j * normal;
    A.velocity -= impulse / A.mass;
    B.velocity += impulse / B.mass;
}

3.6.2. 침투 깊이 보정

구들이 겹치는 경우, 충돌 해소를 위해 침투 깊이를 계산하고 이를 바탕으로 위치를 보정한다.

void positionalCorrection(Sphere& A, Sphere& B) {
    const float percent = 0.8; // 보정 비율
    const float slop = 0.01; // 소수 제거
    Vector3 collisionNormal = (B.center - A.center).normalize();
    float penetrationDepth = A.radius + B.radius - (B.center - A.center).length();
    Vector3 correction = std::max(penetrationDepth - slop, 0.0f) * percent * collisionNormal;

    A.center -= correction * (A.radius / (A.radius + B.radius));
    B.center += correction * (B.radius / (A.radius + B.radius));
}

구 충돌 감지 알고리즘은 게임 및 시뮬레이션에서 매우 중요하다. 효율적으로 충돌을 감지하고 처리하기 위해서는 다양한 최적화 기법과 충돌 후 처리 방법을 이해하고 사용할 필요가 있다.