Graphics Programming

AABB 정밀 충돌 감지 본문

Season 1/플래시

AABB 정밀 충돌 감지

minseoklee 2011. 1. 18. 15:49

머리 싸매고 고안한 건데 이미 있는 알고리즘이다 -_-
<게임 물리 바이블>을 읽다보니 거의 똑같은 알고리즘이 나오는데 Ron Levine이 만들었다고 한다.


파란 상자와 빨간 상자가 이렇게 휙 움직인다면 hitTestObject() 같은 걸로 충돌 검사를 해도 도중에 충돌하는 걸 감지할 수 없다.


그래서 목적은 도중에 충돌하는 순간을 구해서 나타내는 것이다.

상황 설정
1. 물체는 AABB(안 돌린 직사각형)이다.
2. 물체는 한 프레임 동안 등속직선운동을 한다.

목적 설정
물체의 속도를 v, 한 프레임 동안의 경과 시간을 t라고 하면 물체는 v * t 만큼 움직인다. 경과 시간을 기반으로 물체가 움직인다면 t의 단위가 밀리초겠지만, 지금은 초기 위치와 나중 위치를 설정하고 두 위치 사이의 차이를 v로 삼을 것이기 때문에 t를 1로 둔다. 두 물체가 움직이는 도중에 중간 쯤에서 충돌할 것이라면 대략 t = 0.5 이고 그러면 물체는 v * 0.5 만큼만 움직이는 식이다. 목적은 알맞은 t를 구하는 것이다. 도중에 충돌하지 않는다면 그냥 t = 1 이다.

이제 문제를 풀어야겠는데 두 상자가 동시에 움직이는 걸 따지려니 머리가 꼬여서 먼저 상대 속도로 문제를 조금 쉽게 만들자.

상대 속도는 어느 물체가 본 다른 물체의 속도인데 수식은 이렇다.
Vab = Vb - Va (Va는 a의 속도, Vb는 b의 속도, Vab는 a가 본 b의 속도)

정의든 수식이든 당장 와닿지는 않으니 다른 식으로 설명을 좀 하자면, a랑 b 둘 다 움직이는데 a가 멈춰있다 치고 a가 보기에 b는 어떻게 움직이는 지 알아보는 것이다. a와 b가 동일 속력으로 서로에게 접근하는 것과 a는 멈춰있고 b는 a에게 두 배 속력으로 접근하는 것 모두 a가 보기에 b는 같은 운동을 한다. (다른 물체 c가 있다면 a가 움직일 때와 멈춰 있을 때 분명 a는 차이를 느끼지만 지금 a와 b만 따지는 중이다) 그리고 a가 멈춰있다고 치는 이유는 a가 본 a의 속도는 0이기 때문이다. (a가 본 a의 속도 Vaa = Va - Va = 0)

그러니 이 문제를 풀 때도 상대 속도를 이용해서 한 물체는 고정시켜놓고 풀자는 말이다. 위 그림에서 파란 상자는 a, 빨간 상자는 b라고 하고 b가 본 세상을 분석한다. b는 멈춰 있는 셈이고 b가 본 a의 속도 Vba = Va - Vb 이다. 그러면
 vx = (a의 x방향 속도 - b의 x방향 속도)
 vy = (a의 y방향 속도 - b의 y방향 속도)
라고 놓고 잠깐 AABB간 충돌 조건을 살펴보자.

AABB인 a의 네 속성을 이렇게 정의한다.
a.left : a의 왼쪽 가장자리의 x좌표
a.right : a의 오른쪽 가장자리의 x좌표
a.top : a의 위 가장자리의 y좌표
a.bottom : a의 밑 가장자리의 y좌표

밑의 네 조건을 모두 만족하면 충돌한 것이다.
a.right - b.left > 0
b.right - a.left > 0
a.bottom - b.top > 0
b.bottom - a.top > 0

이유는 직접 그림 그려가면서 따져보시고;



