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

Алгоритм расстояния Гилберта-Джонсона-Кирти , Дэниелом В. Джонсоном и С. Сатьей Кирти в 1988 году. В отличие от многих других алгоритмов — это метод определения минимального расстояния между двумя выпуклыми множествами , впервые опубликованный Элмером Г. Гилбертом расстояния, он не требует хранения геометрических данных в каком-либо конкретном формате, а вместо этого полагается исключительно на вспомогательную функцию для итеративного создания симплексов, более близких к правильному ответу, с использованием препятствия конфигурационного пространства (CSO) из двух выпуклых форм, более известного как разница Минковского. .

Алгоритмы «Улучшенный GJK» используют информацию о краях для ускорения работы алгоритма, следуя по краям при поиске следующего симплекса. Это существенно повышает производительность для многогранников с большим количеством вершин.

GJK использует подалгоритм расстояния Джонсона, который в общем случае вычисляет точку тетраэдра, ближайшую к началу координат, но, как известно, страдает от проблем с численной устойчивостью. В 2017 году Монтанари, Петринич и Барбьери предложили новый подалгоритм, основанный на знаковых объемах, который позволяет избежать умножения потенциально небольших количеств и обеспечивает ускорение от 15% до 30%.

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

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

Обзор

GJK выполняет две функции:

$\mathrm {Support} (\mathrm {shape} ,{\vec {d}})$ , который возвращает точку на $фигуре$ , имеющую наибольшее скалярное произведение с ${\vec {d}}$ .
$\mathrm {NearestSimplex} (s)$ , который принимает симплекс $s$ и возвращает симплекс $s,$ ближайший к началу координат, а также направление к началу координат, нормальное к новому симплексу. Если $s$ само содержит начало координат, $NearestSimplex$ принимает $s$ , и две фигуры определяются как пересекающиеся.

Каждый симплекс, обрабатываемый $NearestSimplex$ , может быть любым симплексным подпространством $R. н$ . Например, в 3D это могут быть точка, отрезок, треугольник или тетраэдр ; каждый определяется 1, 2, 3 или 4 баллами соответственно.

Псевдокод

function GJK_intersection(shape p, shape q, vector initial_axis):
    vector  A = Support(p, initial_axis) − Support(q, −initial_axis)
    simplex s = {A}
    vector  D = −A

    loop:
        A = Support(p, D) − Support(q, −D)
        if dot(A, D) < 0:
            reject
        s = s ∪ {A}
        s, D, contains_origin := NearestSimplex(s)
        if contains_origin:
            accept

Иллюстрация

См. также

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

«Быстрая процедура вычисления расстояния между сложными объектами в трехмерном пространстве», Гилберт, Джонсон и Кирти — первая публикация.
«Вычисление расстояния между объектами», реализация GJK профессором Оксфорда Стивеном Кэмероном.
«Странный, но элегантный подход к удивительно сложной проблеме (алгоритм GJK)»
52-минутная видеолекция по внедрению Гилберта-Джонсона-Кирти
«Улучшение алгоритма GJK для более быстрых и надежных запросов расстояния между выпуклыми объектами» , Монтанари, Петринич и Барбьери.
«Ускоренное обнаружение столкновений: перспектива оптимизации» , Монто, Ле Лидек, Петрик, Сивич и Карпентье. В этой исследовательской статье, в частности, показано, как можно ускорить оригинальный алгоритм GJK, используя стратегии ускорения типа Нестерова, что способствует снижению общей вычислительной сложности GJK.
«Алгоритм Гилберта-Джонсона-Кирти объяснен максимально просто»

Эта прикладной математике, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .