OBB충돌

작성일 | In

OBB충돌 체크 알고리즘 설명입니다.
이 설명은 벡터를 다룹니다. 벡터와 벡터의 내적을 모르면 이해하기가 어려울 수 있습니다.

AABB와 OBB는 직사각형 모양의 Bounding Box를 이용해 객체들이 충돌했는지를 판단합니다.

AABB는 Axis Aligned Bounding Box 의 약자로, 축 방향으로 정렬된 경계 경계 상자(Bounding Box) 를 뜻합니다.
2차원으로 생각했을 때, 모든 변이 x, y축에 평행한 직사각형을 경계 상자로 정해 충돌 체크를 합니다.

반면, OBB는 Oriented Bounding Box의 약자로, 방향성이 있는 경계 상자(Bounding Box) 를 뜻합니다.
2차원으로 생각했을 때, 회전이 있는(회전이 된) 도형을 경계 상자로 정해 충돌 체크를 합니다.
(이 글에서는 2차원 OBB, 그 중, 경계 상자가 직사각형 형태인 경우만 다룰 것입니다.)

AABB와 OBB의 경계 상자(Bounding Box)는 그림 1-1처럼 되어있습니다.
(그림 1-1)

OBB는 분리 축 이론을 기반으로 동작합니다.

분리 축 이론을 간단하게 설명하자면,

1
두 볼록 다면체(혹은 볼록 다각형)를 분리할 수 있는 선(축)이 있다 ⇔ 두 볼록 다면체(혹은 볼록 다각형)는 충돌하지 않았다.

라고 할 수 있습니다. 그림 2-1을 보면 이해하기 쉬울 것 입니다.
따라서 OBB의 경계 상자(Bounding Box)가 직사각형 뿐만 아니라 다른 볼록 다면체, 혹은 볼록 다각형 형태도 가능하지만 이 글에서는 경계 상자가 직사각형인 경우만 다룹니다.

그림으로 그리는 건 쉽지만, 수학적으로 어떻게 분리 축을 찾아낼지가 문제입니다.
하지만, 그냥 볼록 다각형이 아닌 두 직사각형만 다루기 때문에 문제가 조금 간단 해집니다.

분리 축이 존재한다면, 어느 직선에 도형을 투영시켰을 때 투영된 구간이 겹치지 않는 경우가 생깁니다.
간단히 말해, 두 도형에 평행한 빛을 비추면 그 그림자가 겹치지 않는 각도가 존재한다고 할 수 있습니다. (그림 2-2 참고)

투영을 시키기 위해 벡터를 사용할 것 입니다. (여기부터 벡터의 개념이 들어갑니다. 이해가 어렵다면 벡터 관련 글을 읽으신 뒤, 이 내용을 보시는 것을 추천 드립니다.)


그림 2-1


그림 2-2

이제 벡터를 투영시켜 봅시다.
벡터를 단위벡터(크기가 1인 벡터)를 내적하면, 단위벡터와 평행한 직선에 투영된 크기를 얻을 수 있습니다. (내적의 기하학적 의미 이용)
컴퓨터의 XY좌표계는 상하(上下)가 반전되어 있습니다. 위쪽이 0도, 오른쪽이 90, 아래가 180, 왼쪽이 270도 입니다.
그러므로 x축과 시계 방향으로 각 θ를 이루는 단위벡터는 (cosθ, sinθ)로 나타낼 수 있습니다. 벡터A와 단위벡터U를 내적하면, 벡터A를 단위벡터U 의 방향으로 투영시킨 벡터의 크기를 얻을 수 있습니다. (그림 3-1 참고)

그림 3-1

이제 구체적으로 구현을 해보기에 앞서, 1차원에서의 충돌을 먼저 구상해봅시다.

1차원 공간에 길이가 4인 막대기A와 길이가 8인 막대기B가 있다고 생각해봅시다. 두 막대기의 거리를 7일때 두 막대기가 만날지 안만날지 생각해봅시다. (단, 막대기의 거리는 두 막대기의 중심의 거리를 뜻합니다.)

A는 중심으로부터 양 옆쪽으로 2만큼 뻗어있고, B는 중심으로부터 4만큼 뻗어있습니다. 중심 사이의 거리가 7이면, A와 B는 겹치지 않습니다. 중심 사이의 거리가 6이면 만나고, 6 초과면 만나지 않고, 6 미만은 겹칩니다.
일반화를 시키면, (식1) 을 만족할 때 두 막대기는 만나거나 겹칩니다.

식 1

이제 앞에서 만든 부등식을 활용해 2차원에서의 충돌 체크 알고리즘을 만들어봅시다.
그 전에 경계 상자를 벡터로 표현하는 방법을 알아봅시다.

