Separating Axis Theorem (SAT)

http://www.dyn4j.org/2010/01/sat/

SAT (Separating Axis Theorem)
이것은 언젠가 할려고 한 글이지만, 결코 해내지 못했었다. 내가 먼저 이 특별한 충돌 탐지 알고리즘에 대해 웹에서 매우 많은 자료들이 있다고 말하여 시작할 것이다. 내가 그 이용가능한 자료들과 가졌던 문제는, 그것들은 구현의 세부사항 몇몇을 설명할 때 종종 애매 하다는 것이다. (아마도 우리의 이익을 위해서)

나는 그 알고리즘을 설명하려는 계획을 했고, 또한 이것을 스스로 구현할 때의 가졌던 빈칸을 채울 계획이였다.

처음에 여기에 상호작용하는 flash 예제가 있는 훌륭한 튜토리얼이 있다.

1. Introduction
2. Convexity
3. Projection
4. Algorithm (1. No Intersection, 2. Intersection)
5. Obtaining The Separating Axes
6. Projecting A Shape Onto An Axis
7. Finding the MTV
8. Curved Shapes
9. Containment
10. Other Things To Note

Introduction

Separating Axis Theorem, 줄여서 SAT는 두 개의 볼록한 도형들이 교차하는지를 결정하는 방법이다. 그 알고리즘은 또한 물리 시뮬레이션과 많은 다른 프로그램들에 유용한 최소한의 관통하는 벡터를 찾는데 사용할 수 있다. SAT는 각 모양 유형의 pair에 대해 충돌 탐지 코드를 갖을 필요성을 줄일 수 있는 빠르고 generic한 알고리즘이다. 그리고 그것으로 인해 코드와 유지보수를 줄인다.

Convexity

이전에 언급되었듯이, SAT는 두 개의 볼록 도형들이 교차하는지를 결정하는 방법이다. 한 도형은 만약 그 도형을 통과하는 어떤 선에 대해 그 선이 오직 두 번만 지나간다면 볼록하다고 고려된다. 만약 한 직선이 그 도형을 통과해서 그려지고 두 번 이상 통과된다면, 그 도형은 볼록이 아니다 (또는 오목이다). 좀 더 수학적 그리고 공식적인 정의를 위해서는 위키의 정의와 MathWorld의 정의를 보아라. 그래서 몇 가지 예제를 봐보자:

그 첫 번째 도형은 볼록으로 고려된다. 왜냐하면 그 도형을 통과하여 두 번 이상 통과하도록 그려질 수 있는 한 선이 존재 하지 않기 때문이다. 두 번째 도형은 볼록이 아니다. 왜냐하면 두 번 이상 통과하는 한 직선이 존재하기 때문이다.

SAT는 오직 볼록 도형만을 다루지만, 볼록이 아닌 도형은 볼록 도형들의 조합 (convex decomposition(볼록 분해)이라고 불려지는) 으로 나타내어지기 때문에 괜찮다. 그래서 만약 그림 2에서 오목한 모형을 취하고 convex decomposition을 수행한다면, 우리는 두 개의 convex 도형을 얻을 수 있다. 우리는 그러고나서 각 convex shape를 전체 도형에 대해 충돌을 결정하기 위해 테스트할 수 있다.

Projection

SAT가 사용하는 다음의 개념은 projection(사영, 투영)이다. 너가 광선이 모두 평행한 광원을 가지고 있다고 상상해라. 만약 너가 그 빛을 한 오브젝트에 비춘다면, 그것은 표면에 그림자를 만들 것이다. 한 그림자는 한 삼차원 오브젝트의 2차원 사영이다. 2차원 오브젝트의 사용은 1차원 "그림자"이다.

Algorithm

SAT는 다음과 같이 말한다 : "만약 두 개의 볼록 오브젝트들이 관통하지 않는다면, 그 오브젝트들의 사영이 중첩되지 않는 축이 존재한다."

No Intersection

처음에 SAT가 두 도형이 교차하지 않는지를 어떻게 결정하는지 이야기 해보자. 그림 5에서, 우리는 두 도형이 교차하지 않고 있는지를 안다. 이것을 보여주기 위해 한 직선이 그려진다.

만약 그림 5에서 두 도형을 분리하는 선에 수직인 선을 선택하고, 그 도형들을 그 선에 사영시킨다면, 우리는 그것들의 사영에서 중첩이 없는 것을 볼 수 있다. 그 도형들의 사영(그림자)가 중첩되지 않는 선은 separation axis(분리축) 이라고 불려진다. 그림 6에서 그 어두운 회색 선은 separation axis이고, 그 각각의 색이 있는 선들은 그 도형들의 분리축에 대한 사영이다. 그림 6에서 사영물들이 중첩하지 않는다는 것을 주목해라. 그러므로 SAT에 따라서, 그 도형들은 교차하고 있지 않다.

