Octree

개요

Octree는 자식노드가 8개인 트리 자료 구조이다. Octree는 공간상에서 3차원의 공간을 8개의 자식으로 나누는 경우에 많이 이용된다. 팔진트리의 각각의 노드들은 8개의 나누어진 공간을 대표한다.

Octree 생성

Octree의 생성은 주어진 공간을 8등분함으로써 생성된다. Octree를 생성하기 위해 공간을 나누는 축은 꼭 축에 평행할 필요는 없지만 평행하게 만드는 것이 편리함으로 그렇게 하는 편이다. 공간을 어떻게 나눌지는 여러 방법이 있다. 그러나 공간을 균등하게 8등분 하는 것이 편리함으로 많이 쓰인다. 따라서 축에 평행하게 균등하게 8등분으로 나누는 것을 기준으로 설명한다. 공간을 8등분으로 균등하게 나눈뒤, 원소들을 다시 그 공간에 배분하고 재귀적으로 계속 이 작업을 어떤 한계 조건에 이룰 때 까지 반복 함으로써 공간을 나누게 된다. 여기서 주의할 점은 때론 절대로 공간상에 원하는 개수의 삼각형들을 담을 수 없는 경우도 존재함으로 최대 깊이 혹은 최소 공간의 부피등을 정해서 어디까지 나눌 것인지 설정하는 부분이 들어가야 한다는 것이다.

Octree 탐색

Octree의 탐색은 우선 현재 노드가 Leaf Node(말단 노드)인지 검사하는 작업을 시점으로 시작된다. 만약 노드가 Leaf Node라면 그 노드에 존재하는 원소들중 주어진 조건을 만족하는 한 원소를 선택해서 리턴한다. 예를 들어, 만약 레이 트레이싱의 상황이라면 Ray가 각 원소들(여기선 faces)과 교점이 존재하는 지 확인한후 교점이 존재하면 리턴하는 것을 들 수 있다. 만약 리프 노드가 아니라면 각 bounding box들에 다시 Octre 탐색을 재귀적으로 시도한다.

Octree 가속

Octree 또한 여러가지 면에서 가속할 수 있다. 우선 Octree의 각 노드들의 탐색이나 생성을 SIMD를 이용해 병렬적으로 처리하는 것을 들 수 있다. 또한 Octree 탐색에서 리프 노트 탐색시 조건을 만족시키지 않는 bounding box들은 탐색을 시도하지 않음으로써 탐색시간을 줄일 수도 있다. 예를 들어 현재 한 boudning box에서 ray가 삼각형과 충돌했고, 다른 bounding box들이 그 bounding box 보다 더 멀리 떨어져 있다면 그 박스들은 탐색할 필요가 없을 것이다.