개요

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