길버트-존슨-케르티 거리 알고리즘

길버트-존슨-케르티 거리 알고리즘은 두 볼록 세트 사이의 최소 거리를 결정하는 방법이다.다른 많은 거리 알고리즘과는 달리, 그것은 기하학적 데이터를 특정한 형식으로 저장할 필요가 없고, 대신 두 개의 볼록형 모양의 구성 공간 장애물(CSO)을 사용하여 정답을 더 가깝게 단순하게 만들기 위해 지원 기능에만 의존한다(일반적으로 민코우스키 차이라고 더 잘 알려져 있다).

"향상된 GJK" 알고리즘은 에지 정보를 사용하여 다음 심플렉스(simplex)를 찾을 때 에지를 따라 알고리즘의 속도를 높인다.이것은 정점 수가 많은 폴리탑의 성능을 상당히 향상시킨다.

GJK는 존슨의 거리 하위 알고리즘을 활용하는데, 일반적인 경우 원점에 가장 근접한 사면체의 점을 계산하지만, 수치적 강건성 문제로 어려움을 겪는 것으로 알려져 있다.2017년 몬타나리, 페트리닉, 바비에리는 잠재적으로 소량의 곱셈을 피하고 15%~30%의 속도 상승을 달성하는 서명된 볼륨에 기반한 새로운 하위 알고리즘을 제안했다.

GJK 알고리즘은 시뮬레이션 시스템과 비디오 게임에서 점진적으로 사용되는 경우가 많다.이 모드에서는 다음 반복, 즉 "프레임"에서 초기 추측으로 이전 해법의 최종 심플렉스를 사용한다.새 프레임의 위치가 기존 프레임의 위치와 가까우면 알고리즘은 한두 번의 반복으로 수렴한다.이것은 거의 일정한 시간에 작동하는 충돌 감지 시스템을 산출한다.

알고리즘의 안정성, 속도 및 작은 저장 공간은 실시간 충돌 감지, 특히 비디오 게임용 물리 엔진에서 인기가 있다.

개요

GJK는 다음 두 가지 기능에 의존한다.

• ${\displaystyle }$$S{\displaystyle \stackrel{}{}}$u p ${\displaystyle \mathrm{p}}$ ${\displaystyle \mathrm{o}}$ ${\displaystyle \mathrm{t}}$(${\displaystyle s\mathrm{}}$ h ${\displaystyle \mathrm{a}}$ ${\displaystyle \mathrm{e},}$ ${\displaystyle d\stackrel{}{}}$→${\displaystyle }$) ${\displaystyle \mathrm {Support}(\mathrm {shape},{\vec$${d$$\})\},$ d → ${\d}$로 가장 높은 도트 제품을 가진 형상상의 점을 반환한다$.$
• ${\displaystyle \mathrm{N}}$ ${\displaystyle \mathrm{e}}$ a ${\displaystyle \mathrm{e}}$ a e ${\displaystyle \mathrm{s}}$ t ${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{i}}$ ${\displaystyle \mathrm{p}}$ l ${\displaystyle \mathrm{e}}$ ${\displaystyle \mathrm{x}(s}$ )$${\$displaystyle \mathrm {NewestSimplex} (s$ 이것은 심플렉스 s를 취하여 원점에 가장 가까운 s에 심플렉스(s)를 반환하고, 새로운 심플렉스(s)에 정상인 원점을 향한 방향을 반환한다.s 자체가 원점을 포함하는 경우, NearstSimplex는 s를 허용하고 두 모양이 교차하도록 결정된다.

NearstSimplex에서 처리하는 단순성은 각각 R의ⁿ 단순한 하위 공간일 수 있다.예를 들어, 3D에서는 점, 선 세그먼트, 삼각형 또는 사면체일 수 있다. 각각 1, 2, 3 또는 4개의 점으로 정의된다.

가성음

함수 GJK_intersection(shape p, shape q, vector initial_axis): 벡터 A = Support(p, initial_axis) - Simplex s = {A}벡터 D = -A 루프:A = Support(p, D) - Support(q, -D) 도트(A, D) > 0: reject s = s ∪ A s, D, include_orgin := NearstSimplex(s: include_gin: accept)

삽화

참고 항목

• 민코프스키 포털 정교화

외부 링크

• "3차원 공간에서 복잡한 물체 사이의 거리를 계산하는 빠른 절차", Gilbert, Johnson, Keerthi - 초간 출판물
• 스티븐 캐머런 옥스퍼드 교수의 GJK 구현 '물체 간 거리 계산'
• "놀라울 정도로 어려운 문제에 대한 낯설지만 우아한 접근법"
• Gilbert-Johnson-Keerthi 구현에 대한 52분 비디오 강의
• 몬타나리, 페트리닉, 바비에리 등 "볼록사물 간 보다 빠르고 안정적인 거리 조회를 위한 GJK 알고리즘 개선"