[번역] 2D 다각형 충돌 검사

원문: http://pogopixels.com/blog/2d-polygon-collision-detection/

2D 다각형 충돌 검사

이 글에서는 움직이는 두 다각형간 충돌을 검사하는 방법을 설명한다. 이 글이 이 화제에 대한 최초의 튜토리얼은 아니지만, 인터넷에 퍼진 튜토리얼들은 쉬운 문제를 복잡하게 해결한다. 소스 코드마다 너무 축약해놔서 알아먹을 수가 없고 C 최적화 때문에 이리저리 꼬였다. 그래서 나는 코드를 단순하게 놔뒀다. 나무늘보 움직이는 속도가 느껴지는 픽셀 비교 충돌 검사를 쓸 바에야 이 기법을 써라.

• Download the .NET / C# source code
• Download the .NET demo

배경 지식

두 다각형이 교차하는지 축 분리 정리(separating axis theorem, SAT)를 써서 검사할 것이다. 두 다각형을 구분하는 선을 찾자는 발상이다. 그런 선이 있으면 두 다각형은 교차하지 않는다(그림 1). 이 정리를 구현하는 것은 간단하고 이렇게 요약할 수 있다.

• 두 다각형의 각 변에 대해
  • 현재 변에 수직인 축을 찾는다
  • 두 다각형을 이 축에 정사영한다
  • 두 정사영이 겹치지 않으면 두 다각형은 교차하지 않는다.

한 단계만 추가하면 다각형들이 움직일 때도 잘 먹힌다. 현재 정사영이 겹치지 않음을 확인한 다음 다각형들의 상대 속도를 그 축에 정사영한다. 현재 A의 정사영에 속도 정사영을 더해 늘린다(그림2). 이제 A와 B의 정사영이 겹치지 않으면 두 다각형은 충돌하지 않을 것이다. (주의: 하지만 겹친다고 반드시 충돌할 것이라는 뜻은 아니다. 모든 변에 대해 검사해야 단정할 수 있다)

두 다각형이 충돌하려는 참이면 두 다각형 사이를 벌려놓아야 한다. 정사영 겹침이 최소인 축에서 충돌이 일어날 것이다. 이 축을 따라 A를 밀어낼 것이다. 옮기는 양은 그저 이 축에서 겹치는 양과 같다.

이거다! 충돌이 일어날 때마다 A가 B의 표면을 스르륵 미끄러질 것이다.

그림 1: 축에 대한 두 다각형의 정사영

그림 2: 움직이는 두 다각형의 정사영

그림 3: 최소 겹침을 찾아 밀어낼 양을 계산한다.

코드 사용

PolygonCollision() 함수는 위에 나열한 모든 작업을 한 다음에 충돌을 다루는 데 필요한 모든 정보가 있는 PolygonCollisionResult 구조체를 반환한다.

// PolygonCollision 함수의 결과를 저장하는 구조체
public struct PolygonCollisionResult {
    // 다각형들이 교차하려고 하는가?
    public bool WillIntersect;

    // 지금 교차했는가?
    public bool Intersect;

    // 표면으로 밀어내기 위한 첫 번째 다각형의 이동량
    public Vector MinimumTranslationVector;
}

PolygonCollision 함수는 두 도우미 함수를 쓴다. 하나는 다각형을 축에 정사영하기 위해 쓴다.

// 축에 대한 다각형의 정사영을 계산하고 [min, max] 간격을 반환한다.
public void ProjectPolygon(Vector axis, Polygon polygon,
                           ref float min, ref float max) {
    // 점을 축에 정사영하기 위해 내적을 쓴다
    float dotProduct = axis.DotProduct(polygon.Points[0]);
    min = dotProduct;
    max = dotProduct;
    for (int i = 0; i < polygon.Points.Count; i++) {
        dotProduct = polygon.Points[i].DotProduct(axis);
        if (d < min) {
            min = dotProduct;
        } else {
            if (dotProduct> max) {
                max = dotProduct;
            }
        }
    }
}

