# GJK (Gilbert-Johnson-Keerthi) 알고리즘

### 개요

GJK 알고리즘은 Convex Hull의 충돌을 판단하는 데 사용되는 효율적인 알고리즘이다. Gilbert, Johnson, Keerthi에 의해 1988년에 개발되었으며, 두 볼록 집합 사이의 최소 거리 또는 충돌 여부를 계산하는 데 초점을 맞추고 있다. 이 알고리즘은 주로 실시간 충돌 감지 시스템에서 많이 사용된다.

### 주요 개념

#### Minkowski Difference

GJK 알고리즘의 핵심 개념 중 하나는 Minkowski Difference이다. 두 볼록 집합 $\mathbf{A}$와 $\mathbf{B}$가 주어질 때, Minkowski Difference $\mathbf{C}$는 다음과 같이 정의된다:

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

이 $\mathbf{C}$는 원점(0,0,0)을 포함하는지 여부로 두 집합의 충돌 여부를 확인할 수 있다.

#### Support Function

GJK 알고리즘에서 또 다른 중요한 개념은 Support Function이다. 한 방향 $\mathbf{d}$에 대한 Support Function $S(\mathbf{A}, \mathbf{d})$는 집합 $\mathbf{A}$ 내 최종 지점을 반환한다:

$$
S(\mathbf{A}, \mathbf{d}) = \text{argmax}\_{\mathbf{a} \in \mathbf{A}} (\mathbf{a} \cdot \mathbf{d})
$$

Support Function $S$는 주어진 방향 $\mathbf{d}$에 대해 가장 먼 지점을 찾는 기능을 한다.

### 알고리즘 단계

#### Initial Setup

1. 두 볼록 집합 $\mathbf{A}$와 $\mathbf{B}$의 초기 방향 벡터 $\mathbf{d}$를 설정한다. 일반적으로 초기 $\mathbf{d}$는 임의의 벡터로 설정된다.
2. Support Function을 사용하여 $\mathbf{A}$와 $\mathbf{B}$ 각각에서 $\mathbf{d}$ 방향으로 가장 먼 점을 찾는다.
3. 이 점들의 차이 $\mathbf{p\_0} = S(\mathbf{A}, \mathbf{d}) - S(\mathbf{B}, -\mathbf{d})$를 계산한다.

#### Iterative Process

1. 새로운 방향 벡터 $\mathbf{d}$는 원점에서 가장 가까운 단순 단추(Simplices)를 찾기 위해 변경된다.
2. 현재 Simplices 내의 최상단 벡터가 원점을 포함하는지 확인한다.
3. 포함하지 않는다면, 새로운 지점 $S(\mathbf{P}, \mathbf{d})$을 추가한다.
4. 이 과정을 원점이 Simplices에 포함되거나 유효한 Simplices가 더 이상 존재하지 않을 때까지 반복한다.

#### Convergence and Termination

* 값이 수렴하여 원점이 포함되면 두 집합이 충돌했다고 간주한다.
* 원점이 포함되지 않도록 하는 최대 반복 횟수 조건을 도입할 수 있으며, 이 경우 두 집합이 충돌하지 않았음을 뜻한다.

### 수학적 설명

#### Support Points

Minkowski Difference와 함께 사용될 수학적 식은 아래와 같다:

$$
\mathbf{p} = S(\mathbf{A}, \mathbf{d}) - S(\mathbf{B}, -\mathbf{d})
$$

Wake-splitting 조건을 계산하여 새로운 방향 벡터 $\mathbf{d}$를 설정한다:

$$
\mathbf{d} = - \mathbf{p}
$$

이 과정을 통해 충돌 여부를 판단한다.

#### Simplex Update

알고리즘 진행 과정에서 단순 단추(Simplex)를 업데이트한다:

$$
\mathbf{d} = \mathbf{\Delta}(\mathbf{p\_n}, \mathbf{p\_{n-1}}, \ldots, \mathbf{p\_1})
$$

반복적 Refresh 과정에서 단순 단추를 고려하여 정확한 방향 벡터를 도출해낸다.

#### Convex Hull Optimization

GJK 알고리즘이 다양한 자료구조를 사용하여 Convex Hull을 최적화하는 방법도 있다. 이 방법들은 알고리즘의 성능과 정확성을 증가시키는 데 도움을 준다.

### 성능 최적화 기법

#### Caching and Memoization

동일한 Support Function 계산이 반복적으로 발생하는 것을 피하기 위해, 이전에 계산된 Support Point를 저장하는 캐시를 사용할 수 있다. 이를 통해 중복된 계산을 방지하고 성능을 크게 향상시킬 수 있다.

#### Spatial Partitioning

공간 분할 기법은 그리드, 옥트리, BSP 트리와 같은 자료구조를 사용하여 충돌 영역을 세분화한다. 이를 통해 불필요한 충돌 체크를 피하고 효율성을 높일 수 있다.

#### Incremental Updates

연속적인 프레임 또는 시뮬레이션 단계에서 충돌 객체의 위치 변화가 적거나 미미한 경우, 이전 상태의 정보를 활용하여 새로운 충돌 결과를 빠르게 계산할 수 있다. 이는 특히 실시간 물리 엔진에서 중요한 성능 최적화 기술이다.

#### Parallel Processing

병렬 처리 기법을 적용해 복수의 충돌 체크를 동시에 수행함으로써 성능을 향상시킬 수 있다. GPU 컴퓨팅이나 멀티스레드 프로세싱을 활용할 수 있다.

### GJK 알고리즘의 응용

#### 게임 엔진

GJK 알고리즘은 다양한 상용 게임 엔진에서 사용되며, 실시간 물리 시뮬레이션과 충돌 감지에 매우 적합한다. Unity, Unreal Engine 등은 GJK 알고리즘을 활용하여 높은 성능을 발휘한다.

#### 로봇 공학

로봇의 움직임 경로를 계획하는 데 있어 GJK 알고리즘을 활용해 충돌 회피 경로를 계산할 수 있다. 이는 로봇이 복잡한 환경에서 원활하게 동작하도록 도와준다.

#### 가상 현실과 증강 현실

VR 및 AR 환경에서는 실제 세계와 가상 객체 간의 충돌을 실시간으로 감지해야 한다. GJK 알고리즘은 이러한 상황에서 유용하게 활용될 수 있다.

***

GJK 알고리즘은 단순하면서도 매우 강력한 충돌 감지 알고리즘이다. 효율적인 성능과 높은 정확성을 제공하며, 다양한 최적화 기법을 통해 더 빠르고 정확한 계산이 가능한다. 이를 통해 게임 엔진, 로봇 공학, 가상 현실 등 다양한 분야에서 큰 효과를 발휘할 수 있다.