게임에서 사용하는 수학 활용 공부(3) OBB 충돌

1. OBB(Oriented Bounding Box) 충돌

OBB는 축에 정렬되지 않은 직사각형(2D) 또는 직육면체(3D) 충돌 박스이다.

AABB충돌과 달리 OBB는 회전이 가능하여 회전된 오브젝트에 대한 충돌 감지가 더 정확하게 이루어진다.

 

AABB와 OBB의 차이점은

 

1. 정렬방식 : AABB는 월드 좌표계 기준으로 축에 정렬됌, OBB는 로컬 좌표계 기준으로 기울어질 수 있다.

2. 회전 가능 여부 : AABB는 불가능(회전 시 크기가 커짐), OBB 가능(기울어진 형태를 유지함)

3. 충돌 감지 속도 : AABB는 단순 값 비교로 빠름, OBB 기하학적 계산이 필요하여 상대적으로 느림

4. 정확도 : AABB는 물체가 회전 시 에는 비효율적으로 낮음, OBB는 객체 크기에 딱 맞게 조정 하기에 높음

 

1. 2D OBB 충돌 감지 방법

1.SAT(Separating Axis Theorem, 분리 축 정리) 이용

SAT는 두 개의 도형이 충돌하지 않으려면 어느 한 축에서라도 겹치지 않아야 한다는 원리를 이용한다.

쉽게 말하자면 두 도형에 여러 각으로 평행한 빛을 비추었을때, 그 그림자가 겹치지 않는 각도가 존재하는지에 대한 유무에 따라 충돌이 이루어진다.

 

해당 과정을 투영한다라고 하며, 투영 시키기 위해서는 벡터를 사용하여 문제를 풀 수 있다.

해당 이론은 볼록다각형의 경우에만 적용이 가능하다.

 

그렇다면 수학적으로 어떻게 분리 축을 찾을 수 있을까.

 

벡터를 단위벡터(크기가 1인 벡터)를 내적해준다. 즉 정규화된 벡터를 내적하여준다.

단위 벡터와 평행한 직선에 투영된 크기(스칼라 값)를 얻을 수 있다.

||A||, ||B||는 각 벡터의 크기(길이)

θ 는 두 벡터 사이의 각도

cosθ 는 두 벡터의 방향성으로 

벡터 A를 벡터 B 방향으로 얼마나 투영할 수 있는지를 나타낸다.

 

구체적으로 구현을 하기에 앞서 1차원에서의 충돌로 생각을 해보자

 

1차원 공간에 길이가 4인 막대 A, 길이가 8인 막대 B가 있다고 했을때

중심사이의 거리 d가 6미만이면 충돌이 일어난것이고 6 초과면 만나지 않는다.

 

 

 

이런식으로 표현이 된다.

자 그러면 이제 2D에서의 직사각형으로 생각해보자

 

OBB에서 직사각형을 결정하는 요소는 높이, 너비, 각도 총 3가지 이다.

1차원에서의 충돌 체크할 떄 비교에 사용된건 막대기 길이가 아닌 막대기 길이의 절반 이었다.

그렇기 때문에 직사각형의 높이의 절반을 높이벡터, 너비의 절반을 너비벡터라고 표현하고 시작하겠다.

 

거리 벡터 d, 투영하는 곳의 단위 벡터를 u,

직사각형의 A의 높이, 너비벡터를 각각 Ah, Aw, 

직사각형의 B의 높이, 너비벡터를 각각 Bh, Bw로 한다.

 

코드 구현

 

1. 중심 간 거리 벡터 D 구하기

Vector2D d = other.center - center;

d = other.center - center = d(dx, dy) 두 박스의 중심 좌표를 기준으로 중심 간 거리 벡터를 구해줌

 

2. 검사할 투영 축 설정

Vector2D axes[4] = { axisX, axisY,  other.axisX, other.axisY };

Vector2D axis = axes[i].normalize();

 

검사할 축은 총 4개로

A박스의 X, Y축,  B박스의 X,Y 축

각 축은 단위벡터로 정규화 하여 사용해야 한다.

 

3. 중심 거리의 투영 길이 proj1

float proj1 = fabs((d.dot(axis))) / axis.length();

중심 거리 벡터 d를 검사할 축 axis에 투영한 길이 proj1은 내적을 사용하여 구해준다.

이는 중심 간 거리가 특정 축을 따라 얼마나 떨어져 있는지를 나타낸다.

 

 

4. 두 박스의 투영된 반지름의 합 proj2

 

float proj2 = halfwidth * fabs(axisX.dot(axis)) +
halfheight * fabs(axisY.dot(axis)) +
other.halfwidth * fabs(other.axisX.dot(axis)) +
other.halfheight * fabs(other.axisY.dot(axis));

 

각 OBB의 크기를 axis 방향으로 투영한 후, 두 OBB의 투영 반지름을 합산한다.

각 OBB의 X,Y축 벡터를 axis 축에 내적하여 크기를 투영한다.

 

axis 방향으로 OBB가 차지하는 공간의 총합을 의미한다.

 

 

5. 충돌 판정 조건

충돌 조건은 proj1이 proj2 보다 크면 두 OBB가 떨어져 있는 것으로

즉, 하나라도 충돌이 없으면 바로 false를 반환하고

모든 축에서 겹치면 충돌이 있는 것으로 true를 반환한다.

 

6. 코드 예제