옥트리

옥트리(Octree) 개념
옥트리(Octree)는 3D 공간을 8개의 균등한 크기의 서브 큐브(옥탄트)로 분할하는 트리 구조입니다. 공간 분할을 통해 충돌 감지, 광선 추적, LOD(Level of Detail) 관리, 공간 파티셔닝 등의 최적화에 활용됩니다.

게임에서의 사용 사례
충돌 감지(Collision Detection)
많은 오브젝트가 존재하는 3D 공간에서 충돌 체크 범위를 좁혀 연산량을 줄임.
광선 추적(Ray Tracing)
빛의 경로를 트리 구조로 나누어 효율적으로 계산.
LOD(Level of Detail) 관리
플레이어의 시점에 따라 디테일이 높은 오브젝트만 렌더링.
공간 파티셔닝(Spatial Partitioning)
AI 탐색, 군집 거동, 네비게이션 메쉬 최적화 등에 활용.
C++ 예제 코드: 기본적인 옥트리 구현
아래는 3D 공간에서 점(Point)을 저장하는 옥트리 구현 예제입니다.

1. OctreeNode 클래스 (옥트리 노드)

#include <iostream>
#include <vector>
#include <memory>

struct Point3D {
    float x, y, z;
};

class OctreeNode {
public:
    Point3D center;  // 노드의 중심 좌표
    float halfSize;  // 한 변의 길이의 절반
    std::vector<Point3D> points;  // 현재 노드에 저장된 점들
    std::unique_ptr<OctreeNode> children[8];  // 8개의 자식 노드

    OctreeNode(Point3D c, float hSize) : center(c), halfSize(hSize) {}

    bool contains(const Point3D& p) {
        return (p.x >= center.x - halfSize && p.x <= center.x + halfSize &&
                p.y >= center.y - halfSize && p.y <= center.y + halfSize &&
                p.z >= center.z - halfSize && p.z <= center.z + halfSize);
    }

    void subdivide() {
        if (children[0] != nullptr) return; // 이미 분할된 경우 무시

        float newHalf = halfSize / 2.0f;
        for (int i = 0; i < 8; ++i) {
            float dx = (i & 1) ? newHalf : -newHalf;
            float dy = (i & 2) ? newHalf : -newHalf;
            float dz = (i & 4) ? newHalf : -newHalf;
            children[i] = std::make_unique<OctreeNode>(Point3D{center.x + dx, center.y + dy, center.z + dz}, newHalf);
        }
    }

    void insert(const Point3D& p) {
        if (!contains(p)) return;

        if (points.size() < 4) {  // 노드에 4개 이하의 점이면 저장
            points.push_back(p);
            return;
        }

        if (children[0] == nullptr) subdivide(); // 자식 노드가 없으면 분할

        for (auto& child : children) {
            if (child->contains(p)) {
                child->insert(p);
                return;
            }
        }
    }

    void print() {
        std::cout << "Node at (" << center.x << ", " << center.y << ", " << center.z 
                  << ") with size " << halfSize * 2 << " containing " << points.size() << " points.\n";

        for (auto& child : children) {
            if (child) child->print();
        }
    }
};

2. 옥트리 생성 및 점 추가

int main() {
    OctreeNode root({0, 0, 0}, 10.0f);  // 중심 (0,0,0) 반경 10인 옥트리

    std::vector<Point3D> points = {
        {1, 1, 1}, {-2, -3, 4}, {5, 5, 5}, {-6, -6, -6}, {2, 2, 2},
        {-8, 8, 8}, {3, 3, 3}, {-1, -1, -1}, {7, 7, 7}, {0, 0, 0}
    };

    for (const auto& p : points) {
        root.insert(p);
    }

    root.print();  // 트리 출력
    return 0;
}

📌 코드 설명
OctreeNode 클래스는 중심 좌표(center)와 공간 크기(halfSize)를 가진다.
insert() 함수에서:
4개 이하의 점이면 현재 노드에 저장.
초과하면 subdivide()를 호출해 자식 노드를 생성하고 적절한 곳에 배치.
print() 함수로 옥트리 구조를 확인 가능.