분리축 정리

게임 개발 컴퓨터 그래픽스 마지막 수정: 2026-08-23 04:49:06

1. 개요[편집]

분리축 정리 Separating Axis Theorem (SAT)
수학적 뿌리	볼록집합의 초평면 분리 정리
판정	어떤 축에 투영했을 때 두 구간이 벌어지면 안 겹친다
2D 볼록 다각형	두 다각형의 변 법선만 검사하면 충분
3D 볼록 다면체	면 법선 + 모서리 쌍 외적 (상자끼리면 3+3+9 = 15축)
부산물	최소 침투 벡터(MTV) — 겹침이 가장 작은 축
전제	볼록. 깨지면 정리 자체가 성립하지 않는다

분리축 정리(separating axis theorem, SAT)는 두 볼록체가 겹치지 않을 필요충분조건은, 두 물체를 각각 투영했을 때 투영 구간이 서로 벌어지는 축이 하나라도 존재하는 것이라는 정리다. 그리고 그 “하나라도”를 확인하기 위해 검사해야 할 축이 유한 개라는 사실이, 이 정리를 충돌 감지의 실무 알고리즘으로 만든다.

수학 쪽 뿌리는 볼록해석의 초평면 분리 정리다. 서로소인 두 볼록집합 $A$ , $B$ 에 대해 어떤 벡터 $\mathbf{a} \neq \mathbf{0}$ 와 상수 $c$ 가 있어

\sup_{\mathbf{x} \in A} \mathbf{a}\cdot\mathbf{x} \;\le\; c \;\le\; \inf_{\mathbf{y} \in B} \mathbf{a}\cdot\mathbf{y}

가 성립하고, 한쪽이 콤팩트이고 다른 쪽이 닫혀 있으면 부등호를 강부등호로 만들 수 있다. 여기서 $\mathbf{a}$ 가 초평면의 법선이자 곧 분리축이다. 게임 엔진이 하는 일은 이 무한 차원 정리를 “다면체이므로 후보 법선이 유한하다”는 관찰로 잘라 내 상수 시간 루프로 바꾼 것뿐이다.¹

2. 왜 유한 개의 축만 보면 되는가[편집]

투영 자체는 간단하다. 단위벡터 $\hat{\mathbf{a}}$ 에 대한 볼록체 $A$ 의 투영 구간은 지지함수로 쓰면

I_A(\hat{\mathbf{a}}) = \bigl[\,-h_A(-\hat{\mathbf{a}}),\ h_A(\hat{\mathbf{a}})\,\bigr], \qquad h_A(\hat{\mathbf{a}}) = \max_{\mathbf{x}\in A}\ \mathbf{x}\cdot\hat{\mathbf{a}}

이고, 다면체라면 최댓값은 반드시 꼭짓점에서 잡히므로 꼭짓점 내적의 최대·최소면 끝이다. 두 구간이 안 겹치면 분리, 겹치면 그 축은 무죄 — 모든 축에서 겹쳐야만 충돌이다.

문제는 축이 연속적으로 무한히 많다는 것인데, 여기서 민코프스키 합의 관점이 답을 준다. 두 볼록체가 겹칠 필요충분조건은 민코프스키 차 $A \ominus B$ 가 원점을 포함하는 것이다(GJK 알고리즘이 쓰는 바로 그 성질). 그런데 두 볼록 다면체의 민코프스키 차는 다시 볼록 다면체이고, 그 면들의 법선은 다음 셋 중 하나에서 온다.

$A$ 의 면 법선
$B$ 의 면 법선(부호 반전)
$A$ 의 모서리 방향과 $B$ 의 모서리 방향의 외적

원점이 볼록 다면체 밖에 있으면 그 다면체를 원점과 갈라놓는 지지 초평면이 존재하고, 그 초평면은 어떤 면 위에 놓을 수 있다. 따라서 분리축이 있다면 위 유한 목록 안에 반드시 있다. 이것이 SAT의 후보 축 집합이 유한한 이유이며, 동시에 왜 그 목록을 하나라도 빠뜨리면 안 되는지의 이유이기도 하다.

3. 2차원 — 변 법선만으로 충분하다[편집]

평면에서는 세 번째 항목이 사라진다. 2차원 “모서리”의 방향 둘을 외적하면 평면에 수직한 벡터가 나오는데, 그 축에 투영하면 두 다각형이 전부 한 점으로 뭉개져 아무 정보도 주지 않는다. 달리 말해 두 볼록 다각형의 민코프스키 차의 변은 전부 $A$ 나 $B$ 의 변을 평행이동한 것이라, 후보 법선이 두 다각형의 변 법선 $n + m$ 개로 끝난다.

절차는 이렇다. 각 후보 축 $\hat{\mathbf{a}}$ 에 대해 두 다각형의 꼭짓점을 전부 투영해 $[\min_A, \max_A]$ , $[\min_B, \max_B]$ 를 구하고,

\mathrm{overlap} \;=\; \min(\max_A, \max_B) \;-\; \max(\min_A, \min_B)

가 $\le 0$ 인 축이 하나라도 나오면 즉시 “분리”를 반환하고 끝낸다. 전부 양수면 충돌이며, 그중 가장 작은 overlap 을 준 축이 최소 침투 방향이다.

비용은 순진하게 짜면 축 $n+m$ 개 × 투영 $O(n+m)$ 이라 $O((n+m)^2)$ 다. 볼록성을 이용해 지지점을 이진 탐색이나 언덕 오르기로 찾으면 축당 $O(\log)$ 로 떨어지지만, 실제 게임에서 다루는 다각형은 꼭짓점이 서너 개에서 여덟 개 사이라 상수를 줄이는 편이 점근을 줄이는 것보다 훨씬 이득이다. 그래서 실무 코드는 대개 투영 루프를 그냥 펼쳐 쓴다.

두 볼록 다각형의 변 법선을 전부 축으로 삼아 정점을 투영하고, 두 구간이 떨어지는 축이 하나라도 나오면 거기서 판정을 끝낸다. 겹치면 밀어내기가 가장 짧은 축이 최소 침투 벡터(MTV)이고, 그만큼 민 B 를 매 프레임 재검사한다 — 무작위 볼록쌍 20000개에서 클리핑 교집합 면적 판정과 불일치 0건, MTV 로 민 뒤 잔여 겹침은 최대 3.47e-6 px 였다.

원이나 캡슐이 섞이면 이야기가 달라진다. 원은 면 법선이 무한히 많아서 후보 목록을 만들 수 없다. 다각형-원 판정에서는 다각형의 변 법선들에 원 중심에서 가장 가까운 꼭짓점으로 향하는 축 하나를 추가하면 되는데, 이건 SAT의 일반 절차가 아니라 그 형상에 대해 따로 유도한 예외다. 곡면이 하나라도 섞이면 SAT는 도형별 특수 케이스의 모음이 된다 — 임의의 볼록 형상을 지지함수 하나로 다루는 GJK 알고리즘과 갈리는 지점이 정확히 여기다.

4. 3차원 — 면 법선만으로는 부족하다[편집]

3차원에서 면 법선만 검사하면 틀린 답이 나온다. 두 상자를 서로 비스듬히 돌려 모서리끼리 스쳐 지나가게 배치하면, 여섯 개의 면 법선 전부에서 투영이 겹치는데도 실제로는 떨어져 있는 배치를 쉽게 만들 수 있다. 이 경우 둘을 갈라 주는 초평면의 법선은 어느 면에도 수직하지 않고, $A$ 의 한 모서리와 $B$ 의 한 모서리 양쪽에 수직한 방향이다. 그래서 외적 축이 목록에 들어가야 한다.

면이 $F_A$ , $F_B$ 개이고 모서리 방향이 $E_A$ , $E_B$ 종류인 두 볼록 다면체라면 축은 $F_A + F_B + E_A E_B$ 개다. 직육면체는 면 법선이 (평행한 면끼리 같으므로) 각 3개, 모서리 방향도 각 3종류라

3 + 3 + 3\times 3 \;=\; 15

축이 나온다. 이것이 방향성 경계 상자(OBB) 교차 판정의 그 유명한 15축 검사다.² 상자끼리는 투영 반경이 닫힌 식으로 나와서 꼭짓점을 훑을 필요조차 없다. $A$ 의 국소 축을 $\mathbf{u}_i$ , 반크기를 $a_i$ 라 하면 축 $\mathbf{L}$ 에 대한 투영 반경은 $r_A = \sum_i a_i \lvert \mathbf{u}_i \cdot \mathbf{L}\rvert$ 이고, 중심 간 벡터 $\mathbf{t}$ 에 대해

\lvert \mathbf{t}\cdot\mathbf{L} \rvert \;>\; r_A + r_B

이면 분리다. 두 상자의 상대 회전행렬을 한 번 만들어 두면 15축 전체가 곱셈 200회 남짓에 끝나고, 이것이 경계 볼륨 계층의 OBB 트리가 실시간으로 돌아가는 이유다. 삼각형이 섞이면 축 수가 늘어난다 — 상자-삼각형 판정은 상자 면 3 + 삼각형 면 1 + 외적 9 = 13축이 표준이다.

5. 최소 침투 벡터와 조기 탈출[편집]

SAT의 부산물이 최소 침투 벡터(minimum translation vector, MTV)다. 모든 축에서 겹쳤다면, overlap 이 가장 작았던 축 $\hat{\mathbf{a}}^\ast$ 방향으로 그 크기만큼 밀어내는 것이 두 물체를 떼어 놓는 최소 이동이다.

