http://www.gingaminga.com/Data/Note/oriented_bounding_boxes/


Object Oriented Bounding Box  이용한 Collision Detection

96419-044

원선

출처; http://mimosa.snu.ac.kr/~rabbit2/

 

<목차>

  1. 소개글
  2. 이론
  3. 코드 다운로드  사용법
  4. 참고 문헌
  5. 웹페이지 다운로드

 

1. 소개글

지금까지 리서치 주제로 BSP tree 라던지 bounding sphere에 의한 collision detection(이하 CD)은 많이 있었는데그에 비해 bounding box에 의한 CD에 대한 글은 없었던 것 같다물론, bounding sphere에 의한 CD의 쓰임새도 많지만(예를 들어 당구공에 의한 CD라던지), 생각해 보면 우리 주위에 있는 물체 중에서 둥근 것보다는 네모난 것이 훨씬 더 많다는 것을 알 수 있다만일 직육면체에 가까운 물체를 bounding sphere로 모델링하게 되면밑에 그림에서 볼 수 있듯이 많은 공간이 남게 되고이 공간을 줄이기 위해서는 depth가 여러 레벨인 sphere tree를 구성할 수 밖에 없다그럼에도 불구하고 bounding sphere가 널리 이용되는 가장 큰 이유는, bounding sphere가 구현하기가 가장 쉽기 때문인 것 같다. Bounding sphere로 일단 모델링하고 나면 CD를 하기 위해서 단순히 두 구 사이의 거리를 측정해서 각 구의 반지름의 합과 비교하기만 하면 된다.
Bounding box
에 의한 모델링은 axis-aligned bounding box(이하 AABB) object-oriented bounding box(이하 OBB) 두 가지 방법이 있다. AABB bounding box를 잡을 때 항상 world coordinate system 3개의 축과 평행한 방향으로만 잡는 것이고이것은 bounding sphere와 마찬가지로 구현하기는 매우 쉬우나역시 물체가 world coordinate system 축과 다른 방향으로 놓이게 되면 많은 빈공간이 생기게 되어 효율이 급격하게 떨어지게 된다당연히 직육면체 모양의 물체를 가장 효율적으로 모델링하기 위해서는 그 물체가 놓여 있는 방향으로 bounding box를 잡는 것인데이것이 바로 OBB이다하지만 OBB는 구현하기가 비교적 난해하므로 지금까지 리서치가 안 되었었던 것 같은데필자는 최대한 잘 설명하려고 노력하겠다 -_-;;;

<bounding sphere>

직육면체의 물체를 모델링하기 위해서는 여러 개의 구가 필요하고구에빈공간이 생겨서 정확히 모델링이 되지 않는다.

 

 

<axis-aligned bounding box>

물체가 world coordinate axis와 다른 방향으로 놓여 있을 때 효율이 급격하게 떨어진다.

 

 

<object-oriented bounding box>

물체의 방향을 중심으로 bounding box를 잡기 때문에직육면체 모양의 물체를 가장 효율적으로 모델링할 수 있다.

anigray09_up.gif 위로

2. 이론

Mesh를 생성할 때 bounding box도 같이 생성하여, mesh transform 할 때 bounding box도 같이 transform을 해 주면 항상 모든 mesh에 대해 OBB를 유지할 수가 있다그렇다면 우리는 이제 mesh가 움직이면서 같이 돌아댕기는 여럿의 OBB를 갖고 있다이 때, OBB가 서로 충돌했는지는 어떻게 감지할 수가 있을까가장 무식한 방법은 두 개의 OBB의 모든 면과 모든 edge에 대해서 면을 통과하는 edge가 있는지 검사하는 방식일 것이다그런데 이 방식은 144번의 비교가 필요하고상당히 비싼 테스트이다여기서는 훨씬 더 효율적인 'axial projection'을 이용한 테스트를 소개한다.

Axial projection 이란 무엇인가?

두 개의 OBB가 서로 분리되어 있는지를 알기 위한 쉬운 방법 중 하나는 OBB를 공간상의 어떤 축(반드시 x,y,z축일 필요는 없다)에 투영하는 것이다이 투영을 'axial projection'이라고 하며이 투영을 통해 각 OBB는 축 상에 어떤 interval을 형성한다.만일 이렇게 형성된 2개의 interval이 서로 겹치지 않으면 2개의 OBB는 서로 분리되어 있는 것이 확실하며이때 이 축을 'separating axis'라고 한다만일 2개의 interval이 서로 겹친다면 2개의 OBB는 서로 분리되어 있을 수도 있고 아닐 수도 있기 때문에 더 많은 검사가 필요하다.

