Chapter 6 Bounding Volume Hierarchies (실시간 충돌탐지)

Chapter 6 Bounding Volume Hierarchies
오브젝트들을 bounding volumes으로 감싸고, object geometry를 테스트하기 전에 bonuding volumes에 대한 테스트를 수행하는 것은 중요한 성능 향상을 만들어낼 수 있다. 그러나, 그 테스트 그 자체로 간단하게 될지라도, 같은 수의 pairwise tests가 여전히 수행되어야 한다. 그 asymptotic time complexit는 같게 남아있고, bounding volume의 사용은 상수 요소로 그 상황을 향상시킨다. bounding volumes을 bounding volume hierarchy(BVH) 라고 불리는 트리 hierarchy로 배치하여, 그 시간 복잡도는 수행되는 테스트 개수가 logarithmic하게 줄어들 수 있다.

bounding volumes의 원래의 집합은 이 bounding volume hierarchy인 tree의 leaf nodes를 형성한다. 이러한 노드들은 그러고나서 작은 집합으로서 그룹지어지고, 더 큰 bounding volumes으로 둘러싸여진다. 차례로 이러한 것들은 또한 그룹지어 지고, 재귀의 방식으로 다른 더 큰 bounding volumes 내에서 둘러싸여진다. 결과적으로 트리의 꼭대기에 단일의 bounding volume을 가진 자료구조를 결과로 만든다. 그림 6.1은 5개의 오브젝트들로 구성된 하나의 작은 AABB hierarchy를 보여준다.

준비가 된 hierarchy와 함께, 충돌 탐지 동안 자식들은 만약 그것들의 부모 volume이 교차되지 않는다면 시험될 필요가 없다. 그 같은 bounding volume hierarchies는 또한 예를들어 scene graphs와 ray tracing에서 and view-frustum culling을 위해서 사용된다.

bounding volume hierarchies와 spatial partitioning schemes (see Chapter 7)을 비교하자면, 주된 차이는 BVH안에 두 개 이상의 volumes는 같은 공간을 덮을 수 있고, 오브젝트들은 일반적으로 단일의 volume안에 삽입된다. 대조적으로, spatial partioning scheme에서, 그 partitions는 분리되어있고, spatial partitioning 에 포함된 오브젝트들은 일반적으로 두 개 이상의 파티션에 나타내어지는 것이 허용된다.

한 부모 노드의 bounding volume이 필수적으로 그것의 자식 노드들의 bounding volume을 감쌀 필요가 없는 것을 주목하는 것이 중요하다. 비록 종종 이 부모 자식 특성이 유효한 hierarchies를 구성하는 게 더 쉬울지라도, 그 부모 bounding volume은 그것의 자식들의 subtrees에서 포함된 오브젝트 primitives를 둘러쌀 필요가 있다.

hierarchies를 만드는 한 가지 접근법은 디자이너 또는 아티스트들이 수동으로 그것들을 그것들의 modeling hierarchies의 일부로서 만들게 하는 것이다. 그러나 트리를 수동으로 만드는 것은 이상적이다. 첫 째로, 디자이너는 공간적으로 보다는 함수적으로 생각하는 경향이 있다. 결과적으로, 예를들어 한 큰 기계적 설계의 모든 너트와 볼트가 같은 노드 아래에 그룹지어질 가능성이 높다. 그러한 그룹핑은 충돌 탐지 관점에서 좋지 않다. 둘 째로, 그 hierarchy는 또한 잘못된 장소에서 너무 shallow하거나 deep 하는 둘 중 하나의 가능성이 높다. 디자이너의 모델링 hierarchy는 - 그리고 거의 그래야 한다 - 쉬운 편집을 위해 구성되고, 효율적인 교차 쿼리를 가능하게 하지 않는다. 비록 디자이너들이 이론적으로 그것들의 hierarchies가 좀 더 공간 지향적이고 충돌 queries에 더 적합하도록 할 수 있을지라도, 그들의 시간에 효과적인 사용이 안될 가능성이 높다. 더 좋은 솔루션은 가능하면, 제공된 모델들로부터 hierarchies의 생성을 자동화하는 것이다. 그러한 자동화는 항상 사소한 프로세스는 아니고, 다음 섹션에서 보여주듯이 고려해야할 많은 이슈들이 있다.

6.1 Hierarchy Design Issues
bounding volume hierarchy를 구성하는 많은 방법들이 있다. 다음 섹션은 좋은 hierarchies를 위한 많은 바람직한 특징들의 개요를 보여준다. 다양한 hierarchical schemes에 대한 queries의 비용 비교를 돕는 generic cost function은 Section 6.1.2에서 발견된다. 마지막으로, Section 6.1.3은 무슨 tree degree가 가장 좋은 hierarchy를 제공하는지에 대한 질문을 이야기 한다.

6.1.1 Desired BVH Characteristics
bounding volumes과 유사하게, BVH에 대한 몇 가지 요구되는 특징들이 제안된다:

• 어떤 주어진 subtree에 퐘된 노드들은 서로 가까워야 한다. explicitly하게 nearness를 정의하는 것 없이, 트리 노드들이 더 낮을 수록 그것들은 서로에 더가까워야 한다.
• hierarchy에서 각 노드는 minimal volume이여야 한다.
• 모든 bounding volumes의 합은 minimal이여야 한다.
• hiearchy의 root의 가까이에 있는 노드들에 대해 더 큰 관심이 주어져야 한다. 트리의 root에 가까이 있는 node들을 쳐내는 것은 더 깊은 노드의 제거가 하는 것보다 고려할 더 많은 오브젝트들을 제거한다.
• sibling nodes들의 overlap volume은 최소여야 한다.
• hierarchy는 그것의 노드 구조와 그것의 내용에 관하여 균형있어야 한다. balacing하는 것은 가능한한 많은 hierarchy가 pruned되도록 한다, 한 branch가 traverse되지 않을 때 마다.

실시간 프로그램에 대해, 특히 게임들에서, 이전 리스트에 대해 중요한 추가물은 쿼리에 대한 worst-case time이 average-case query time보다 더 나쁘지 않아야 한다는 요구이다. 이 요구는 특히 콘솔 게임에 중요한데, 왜냐하면 고정 프레임 율이 보통 요구되기 떄문이다 (일반적으로 60fps).

