옥트리(octree)

Octree

정의

옥트리는 삼차원 공간에서 오브젝트를 표현하기 위한 자료구조이다. 이는 자동적으로 그것들을 계층화하여 그룹화하고, 공간 내의 빈 부분에 대한 표현을 피한다.

첫 번째 옥트리 노드는 루트 셀인데, 아래의 그림에서 보이듯이 이는 여덟 개의 연속되는 요소들의 배열이다. 이들 각 요소들은 여덟 개의 연속된 요소들 중 다른 하나를 가리킬 수 있다. 여기에서 각각은 여덟 개의 연속되는 요소들 중 다른 하나를 가리키는 식인데, 이는 특정한 최대 숫자의 레벨에 도달할 때까지 계속된다. 마지막 레벨은 단말 레벨이며, 여기에서 단말 요소나 복셀(voxel)이 저장된다.

 

복셀 검색 원리

위의 그림은 자료 구조가 메모리(왼쪽)와 그것의 삼차원 공간 표현(오른쪽) 사이에서 어떻게 대응되는지를 보여준다. 트리는 여덟 개의 복셀과 다섯 개의 레벨을 가지고 있다. 각 레벨은 서로 다른 색으로 표현된다. 옥트리의 마지막 레벨에 저장되는 여덟 개의 레벨은 분홍색으로 표현된다. 위의 그림의 표는 마지막 셀에 있는 다섯번 째 복셀(index 4)의 좌표를 보여준다. 그것의 좌표는 : 31, 30, 30이며, 후에 오른쪽에서 이진 형식으로 보여진다. 마지막으로 각 좌표 비트와 연관된 각 열도 옥트리의 레벨과 관련이 있다. 각 열의 비트를 합치면, 관련 레벨을 위한 셀의 각 요소에 대한 (테이블의 마지막 열에 나온) 인덱스를 획득하게 된다. 그리고 이것은 트리를 순회하고 검색된 복셀을 찾는 데 사용된다. 이것이 옥트리에서 주어진 복셀을 검색하는 원리이다.

(역주 :

각 열을 합칠 때, x를 0비트, y를 1비트, z를 2비트로 취급하면, 1 + 2 + 4 = 7, 0 + 0 + 4 = 4가 된다. 위의 표에서 열이 나타내는 숫자 0, 1, 2, 3, 4는 복셀의 인덱스를 의미하고 있다.

그런데 표가 이상하다. 비트의 합이 0 ~ 7까지 순서대로 나오는게 맞을텐데 다 7이고 4번째 열만 4다

)

이러한 구조의 주요 이점은 복셀 좌표가 저장되지 않고, 순회되는 요소들의 위치에 의해 암묵적으로 내포된다는 것이다. 이것은 좌표가 저장하기에는 크고 성가신 고해상도 복셀 공간에서 매우 편리하다. 3D 그리드도 복셀 위치를 내포하는 좌표를 가지고 있지만, 대부분의 볼륨이 비어있는 경우에도 볼륨 내의 모든 복셀을 표현해야 한다는 심각한 단점을 가지고 있다.

메모리 점유

위의 단말 레벨에서 모든 셀의 요소들이 셀을 가리키고 있다면, 그 옥트리를 "꽉찬 옥트리(full octree)"라고 부른다. n개의 레벨을 가지고 있는 꽉찬 옥트리는 해상도 2ⁿ x 2ⁿ x 2ⁿ의 정규 3D 그리드와 같은 복셀 개수를 포함한다(예를 들어 꽉찬 옥트리가 5레벨이라면 32 x 32 x 32 해상도를 가진 3D 그리드와 같다). 이런 극단적인 경우에 옥트리는 관련 3D 그리드보다 14% 많은 방(역주 : 메모리공간인듯)을 차지한다. 그러나 복셀이 볼륨 대신에 서피스를 표현한다면, 대부분의 공간은 비어있으며 그것은 옥트리 내에 표현되지 않는다. 이런 경우에 옥트리는 매우 경제적이며, 적은 메모리 소비만으로 고해상도 복셀 공간을 만들 수 있게 해 준다