Алгоритм Гилберта — Джонсона — Кирти

Алгоритм Гилберта — Джонсона — Кирти (Шаблон:Lang-en, сокращённо GJK) — алгоритм для определения расстояния между двумя выпуклыми множествами (объектами). В отличие от многих других алгоритмов нахождения расстояния, GJK не требует, чтобы геометрические данные были сохранены в каком-либо специфическом формате. Вместо этого алгоритм GJK полностью полагается на носитель функции и итерационным методом (с помощью итераций) генерирует ближайшие симплексы для корректного определения расстояния между двумя выпуклыми объектами. При этом алгоритм GJK в своей работе использует понятия суммы Минковского для двух выпуклых форм.

В случае нахождения расстояния между двумя невыпуклыми объектами можно:

1. разбить невыпуклый объект на несколько выпуклых и затем применить метод для образовавшихся выпуклых объектов;
2. представить геометрию как триангулярную поверхность и использовать общий алгоритм столкновения триангулярных сеток (Шаблон:Lang-en), что опять включает использование алгоритма столкновений выпуклых объектов.

Описание

Алгоритм Гилберта — Джонсона — Кирти предоставляет довольно эффективный метод обнаружения столкновений между выпуклыми объектами. Он полагается на несколько ключевых моментов, которые кратко выделены ниже:

Сумма Минковского: Имеется два множества $A$ и $B$, их сумма Минковского определяется как:

$A+B=\{x+y:x\in A,y\in B\}.$

Это определение кажется неправильным, так как суммирование точек бессмысленно. В этом свободном замечании $x$ и $y$ пусть скорее будут восприняты как векторы $\overrightarrow{x}=𝐱-𝐨$, где $𝐨$ является началом мировой системы координат.

Конфигурационное пространство препятствий (Шаблон:Lang-en — CSO). Для пары $(A,B)$ выпуклых объектов их CSO будет дано $A-B$, то есть сумма Минковского от $A$ и $-B$. Этот набор особенно полезный в определениях столкновений, так как можно доказать, что $A$ и $B$ пересекаются тогда и только тогда, когда их CSO содержат начало системы координат:

$A\cap B\ne \varnothing \equiv 0\in A-B.$

Кроме того, их дистанция даётся:

$d(A,B)=\min \{\Vert x\Vert :x\in A-B\}.$

Подобным образом глубина проникновения пар объектов может быть выраженная в терминах их CSO как:

$p(A,B)=\inf \{\Vert x\Vert :x\in A-B\}.$

Для пары пересекающихся объектов глубина проникновения реализуется точкой на границе $A-B$, которая наиболее близка к началу системы координат.

Support Mapping. Support Mapping $S_A(v)$ является функцией, которая принимает вектор $v$ и выпуклое множество $A$, возвращает наиболее «экстремальную» точку для выпуклого объекта $A$ в этом направлении (направлении вектора $v$). Формально говоря:

$S_A(v)\in A\mid v\cdot S_A(v)=\max \{v\cdot x:x\in A\}.$

Разделяющая плоскость/ось (Шаблон:Lang-en): Дано два объекта $A$ и $B$, плоскость $H(v,\delta )$, которая разделяет $A$ и $B$, если для каждой точки $a\in A,v\cdot a+\delta ⩾0$ и для каждой точки $b\in B,v\cdot b+\delta ⩾0$. Вектор $v$ известен как «слабо отделённая ось» (Шаблон:Lang-en) для $A$ и $B$, поскольку есть по крайней мере одна отделяющая плоскость, которая есть нормалью к нему, или, эквивалентно,

$v\cdot S_A(-v)⩾v\cdot S_B(v).$

Общая идея алгоритма GJK состоит в изучении конфигурационного пространства препятствий (CSO) для двух данных объектов $A$ и $B$, ища симплекс, который содержит начало системы координат. Если поиск заканчивается с отрицательным ответом, то есть начало системы координат лежит вне CSO, то тогда объекты не пересекаются. В этом случае точка из CSO, которая является ближайшей к началу системы координат, представляет разделяющую ось $A$ и $B$, и это, в свою очередь, может использоваться как отправная точка для тестирования столкновений в последующих итерациях.

Два типа столкновений и соответствующих им CSO-граней: грань-вершина (сверху) и ребро-ребро (снизу)

С другой стороны, если поиск был успешен, и потом объекты пересеклись, то для того, чтобы исполнить реакцию на столкновение и некоторые другие детали по отношению к столкновению, необходимы вычисления. Например, типичная схема, пытающаяся определить глубину проникновения, которая, в свою очередь, нуждается в поиске точки на границе CSO, которая будет ближайшей к началу системы координат. Ван ден Берген (Шаблон:Lang-en) предлагает расширенный алгоритм политопов для этого случая. Однако наша система вычисляет относительную информацию — ударную грань (Шаблон:Lang-en), то есть ту грань на оболочке CSO, которая является ближайшей к началу системы координат. Анализируя вершины в этой грани, является возможным определить, какая составная часть объекта приняла участие в столкновении. Здесь различают два основных случая: столкновения типа «ребро-ребро» (Шаблон:Lang-en) и столкновения типа «вершина-грань» (Шаблон:Lang-en). Для того, чтобы понять, как идентифицируются составные части, заметим, что каждый из CSO соответствует паре векторов $(a_i,b_j),a_i\in A,b_j\in B$. Например, вершина выпуклого объекта $A$ столкнулась с гранью выпуклого объекта $B$, которая характеризуется тем, что имеет все три вершины ударной грани, соответственные к той самой вершине объекта $A$, но к трём разным вершинам объекта $B$.

Использование

Алгоритм GJK часто используется в системах моделирования, компьютерной анимации и компьютерных играх. В этом режиме при расчёте финальный (выходной, результирующий) симплекс из предыдущей итерации используется как начальные данные в следующей итерации (фрейме, кадре). Если позиция в новом фрейме близка к аналогичной позиции в старом фрейме, то алгоритм будет сходиться в одной или в двух итерациях.

Стабильность, скорость и занимаемый объём памяти алгоритма сделали его популярным в обнаружениях столкновений в реальном времени, особенно в физических движках для компьютерных игр.

Внешние ссылки

• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• gjkd — Двухмерная реализация алгоритма GJK, написанная на языке программирования D
• Шаблон:Cite web
• Шаблон:Cite web