«   2017/12   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
Archives
Today
163
Total
239,643
관리 메뉴

CODEONWORT

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

수학

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

codeonwort 2010.12.10 00:07

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


2D 다각형 충돌 검사

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

배경 지식

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

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

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

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

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

Projections of polygons onto an axis

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

Projections of moving polygons onto an axis

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

Polygon Collision

그림 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);
저작자 표시 비영리 동일 조건 변경 허락
신고
10 Comments
댓글쓰기 폼