옥트리(Octree)

옥트리는 각 내부 노드(리프 노드가 아닌)가 8개의 자식 노드를 가지는 트리 구조이다. 주로 게임에서 충돌 감지와 같은 용도로 활용된다.

문제 상황

3D 공간에 여러 객체를 저장해야 하는 상황을 생각해 보자. 각 객체는 X, Y, Z 좌표로 특정 위치에 있다. 그리고 특정 3D 영역 내에 어떤 객체가 있는지 확인해야 한다. 가장 간단한 방법은 모든 점을 배열에 저장한 후, 각 점을 하나씩 순회하면서 해당 영역에 속하는지 확인하는 것이다. 하지만 이 방법은 O(n)의 시간 복잡도를 가진다.

더 나은 접근 방식

옥트리는 일반적으로 3차원 공간을 재귀적으로 8개의 영역으로 분할하여 공간을 나누는 데 사용한다. 옥트리를 활용해 값을 저장하는 방법을 살펴보자.

트리의 각 노드는 박스 형태의 영역을 나타낸다. 리프 노드는 해당 영역 내의 단일 지점과 그 지점에 할당된 객체 배열을 저장한다.

동일한 영역 내 다른 지점에 객체가 추가되면, 리프 노드는 내부 노드로 변환되고 8개의 자식 노드(리프)가 추가된다. 이전에 노드에 포함된 모든 지점은 해당 자식 노드로 전달되어 저장된다. 따라서 실제 지점과 값은 리프 노드에만 포함된다.

주어진 영역에 속하는 지점을 찾기 위해, 트리를 위에서 아래로 탐색하며 적합한 지점을 노드에서 수집할 수 있다.

점을 추가하거나 검색하는 작업은 최악의 경우 여전히 O(n)의 시간이 걸릴 수 있다. 트리가 어떤 방식으로도 균형을 이루지 않기 때문이다. 그러나 평균적으로는 O(log n)에 가까운 속도로 훨씬 빠르게 동작한다.

더 알아보기

위키백과에서 더 많은 정보를 확인할 수 있다.
Apple의 GKOctree 구현도 참고하자.

Swift Algorithm Club을 위해 Jaap Wijnen이 작성함
Timur Galimov의 Quadtree 구현과 Apple의 GKOctree 구현에서 큰 영감을 받음