Алгоритм Гилберта — Джонсона — Кёрти (англ. Gilbert — Johnson — Keerthi algorithm, сокращённо GJK) — алгоритм для определения минимального расстояния между двумя выпуклыми множествами (объектами). В отличие от многих других алгоритмов нахождения расстояния, GJK не требует, чтобы геометрические данные были сохранены в каком-либо специфическом формате. Вместо этого алгоритм GJK полностью полагается на носитель функции и итерационным методом (с помощью итераций) генерирует ближайшие симплексы для корректного определения минимального расстояния между двумя выпуклыми объектами. При этом алгоритм GJK в своей работе использует понятия суммы Минковского для двух выпуклых форм.
В случае нахождения минимального расстояния между двумя невыпуклыми объектами можно:[1]
Алгоритм Гилберта — Джонсона — Кёрти предоставляет довольно эффективный метод обнаружения столкновений между выпуклыми объектами. Он полагается на несколько ключевых моментов, которые кратко выделены ниже:[2]
Сумма Минковского: Имеется два множества и , их сумма Минковского определяется как:[2]
Это определение кажется неправильным, так как суммирование точек бессмысленно. В этом свободном замечании и пусть скорее будут восприняты как векторы , где является началом мировой системы координат.[2]
Конфигурационное пространство препятствий (англ. Configuration Space Obstacle — CSO). Для пары выпуклых объектов их CSO будет дано , то есть сумма Минковского от и . Этот набор особенно полезный в определениях столкновений, так как можно доказать, что и пересекаются тогда и только тогда, когда их CSO содержат начало системы координат:[2]
Кроме того, их дистанция даётся:
Подобным образом глубина проникновения пар объектов может быть выраженная в терминах их CSO как:[2]
Для пары пересекающихся объектов глубина проникновения реализуется точкой на границе , которая наиболее близка к началу системы координат.
Support Mapping. Support Mapping является функцией, которая принимает вектор и выпуклое множество , возвращает наиболее «экстремальную» точку для выпуклого объекта в этом направлении (направлении вектора ). Формально говоря:[2]
Разделяющая плоскость/ось (англ. Separating Plane/Axis): Дано два объекта и , плоскость , которая разделяет и , если для каждой точки и для каждой точки . Вектор известен как «слабо отделённая ось» (англ. weakly separating axis) для и , поскольку есть по крайней мере одна отделяющая плоскость, которая есть нормалью к нему, или, эквивалентно,
Общая идея алгоритма GJK состоит в изучении конфигурационного пространства препятствий (CSO) для двух данных объектов и , ища симплекс, который содержит начало системы координат. Если поиск заканчивается с отрицательным ответом, то есть начало системы координат лежит вне CSO, то тогда объекты не пересекаются.[3] В этом случае точка из CSO, которая является ближайшей к началу системы координат, представляет разделяющую ось и , и это, в свою очередь, может использоваться как отправная точка для тестирования столкновений в последующих итерациях.[2]
С другой стороны, если поиск был успешен, и потом объекты пересеклись, то для того, чтобы исполнить реакцию на столкновение и некоторые другие детали по отношению к столкновению, необходимы вычисления. Например, типичная схема, пытающаяся определить глубину проникновения, которая, в свою очередь, нуждается в поиске точки на границе CSO, которая будет ближайшей к началу системы координат. Ван ден Берген (англ. G. van den Bergen) [4] предлагает расширенный алгоритм политопов для этого случая. Однако наша система вычисляет относительную информацию — ударную грань (англ. hit face), то есть ту грань на оболочке CSO, которая является ближайшей к началу системы координат. Анализируя вершины в этой грани, является возможным определить, какая составная часть объекта приняла участие в столкновении. Здесь различают два основных случая: столкновения типа «ребро-ребро» (англ. edge-edge) и столкновения типа «вершина-грань» (англ. vertex-face). Для того, чтобы понять, как идентифицируются составные части, заметим, что каждый из CSO соответствует паре векторов . Например, вершина выпуклого объекта столкнулась с гранью выпуклого объекта , которая характеризуется тем, что имеет все три вершины ударной грани, соответственные к той самой вершине объекта , но к трём разным вершинам объекта .[2]
Алгоритм GJK часто используется в системах моделирования, компьютерной анимации и компьютерных играх. В этом режиме при расчёте финальный (выходной, результирующий) симплекс из предыдущей итерации используется как начальные данные в следующей итерации (фрейме, кадре). Если позиция в новом фрейме близка к аналогичной позиции в старом фрейме, то алгоритм будет сходиться в одной или в двух итерациях.
Стабильность, скорость и занимаемый объём памяти алгоритма сделали его популярным в обнаружениях столкновений в реальном времени, особенно в физических движках для компьютерных игр.[1]
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .