GJK 알고리즘

게임 개발 컴퓨터 그래픽스 마지막 수정: 2026-07-12 04:18:12

1. 개요[편집]

GJK 알고리즘 Gilbert–Johnson–Keerthi Algorithm
제안	Gilbert, Johnson, Keerthi (1988)
분야	계산기하 × 충돌 감지 × 물리 엔진
대상	볼록체(convex shape) 간 거리·교차
핵심 도구	민코프스키 차, 심플렉스, 지지함수
짝꿍 알고리즘	EPA(침투 깊이)

GJK 알고리즘(Gilbert–Johnson–Keerthi algorithm)은 두 볼록체(convex shape) 사이의 최단 거리를 구하거나 서로 겹치는지를 판정하는 계산기하 알고리즘이다. 1988년 세 저자의 이름을 따 명명되었으며, 오늘날 거의 모든 실시간 물리 엔진의 충돌 감지 핵심으로 쓰인다.

GJK가 강력한 이유는 두 물체를 직접 비교하지 않는다는 발상에 있다. 두 볼록체 $A$ , $B$ 의 민코프스키 차(Minkowski difference)라는 새 도형을 생각하고, “그 도형이 원점을 포함하는가?”라는 단 하나의 질문으로 충돌 여부를 환원한다. 게다가 이 도형을 실제로 만들지도 않는다. 필요한 정보만 지지함수로 그때그때 뽑아 쓰기 때문에, 정점 수와 무관하게 빠르고 메모리도 거의 안 쓴다.

2. 민코프스키 차[편집]

두 집합 $A$ , $B$ 의 민코프스키 차는 모든 점 쌍의 차로 정의된다.

A \ominus B = \{\, \mathbf{a} - \mathbf{b} \mid \mathbf{a} \in A,\ \mathbf{b} \in B \,\}

핵심 성질은 이렇다. 두 물체가 겹칠 필요충분조건은, 공통점 $\mathbf{a}=\mathbf{b}$ 가 존재하는 것, 즉 $\mathbf{a}-\mathbf{b}=\mathbf{0}$ 인 점이 $A \ominus B$ 안에 있는 것이다. 정리하면:

$A$ 와 $B$ 가 교차한다 $\iff$ 원점 $\mathbf{0}$ 이 $A \ominus B$ 안에 있다.
겹치지 않으면, $A \ominus B$ 에서 원점까지의 최단 거리가 곧 두 물체 사이 거리다.

두 볼록체의 민코프스키 차는 다시 볼록체이므로, “볼록 도형이 원점을 품는가”라는 잘 정의된 문제만 풀면 된다. GJK는 이 도형 전체를 만들지 않고 아래의 지지함수만으로 이 판정을 수행한다.

3. 지지함수와 심플렉스[편집]

지지함수(support function)는 어떤 방향 $\mathbf{d}$ 로 도형에서 가장 멀리 있는 점을 돌려주는 함수다.

S_A(\mathbf{d}) = \arg\max_{\mathbf{x} \in A} \ \mathbf{x} \cdot \mathbf{d}

민코프스키 차 위의 지지점은 각 도형의 지지점을 빼기만 하면 얻어진다. 즉 $S_{A \ominus B}(\mathbf{d}) = S_A(\mathbf{d}) - S_B(-\mathbf{d})$ . 볼록체마다 이 함수는 쉽게 정의된다. 구는 중심에서 방향으로 반지름만큼, 다면체는 정점 중 내적이 최대인 것을 고르면 끝이다. 도형을 명시적으로 다루지 않고 이 함수 하나로 추상화하는 것이 GJK의 우아함이다.

심플렉스(simplex)는 2·3차원에서 점·선분·삼각형·사면체를 통칭한다. GJK는 민코프스키 차 위의 점을 하나씩 골라 심플렉스를 키워 가며 그 안에 원점이 갇히는지를 검사한다. 큰 흐름은 이렇다.

아무 방향으로 지지점 하나를 잡아 심플렉스를 시작한다.
현재 심플렉스에서 원점에 가장 가까운 부분(면·모서리)을 찾고, 원점을 향하는 방향 $\mathbf{d}$ 를 정한다.
그 방향으로 새 지지점을 추가한다. 새 점이 원점 쪽으로 충분히 나아가지 못하면(지지점이 방향을 넘어서지 못하면) 두 도형은 떨어져 있는 것이므로 종료.
심플렉스가 원점을 감싸면(사면체가 원점을 포함) 교차로 판정하고 종료.

