TMI(Triangle Mesh Information) Project #7.1 - Bounding Volume Hierarchy

0. 들어가기 앞서

 이전 포스팅에서는 OBB에서는 Collision Detection을 어떻게 하는지 알아본 뒤 Collision 됐을 시에 VTK를 활용해 Bounding Box의 색을 변경해 가시화 해보았습니다.

https://mathmakeworld.tistory.com/107

TMI(Triangle Mesh Information) Project #6.3 - OBB Collision Detection

이번 포스팅에서는 Bounding Volume Hierarchy에 대해서 알아보고 왜 Bounding Volume Hierarchy를 사용하는지에 대해 알아보도록 하겠습니다.

 

 들어가기 전 이 포스팅을 읽고 계신 분들은 간단한 Tree 구조에 대해 안다고 생각하고 시작하겠습니다. 혹시라도 Tree 구조를 모르시는 분들은 아래 포스팅에서 정리를 잘 해두셨으니 한번 읽어보고 오시면 될 것 같습니다!

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

[자료구조] 트리(Tree)란 - Heee's Development Blog

 

1. Bounding Volume Hierarchy란?

 Bounding Volume Hieararchy를 구글에 검색해보면 Wikipedia에 아래와 같이 시작합니다.

 "A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, that form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larger bounding volumes." 

 이 글에서 Bounding Volume Hierarchy(앞으로는 줄여서 BVH라고 부르겠습니다.)에 대한 단서를 찾을 수 있습니다.

 

단서

 1. tree structure 입니다.

 2. tree의 leaf nodes들은 geometric objects로 구성되어 있습니다.

 3. geometric object들은 각각의 bounding volume을 가집니다. 4. 각각의 bounding volume은 다른 bounding volume과 합쳐져 더 큰 bounding volume이 됩니다.

 

2. BVH를 왜 써야하나?

 BVH를 쓰는 이유는 Collision Detection에 효과가 좋습니다. 2가지 부분에서 성능을 상승시켜주는데

   - Tree 구조이기 때문에 불필요한 부분을 검사하지 않습니다.(물론 Balance가 잘 잡힌 Tree라는 가정입니다.)

   - Bounding Volume으로 검사하기 때문에 Collision Check가 빠르다. Leaf Node에서만 디테일하게 계산해주면 된다.

 

3. BVH의 구성

BVH를 잘 표현한 그림은 아래와 같습니다. 

Bounding Volume Hierarchy 출처 : WIKIPEDIA

3-1 단말 노드(leaf node)의 설정

 가장 하단의 단말 노드(leaf node)는 geometric object로 구성되어있습니다. 그림과 같이 별 원과 같이 하나의 Mesh를 넣어도 되고, 하나의 Mesh를 가지고 BVH를 생성하려면 각 face의 삼각형을 geometric object로 구성해도 됩니다. 만드는 사람이 최종 단말 노드로 무엇을 둘지를 정하면 될 것 같습니다.

 

위의 그림에서는 하나의 Object를 단말 노드로 설정하였습니다. 하지만 우리는 하나의 Mesh Model을 Tree구조로 만들어볼 것 입니다. 그러면 각각의 Triangle이 geometric object가 되고 각 object의 Bounding Volume이 있을겁니다. 우리는 이 것을 이미 이전 포스팅에서 만들어 보았고(AABB, OBB, Sphere), 오늘 포스팅에서도 AABB를 Bounding Volume으로 사용하겠습니다.

 

결과적으로 우리가 생성하려는 BVH의 단말노드에는 Triangle의 index와 AABB의 정보가 들어갈 것입니다.

Code로 보면 아래와 같습니다. Mesh(transformPolyData)의 모든 face를 순회하면서 각 face의 3점을 가지고 AABB를 생성하고 tree에 넣어줍니다.

모든 Face를 AABB로 만들고 tree에 insert

 

3-2 BVH 구조 생성

 우리는 앞에서 하나의 Mesh로 BVH를 생성할 것이고, 단말 노드에는 triangle의 AABB와 triangle Index가 들어간다는 사실을 정했습니다. 그렇다면 비어있는 BVH에 Triangle을 하나씩 넣어주면서 Tree를 만들어 나가면 됩니다. Tree를 만들어 나가는 방법은 다 적기에는 양이 너무 많으므로 아래 Box2D에서 설명해주는 글을 참고하시면 좋을 것 같습니다.

https://box2d.org/files/ErinCatto_DynamicBVH_GDC2019.pdf

 

간략하게 설명하자면

 1. 새로운 노드를 넣을 때마다 가장 적절한 위치를 cost를 계산해서 찾고 넣어준 뒤(위 자료에서는 Sibling을 찾는다고 표현합니다. 링크 31page 참고) 

 2. 전체적인 balance를 계산해 Tree를 재구성해주는 과정을 반복합니다.(링크 73page 참고)

 실제 Code에서는 Util/BoundingVolumeHierarchy.cpp의 InsertLeafNode(int nodeID) 함수와 BalanceSubTreeAtNode(int nodeID) 함수를 확인하시면 될 것 같습니다. cost는 각각의 노드가 가지고 있는 AABB의 부피로 계산합니다.

 3. 단말 노드가 아닌 나머지 노드들은 부모 노드와 자식노드의 연결정보, 또한 본인이 가진 모든 단말 노드의 AABB를 포함하는 AABB 정보를 가지고 있게 됩니다.

 

 아래 그림을 보면 위의 Tree 보다 아래 Tree가 B, C 노드의 부피가 더 작은 것을 알 수 있고, 우리는 이것을 적절한 Sibling을 찾아 넣었다고 이야기합니다.

위 - 적절하지 못한 Tree, 아래 - 적절하게 Insert된 Tree

 

 위의 그림처럼 새로운 object가 들어왔을 때 계속해서 적절한 노드의 위치를 찾고 Update된 Tree의 Balance를 맞춰주면 최종적으로 우리가 원하는 BVH를 얻을 수 있습니다. 위에서 이야기 했듯이 BVH의 단말 노드(leaf Node)가 아닌 노드는 실제 Data는 가지고 있지 않지만 본인이 가지고 있는 모든 단말 노드의 Data가 포함된 Bounding Volume을 가지고 있게 됩니다.

 

4 Test Code

 위의 내용을 담은 Code를 아래 Git에 업데이트 해두었습니다. main문에서 CExample_4_BVH bvh; bvh.Run();을 실행하면 아래 영상과 같이 BVH의 Depth에 따른 Bounding Volume들을 가시화 하는 Code를 실행하실 수 있습니다.

BVH Bounding Volume 가시화

BoundingVolumeHierarchy_Depth.mp4

6.03MB

 Key 설명은 ReadMe에 있으니 확인바랍니다.

 

 

코드는 Git에 계속해서 Upload 하고 있으니 필요하신 분들은 다운받아 쓰시면 될 것 같습니다! 

https://gitlab.com/bshong2850/blog_vtk

ByeongSun Hong / Blog_VTK

오늘은 Bounding Volume Hierarchy에 대해 알아보았습니다. 다음 포스팅에서는 Bounding Volume Hierarchy를 활용하여 Collision Detection을 가속화 하는 법에 대해 알아보도록 하겠습니다.