2개의 OBB가 충돌했는지 알기 위해서는 axial projection을 몇 번 해야 하는가?

(공리)
공간상의 2개의 분리된 convex한 다각면체는 1) 두 개의 다각면체 중 하나의 어느 면과 평행인 면또는 2) 두 개의 다각면체 각각에서 하나의 edge와 평행한 면에 의해 분리될 수 있다.

이 공리를 증명한 논문도 있긴 하지만그것은 관심있는 분은 찾아 보시고어쨌든 이 공리의 결과로서우리는 다음을 알 수 있다:
공간상의 2개의 convex한 다각면체가 분리되기 위한 필요충분 조건은, 1) 두 개의 다각면체 중 하나의 어느 면과 수직인 separating axis가 존재하거나, 2) 두 개의 다각면체 각각에서 하나의 edge와 수직인 separating axis가 존재하는 것이다.

 OBB 3개의 unique한 면 방향이 있고, 3개의 unique edge 방향이 있다따라서 위의 조건을 검사하기 위해서는 15개의 separating axis를 검사해야 한다.(하나의 OBB에서 3개의 면다른 OBB에서 3개의 면, 9개의 2개의 OBB에서 edge들의 조합만일 2개의 OBB가 서로 분리되어 있다면(충돌하지 않았다면) separating axis가 반드시 존재해야 하고 위에서 언급한 15개의 axis 중 하나가 그 axis가 되어야 한다만일 OBB들이 충돌했다면 separating axis가 존재하지를 않을 것이다따라서, 2개의 OBB의 충돌 여부를 검사하기 위해서는 15개의 seperating axis의 검사로 충분하다.

Separating axis 검사는 어떤 방식으로 할 수가 있는가?

이 검사를 하는 기본적인 전략은 다음과 같다:
1) 
 OBB의 중심을 해당 axis에 투영한다.
2) 
 OBB가 해당 axis에 투영되었을 interval radius(길이의 반)을 계산한다.
3) 
만일 해당 axis에 투영했을 때 OBB의 중심 사이의 거리가 각 OBB interval radius의 합보다 크면두 개의 OBB는 분리된 것으로 볼 수 있다.

밑에 있는 그림을 보면 이해가 더 쉽게 갈 것이다그림에서 A B는 각각 OBB이고 B A로부터 rotation R translation T만큼 이동한 위치에 있다. A B half dimension(또는 radius) 는 각각 ai, bi로 표기한다(i=1,2,3). A B에서 각 edge와 평행을 이루는 axis의 단위 벡터를 각각 Ai Bi라고 표기한다(i=1,2,3). 이렇게 해서 생긴 6개의 단위 벡터를 box axis라고 하자여기서 주목할 것은 A box axis basis로 사용하면회전 매트릭스 R 3개의 column(x,y,z 단위벡터를 transform 했을 때 나오는 벡터) 3개의 Bi axis 벡터와 같다는 사실이다.





<여기서 A B L에 투영하면 서로 분리된 interval이 되므로 L OBB A B에 대한 separating axis이다.>

보다시피 각 OBB의 중심은 투영된 interval의 중간에 투영된다 box radius axis L에 투영하고 투영된 길이의 합을 구함으로써 우리는 각 OBB의 투영된 interval을 구할 수가 있다위에서 OBB A interval radius는 다음과 같다:



OBB B에 대해서도 비슷한 식을 세울 수가 있다. Seperating axis의 위치는 검사에 아무런 영향을 끼치지 않으므로 우리는 axis가 A의 중심을 통과한다고 가정한다. 이 때, 2개의 interval 사이의 거리는   가 된다(그림 참고). 따라서, 2개의 interval 분리되어 있기 위한 필요충분 조건은 다음과 같다:



이 식은 액면으로는 복잡하지만, 15개의 separating axis에 적용하게 되면 L이 box axis이거나 box axis의 cross product가 되기 때문에 많이 단순화 된다. 예를 들어, 이라고 하자. 



위의 식에서 첫 번째 summation의 두 번째 항은 다음과 같이 단순화 된다.