이 과정은 최적화 관점에서 보면 원점에 가장 가까운 점을 반복해 좁혀 가는 하강 절차이며, 볼록성 덕분에 유한 스텝에 수렴한다.

주목할 점은 심플렉스가 아무리 커져도 차원 수+1개의 정점(3차원이면 최대 4개)만 유지하면 된다는 것이다. 새 지지점을 추가할 때 원점에 가장 가까운 부분에 기여하지 않는 오래된 정점은 곧바로 버린다. 덕분에 GJK는 도형의 정점이 수만 개든 심플렉스는 늘 작게 유지되어, 반복마다의 비용이 도형 복잡도와 사실상 무관하다. 이 “필요한 정점만 최소로 붙들고 나머지는 버린다”는 절약이 GJK를 실시간 예산 안에서 굴러가게 하는 비결이다.

4. EPA와 침투 깊이[편집]

GJK는 “겹치는가/안 겹치는가”와 “떨어진 거리”까지는 알려주지만, 얼마나 깊이 파고들었는가(침투 깊이)와 그것을 어느 방향으로 밀어내야 하는가는 알려주지 않는다. 물리 엔진이 충돌을 해소하려면 이 정보가 반드시 필요하다.

그래서 GJK가 교차를 확인해 원점을 감싼 심플렉스를 넘겨주면, EPA(Expanding Polytope Algorithm)가 이어받는다. EPA는 그 심플렉스를 민코프스키 차 경계 쪽으로 계속 부풀려, 원점에서 경계까지의 최소 거리와 그 방향을 찾는다. 이 방향이 최소 이동 벡터(MTV, minimum translation vector)로, 강체 동역학의 접촉 처리와 제약 해결기가 이 값을 받아 물체를 겹침에서 밀어낸다.

5. 물리 엔진에서의 활용[편집]

Bullet: 볼록-볼록 충돌의 좁은 단계(narrow phase)에서 GJK+EPA를 표준으로 쓴다. 오픈소스라 GJK 구현의 사실상 교과서 역할도 한다.
PhysX: NVIDIA의 물리 엔진 역시 볼록체 충돌에 GJK 계열을 채택한다.
GJK는 어디까지나 볼록체 전용이다. 오목한(concave) 메시는 볼록 조각으로 분해(convex decomposition)하거나 삼각형 단위로 나눠 처리해야 한다.
실무에서는 매 프레임 GJK를 모든 쌍에 돌리지 않는다. 공간 분할 자료구조나 AABB 기반 넓은 단계(broad phase)로 후보 쌍을 먼저 걸러낸 뒤, 살아남은 쌍에만 GJK를 돌린다.¹
빠르게 스치는 물체가 프레임 사이를 통과해 버리는 터널링(tunneling)을 막으려면, 움직임을 따라 GJK를 훑는 컨서버티브 어드밴스먼트나 연속 충돌 감지로 확장한다.

6. 여담[편집]

GJK는 “볼록성”이라는 단 하나의 가정으로 이렇게 많은 것을 해내는 대표적인 예다. 볼록집합에서는 국소 최소가 곧 전역 최소라는 성질이 알고리즘의 종료와 정확성을 동시에 보장한다.
구현이 짧고 정점 수와 거의 무관하게 빠르지만, 원점에 심플렉스가 아슬아슬하게 걸치는 퇴화(degenerate) 상황에서 수치적으로 예민해진다. “GJK는 30줄인데 그중 20줄이 예외 처리”라는 농담이 괜히 나온 게 아니다.²
거리 쿼리 버전은 게임 AI의 시야 판정이나 로봇 팔의 충돌 회피 경로계획에도 그대로 쓰인다. 충돌 감지 밖으로도 쓰임새가 넓다.

7. 관련 문서[편집]

넓은 단계는 “겹칠 가능성이 있는가”를 대충 빠르게, 좁은 단계는 “정확히 어떻게 겹치는가”를 정밀하게 본다. GJK는 좁은 단계의 주역이다. 이 2단 구조가 없으면 물체 $N$ 개에 대해 $O(N^2)$ 쌍을 전부 정밀 검사하는 참사가 벌어진다. ↩
특히 3차원에서 심플렉스가 사면체로 커질 때, 원점이 어느 영역(voronoi region)에 속하는지 가르는 분기가 만만치 않다. 그래서 실무 구현은 Casey Muratori의 강의처럼 케이스를 시각적으로 정리해 두고 참고하는 경우가 많다. ↩