<aside> <img src="/icons/list_gray.svg" alt="/icons/list_gray.svg" width="40px" />

목차

</aside>

개념

옥트리(Octree)는 각 내부 노드가 정확히 8개의 자식 노드를 갖는 트리 자료구조입니다. 3차원 공간을 8개의 균등한 영역으로 재귀적으로 분할하는 데 가장 자주 사용됩니다.

이진 트리가 1차원, 쿼드 트리가 2차원이라면, 옥트리는 3차원 공간을 효율적으로 관리하는데 사용되는 자료구조입니다

구조

기본 구성 요소

• 루트 노드(Root Node): 전체 3차원 공간을 나타내는 최상위 노드
• 자식 노드(Children Node): 루트 노드를 8개의 동일한 크기의 서브 큐브로 분할하여 각각을 자식 노드로 둡니다
• 리프 노드(Leaf Node): 더 이상 하위 노드로 나누지 않거나, 나눌 필요가 없는 노드로, 일반적으로 해당 구역에 담긴 객체의 목록이나 참고 정보가 저장됩니다

공간 분할 방식

옥트리는 입방체(정육면체)로 감싸인 3차원 공간을 표현하는데 이상적인 구조로, 공간을 분할하기 위해 쓰이는 경우 각 노드의 자식들은 부모 입방체를 8등분하는 동일한 입방체들이 됩니다.