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

0. 들어가기 앞서

 이전 포스팅에서 AABB, Sphere Bounding Box의 Collision Check 하는 방법에 대해서 알아본 뒤 Collision 됐을 시에 VTK를 활용해 Bounding Box의 색을 변경해 가시화 해보았습니다.

https://mathmakeworld.tistory.com/106

TMI(Triangle Mesh Information) Project #6.2 - AABB, Sphere Bounding Box Collision Detection

이번 포스팅에서는 OBB의 Collision Check를 하고 이 전과 같이 Collision 됐을 때 Bounding Box의 색을 변경해 가시화 해보도록 하겠습니다.

 

1. OBB 정보 받아오기

 이전 포스팅에서 OBB는 총 3가지 값을 가지고 있다고 했습니다.

 - Axis : 3가지 방향으로 각각의 방향 벡터

 - Extent : 각각의 방향 벡터로 가지는 Box의 크기

 - Center : Center 좌표

위의 정보들은 vtkOBBTree Filter를 사용하여 아래와 같이 받아올 수 있습니다.

OBB 정보 저장

ComputeOBB라는 함수를 통해 OBB의 한 corner값과 3축을 받아올 수 있습니다. 이 값을 토대로 extent와 center값을 계산하여 저장해 주었습니다.

 

2. OBB Class

 위에서 계산한 값들을 관리하기 위해서 아래와 같이 OBB Class를 만들었습니다.

OBB Class

또한, 연산을 편하게 하기 위해 CVec이라는 Class도 만들어서 여러가지 Operation들을 오버로딩해 두었습니다. Git Code Util 폴더에서 확인하실 수 있습니다.

 

3. Bounding Box Rendering

 다음으로는 Bounding Box를 Rendering 해주기 위해서 각 꼭지점의 좌표를 계산하고 각 꼭지점을 Line으로 이어주는 작업이 필요합니다. 아래 코드에 주석으로 그려놓은 그림과 같이 꼭지점 번호를 임의로 지정하였고 각 꼭지점에 맞게 좌표를 설정해 주었습니다.

OBB Set 8 Points

그 다음으로는 아래와 같이 vtkAppendPolyData Filter를 활용하여 Line들을 하나의 PolyData로 만들어주었습니다.

AppendPolyData를 활용한 12 Line 하나로 만들기

이렇게 생성된 Actor를 Rendering 해주게 되면 아래 스크린 샷 처럼 OBB가 가시화됩니다.

가시화된 OBB

 

4. 2D OBB Collision Check

 OBB Collision Check는 분리축 이론에 기초합니다.

분리축 이론이란 두 볼록(중요!) 다각형(3D에서는 다면체)을 분리하는 선이 있다면 두 다각형(다면체)는 겹치지 않는다. 라고 간단하게 적을 수 있습니다. 

 간단하게 2D에서 설명해 보자면 아래 그림에서 파란색과 빨간색의 두 직사각형이 있고, 두 직사각형을 분리하는 선(초록 점선)이 존재합니다. 또한, 분리하는 선에 직교되는 선을 Separating Axis라고 합니다. 

 2D Box에서는 box1과 box2의 두 Axis 벡터가 Separating Axis가 됩니다. 그러면 총 4개의 Separating Axis가 나오게 되고, 4번의 충돌검사가 필요하게 되는 것입니다.

 각각의 충돌 검사는 두 박스의 4 Axis 벡터 * extent를 Separating Axis에 내적한 합이 두 중심을 이은 벡터가 Separating Axis에 내적한 길이보다 크면 충돌 하지 않았다고 판단합니다. 이렇게 말로 적어두면 어려우니 하나씩 확인해보도록 하겠습니다.

 

  4-1 두 중심을 이은 벡터가 Separating Axis에 투영된 길이

    아래 그림과 같이 두 박스의 중심을 이은 벡터(검정색 화살표)를 Separating Axis(노란선)에 투영한 결과(검정색 선) 입니다. 이 길이가 기준이 됩니다.

  4-2 box1의 두 Axis 벡터 * Extent가 Separating Axis에 투영된 길이

    아래 그림은 box1의 두 Axis 벡터 * Extent를 투영한 결과를 나타낸 것입니다.

 

  4-3 box2의 두 Axis 벡터 * Extent가 Separating Axix에 투영된 길이

    아래 그림은 box2의 두 Axis 벡터 * Extent를 투영한 결과를 나타낸 것입니다. box2의 axis2는 Separating Axis와 수직이므로 투영했을 때의 길이는 0이 되기 때문에 표시하지 않았습니다.

  4-4 길이 비교

    각 거리를 더해 비교해보면 Axis 벡터 * Extent가 투영된 거리의 합보다 두 box의 Center를 이은 벡터가 투영된 거리가 더 긴 것을 확인할 수 있습니다. 따라서 두 Box는 충돌하지 않았다 라고 판단 할 수 있게 됩니다.

 

 5. 3D OBB Collision Check

 그렇다면 3D OBB는 어떻게 Collision Check를 하게 될까요? 3D OBB는 총 15개의 Separating Axis를 체크해야합니다. Box1의 Axis 3개 + Box2의 Axis 3개 + (Box1의 Axis와 Box2의 Axis의 외적 3x3 총 9개)

 이 내용은 아래 블로그를 참고하였고 쉽게 잘 적어놨으니 읽어보시면 이해가 되실 겁니다.

https://3dmpengines.tistory.com/1339

Object Oriented Bounding Box 를 이용한 Collision Detection

 

이제 실제로 코드 상에서 어떻게 돌아가는지 확인해볼 차례입니다. 아래 이미지를 보시면 

 centerDist가 두 Box의 Center간의 거리를 투영한 결과이고 그 밑으로 각 Box의 3축에 대해 투영한 거리입니다. 그래서 총 6개의 투영한 거리의 합이 center간의 거리보다 짧다면 분리축이 존재하는 것이고, 두 OBB는 충돌하지 않았다고 판단할 수 있습니다.

Separating Axis가 있는지 확인

 위의 과정을 총 15개의 Separating Axis에 대해 진행하고 단 하나라도 충돌이 됐다고 판단된다면 충돌처리하였습니다. 코드는 아래 그림과 같습니다. 모든 코드는 Git에 올려놓았으니 확인 및 Test가 가능합니다.

15개의 Separating Axis를 확인

6. Test Code

 지금까지 설명한 내용들을 토대로 Collision이 되면 Bounding Box가 빨간색이 되도록 Code를 짜보았습니다. 아래 이미지는 두 Cat Model에 대해서 OBB를 생성하고 Collision이 되어 빨간색으로 표현된 상태입니다.

 실제로 받아서 실행해보시면 여러 Key를 가지고 Collision Test를 해보실 수 있습니다.

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

 

 

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

https://gitlab.com/bshong2850/blog_vtk

ByeongSun Hong / Blog_VTK

오늘은 OBB Collision Detection에 대해 알아보았습니다. 다음 포스팅에서는 Bounding Volume Hierarchy에 대해 알아보도록 하겠습니다.