Алгоритм GJK¶

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

¶История

Алгоритм был предложен в 1988 году американскими учёными Элмером Гилбертом, Дэниелом Джонсоном и Сридхаром Кирти в статье «A fast procedure for computing the distance between complex objects in three-dimensional space» (опубликована в журнале IEEE Journal on Robotics and Automation). Разработка была мотивирована потребностью в быстром обнаружении столкновений в системах управления роботами. В отличие от более ранних методов, основанных на переборе граней или вершин, GJK использует концепцию опорных функций и симплексов, что позволяет работать с объектами, заданными не только полигональными сетками, но и аналитическими функциями (например, сферами, эллипсоидами, цилиндрами).

¶Основные понятия

¶Выпуклое множество

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

¶Опорная функция

Опорная функция (support function) — это функция, которая для заданного направления d возвращает точку множества, наиболее удалённую в этом направлении. Для выпуклого многогранника опорная точка обычно находится среди его вершин. Для аналитически заданных тел (например, сферы) опорная точка вычисляется по формуле:

• Сфера радиуса r с центром c: support(d) = c + r * d / |d|.
• Эллипсоид: support(d) = c + R d / |R d|, где R — матрица преобразования.

¶Разность Минковского

Центральная идея GJK — сведение задачи пересечения двух множеств A и B к задаче принадлежности начала координат разности Минковского A ⊖ B = {a - b | a ∈ A, b ∈ B}. Два множества пересекаются тогда и только тогда, когда начало координат (0,0,0) принадлежит A ⊖ B. Алгоритм не строит разность Минковского явно, а использует опорные функции для поиска точек на её границе.

¶Симплекс

Симплекс — это геометрическая фигура, являющаяся обобщением треугольника на произвольную размерность:

• 0-симплекс — точка,
• 1-симплекс — отрезок,
• 2-симплекс — треугольник,
• 3-симплекс — тетраэдр.

В GJK симплекс используется как текущее приближение множества A ⊖ B. Алгоритм итеративно строит симплекс, содержащий точки из разности Минковского, и проверяет, может ли начало координат находиться внутри этого симплекса.

¶Алгоритм

¶Инициализация

Выбирается начальное направление поиска d (например, произвольный ненулевой вектор). Вычисляется первая точка p0 = support_A(d) - support_B(-d). Симплекс инициализируется этой точкой.

¶Основная итерация

1. Вычисление опорной точки: Для текущего направления d вычисляется новая точка p = support_A(d) - support_B(-d).
2. Проверка на пересечение: Если p не находится дальше в направлении d, чем начало координат (т.е. dot(p, d) < 0), то начало координат не может быть достигнуто, и алгоритм завершается с результатом «нет пересечения».
3. Добавление точки: Точка p добавляется к симплексу.
4. Поиск ближайшего симплекса: Из текущего симплекса выбирается подмножество (подсимплекс), которое содержит точку, ближайшую к началу координат. Остальные точки отбрасываются.
5. Обновление направления: Направление d устанавливается как вектор от ближайшей точки подсимплекса к началу координат.
6. Проверка сходимости: Если ближайшая точка совпадает с началом координат (с заданной точностью), то алгоритм завершается с результатом «пересечение». Иначе — переход к шагу 1.

¶Критерий остановки

Алгоритм сходится за конечное число шагов, так как на каждой итерации симплекс приближается к началу координат. Для выпуклых многогранников с числом вершин n число итераций не превышает n+1 в худшем случае. На практике для трёхмерных объектов достаточно 3–6 итераций.

¶Вычисление минимального расстояния

Если алгоритм завершился с результатом «нет пересечения», то расстояние от начала координат до ближайшей точки симплекса равно минимальному расстоянию между множествами A и B. Ближайшие точки на границах A и B восстанавливаются по координатам точек симплекса и опорным функциям.

¶Применение

¶Обнаружение коллизий в физических движках

GJK является основным алгоритмом для проверки пересечения выпуклых тел в таких движках, как Bullet, PhysX, Havok, Box2D и других. Он используется для определения момента контакта между объектами в симуляциях твёрдых тел, автомобильных симуляторах, компьютерных играх.

¶Робототехника

В планировании движений и управлении манипуляторами GJK применяется для проверки столкновений робота с препятствиями, а также для вычисления расстояния до препятствий с целью избегания контакта.

¶Вычислительная геометрия

Алгоритм используется для решения задач о ближайших точках, проверки принадлежности точки выпуклому многограннику, а также в алгоритмах триангуляции и построения выпуклых оболочек.

¶Преимущества и недостатки

¶Преимущества

• Высокая скорость: Линейная сложность по числу вершин в типичных случаях.
• Простота реализации: Не требует сложных структур данных, достаточно опорной функции.
• Универсальность: Работает с любыми выпуклыми множествами, заданными аналитически или полигонально.
• Точность: Позволяет вычислять минимальное расстояние с произвольной точностью.

¶Недостатки

• Требование выпуклости: Неприменим напрямую к невыпуклым объектам без декомпозиции.
• Чувствительность к вырожденным случаям: При работе с очень тонкими или плоскими объектами может возникать численная неустойчивость.
• Необходимость опорной функции: Для сложных объектов (например, с закруглениями) требуется точное аналитическое описание или аппроксимация.

¶Варианты и расширения

¶EPA (Expanding Polytope Algorithm)

EPA — расширение GJK для вычисления глубины проникновения (penetration depth) при пересечении объектов. После обнаружения пересечения GJK строит симплекс, содержащий начало координат, а EPA итеративно расширяет его до полного многогранника, чтобы найти точку на границе разности Минковского, ближайшую к началу координат. Это позволяет определить направление и силу контакта для физической симуляции.

¶GJK для невыпуклых объектов

Для невыпуклых объектов GJK применяется после разбиения на выпуклые части (например, с помощью алгоритма выпуклой декомпозиции). Затем проверка пересечения выполняется для каждой пары выпуклых частей.

¶Параллельная реализация

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

¶Интересные факты

• Алгоритм GJK был назван в честь первых букв фамилий авторов, но также иногда упоминается как «алгоритм Гилберта — Джонсона — Кирти».
• В 1999 году Элмер Гилберт получил премию IEEE Robotics and Automation Award за вклад в развитие робототехники, включая создание GJK.
• GJK является одним из немногих алгоритмов, которые одновременно решают задачу пересечения и задачу минимального расстояния без дополнительных затрат.

¶Источники

• Gilbert, E. G., Johnson, D. W., & Keerthi, S. S. (1988). «A fast procedure for computing the distance between complex objects in three-dimensional space». IEEE Journal on Robotics and Automation.
• Van den Bergen, G. (2003). «Collision Detection in Interactive 3D Environments». Morgan Kaufmann.
• Ericson, C. (2005). «Real-Time Collision Detection». CRC Press.
• Документация физического движка Bullet Physics SDK.