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

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

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

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

ОписаниеПравить

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

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

$A+B=\{x+y:<!--\; :\; -->x\in <!--\; \in \; -->A,y\in <!--\; \in \; -->B\}.$$A+B=\{x+y\colon \;\;x\in A,\;y\in B\}.$ 

Это определение кажется неправильным, так как суммирование точек бессмысленно. В этом свободном замечании $x$$x$  и $y$$y$  пусть скорее будут восприняты как векторы $\stackrel{\to <!--\; \to \; -->}{x}=\mathbf{x}-<!--\; -\; -->\mathbf{o}$${\vec {x}}=\mathbf {x} -\mathbf {o}$ , где $\mathbf{o}$$\mathbf {o}$  является началом мировой системы координат.

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

$A\cap <!--\; \cap \; -->B\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}\equiv <!--\; \equiv \; -->0\in <!--\; \in \; -->A-<!--\; -\; -->B.$$A\cap B\neq \varnothing \equiv 0\in A-B.$ 

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

$d(A,B)=min\{\Vert <!--\; \Vert \; -->x\Vert <!--\; \Vert \; -->:<!--\; :\; -->x\in <!--\; \in \; -->A-<!--\; -\; -->B\}.$$d(A,\;B)=\min\{\|x\|\colon x\in A-B\}.$ 

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

$p(A,B)=inf\{\Vert <!--\; \Vert \; -->x\Vert <!--\; \Vert \; -->:<!--\; :\; -->x\in <!--\; \in \; -->A-<!--\; -\; -->B\}.$$p(A,\;B)=\inf\{\|x\|\colon x\in A-B\}.$ 

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

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

$S_A(v)\in <!--\; \in \; -->A\mid <!--\; \mid \; -->v\cdot <!--\; \cdot \; -->S_A(v)=max\{v\cdot <!--\; \cdot \; -->x:<!--\; :\; -->x\in <!--\; \in \; -->A\}.$$S_{A}(v)\in A\mid v\cdot S_{A}(v)=\max\{v\cdot x\colon x\in A\}.$ 

Разделяющая плоскость/ось (англ. Separating Plane/Axis): Дано два объекта $A$$A$  и $B$$B$ , плоскость $H(v,\mathrm{\delta <!--\; \delta \; -->})$$H(v,\;\delta )$ , которая разделяет $A$$A$  и $B$$B$ , если для каждой точки $a\in <!--\; \in \; -->A,v\cdot <!--\; \cdot \; -->a+\mathrm{\delta <!--\; \delta \; -->}⩾<!--\; ⩾\; -->0$$a\in A,\;v\cdot a+\delta \geqslant 0$  и для каждой точки $b\in <!--\; \in \; -->B,v\cdot <!--\; \cdot \; -->b+\mathrm{\delta <!--\; \delta \; -->}⩾<!--\; ⩾\; -->0$$b\in B,\;v\cdot b+\delta \geqslant 0$ . Вектор $v$$v$  известен как «слабо отделённая ось» (англ. weakly separating axis) для $A$$A$  и $B$$B$ , поскольку есть по крайней мере одна отделяющая плоскость, которая есть нормалью к нему, или, эквивалентно,

$v\cdot <!--\; \cdot \; -->S_A(-<!--\; -\; -->v)⩾<!--\; ⩾\; -->v\cdot <!--\; \cdot \; -->S_B(v).$$v\cdot S_{A}(-v)\geqslant v\cdot S_{B}(v).$ 

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

 

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

С другой стороны, если поиск был успешен, и потом объекты пересеклись, то для того, чтобы исполнить реакцию на столкновение и некоторые другие детали по отношению к столкновению, необходимы вычисления. Например, типичная схема, пытающаяся определить глубину проникновения, которая, в свою очередь, нуждается в поиске точки на границе CSO, которая будет ближайшей к началу системы координат. Ван ден Берген (англ. G. van den Bergen) предлагает расширенный алгоритм политопов для этого случая. Однако наша система вычисляет относительную информацию — ударную грань (англ. hit face), то есть ту грань на оболочке CSO, которая является ближайшей к началу системы координат. Анализируя вершины в этой грани, является возможным определить, какая составная часть объекта приняла участие в столкновении. Здесь различают два основных случая: столкновения типа «ребро-ребро» (англ. edge-edge) и столкновения типа «вершина-грань» (англ. vertex-face). Для того, чтобы понять, как идентифицируются составные части, заметим, что каждый из CSO соответствует паре векторов $(a_i,b_j),a_i\in <!--\; \in \; -->A,b_j\in <!--\; \in \; -->B$$(a_{i},\;b_{j}),\;a_{i}\in A,\;b_{j}\in B$ . Например, вершина выпуклого объекта $A$$A$  столкнулась с гранью выпуклого объекта $B$$B$ , которая характеризуется тем, что имеет все три вершины ударной грани, соответственные к той самой вершине объекта $A$$A$ , но к трём разным вершинам объекта $B$$B$ .

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

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

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

Внешние ссылкиПравить

• Gilbert, E. G., Johnson, D. W., Keerthi, S. S. A fast procedure for computing the distance between complex objectsin three-dimensional space (англ.). IEEE Xplore (апрель 1988). — первоначальная публикация Гилберта, Джонсона и Кирти. Дата обращения: 1 июля 2009. Архивировано 3 апреля 2012 года.
• Chong Jin Ong, Gilbert, E.G. The Gilbert-Johnson-Keerthi distance algorithm: a fast version forincremental motions (англ.) (недоступная ссылка — история). IEEE Xplore (20 апреля 1997). — Публикация усовершенствованного алгоритма. Дата обращения: 1 июля 2009.
• Computing the Distance between Objects (англ.). OXFORD UNIVERSITY COMPUTING LABORATORY. Дата обращения: 1 июля 2009. Архивировано 3 апреля 2012 года.
• gjkd — Двухмерная реализация алгоритма GJK, написанная на языке программирования D
• Shen-Po Shiang, Yu-Ren Chien, Jing-Sin Liu. On Enhancing GJK Algorithm for Distance Computation Between Convex Polyhedra: Comparison of Improvements (англ.). Institute of Information Science. Academia Cinica. Nankang, Taipei, Taiwan 11529 R.O.C. Дата обращения: 1 июля 2009. Архивировано 24 мая 2012 года.
• Александр Игоревич Синяков. Gilbert-Johnson-Keerthi алгоритм  (рус.). GameDev.ru (20 февраля 2006). — Математическое описание GJK. Дата обращения: 1 июля 2009.