문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류:그래픽 가속 알고리즘]] == 개요 == Bounding Volume Hierarchy [[바운딩 박스]]를 계속 재귀적으로 계산하여 트리를 만들고 충돌판정에서 이 트리를 이용한다. Linear Search 는 O(n)의 효율을 가지지만, Tree Search는 O(logN)이기 때문에 훨씬 빠르게 충돌 판정을 할 수 있다. == 트리 만들기 == [[파일:BVH make tree.png|섬네일]] #바운딩 박스를 만든다. #바운딩 박스를 적절하게 두 부분으로 나눈다. 적절하게 나누는 방식은 [[SAH]](Surface Area Heuristic)이나 정렬하고 가운데를 잡는방식는 다양한 방법이 존재할 수 있다. #노드의 개수가 원하는 개수가 될때까지 1단계로 돌아가서 반복한다. == 트리 찾아가기== [[파일:Bounding Volume Hierarchy.png|섬네일]] #바운딩 박스와 레이가 교점이 존재하는지 확인한다. #만약 교점이 존재하면 자식노드의 어떤 노드와 만나는지 확인한다. #Leaf Node(자식이 없는 노드)가 나올때까지 반복한다. #Leaf Node 에서 삼각형과 교점을 확인하여 충돌을 검출한다. Bounding volume hierarchy 문서로 돌아갑니다.