[게임 개발]#1_충돌

 

#1. 개념

 

1. 게임 개발의 '충돌'

게임 개발에서 '충돌'은 게임 객체 간의 상호작용을 결정하는 핵심 요소 중 하나입니다. 일반적으로, 사각형-사각형 충돌, 원-원 충돌, 그리고 원-사각형(생략) 충돌 감지 방법이 활용됩니다. 특히, '사각형' 간 충돌 감지에 활용되는 알고리즘으로 AABB(Aligned-Axis Bounding Box)와 OBB(Oriented Bounding Box) 방식을 활용합니다.

 

---

 

#2. 사각형 충돌

 

1. AABB(Aligned Axis Bounding Box) 충돌

 

1. 개념

AABB는 축에 정렬된 경계 상자를 의미합니다. 이는 모든 면이 X,Y, 그리고 Z과 평행한 정육면 모양의 상자, 3D 공간에서 객체를 감싸는 데 사용되는 상자입니다. AABB는 고정되어 회전하지 않고, 객체의 회전에 따라서 Scale값을 수정하며 조정됩니다. 따라서, AABB 간 충돌은 각 축에 대한 최소 값과 최대 값을 비교하는 방식으로 작동합니다. 만약, 한 축이라도 겹치지 않는다면, 두 AABB는 충돌하지 않은 것으로 판단합니다.

 

2. 동작 방식

#include <iostream>

struct AABB {
    float minX, minY, minZ;
    float maxX, maxY, maxZ;
};

bool isColliding(const AABB& a, const AABB& b) {
    return (a.minX <= b.maxX && a.maxX >= b.minX) &&
           (a.minY <= b.maxY && a.maxY >= b.minY) &&
           (a.minZ <= b.maxZ && a.maxZ >= b.minZ);
}

int main() {
    AABB box1 = {0, 0, 0, 1, 1, 1};
    AABB box2 = {0.5, 0.5, 0.5, 1.5, 1.5, 1.5};

    if (isColliding(box1, box2)) {
        std::cout << "AABB 충돌 발생!" << std::endl;
    } else {
        std::cout << "AABB 충돌 없음." << std::endl;
    }

    return 0;
}

AABB 충돌 방식은 X, Y, 그리고 Z축에 평행한 각 변의 최소 값과 최대 값의 비교 연산을 통해 두 AABB의 충돌 여부를 검사합니다. 이때, 한 축이라도 겹치지 않는다면 두 AABB는 충돌하지 않은 것으로 판단합니다. 

 

2. OBB(Oriented Bounding Box) 충돌

 

1. 개념

OBB는 회전하는 객체를 더욱 정확하게 감쌀 수 있는 경계 박스입니다. 이는 AABB와 달리 축에 평행/정렬되지 않으며, 객체의 회전과 함께 회전합니다. 따라서, OBB 간 충돌 감지는 AABB 간 충돌 감지보다 더 정확하지만, 계산 비용이 더 높습니다. OBB 간 충돌 감지는 분리 축 정리(Sperating Axis Theorem)를 기반으로 합니다. 분리 축 정리는 두 볼록 다각형 또는 볼록 다면체가 충돌하지 않기 위해서는, 적어도 하나의 축이 존재하여 두 다각형을 분리할 수 있다고 말합니다. 이때, 이 축을 분리 축이라고 하며, OBB 간 충돌 감지를 위해 필요한 개념입니다.

 

2. 동작 방식

 

1. 분리 축 선정 : OBB의 각 면에 수직인 로컬 축과 이들의 외적으로 얻어지는 축을 분리축으로 활용합니다. 두 OBB에 대하여 3개의 로컬 축이 존재하며, 이들 간의 외적으로 얻을 수 있는 분리 축은 최대 15개입니다. 
2. 분리 축에 투영(Projection) : 선정한 분리 축들에 대하여 두 OBB를 Projection합니다. Projection을 위하여 각 OBB의 각 꼭짓점(위치 벡터)을 분리 축에 대하여 내적 하여 얻을 수 있습니다(vector의 내적은 scalar값, 벡터가 아님).
3. 최소 값+최대 값 : 투영된 모든 스칼라 값들 중에서 최소 값과 최대 값을 찾아 하나의 선분을 구성합니다.
4. 투영된 선분의 겹침 여부 : 분리 축에 대하여 두 OBB의 투영된 선이 겹치는지 확인합니다. 만약, 모든 분리 축에 대하여 어떤 한 축이라도 두 선분이 겹치지 않는다면, 두 OBB는 충돌하지 않은 것으로 판단합니다. 

 

