Разработка физики для игр
GameDev.ru / Сообщества / Физика для игр / Статьи / Gilbert-Johnson-Keerthi алгоритм.

Gilbert-Johnson-Keerthi алгоритм.

Автор:

Данная статья создана на основе лекции http://www.gamedev.ru/community/gamedev_lecture/articles/?id=16

Сума Минковского  двух множеств A и B в Евклидовом пространстве это результат сложения каждого элемента A с каждым элементом B: A+B={a+b|a принадлежит A, b принадлежит B}.
Пример:

Сума
A={(-3,1), (-3,2), (-1,1)} и B=={(0,0), (2,0), (0,2),(2,2)}, тогда A+B ={(-3,1),(-3,4),(-1,4),(1,3),(1,1)}

Разница
A={(0,2), (0,3), (2,2)} и B=={(1,1), (3,1), (3,4),(1,4)}, тогда A-B ={(-1,-1),(-1,2),(3,2),(3,-2),(1,-2)}

Графический пример сумы Минковского (рис 1) и разницы Минковского(рис 2):
Изображение
    GJK использует тот факт, что два многогранника пересекаются только в том случае, если их разница Минковского C = A-B содержит начало системы координат. В действительности, возможно получить еще полезнее результат - посчитать минимальное расстояние между A и B, что эквивалентно вычислению минимального расстояния между C и началом системы координат. Т.е. distance(A,B) = min{||a-b|| : a принадлежит A, b принадлежит B} = min{||c|| : c принадлежит A - B}.  Еще важное замечание, разницу Минковского двух объектов иногда называют TCSO (translation configuration space obstacle).
Вообще говоря, посчитать разницу Минковского на каждой итерации алгоритма довольно тяжело, поэтому в GJK используется support mapping. Это функция которая в заданном направлении d отображает экстремальную точку для выпуклого объекта A в этом направлении. Например, для сферы, которая находится в O, с радиусом r, support mapping имеет вид:
Sc = O+rd/||d||
Изображение
P – экстремальная точка.
Или для box: Sc(d) = (sgn(x)d_x, sgn(y)d_y, sgn(z)d_z).
Для сложных фигур используется алгоритм hill climbing. О нем будет рассказано далее.

    Support mapping для двух объектов Разницы Минковского A и B можно переписать следующим образом:
S(A-B) = SA(d)-SB(-d)
Откуда следует, что точки разницы Минковского могут быть вычислены из экстремальных точек отдельных многогранников A и B. Для того что бы найти разницу Минковского С для точки ближайшей к началу системы координат, GJK использует Caratheodory’s Theorem:
Для выпуклого тела H (R^d), каждая точка из H может быть выражена как выпуклая комбинация не более чем d+1 точек из H. Подробнее и с примером http://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_%28convex_hull%29. Если начало координат содержится в текущем симплексе, A и B пересекаются и алгоритм прекращает свою работу. Иначе, множество Q обновляется таким образом, что новый симплекс, гарантировано будет содержать точки ближайшее к началу системы координат, чем предыдущий симплекс.

Классический псевдокод:

while not best_simplex(S) do
S<-refine_features(S);
endwhile

В случае когда A и B не пересекаются, наименьшее расстояние между A и B находится с помощью точки минимальной нормы в CH(Q) (convex hull Q).

Общий алгоритм таков:
1. Инициализируем симплекс Q d+1 точками из разницы Минковского A и B.
2. Вычисляем точку минимальной нормы P в CH(Q).
3. Если P и есть начало координат, то начало координат содержится в разнице Минковского A и B. Останавливаемся и возвращаем, что A и B пересекаются.
4. Уменьшаем Q до подмножества Q’, такого что P принадлежит CH(Q’).
5. Пусть V = Sa-b(-P)=Sa(-P)-Sb(P) будет экстремальной точкой в направлении P.
6. Если V не является экстремальной точкой в направлении P, тогда возвращаем, что A и B не пересекаются. Длина вектора от начала координат к P это разделяющее расстояние от A до B.
7. Добавляем V в Q и переходим на шаг 2.

Пример:
Изображение
Алгоритм начинает с вершины A и инициализирует множество Q = {A}. Для начальной вершины, ближняя вершина и есть сама вершина. Это пункт два алгоритма. Экстремальной вершиной для вершины A будет вершина B, следовательно добавляем в множество: Q = {A,B}. Точка в CH(Q) ближайшая к началу системы координат это C. Поскольку обе вершины A и B необходимо выразить C как выпуклую комбинацию, обе остаются в Q. D это экстремальная вершина в направлении C, поэтому Q = {A,B,D}. Точка в CH(Q) ближайшая к началу системы координат теперь E. Поскольку только через B и D можно выразить как выпуклою комбинацию вершин в Q, то Q = {B,D}. Экстремальная вершина в направлении E это F, которая добавляется в Q. Точка в CH(Q) ближайшая к началу системы координат теперь G. Поскольку, теперь хватает D и F  что бы выразить G как выпуклою комбинацию, => Q = {D,F}. И завершающая стадия алгоритма: поскольку нет  вершин лежащих ближе всего к началу системы координат в направлении G, то G и является ближайшей точкой к центру и алгоритм прекращает свою работу.

Hill Climbing для экстремальных вершин.
Экстремальные вершины могут быть найдены за O(n) перебором всех n вершин.
Еще лучше хранить информацию о соседних вершинах для каждой вершины,
тогда эту экстремальную вершину можно найти обычным Hill Climbing алгоритмом.
Из текущей вершины V, соседние вершины Vi будут проверятся пока некоторая вершина Vj будет найдена более экстремальной в заданном направлении чем V. Тогда Vj становится текущей вершиной и процесс повторяется.

Пример:
Изображение
В примере текущая вершина V, у которой соседние вершины V0,V1 и V2.
V0 более экстремальна чем V в направлении d, потому что (V0 – V)d>0 и поэтому становится текущей вершиной. Далее по аналогии: V5 более экстремальна чем V0 и V4, затем V6, затем V7 и, собственно экстремальная вершина V8.

Для огромных многогранников, Hill Climbing можно ускорить добавлением одной или более artificial neighbors в список соседей для вершины.
Изображение
Т.е., если соединим вершины наиболее удаленные от текущей вершины,  Hill Climbing уже за две итерации найдет V8. И, естественно, artifical соседей лучше добавлять в начало списка.

Кэширование в GJK.
В Hill Climbing, если повезет, текущей вершиной будет экстремальная вершина.
В худшем случае, текущая вершина лежит в противоположной части многогранника от экстремальной вершины. Если у нас сцена с большой когерентностью, то можно хранить индекс экстремальной вершины (или даже целый симплекс с посл. итерации GJK) с предыдущего кадра. Для обоих случаев можно завести, скажем, hash table. В сцене с невысокой когерентностью, можно найти вектор между центрами тел, посчитать экстремальные вершины на обоих многогранниках относительно этого вектора, и использовать эти вектора как текущие вершины в Hill Climbing.
Часть из этих методов лучше делать в first – time initialization.

20 февраля 2006

2001—2018 © GameDev.ru — Разработка игр