부가적으로, hierarchy가 자동적으로 사용자 개입없이 자동적으로 생성될 수 있는 것이 바라진다. 실시간 프로그램에 대해, 대부분의 hierarchies는 보통 전처리 단계에서 생성된다, 런타임에서가 아니라. 게임에 대해, 구성할 미리 연산된 구조를 과도하게 기다리는 것은 level construction과 design에 해로운 영향을 가질 수 있다. 그러므로, precomputation이 그 구성하는 시간을 덜어줄지라도, 2차 복잡도와 그 이상의 중요한 알고리즘들은 여전히 preprocessing use에 너무 느릴 가능성이 높다. 만약 한 hierarchy가 런타임에 구성된다면, 그 hierarchy를 구성하는 것은 또한 그 자체에 대해 지불해야 하는데, 구성을 위해 취해지는 시간이 hierarchy를 사용하여 절약된 시간 보다 더 작게 한다는 점에서이다.

마지막으로, 충돌 탐지를 다루는데 있어서 종종 빛나는 한 매우 중요한 요소는 BVH를 나타내는데 사용되는 자료구조에 대한 총 메모리 요구사항이다. 예를들어, 콘솔 게임들은 대강 충돌 데이터에 대한 이용가능한 메모리의 1/10을 할당한다. 반면에 다음 세대 콘솔 시스템에 대해 내장 메모리는 각 세대에 대해 증가하는 반면에, 충돌 탐지 데이터에 대해 할당되는 비율은 대강 변하지 않고 남을 가능성이 높다. 왜냐하면 다른 시스템에 대한 메모리 요구사항 (렌더링, 애니메이션, 그리고 AI) 또한 비례하게 성장할 가능성이 높기 때문이다. 이러한 메모리 제약은 모든 고려되는 충돌 탐지 시스템에 대해 어려운 제약을 설정한다.

6.1.2 Cost Functions
몇 사람들은 BVH queries의 예상되는 비용에 기여하는 다양한 부분들을 인식하려는 수식들을 생각해냈다. [Weghorst84]에서 처음 보여진 cost formula와 [Gottschalk96]에 의해 BVH를 위해 적용되고 [Klosowski98]과 [He99]에 의해 차후에 다듬어진 것은



여기에서 T는 두 hierarchies를 교차하는 총 비용이고, N_v는 overlap을 위해 테스트되는 BV pairs의 개수이고, C_v는 overalp을 위한 BV의 한 쌍을 테스트하는 비용, N_p는 테스트되는 primitive paris의 개수, C_p는 한 primitive pair를 테스트하는 비용, N_u는 업데이트 될 필요가 있는 노드의 개수, C_u는 각 그러한 노드를 업데이트 하는 비용, 그리고 필요하다면, C_o는 one-time processing의 비용이다 (오브젝트들 사이의 좌표변환 같은).

이러한 변수들 중에서, 예를들어 N_v와 N_p는 bounding volume을 그 오브젝트에 가능한 꽉 맞추도록 하여 최소화 되어야 한다. overlap tests를 가능한 빠르게 하여, C_v와 C_p는 최소화된다. 불행하게도, bounding volume을 일반적으로 더 꽉 맞게 하는 것은 overlap test를 수행하는 시간을 증가시킨다. 동시에, 더 꽉 맞는 bounding volume은 더 적은 intersection tests를 만들어낼 가능성이 높다. 일반적으로, 그 값들은 매우 내적으로 연결되어 있어서, 한 값을 최소화하는 것은 또한 다른 것이 증가하도록 야기한다. 존재하는 요구사항 사이의 타협을 발견하는 것은 모든 충돌 탐지 시스템에서의 도전이다.

6.1.3 Tree Degree
intersecting question은 BVH를 나타내는 트리에서 어떤 degree or branching factor가 사용되는지에 대한 질문이다. 더 좋은 binary, ternary, d-ary (for some d) or a tree with any number of children at a node? 더 높은 degree(차수, 한 노드가 갖는 자식의 수)를 갖는 한 tree는 더 작은 height를 가질 것이고, root-to-leaf로 가는 traversal time을 최소화 한다. 동시에 좀 더 많은 작업이 각 방문된 노드에서 overlap에 대해 그것의 자식들으 체크하는데 소모되어야만 한다. 반대의 것은 낮은 차수의 트리에 유효하다 : 비록 그 트리가 더 높은 톺이를 가졌을 지라도, 더 작은 작업이 각 노드에 쓰여진다. 사이즈의 관점에서, n개의 leaves를 가진 d-ary tree는 트리에서 (nd - 1) / (d - 1)의 노드들 중에서 (n - 1) / (d - 1)의 내부 노드들을 갖는다. 명백히, 차수가 더 클수록, 트리를 형성하는데 필요한 내부 노드들은 더 적다.

무슨 차수를 사용할지에 대한 질문은 어려운 것이고, 어떠한 명백한 답도 확실하지 않다. 실제 사용을 보면은, 이진 트리가 지금까지 가장 흔한 hierarchical representation 인 것 처럼 보인다. 한 중요한 이유는 이진 트리가 구성하기에 쉽고, 그리고 어느 정도로, 다른 트리보다 나타내고 traverse하기에 더 쉽다는 것이다. 예를들어, tree를 top-down으로 구성할 때, 오브젝트들의 집합을 두 개의 부분집합으로 나누기 위해서, 단일의 splitting plane만이 발견되어야만 한다. m개의 오브젝트들을 두 개의 (비어있지 않는) 파티션으로 나누는 것은 2^(m-1) - 1방법들로 처리될 수 있고, 대응되는 수식은 기하급수적으로 커진다 (그러므로 엄청나게) 증가된 많은 파티션을 갖는다.

분석적인 주장은 또한 이진 트리의 선택의 지지에서 제안된다 [Klosowski98] [Konecny98]. 한 충돌 query의 실제 비용은 그 hierarchies를 탐색할 때 무슨 descent(하강) 규칙이 사용되었는지에 의존한다. 예를들어, n개의 leaves를 가진 balanced d-ary tree가 주어진다면, "descend A before B"와 "descend A and B simultaneously" 규칙들 (나중에 둘 다 설명된다) f(d) = dlog_d(n)과 f(d) = d^2 log_d(n)에 개별적으로 비례하는 비용을 갖는다. 그 전자는 d = 2.718로, 후자는 d = 2로 최소화되는데, 이진 또는 가급적 ternary(3개의 자식을 가진) tree를 사용하는 것이 최적이라고 제안한다.  경험적인 결과는 또한 d = 2인 선택을 지지하는 것 처럼 보이지만, 이것들은 결정적인 것은 아니다 - 특히 왜냐하면 몇 가지 실험들은 더 높은 차수의 트리들로 수행되었던 것처럼 보이기 때문이다.

플랫폼 아키텍쳐 이슈는 또한 무슨 유형의 트리가 잘 수행하는지에 대해 중요한 역학을 수행한다. 이상적으로, 트리는 메모리에 놓여야 하는데, 노드들이 traversal하는 동안 메모리에 선형으로 발생하도록 해야 한다. 캐시 효율적인 트리 구조의 이슈는 Chapter 13에서 다시 방문된다.

6.2 Building Strategies for Hierarchy Construction
가능한 트리의 개수가 입력 집합의 원소들의 개수의 관점에서 기하급수적으로 증가하기 때문에, 가장 좋은 트리에 대한 철저한 search는 실행 불가능하다. 이것은 최적의 트리를 찾는 것을 제외시킨다. 대신에 heuristic rules이 그 구성을 안내하는데 사용되고, 각 의사 결정 단계에서 몇 가지 대안을 보고, 가장 좋은 대안을 고른다. suboptimal solution에 도착하는 것은 필수적으로 문제는 아니다, 왜냐하면 보통 너무 최적이 아닌 많은 트리들이 있기 때문이다.

트리 구성 방식에 세 가지 주요한 분류가 있다: top-down, bottom-up, and insertion methods (그림 6.2).  Top-down (또는 분열되는) 방법은 그 입력 집합을 두 개의 (또는 그 이상의) 부분집합으로 나누고, 그것들을 선택된 bounding volume으로 제한시키고, 그러고나서 그 bounded subsets에 대해 재귀하여 진행한다. 그것들이 구현되는 것의 편암함 덕택에, top-down methods는 지금까지 가장 인기있는 것이다. 그러나, 그것들은 일반적으로 최상의 가능한 트리를 만들어내지 않는다.

Bottom-up (또는 응집하는) 방식은 트리의 leaves로서 그 입력집합과 시작하고, 그것들 중의 두 개 이상을 하나의 새로운 (내부) 노드를 형성하기 위해 그룹화 하고, 같은 방식으로 모든 것이 한 단일 노드 아래에 (트리의 root) 그룹화 될 때 까지 진행된다. 비록 bottom-up 방식이 다른 방법들 보다 더 좋은 트리를 만들어낼 가능성이 높지만, 그것들은 또한 구현하기에 더 어렵다.

Insertion methods는 오브젝트들을 트리에 한 번에 한 개씩 넣어서 점점 hierarchy를 구성한다. 그 insertion position은 최종 트리에 대한 몇 가지 cost measurement를 최소화하도록 선택된다. Insertion methods는 on-line methods로 고려되는데, 반면에 top-down과 bottom-up 방법들 둘 다는 off-line methods로 고려된다. 이것은 그것들이 모든 primitives가 구성을 시작하기 전에 이용가능 할 것을 요구한다는 점에서 그렇다. on-line methods의 한 장점은 그것들이 업데이트가 런타임에 수행되는 것을 허용한다. 충돌 탐지 hierarchies를 구성하는데 insertion methods에 대한 연구가 거의 되지 않았다.

이전에 주목 되었듯이, 비록 대부분의 hierarchy construction이 전처리 단계에서 발생할지라도, 빠른 construction methods를 찾는 것은 여전히 중요하다. O(n^2) 복잡도오 ㅏ그 이상의 어떤 알고리즘들은 더 많은 개수의 primitives로부터 hiearchies를 구성하는데 너무 느릴 가능성이 높다.

그 표기를 간단히 하기 위해서, 다음 섹션에서, 그 discussion은 주로 binary trees로 제한된다. 그 같은 방법들은 일반적으로 또한 n-ary 또는 심지어 일반 트리에도 적용된다.

6.2.1 Top-down Construction
top-down method는 재귀 절차의 관점에서 설명될 수 있다. 그것은 bounding volume에서 primitives (또는 objects)들의 입력 집합을 bounding 하여 시작한다. 이러한 primitives는 그러고나서 두 개의 부분집합으로 분할된다. 그 절차는 이제 그 두 개의 부분집합에 대한 subhierarchies를 구성하기 위해 재귀적으로 호출된다. 그리고 그러고나서 그것은 그 부모 volume에 대한 자식으로서 연결된다. 그 재귀는 그 입력 집합이 한 단일 primitive을 구성할 때 멈춘다 (또는, 만약 선택된다면, 그것보다 더 이전에), 그 시점에, 그 절차는 primitive에 대한 bounding volume을 만든 후에 반환된다. 그 다음 코드 fragment는 어떻게 top-down construction이 구현될 수 있는지를 보여준다.

// Construct a top-down tree. Rearranges object[] array during construction
void RTCD::TopDownBVTree(Node ** tree, Object object[], int numObjects)
{
 assert(numbObjects > 0);

 const int MIN_OBJECTS_PER_LEAF = 1;
 Node* pNode = new Node;
 *tree = pNode;

 // Compute a bounding volume for object[0], ..., object[numbObjects - 1]
 pNode->BV = ComputeBoundingVolume(&object[0], numObjects);

 if (numObjects <= MIN_OBJECTS_PER_LEAF)
 {
  pNode->type = LEAF;
  pNode->numObjects = numObjects;
  pNode->object = &object[0]; // Pointer to first object in leaf
 }
 else
 {
  pNode->type = NODE;
  // Based on some partitioning strategy, arrange objects into
  // two partitions: object[0..k-1], and object[k.. numObjects-1]
  int k = PartitionObjects(&object[0], numObjects);
  // Recursively construct left and right subtree from subarrays and
  // point the left and right fields of the current node at the subtrees
  TopDownBVTree(&(pNode->left), &object[0], k);
  TopDownBVTree(&(pNode->right), &object[k], numObjects - k);
 }
}

무슨 bounding volume을 사용할지에 대한 선택을 제쳐두고, 오직 한 단일의 안내하는 기준이 그 최종 트리의 구조를 통제한다 : 그 입력 집합이 어떻게 두 개의 부분집합으로 나눠지는지에 대한 선택이다. n개의 원소들을 가진 한 집합이 두 개의 비어있지 않은 부분집합으로 2^(n-1) - 1개의 방식으로 분할될 수 있기 때문에, 모든 파티션의 오직 작은 부분집합만이 합리적으로 고려될 수 있다는 것이 명백하다.

파티셔닝을 간단하게 하기 위해, 그 집합은 보통 splitting hyperplane을 사용하여 부분집합으로 나눠진다. 어떤 primitives를 가로질러서 자르지 않는 splitting plane을 선택하는 것을 보장하는 것이 가능하지 않기 때문에, 어떤 가로지르는 primitives가 그 집합을 나눌 때 다뤄져야만 한다. 한 솔루션은 그 primitive를 두 개로 나누고, 그 부분들을 그것들의 각각의 부분집합으로 할당하는 것이다. pimitives의 splitting은 그 자식 bounding volume이 더 작게 되도록 하고, 그것들의 overlap을 최소화하고, 가급적 완전히 그것을 제거한다. splitting straddling primitives의 장점은 어떤 split primitives가 또 다시 splitting에 종속될 수 있고, 잠재적으로 primitives의 큰 증가를 발생시킬 수 있다.

아마도 좀 더 흔한 솔루션은 primitive를 분리하는게 아니라, splitting plane과 관련하여 그것의 중심점의 위치가 그것이 어떤 subset에 들어갈지를 결정하게 하는 것이다. primitive를 어떤 부분집합에 할당할지를 결정하기 위해 centroid를 사용하는 것은 sibling bounding volumes 사이의 overlap을 최소화 하려고 시도한다. 이 방식으로, bouding volume은 그 primitive의 너비의 절반으로 너비가 확장될 것이다. 만약 그 primitive가 대신에 부분집합에 임의로 할당된다면, 최악의 경우에 그 부분집합에 대한 bounding volume은 그 primitive의 full width만큼 확장될 수 있다.

6.2.1.1 Partitioning Strategies
간단한 partitioning method는 median-cut algorithm이다. 여기에서, 그 집합은 두 개의 동일한 크기의 부분으로 나눠지는데, 선택된 축을 따라서 그것들을 사영과 관련해서 된다. 그리고 이것은 balanced tree를 만들어낸다. median cut은 한 가지 가능한 전략이다. 이전에 주어진 요구되는 특성의 리스트로 돌아가서, 다른 가능한 파티션 전략들이 있다:

• 자식 volumes의 volumes(또는 surface areas)의 합을 최소화 해라. 한 bounding volume과 그 두 개의 자식 volumes 들 중 하나 사이의 교차의 가능성은 그것들의 크기에 비례한다고 예상되어질 수 있다. 따라서, 그 volumes의 합을 효과적으로 최소화 하는 것은 교차의 가능성을 최소화 한다.  ray query에 대해, 한 bounding volume을 치게 될 ray의 가능성은 대신에 bounding volume의 surface area에 비례한다.
• child volumes의 maximum volume (surface area)를 최소화 해라. 이전 전략은 다른 것보다 더 큰 한 volume을 만들어내는 반면에, 이 전략은 그 볼륨이 크기에서 좀 더 동일하게 만든다, 이것은 그 더 큰 volume을 가능한 작게 만들어서 된다. 이것은 좀 더 balanced query를 만들어 내고, worst-case behavior를 개선시킨다.
• child volumes의 intersection의 volume (surface area)를 최소화 해라. 이 전략은 두 자식이 중첩되고 가로지르게 되는 가능성을 줄인다. 사용된 bounding volume에 따라, 그 교차는 구성하기에 복잡할 수 있고, 심지어 근사하기에 복잡할 수 있다.
• child volumes의 separation을 최대화 해라. 자식들을 분리하는 것, 심지어 중첩되지 않을 때, 그렇게 하는 것은 두 자식이 가로지르게 되는 가능성을 줄일 수 있다.
• 그 자식 volumes 사이의 primitives를 동일하게 나누어라. 이 전략은 이 섹션의 처음에 언급된 median-cut algorithm이다. 그것의 강점은 가능한 가장 균형있는 hierarchy를 준다는 것에 있다.
• 이전 전략들의 조합.

partitioning이 멈추고 한 노드가 어떤 특정한 중지 기준에 도달될 때 한 leaf로 고려된다. 흔한 stop criteria는:

• 그 노드는 단일 primitive만을 포함하거나, 어떤 k primitives보다 적다.
• bounding volume의 volume이 한 정해진 cut-off limit아래로 떨어졌다.
• 그 노드의 depth가 미리 정의된 cut-off depth에 도달한다.

Partitioning은 또한 early fail할 수 있는데, stop criterion이 촉발되기 전에, 예를들어:

• 모든 primitives가 split plane의 한 면 위에 있을 때.
• 하나 또는 두 자식 volumes이 부모 volume만큼 많은 (거의 많은) primitives를 가질 때.
• 두 child volumes이 (거의) parent volume만큼 클 때

이러한 실패 조건들은 또한 stopping criteria로 다뤄질 수 있다. 멈추기 전에, 그러나, 다른 partitioning criteria를 시도하는 것은 합리적이다. 예를들어 - box-based tree에 대해 - 가장 긴 side를 따라서 split하는 것에 실패한 후에, 처음에 그 다음으로 긴 side 그리고나서 가장 짧은 side가 테스트될 수 있다. 세 개 다 실패한다면, splitting은 멈출 것이다. leaf node당 그냥 한 개의 primitive보다 k개를 가지고 일찍 멈추는 것은 덜 메모리를 사용하는 장점이 있다. 불행하게도, leaf-leaf tests동안 단일 primitive-primitive test대신에 이제 O(k^2) 테스튿ㄹ이 수행되어야 한다.

partitioning plane의 선택은 보통 두 단계로 나눠진다. 처음에 한 축이 선택되고, 그러고나서 이 축을 따라 한 포지션이 선택된다. 이러한 선택들은 다음에 다뤄진다.

6.2.1.2 Choice of Partitioning Axis

가능한 축들의 무한한 개수에서, 어느정도 단일 축이 분할 축으로서 선택되어야만 한다. 이론적으로 가장 좋은 가능한 축을 찾기 위해 반복적인 최적화 방법을 적용하는 것이 가능하다. 실제로, 그러한 접근법은 보통 전처리 단계에서 너무 비싸다. 결과적으로, 그 탐색은 가장 좋은 것이 선택되는 작은 수의 축들로 제한되어야만 한다. 이 제한된 집합을 포함하는 축들에 대한 흔한 선택들은:

1. Local x, y, and z coordinate axes. 이러한 것들은 보통 연산을 수행하기에 쉽기 때문에 포함된다. 그것들은 또한 직교 집합을 형성하고, 넓게 다른 방향을 다루도록 보장된다.
2. 만들어진 aligned bounding volume의 축들. item 1의 local axes들은 AABB의 face normals과 일치한다. k-DOP같은 어떤 bounding volumes은 분리축에 대해 자연스러운 선택을 또한 형성하는 부가적인 고정된 축을 가진다.
3. parent bounding volume의 축들. 만약 그 hierarchy가 OBB로 구성된다면, 그 partitioning아래에 있는 현재의 집합의 bounding OBB를 정의하는 축들은 좋은 후보 축들이다. 비록 그 hierarchy가 구성될지라도, 가령 spheres (어떤 명백한 관련 축들이 없는), 임의의 OBB는 여전히 parent's data set에 대해 연산되어질 수 있다, 그리고 그것으로 부터, 분리 축들 후보군이 제거될 수 있다.
4. 두 개의 가장 멀리 있는 점들에 대한 축. 입력 집합에서 가장 멀리 있는 두 개의 점을 가로지르는 축을 따라 파티셔닝하는 것은 그 자식 volumes의 부피를 최소화하는 시도와 일치한다. 가장 멀리있는 점에 대한 최적에 가까운 근사는 간단한 O(n) heuristic 으로 주어지는데, Section 4.3.2에서 MostSeparatedPointsOnAABB()에서 함수로서 구현되어 있다.
5. variance가 가장 큰 축. 입력 데이터가 가장 큰 spread를 가지는 차원을 따라 splitting하는 것은 또한 그 자식 볼륨의 부피를 최소화하는 역할을 한다. OBB가 covariance fitted하게 되는 OBB hierarchy에서, 가장 큰 variance의 축은 간단히 그 부모 OBB의 가장 긴 side를 정의하는 축과 일치한다.

비록 완전화 최적화 단계가 그럴듯 하지 않을지라도, 한 partitioning axis가 선택되고 나면, 작은 수의 hill-climbing steps이 그 축에 대해 개선하기 위해 수행될 수 있다. 한 가지 접근법은 그 축의 방향을 흔들리게 하는 것을 포함하는데, 만약 그 흔들린 축이 더 잘 수행된다면 그 선택된 축을 대체하고, 여유가 되는 한 많은 단계에 대해 이것을 반복한다.

한 흥미로운 그러나 크게 탐사되지 않은 옵션은 분리 축들을 찾는 문제에 대한 원칙적 컴포넌트 분석에 다른 통계적 방법을 적용하는 것이다. 이러한 것은 projection pursuit, independent component analysis, and blind signal separation의 관련된 방법을 포함하는데, 이러한 것은 모두 관찰된 혼합된 source로부터 관찰되지 않은 개별 components를 찾는 기법이다. 예를들어, 간단하게 된 것으로서 projection pursuit의 방법은 한 방향을 얻는 방법으로서 설명될 수 있는데, 거기에서 사영된 데이터의 (variance보다는) entropy가 최대화되는 될 때이다. entropy는 정보 또는 "interestingness"의 척도이고, 데이터 클러스터들은 높은 entropy를 가질 것이기 때문에, 이 방향은 두 개 이상의 클러스터에서 데이터를 분리하는 좋은 후보 축을 형성한다. projection pursuit과 independent component analysis에 대한 입문은 [Stone98]을 보아라. blind signal separation은 [Cardoso98]을 보아라.

6.2.1.3 Choice of Split Point

모든 가능한 축들에 대해 최적화하는 것의 실행 할 수 없음은 split point의 선택에도 또한 적용된다. 그 축을 따라 많은 분리 점들이 무한히 있기 때문에, 그 선택은 선택들의 한 집합으로서 제한되어야 한다, 다음과 같은:

• centroid 좌표의 median (object median). object median에서 균일하게 splitting하는 것은 부분집합 사이의 primitives를 분배하고, 균형있는 트리를 만들어낸다. 그 median은 자명하게 그 점들을 정렬하여 O(nlogn) 시간에 발견되고, 좀 더 정교한 방식을 사용하여 O(n) 시간에 된다 (see [Cormen90] for details).
• centroid 좌표의 Mean (object mean). 잘 균형잡힌 트리들은 필수적으로 가장 좋은 query times을 주지 않는다. 가장 큰 variance를 가진 local axis를 따라 분리하여, [Klowsowski98]은 그 object mean을 사용하는 것이 object median을 사용하는 것을 앞선다고 보고한다. 그들은 mean에서 splitting하는 것이 일관되게 더 작은 volume trees를 주고, 더 낮은 수의 연산이 수행되고 더 좋은 쿼리 타임이 결과적으로 나온다고 보고한다. 그 오브젝트 mean은 O(n) time에 발견된다.
• bounding volume projection extents의 Median (spatial median). spatial median에서 분리하는 것은 (따라서 그 volume을 두 개의 동일한 부분으로 분리하는 것) 매력적인 대안이다. 그 split point가 bounding volume을 검사하여 상수 시간에 발견되기 떄문이다, 그것의 포함된 데이터를 검사하지 않고. 이 대안은 종종 그 축이 parent volume으로 부터 선택될 때 사용된다 (예륻들어, 가장 긴 side rule을 사용해서).
• k개의 균일하게 spaced points에서 bounding volume projection extents를 따라 분리하는 것. "intelligently guessing"인 것에 시간을 쓰는 것 대신에, 좋은 split position,인 이 brute-force alternative는 그 축을 따라 균일하게 spaced points의 작은 개수를 테스트하고 가장 좋은 것을 고른다.
• centroid 좌표 (랜덤 부분집합) 사이에서 splitting하기. 이전 방법과 유사하게, 사영된 centroids 사이의 splitting은 그 splitting plane을 가로지르는 primitives의 개수를 최소화 하려고 한다, centroids를 사영해서 정렬하는 것을 희생해서.

그림 6.3은 이러한 splitting choices의 몇 가지를 보여준다. 직접적으로 splitting point를 선택하는 대신에, 그 부분집합은 증가되어 구성될 수 있다. 예를들어, [Zachmann98]은 두 개의 가장 먼 거리의 점들 a와 b를 통한 축을 따라서 분리한다. a와 b와 관련된 faces를 두 개의 다른 부분집합에 추가하여 시작하여, 그는 나머지 primitives를 부분집합에 할당한다, 그 부분집합에서 bounding volume은 primitive가 추가될 때 덜 증가된다. 만약 두 volumes이 같은 양으로 증가하거나 또는 전혀 증가하지 않는다면 (volume 안에 완전히 있는 primitive 때문에), 그 primitive는 더 작은 primitives를 가진 집합에 추가된다.

Top-down construction은 지금까지 bounding volume hierarchies를 구성하는 가장 흔한 접근법이다. 그 장점은 구현의 쉬움과 빠른 트리 구성을 포함한다. 단점은 중요한 결정들이 알고리즘의 초반에 모든 저옵가 이용가능 하지 않은 시점에서 되어야 하기 떄문에, 그 트리가 일반적으로 가능한 좋지 않다는 것이다.

6.2.2 Bottom-up Construction

top-down methods와 대조적으로, bottom-up methods는 구현하기에 더 복잡하고, 더 늦은 construction time을 가지만, 보통 가장 좋은 trees를 생성한다 [Omohundro89]. tree hierarchy를 밑바닥부터 구성하기 위해, 그 첫 번째 단계는 각 primitive를 한 bounding volume 내에서 둘러싸는 것이다. 이러한 volumes은 그 트리의 leaf nodes를 형성한다. volumes들의 결과 집합으로부터, 두 개 (또는 그 이상의) leaf nodes가 그러고나서 bounding volume 내에서 제한된다, 거기에서 그 bounding volume은 그 집합에서 원래 노드들을 대체한다. 이 pairing procedure는 그 집합이 구성된 트리의 root node를 나타내는 한 단일의 bounding volume으로 구성될 때 까지 반복한다.

Node * RTCD::BottomUpBVTree(Object object[], int numObjects)
{
 assert(numbobjects != 0);

 int i, j;

 // Allocate temporary memory for holding node pointers to
 // the current set of active nodes (initially the leavs)
 NodePtr* pNodes = new NodePtr[numObjects];

 // Form the leaf nodes for the given input objects
 for (i = 0; i < numObjects; ++i)
 {
  pNodes[i] = new Node;
  pNodes[i]->type = LEAF;
  pNodes[i]->object = &object[i];
 }

 // Merge pairs together until just the root object left
 while (numObjects > 1)
 {
  // Find indices of the two "nearest" nodes, based on some criterion
  FindNodesToMerge(&pNodes[0], numObjects, &i, &j);
  // Group nodes i and j together under a new internal node
  Node* pPair = new Node;
  pPair->type = NODE;
  pPair->left = pNodes[i];
  pPair->right = pNodes[j];
  // Compute a bounding volume for the two nodes
  pPair->BV = ComputeBoundingVolume(pNodes[i]->object, pNodes[j]->object);

  // Remove the two nodes from the active set and add in the new node.
  // Done by putting new node at index 'min' and copying last entry to 'max'
  int min = i, max = j;
  if (i > j) min = j, max = i;
  pNodes[min] = pPair;
  pNodes[max] = pNodes[numObjects - 1];
  --numObjects;
 }
 // Free temporary storage and return root of tree
 Node* pRoot = pNodes[0];
 delete pNodes;
 return pRoot;
}

이전 섹션의 로직을 따라서, 좀 더 의미있는 merging criteria중의 하나는 그것들의 bounding volume의 부피가 최소화가 되도록 한 쌍을 선택하는 것이다. 합쳐질 어떤 두 노드들을 찾는 것에 대핸 brute-force approach는 모든 가능한 쌍을 조사하고, 그것들의 bounding volume을 연산하고, 가장 작은 bounding volume을 가진 쌍을 고른다. 그 brute-force approach는 O(n^2)의 시간을 요구한다. 전체 트리를 형성하는데 반복된 n - 1 번 반복되어, 총 구성 시간은 O(n^3)이 된다.

6.2.2.1 Improved Bottom-up Construction
좀 더 정교한 구현은 brute-force 접근법의 성능을 상당해 개선할 수 있다. 항상 각 노드에 대해 선호되는 minimum volume pairings을 재 계산하는 대신에, 노드들은 그것들이ㅡ 선호되는 pairing nodes들과 그 쌍을 위한 새로운 volume을 추적할 수 있다. 그러고나서 어떤 주어진 시점에, 가장 작은 저장된 volume을 가진 node와 그것의 저장된 pairing node는 합쳐질 노드들의 가장 좋은 쌍이 될 것이다. 이러한 (node, pairing node, volume)-tuples은 효과적으로 volume으로 정렬되는 (heap or binary search tree) 우선순위 큐같은 자료구조에서 유지될 수 있다. 그리고 이것은 최소 volume entry에 대한 빠른 접근을 허용한다.

한 새로운 쌍이 형성 될 때 마다, 대부분의 그 저장된 minimum volume pairings는 같게 남는다. 오직 그 두 개의 새롭게 paired된 nodes들 중 하나를 포함하는 저장된 pairings가 영향 받는다. 좀 더 중요하게, 그것들이 변할 때, 그 쌍에 대한 저장된 volume만이 증가할 수 있다. 이것은 그 pairing node가 게으르게 재 연산되는 것을 허용하고, 그 pair이 우선순위 큐에서 제거되는 시간때 까지 그 계산을 지연시킨다.

사실 상, 그 알고리즘은 반복인데, 거기에서 그 현재 가장 좋은 pair는 큐로부터 제거된다. 만약 그 노드가 이미 paired 되어있다면, 그 pair는 간단히 버려지고, 그 다음 가장 좋은 pair가 추출된다. 만약 그렇지 않다면, 그 노드에 대한 가장 좋은 pairing node가 계산된다. 만약 그것이 저장된 pairing node와 부합한다면, 이 pair는 최소 volume pair가 되어야만 하고, 그것들은 합쳐질 수 있다. 만약 그것이 부합하지 않다면, 그 pairing node는 이전 단계에서 paired 되어야만 하고, 그래서 그 노드와 그 새로운 pairing node는 새로운 volume priority value를 가지고 priority queue에 재삽입된다.

부족한 부분은 어떻게 주어진 query node가 paired될 때 가장 작은 volume을 형성하는 pairing node를 빠르게 계산하는가 이다. 흥미롭게도, dynamic bounding volume tree (특히, top-down incremental insertion algorithm은 나중에 보여진다)가 그것이 구성될 때 트리의 bottom-up fragments를 유지하는 적절한 자료구조이다. 그러한 구조가 주어진다면, 그 pairing node는 tree의 top으로부터 탐색하여 찾아지고, query volume이 교차하는 모든 자식들로 내려간다. 그 query volume이 hierarchy에서 발견될 때, 그 pairing node는 그 부모 volume의 다른 자식이다 (즉, sibling node). 다음의 코드 fragment는 그 개선된 알고리즘이 어떻게 구현되는지를 보여준다.

Node * RTCD::ImprovedBottomBVTree(Object object[], int numObjects)
{
 PriorityQueue<Pair> q;
 InsertionBVTree t;

 // Bound all objects in BV, forming leaf nodes. Insert leaf nodes into a
 // dynamically chanable insertion-built BV tree
 InitializeInsertionBVTree(t, object, numObjects);

 // FOr all nodes, form pair of references to the node and the node it pairs
 // best with (resulting in the smalles bounding volume). Add all pairs to
 // the priority queue, sorted on increasing volume order
 InitializePriorityQueue(q, object, numObjects);

 while (SizeOf(q) > 1)
 {
  // Fetch the smalles volume pair from the queue
  Pair* p = Dequeue(q);

  // Discard pair if the node has already been paired
  if (HasAlreadyBeenPaired(p->node)) continue;

  // Recompute the best pairing node for this node to see if
  // the stored pair node is still valid
  Node* bestpairnode = ComputeBestPairingNodeUsingTree(t, p->node);
  if (p->pairnode == bestpairnode)
  {
   // The store pair node is OK, pair the two nodes together;
   // link the nodes together under a new node
   Node* n = new Node;
   n->left = p->node;
   n->right = p->pairnode;

   // Add new node to BV tree; delete old nodes as not possible to pair with
   Delete(t, p->node);
   Delete(t, p->pairnode);
   Insert(t, n);

   // Compute a pairing node for the new node; insert it into queue
   Node* newbestpairnode = ComputeBestPairingNodeUsingTree(t, n);
   p = Pair(n, newbestpairnode);
  }
  else
  {
   // Best pair node changed since the pair was inserted;
   // update the pair, reinsert into queue and try again
   p = Pair(p->node, bestpairnode);
  }
  Enqueue(q, p, VolumeOfBVForPairedNodes(p)); // Queue, pair, priority
 }
 return Dequeue(q)->node;
}

비슷한 접근법이, 특히 sphere trees를 구성할 때, [Omohundro89]에 보여진다.

6.2.2.2 Other Bottom-up Construction Strategies
6.2.2.3 Bottom-up n-ary Construction Strategies
제외..

6.2.3 Incremental (Insertion) Construction
구성 접근법의 마지막 유형은 incremental or insertion method이다. 여기에서, 그 트리는 한 번에 한 오브젝트를 넣어서 구성된다, 텅비 트리로부터 시작하여. 오브젝트들은 트리가 cost metric에 따라서 가능한 가장 적게 성장하도록 하는 트리에서 insertion location을 찾아서 삽입된다. 일반적으로 한 주어진 위치에 한 오브젝트를 넣는것 과 관련된 비용은 그것의 bounding volume의 비용과 그 트리에 그것 위에 있는 모든 조상 volumes에서 그 insertion이 발생시키는 volume의 증가와 더해진 것의 비용으로 취해진다.

만약 그 삽입될 오브젝트가 존재하는 노드에 비해 크다면, 그것은 그 hierarchy의 꼭대기 가까이에 있을 경향이 있다. 더 작은 오브젝트들은 존재하는 bounding volume 내에 있을 가능성이 높고, 대신에 바닥 가까이에 있을 것이다. 그 새로운 오브젝트가 존재하는 오브젝트들과 멀리 있을 때, 그것은 또한 top에 가까울 것이다. 전반적으로, 그 최종 트리는 그러므로 오브젝트들의 원래 집합에서 실제 클러스터링을 반영하는 경향이 있을 것이다.

한 트리의 구조는 그것에 삽입되는 오브젝트들에 의존적이기 때문에, 그리고 삽입 결정들이 현재 구조를 기반으로 되어지기 때문에, 그것은 오브젝트들이 삽입되는 순서가 중요하다는 것을 따른다. authoring tool에 의해 정의된 순서로 오브젝트들을 사용하는 것은 실제 오브젝트 clustering을 반영하지 않는 나쁜 hierarchies를 만들 수 있다. 데이터를 정렬하는 것은 같은 문제를 겪을 수 있고, 더 그럴 수 있다. degenerate behavior를 피하기 위해서, 가장 좋은 접근법은 랜덤으로 삽입전에 그 오브젝트들을 shuffle하는 것처럼 보인다.

