게임 개발의 핵심인 충돌 감지 알고리즘, SAT와 GJK의 수학적 원리와 내부 동작 방식을 깊이 파헤쳐봅니다. 실제 게임 개발에 어떻게 적용되는지 실무 관점에서 분석합니다.
안녕하세요, 게임 개발의 흥미로운 세계에 오신 여러분을 환영합니다. 게임 개발의 꽃이라고 할 수 있는 화려한 그래픽 뒤에는, 보이지 않는 곳에서 게임의 현실감을 부여하고 예측 가능한 상호작용을 가능하게 하는 수많은 기술이 숨어 있습니다. 그중에서도 물리 엔진은 게임 속 오브젝트들이 실제 세계처럼 움직이고 부딪히도록 만듭니다. 하지만 단순히 오브젝트가 스쳐 지나가지 않도록 하는 것을 넘어, ‘어떻게’ 충돌했는지 정확히 감지하고 반응하는 것은 결코 쉬운 일이 아닙니다.
혹시 게임 속 캐릭터가 벽을 뚫고 지나가거나, 오브젝트들이 서로 겹쳐지는 현상을 경험해 본 적 있으신가요? 이러한 버그는 대부분 충돌 감지(Collision Detection) 알고리즘이 제대로 작동하지 않거나, 복잡한 상황을 처리하지 못할 때 발생합니다. 특히 3D 환경에서 다양한 형태의 오브젝트들이 복잡하게 움직일 때, 충돌 여부를 정확하고 효율적으로 판단하는 것은 물리 엔진의 성능을 좌우하는 핵심 요소가 됩니다.
이번 글에서는 게임 물리 엔진의 심장이라 불리는 두 가지 주요 충돌 감지 알고리즘, 바로 분리 축 정리(Separating Axis Theorem, SAT)와 길버트-존슨-케어시히(Gilbert-Johnson-Keerthi, GJK) 알고리즘을 심층적으로 해부해보고자 합니다. 단순히 "이것은 이런 기능을 한다"를 넘어, 이들이 어떻게 복잡한 도형 간의 충돌을 수학적으로 찾아내는지 그 내부 동작 원리를 깊이 있게 파헤쳐 보겠습니다. 실무 1~3년차 주니어 개발자로서 기본적인 지식은 갖추고 있지만, 실제 엔진 속에서 이 알고리즘들이 어떻게 구현되고 활용되는지 궁금했던 분들을 위한 글입니다. 함께 게임 물리 엔진의 비밀을 풀어보는 여정을 시작해 볼까요?
📑 목차
- 1. 문제 상황: 단순 충돌 감지의 한계와 복잡한 도형의 등장
- 2. 초기 접근: 분리 축 정리(SAT)로 다각형 충돌 문제 해결하기
- 2.1. SAT의 기본 원리: 축 투영
- 2.2. SAT의 장단점 및 한계
- 3. 더 복잡한 문제: 볼록 다면체와 GJK 알고리즘의 필요성
- 4. SAT의 진화: 민코프스키 합과 GJK 알고리즘
- 4.1. GJK의 핵심: 민코프스키 합과 원점 찾기
- 4.2. GJK 알고리즘의 동작 과정 (심플렉스 구성)
- 4.3. GJK의 특징 및 장점
- 5. 충돌 정보 추출: EPA 알고리즘의 역할
- 5.1. EPA의 동작 원리
- 6. SAT와 GJK, 실제 게임 개발에서의 선택 가이드
- 6.1. 언제 SAT를 선택해야 할까요?
- 6.2. 언제 GJK를 선택해야 할까요?
- 7. 마무리하며: 충돌 감지 알고리즘의 미래와 당신의 역할
Image by Septimiu on Pixabay
1. 문제 상황: 단순 충돌 감지의 한계와 복잡한 도형의 등장
가장 기본적인 충돌 감지는 두 원(2D) 또는 두 구(3D) 사이의 거리 비교로 시작합니다. 두 원의 중심 간 거리가 반지름의 합보다 작으면 충돌한 것으로 판단하는 방식이죠. 매우 빠르고 구현하기 쉽다는 장점이 있습니다. 하지만 모든 게임 오브젝트가 완벽한 원이나 구 형태일 수는 없습니다. 캐릭터, 건물, 무기 등 대부분의 오브젝트는 사각형, 다각형, 그리고 3D 환경에서는 복잡한 다면체 형태를 가집니다.
사각형이나 축 정렬 바운딩 박스(Axis-Aligned Bounding Box, AABB) 간의 충돌은 각 축(X, Y, Z)에서 구간 겹침 여부를 확인하는 방식으로 비교적 쉽게 처리할 수 있습니다. 그러나 회전하는 사각형이나 임의의 다각형, 그리고 볼록 다면체(Convex Polyhedra)가 등장하면 문제는 훨씬 복잡해집니다. AABB는 회전하는 오브젝트에 대해 지나치게 여유로운 경계를 제공하여, 실제로는 충돌하지 않았는데도 충돌했다고 판단하는 오탐(False Positive)을 유발하기 쉽습니다. 이러한 오탐은 불필요한 물리 계산으로 이어져 성능 저하를 야기하고, 게임의 정확성을 떨어뜨립니다.
따라서 우리는 더욱 정교하고 효율적으로 복잡한 도형 간의 충돌을 감지할 수 있는 알고리즘이 필요해집니다. 단순히 충돌 여부를 판단하는 것을 넘어, 충돌이 발생했다면 어느 방향으로, 얼마나 깊이 겹쳤는지(접촉 법선 벡터와 관통 깊이)까지 알아내야 합니다. 이 정보는 충돌 후 오브젝트를 밀어내거나, 충격량(Impulse)을 계산하여 현실적인 물리 반응을 구현하는 데 필수적이기 때문입니다.
이러한 요구사항을 충족시키기 위해 등장한 대표적인 알고리즘이 바로 SAT와 GJK입니다. 각각의 장단점과 적용 시나리오를 이해하는 것이 중요하며, 이제 이들을 하나씩 깊이 있게 살펴보겠습니다.
2. 초기 접근: 분리 축 정리(SAT)로 다각형 충돌 문제 해결하기
분리 축 정리(Separating Axis Theorem, SAT)는 두 볼록 다각형(2D) 또는 볼록 다면체(3D)가 충돌하지 않는다면, 반드시 두 도형을 완벽하게 분리하는 하나 이상의 축(Separating Axis)이 존재한다는 수학적 원리에 기반합니다. 반대로 말하면, 모든 가능한 분리 축에 대해 두 도형이 서로 겹치지 않는다는 것을 증명할 수 없다면, 두 도형은 충돌한 것으로 간주합니다.
2.1. SAT의 기본 원리: 축 투영
SAT의 핵심은 바로 투영(Projection)입니다. 두 도형이 충돌했는지 여부를 판단하기 위해, 우리는 특정 축에 두 도형을 투영하여 각각의 투영 구간(Projected Interval)을 얻습니다. 만약 이 두 투영 구간이 서로 겹치지 않는다면, 그 축은 두 도형을 분리하는 축이 되며, 우리는 즉시 두 도형이 충돌하지 않았다고 결론 내릴 수 있습니다. 만약 모든 후보 축에 대해 투영 구간이 겹친다면, 비로소 두 도형이 충돌했다고 판단하게 됩니다.
그렇다면 어떤 축들을 후보로 삼아야 할까요? SAT는 두 볼록 도형의 모든 면(또는 모서리)의 법선 벡터를 잠재적인 분리 축으로 고려합니다. 2D 다각형의 경우, 각 모서리의 법선 벡터가 후보 축이 됩니다. 3D 다면체의 경우, 각 면의 법선 벡터뿐만 아니라, 두 다면체의 모서리 쌍에서 생성되는 교차곱(Cross Product) 벡터도 후보 축으로 추가해야 합니다. 이 교차곱 벡터는 두 다면체 사이의 "틈새"를 찾아낼 수 있는 축을 제공합니다.
예를 들어, 2D에서 두 사각형 A와 B의 충돌 여부를 판단한다고 가정해 봅시다. 사각형 A의 모서리 4개에서 4개의 법선 벡터를 얻고, 사각형 B의 모서리 4개에서 4개의 법선 벡터를 얻습니다. 총 8개의 후보 축에 대해 각각 A와 B를 투영하여 투영 구간의 겹침 여부를 확인합니다. 단 한 번이라도 겹치지 않는 축을 찾으면, 두 사각형은 충돌하지 않은 것입니다.
// 가상의 투영 함수 예시 (2D)
public class Vector2 { /* ... */ }
public class Polygon {
public List<Vector2> Vertices { get; set; }
// ...
public Interval Project(Vector2 axis) {
float min = Vector2.Dot(Vertices[0], axis);
float max = min;
for (int i = 1; i < Vertices.Count; i++) {
float projection = Vector2.Dot(Vertices[i], axis);
if (projection < min) min = projection;
if (projection > max) max = projection;
}
return new Interval(min, max);
}
}
public class Interval {
public float Min { get; set; }
public float Max { get; set; }
public bool Overlaps(Interval other) {
return Max >= other.Min && other.Max >= Min;
}
}
// 충돌 감지 로직의 일부
public bool CheckCollisionSAT(Polygon p1, Polygon p2) {
List<Vector2> axes = new List<Vector2>();
// p1의 모서리 법선 벡터 추가
for (int i = 0; i < p1.Vertices.Count; i++) {
Vector2 p1v1 = p1.Vertices[i];
Vector2 p1v2 = p1.Vertices[(i + 1) % p1.Vertices.Count];
Vector2 edge = p1v2 - p1v1;
axes.Add(new Vector2(-edge.Y, edge.X).Normalized()); // 법선 벡터
}
// p2의 모서리 법선 벡터 추가
for (int i = 0; i < p2.Vertices.Count; i++) {
Vector2 p2v1 = p2.Vertices[i];
Vector2 p2v2 = p2.Vertices[(i + 1) % p2.Vertices.Count];
Vector2 edge = p2v2 - p2v1;
axes.Add(new Vector2(-edge.Y, edge.X).Normalized());
}
foreach (Vector2 axis in axes) {
Interval p1Proj = p1.Project(axis);
Interval p2Proj = p2.Project(axis);
if (!p1Proj.Overlaps(p2Proj)) {
return false; // 분리 축 발견, 충돌 아님
}
}
return true; // 모든 축에서 겹침, 충돌임
}
2.2. SAT의 장단점 및 한계
SAT는 볼록 다각형 및 다면체 간의 충돌 감지에 매우 효과적이며, 충돌이 발생하지 않았을 때 빠르게 '분리 축'을 찾아내 계산을 조기에 종료할 수 있다는 장점이 있습니다. 또한, 모든 축에서 겹침이 확인되면 가장 작은 겹침(Minimum Overlap)을 가진 축과 그 겹침의 양을 통해 관통 깊이(Penetration Depth)와 접촉 법선(Contact Normal)을 쉽게 얻을 수 있어, 충돌 반응을 구현하는 데 필요한 정보를 직접적으로 제공합니다. 이는 물리 엔진에서 오브젝트를 밀어내거나 반사시킬 때 매우 유용합니다.
하지만 SAT에도 한계는 명확합니다. 첫째, 오직 볼록 도형에만 적용됩니다. 오목한 도형은 볼록 도형으로 쪼개서 처리해야 하는데, 이 과정 자체가 복잡하고 성능 비용이 발생할 수 있습니다. 둘째, 후보 축의 수가 도형의 면(모서리) 수에 비례하여 증가합니다. 특히 3D 다면체의 경우, 두 다면체의 모서리 쌍에서 생성되는 교차곱 축까지 고려해야 하므로, 복잡한 다면체일수록 계산량이 급격히 늘어날 수 있습니다. 예를 들어, N개의 면을 가진 다면체와 M개의 면을 가진 다면체가 충돌하면, N+M개의 면 법선 축과 N*M개의 모서리 교차곱 축을 확인해야 합니다. 이는 많은 수의 정점을 가진 오브젝트에는 비효율적일 수 있습니다.
3. 더 복잡한 문제: 볼록 다면체와 GJK 알고리즘의 필요성
SAT는 2D 볼록 다각형 충돌에 매우 강력하지만, 3D 볼록 다면체로 확장될 때 후보 축의 개수가 기하급수적으로 늘어나는 문제에 직면합니다. 특히 면과 정점의 수가 많은 복잡한 3D 모델의 경우, 모든 면 법선과 모서리 교차곱을 계산하는 것은 상당한 성능 부담을 초래합니다. 또한, SAT는 오목한 도형에는 직접 적용할 수 없다는 근본적인 한계가 있습니다.
게임 개발에서는 맵의 지형, 캐릭터 모델 등 다양한 형태의 오브젝트가 등장하며, 이들은 반드시 볼록 도형만은 아닙니다. 물론 오목한 도형은 여러 개의 볼록 도형으로 분해하여 처리할 수 있지만, 이는 추가적인 전처리 작업과 충돌 감지 로직의 복잡성을 증가시킵니다. 따라서 우리는 복잡한 3D 볼록 다면체 간의 충돌을 더욱 효율적으로 감지하고, 나아가 오목한 도형까지도 간접적으로 처리할 수 있는 알고리즘이 필요해집니다.
이러한 배경에서 길버트-존슨-케어시히(Gilbert-Johnson-Keerthi, GJK) 알고리즘이 등장합니다. GJK는 SAT와는 전혀 다른 접근 방식을 취하며, 두 볼록 도형 사이의 최소 거리를 찾아 충돌 여부를 판단합니다. 특히, GJK는 후보 축을 미리 정해놓고 모두 확인하는 SAT 방식과 달리, 반복적인 탐색을 통해 필요한 정보만을 얻어내므로, 복잡한 도형에서도 효율적인 성능을 보여줍니다.
Image by distelAPPArath on Pixabay
4. SAT의 진화: 민코프스키 합과 GJK 알고리즘
GJK 알고리즘은 민코프스키 합(Minkowski Sum)이라는 강력한 수학적 개념을 기반으로 합니다. 두 볼록 도형 A와 B가 충돌했는지 여부는, 두 도형의 민코프스키 차이(Minkowski Difference) 안에 원점(Origin)이 포함되어 있는지 여부와 동일합니다. 민코프스키 차이 $A - B$는 모든 점 $a \in A$와 $b \in B$에 대해 $a - b$로 얻어지는 모든 점들의 집합입니다.
즉, $A \cap B \neq \emptyset \iff 0 \in (A - B)$ 입니다. 두 도형 A와 B가 겹친다면, A와 B에 공통으로 속하는 점 $p$가 존재합니다. 그러면 $p - p = 0$ 이므로, 원점은 민코프스키 차이 안에 존재하게 됩니다. GJK는 이 원리를 이용하여, 민코프스키 차이 $A - B$ 내부에서 원점에 가장 가까운 점을 반복적으로 찾아나가는 알고리즘입니다.
4.1. GJK의 핵심: 민코프스키 합과 원점 찾기
GJK는 실제로 민코프스키 차이 도형 $A-B$ 전체를 명시적으로 구성하지 않습니다. 대신, 지지 함수(Support Function)라는 추상적인 개념을 사용합니다. 지지 함수 $S_C(d)$는 방향 벡터 $d$에 대해 볼록 도형 $C$의 가장 먼 점을 반환하는 함수입니다.
두 도형 A와 B의 민코프스키 차이 $A-B$의 지지 함수는 다음과 같이 정의됩니다:
$S_{A-B}(d) = S_A(d) - S_B(-d)$
이 지지 함수를 통해 우리는 민코프스키 차이 도형의 경계면에 있는 점들을 효율적으로 찾아낼 수 있습니다. GJK는 이 지지 함수를 사용하여 민코프스키 차이 도형 내부에 심플렉스(Simplex)라는 최소한의 기하학적 구조(점, 선분, 삼각형, 사면체)를 구축하며, 이 심플렉스가 원점을 포함하는지 여부를 판단합니다.
4.2. GJK 알고리즘의 동작 과정 (심플렉스 구성)
GJK 알고리즘은 다음과 같은 단계로 진행됩니다:
- 초기 방향 설정 및 첫 번째 점 추가: 임의의 방향 $d$를 설정하고, 민코프스키 차이의 지지 함수를 사용하여 첫 번째 점 $v_0 = S_{A-B}(d)$를 심플렉스에 추가합니다. 이 점은 민코프스키 차이 도형의 경계면에 있습니다.
- 원점에 가장 가까운 점 찾기 및 새로운 방향 설정: 현재 심플렉스 내에서 원점에 가장 가까운 점 $P$를 찾습니다. 그리고 원점에서 $P$를 향하는 벡터를 새로운 탐색 방향 $d_{new} = \text{Origin} - P$로 설정합니다.
- 새로운 점 추가: 새로운 방향 $d_{new}$를 사용하여 $v_{new} = S_{A-B}(d_{new})$를 계산하고 심플렉스에 추가합니다.
- 충돌 여부 판단 및 심플렉스 업데이트:
- 만약 $v_{new}$가 $d_{new}$ 방향으로 원점보다 멀리 있지 않다면 (즉, $d_{new} \cdot v_{new} < 0$), 이는 원점이 민코프스키 차이 도형의 바깥에 있다는 의미이므로, 두 도형은 충돌하지 않은 것입니다. 알고리즘을 종료하고 '충돌 없음'을 반환합니다.
- 만약 $v_{new}$가 $d_{new}$ 방향으로 원점보다 가깝다면, 심플렉스를 업데이트합니다. 원점을 포함하는 심플렉스의 부분집합을 선택하고, 이전 점들 중 불필요한 점은 제거합니다.
- 만약 심플렉스가 원점을 포함하게 되면 (예: 2D에서는 삼각형이 원점을 포함, 3D에서는 사면체가 원점을 포함), 두 도형은 충돌한 것입니다. 알고리즘을 종료하고 '충돌'을 반환합니다.
- 반복: 위의 2단계부터 4단계까지를 반복하여 원점에 가장 가까운 점을 찾거나 원점을 포함하는 심플렉스를 발견할 때까지 진행합니다.
GJK는 최대 4개(3D의 경우)의 점으로 구성된 심플렉스만을 유지하므로, 계산량이 도형의 복잡도(정점 수)에 크게 의존하지 않고 일정한 반복 횟수 내에서 수렴하는 경향이 있습니다. 이것이 GJK가 복잡한 3D 볼록 다면체 충돌 감지에 매우 효율적인 이유입니다.
// 가상의 GJK 알고리즘 구조 예시
public class GJKAlgorithm {
// SupporFunction: 주어진 방향 벡터 d에 대해 도형의 가장 먼 점을 반환
public Vector3 Support(ConvexShape shape, Vector3 direction) {
// 실제 구현에서는 shape의 정점들을 순회하며 dot product가 최대인 정점을 찾음
// 예: shape.Vertices.Aggregate((maxV, nextV) => Vector3.Dot(maxV, direction) > Vector3.Dot(nextV, direction) ? maxV : nextV);
return shape.GetFarthestPointInDirection(direction);
}
// Minkowski Difference의 Support Function
public Vector3 SupportMinkowskiDifference(ConvexShape shapeA, ConvexShape shapeB, Vector3 direction) {
return Support(shapeA, direction) - Support(shapeB, -direction);
}
public bool CheckCollision(ConvexShape shapeA, ConvexShape shapeB) {
List<Vector3> simplex = new List<Vector3>();
// 1. 초기 방향 설정 (예: 임의의 축)
Vector3 direction = new Vector3(1, 0, 0);
// 2. 첫 번째 점 추가
simplex.Add(SupportMinkowskiDifference(shapeA, shapeB, direction));
// 3. 원점에서 첫 번째 점을 향하는 방향으로 업데이트
direction = -simplex[0];
while (true) {
Vector3 newPoint = SupportMinkowskiDifference(shapeA, shapeB, direction);
// 4. 새로운 점이 원점 방향으로 나아가지 않았다면 충돌 아님
if (Vector3.Dot(newPoint, direction) <= 0) {
return false;
}
simplex.Add(newPoint);
// 5. 심플렉스 처리: 원점을 포함하는지 확인하고, 심플렉스를 업데이트 (점, 선, 면, 사면체)
// 이 부분이 GJK 알고리즘의 핵심이자 가장 복잡한 부분
// Simplex.ContainsOriginAndUpdate(simplex, ref direction)
// 이 함수는 원점을 포함하는지 여부와 다음 탐색 방향을 반환함
bool originContained = ProcessSimplex(simplex, ref direction);
if (originContained) {
return true; // 원점을 포함하는 심플렉스 발견, 충돌
}
// Simplex가 최대 4개의 점을 넘지 않도록 관리
// ... (불필요한 점 제거 로직)
}
}
// ProcessSimplex는 심플렉스의 차원에 따라 원점을 포함하는지 확인하고
// 다음 탐색 방향을 결정하는 복잡한 로직을 담고 있습니다.
// 여기서는 개념적인 placeholder로 대체합니다.
private bool ProcessSimplex(List<Vector3> simplex, ref Vector3 direction) {
// 2D: 선분, 삼각형
// 3D: 선분, 삼각형, 사면체
// 심플렉스의 현재 형태에 따라 원점이 포함되는지 확인하고
// 포함되지 않으면 원점에 가장 가까운 점을 찾아 다음 방향을 설정
// 포함되면 true 반환
// 예: 4개의 점으로 사면체가 구성되었고 원점을 포함한다면 true 반환
// 그렇지 않다면, 원점에 가장 가까운 면/모서리/점을 기반으로 새로운 direction 설정
// 그리고 심플렉스에서 불필요한 점들을 제거 (최대 4개 유지)
return false;
}
}
4.3. GJK의 특징 및 장점
GJK는 다음과 같은 특징과 장점을 가집니다:
- 효율성: 도형의 복잡도(정점/면 수)에 덜 민감합니다. 반복 횟수가 적고, 각 반복에서 계산하는 양이 적습니다. 이는 특히 3D 환경에서 수백, 수천 개의 정점을 가진 복잡한 볼록 메쉬 간의 충돌 감지에 매우 유리합니다.
- 범용성: 어떤 형태의 볼록 도형이든 지지 함수만 제공할 수 있다면 충돌 감지가 가능합니다. 원, 구, AABB, OBB(Oriented Bounding Box), 볼록 메쉬 등 다양한 도형에 동일한 알고리즘을 적용할 수 있습니다.
- 거리 정보 제공: 충돌하지 않았을 경우, 원점에서 민코프스키 차이의 가장 가까운 점까지의 거리를 알 수 있습니다. 이는 두 도형 사이의 최소 거리를 의미하며, 충돌 예측(Continuous Collision Detection)에도 활용될 수 있습니다.
하지만 GJK는 SAT와 달리, 단순히 충돌 여부만 알려줄 뿐 충돌 법선 벡터나 관통 깊이를 직접적으로 제공하지 않습니다. 충돌 반응을 위해서는 이 정보가 필수적이므로, GJK로 충돌을 감지한 후에는 확장된 위상 알고리즘(Expanding Polytope Algorithm, EPA)과 같은 보조 알고리즘을 사용하여 이 정보를 추출해야 합니다.
5. 충돌 정보 추출: EPA 알고리즘의 역할
앞서 언급했듯이, GJK는 두 볼록 도형이 충돌했는지 여부만을 효율적으로 알려줍니다. 하지만 게임에서 충돌 반응을 구현하려면, 충돌 법선(Contact Normal)과 관통 깊이(Penetration Depth)가 필수적입니다. 이때 GJK와 함께 사용되는 알고리즘이 바로 확장된 위상 알고리즘(Expanding Polytope Algorithm, EPA)입니다.
EPA는 GJK가 충돌을 감지하여 원점을 포함하는 최종 심플렉스(3D의 경우 사면체)를 찾았을 때 작동합니다. 이 심플렉스는 민코프스키 차이 도형 $A-B$ 내부에 있지만, 정확한 충돌 정보를 얻기 위해서는 민코프스키 차이 도형의 경계면(Boundary)을 찾아야 합니다. EPA는 GJK가 찾은 심플렉스를 시작으로, 민코프스키 차이 도형의 경계면을 점진적으로 확장(Expanding)해나가며 원점에서 가장 가까운 경계면을 찾는 알고리즘입니다.
5.1. EPA의 동작 원리
EPA는 다음과 같은 단계로 진행됩니다:
- GJK의 심플렉스 활용: GJK가 충돌을 감지하고 반환한, 원점을 포함하는 최종 심플렉스(3D의 경우 사면체)를 EPA의 시작점으로 사용합니다.
- 가장 가까운 면 찾기: 현재 심플렉스의 모든 면(Facet) 중에서 원점에서 가장 가까운 면을 찾습니다. 이 면의 법선 벡터가 현재까지 찾은 충돌 법선의 후보가 됩니다.
- 새로운 지지점 추가: 원점에서 가장 가까운 면의 법선 방향으로 민코프스키 차이의 지지 함수를 호출하여 새로운 지지점 $v_{new}$를 얻습니다.
- 확장 및 업데이트:
- 만약 새로운 지지점 $v_{new}$가 현재 원점에서 가장 가까운 면과 거의 같은 거리에 있다면 (즉, 더 이상 도형을 확장할 수 없다면), 해당 면의 법선 벡터가 최종 충돌 법선이 되고, 원점에서 그 면까지의 거리가 관통 깊이가 됩니다. 알고리즘을 종료합니다.
- 만약 $v_{new}$가 현재 면보다 원점에 더 가까이 있다면, 심플렉스를 업데이트하여 $v_{new}$를 포함시키고, 도형을 확장하여 원점에 더 가까운 면을 찾기 위해 2단계부터 다시 반복합니다. 이 과정에서 기존 심플렉스의 일부 면이 제거되고 새로운 면이 생성될 수 있습니다.
EPA는 GJK가 제공한 심플렉스에서 시작하여, 마치 풍선을 불듯이 민코프스키 차이 도형의 경계면을 원점을 향해 확장해나가는 과정과 유사합니다. 최종적으로 원점에서 가장 가까운 경계면을 찾아내고, 그 면의 법선과 원점으로부터의 거리를 통해 충돌 법선과 관통 깊이를 얻어냅니다.
EPA는 GJK와 결합하여 볼록 도형 간의 충돌 감지 및 반응에 필요한 모든 정보를 제공하는 강력한 조합을 이룹니다. 이 두 알고리즘은 현대 게임 물리 엔진에서 널리 사용되며, 복잡한 3D 환경에서의 효율적인 충돌 처리를 가능하게 합니다.
Image by Pixel-mixer on Pixabay
6. SAT와 GJK, 실제 게임 개발에서의 선택 가이드
SAT와 GJK는 모두 볼록 도형 간의 충돌을 감지하는 강력한 알고리즘이지만, 각각의 특성과 성능 프로파일이 다르므로 실제 게임 개발에서는 상황에 맞춰 적절히 선택하거나 조합하여 사용해야 합니다. 다음 표에서 두 알고리즘의 주요 특징을 비교해 보겠습니다.
| 특징 | 분리 축 정리 (SAT) | GJK 알고리즘 |
|---|---|---|
| 적용 도형 | 볼록 다각형 (2D), 볼록 다면체 (3D) | 모든 볼록 도형 (구, AABB, OBB, 볼록 메쉬 등) |
| 주요 원리 | 분리 축 존재 여부 확인 (축 투영) | 민코프스키 차이 내 원점 포함 여부 확인 (반복적 탐색) |
| 성능 (복잡도) | 후보 축 수에 비례 (2D는 효율적, 3D는 도형 복잡도에 따라 증가) | 도형 복잡도에 덜 민감 (일정한 반복 횟수 내 수렴) |
| 충돌 정보 제공 | 충돌 법선, 관통 깊이 직접 제공 (최소 겹침 축) | 충돌 여부만 제공 (정보 추출을 위해 EPA 필요) |
| 구현 난이도 | 2D는 비교적 쉬움, 3D는 후보 축 관리 및 교차곱 계산이 복잡함 | 개념 이해 및 심플렉스 처리 로직이 복잡함 |
| 특징 | 충돌하지 않을 때 조기 종료 가능. 볼록성에 의존. | 충돌하지 않을 때 최소 거리 정보 제공. 어떤 볼록 도형이든 통합 처리 가능. |
6.1. 언제 SAT를 선택해야 할까요?
- 2D 게임 개발: 2D 볼록 다각형 간의 충돌 감지에는 SAT가 매우 효율적이고 구현하기 쉽습니다. 특히 충돌 법선과 관통 깊이를 바로 얻을 수 있어 충돌 반응 구현이 간편합니다.
- 단순한 3D 볼록 도형: AABB나 OBB와 같이 면과 정점의 수가 적은 3D 볼록 도형 간의 충돌에는 여전히 SAT가 좋은 선택일 수 있습니다.
- 정확한 충돌 정보의 즉각적인 필요: 충돌 여부와 동시에 충돌 법선, 관통 깊이가 바로 필요하고, 도형의 복잡도가 높지 않은 경우에 유리합니다.
6.2. 언제 GJK를 선택해야 할까요?
- 복잡한 3D 볼록 다면체: 수많은 정점을 가진 복잡한 3D 볼록 메쉬 간의 충돌 감지에 GJK가 SAT보다 훨씬 효율적입니다. 실제 게임 엔진에서는 대부분 GJK를 사용합니다.
- 다양한 형태의 볼록 도형 처리: 구, 캡슐, OBB 등 다양한 종류의 볼록 도형을 통합된 방식으로 처리해야 할 때 GJK의 범용성이 빛을 발합니다. 지지 함수만 구현하면 되기 때문입니다.
- 충돌 예측(Continuous Collision Detection, CCD): GJK는 두 도형 간의 최소 거리를 효율적으로 계산할 수 있으므로, 빠른 속도로 움직이는 오브젝트들의 충돌 예측에 활용될 수 있습니다.
- 성능 최적화: 대규모 3D 환경에서 수많은 오브젝트들의 충돌을 감지해야 할 때, GJK의 일관된 성능이 중요합니다. 물론 충돌 반응을 위한 EPA가 추가되지만, 전체적인 효율성에서 우위를 점할 수 있습니다.
실제 게임 엔진에서는 계층적 충돌 감지(Hierarchical Collision Detection) 방식을 많이 사용합니다. 넓은 단계에서는 AABB와 같은 간단한 바운딩 볼륨으로 빠르게 후보군을 걸러내고(브로드 페이즈), 충돌 가능성이 있는 오브젝트 쌍에 대해서만 SAT 또는 GJK와 같은 정교한 알고리즘을 적용하여 정확한 충돌 여부를 판단합니다(내로우 페이즈). 이처럼 여러 알고리즘을 조합하여 사용하는 것이 일반적입니다.
7. 마무리하며: 충돌 감지 알고리즘의 미래와 당신의 역할
지금까지 게임 물리 엔진의 핵심인 SAT와 GJK 충돌 감지 알고리즘의 수학적 원리와 내부 동작 방식을 깊이 있게 살펴보았습니다. 2D 환경에서 빛을 발하는 SAT의 직관적인 축 투영 방식부터, 3D 복잡 다면체에 효율적인 GJK의 민코프스키 차이와 심플렉스 기반 탐색, 그리고 GJK의 부족한 정보를 채워주는 EPA까지, 각 알고리즘이 어떻게 게임 속 오브젝트들의 상호작용을 가능하게 하는지 이해하셨기를 바랍니다.
이러한 알고리즘들은 단순히 이론적인 개념을 넘어, 여러분이 만들 게임의 현실감과 플레이 경험에 직접적인 영향을 미칩니다. 충돌 감지 알고리즘에 대한 깊이 있는 이해는 게임의 버그를 줄이고, 성능을 최적화하며, 더욱 견고하고 예측 가능한 물리 시스템을 구축하는 데 필수적인 역량입니다. 특히 실무 1~3년차 주니어 개발자로서, 단순히 API를 사용하는 것을 넘어 그 내부 동작 원리를 파악하려는 노력은 여러분을 한 단계 더 성장시키는 중요한 밑거름이 될 것입니다.
게임 물리 엔진 분야는 끊임없이 발전하고 있습니다. 더욱 복잡한 도형, 유체 역학, 천 역학 등 다양한 물리 현상을 현실적으로 시뮬레이션하기 위한 새로운 알고리즘과 최적화 기법들이 계속해서 연구되고 있습니다. 오늘 우리가 살펴본 SAT와 GJK는 이 거대한 여정의 중요한 이정표이며, 이들을 통해 얻은 지식은 여러분이 미래의 더욱 복잡한 문제들을 해결하는 데 큰 도움이 될 것입니다.
이 글이 여러분의 게임 개발 여정에 작은 불씨가 되기를 바라며, 앞으로도 물리 엔진의 흥미로운 세계를 탐험하며 멋진 게임을 만들어나가시길 응원합니다!
혹시 이 글에 대해 궁금한 점이나 추가하고 싶은 내용, 또는 여러분의 경험담이 있다면 언제든지 댓글로 공유해주세요. 함께 배우고 성장하는 개발 커뮤니티를 만들어가요!
📌 함께 읽으면 좋은 글
- [이슈 분석] 해커톤에서 MVP, 성공적인 결과물을 위한 핵심 전략은 무엇일까?
- [게임 개발] GDScript 성능 저하의 주범: 불필요한 GC 할당과 비효율적 데이터 구조, 이렇게 피하세요
- [모바일 앱 개발] 딥링크 오류 70% 감소! App Links/Universal Links로 모바일 앱 UX 혁신하기
이 글이 도움이 되셨다면 공감(♥)과 댓글로 응원해 주세요!
궁금한 점이나 다루었으면 하는 주제가 있다면 댓글로 남겨주세요.
'게임 개발' 카테고리의 다른 글
| 언리얼 엔진 GAS로 복잡한 캐릭터 스킬과 상태를 설계하는 모범 사례 활용법 (0) | 2026.07.30 |
|---|---|
| 게임 물리 시뮬레이션 중 강체 오브젝트가 떨리는 문제, 어떻게 해결해야 할까? (0) | 2026.07.30 |
| 게임이 밋밋하다고? Godot GLSL 셰이더로 마법을 부린 이야기 (0) | 2026.07.26 |
| 대규모 오브젝트 렌더링, Unity GPU Instancing과 SRP Batcher로 성능 최적화하는 법 (0) | 2026.07.24 |
| GDScript 성능 저하의 주범: 불필요한 GC 할당과 비효율적 데이터 구조, 이렇게 피하세요 (0) | 2026.07.23 |