Octree에 대해 설명해주세요.

이 게시글은 장형기님의 SLAM 기술면접 질문 100선에 대한 제 나름대로의 답을 정리한 것입니다.

---

Octree 정의

Octree는 3차원 공간을 효율적으로 관리하기 위해 사용하는 트리 기반 자료구조입니다.
한 노드가 최대 8개의 자식 노드를 가질 수 있는 구조를 가지고 있고 2차원 공간에서의 Quadtree를
3차원으로 확장한 형태라고 볼 수 있습니다. Octree는 3차원 공간을 작은 구역으로 분할하여,
필요한 연산을 수행할 때 연산량을 대폭 줄이는데 활용됩니다.

Octree 기본 구조

• Root Node

  • 전체 3차원 공간을 하나의 큐브로 간주한 최상위 노드입니다.
    
    

• Children node

  • Root node를 8개의 동일한 크기의 서브 큐브로 분할하여 각각을 자식 노드로 둡니다.

  • 각 자식 노드도 필요에 따라 다시 8개의 하위 구역으로 분할될 수 있습니다.

• Leaf Node

  • 더 이상 하위 노드로 나누지 않거나, 나눌 필요가 없는 노드입니다.

  • 일반적으로 리프 노드에는 해당 구역에 담긴 객체의 목록이나 참고 정보가 저장됩니다.

  
  

Octree의 동작 방식

• Division

  • 노드에 들어 있는 데이터가 특정 기준을 초과하면 노드를 8개의 자식으로 분할합니다.

  • 분할된 각 자식 노드는 자신의 공간 내에 어떤 데이터가 있는지를 다시 확인하고, 같은 방식으로 더 나눌지 결정합니다.

• Insertion

  • 객체나 점을 삽입할 때, 우선 루트 노드에서 시작합니다.

  • 해당 객체가 포함될 수 있는 공간을 찾아가면서, 기준 이상으로 밀도가 높아지면 분할하여 재배치합니다.

• Query

  • 특정 위치나 영역에 관련된 데이터를 검색할 때, Octree를 활용하면 전 공간을 전부 확인할 필요 없이
    관련된 노드만 확인하여 검색 비용을 줄일 수 있습니다.
    
    

Octree의 장단점

• 장점

  • 3D 공간을 작은 구역으로 적절히 분할하여, 충돌 감지나 렌더링 등에서 불필요한 연산을 많이 줄일 수 있습니다.
  • 데이터가 어느 구역에 위치하는지 따라 간단히 노드를 타고 내려가며 관리할 수 있어 구현이 비교적 직관적입니다.
    
    

• 단점

  • 필요 이상으로 너무 많은 노드를 생성할 경우, 자료구조 관리가 오히려 복잡해지고 메모리 사용량이 커짐

  • 데이터가 특정 구역에 몰려 있거나 한쪽에만 치우쳐 있으면, 분할이 한쪽으로 치중되어 트리 깊이가 과도하게 깊어질 수 있습니다.

  ---

  저는 보통 KD-Tree를 사용하는데 Octree도 NeRF나 Gaussian Splatting에서 많이 사용되는 것 같습니다.
  공간 크기를 결정하고 시작해서 SLAM에는 쓸 수 있을까 생각이 들긴 하는데 한 번 고민을 해봐야 할 지점인 것 같습니다.