압축 쿼드트리(Compressed Quadtrees)
쿼드트리에서 분할된 각 셀에 해당하는 노드를 모두 저장하다 보면, 실제 데이터가 없는 빈 노드까지 대량으로 저장하게 되어 트리가 불필요하게 비대해질 수 있습니다. 이런 희소(sparse) 트리의 크기를 줄이는 방법은, 잎(leaf)에 의미 있는 데이터를 지닌 서브트리, 즉 '중요 서브트리'만 저장하는 것입니다.
여기서 한 걸음 더 나아갈 수도 있습니다. 중요 서브트리만 남긴 상태에서 가지치기를 진행하면, 중간 노드의 차수가 2(부모로 가는 링크 하나, 자식으로 가는 링크 하나)인 긴 경로를 제거할 수 있습니다. 실제로는 경로의 시작점 노드 U만 저장하고(삭제된 노드들을 표현하는 메타데이터를 함께 연결), 경로 끝에 뿌리를 둔 서브트리를 U에 붙이면 됩니다. 다만 이렇게 압축한 트리라도 '나쁜' 입력 점들이 주어지면 여전히 선형(linear) 높이를 가질 수 있다는 점에 유의해야 합니다.
트리의 상당 부분을 잘라냈음에도, Z-order 곡선(Z-order curve)을 활용하면 로그 시간(logarithmic-time)의 삽입·삭제·탐색을 달성할 수 있습니다. Z-order 곡선은 전체 쿼드트리의 각 셀(따라서 압축 쿼드트리의 셀도 마찬가지)을 O(1) 시간에 1차원 직선 위의 값으로 변환하며, 역변환 역시 O(1)에 가능합니다. 이를 통해 원소들 사이에 전체 순서(total order)가 만들어지므로, 쿼드트리를 순서 집합(ordered set)용 자료구조에 트리 노드 형태로 저장할 수 있습니다.
논의를 이어가기 전에 몇 가지 합리적인 가정을 명확히 해두겠습니다. 첫째, 두 실수 α, β ∈ [0,1]이 이진수로 주어졌을 때 서로 다른 첫 번째 비트의 인덱스를 O(1) 시간에 계산할 수 있어야 합니다. 둘째, 쿼드트리에서 두 점(또는 셀)의 최소 공통 조상을 O(1) 시간에 구하고 두 대상의 상대적 Z-order를 정할 수 있어야 합니다. 셋째, floor 함수를 O(1) 시간에 계산할 수 있어야 합니다. 이러한 가정 아래에서 주어진 점 Q에 대한 점 위치 찾기(point location, 즉 Q를 포함하게 될 셀 찾기), 삭제, 삽입 연산은 모두 O(log n) 시간에 수행할 수 있습니다. 이는 기반이 되는 순서 집합 자료구조에서 탐색하는 데 걸리는 시간과 동일합니다.
압축 쿼드트리에서의 점 위치 찾기
주어진 점 Q가 속한 셀을 압축 트리에서 결정하는 절차는 다음과 같습니다.
- Z-order에서 Q보다 앞서는 기존 셀을 압축 트리에서 찾습니다. 이 셀을 V라고 부릅니다.
- Q ∈ V가 성립하면 V를 반환합니다.
- 그렇지 않다면, 압축되지 않은 쿼드트리였다면 점 Q와 셀 V의 최소 공통 조상이 되었을 셀을 찾습니다. 이 조상 셀을 U라고 부릅니다.
- Z-order에서 U보다 앞서는 기존 셀을 압축 트리에서 찾아 반환합니다.
세부 사항을 생략하고 요약하면, 삽입과 삭제는 먼저 대상에 대한 점 위치 찾기를 수행한 뒤 실제 연산을 실행하는 방식으로 처리합니다. 이 과정에서 필요에 따라 노드를 생성·삭제하면서 트리 구조를 적절히 재구성하는 작업이 반드시 수반되어야 합니다.
옥트리(Octree)
옥트리는 각 내부 노드가 정확히 여덟 개의 자식을 갖는 트리 자료구조로 정의됩니다.
옥트리는 3차원 공간을 여덟 개의 옥턴트(octant)로 재귀적으로 세분화함으로써 공간을 분할(partition)하는 데 가장 널리 사용됩니다.
옥트리는 쿼드트리의 3차원 유사체로 취급됩니다. 이름은 oct + tree에서 파생되었지만, 통상 't'를 하나만 써서 "octree"로 표기한다는 점에 유의하세요.
옥트리는 3D 그래픽과 3D 게임 엔진에서 자주 활용됩니다.
공간 표현
옥트리의 각 노드는 자신이 나타내는 공간을 여덟 개의 옥턴트로 분할하는 역할을 담당합니다. 구현 방식에 따라 대표적인 두 가지 형태가 있습니다.
PR(Point Region) 옥트리: 노드가 명시적인 3차원 점 하나를 저장합니다. 이 점은 해당 노드 분할의 '중심(center)' 역할을 하며, 여덟 자식 각각의 한쪽 모서리(corner)를 지정합니다.
MX(Matrix-based) 옥트리: 분할 점이 별도로 저장되지 않고, 노드가 나타내는 공간의 중심으로 암묵적으로 정해집니다.
PR 옥트리의 루트 노드는 무한 공간을 나타낼 수 있습니다. 반면 MX 옥트리의 루트 노드는 암묵적 중심들이 잘 정의되도록 유한하고 경계가 명확한 공간을 나타내야 합니다.
옥트리의 주요 활용 분야
- 3D 컴퓨터 그래픽에서의 LOD(Level of Detail) 렌더링
- 공간 인덱싱(spatial indexing)
- 최근접 이웃 탐색(nearest neighbor search)
- 3차원 환경에서의 효율적인 충돌 감지(collision detection)
- 유한 요소 해석(finite element analysis)
- 희소 복셀 옥트리(sparse voxel octree)
- 상태 추정(state estimation)
- 집합 추정(set estimation)