AABB에 대해서

AABB(Axis Aligned Bounding Box)

축 정렬 경계 상자라고 직역이 가능하지만, 보통 AABB라고 부른다. 그렇다면 해당 상자를 어떻게 만드는지에 대해 의문일 것이다.

필요한 재료는 두 가지이다.

1. $c$ : 상자의 중점(center)
2. $e$ : 중점에서 각 면까지의 거리들(extents)

$$c = 0.5(v_{min}+v_{max})\tag{1}$$
$$e = 0.5(v_{max}-v_{min})\tag{2}$$

두 값을 구하기 위해서는 우리는 $v_{min}$ 과 $v_{max}$ 를 알아야한다. 기본적으로 물체를 만들 때 vertex 값을 이용해서 물체를 만들게 된다. 이것을 이용해서 AABB의 상자를 만들 수 있다.

 

물체를 그리는 공간은 3차원 공간(x, y, z)으로 이루져 있다. 따라서 $v_{min}$과 $v_{max}$을 구하기 위해서는 3차원 공간에서의 x, y, z축 각각 최솟값과 최댓값을 구해야한다는 이야기다.

 

반복문을 통해서 값을 최신화해가며 구하는 방법이 있지만, std::minmax_element를 통해서 쉽게 값을 도출할 수 있다. 해당 STL함수를 이용하면, 첫 번째 값과 두 번째 값이 각각 최솟값과 최댓값을 가리키는 한 쌍의 반복자를 반환한다.

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{

    std::vector<int> v = {1, 10, 3, 8, 71, 9, 8};

    auto it = std::minmax_element(v.begin(), v.end());
    int min = *it.first;
    int max = *it.second;

    std::cout << min << ", " << max << std::endl;        // 1, 71
    return 0;
}

/////////// you can use std::distance for finding iterator index.
int min_idx = std::distance(v.begin(), it.first);
int max_idx = std::distance(v.begin(), it.second);

특정 축의 최솟값, 최댓값을 찾는 법

using V = typename std::iterator_traits<Iterator>::value_type;

auto x_extremes = std::minmax_element(begin, end,
    [](V const& lhs, V const& rhs) {
        return lhs.position.x < rhs.position.x;
    });

std::iterator_traits<>::value_type은 iterator가 가지고 있는 타입을 추론하는 STL 함수이다. 타입을 알아내 람다함수를 구현할 때 위와 같이 유용하게 사용할 수 있다.

Vector3 lower_left(x_extremes.first->position.x, y_extremes.first->position.y, z_extremes.first->position.z);
Vector3 upper_right(x_extremes.second->position.x, y_extremes.second->position.y, z_extremes.second->position.z);

구한 값들을 이용하여, 3차원 공간에서의 $v_{min}$ 과 $v_{max}$을 도출할 수 있다. 이를 이용해서 $c$와 $e$도 위의 식을 이용해서 도출하면 된다.

Bounding Box(AABB) 만들기

상자를 위한 재료들은 모두 준비했다. 그러면 이제 본격적으로 상자를 만들어 볼 차례이다. DirectXMath에서 제공하는 헤더 중 Bounding Box 관련된 헤더가 있다. 바로, DirectXCollision.h 헤더 파일이다.

 

해당 파일에서 제공하는 구조체는 총 4가지이다.

1. Bounding Sqhere
2. Bounding Box
3. Bounding OrentedBox
4. Bounding Frustum

//-------------------------------------------------------------------------------------
// Axis-aligned bounding box
//-------------------------------------------------------------------------------------
struct BoundingBox
{
    static constexpr size_t CORNER_COUNT = 8;

    XMFLOAT3 Center;            // Center of the box.
    XMFLOAT3 Extents;           // Distance from the center to each side.

    // Creators
    BoundingBox() noexcept : Center(0, 0, 0), Extents(1.f, 1.f, 1.f) {}

    BoundingBox(const BoundingBox&) = default;
    BoundingBox& operator=(const BoundingBox&) = default;

    BoundingBox(BoundingBox&&) = default;
    BoundingBox& operator=(BoundingBox&&) = default;

    constexpr BoundingBox(_In_ const XMFLOAT3& center, _In_ const XMFLOAT3& extents) noexcept
        : Center(center), Extents(extents) {}

    // Methods
    void    XM_CALLCONV     Transform(_Out_ BoundingBox& Out, _In_ FXMMATRIX M) const noexcept;
    void    XM_CALLCONV     Transform(_Out_ BoundingBox& Out, _In_ float Scale, _In_ FXMVECTOR Rotation, _In_ FXMVECTOR Translation) const noexcept;

    void GetCorners(_Out_writes_(8) XMFLOAT3* Corners) const noexcept;
    // Gets the 8 corners of the box

    ContainmentType    XM_CALLCONV     Contains(_In_ FXMVECTOR Point) const noexcept;
    ContainmentType    XM_CALLCONV     Contains(_In_ FXMVECTOR V0, _In_ FXMVECTOR V1, _In_ FXMVECTOR V2) const noexcept;
    ContainmentType Contains(_In_ const BoundingSphere& sh) const noexcept;
    ContainmentType Contains(_In_ const BoundingBox& box) const noexcept;
    ContainmentType Contains(_In_ const BoundingOrientedBox& box) const noexcept;
    ContainmentType Contains(_In_ const BoundingFrustum& fr) const noexcept;

    bool Intersects(_In_ const BoundingSphere& sh) const noexcept;
    bool Intersects(_In_ const BoundingBox& box) const noexcept;
    bool Intersects(_In_ const BoundingOrientedBox& box) const noexcept;
    bool Intersects(_In_ const BoundingFrustum& fr) const noexcept;

    bool    XM_CALLCONV     Intersects(_In_ FXMVECTOR V0, _In_ FXMVECTOR V1, _In_ FXMVECTOR V2) const noexcept;
    // Triangle-Box test

    PlaneIntersectionType    XM_CALLCONV     Intersects(_In_ FXMVECTOR Plane) const noexcept;
    // Plane-box test

    bool    XM_CALLCONV     Intersects(_In_ FXMVECTOR Origin, _In_ FXMVECTOR Direction, _Out_ float& Dist) const noexcept;
    // Ray-Box test

    ContainmentType     XM_CALLCONV     ContainedBy(_In_ FXMVECTOR Plane0, _In_ FXMVECTOR Plane1, _In_ FXMVECTOR Plane2,
        _In_ GXMVECTOR Plane3, _In_ HXMVECTOR Plane4, _In_ HXMVECTOR Plane5) const noexcept;
    // Test box against six planes (see BoundingFrustum::GetPlanes)

    // Static methods
    static void CreateMerged(_Out_ BoundingBox& Out, _In_ const BoundingBox& b1, _In_ const BoundingBox& b2) noexcept;

    static void CreateFromSphere(_Out_ BoundingBox& Out, _In_ const BoundingSphere& sh) noexcept;

    static void    XM_CALLCONV     CreateFromPoints(_Out_ BoundingBox& Out, _In_ FXMVECTOR pt1, _In_ FXMVECTOR pt2) noexcept;
    static void CreateFromPoints(_Out_ BoundingBox& Out, _In_ size_t Count,
        _In_reads_bytes_(sizeof(XMFLOAT3) + Stride * (Count - 1)) const XMFLOAT3* pPoints, _In_ size_t Stride) noexcept;
};

우리가 AABB를 구현하기 위해 사용할 Bounding Box는 위와 같이 구현되어 있다. center와 extents만 잘 구했다면, DirectX::BoundingBox(center, extents)를 통해서 간단하게 BoundingBox를 만들 수 있다.