Collider

Collider 간 충돌 판단은 DirectX의 충돌 감지 기능을 활용한 계층적 구조로 구현되어 있습니다.

기본 구조

               BaseCollider (추상 클래스)
                         ↓
                   ┌─────┴─────┐
                   │           │
             BoxCollider  SphereCollider

충돌 감지 세부 작동 원리

박스-박스 충돌 (Box vs Box)

// BoxCollider.cpp
case ColliderType::Box:
    return _boundingBox.Intersects(dynamic_pointer_cast<BoxCollider>(other)->GetBoundingBox());

• DirectX의 BoundingOrientedBox::Intersects() 메서드를 호출

• 두 OBB(Oriented Bounding Box)의 분리축 테스트(Separating Axis Theorem)를 수행

• 축이 분리되어 있지 않으면 충돌로 판정

구-구 충돌 (Sphere vs Sphere)

// SphereCollider.cpp
case ColliderType::Sphere:
    return _boundingSphere.Intersects(dynamic_pointer_cast<SphereCollider>(other)->GetBoundingSphere());

• DirectX의 BoundingSphere::Intersects() 메서드 호출

• 두 구의 중심 간 거리와 반지름 합을 비교

• 중심 간 거리 ≤ 반지름 합이면 충돌로 판정

박스-구 충돌 (Box vs Sphere / Sphere vs Box)

// BoxCollider.cpp
case ColliderType::Sphere:
    return _boundingBox.Intersects(dynamic_pointer_cast<SphereCollider>(other)->GetBoundingSphere());

// SphereCollider.cpp
case ColliderType::Box:
    return _boundingSphere.Intersects(dynamic_pointer_cast<BoxCollider>(other)->GetBoundingBox());

• DirectX의 BoundingOrientedBox::Intersects(BoundingSphere)와BoundingSphere::Intersects(BoundingOrientedBox) 메서드 호출

• 구에서 OBB로의 최단 거리를 계산하여 이 거리가 구의 반지름보다 작거나 같으면 충돌로 판정

충돌체 업데이트 메커니즘

void BoxCollider::Update()
{
    shared_ptr<Transform> transform = GetTransform();
    
    // 중심점 업데이트
    _boundingBox.Center = transform->GetWorldPosition() + _center;
    
    // 크기 업데이트
    Vec3 scale = transform->GetWorldScale() * _scale;
    _boundingBox.Extents = Vec3(scale.x * 0.5f, scale.y * 0.5f, scale.z * 0.5f);
    
    // 회전 업데이트
    _boundingBox.Orientation = transform->GetQTRotation();
}

• 매 프레임 Transform 컴포넌트의 정보(위치, 크기, 회전)를 바운딩 볼륨에 반영

• 이를 통해 게임 오브젝트 변형에 따라 충돌 영역도 자동 업데이트

핵심 포인트

1. 타입 기반 디스패치: 충돌체 타입에 따라 적절한 충돌 검사 로직으로 분기

2. DirectX 내장 충돌 함수 활용: 복잡한 충돌 계산은 DirectX 라이브러리에 위임

3. Transform과 연동: 게임 오브젝트의 변형(위치, 크기, 회전)을 충돌 영역에 반영

4. 컴포넌트 기반 설계: 충돌 처리가 컴포넌트로 캡슐화되어 객체 지향적 설계 구현

효율적인 충돌 처리 방식

충돌체 수집 및 최적 축 선택

vector<shared_ptr<BaseCollider>> colliders;
const auto& gameObjects = GetGameObjects();
for (shared_ptr<GameObject> gameObject : gameObjects)
{
    if (gameObject->GetComponent<BaseCollider>() == nullptr)
        continue;

    colliders.push_back(gameObject->GetComponent<BaseCollider>());
}

// 최적 축 선택
int bestAxis = 0; // 기본값은 x축

