Octree

Octree는 3차원 공간을 재귀적으로 분할하여 표현하는 트리 기반의 데이터 구조로, 3차원 공간을 8개의 동일한 크기의 정육면체(옥탄트)로 재귀적으로 분할하는 트리 구조이다.
각 노드는 공간의 한 영역을 나타내며, 필요에 따라 더 작은 영역으로 세분화된다.

![Octree](Octree2.png “https://ko.wikipedia.org/wiki/%ED%8C%94%EC%A7%84%ED%8A%B8%EB%A6%AC#/media/%ED%8C%8C%EC%9D%BC:Octree2.png)

특징

  1. 계층적 구조: 공간을 재귀적으로 분할하여 계층적으로 표현한다.
  2. 적응적 해상도: 필요한 영역만 세밀하게 분할하여 효율적인 공간 표현이 가능하다.
  3. 8분할: 각 노드는 최대 8개의 자식 노드를 가질 수 있다.

장점

  1. 효율적인 공간 표현: 복잡한 3차원 구조를 효율적으로 표현할 수 있다.
  2. 빠른 검색: 계층 구조를 활용하여 특정 영역의 빠른 검색이 가능하다.
  3. 메모리 효율성: 균일하지 않은 데이터 분포에 대해 메모리를 효율적으로 사용한다.

단점

  1. 구현 복잡성: 구현과 관리가 상대적으로 복잡할 수 있다.
  2. 메모리 오버헤드: 트리 구조로 인한 추가적인 메모리 사용이 발생할 수 있다.
  3. 불균형 가능성: 데이터 분포에 따라 트리가 불균형해질 수 있다.

응용

  1. 3D 컴퓨터 그래픽스: 3D 모델링, 렌더링, 충돌 감지 등에 사용된다.
  2. 로보틱스: 3D 환경 매핑 및 경로 계획에 활용된다.
  3. 게임 개발: 3D 게임 월드의 효율적인 표현과 관리에 사용된다.
  4. 과학 시뮬레이션: 대규모 3D 시뮬레이션에서 공간 데이터 관리에 활용된다.

동작 원리

  1. 초기화: 전체 3D 공간을 포함하는 루트 노드로 시작한다.
  2. 분할: 필요에 따라 각 노드를 8개의 자식 노드로 분할한다.
  3. 데이터 할당: 각 노드에 해당 영역의 데이터를 할당한다.
  4. 재귀적 분할: 특정 조건(예: 데이터 밀도, 깊이 제한)을 만족할 때까지 2-3 과정을 반복한다.

구성 요소

  1. 노드: 3D 공간의 한 영역을 나타내며, 데이터와 자식 노드에 대한 참조를 포함한다.
  2. 루트 노드: 전체 3D 공간을 나타내는 최상위 노드이다.
  3. 내부 노드: 8개의 자식 노드를 가질 수 있는 중간 노드이다.
  4. 리프 노드: 더 이상 분할되지 않는 최하위 노드로, 실제 데이터를 저장한다.

구현 방식

Octree의 기본적인 구현은 재귀적인 트리 구조를 사용한다.
다음은 Python을 사용한 간단한 Octree 구현 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class OctreeNode:
    def __init__(self, center, size):
        self.center = center
        self.size = size
        self.data = None
        self.children = [None] * 8

    def is_leaf(self):
        return all(child is None for child in self.children)

class Octree:
    def __init__(self, center, size):
        self.root = OctreeNode(center, size)

    def insert(self, point, data):
        def _insert(node, point, data):
            if node.is_leaf():
                if node.data is None:
                    node.data = data
                else:
                    self._split(node)
                    _insert(node, point, data)
            else:
                octant = self._get_octant(node, point)
                if node.children[octant] is None:
                    new_size = node.size / 2
                    new_center = [
                        node.center[i] + new_size * (1 if i == octant else -1)
                        for i in range(3)
                    ]
                    node.children[octant] = OctreeNode(new_center, new_size)
                _insert(node.children[octant], point, data)

        _insert(self.root, point, data)

    def _split(self, node):
        for i in range(8):
            new_size = node.size / 2
            new_center = [
                node.center[j] + new_size * (1 if j == i else -1)
                for j in range(3)
            ]
            node.children[i] = OctreeNode(new_center, new_size)

    def _get_octant(self, node, point):
        return sum(
            (point[i] > node.center[i]) << i
            for i in range(3)
        )

# 사용 예시
octree = Octree([0, 0, 0], 1)
octree.insert([0.1, 0.2, 0.3], "Data1")
octree.insert([0.6, 0.7, 0.8], "Data2")

참고 및 출처