Bounding volume hierarchy

개요

Bounding Volume Hierarchy

바운딩 박스를 계속 재귀적으로 계산하여 트리를 만들고 충돌판정에서 이 트리를 이용한다. Linear Search 는 O(n)의 효율을 가지지만, Tree Search는 O(logN)이기 때문에 훨씬 빠르게 충돌 판정을 할 수 있다.

트리 만들기

1. 바운딩 박스를 만든다.
2. 바운딩 박스를 적절하게 두 부분으로 나눈다. 적절하게 나누는 방식은 SAH(Surface Area Heuristic)이나 정렬하고 가운데를 잡는방식는 다양한 방법이 존재할 수 있다.
3. 노드의 개수가 원하는 개수가 될때까지 1단계로 돌아가서 반복한다.

트리 찾아가기

1. 바운딩 박스와 레이가 교점이 존재하는지 확인한다.
2. 만약 교점이 존재하면 자식노드의 어떤 노드와 만나는지 확인한다.
3. Leaf Node(자식이 없는 노드)가 나올때까지 반복한다.
4. Leaf Node 에서 삼각형과 교점을 확인하여 충돌을 검출한다.