BVH, Collision Detection(GJK+Minkowski sum)

1. 개념

 컴퓨터 그래픽스로 다양한 물체를 표현하면서, 충돌감지를 하기는 힘든 일이다. 스캔된 데이터가 크면 클수록(vertex 수가 많다거나..) 프로세싱 해야할 face 수도 자연히 늘어날 것이다. 단순하게 생각하면 N개의 vertex, M개의 vertex로 이루어진 두 objects를 collision detection 하는데 이를 단순히 학부 과정에서 생각하려면 힘들 것이다. 따라서 빠르고 정확하게 C.D. 하기위한 방법들을 소개한다. (3D 기준에서 모든 것을 설명할 것이다.)

2. BV

 Bounding Volume은 어떤 polygon으로 이루어진 물체를 포함하는 간단한 형태의 Volume이다. 예를 들어, 단순히 polygon-polygon 충돌감지를 하려면 매 timestep마다 triangle로 분해해서 서로 N*M번 체크하는 방법이 있는데, 멀리 떨어져있고 만날 확률이 적다면 sphere로 감싸서 sphere-sphere 충돌감지를 하는게 훨씬 쉬울 것이다. 왜냐하면 후자는 중심점에서의 거리만 알면 충돌했는지 알 수 있기 때문이다. 물론 엄밀히 알고리즘 상 최악의 시간을 줄이는 것은 아닐 것이다. 다만 대부분의 경우에서 줄여주기 때문에, 실용적인 방법이라고 할 수 있다.

3. BVH

 Bounding Volume Hierarchy는 물체가 여러개 있을때, 더 쉽고 빠르게 C.D. 할 수 있는 BV 여러개를 BV로 감싼 것을 말한다. BVH 간 C.D.는 따라서 여러번 이루어지는데, 이를 BVTT라 한다.

4. BVTT

 Bounding Volume Testing Tree는 'BV tree'(BVH라 생각하면 된다)간 C.D.하는 과정을 트리로 나타낸 것이다. 제일 큰 BV와 충돌했다면, 계속해서 그 밑의 BV로 내려가서 확인하는 것인데 일정 기준으로 두 BV 중 어떤 BV를 쪼개서 그 밑의 BV와 검사할 것인지 선택해야한다. BVTT는 실제로 구현할때 저장한다거나 하는건 아니고 추상적인 개념이다.

 testing시 front line을 저장하는 최적화 방법이 있는데, 이는 BVTT에서 충돌하기 직전의 node 위치를 모두 저장해서 다음 timestep에 충돌검사를 하면 그 위치부터 다시 검사하는 방법이다. 이 노드들의 위치를 front line이라 하여 라인으로 표현한다. 교과서에 소개된 한 논문은 front line을 사용할 때 다음 timestep마다 저장된 노드를 그들의 부모로 바꿔서 테스트 하면 가장 좋다고 한다. front line은 temporal coherence(잠깐동안 많이 움직이지 않았을 것이라는 특성)을 이용한 caching mechanism이다.

 만약 테스팅할게 많은데 timestep에 주어진 시간이 짧다면, 전체 BVTT 레벨의 루트부터 절반을 BFS로 탐색하고, 이후 C.D.된 노드들에 대해서만 DFS 하는 방법이 있다. 이렇게 한다면 충돌 가능성이 있는 부분이라도 대부분 알 수 있기에 사용된다고 한다. 아니면, 원래부터 충돌가능성이 높은 부분의 노드에 높은 priority를 주어 먼저 검사하기도 한다고 한다. 

5. Deformable model

 BV를 기껏 만들었는데, 물체의 모양이 바뀌어버리면 해당 물체의 BVH 모든 구성요소나 해당 물체에 대한 BV를 새로 만들어야한다. 때문에, OBB와 같이 만드는데 시간이 많이 걸리는 BV는 Deformable model에 적합하지 않다. AABB나 Bounding Sphere를 사용해서 빠르게 재구성해야한다.

 여기서도 짚고 넘어가야할 최적화 방법이 있는데, BVH에서 윗부분만을 재구성한다면 시간 절약을 할 수 있다. 아랫부분은 필요할때되서 만드는 방법인데, 이를 통해 굳이 충돌 안할, 재구성 안해도 되는 BV를 만들지 않고 넘어갈 수 있다. 여기서도 윗부분과 아랫부분은 이전 timestep의 BVH 레벨의 절반을 기준으로 나누는 것이 좋다고 한다. 

6. SAT (Separating Axis Theorem)

 어떤 두 convex 물체가 겹치는지 아닌지 확인하려면, 어떤 한 각도(∃angle)에서 바라봤을때(projection 했을 때) 분리되면 겹치지 않는다는 정리이다. 따라서 각진 BV(AABB, OBB 등)가 겹치는지 확인하려면, BV 간에 이룰 수 있는 모든 각도(OBB-OBB라면 한 OBB가 가지는 각 중 어떤 축과 다른 OBB가 가지는 각 중 어떤 축의 cross product로 projection해서 확인한다. 다음에 정확히 설명할 것임)들로 확인해서 분리되면 겹치지 않는 것이다.

BV 종류에 대한 설명은 아래 블로그를 참조하기 바란다.

AABB, Bounding Sphere, OBB, 2D GJK, Minkowski sum

https://m.blog.naver.com/PostView.nhn?blogId=wjdalsdl1016&logNo=220768308382&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

3D GJK

https://hamaluik.com/posts/building-a-collision-engine-part-3-3d-gjk-collision-detection/