이제부터 할 일이 중요한데 충돌하는 시간 범위를 x축, y축 따로 구하는 것이다. 지금 시각을 0, 속도대로 완전히 이동한 후 시각을 1이라고 하면
 a.right - b.left > 0
 b.right - a.left > 0
을 만족하는 시간을 따로 구하고
 a.bottom - b.top > 0
 b.bottom - a.top > 0
을 만족하는 시간을 따로 구하는 것이다. 그리고 두 구간이 [0, 1] 사이에서 겹치는 부분이 있으면 충돌이 일어나는 것이고 충돌이 일어나는 시각은 겹치는 구간에서 가장 작은 값이다.


그러면 x축 상에서 충돌하는 시간을 [txMin, txMax]라 하고 y축 상에서 충돌하는 시간을 [tyMin. tyMax]라 하고 txMin, txMax, tyMin, tyMax를 구해보자.

먼저 x축을 보는데 b가 본 a의 x방향 속도 vx가 vx=0, vx>0, vx<0일 때 이렇게 세 경우로 나눠서 따져보자.

1) vx = 0 일 때
시각 0인 지금 충돌하지 않으면 앞으로도 충돌하지 않는다.
 a.right - b.left > 0
 b.right - a.left > 0
지금 이 부등식을 만족하면 txMin = 0 , txMax = 1 이고 아니면 y축상 이동이야 어쨌든 시간 [0, 1] 내에서 둘은 충돌하지 않는다.

2) vx > 0 일 때
a.right와 b.left가 만나는 순간이 x축상에서 처음 겹치는 순간이고 b.right와 a.left가 만나는 순간이 마지막으로 겹치는 순간이다. 등속 직선 운동할 때의 공식 s = vt (이동거리 = 속력 * 시간)으로 간단하게 구할 수 있다.
* 시각 0일 때부터 x축상에서 겹쳐 있으면 txMin이 음수가 나오지만 신경쓰지 않아도 된다. a가 처음부터 속도 vx로 움직이는데 둘이 어느 정도 겹친 지금의 시각을 0이라고 정했으면 그 전부터 겹쳐있는 것이기 때문에 음수가 나온 것이라고 보자.
** 아예 시각 0일 때부터 a.left가 b.right보다 큰 상태면 txMin, txMax 둘 다 음수로 나오지만 역시 나중에 걸러지니까 걱정할 필요가 없다.

3) vx < 0 일 때
부호만 반대이지 별 다를 건 없다.

vx < 0이므로 vx에 -를 붙였다.

y축 상에서의 겹침은 또 계산할 필요도 없이 이렇게 구한다.

1) vy = 0 일 때
시각 0인 지금
 a.bottom - b.top > 0
 b.bottom - a.top > 0
을 만족하면 tyMin = 0 , tyMax = 1

2) vy > 0 일 때
  tyMin = (b.top - a.bottom) / vy
  tyMax = (b.bottom - a.top) / vy

3) vy < 0 일 때
  tyMin = (a.top - b.bottom) / (-vy)
  tyMax = (a.bottom - b.top) / (-vy)

x축 상에서 left에서 right로 가는 쪽이 좌표값이 커지는 방향이라 식이 저렇게 나온 것이고 y축 상에서는 top에서 bottom으로 가는 쪽이 좌표값이 커지는 방향이니 left를 top으로, right를 bottom으로, vx를 vy로만 바꿔주면 된다.

이제 다음의 세 조건을 만족하면 충돌이 일어난 것이고 충돌 시각을 구할 수 있다.
1) [txMin, txMax]가 [0, 1]과 겹친다
2) [0, 1]과 [tyMin, tyMax]가 겹친다
3) [tyMin, tyMax]가 [txMin. txMax]와 겹친다
-> 충돌 시각 t 는 t = max(txMin, tyMin, 0) 이다.

마지막으로 지금까지 설명한 걸 구현한 플래시를 올리고
 
상자를 누르고 끌어서 다음 위치를 정하고 실행
Comments