마지막 단계는 전에 언급했듯이 B의 box axis는 A에 대한 B의 rotation matrix R의 column에 해당한다는 사실을 이용한 것이다. 이런 식으로 모든 항들은 단순화되고 때로는 값이 0이 되어 없어지기도 한다. 이렇게 단순화한 이후의 위의 seperating axis L에 대한 검사는 다음과 같이 된다:





모든 15개의 seperating axis에 대한 검사는 이런 방식으로 단순화되며, 이 검사의 과정에서 matrix R의 각 항은 4번씩 사용이 되므로 모든 검사를 시작하기 전에 matrix R을 미리 계산해 놓는다. 만일 이 검사 도중 식이 만족이 되면, seperating axis를 발견한 것이고, 그렇다면 2개의 OBB는 서로 분리되어 있음을 밝힌 것이 되기 때문에 나머지 검사는 할 필요가 없어진다. 아래의 표는 15개의 seperating axis에 대한 식을 정리한 것이다:






여기서 R0 항목은 OBB A interval radius, R1 항목은 OBB B interval radius, R 항목은 2개의 OBB의 중심 간의 투영된 거리를 나타낸다.
* D 
벡터는 2개의 OBB의 중심을 잇는 벡터를 나타낸다.
Cij 
 rotation matrix R에서의 (i,j항을 나타낸다.

anigray09_up.gif 위로

3. 코드 다운로드 및 사용법

aniapple_red.gif코드 다운로드

aniberry02_red.gif실행파일(exe) 다운로드

<실행방법>
 
그냥 가만히 실행시키고 기다리고 있으면 차가 건물에 가서 쿵.. 하고 박는다 -_- 화살표로 시점을 약간 변화시킬 수 있다.

<코드설명>
circle01_black.gifCBox 
클래스

CBox

Object oriented bounding box를 표현하는 클래스

CBox::center[3]

Bounding box의 중심 좌표

CBox::axis[3][3]

Bounding box 3 방향으로의 axis 벡터

CBox::extent[3]

Bounding box의 각 axis 벡터 방향으로의 radius

circle01_black.gifint BoxBoxIntersectionTest(const CBox& box0,const CBox& box1)
box0 
 box1이 서로 교차하는지 검사를 해서 교차를 하면 1, 그렇지 않으면 0을 리턴한다함수의 동작방식은 위의 표에 있는 15개의 seperating axis를 하나씩 검사하는 방식이다주석을 보고 표를 참고하면 이해하는데 아무런 어려움이 없을 것이다.

circle01_black.gifD3DXMATRIX* GetBoxTransform(D3DXMATRIX *pMatCBoxpBox)
pBox
 transform D3DXMATRIX 형태로 변환시켜 주는 일종의 wrapper 함수이다.

circle01_black.gifvoid SetBoxTransform(const D3DXMATRIX* pMatCBoxpBox)
위 함수와 쌍을 이루는이번에는 pMat transform pBox axis 벡터로 변환을 해 주는 함수이다.

circle01_black.gifvoid initBox(CBox *pBox, const D3DXVECTOR3& vecMin, const D3DXVECTOR3& vecMax)
Mesh
로부터 구해 온 bounding box minimum 좌표, maximum 좌표를 받아서 pBox center extent를 계산하고 axis를 초기화한다.

circle01_black.gifvoid moveBox(CBox *pBox, const D3DXMATRIX& mat)
pBox
 mat에 의해 움직인다일단 3개의 axis들을 변환한 이후에 center를 변화하는 방식으로 되어 있다.

circle01_black.gif이 함수들을 이용해서 코드는 다음 순서로 동작하면 된다:

  1. Mesh를 로드 한 후에 D3DXComputeBoundingBox를 이용하여 bounding box를 계산한다.
  2. Bounding box로부터 얻은 값을 이용하여 initBox CBox 객체를 초기화한다.
  3. 이후에 문제가 움직일 때마다 변환 matrix를 인자로 moveBox를 호출해 CBox 객체를 갱신해 준다.
  4. 움직일 때마다 그 CBox와 다른 CBox들이 충돌이 일어났는지 BoxBoxIntersectionTest로 검사한다.

anigray09_up.gif 위로

4. 참고 문헌

5. 웹페이지 다운로드

aniberry01_red.gif웹페이지 전체 다운로드

anigray09_up.gif 위로



저작자 표시 비영리 동일 조건 변경 허락
신고

+ Recent posts