TMI(Triangle Mesh Information) Project #7.2 - Bounding Volume Hierarchy를 활용한 Collision Detection

0. 들어가기 앞서

 이전 포스팅에서는 Bounding Volume Hierarchy에 대한 개념과 생성하는 법에 대해서 알아보고 Depth에 해당하는 Bounding Box들을 가시화 해보았습니다.

https://mathmakeworld.tistory.com/108?category=454083 

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

이번 포스팅에서는 Bounding Volume Hierarchy(뒤에서는 BVH로 줄여서 말하겠습니다.)를 활용하여 충돌 검사를 하는 방법에 대해서 알아보고 일반적인 방법과 비교해봤을 때 얼마나 큰 성능차이가 있는지 알아보겠습니다.

 

1. 순서도

 BVH를 활용하여 충돌 검사를 하는 순서는 아래와 같습니다. 이번 포스팅을 쭉 읽은 뒤에 다시 순서도를 보시면 좀 더 이해하기 수월하실 것 같습니다.

  

 

2. BVH를 활용한 BVH - Object 충돌 검사

 오늘 충돌 검사를 설명하면서 아래 그림의 BVH를 예시로 활용하도록 하겠습니다.

 오른쪽 실제 Data의 원들(7~14)이 BVH를 구성하는 단말노드의 Data이고 전체 BVH는 왼쪽과 같이 구성하였습니다.

 

BVH 예시

이전 포스팅에서 알아본 것과 같이 BVH의 각 노드는 실제 Data는 가지지 않고 자기 자신의 모든 단말 노드의 Bounding Volume(Bounding Volume에는 AABB, OBB, Sphere 등등 많은 종류가 있지만 앞으로는 AABB로 예시를 들어 설명할테니 AABB라고 표현하도록 하겠습니다.)을 포함하는 AABB를 가지고 있다고 이야기 했습니다.

BVH와 Object 충돌 예시

 위의 예시를 보시면 검정색 0번 노드는 단말노드 7~14의 AABB를 모두 포함하는 검정색 AABB를 가지고 있고,

 초록색 1번 노드는 단말노드 7~10 , 2번 노드는 단말노드 11~14의 AABB를 각각 포함하는 초록색 AABB를 가지고 있는 것을 확인할 수 있습니다.

 

 그렇기 때문에 아래와 같은 가정이 가능합니다.

   가정 1. 현재 노드의 AABB가 다른 Object의 AABB와 충돌 하였다면! 그 노드의 자식 노드들은 다른 Object와

             충돌했을 "가능성이 있는" 노드가 됩니다. (자식 노드 확인해봐야 함)

   가정 2. 현재 노드의 AABB가 다른 Object의 AABB와 충돌하지 않았다면! 그 노드의 자식 노드들은 다른 Object와

             충돌했을 "가능성이 전혀 없는" 노드가 됩니다. (자식 노드 확인할 필요 없음)

 

 이렇게 가정할 수 있는 이유를 위의 그림으로 확인해보겠습니다. 새로운 Object(빨간 삼각형)가 지금의 BVH와 충돌되었는지 확인해보면 빨간 삼각형의 AABB는 현재 0번 노드의 AABB와는 충돌하였습니다. 그렇기 때문에 위에서 말한 가정 1에 따라 0번 노드의 자식노드인 1,2번 노드는 빨간 삼각형과 충돌했을 "가능성이 있게" 됩니다.

 

 1번과 2번 노드가 가능성이 있는 노드이기 때문에 두 노드에 대해서 빨간 삼각형과 충돌 확인을 합니다. 

 1번 노드의 AABB와 빨간 삼각형의 AABB는 충돌상태입니다. 따라서 1번 노드의 자식 노드인 3번과 4번도 충돌 가능성이 있는 노드가 되어 후보가 됩니다.

 2번 노드의 AABB와 빨간 삼각형의 AABB는 충돌이 아닌 상태입니다. 2번 노드의 자식노드들은 전부 2번 노드의 AABB의 안쪽에 존재하기 때문에 모든 노드가 빨간 삼각형과 충돌 가능성이 전혀 없게 됩니다. 그렇기 때문에 우리는 2번 노드의 모든 자식노드를 충돌 체크하지 않아도 됩니다.

 

 위의 방법을 계속 반복하여 단말 노드가 나올때까지 내려갑니다. 결국 후보는 0-1-4-(9 ,10) 순으로 찾아져서 9번과 10번 노드가 단말 노드이자 충돌 가능성이 있는 노드가 됩니다.

