사각형 충돌 판정에서 원 충돌까지 (AABB의 원리와 일반화)

 

AABB와 원 충돌 판정 대표 이미지

Java 실습 문제 중에 이런 게 있었다. 2차원 평면에서 두 점 (x1, y1), (x2, y2)로 만들어지는 직사각형이 (100, 100), (200, 200)으로 이루어진 직사각형과 충돌하는지 판별하라는 문제. 답은 맞췄는데, 풀고 나서 같은 로직을 원 대 원으로 일반화해보고 싶어졌다. 두 케이스의 공통 원리를 알면 원-사각형처럼 다른 조합도 다 풀린다는 걸 이번에 이해했다. 게임 개발에서 진짜 자주 쓰는 개념인데 처음 직관이 안 잡히면 의외로 헤매기 쉬운 부분이다.

AABB 사각형 충돌

AABB, Axis-Aligned Bounding Box는 축에 평행한 사각형을 말한다. 회전 없이 가로세로 축에 딱 맞춰진 사각형이라는 뜻이고, 게임에서 제일 흔한 충돌 모양으로 쓰이는 이유는 단순히 계산이 압도적으로 빠르기 때문이다.

두 사각형 A와 B가 충돌하는 조건을 바로 생각하려 하면 헷갈리는데, 반대로 "안 겹치는 경우"부터 생각하면 정리가 쉽다. 두 사각형이 안 겹치려면 A가 완전히 B의 왼쪽에 있거나, 완전히 오른쪽에 있거나, 완전히 위에 있거나, 완전히 아래에 있어야 한다. 이 네 가지 중 하나라도 참이면 안 겹치고, 반대로 넷 다 거짓이어야 겹친다.

수식으로 옮기면 사각형 A가 (Ax1, Ay1)-(Ax2, Ay2)이고 B가 (Bx1, By1)-(Bx2, By2)일 때:

충돌 = (Ax1 < Bx2) && (Ax2 > Bx1) && (Ay1 < By2) && (Ay2 > By1)

네 조건이 모두 참이면 겹친 거다. Java로 옮기면:

public static boolean rectIntersect(
    double ax1, double ay1, double ax2, double ay2,
    double bx1, double by1, double bx2, double by2)
{
    return ax1 < bx2 && ax2 > bx1
        && ay1 < by2 && ay2 > by1;
}

문제에서 B가 (100,100)-(200,200)으로 고정이면 이렇게 단순화된다.

public static boolean collidesWithFixed(double x1, double y1, double x2, double y2) {
    return x1 < 200 && x2 > 100
        && y1 < 200 && y2 > 100;
}

여기서 하나 빠뜨려서 막혔던 부분이 있다. 사용자가 입력하는 두 점이 항상 좌상단-우하단 순서라는 보장이 없다는 거다. 1 2 300 200을 입력하면 (1,2)-(300,200)으로 순서가 맞지만, 300 200 1 2처럼 뒤집어서 입력하면 x1 = 300, x2 = 1이 되어 x1 < x2 자체가 거짓이 되면서 위 조건식이 무너진다. 해결은 입력받자마자 작은 값과 큰 값을 정렬해두는 거다.

double xMin = Math.min(x1, x2);
double xMax = Math.max(x1, x2);
double yMin = Math.min(y1, y2);
double yMax = Math.max(y1, y2);

이렇게 정리한 xMin/xMax/yMin/yMax를 충돌 판정식에 넣으면 입력 순서와 무관하게 잘 동작한다. 이거 안 해놓고 "1 2 300 200 입력했는데 왜 충돌 안 되냐"고 한참 헤맸다.

원 대 원은 훨씬 간단하다

두 원이 겹치는지는 사각형보다 코드가 짧다. 두 원 중심 사이 거리가 반지름의 합보다 작거나 같으면 겹친다.

distance = √((x2 - x1)² + (y2 - y1)²)
중심 거리 ≤ r1 + r2  →  충돌

여기에 작은 최적화가 하나 들어가는데, 제곱근 연산이 비싸기 때문에 둘 다 제곱한 채로 비교한다.

(x2 - x1)² + (y2 - y1)²  vs  (r1 + r2)²

좌변이 우변보다 작으면 충돌이고, 이러면 제곱근을 한 번도 호출하지 않아도 된다.

public static boolean circleIntersect(
    double x1, double y1, double r1,
    double x2, double y2, double r2)
{
    double dx = x2 - x1;
    double dy = y2 - y1;
    double distSq = dx * dx + dy * dy;
    double rSum = r1 + r2;
    return distSq <= rSum * rSum;
}

음수 좌표가 들어와도 문제없는데, (x2 - x1)이 음수여도 제곱하면 양수가 되기 때문이다. 거리 자체가 원래 부호에 영향을 안 받는 양수 값이라 그렇다.

두 케이스를 관통하는 원리

사각형 충돌과 원 충돌을 따로 보면 완전히 다른 알고리즘처럼 보이는데 본질은 같다. 두 도형이 "분리 가능한가"를 보는 거다. 분리할 수 있으면 충돌이 아니고, 못 하면 충돌이다. 사각형끼리는 X축이나 Y축으로 분리할 수 있는지 보고, 원끼리는 두 중심을 잇는 직선 위에서 분리할 수 있는지, 즉 중심 거리가 반지름 합보다 큰지를 본다.

이 일반화된 원리가 분리축 정리(Separating Axis Theorem, SAT)다. 회전한 사각형이나 임의의 다각형 충돌도 같은 원리로 풀 수 있는데, 적당한 축을 골라서 두 도형을 그 위에 투영하고 투영된 구간이 겹치는지 확인하면 된다. 게임 엔진의 충돌 시스템 대부분이 이 위에 만들어져 있다.

자잘하게 걸렸던 것들

경계가 정확히 맞닿은 상태를 충돌로 볼지 말지는 문제마다 다르다. 수업 문제는 지문을 잘 읽고 <와 <=를 구분해야 했는데, 보통 게임에서는 정확히 닿은 건 충돌 안 한 걸로 처리하는 경우가 많다.

좌표를 정수로 받으면 거리 계산에서 오버플로 위험이 있다. 값이 충분히 크면 int * int가 int 범위를 넘을 수 있어서, long으로 캐스팅하거나 처음부터 double을 쓰는 게 안전하다.

long dx = (long)x2 - x1;  // 안전

사각형 표현 방식도 두 가지가 있다. (x1, y1)-(x2, y2)처럼 두 코너 점으로 표현하는 방식과, (x, y, w, h)처럼 좌상단 점과 가로세로 크기로 표현하는 방식. 서로 변환은 가능한데 충돌 코드 모양이 조금 다르다. java.awt.Rectangle이나 MonoGame, Pygame 같은 라이브러리는 대체로 후자를 쓴다.

return ax < bx + bw && ax + aw > bx
    && ay < by + bh && ay + ah > by;

논리는 똑같고 좌표 계산만 살짝 다르다.

원과 사각형의 충돌은 이 둘의 중간쯤 되는 난이도다. 핵심 트릭은 사각형 위에서 원 중심에 가장 가까운 점을 찾고, 그 점과 원 중심 사이 거리가 반지름보다 작은지 보는 거다.

double closestX = Math.max(rectX, Math.min(circleX, rectX + rectW));
double closestY = Math.max(rectY, Math.min(circleY, rectY + rectH));
double dx = circleX - closestX;
double dy = circleY - closestY;
return (dx * dx + dy * dy) < radius * radius;

Math.min/Math.max 조합이 클램프 연산이다. 원 중심을 사각형 경계 안쪽으로 당겨놓고, 그 결과 점이 원 안에 있는지 보는 방식인데 처음 보면 잘 안 와닿다가 그림으로 그려보면 바로 이해된다.

참고한 자료는 LearnOpenGL의 Collision detection 문서(AABB와 원-사각형 클램프 트릭), MDN Web Docs의 2D collision detection, MonoGame 문서 12장(제곱 거리 비교 트릭), 위키피디아의 Separating Axis Theorem 항목이다.

충돌 판정은 모양보다 거리의 조건이다

AABB는 각 축의 구간이 모두 겹치는지 보고, 원은 중심 거리의 제곱이 반지름 합의 제곱보다 작은지 본다. 사각형과 원은 원의 중심을 사각형 내부의 가장 가까운 점으로 clamp한 뒤 그 점과 중심 거리를 계산하면 된다. 세 식을 같은 “분리되는 조건이 있는가” 관점으로 보면 일반화가 쉬웠다.

MDN 2D collision detection 문서

MDN 3D collision detection의 bounding volume 설명

Wolfram MathWorld Circle 문서

LearnOpenGL 2D collision detection 예제

closestX = clamp(circleX, rectLeft, rectRight)
closestY = clamp(circleY, rectTop, rectBottom)
dx = circleX - closestX
dy = circleY - closestY
collides = dx*dx + dy*dy <= radius*radius

제곱근을 생략하고 제곱 거리끼리 비교하면 결과는 같고 계산은 단순해진다. 접촉을 충돌로 볼지 여부에 따라 <와 <=를 의도적으로 고른다.

참고 자료

• MDN 2D collision detection
• MathWorld Circle
• LearnOpenGL Collision detection