Cryun's WIKI

Octree

8 min read

개요


center


Octree는 3D 공간을 계층적으로 분할하는 트리 자료구조이다. 각 노드가 최대 8개의 자식 노드를 가지며, 3D 공간을 8개의 동일한 크기의 정육면체로 재귀적으로 분할한다. 게임 엔진과 그래픽스 응용 프로그램에서 공간 쿼리, 충돌 감지, 가시성 판정 등을 효율적으로 수행하기 위해 널리 사용된다.



트리의 노드

  • 루트 노드는 전체 3D 공간
  • 하나의 노드는 8개의 자식 노드
  • 리프 노드는 더이상 분할되지 않는 최소 공간

자식 노드의 인덱싱


center


  • 0 : (-, -, -) → 좌하후
  • 1 : (+, -, -) → 우하후
  • 2 : (-, +, -) → 좌상후
  • 3 : (+, +, -) → 우상후
  • 4 : (-, -, +) → 좌하전
  • 5 : (+, -, +) → 우하전
  • 6 : (-, +, +) → 좌상전
  • 7 : (+, +, +) → 우상전

노드 구조

프로퍼티설명
Bounds경계 영역( Bounding Box), 노드가 표현하는 3D 공간 영역
Children[ 8 ]자식 노드
Objects노드 공간에 포함된 객체 리스트
Depth루트 노드로부터의 깊이 레벨

분할 기준

조건설명일반적인 값
최대 깊이특정 깊이 이상 분할하지 않음8-12 레벨
최소 크기노드 크기가 최소값 이하로 작아지지 않음1.0 ~ 10.0 units
객체 수노드에 포함된 객체가 임계값을 초과하면 분할4-16 객체
공간 밀도객체 밀도가 높은 영역을 더 세밀하게 분할밀도 기반


핵심 알고리즘

자식 인덱스 계산

점 P가 속한 자식 노드의 인덱스는 다음과 같이 계산된다:

GetChildIndex( Point P, Center C ):
    index = 0
 
    if P.x >= C.x then index = index | 1    // X축 양수면 비트 0
    if P.y >= C.y then index = index | 2    // Y축 양수면 비트 1
    if P.z >= C.z then index = index | 4    // Z축 양수면 비트 2
 
    return index

비트 연산을 통한 인덱싱:

  • index & 1: X축 방향 (0=음수, 1=양수)
  • index & 2: Y축 방향 (0=음수, 2=양수)
  • index & 4: Z축 방향 (0=음수, 4=양수)

노드 분할

Split( Node ):
    if Node는 리프가 아님 then return
 
    center = Node의 중심점
    halfSize = Node 크기의 절반
 
    // 8개의 자식 노드 생성
    for i = 0 to 7:
        offset = CalculateOffset( i, halfSize )
        childCenter = center + offset
        childBounds = CreateBounds( childCenter, halfSize / 2 )
 
        Node.Children[i] = CreateNode( childBounds, depth + 1 )
 
    // 기존 객체들을 자식 노드로 재배치
    for each object in Node.Objects:
        childIndex = GetChildIndex( object.Position, center )
        Node.Children[childIndex].Insert( object )
 
    Node.Objects.Clear()

객체 삽입

Insert( Node, Object ):
    // 경계 밖이면 종료
    if not Node.Bounds.Contains( Object.Position ) then
        return
 
    // 리프가 아니면 적절한 자식으로 전달
    if not Node.IsLeaf() then
        childIndex = GetChildIndex( Object.Position, Node.Center )
        Insert( Node.Children[childIndex], Object )
        return
 
    // 리프 노드에 객체 추가
    Node.Objects.Add( Object )
 
    // 분할 조건 확인
    if Node.Objects.Count > MaxObjects and Node.Depth < MaxDepth then
        Split( Node )

영역 검색

Query( Node, QueryBounds, Results ):
    // 교차하지 않으면 종료
    if not Node.Bounds.Intersects( QueryBounds ) then
        return
 
    // 리프 노드면 객체 검사
    if Node.IsLeaf() then
        for each object in Node.Objects:
            if QueryBounds.Contains( object.Position ) then
                Results.Add( object )
        return
 
    // 자식 노드들을 재귀 검색
    for i = 0 to 7:
        if Node.Children[i] exists then
            Query( Node.Children[i], QueryBounds, Results )

레이캐스트

Raycast( Node, Ray ):
    // 레이가 노드와 교차하지 않으면 종료
    if not Node.Bounds.Intersects( Ray ) then
        return false
 
    // 리프 노드면 객체들과 교차 테스트
    if Node.IsLeaf() then
        hitDistance = ∞
        hitObject = null
 
        for each object in Node.Objects:
            distance = object.IntersectRay( Ray )
            if distance < hitDistance then
                hitDistance = distance
                hitObject = object
 
        return hitObject != null
 
    // 자식 노드들을 거리 순으로 검색
    closestHit = ∞
    hitObject = null
 
    for i = 0 to 7:
        if Node.Children[i] exists then
            if Raycast( Node.Children[i], Ray ) then
                if distance < closestHit then
                    closestHit = distance
                    hitObject = result
 
    return hitObject != null


활용

  • 충돌 감지: 가까운 객체들 간의 충돌만 검사 (Broad Phase)
  • 절두체 컬링(Frustum Culling): 카메라 시야 밖의 객체 제거
  • 레이트레이싱: 레이-객체 교차 테스트 가속화
  • 공간 쿼리: 특정 영역 내 객체 빠른 검색
  • LOD 관리: 거리에 따른 디테일 레벨 관리
  • 동적 조명: 광원 영향 범위 내 객체 탐색
  • 파티클 시스템: 파티클 간 상호작용 최적화


특성

복잡도

연산평균최악
삽입O(log N)O(N)
검색O(log N + k)O(N)
삭제O(log N)O(N)
레이캐스트O(log N + k)O(N)
  • k: 결과로 반환되는 객체 개수
  • 공간 복잡도: O(N) ~ O(8N)
  • 트리 깊이: O(log N) (균등 분포 가정)

장단점

장점단점
효율적인 공간 쿼리 O(log N)2D Quadtree보다 구현 복잡
동적 업데이트 용이객체가 적을 때 오버헤드
객체 밀도에 따라 적응적 분할불균등 분포 시 비효율적
메모리 효율적 (필요한 영역만 분할)경계에 걸친 객체 처리 복잡


변형 및 최적화

Loose Octree

노드 경계를 실제 크기보다 크게 설정하여 객체가 여러 노드에 걸치는 문제를 완화한다. 약간의 메모리 오버헤드로 업데이트 성능이 향상된다.


Dynamic Octree

객체 이동 시 트리를 동적으로 재구성하여 객체 분포 변화에 적응한다. 주기적인 리밸런싱으로 성능을 유지한다.


Sparse Octree

빈 노드는 생성하지 않아 메모리 효율성을 극대화한다. 주로 복셀 기반 렌더링에 사용된다.



다른 자료구조와 비교

특성OctreeQuadtreeBVHUniform Grid
차원3D2D3D2D/3D
자식 수842N × N (× N)
분할 방식공간 균등공간 균등객체 적응공간 균등
구현 복잡도중간낮음높음매우 낮음
메모리적응적적응적적응적고정
동적 씬보통보통우수우수
적합한 경우3D 환경지형, 2D동적 객체균등 분포

선택 가이드:

  • 2D 게임, 지형: Quadtree
  • 3D 정적 씬: Octree
  • 3D 동적 씬: BVH 또는 Dynamic Octree
  • 균등 분포: Uniform Grid
  • 복셀 렌더링: Sparse Octree

그래프 뷰

백링크