if (colliders.size() > 1)
{
    float xSpread = CalculateSpread(colliders, 0);
    float ySpread = CalculateSpread(colliders, 1);
    float zSpread = CalculateSpread(colliders, 2);

    // 가장 분산이 큰 축 선택 (객체 간격이 가장 넓은 축)
    if (ySpread > xSpread && ySpread > zSpread)
        bestAxis = 1; // y축
    else if (zSpread > xSpread && zSpread > ySpread)
        bestAxis = 2; // z축
}

이 부분의 핵심은 분포 기반 축 선택입니다. 각 축(x, y, z)별로 충돌체 분포도를 계산하고, 가장 분산이 큰 축을 선택합니다. 이는 다음과 같은 이유로 효율적입니다:

• 오브젝트 간 간격이 넓은 축을 선택하면 불필요한 충돌 검사를 크게 줄일 수 있음

• 장면의 특성에 따라 적응적으로 최적 축을 선택함

• 예: 수평으로 넓게 배치된 장면에선 x축, 수직 구조물이 많은 장면에선 y축이 효과적

CalculateSpread 함수는 이 분포를 계산합니다:

float Scene::CalculateSpread(const vector<shared_ptr<BaseCollider>>& colliders, int axis)
{
    if (colliders.empty())
        return 0.0f;

    float minValue = FLT_MAX;
    float maxValue = -FLT_MAX;

    // 해당 축에서 최소값과 최대값 찾기
    for (const auto& collider : colliders)
    {
        float min = GetMinBound(collider, axis);
        float max = GetMaxBound(collider, axis);

        if (min < minValue) minValue = min;
        if (max > maxValue) maxValue = max;
    }

    // 분산 계산 (최대-최소 범위)
    return maxValue - minValue;
}

Sort and Sweep 알고리즘 구현

// 선택된 최적 축으로 정렬
SortAndSweep(colliders, bestAxis);

SortAndSweep 함수는 충돌체를 선택한 축을 기준으로 정렬합니다:

void Scene::SortAndSweep(vector<shared_ptr<BaseCollider>>& colliders, int axis)
{
    // 지정된 축을 기준으로 충돌체들을 정렬
    std::sort(colliders.begin(), colliders.end(), [axis](const shared_ptr<BaseCollider>& a, const shared_ptr<BaseCollider>& b) {
        float aMin = 0.0f;
        float bMin = 0.0f;

        // 각 충돌체 타입에 따라 해당 축의 최소값 구하기
        if (a->GetColliderType() == ColliderType::Box)
        {
            shared_ptr<BoxCollider> boxCollider = dynamic_pointer_cast<BoxCollider>(a);
            BoundingOrientedBox box = boxCollider->GetBoundingBox();

            // 중심 위치와 크기 값 가져오기
            Vec3 center = Vec3(box.Center.x, box.Center.y, box.Center.z);
            Vec3 extents = Vec3(box.Extents.x, box.Extents.y, box.Extents.z);

            // 해당 축의 최소값 계산
            if (axis == 0) aMin = center.x - extents.x;  // x축
            else if (axis == 1) aMin = center.y - extents.y;  // y축
            else aMin = center.z - extents.z;  // z축
        }
        else if (a->GetColliderType() == ColliderType::Sphere)
        {
            // ... 구 충돌체 처리 코드 ...
        }

        // 두 번째 충돌체에 대해서도 동일한 계산
        // ... 생략 ...

        // 최소값을 기준으로 정렬
        return aMin < bMin;
    });
}

이 정렬 과정은 O(n log n) 복잡도를 가지며, 다음 단계인 스윕 과정을 위한 기초를 제공합니다.

액티브 리스트 기반 스윕 과정

// 스윕 과정 - 선택된 축을 기준으로 진행
vector<shared_ptr<BaseCollider>> activeList;
for (int i = 0; i < colliders.size(); i++)
{
    float currentMax = GetMaxBound(colliders[i], bestAxis);

    for (int j = 0; j < activeList.size(); j++)
    {
        float activeMin = GetMinBound(activeList[j], bestAxis);

        if (activeMin > currentMax)
        {
            activeList.erase(activeList.begin() + j);
            j--;
        }
        else
        {
            potentialCollisions.push_back({
                activeList[j]->GetGameObject(),
                colliders[i]->GetGameObject()
            });
        }
    }

    activeList.push_back(colliders[i]);
}

이 스윕 과정은 Sort and Sweep 알고리즘의 핵심이며 다음과 같이 작동합니다:

1. 액티브 리스트 유지: 현재 처리 중인 축 방향으로 겹칠 가능성이 있는 충돌체만 활성 목록에 유지

2. 불필요한 충돌체 제거: activeMin > currentMax 조건을 통해 더 이상 겹치지 않는 충돌체를 목록에서 제거

3. 효율적 후보 생성: 정렬된 충돌체를 순차적으로 처리하며 잠재적 충돌 쌍만 후보로 추가

이 방식의 효율성은 다음과 같이 설명할 수 있습니다:

• 브루트포스 방식: 모든 가능한 쌍을 비교 - O(n²) 복잡도

• Sort and Sweep 방식: 한 축으로 정렬 후 스윕 - O(n log n + k) 복잡도 (k는 잠재적 충돌 쌍 수)

최악의 경우(모든 객체가 겹치는 경우) O(n²)이 될 수 있지만, 실제 게임에서는 대부분의 객체가 서로 멀리 떨어져 있어 k << n²이 됩니다.

다중 축 필터링을 통한 정확도 향상

// 추가 필터링 - 다른 두 축에서도 겹치는지 확인하여 후보 더 줄이기
vector<pair<shared_ptr<GameObject>, shared_ptr<GameObject>>> filteredCollisions;
for (const auto& pair : potentialCollisions)
{
    shared_ptr<BaseCollider> colliderA = pair.first->GetComponent<BaseCollider>();
    shared_ptr<BaseCollider> colliderB = pair.second->GetComponent<BaseCollider>();

    // 다른 두 축에서도 겹치는지 확인
    bool overlapsOnAllAxes = true;
    for (int axis = 0; axis < 3; axis++)
    {
        if (axis == bestAxis)
            continue; // 이미 검사한 축은 건너뜀

        if (GetMaxBound(colliderA, axis) < GetMinBound(colliderB, axis) ||
            GetMinBound(colliderA, axis) > GetMaxBound(colliderB, axis))
        {
            overlapsOnAllAxes = false;
            break;
        }
    }

    if (overlapsOnAllAxes)
        filteredCollisions.push_back(pair);
}

이 단계에서는 추가적인 최적화를 수행합니다:

1. AABB 테스트 적용: 다른 두 축에 대해서도 겹침 검사를 수행

2. 정확한 필터링: 한 축에서만 겹치는 객체 쌍을 제거하여 후보 수를 크게 줄임

3. 3차원 공간 고려: 실제 3D 공간에서 충돌하려면 모든 축에서 겹쳐야 한다는 원리 적용

이 추가 필터링 과정은 복잡도 측면에서는 O(k)이지만, 정밀 충돌 검사 단계에서 처리해야 할 쌍의 수를 크게 줄여 전체 성능을 향상시킵니다.

최종 정밀 충돌 검사

// 최종 충돌 검사 수행
for (const auto& pair : filteredCollisions)
{
    shared_ptr<BaseCollider> colliderA = pair.first->GetComponent<BaseCollider>();
    shared_ptr<BaseCollider> colliderB = pair.second->GetComponent<BaseCollider>();

    if (colliderA->Intersects(colliderB))
    {
        // 예시(충돌체 제거)
        RemoveGameObject(pair.first);
        RemoveGameObject(pair.second);
    }
}

마지막 단계에서는 실제 정밀 충돌 검사를 수행합니다:

1. 정확한 형상 기반 검사: AABB 테스트를 통과한 후보들에 대해 실제 형상 기반 충돌 테스트 수행

