2D충돌 알고리즘 AABB, OBB, SAT

BoundingBox

https://www.peopleforai.com/glossary/bounding-box/

객체간에 충돌을 검사하기 위한 단순한 모양인 박스,구,캡슐 형태를 말한다.

AABB

AABB(Axis Aligned Bounding Box) : 정렬된 축의 박스끼리의 충돌

AAB는 아래 2가지 조건이 모두 충족해야한다.

1. 두 사각형 중점 x거리(너비) < (두 사각형 가로 HalfSize 합)

2. 두 사각형 중점 y거리(너비) < (두 사각형 세로 HalfSize 합)

1. 세로, 2. 가로, 3. 가로세로 충돌

 

비교적 간단한 연산으로 정렬된 축으로 이루어진 충돌박스만 존재할때 적절하다. 

이런 상황에서는 AABB 충돌검사로 애매한 상황이 발생한다.

빨간색 사각형에 BB는 초록색 BB와 충돌했지만, 우리에게 보여지는 빨간색 사각형은 아직 충돌하지 않은 상태다.

이 문제점을 보완한 OBB+SAT로 좀 더 정교한 충돌체크를 할 수 있다.

 

OBB

OBB(Oriented Bounding Box) : 박스와 함께 축도 회전

OBB충돌 여부는 SAT를 통해 충돌 여부를 판단한다. 

 

SAT란?

'두 도형이 충돌하지 않는 분리 축이 단 하나라도 존재하면, 두 도형은 충돌하지 않는다'라는 이론이다.

즉 모든 기준 축들에서 투영구간이 겹치면 충돌이다라는 말이다.

 

여기서 기준 축은 각 박스가 가지고 있는 고유한 방향의 수직벡터이다. (쉽게 Up벡터와 Right벡터이다.)

 

OBB vs OBB SAT 충돌검사 과정

1. 검사 축 4개 구하기 

박스 A의 Right 방향, 박스 A의 Right 방향, 박스 B의 Up 방향, 박스 B의 Right 방향

 

2. 충돌 검사 방법

1) 각 축을 단위벡터로 정규하한다. (크기는 필요없기 때문에)

2) 두 박스의 모든 꼭지점을 그 축에 dot연산으로 투영한다. 결과는 스칼라 값

 

3) 두 박스의 투영 구간 [minA, maxA], [minB,maxB]를 비교한다.

 

4) 한 축에서라도 겹치지 않는 구간이 발생하면 충돌하지 않는다.

5) 모든 축에서 겹친다면 충돌 상태이다.