Object Oriented Bounding Box 를 이용한 Collision Detection

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를 잡기 때문에, 직육면체 모양의 물체를 가장 효율적으로 모델링할 수 있다.

 위로

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들의 조합) 

(상자  A 의 축들에 대해서 3개, 상자 B 축들에 대해서 3개, 그리고 A 에서 한축 그리고 B 에서 하나를 사용하여 9개의 외적들을 만든것이 총 15개) : [Gottschalk , SIGRAPH 에 실린 내용]

만일 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) 항을 나타낸다.

 위로

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

코드 다운로드

실행파일(exe) 다운로드

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

<코드설명>
CBox 클래스

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

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

D3DXMATRIX* GetBoxTransform(D3DXMATRIX *pMat, CBox* pBox)
pBox의 transform을 D3DXMATRIX 형태로 변환시켜 주는 일종의 wrapper 함수이다.

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

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

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

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

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

 위로

4. 참고 문헌

• 'When Two Hearts Collide: Axis-Aligned Bounding Boxes' by Jeff Lander
  
• 'Dynamic Collision Detection using Oriented Bounding Boxes' by David Eberly, Magic Software Inc. 
• 'OBBTree: A Hierarchical Structure for Rapid Interference Detection' by S. Gottschalk, M. C. Lin, D. Manocha, Dept. of Computer Science, University of North Carolina

5. 웹페이지 다운로드

웹페이지 전체 다운로드

 위로