간단한 insertion method 구현은일관되게 child로 내려가서 한 단일의 root-leaf traverslal를 수행하는 것인데, 거기에서 그 삽입은 더 쌀 것이다. 그러고나서 그 삽입 노드는 방문된 노드로 부터 traced path를 따라 선택되어질 것인데, 그 전체 트리 volume이 최소화가 되도록 되어야 한다. O(logn) search가 각 오브젝트 삽입마다 수행되기 때문에, 전체 복잡도는 O(nlogn)이다.  좀 더 고급 구현은 전체 트리를 검사하고, 가장 좋은 첫 번쨰 방식으로 진행하는 것인데, 우선순위 큐를 사용하여 search front를 유지하고, 항상 현재 가장 좋은 노드를 따라 내려간다. 두 방법들은 [Omohundro89]에 sphere trees를 만드는 관점에서 설명된다.

Insertion strategies는 빠를 수 있거나 또는 심지어 top down methods들 보다 더 빠를 수 있고, 더 좋은 결과들을 만들 수 있다. 그것들은 on-line methods로 고려되는데, 모든 오브젝트들이 프로세스를 시작할 때 존재할 필요가 없다는 의미에서 그렇다. 그것들이 on-line methods라는 것은 또한 그것들이 한 이미 존재하는 tree를 업데이트하는 것에 대해 사용되어지는 것을 허용하고, dynamic systems에 유용하게 만든다. 그러므로 어느정도 거의 어떠한 충돌 탐지 시스템도 incremental construction methods를 사용한다고 보고하지 않는 것은 놀랍다.

6.2.3.1 The Goldsmith-Salmon Incremental Construction Method
ray tracing에서 사용하기 위해 BVH를 구성하는데 한 흥미로운 알고리즘은 [Goldsmith87]에서 설명되고, [Haines88]에서 개선점들이 발견된다. 이전처럼, 오브젝트들은 한 번에 한 개씩 넣어지고, 그 위치에서 가장 최적인 운명이었다. root에서 leaf로 가는 단일 경로는 bounding volume surface area에서 가장 적게 증가하는 child로 내려가고, 그 오브젝트는 그것의 자식이 되도록 삽입된다.

surface area가 사용되는 이유는 projective geometry의 결과를 따르는데, convex 3D volume의 평균적인 사영된 area가 그것의 surface area의 1/4이라는 주장이다. 게다가, 만약 ray가 부모 bounding volume A에 부딪힌다면, random ray가 한정된 bounding volume B에 부딪힌다는 conditional probability는 그러므로 그것들의 surface areas의 비율에 비례한다. 그 root volume은 편리하게 모든 연산 내에 volume A로서 사용될 수 있고, 그 division이 직접적으로 대신에 현재 probabilities를 비교하여 피해질 수 있도로 ㄱ한다.

surface areas가 비율로서만 사용되기 때문에, 그것들은 오직 상수 요소 내에서 주어져야 한다, contant factor가 상쇄하기 때문이다. x, y, z 차원을 가진 bounding box에 대해, 그 넓이는 x(y+ z) + yz로서 연산될 수 있고, 반지름이 r인 sphere에 대해서 그 area는 r^2으로 연산될 수 있다.

이제 한 ray가 root volume에 부딪힐 때, 적어도 한 부가적인 k개의 교차 테스트가 수행되어야 하는데, 거기에서 k는 root의 자식의 숫자 이다. 이 특징은 또한 어떤 노드에 대해서 유효하지만, root는 아니다. 한 노드가 오직 그것의 부모가 hit되어야만 hit된다는 conditional probability를 설명하여, 한 노드를 hitting하는 것에 대한 total average cost는 k * (root node의 surface area로 나눈 node의 surface area)가 된다. 구체적으로, root node의 비용은 그것이 갖는 자식의 개수이고, leaf node의 비용은 zero이다 (그것의 비용은 부모의 비용에 포함되기 때문에). 한 트리에 대한 total cost는 이제 O(n) time에 모든 노드의 비용의 합으로 계산되어질 수 있다.

tree cost는 또한 트리가 구성됨에 따라 증가하여 연산되어질 수 있다. 이것은 hierarchy가 insertion동안 traverse될 때 incremental "inheritance cost"를 child nodes에 넘겨서 구현된다. 이 비용은 조상 volumes에 대한 volume의 증가와 일치한다, 오브젝트를 트리에 삽입하기 떄문이다. 이것에 대해, 오브젝트를 삽입의 세 개의 다른 선택에 따라 현재 위치에 넣는 비용에 더해진다:

1. 그 오브젝트와 leaf node는 한 새로운 node아래에서 paired 된다. 이 경우에 inheritance cost에 대한 incremental change는 d = 2Area (new node)이다. 이 경우는 또한 새로운 루트 아래에서 그 오브젝트와 오래된 root를 pairing할 때 적용된다.
2. 그 오브젝트는 존재하는 노드에 한 새로운 child로서 추가된다. 존재하는 오래된 노드의 비용은 c = kArea(old node)가 된다. 그 새로운 노드는 c' = (k + 1)Area (new node)의 비용을 가질 것이다. 그 증가하는 비용은 그러므로 d = c' - c = k(Area(new node) - Area(old node)) + Area(new node) 이다.
3. 
   

6.3 Hierarchy Travesal
6.3.1 Descent Rules
6.3.2 Generic Informed Depth-first Traversal
6.3.3 Simultaneous Depth-first Traversal
6.3.4 Optimized Leaf-direct Depth-first Traversal

6.4 Sample Bounding Volume Hierarchies
6.4.1 OBB Trees
6.4.2 AABB Trees and BoxTrees
6.4.3 Sphere Tree Through Octree Subdivision
6.4.4 Sphere Tree from Sphere-covered Surfaces
6.4.5 Generate-and-Prune Sphere Covering
6.4.6 k-dop Trees

6.5 Merging Bounding Volumes
6.5.1 Merging Two AABBs
6.5.2 Merging Two Spheres
6.5.3 Merging Two OBBs
6.5.4 Merging Two k-DOPs

6.6 Efficient Tree Representation and Traversal
6.6.1 Array Representation
6.6.2 Preorder Traversal Order
6.6.3 Offsets Instead of Pointers
6.6.4 Cache-friendlier Structures (Nonbinary Trees)
6.6.5 Tree Node and Primitive Ordering
6.6.6 On Recursion
6.6.7 Grouping Queries

6.7 Improved Queries Through Caching
6.7.1 Surface Caching : Caching Intersecting Primitives
6.7.2 Front Tracking

6.8 Summary