충돌 체크: Oriented Bounding Box

이전 글 AABB에 이어서,
위의 그림과 같은 경우 AABB 테스트에서는 충돌로 판정된다.
하지만 이것은 우리가 원하는 충돌 판정이 아니다. 따라서, 필요하다면 Oriented Bounding Box 방식으로 보다 세밀하게 충돌 판정을 해 줄 필요가 있다.
OBB란 바운딩 박스가 회전 되어서 좌표축에 나란하지 않다는 얘기다.


OBB 방식의 충돌 문제를 구현하기 위한 여러 방식들 가운데 SAT라는 것이 있다.

Separating Axis Theorem


  • 두 개의 바운딩 박스가 서로 충돌하지 않는다면, 둘 사이를 가르는 직선이 존재한다.
바꾸어 말하자면, 둘 사이를 가르는 임의의 직선이 존재한다면, 두 개의 바운딩 박스는 서로 충돌하지 않는다고 할 수 있다.

위 그림에 그린 임의의 붉은 직선이 Separating Axis이다.
Separating Axis에 직교하는 다른 직선에 바운딩 박스를 투영시켜 보자. 이 때 직선 상에 투영된 두 개의 선분이 서로 겹치지 않는다면 두 개의 바운딩 박스는 서로 충돌하지 않는다고 말할 수 있다.

그렇다면,

Separating Axis는 어떻게 찾을 것인가.

라는 새로운 문제를 맞이하게 된다.

  • Separating Axis는 다각형을 구성하고 있는 변들 중 하나 이상과 나란하다.

절차
바운딩 박스를 구성하는 변들 중 하나를 선택해서,
그 변과 나란한 가상의 축에 직교하는 임의의 축을 가정하고,
그 축에 바운딩 박스를 투영시킨다.
만일, 두 개의 선분이 겹치지 않으면 서로 충돌하지 않음으로 판정하고 종료,
두 선분이 서로 겹친다면 다른 변을 선택해서 반복 수행.

사각형 vs 사각형의 문제인 경우 최대 8개의 축에 대해 충돌 테스트를 시행해 보아야 한다. 그러나, 위 그림과 같이 서로 나란한 변이 있다면 시행 횟수는 줄어든다.



[Tip]
OBB는 직사각형이 아니어도, 다각형이어도 적용 가능하다. 그러나, 모서리가 안쪽으로 파인 모양에는 적용이 안된다.

[참고]
http://www.dyn4j.org/2010/01/sat/


댓글

이 블로그의 인기 게시물

자바 암호화 확장 (JCE) 관련 자바 1.8.0_151 이후 변경 사항

좌표 변환: 회전 이동

HTTP POST