Расстояние Гилберта-Джонсон-Keerthi алгоритм является методом определения минимального расстояния между двумя выпуклыми множествами . В отличие от многих других алгоритмов расстояния, он не требует, чтобы геометрические данные хранились в каком-либо конкретном формате, но вместо этого полагается исключительно на функцию поддержки для итеративного создания более близких симплексов к правильному ответу с использованием препятствия в пространстве конфигурации (CSO) двух выпуклых форм , более известная как разница Минковского .
Алгоритмы "Enhanced GJK" используют информацию о ребрах для ускорения алгоритма, отслеживая ребра при поиске следующего симплекса. Это существенно улучшает производительность многогранников с большим числом вершин.
GJK использует подалгоритм расстояния Джонсона, который вычисляет в общем случае точку тетраэдра, ближайшую к началу координат, но, как известно, страдает проблемами числовой устойчивости. В 2017 году Монтанари, Петринич и Барбьери предложили новый подалгоритм, основанный на подписанных объемах, который позволяет избежать умножения потенциально небольших количеств и достиг ускорения от 15% до 30%.
Алгоритмы GJK часто используются постепенно в системах моделирования и видеоиграх. В этом режиме последний симплекс из предыдущего решения используется в качестве начального предположения в следующей итерации, или «кадра». Если позиции в новом кадре близки к позициям в старом кадре, алгоритм сойдется за одну или две итерации. Это дает системы обнаружения столкновений, которые работают практически с постоянным временем.
Стабильность, скорость и небольшой объем памяти алгоритма делают его популярным для обнаружения столкновений в реальном времени , особенно в физических движках для видеоигр .
Обзор
GJK выполняет две функции:
- , который возвращает точку на фигуре с наибольшим скалярным произведением с.
- , который принимает симплекс s и возвращает симплекс на s, ближайшем к началу координат, и направление к началу координат, нормальное к новому симплексу. Если s сам содержит начало координат, NearestSimplex принимает s, и две фигуры определяются как пересекающиеся.
Каждый симплекс, обрабатываемый NearestSimplex, может быть любым симплексным подпространством R n . Например, в 3D они могут быть точкой, отрезком линии, треугольником или тетраэдром ; каждый определяется 1, 2, 3 или 4 баллами соответственно.
Псевдокод
функция GJK_intersection (форма p, форма q, начальная_ ось вектора): вектор A = Support (p, initial_axis) - Support (q, −initial_axis) симплекс s = {A} вектор D = −A цикл : A = Поддержка (p, D) - Поддержка (q, −D) если точка (A, D) <0: отклонять s = s ∪ A s, D, contains_origin: = Ближайший симплекс (ы) если contains_origin: принимать
Иллюстрация
Смотрите также
Внешние ссылки
- «Быстрая процедура вычисления расстояния между сложными объектами в трехмерном пространстве», Гилберт, Джонсон и Кирти - первая публикация
- «Вычисление расстояния между объектами», реализация GJK профессором Оксфорда Стивеном Кэмероном
- «Странный, но элегантный подход к удивительно сложной проблеме (алгоритм GJK)»
- 52-минутная видеолекция о реализации Гилберта-Джонсона-Кирти
- «Улучшение алгоритма GJK для более быстрых и надежных запросов о расстоянии между выпуклыми объектами» , Монтанари, Петриник и Барбьери.