다른 건 두 정사영 사이의 부호 있는 거리를 반환한다.

// [minA, maxA]와 [minB, maxB] 사이의 거리를 계산한다
// 구간이 겹치면 거리는 음수다
public float IntervalDistance(float minA, float maxA, float minB, float maxB) {
    if (minA < minB) {
        return minB - maxA;
    } else {
        return minA - maxB;
    }
}

이게 주인공 함수

// A가 B랑 충돌하려는지 검사한다.
// 마지막 매개변수는 po상대wer 속도다 (속도A - 속도B)


public PolygonCollisionResult PolygonCollision(Polygon polygonA,
                              Polygon polygonB, Vector velocity) {
    PolygonCollisionResult result = new PolygonCollisionResult();
    result.Intersect = true;
    result.WillIntersect = true;

    int edgeCountA = polygonA.Edges.Count;
    int edgeCountB = polygonB.Edges.Count;
    float minIntervalDistance = float.PositiveInfinity;
    Vector translationAxis = new Vector();
    Vector edge;

    // 두 다각형의 모든 변에 대해 루프
    for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
        if (edgeIndex < edgeCountA) {
            edge = polygonA.Edges[edgeIndex];
        } else {
            edge = polygonB.Edges[edgeIndex - edgeCountA];
        }

        // ===== 1. 지금 교차하는지 본다 =====
        // 지금 변에 수직인 축을 찾는다
         Vector axis = new Vector(-edge.Y, edge.X);
        axis.Normalize();

        // 지금 축에 다각형을 정사영한다
        float minA = 0; float minB = 0; float maxA = 0; float maxB = 0;
        ProjectPolygon(axis, polygonA, ref minA, ref maxA);
        ProjectPolygon(axis, polygonB, ref minB, ref maxB);

        // 지금 교차하는지 검사한다
        if (IntervalDistance(minA, maxA, minB, maxB) > 0)
            result.Intersect = false;

        // ===== 2. 충돌*하려는지* 본다 =====
        // 지금 축에 속도를 정사영한다
        float velocityProjection = axis.DotProduct(velocity);

        // 이동 중 다각형 A의 정사영을 얻는다
        if (velocityProjection < 0) {
            minA += velocityProjection;
        } else {
            maxA += velocityProjection;
        }

        // 새로운 정사영을 가지고 아까 한 거랑 같은 걸 한다
        float intervalDistance = IntervalDistance(minA, maxA, minB, maxB);
        if (intervalDistance > 0) result.WillIntersect = false;

        // 교차하지 않고 교차하지 않을 것이면 루프를 종료한다
        if (!result.Intersect && !result.WillIntersect) break;

        // 지금 간격이 최소 간격인지 확인한다. 최소 옮김 벡터를 구하는 데 쓴다


        intervalDistance = Math.Abs(intervalDistance);
        if (intervalDistance < minIntervalDistance) {
            minIntervalDistance = intervalDistance;
            translationAxis = axis;

            Vector d = polygonA.Center - polygonB.Center;
            if (d.DotProduct(translationAxis) < 0)
                translationAxis = -translationAxis;
        }
    }

    // 최소 옮김 벡터로 멀어지는 그들
    if (result.WillIntersect)
        result.MinimumTranslationVector =
               translationAxis * minIntervalDistance;

    return result;
}

이런 식으로 쓴다

Vector polygonATranslation = new Vector();

PolygonCollisionResult r = PolygonCollision(polygonA, polygonB, velocity);

if (r.WillIntersect) {
  // 다각형을 속도만큼 이동시키고 최소 옮김 벡터로 떨어뜨린다
  polygonATranslation = velocity + r.MinimumTranslationVector;
} else {
  // 그냥 속도만큼 이동시킨다
  polygonATranslation = velocity;
}

polygonA.Offset(polygonATranslation);