[TIL][C++] 250627 MMO 서버 개발 45일차: 회전하는 사각형(OBB)사이의 충돌 처리

주의사항: 해당 글은 일기와 같은 기록용으로, 다듬지 않은 날것 그대로인 글입니다. 

AABB의 한계

• 이전 글에서 AABB의 충돌 판정을 하는 법에 대해 알아보았다. AABB의 충돌 판정을 처리하는 알고리즘은 굉장히 빠르며, 게임에서 활용하기 좋다는 장점이 있었다.
• 문제는 AABB만으로 모든 게임 장르에 등장하는 충돌 판정을 처리할 수 없다는 것이다. 어디까지나 충돌체의 회전 개념이 없을 때에 한정되어 사용할 수 있는 것이지, 로스트아크, 탕탕 특공대와 같이 탑다운 방식의 게임에선 투사체의 발사 방향과 상관없이 충돌체 도형을 AABB로 고정시킬 순 없다. 결국, AABB 만으로는 탑다운 방식의 게임에선 회전된 사각형 충돌체에 대해 처리해야 한다.

 

OBB(Oriented Bounding Box)의 충돌 처리 방식

• 회전하지 않는 사각형 충돌체를 AABB라고 했다면, 회전하는 사각형 충돌체는 OBB라고 부른다. OBB의 경우, 사각형의 내부 좌표축이 월드 좌표축과 대부분 일치하지 않기 때문에, AABB의 충돌 판정에 활용한 알고리즘을 그대로 사용할 수 없다. 즉, OBB에 맞는 알고리즘을 사용해야 한다는 의미이다.

OBB의 충돌 처리를 위한 알고리즘, SAT(Separate Axis Theorem)

• SAT는 분리축 이론이라는 의미로, 쉽게 말해서 ‘하나의 축으로 두 도형이 존재하는 영역을 분리할 수 있다면, 두 도형은 만나지 않는다’는 이론이다.
• 그렇다면 SAT는 어떻게 분리축을 구할까? 그림을 보여주고 두 도형을 하나의 축으로 분리하라고 하면 하겠지만, 이를 컴퓨터 연산만을 통해 판정해야 하는 것은 또 다른 이야기이다. SAT에선 분리축을 찾기 위한 방법으로 “각 도형의 법선 벡터(normal vector)”들을 활용한다.

SAT 설명에 들어가기 앞서…

• SAT는 기본적으로 OBB뿐만 아니라, 볼록 다각형에 해당하는 다각형에 적용할 수 있는 알고리즘이다. 여기서 “볼록 다각형”이라는 말이 생소한데, **볼록 다각형(convex polygon)**이란 아래의 조건을 만족하는 다각형을 의미한다.
  • 다각형의 모든 내각이 180도 보다 작다.
  • 다각형의 꼭짓점을 이은 선분들은 항상 다각형 내부에 있다.
• 볼록 다각형의 반대 개념인 **“오목 다각형(Concave Polygon)”**도 있으며, 오목 다각형은 SAT 알고리즘에서 적용 대상이 아니다. 오목 다각형의 경우 아래의 조건을 만족하는 다각형을 의미한다.
  • 다각형의 내각들 중 적어도 하나의 내각은 180도 보다 크다.
  • 다각형의 꼭짓점을 이은 선분들 중 적어도 한 선분은 다각형 외부에 있다.
• (그림을 보면 알겠지만 오목 다각형을 외부에서 쥐어박아서 오목해진 다각형의 모습을 하고 있다. 아무튼, SAT는 OBB 뿐만 아니라 모든 볼록 다각형에 적용할 수 있다.)

변의 법선 벡터가 활용되는 방법: 투영

• SAT의 이론은 요약하면 아래와 같이 보인다.
  1. “임의의 축에 두 도형을 투영시켰을 때 나온 두 선분이 겹치지 않았다면, 두 도형을 충돌하지 않으며, 임의의 축에 수직 하는 축은 분리축이 된다.”
  2. “분리축이 존재한다면, 도형의 변과 수직 되는 축들 중 적어도 하나는 존재한다.”
• 어디까지나 자의적인 해석이라 틀릴 수도 있다. 하지만 어찌 되었건 결론은 “변들의 수직 벡터에 투영시켰을 때 한 번이라도 안 겹치면 충돌 안 한 거고, 다 겹치면 충돌한 거다”라는 것이다.

 

투영된 결과물은 어떻게 활용해야 하는가?

1. 일단 최대/최소점을 찾는다: 내적을 이용하면 각 도형의 점을 투영축에 투영한 점의 위치를 구할 수 있을 것이다. 이 점들은 투영축에 착착 붙어있는 모양새가 되는데, 투영축은 직선이므로, x좌표 기준으로 최소/최대인 점을 찾는다.
2. 최대/최소점을 이용해 투영된 길이를 구한다: 최대/최소점을 찾았다면, 투영된 도형의 전체 길이를 구할 수 있을 것이다. 각 도형의 투영된 길이를 찾았다면, 그중 절반인 rA, rB를 구해놓는다.
3. 두 다각형의 중점을 연결한 선분의 투영된 길이를 구한다: 위 그림처럼, 선분 T의 투영된 선분의 길이를 내적(T, L)을 구한다.
4. 길이 비교: rA + rB < 내적(T, L)이면 충돌 X, rA + rB ≥ 내적(T, L)이면 충돌 O가 된다

 

좀 더 간단한 버전

• 사실 중점을 연결한 선분을 구할 필요는 없다. AABB때처럼 최대/최소 점만 있으면 두 선분이 겹치는지 확인할 수 있기 때문. 따라서, 위 4단계 중 3~4번 단계 대신 아래 코드처럼 써도 된다.

// 내부 코드를 그대로 써도 될거다(아마)
bool AABB_to_AABB(AABB a, AABB b)
{
    if (a.max.x < b.min.x || a.min.x > b.max.x) return false;
    if (a.max.y < b.min.y || a.min.y > b.max.y) return false;
    return true;
}

 

 

SAT 한 번당 몇 개의 투영축? 몇 번의 내적?

• SAT를 사용하면 AABB에 비해 많은 연산이 요구된다. 두 다각형의 각의 개수가 N, M개라면, 변의 개수도 N, M개이므로, SAT를 사용하면 (N+M) 번의 투영축을 생성하고, 각 투영축 생성마다 모든 변을 투영하므로(간단한 버전 기준), 투영축마다 (N+M) 번의 내적을 하게 된다. 즉, SAT 한 번당 대략 (N+M)^2번의 내적을 한다는 것이다.
• 이를 사각형에 똑같이 적용하게 되면, N = 4, M = 4이므로,
  • 법선 벡터 생성: 8개
  • 내적 연산: 8축 × 8번 = 64번
  • 총 연산: 법선 8개 + 내적 64번 = 72번 연산하게 된다.
• 같은 사각형이지만 10번 연산을 넘어가지 않는 AABB와 비교하면 너무 많은 연산이다.

 

보다 빠르게! 최적화된 SAT를 이용한 OOB 충돌 판정

• 다행히, OOB가 직사각형이라는 특징을 활용해 연산 횟수를 크게 줄일 수 있다. 크게 3가지 방식으로 줄일 수 있으며, 각각은 다음과 같다.

1. 법선 벡터 계산 최적화 - OOB의 축이 곧 변의 법선 벡터!: 기존 SAT 방식에서는 모든 변의 법선 벡터를 투영축으로 삼기 위해 법선 벡터를 구해야했다. 하지만, 직사각형의 경우, 직사각형의 두 축이 직사각형 변들의 법선벡터가 되므로, 따로 법선 벡터를 구하지 않아도 된다.
2. 투영축 개수 최적화 - 평행한 변의 법선 벡터는 같다: 직사각형은 마주 보는 변은 평행하다. 이는 마주보는 변은 법선 벡터를 내려도 결과가 같다는 것이다. 따라서, 각 OOB의 가로변 2개, 세로변 2개, 총 4개의 법선 벡터를 구하는게 아니라 가로변 1개, 세로변 1개의 법선 벡터를 구하면 된다.
3. 내적 횟수 최적화 - 투영된 길이는 2개의 변으로만 구할 수 있다: 아래 그림을 보면 알겠지만, 두 변의 투영된 결과만으로 전체 투영 길이를 알 수 있다. 따라서, 내적도 가로변 1개 세로변 1개만 하면 된다.

• 코드로 보면 아래와 같다.

float projectOBB(const OBB& obb, const Vector2& axis) {
    // OBB의 각 축이 분리축에 기여하는 투영 길이(정사열 비율 * 변 길이 / 2)
    float projX = abs(dot(obb.axisX, axis)) * obb.halfExtents.x;
    float projY = abs(dot(obb.axisY, axis)) * obb.halfExtents.y;
    
    // 전체 투영 길이 = 각 축의 기여도 합
    return projX + projY;
}

최적화 효과 정리

• 참고로, 위 방식은 최대/최소 점을 구하는 방식이 아니라서 중점 간의 거리를 투영하는 작업을 해야 한다.

구분 일반 사각형 SAT OBB SAT 최적화 비율

법선 벡터 생성	8개	0개	100% 감소
내적 연산	8축*8번 = 64번	4축*5번 = 20번	69% 감소
총 연산량	72개	20개	72% 감소