옥트리

📌 옥트리(Octree) 개념과 게임에서의 활용
✅ 옥트리(Octree)란?
옥트리(Octree)는 3차원 공간을 8개의 균등한 영역(Octants)으로 재귀적으로 분할하는 자료구조입니다.
이진 트리(Binary Tree)가 1차원, 쿼드트리(Quadtree)가 2차원이라면, 옥트리는 3차원 공간을 효율적으로 관리하는데 사용됩니다.

🛠 옥트리가 게임에서 사용되는 경우
공간 분할 (Spatial Partitioning)

광대한 맵에서 충돌 검사, 렌더링 최적화
예: 오픈월드 게임에서 먼 개체는 비활성화, 가까운 개체만 활성화
충돌 감지 (Collision Detection)

물리 엔진에서 충돌을 빠르게 탐색하기 위해 사용
예: 총알이 날아갈 때, 전체 맵이 아니라 특정 영역만 충돌 검사
레이트레이싱 (Ray Tracing)

광선이 특정 물체에 충돌하는지 검사할 때 옥트리 구조를 사용하면 빠르게 탐색 가능
LOD(Level of Detail) 최적화

카메라 거리에 따라 세밀한 모델을 로드하거나 해상도를 조정할 때 사용
🖥 C++로 옥트리 구현 예제
✅ 1. 옥트리 노드 구조 정의

struct OctreeNode
{
    FVector Center;   // 노드의 중심 좌표
    float Size;       // 노드의 크기
    std::vector<AActor*> Objects;  // 이 노드에 포함된 객체들
    OctreeNode* Children[8];       // 8개의 하위 노드 (옥탄트)
    
    OctreeNode(FVector InCenter, float InSize)
        : Center(InCenter), Size(InSize)
    {
        for (int i = 0; i < 8; i++)
            Children[i] = nullptr;
    }
};

✅ 2. 옥트리 클래스 생성

class Octree
{
public:
    OctreeNode* Root;

    Octree(FVector WorldCenter, float WorldSize)
    {
        Root = new OctreeNode(WorldCenter, WorldSize);
    }

    ~Octree()
    {
        DestroyNode(Root);
    }

    void DestroyNode(OctreeNode* Node)
    {
        if (!Node) return;
        for (int i = 0; i < 8; i++)
        {
            DestroyNode(Node->Children[i]);
        }
        delete Node;
    }

    // 객체 추가 (재귀적으로 적절한 옥트리 노드에 삽입)
    void Insert(AActor* Object, FVector Position)
    {
        InsertRecursive(Root, Object, Position);
    }

    void InsertRecursive(OctreeNode* Node, AActor* Object, FVector Position)
    {
        if (!Node) return;

        // 만약 노드가 충분히 작다면, 현재 노드에 추가
        if (Node->Size <= 100.0f) 
        {
            Node->Objects.push_back(Object);
            return;
        }

        // 적절한 옥탄트를 찾아서 삽입
        int Index = GetOctant(Node->Center, Position);
        if (!Node->Children[Index])
        {
            FVector NewCenter = GetChildCenter(Node->Center, Node->Size, Index);
            Node->Children[Index] = new OctreeNode(NewCenter, Node->Size / 2);
        }

        InsertRecursive(Node->Children[Index], Object, Position);
    }

    // 특정 위치가 어느 옥탄트에 속하는지 계산
    int GetOctant(FVector NodeCenter, FVector Position)
    {
        int Index = 0;
        if (Position.X >= NodeCenter.X) Index |= 1;
        if (Position.Y >= NodeCenter.Y) Index |= 2;
        if (Position.Z >= NodeCenter.Z) Index |= 4;
        return Index;
    }

    // 자식 노드의 새로운 중심점 계산
    FVector GetChildCenter(FVector ParentCenter, float ParentSize, int Index)
    {
        float Offset = ParentSize / 4;
        return ParentCenter + FVector(
            (Index & 1) ? Offset : -Offset,
            (Index & 2) ? Offset : -Offset,
            (Index & 4) ? Offset : -Offset
        );
    }
};

✅ 3. 언리얼 엔진에서 옥트리 활용

void AMyGameMode::SpawnObjects()
{
    // 월드 크기 10000x10000x10000 기준으로 옥트리 생성
    Octree MyOctree(FVector(0, 0, 0), 10000.0f);

    for (int i = 0; i < 100; i++)
    {
        FVector SpawnLocation = FVector(FMath::RandRange(-5000, 5000), 
                                        FMath::RandRange(-5000, 5000), 
                                        FMath::RandRange(-5000, 5000));

        AActor* NewActor = GetWorld()->SpawnActor<AActor>(ActorClass, SpawnLocation, FRotator::ZeroRotator);
        MyOctree.Insert(NewActor, SpawnLocation);
    }
}

🎯 정리
✅ 옥트리는 3D 공간을 8개로 나누어 관리하는 자료구조
✅ 게임에서 충돌 감지, LOD 최적화, 레이트레이싱 등에 활용
✅ 객체 삽입, 탐색, 충돌 감지 성능을 향상시키는 데 유용
✅ C++로 옥트리를 구현하면 게임 성능을 최적화할 수 있음

🎮 특히 오픈월드 게임이나 대규모 오브젝트가 있는 환경에서 필수적으로 활용되는 개념! 🚀