OBB에서 직사각형을 결정하는 요소는 높이(Height), 너비(Width), 각도(Rotation), 총 3가지입니다. 저는 경계 상자를 높이와 너비로 표현하려고 합니다. 1차원에서의 충돌 체크 할 때 비교에 사용되었던 것은 막대기의 길이가 아닌 막대기의 길이의 절반 이였습니다. 그러므로 직사각형의 높이의 절반을 높이 벡터, 너비의 절반을 너비 벡터로 잡겠습니다. (그림 5-1 참고)

거리벡터를 d, 투영하는 곳의 단위벡터를 u, 직사각형A의 높이, 너비 벡터를 각각 Ah, Aw, 직사각형B의 높이, 너비 벡터를 각각 Bh, Bw로 잡겠습니다. (그림 5-2 참고)

이 때, (식2) 를 만족한다면, 그것은 단위벡터 u의 방향으로 투영된 것이 겹친다는 것입니다. 그러므로 Ah, Aw, Bh, Bw의 방향으로 투영 시켰을때 모두 위의 부등식이 성립한다면 두 직사각형은 겹친 것 입니다. 이 명제의 대우는 하나라도 부등식이 성립하지 않는다면 두 직사각형은 충돌하지 않은 것 입니다.


그림 5-1


그림 5-2


식 2

아래의 입력 조건에 맞춰 구현을 해봅시다.

직사각형A의 좌상단 꼭짓점의 y, x좌표가 주어지고 높이, 너비, 회전 각도가 입력되고,
직사각형B의 좌상단 꼭짓점의 y, x좌표가 주어지고 높이, 너비, 회전 각도가 입력된다고 가정하면 코드는 아래와 같이 작성하면 됩니다.
(단, 직사각형이 회전할 때에는 직사각형의 중심을 축으로 하여 회전하고, 회전 각도는 60분법으로 표현하며 오른쪽이 90, 아래가 180, 왼쪽이 270도 이다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

struct VECTOR{ //define vector
double x, y;
};

struct SHAPE{ //define shape
  double top, left, height, width, rot;
};

VECTOR addVector(VECTOR a, VECTOR b){ //vector plus
  VECTOR ret;
  ret.x = a.x + b.x;
  ret.y = a.y + b.y;
  return ret;
}

double absDotVector(VECTOR a, VECTOR b){ //vector inner
  return abs(a.x * b.x + a.y * b.y);
}

double Deg2Rad(double deg){ //deg -> rad
  return deg / 180 * 3.141592;
}

VECTOR getDistanceVector(SHAPE a, SHAPE b){ //distance vector
  VECTOR ret;
  ret.x = (a.left + a.width / 2) - (b.left + b.width / 2);
  ret.y = (a.top + a.height / 2) - (b.top + b.height / 2);
  return ret;
}

VECTOR getHeightVector(SHAPE a){ //height vector
  VECTOR ret;
  ret.x = a.height * cos( Deg2Rad(a.rot - 90) ) / 2;
  ret.y = a.height * sin( Deg2Rad(a.rot - 90) ) / 2;
  return ret;
}

VECTOR getWidthVector(SHAPE a){ //width vector
  VECTOR ret;
  ret.x = a.width * cos( Deg2Rad(a.rot) ) / 2;
  ret.y = a.width * sin( Deg2Rad(a.rot) ) / 2;
  return ret;
}

VECTOR getUnitVector(VECTOR a){ //unit vector
  VECTOR ret;
  double size;
  size = sqrt( pow(a.x, 2) + pow(a.y, 2) );
  ret.x = a.x / size;
  ret.y = a.y / size;
  return ret;
}

bool OBB(SHAPE a, SHAPE b){ //final check
  VECTOR dist = getDistanceVector(a, b);
  VECTOR vec[4] = {getHeightVector(a), getHeightVector(b), getWidthVector(a), getWidthVector(b)};
  VECTOR unit;
  for(int i=0; i<4; i++){
      double sum = 0;
      unit = getUnitVector(vec[i]);
      for(int j=0; j<4; j++){
          sum += absDotVector(vec[j], unit);
      }
      if(absDotVector(dist, unit) > sum){
          return false;
      }
  }
  return true;
}

int main(){
  SHAPE a, b;
  scanf("%lf %lf %lf %lf %lf", &a.top, &a.left, &a.height, &a.width, &a.rot);
  scanf("%lf %lf %lf %lf %lf", &b.top, &b.left, &b.height, &b.width, &b.rot);
  if(OBB(a, b)) printf("crash");
  else printf("Not crash");
}

addVector는 벡터의 덧셈 연산
absDotVector는 벡터의 내적의 절대값
Deg2Rad은 degree를 radian으로 변환

getDistanceVector는 거리벡터
getWidthVector는 너비벡터
getHeightVector는 높이벡터
getUnitVector는 단위벡터
를 구하는 함수입니다.

이미지 출처 http://cafe.naver.com/gameppt/98155