AABB끼리 충돌된 노드들

 결국 최종적으로 9번과 10번 단말 노드가 충돌 후보가 되었고, 단말 노드이기 때문에 실제 Data와 실제 Object간의 충돌이 있는지 확인해야 합니다.

 위 예제 같은 경우에는 9번 원 - 빨간 삼각형 , 10번 원 - 빨간 삼각형이 충돌되었는지 확인하게 되는데 9번 원 같은 경우에는 충돌하지 않고 10번 원은 충돌한 것을 확인하실 수 있습니다. 결국 10번 원이 충돌됐다는 것을 확인하게 됩니다.

 

 이 과정을 통해 우리가 생각할 수 있는 BVH의 이점은

  1. 필요없는 노드를 확인하지 않기 때문에 효율적이다.

  2. 단말 노드가 아니라면 AABB만으로 충돌 검사를 하기 때문에 효율적이다.

  3. 어떤 노드인지 찾지 않고 오직 충돌 여부만 확인하려면 BVH의 높이만큼 즉 위의 Tree에서 0-1-4-10 순으로만 보면 되기 때문에 효율적이다.

 

 위의 3가지 이점이 있기 때문에 모든 오브젝트를 확인하는 것보다 훨씬 효과적이라고 말씀드릴 수 있습니다.

 

 

3. BVH를 활용한 BVH - BVH Collision Detection

 그렇다면 BVH와 BVH간의 충돌 체크는 어떻게 할까요?

 위의 방법과 똑같지만 확인해야할 내용이 조금 더 많아집니다. 아래 간단한 예시로 확인해 보도록 하겠습니다.

BVH - BVH 충돌 예시

시작 순서는 똑같습니다. 먼저 숫자 BVH의 루트인 0번 노드와 알파벳 BVH의 루트인 a 노드의 AABB간의 충돌을 확인합니다. 충돌이 됐다면 단말 노드인지 확인하고 단말 노드가 아니라면 서로의 자식노드를 교차하여 저장합니다.

 즉, 그림에서 보시면 1 - b, 1 - c, 2 - b, 2 - c 이렇게 총 4쌍의 노드를 저장하게 됩니다.

 

 그 다음 4쌍의 노드를 확인해보면

  1. 1 - b : 충돌 X

  2. 1 - c : 충돌 X

  3. 2 - b : 충돌 O - 충돌 했기 때문에 단말 노드인지 확인 후 5 - d, 5 - e, 6- d, 6 - e를 저장

  4. 2 - c : 충돌 X

 

위와 같은 방법으로 숫자 노드와 알파벳 노드가 모두 단말 노드 일 때까지 저장하게 됩니다. 그렇다면 최종적으로 5 - e가 충돌 단말 노드가 되고, 최종적으로 5번 노드의 Data와 e 노드의 Data의 충돌을 확인해보면 충돌한 것을 알 수 있습니다. 

 

4. Test Code

 위의 내용을 담은 Code를 아래 Git에 데이트 해두었습니다. main문에서 CExample_5_BVHCollision bvhCollision; bvhCollision.Run();을 실행하면 아래 영상과 같이 실시간으로 충돌을 확인하는 결과를 보실 수 있습니다.

BVH_CollisionDetection.mp4

3.20MB

 또한, 1번 키와 2번 키를 활용하여 BVH를 사용했을 때와 사용하지 않고 전체 탐색을 했을 때 log창에 수행시간이 나오기 때문에 실제로 속도 차이가 얼마나 나는지 확인하실 수 있습니다. 제 컴퓨터에서는 아래와 같이 약 20배의 성능차이가 나는 것을 확인하였습니다. Face 숫자가 많아지면 많아질 수록 이 차이는 더 커지게 됩니다.

좌 - BVH를 활용한 충돌 확인, 우 - 전체 탐색을 활용한 충돌 확인

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

 

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

https://gitlab.com/bshong2850/blog_vtk

ByeongSun Hong / Blog_VTK

오늘은 Bounding Volume Hierarchy의 충돌에 대해 알아보았습니다. 다음 포스팅에서는 Parameterization에 대해서 이야기해보도록 하겠습니다.