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

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

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

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

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

Описание

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

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

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

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

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

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

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

$d(A,\;B)=\min\{\|x\|\colon x\in A-B\}.$

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

$p(A,\;B)=\inf\{\|x\|\colon x\in A-B\}.$

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. ↑ ^{1 2} Jatin Chhugani, Sergey Lyalin, Aleksey Bader, Teresa Morrison, Alexei Soupikov, Stephen Junkins, Pradeep Dubey, Mikhail Smelyanskiy Производительность игровой физики на архитектуре Larrabee (рус.). Intel Software Network (13 мая 2009 года (последнее изменение)). — Детальная статья, рассматривающая все аспекты и особенности реализации современной игровой физики, а также оптимизацию алгоритмов игровой физики под Intel Larrabee. Проверено 1 июля 2009.
2. ↑ ^{1 2 3 4 5 6 7 8} Yalmar Ponce Atencio 5.1 The GJK algorithm (англ.). lcg.ufrj.br (14 октября 2005 года). — Математическое описание GJK. Проверено 1 июля 2009.
3. ↑ Другими словами, два многогранника пересекаются только в том случае, если их разница Минковского содержит начало системы координат.
4. ↑ G. van den Bergen. «Efficient collision detection of complex deformable models using AABB trees.» J. Graph. Tools, 2(4):1-13, 1997.

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

• 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.
• Chong Jin Ong, Gilbert, E.G. The Gilbert-Johnson-Keerthi distance algorithm: a fast version forincremental motions (англ.). IEEE Xplore (20-25 апреля 1997 года). — Публикация усовершенствованного алгоритма. Проверено 1 июля 2009.
• Computing the Distance between Objects (англ.). OXFORD UNIVERSITY COMPUTING LABORATORY. Проверено 1 июля 2009.
• 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.
• Александр Игоревич Синяков Gilbert-Johnson-Keerthi алгоритм (рус.). GameDev.ru (20 февраля 2006 года). — Математическое описание GJK. Проверено 1 июля 2009.