\mathbf{MTV} \;=\; \mathrm{overlap}_{\min} \cdot \hat{\mathbf{a}}^\ast

이것이 진짜 최솟값인 이유도 민코프스키 차로 설명된다. 침투 깊이란 원점에서 $A \ominus B$ 경계까지의 최단 거리인데, 원점이 볼록 다면체 내부에 있으므로 최근접 경계점은 어떤 면 위에 있고, 그 거리는 그 면의 지지평면까지의 거리와 같다. 면 법선은 전부 후보 축 목록 안에 있으므로 후보 축 위 overlap 의 최솟값 = 침투 깊이다. 단, 목록을 온전히 검사했을 때만 그렇다. 3차원에서 외적 축을 생략하면 분리 판정이 틀릴 뿐 아니라 MTV도 과대평가된다.

여기서 초보자가 반드시 한 번 밟는 지뢰가 있다. 분리 판정만 할 거면 축을 정규화하지 않아도 되지만, MTV를 뽑으려면 반드시 정규화해야 한다. 부호 비교는 스케일에 무관하지만 서로 다른 축의 overlap 크기를 비교하는 순간 축 길이가 개입하기 때문이다. 정규화를 빼먹으면 대부분의 상황에서 그럴듯하게 동작하다가 특정 각도에서만 물체가 엉뚱한 방향으로 튀어나가는, 재현하기 고약한 버그가 된다.³

성능 쪽 요령은 반대 방향이다. 분리 판정만 필요한 경우(대부분의 쌍이 여기 해당한다)에는 첫 분리축을 찾는 즉시 탈출한다. 그리고 지난 프레임에서 이 쌍을 분리했던 축을 캐시해 두었다가 다음 프레임에 맨 먼저 검사한다. 물체가 프레임 사이에 조금씩만 움직인다는 시간적 일관성 덕분에, 떨어져 있는 쌍은 대개 첫 축에서 바로 끝난다. 실제 접촉 중인 소수의 쌍만 15축을 전부 돌게 되는 구조다.

수치 강건성도 챙겨야 한다. 두 모서리가 거의 평행하면 외적이 거의 영벡터가 되고, 그것으로 나눈 정규화가 폭발한다. 상자가 바닥에 반듯이 놓인 흔한 배치가 정확히 이 경우다. 표준 처방은 상대 회전행렬의 절댓값 성분에 작은 $\varepsilon$ 을 더해 두는 것 — 축 길이가 임계값 아래면 그 축을 아예 건너뛰는 처리와 함께 쓴다. 건너뛴 축이 유일한 분리축이었다면 오탐(실제로는 안 닿았는데 닿았다고 판정)이 나지만, 그 상황은 두 물체가 이미 $\varepsilon$ 안쪽으로 스치는 배치라 실용적으로 무해하다. 부동소수점 연산의 오차를 정직하게 인정하고 안전한 쪽으로 편향시키는, 정확 술어 없이 사는 코드의 전형적인 타협이다.

6. 볼록성이 깨지면[편집]

SAT는 정리 자체가 볼록집합에 대해서만 참이다. 서로 맞물린 두 갈고리처럼 오목한 형상 둘은 완전히 떨어져 있어도 어떤 축으로도 투영 구간이 갈라지지 않을 수 있다. 그러면 알고리즘은 “겹쳤다”고 답한다 — 실제로는 떨어져 있는데도. 반대 방향의 오류(겹쳤는데 분리로 판정)는 원리적으로 안 생긴다. 공통점 하나가 모든 축에서 두 구간에 동시에 들어가기 때문이다. 즉 오목 입력에서 SAT는 한쪽으로만 틀리며 그 오답률을 제어할 방법이 없다. 정리를 “근사”로 쓸 여지가 없다는 뜻이다.

그래서 오목 메시를 만나면 선택지는 셋이다. 볼록 껍질로 감싸 정확도를 버리거나, 볼록 분해로 볼록 조각들로 쪼개 조각 쌍마다 SAT를 돌리거나, 삼각형 수프로 취급해 삼각형-볼록체 판정을 반복하거나. 실무는 정적 지형에는 삼각형 수프를, 움직이는 물체에는 볼록 분해를 쓴다. 여기서 주의할 점 하나 — 분해 결과의 조각이 $10^{-9}$ 만큼이라도 오목하면 SAT의 후보 축 목록이 불완전해져 판정이 틀린다. 볼록 분해 코드의 강건성이 충돌 판정의 정확성으로 그대로 전이된다.

7. GJK와의 비교, 그리고 스윕 SAT[편집]

항목	SAT	GJK + EPA
대상	볼록 다면체 (곡면은 특수 케이스)	지지함수가 있는 모든 볼록체
형태	유한 축 목록 전수 검사	심플렉스를 키우는 반복
분리 시	조기 탈출로 매우 빠름	거리까지 정확히 나옴
침투 시	MTV가 바로 나옴	EPA를 추가로 돌려야 함
축/정점 수 의존	다면체가 복잡해지면 축 수가 폭발	정점 수와 거의 무관
퇴화 상황	평행 모서리에서 외적 소실	원점이 심플렉스에 걸칠 때 예민

정리하면 상자·캡슐·삼각형처럼 면이 몇 개 안 되는 원시 형상에는 SAT, 정점이 많거나 형상 종류가 다양하면 GJK다. 실제 엔진은 둘 다 갖고 있고 형상 쌍의 종류에 따라 디스패치한다. Bullet이나 PhysX의 좁은 단계 테이블을 열어 보면 상자-상자는 전용 SAT 경로로, 볼록-볼록 일반은 GJK+EPA로 가는 식이다.

마지막으로 스윕 SAT. 지금까지의 판정은 한 순간의 스냅숏이라, 빠른 물체가 프레임 사이에 얇은 벽을 통과하는 터널링을 막지 못한다. 두 물체가 한 프레임 동안 등속 병진한다고 가정하면 SAT를 시간축으로 확장할 수 있다. 상대속도 $\mathbf{v}$ 를 축 $\hat{\mathbf{a}}$ 에 투영하면 그 축 위에서 한 구간이 속도 $\mathbf{v}\cdot\hat{\mathbf{a}}$ 로 미끄러지므로, 축마다 겹치기 시작하는 시각 $t_{\rm in}$ 과 겹침이 끝나는 시각 $t_{\rm out}$ 을 1차 방정식으로 풀 수 있다. 모든 축에 대해

\max_{\hat{\mathbf{a}}} t_{\rm in}(\hat{\mathbf{a}}) \;\le\; \min_{\hat{\mathbf{a}}} t_{\rm out}(\hat{\mathbf{a}})

이면 그 구간에서 충돌하고, 최초 충돌 시각(TOI)이 왼쪽 항이다. 축 하나에서 $t_{\rm in} > \min t_{\rm out}$ 이 되는 순간 조기 탈출한다. 회전이 섞이면 투영 구간이 시간의 1차 함수가 아니게 되어 이 방법이 깨지므로, 회전까지 다루려면 보수적 전진(conservative advancement)으로 시간을 조금씩 밀어 가며 정적 판정을 반복하는 쪽으로 넘어간다. 회전은 각속도 상한으로 보수적으로 처리하고 병진만 정확히 푸는 절충이 흔하다.

이렇게 나온 TOI와 접촉 법선이 접촉 매니폴드를 거쳐 제약 해결기로 들어가면, 비로소 강체 동역학의 충돌 응답이 시작된다. SAT가 하는 일은 거기까지 — “겹쳤는가, 얼마나, 어느 방향으로” 세 마디를 최대한 싸게 답하는 것이다.

8. 관련 문서[편집]

그래서 “SAT는 게임 개발자가 만든 알고리즘”이라는 말은 절반만 맞다. 정리는 볼록해석 교과서 앞부분에 나오는 고전이고, 게임 쪽 기여는 후보 축이 유한하다는 것과 그 목록을 정확히 무엇으로 잡아야 하는가를 형상별로 정리한 부분이다. 이론이 존재를 보장하고 공학이 목록을 만든 셈. ↩
15축을 처음 세어 보면 “면 법선이 6개 아니냐”고 생각하기 쉬운데, 직육면체의 마주 보는 두 면은 법선이 부호만 다르고 투영 구간은 똑같아서 3개면 된다. 이 착각이 그나마 안전한 쪽(중복 검사)인 것과 달리, 3차원에서 외적 9축을 빼먹는 착각은 조용히 틀린 답을 낸다. 게다가 그 오류는 두 상자가 비스듬히 스칠 때만 드러나서, 테스트 씬에서는 멀쩡하다가 출시 후 버그 리포트로 돌아온다. ↩
정규화를 빼먹은 MTV 버그가 악질인 이유는 증상이 각도에 의존하기 때문이다. 축 길이가 대체로 비슷한 배치에서는 최솟값 순서가 안 바뀌어 멀쩡히 돌아가고, 특정 회전각 근처에서만 순서가 뒤집힌다. 재현 조건이 “플레이어가 상자를 대충 37도쯤 돌려서 밀었을 때”라 QA가 잡아 주기를 기대하기 어렵고, 결국 단위 테스트에서 무작위 회전을 뿌려 MTV만큼 밀어낸 뒤 정말 안 겹치는지 검사하는 것이 정석이다. 이 테스트 한 줄이 있으면 처음부터 안 겪을 일이었다. ↩