Octree

Octree는 3차원 공간 분할 데이터 구조로, 공간을 효율적으로 관리하고 검색할 수 있게 도와줍니다. 이 구조는 3D 공간을 재귀적으로 8개의 작은 부분으로 나누어 관리합니다. 이는 공간 안의 객체들이 위치한 영역을 빨리 찾고 충돌을 검사하는 등의 작업에 매우 유용합니다.

Octree의 주요 특징

• 노드 구조: 각 노드는 최대 8개의 자식 노드를 가질 수 있습니다. 이 자식 노드는 부모 노드를 8개의 동일한 크기의 구역으로 나눕니다.
• 분할 기준: 공간이 일정 기준을 넘을 때마다, 또는 공간에 포함된 객체 수가 특정 수를 넘을 때 분할이 발생합니다.
• 효율성: 충돌 검사나 범위 검색을 수행할 때, 불필요한 계산을 줄여줍니다.

Octree의 용도

• 충돌 검출: 3D 게임이나 시뮬레이션에서 물체 간의 충돌을 빠르게 검사하는 데 사용됩니다.
• 렌더링 최적화: 카메라가 렌더링할 필요가 없는 객체를 쉽게 무시할 수 있도록 도와줍니다.
• 공간 검색: 특정 위치에 있는 객체들을 빠르게 찾는 데 유용합니다.

Octree 외의 공간 분할 구조

• QuadTree: 2차원 공간을 4개의 영역으로 분할하는 구조. 주로 2D 공간에서 사용됩니다.
• KD-Tree: k-차원 공간을 분할하는 구조. 다양한 차원의 공간에서 사용할 수 있으며, 주로 점의 검색에 사용됩니다.
• BVH (Bounding Volume Hierarchy): 객체들을 포함하는 경계 상자를 계층적으로 구조화하여 충돌 검출 및 렌더링 최적화에 사용됩니다.
• R-Tree: 다차원 공간에서 최소 경계 사각형(MBR)을 사용하여 공간을 분할하고, GIS(지리정보시스템)에서 주로 사용됩니다.