Ahn9807: 새 문서: 분류:그래픽 가속 알고리즘 == 개요 == Bounding Volume Hierarchy 바운딩 박스를 계속 재귀적으로 계산하여 트리를 만들고 충돌판정에서 이 트리를 이용한다. Linear Search 는 O(n)의 효율을 가지지만, Tree Search는 O(logN)이기 때문에 훨씬 빠르게 충돌 판정을 할 수 있다. == 트리 만들기 == 섬네일 #바운딩 박스를 만든다. #바운딩 박스를 적절하게 두...

2023-02-25T11:02:43Z

새 문서: 분류:그래픽 가속 알고리즘 == 개요 == Bounding Volume Hierarchy 바운딩 박스를 계속 재귀적으로 계산하여 트리를 만들고 충돌판정에서 이 트리를 이용한다. Linear Search 는 O(n)의 효율을 가지지만, Tree Search는 O(logN)이기 때문에 훨씬 빠르게 충돌 판정을 할 수 있다. == 트리 만들기 == 섬네일 #바운딩 박스를 만든다. #바운딩 박스를 적절하게 두...

새 문서

[[분류:그래픽 가속 알고리즘]]

== 개요 ==
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 - 편집 역사