3. 코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <array>

struct Vector3 {
    float x, y, z;
    // 생성자
    Vector3(float x = 0, float y = 0, float z = 0) : x(x), y(y), z(z) {}
    // operator- 오버로딩
    Vector3 operator-(const Vector3& other) const {
        return {x - other.x, y - other.y, z - other.z};
    }
    // 두 벡터의 외적 계산을 위한 정적 함수
    static Vector3 cross(const Vector3& a, const Vector3& b) {
        return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x};
    }
    // 두 벡터의 내적 계산을 위한 정적 함수
    static float dot(const Vector3& a, const Vector3& b) {
        return a.x * b.x + a.y * b.y + a.z * b.z;
    }
    // 두 벡터의 스칼라 연산
    Vector3 operator*(float scalar) const {
        return {x * scalar, y * scalar, z * scalar};
    }
    // 벡터의 크기(길이?)
    float magnitude() const {
        return std::sqrt(x * x + y * y + z * z);
    }
    // 벡터의 정규화
    Vector3 normalize() const {
        float len = magnitude();
        if (len == 0) return {0, 0, 0};
        return {x / len, y / len, z / len};
    }
};

struct OBB {
    Vector3 center; // 중심점
    Vector3 halfSizes; // 반 축 길이
    std::array<Vector3, 3> axes; // 로컬 축

    OBB(const Vector3& center, const Vector3& halfSizes, const std::array<Vector3, 3>& axes)
        : center(center), halfSizes(halfSizes), axes(axes) {}
};
// 주어진 분리 축에 대하여 두 OBB가 분리 되는지, 중복되는지 확인
bool isSeparatedByAxis(const Vector3& axis, const OBB& obb1, const OBB& obb2) {
    float projection1 = 0.0f;
    float projection2 = 0.0f;
    // 분리축에 대하여 두 OBB의 로컬 축(X, Y, Z)을 투영(내적)합니다.
    for (int i = 0; i < 3; ++i) {
        projection1 += std::abs(Vector3::dot(axis, obb1.axes[i])) * obb1.halfSizes[i];
        projection2 += std::abs(Vector3::dot(axis, obb2.axes[i])) * obb2.halfSizes[i];
    }

    float distance = std::abs(Vector3::dot(axis, obb1.center - obb2.center));
    return distance > (projection1 + projection2);
}

bool checkOBBOverlap(const OBB& obb1, const OBB& obb2) {
    // 각 OBB의 로컬축이 서로 분리/중복 되는지 확인합니다.
    for (int i = 0; i < 3; ++i) {
        if (isSeparatedByAxis(obb1.axes[i], obb1, obb2)) return false;
        if (isSeparatedByAxis(obb2.axes[i], obb1, obb2)) return false;
    }

    // 이 예제에서는 각 OBB의 주축만을 사용합니다.
    // 더 정확한 계산을 위해 각 OBB의 로컬 축 서로에 대한 '외적'을 통해 추가적인 분리축 생성이 가능합니다!

위 예제 코드에서 각 OBB의 로컬 축 3개를 분리축으로 하는 OBB 간 충돌을 감지하고 있습니다. 이때, 각 OBB의 로컬 축간 '외적'을 통해 추가적인 분리 축 생성이 가능합니다. 이렇게 생성된 추가적인 분리축들을 활용해 더 정확한 충돌 감지가 가능합니다. 다만, 연산량이 많아져 성능 저하를 조심해야겠죠.

 

---