(의역) Separating Axis Theorem(SAT) 설명

[원문]

https://www.sevenson.com.au/actionscript/sat/


Separating Axis Theorem(SAT)는 볼록다각형(convex polygons) 사이의 충돌을 계산하기 위한 기법입니다.

 전 결코 전문가는 아니지만, 저에게 Collision Detection이 필요해진 다음부터,
저는 관련 자료들을 모아왔고, 결국 이를 ActionScript 3로 구현했습니다.

다른 이들이 (저와 같이) 고통을 겪지 않았으면 하는 마음에, 이를 공유합니다.

Flash에서 Polygon들 사이의 충돌계산이 필요함을 느꼈을 때부터,
저는 일명 '분리축 검사 이론(SAT)'로 알려진 이 방법을 알게되었습니다. 유일한 문제는, 제가 이를 제 것으로 만들기위해 엄청나게 고생했다는 것이지요.

아주 많은 Collision Detection 자료를 읽고, 코드 샘플을 조사한 뒤에야 파악할 수 있었습니다.
수포자(?)들을 위해, 먼저 이 이론의 기본적인 원리가 어떻게 작동하는지를 가볍게 살펴보겠습니다.

The quick rundown

일반적으로, SAT의 목적(그리고 다른 모든 Collision Detection 기법) 의 목표는

두 Shape 사이에 간격이 존재하는 지를 테스트 하는 것입니다.

 제가 아는, SAT에 대한 가장 좋은 비유는 다음과 같습니다.

[ 횃불을 켠 다음, 당신이 테스트 하려는 두 Shape를 다른 각도로 비춘다고 상상해 보세요. 

어떤 그림자의 형태가, 그 두 Shape 바로 뒤의 벽에 나타날까요? ]

만약 당신이 그 Shape들 주위를 돌면서 테스트 해보고, 그 그림자들 사이에서 아무런 간격(gap)을 발견하지 못한다면, 그 두 Shape는 틀림없이 접촉하고 있을 것입니다.
 반대로 만약 간격을 찾는다면, 분명히 접촉하지 않은 상태일 것입니다.

Programming의 관점에서, 이는 어~엄청 많은 모든 각도에서 이를 Check해야 함을 의미 할 것입니다.
 다행인 것은, Polygon의 법칙 덕분에 Check 해야할 key 각도의 수는 몇개 되지 않는다는 것입니다.

 당신이 check 해야 할 각도(Angle)의 수는 polygon의 변의 수와 같습니다.
이는 check 해야 할 최대 angle의 수는, 두 shape의 변의 수의 합과 같다는 것입니다.
(ex - 두 5각형은 10개의 angle을 체크해야 합니다.)

(해당 포스트는 2D Collision으로 상황을 한정한 것 같음)

So how do you make it work in code?

아주 간단하지만, 반복적인 방법입니다. 차근차근 살펴보지요.

[ STEP 1 ]

테스트 하려는 polygon 중 한개의 변을 선택하고, 그 변의 normal vector를 찾으세요.
이것은 '축(Axis)'이 될 것입니다.

[ STEP 2 ]
첫번째 polygon의 모든 꼭짓점을 순회하면서, (각 꼭짓점을) 축에 projection 하세요.
(동시에, 이 polygon에 대한 그 값들 중 최댓값과 최솟값을 checking하세요)

[ STEP 3 ]

두번째 polygon에 대해서도 같은 방법으로 check하세요.

[ STEP 4 ]

그 후, 그 value들이 overlap 되는지를 check 하세요.


만약 축에 대해 projection한 다음,
두 Shadow 사이에서 gap을 발견한다면, 두 shape는 분명히 intersect하지 않는 것입니다.

그러나 만약 gap이 존재하지 않는다면, 두 shape는 접촉할 수도 있으며,
당신은 두 polygon의 모든 변을 순회하면서 checking을 이어가야 합니다.
모든 변에 대해 gap을 발견하지 못한다면, 이제 그 두 shape는 충돌하는 것입니다.


기본적으로 이렇습니다.
추가로 하나를 덧붙이자면,
overlap하는 shadow들 중에서 가장 작게 overlap하는 축을 찾는다면,
당신은 그 value를 (충돌한)두 shape를 분리시키는데 이용할 수 있습니다.

What about circles?

SAT로 polygon에 대해 circle을 테스트하는 것은, 조금 낯설지만 이렇게 합니다.

중요한 것은, circle은 어떠한 변도 가지고 있지 않으므로 

당신이 테스트 해야 할 뚜렷한 axis가 없다는 것입니다. 하지만, 테스트 할 필요가 있는 

'not so obvious'한 축은 있습니다.

이 축은, circle의 중심에서 polygon의 가장 가까운 꼭짓점까지를 잇는 축입니다.

그 다음부터는, polygon의 모든 (변에대한)축을 순회하면서, overlap을 체크하면 됩니다.

참고로, circle을 axis에 project하는 방법은, 중심을 projection 한다음 반지름 길이를 더하고 빼면 됩니다.

Pro’s and Con’s

다른 모든 collision detection 기법처럼, SAT 또한 장,단점이 있습니다. 대표적인 것들은
다음과 같습니다.

Pros

1. 빠르다 - 꽤 간단한 vector 계산이고, (충돌감지만이 목적이라면) gap이 발견되자마자 테스트를 마칠 수 있기 때문에, 불필요한 계산을 없앨 수도 있다.
2. 정확하다 - (필자가 아는 한..)

Cons

1. 볼록다각형(Convex Polygon) 에 대해서만 적용 가능하다.
   -> 그렇지 않은 아주 복잡한 shape일 경우에는, 그것을 다시 더 작은 convex shape로 쪼갠다음 각 shape에 대해 테스트 해야한다.
2. 어떤 변이 touching 하고 있는지는 알려주지 않는다.-> 오직 얼마나 많이 overlap 되어있고, 이를 분리시킬 수 있는 가장 짧은 distance만 알려줄 뿐이다. 

이외에도 더 많은 장/단점이 있지만, 제가 생각하는 주요한 것은 여기까지입니다.






-댓글 지적-

I had a quick look at the implementation you posted. It appears to be checking for a collision only, and not actually figuring out how to separate them. If you were to use the ‘axis’ property directly after that method you would always get the last axis that was tested, which is not necessarily the the shortest path of separation.

To get the right axis, you would have to keep track of which axis had the shortest amount of overlap. This should be as simple as having another vector variable declared and checking it each time an axis is tested. If you get to the end and there is a collision, simply use the vector you have stored for the separation.