그러나, SAT는 중첩에 대해 많은 축을 검사할지도 모른다. 그 사영물들이 중첩되지 않은 첫 번째 축에서, 그 알고리즘은 즉시 그 도형이 교차하고 있지 않다고 결정내리는 것을 끝낼 수 있다. 이 빠른 종료 때문에, SAT는 많은 오브젝트를 가지지만 적은 충돌을 가져야하는 프로그램들에 이상적이다 (games, simulations, etc.)

더 설명하기 위해서, 다음의 슈도코드를 봐보자.

Axis[] axes = // get the axes to test;
// loop over the axes
for (int i = 0; i < axes.length; ++i)
{
   Axis axis = axes[i];
   // project both shapes onto the axis
   Projection p1 = shape1.projection(axis);
   Projection p2 = shape2.project(axis);
   // do the projections overlap?
   if(!p1.overlap(p2))
   {
     // then we can guarantee that the shapes do not overlap
     return false;
   }
}

Intersection
만약 모든 축에 대해 그 도형의 사영물들이 중첩한다면, 그러면 우리는 그 도형들이 교차하고 있다고 결론 지을 수 있다. 그림 7은 두 convex shapes가 많은 축에 대해 테스트되고 있는 것을 보여준다. 그러므로 우리는 그 도형들이 교차하고 있다는 것을 결론지을 수 있다.

모든 축들은 교차를 검증하기 위해 중첩에 대해 검증되어야만 한다. 위의 그 수정된 코드는 다음과 같다:

Axis[] axes = // get the axes to test;
// loop over the axes
for (int i = 0; i < axes.length; ++i)
{
   Axis axis = axes[i];
   // project both shapes onto the axis
   Projection p1 = shape1.projection(axis);
   Projection p2 = shape2.project(axis);
   // do the projections overlap?
   if(!p1.overlap(p2))
   {
     // then we can guarantee that the shapes do not overlap
     return false;
   }
}

return true;

Obtaining The Separating Axes
이 알고리즘을 구현할 때 내가 가졌던 첫 번째 질문은 어떻게 내가 테스트할 축들이 무엇인지 아는 방법이였다. 이것은 실제로 꽤 간단하다고 판명되었다:

너가 테스트해야 하는 축들은 각 도형들이 edges의 normals이다.

그 변들의 법선들은 좌표를 바꾸고 음수화하여 얻어질 수 있다. 예를들어:

Vector[] axes = new Vector[shape.vertices.length];

// loop over the vertices
for(int i = 0; i < shape.vertices.length; ++i)
{
   // get the current vertex
   Vector p1 = shape.vertices[i];
   // get the next vertex
   Vertor p2 = shape.vertices[i + 1 == shape.vertices.length ? 0 : i + 1];
   // subtract the two to get the edge vector
   Vector edge = p1.subtract(p2);
   // get either perpendicular vector
   Vector normal = edge.perp();
   // the perp method is just (x, y) => (-y, x) or (y, -x)
   axes[i] = normal;
}

위의 방법에서, 우리는 그 도형의 각 변에 대해 수직인 벡터를 반환한다.

이러한 벡터들은 "normal" vectors라고 불려진다. 그러나 이러한 벡터들은 표준화되어지지 않았다 (단위 길이가 아니다). 만약 너가 SAT 알고리즘으로부터 boolean result만을 필요하다면, 이것은 충분할 것이지만, 그러나 만약 너가 충돌 정보가 필요하다면 (MTV section에서 나중에 이야기 될), 그러면 이러한 벡터들은 표준화 될 필요가 있다 

(Projection A Shape Onto An Axis section을 보아라).

테스트할 축들의 두 개의 리스트를 얻기 위해 각 도형에 대해 이것을 수행해라. 이것을 하는 것은 슈도코드를 위에서 다음으로 바꾼다:

Axis[] axes1 = shape1.getAxes();
Axis[] axes2 = shape2.getAxes();

//loop over the axes1
for(int i = 0; i < axes1.length; i++)
{
   Axis axis = axes1[i];
   // project both shapes onto the axis
   Projection p1 = shape1.projection(axis);
   Projection p2 = shape2.project(axis);
   // do the projections overlap?
   if(!p1.overlap(p2))
   {
      // then we can guarantee that the shapes do not overlap
      return false;
   }
}
//loop over the axes2
for(int i = 0; i < axes2.length; i++)
{
   Axis axis = axes2[i];
   // project both shapes onto the axis
   Projection p1 = shape1.projection(axis);
   Projection p2 = shape2.project(axis);
   // do the projections overlap?
   if(!p1.overlap(p2))
   {
      // then we can guarantee that the shapes do not overlap
      return false;
   }
}
// if we get here then we know that every axis had overlap on it
// so we can guarantee on intersection
return true;