2. 다형성 활용: Intersects 메서드를 통해 충돌체 타입에 맞는 검사 자동 선택

3. 최소한의 계산: 필터링 과정을 통해 이 단계에 도달하는 쌍의 수가 최소화됨

여기서 Intersects 메서드는 충돌체 타입에 따라 다음과 같이 정의되어 있습니다:

// BoxCollider.cpp
bool BoxCollider::Intersects(shared_ptr<BaseCollider>& other)
{
    ColliderType type = other->GetColliderType();

    switch (type)
    {
    case ColliderType::Sphere:
        return _boundingBox.Intersects(dynamic_pointer_cast<SphereCollider>(other)->GetBoundingSphere());
    case ColliderType::Box:
        return _boundingBox.Intersects(dynamic_pointer_cast<BoxCollider>(other)->GetBoundingBox());
    }

    return false;
}

충돌 체크 함수 호출 빈도 조절

void Scene::LateUpdate()
{
    for (const shared_ptr<GameObject>& gameObject : _gameObjects)
    {
        gameObject->LateUpdate();
    }
    Picking();
    UIPicking();
    
    // 물리 업데이트 빈도 제어 (예: 60FPS에서 20FPS로)
    static float accumulatedTime = 0.0f;
    accumulatedTime += TIME.GetDeltaTime();
    
    if (accumulatedTime >= 0.05f)  // 20Hz로 제한
    {
        CheckCollision();
        accumulatedTime = 0.0f;
    }
}

이 구현은 다음과 같은 최적화를 제공합니다:

• CPU 자원 절약: 복잡한 Sort and Sweep 알고리즘 및 AABB 테스트 실행 빈도 감소

• 일관된 물리 동작: 프레임 레이트에 관계없이 일정한 간격으로 물리 연산이 수행되어 안정적인 시뮬레이션 가능

• 프레임 시간 안정화: 무거운 충돌 검사가 매 프레임 실행되지 않아 프레임 시간 편차 감소

오브젝트 피킹

피킹 과정의 시작

void Scene::Picking()
{
    if (!GUI.isSceneView())
        return;

    // ImGui 윈도우가 마우스 입력을 캡처하고 있는지 확인
    ImGuiIO& io = ImGui::GetIO();
    if (io.WantCaptureMouse)
        return;

    Matrix worldMatrix;
    shared_ptr<Camera> cameraComponent = _mainCamera->GetComponent<Camera>();

    Matrix projectionMatrix = cameraComponent->GetProjectionMatrix();
    Matrix viewMatrix = cameraComponent->GetViewMatrix();
    // ...
}

피킹 함수는 우선 씬 뷰 상태를 확인하고, ImGui가 마우스를 사용 중인지 검사합니다. 그 후 현재 카메라의 투영 행렬과 뷰 행렬을 가져옵니다.

마우스 클릭 좌표 획득 및 광선 생성

if (INPUT.GetPublicButtonDown(KEY_TYPE::LBUTTON) && !ImGuizmo::IsUsing() && !ImGuizmo::IsOver())
{
    firstClickedMouseX = INPUT.GetPublicMousePos().x;
    firstClickedMouseY = INPUT.GetPublicMousePos().y;

    const auto& gameObjects = GetGameObjects();

    float minDistance = FLT_MAX;
    picked = nullptr;
    
    // ...게임 오브젝트 순회 및 충돌 검사...
}

마우스 클릭 시 좌표를 저장하고 최소 거리 변수를 초기화합니다.

스크린 좌표에서 광선 생성 - 핵심 부분

실제 Viewport::GetRayFromScreenPoint() 함수를 살펴보면:

Ray Viewport::GetRayFromScreenPoint(float screenX, float screenY, const Matrix& W, const Matrix& V, const Matrix& P, const Vec3& cameraPosition)
{
    Vec3 nearPoint = Unproject(Vec3(screenX, screenY, 0.0f), Matrix::Identity, V, P);
    Vec3 farPoint = Unproject(Vec3(screenX, screenY, 1.0f), Matrix::Identity, V, P);

    Vec3 direction = farPoint - nearPoint;
    direction.Normalize();

    return Ray(cameraPosition, direction);
}

이 함수는 스크린 좌표를 3D 월드 공간의 광선으로 변환합니다:

1. 동일한 스크린 좌표에서 깊이값이 0인 지점(가까운 평면)과 1인 지점(먼 평면)을 3D 공간으로 언프로젝트

2. 이 두 점으로부터 방향 벡터 계산

3. 카메라 위치에서 해당 방향으로 향하는 광선 생성

스크린 -> 월드 좌표 변환의 핵심 Unproject 함수

Vec3 Viewport::Unproject(const Vec3& pos, const Matrix& W, const Matrix& V, const Matrix& P)
{
    Vec3 p = pos;

    p.x = 2.f * (p.x - _vp.TopLeftX) / _vp.Width - 1.f;
    p.y = -2.f * (p.y - _vp.TopLeftY) / _vp.Height + 1.f;
    p.z = ((p.z - _vp.MinDepth) / (_vp.MaxDepth - _vp.MinDepth));

    Matrix wvp = W * V * P;
    Matrix wvpInv = wvp.Invert();

    p = Vec3::Transform(p, wvpInv);
    return p;
}

이 함수는 변환의 핵심으로:

1. 스크린 좌표를 정규화된 장치 좌표(NDC)로 변환 (-1~1 범위)

2. WVP(World-View-Projection) 행렬의 역행렬 계산

3. 정규화된 좌표에 WVP 역행렬을 적용하여 월드 공간 좌표로 변환

광선과 충돌체 검사

for (auto& gameObject : gameObjects)
{
    shared_ptr<BaseCollider> collider = gameObject->GetComponent<BaseCollider>();
    if (collider != nullptr)
    {
        worldMatrix = gameObject->transform()->GetWorldMatrix();
        Ray ray = GP.GetViewport().GetRayFromScreenPoint(firstClickedMouseX, firstClickedMouseY, worldMatrix, viewMatrix, projectionMatrix, _mainCamera->transform()->GetWorldPosition());
        float distance = 0.f;
        if (gameObject->GetComponent<BaseCollider>()->Intersects(ray, OUT distance) == false)
            continue;

        if (distance < minDistance)
        {
            minDistance = distance;
            picked = gameObject;
        }
    }
}

생성된 광선과 각 게임 오브젝트의 충돌체 검사:

1. 광선을 생성하여 충돌체와의 교차 여부 검사

2. 교차한 경우 해당 오브젝트를 선택 후보로 저장

3. 여러 객체와 교차하는 경우 가장 가까운 객체 선택

좌표 변환 과정 핵심 요약

스크린 좌표에서 월드 좌표로의 변환은 다음 수학적 과정을 따릅니다:

1. 스크린 좌표 정규화:

   p.x = 2.f * (p.x - _vp.TopLeftX) / _vp.Width - 1.f;
   p.y = -2.f * (p.y - _vp.TopLeftY) / _vp.Height + 1.f;

1. 깊이값 정규화:

   p.z = ((p.z - _vp.MinDepth) / (_vp.MaxDepth - _vp.MinDepth));

1. 역변환 행렬 적용:

   Matrix wvp = W * V * P;
   Matrix wvpInv = wvp.Invert();
   p = Vec3::Transform(p, wvpInv);

1. 광선 생성:

   Vec3 direction = farPoint - nearPoint;
   direction.Normalize();
   return Ray(cameraPosition, direction);

이 변환 과정을 통해 2D 스크린 상의 마우스 클릭이 3D 월드 공간의 광선으로 변환되고, 이 광선과 충돌하는 오브젝트를 감지하여 피킹을 구현합니다.