Projecting A Shape Onto An Axis
명확하지 않은 또 다른 것은 한 도형을 한 축에 어떻게 사영시키는지였다. 한 도형을 한 축에 사영시키는것은 상대적으로 간단하다; 모든 정점에 대해 축과의 내적을 수행하고 그 최소와 최대값을 저장하는 것을 반복해라.

double min = axis.dot(shape.vertices[0]);
double max = min;
for(int i = 1; i < shape.vertices.length; ++i)
{
   // Note : the axis must be normalized to get accurate projections
   double p = axis.dot(shape.vertices[i]);
   if(p < min)
      min = p;
   else if (p > max)
      max = p;
}
Projection proj = new Projection(min, max);
return proj;

Finding the MTV
지금까지, 우리는 두 도형이 교차하면 true or false만을 반환해왔다. 이것 외에도, SAT는 Minimum Translation Vector(MTV)를 반환할 수 있다. 그 MTV는 충돌에서 도형들을 밀어내기 위해 사용되는 최소한의 크기 벡터이다 (minimum magnitude vector). 만약 우리가 그림 7을 다시 참고한다면, 우리는 축 C가 가장 작은 중첩을 갖는 것을 볼 수가 있다. 그 축과 그 중첩이 MTV이고, 그 축은 벡터 부분이 되고, 중첩은 크기 부분이 된다.

그 도형이 교차하는지를 결정하기 위해서, 우리는 두 도형으로부터 모든 축에 대해 반복해야만 한다. 그래서 동시에, 우리는 최소한의 중첩과 축을 추적할 수 있다. 만약 우리가 이것을 포함하기 위해 우리의 슈도코드를 위에서 바꾼다면, 우리는 그 도형이 교차할 때 MTV를 반환할 수 있다.

double overlap = // really large value;
Axis smallest = null;
Axis[] axes1 = shape1.getAxes();
Axis[] axes2 = shape2.getAxes();

//loop over the axes1
for(int i = 0; i < axes1.length; i++)
{
   Axis axis = axes1[i];
   // project both shapes onto the axis
   Projection p1 = shape1.projection(axis);
   Projection p2 = shape2.project(axis);
   // do the projections overlap?
   if(!p1.overlap(p2))
   {
      // then we can guarantee that the shapes do not overlap
      return false;
   }
   else
   {
     // get the overlap
     double o = p1.getOverlap(p2);
     // check for minimum
     if(o < overlap)
     {
        overlap = o;
        smallest = axis;
     }
   }
}
//loop over the axes2
for(int i = 0; i < axes2.length; i++)
{
   Axis axis = axes2[i];
   // project both shapes onto the axis
   Projection p1 = shape1.projection(axis);
   Projection p2 = shape2.project(axis);
   // do the projections overlap?
   if(!p1.overlap(p2))
   {
      // then we can guarantee that the shapes do not overlap
      return false;
   }
   else
   {
     // get the overlap
     double o = p1.getOverlap(p2);
     // check for minimum
     if(o < overlap)
     {
        overlap = o;
        smallest = axis;
     }
   }
}
MTV mtv = new MTV(smallest, overlap);

// if we get here then we know that every axis had overlap on it
// so we can guarantee on intersection
return mtv;

Curved SHapes
우리는 SAT를 사용해서 어떻게 도형들이 테스트되어질 수 있는지를 보았지만, 원과 같은 곡선의 도형은 어떤가? 곡현의 도형들은 SAT에 대해 문제를 제기한다. 왜냐하면 곡선의 도형들은 무한의 개의 검증할 분리축들이 있기 때문이다. 이 문제가 보통 해결되는 방식은    원 vs 원 그리고 원 vs 도형 검증으로 분리하고 좀 더 특정한 작업을 하는 것이다. 또 다른 대안은 전혀 곡선의 도형들을 사용하지 않고, 그것들을 많은 정점의 개수가있는 도형으로 대체하는 것이다. 두 번쨰 대안은 위의 슈도코드에서 변화를 만들지 않지만, 그러나 그 첫 번째 선택을 다루고 싶다.

처음에, Circle vs Circle을 봐보자. 일반적으로 너는 다음과 같은 것을 할 것이다:

Vector c1 = circle1.getCenter();
Vecter c2 = circle2.getCenter();
Vector v = c1.subtract(c2);
if(v.getMagnitude() < circle1.getRadius() + circle2.getRadius())
{
  // then there is an intersection
}
// else there isn't

우리는 두 원들이 그 원들의 반지름의 합보다 중심들이 더 가까이 있다면 충돌하고 있는 것을 안다. 이 검증은 실제로 SAT같은 검증이다. 이것을 SAT에서 하기 위해서 우리는 다음의 것을 할 수 있다:

Vector[] axes = new Vector[1];
if(shape1.isCircle() && shape2.isCircle())
{
  // for two circles there is only one axis test
  axes[0] = shape1.getCenter().subtract(shape2.getCenter());
}
// then all the SAT code from above

Circle vs Polygon은 좀 더 문제를 제기한다. 도형의 축을 따라서 중심간의 테스트는 충분하지 않다 (사실 중심간 테스트는 빠드려질 수 있다). 이 경우에, 너는 또 다른 축을 포함해야만 한다: 도형의 가장 가까운 정점에서 원점까지의 축. 그 도형에서 그 가장가까운 정점은 많은 방식으로 찾아질 수 있다. 그 받아들여진 솔루션은 Voronoi regions를 사용하는 것이다. 이것은 이 포스트에서 다루지 않을 것이다.

다른 곡선 도형들은 심지어 더 문제이고, 그것들 각각의 방식으로 처리되어야 한다. 예를들어, 캡슐 모양은 사각형과 두 개의 원들로 분해되어질 수 있다.

Containment
많은 개발자들이 무시하는 것을 선택하는 문제들 중 하나는 포함이다. 한 도형이 다른 모형을 포함할 때 무엇이 발생하는가? 이 문제는 큰 문제가 아니다. 대부분의 프로그램들이 결코 이 상황이 일어나게 하지 않을 것이기 때문이다. 처음에 내가 그 문제를 설명하고 그것이 어떻게 다뤄지는지 설명할 것이다. 그러고나서 나는 왜 그것이 고려되어야 하는지를 설명할 것이다.

만약 한 도형이 또 다른 도형에 포함된다면, 우리가 지금까지 가진 슈도코드에 의하면, SAT는 부정확한 MTV를 반환할 것이다. 두 벡터와 크기 부분은 정확하지 않을 것이다. 그림 9는반환된 중첩이 교차 밖으로 도형을 움직이게 충분하지 않는 것을 보여준다. 그래서 우리가 할 필요가 있는 것은 중첩 테스트에서 포함을 점검하는 것이다. 위의 SAT 코드로부터 if 문을 취하여:

if(!p1.overlap(p2))
{
   // then we can guarantee that the shapes do not overlap
   return false;
}
else
{
   // get the overlap
   double o = p1.getOverlap(p2);
   // check for containment
   if(p1.contains(p2) || p2.contains(p1))
   {
      // get the overlap plus the distance from the minimum end points
      double mins = abs(p1.min - p2.min);
      double maxs = abs(p1.max - p2.max);
      // NOTE : depending on which is smaller you may need to
      // negate the separating axis!!
      if(mins < maxs)
         o += mins;
      else
         o += maxs;
   }
    
   // check for minimum
   if(o < overlap)
   {
      overlap = o;
      smallest = axis;
   }
}

Reason #1 : 도형들이 이 설정의 유형에 들어맞을 수 있다. 이것을 다루지 않는 것은 상대적인 도형의 크기에 따라 충돌을 해결하기 위해 SAT의 두 번 이상의 반복을 요구할 것이다.

Reason #2 : 만약 너가 다른 도형들에 대해 Line Segment를 지원하려 한다면, 너는 이것을 해야만 한다. 왜냐하면 그 중첩이 어떤 경우에 0일 수 있기 때문이다 (이것은 Line Segment가 무한히 얇은 도형이라는 사실 때문이다).

Other Things To Note
몇 가지 주목해야할 몇가지 것이 있다:

• 테스트할 축들의 개수는 평행 축들을 검사하지 않아서 줄여질 수 있다. 이것은 한 사각형이 오직 두 개의 검증할 축 테스트를 가진 이유이다.
• 사각형과 같은 몇 가지 도형들은 그것이 그것자신의 projection and getAxes 코드가 있다면 더 빠르게 작동할 수 있다. 한 사각형은 4개의 축이 아닌 2개만 검사하면 되기 때문이다.
• 마지막 분리 축은 그 알고리즘이 비교차의 경우에 O(1)이 될 수 있도록 SAT의 다음 반복을 준비시키기 위해 사용하는 것이다.
• 3D에서 SAT는 많은 축들을 검사하게 된다.
• 나는 적문가가 아니고, 나의 끔찍한 그래픽스를 봐줘라.