Войти
Gamedev LectureСтатьи

Лекция #13. GJK (convex collision detection). [Лектор - Innochenti]

Автор:

Disclaimer: некоторые опечатки поправлены, некоторые посты передвинуты, картинки перезалиты на imageshack. полный лог

[11:59] <Innochenti> тема лекции: GJK на пальцах.
[11:59] <Innochenti> для начала пару основных терминов на которых построен алгоритм.
[12:00] <Innochenti> Сума Минковского  двух множеств A и B в Евклидовом пространстве это результат сложения каждого элемента A с каждым элементом B:
[12:00] <Innochenti> т.е. A+B={a+b|a принадлежит A, b принадлежит B}.
[12:00] <Innochenti> я приготовил тут пару примеров
[12:00] <Innochenti> Сума
[12:00] <Innochenti> 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)}
[12:00] <Innochenti> Разница
[12:00] <Innochenti> 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)}
[12:00] <Innochenti> Графический пример сумы Минковского (рис 1) и разницы Минковского(рис 2):
[12:00] <Innochenti> Изображение
[12:02] <Innochenti> так, теперь зачем это нужно.
[12:02] <Innochenti> GJK использует тот факт, что два многогранника пересекаются только в том случае, если их разница Минковского C = A-B содержит начало системы координат.
[12:03] <Innochenti> В действительности, возможно получить еще полезнее результат:
[12:03] <Innochenti> посчитать минимальное расстояние между A и B,
[12:03] <Innochenti> что эквивалентно вычислению минимального расстояния между C и началом системы координат.
[12:04] <Innochenti> т.е.
[12:04] <Innochenti> distance(A,B) = min{||a-b|| : a принадлежит A, b принадлежит B} = min{||c|| : c принадлежит A - B}.
[12:05] <Innochenti> важно замечание:
[12:05] <Innochenti> разницу Минковского двух объектов иногда называют TCSO
[12:05] <Innochenti> (translation configuration space obstacle)
[12:06] <Innochenti> вдруг, кто-нить захочет всерьез заняться cd.
[12:06] <Innochenti> так теперь опишу техники для этого алгоритма.
[12:06] <Innochenti> понятней будет немного позже, когда буду на примере показывать работу GJK
[12:07] <Innochenti> вообще говоря, посчитать разницу Минковского на каждой итерации алгоритма довольно тяжело, поэтому в GJK используется support mapping.
[12:07] <Innochenti> это функция которая в заданном направлении d отображает экстремальную точку для выпуклого объекта A в этом направлении.
[12:07] <Innochenti> Например, для сферы, которая находится в O, с радиусом r, support mapping имеет вид: Sc = O+rd/||d||
[12:07] <Innochenti> Изображение
[12:07] <Innochenti> на картинке
[12:08] <Innochenti> P - экстремальная точка
[12:08] <Innochenti> или для box:
[12:08] <Innochenti> Sc(d) = (sgn(x)d_x, sgn(y)d_y, sgn(z)d_z).
[12:08] <Innochenti> для других сложных фигур
[12:08] <Innochenti> используется алгоритм hill climbing
[12:08] <Innochenti> о нем немного позже, после описания основного алгоритма.
[12:09] <Innochenti> support mapping для двух объектов Разницы Минковского A и B
[12:09] <Innochenti> можно переписать следующим образом:
[12:09] <Innochenti> S(A-B) = SA(d)-SB(-d)
[12:10] <Innochenti> откуда следует, что точки разницы Минковского могут быть вычислены из экстремальных точек отдельных многогранников A и B.
[12:10] <Innochenti> для того что бы найти разницу Минковского С для точки ближайшей к началу системы
[12:10] <Innochenti> координат, GJK использует Caratheodory's Theorem:
[12:10] <Innochenti> Для выпуклого тела H (R^d),
[12:10] <Innochenti> каждая точка из H может быть выражена как выпуклая комбинация не более чем d+1 точек из H.
[12:11] <Innochenti> Вот тут подробнее и с примером
[12:11] <Innochenti> http://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_%28convex_hull%29
[12:11] <Innochenti> если начало координат содержится в текущем симплексе, A и B пересекаются и алгоритм прекращает свою работу.
[12:11] <Innochenti> Иначе, множество Q обновляется таким образом,
[12:11] <Innochenti> что новый симплекс, гарантировано будет содержать точки ближайшее к началу системы координат, чем предыдущий симплекс.
[12:12] <Innochenti> теперь классический псевдокод GJK ;)
[12:12] <Innochenti> while not best_simplex(S) do
[12:12] <Innochenti> S<-refine_features(S);
[12:12] <Innochenti> endwhile
[12:12] <Innochenti> собственно, так описывают этот алгоритм.
[12:12] <Innochenti> в случае когда A и B не пересекаются, наименьшее расстояние между A и B находится с помощью точки минимальной нормы в CH(Q) (convex hull Q).
[12:13] <Innochenti> так, теперь добрались, до описания общего алгоритма.
[12:13] <Innochenti> Общий алгоритм таков:
[12:13] <Innochenti> - Инициализируем симплекс Q d+1 точками из разницы Минковского A и B.
[12:13] <Innochenti> - Вычисляем точку минимальной нормы P в CH(Q).
[12:14] <Innochenti> - Если P и есть начало координат, то начало координат содержится в разнице Минковского A и B. Останавливаемся и возвращаем, что A и B пересекаются.
[12:14] <Innochenti> - Уменьшаем Q до подмножества Q', такого что P принадлежит CH(Q').
[12:14] <Innochenti> - Пусть V = Sa-b(-P)=Sa(-P)-Sb(P) будет экстремальной точкой в направлении P.
[12:14] <Innochenti> - Если V не является экстремальной точкой в направлении P, тогда возвращаем, что A и B не пересекаются.
[12:15] <Innochenti> Длина вектора от начала координат к P это разделяющее расстояние от A до B.
[12:15] <Innochenti> - Добавляем V в Q и переходим на шаг 2.
[12:18] <Innochenti> вот определение симплекс: http://en.wikipedia.org/wiki/Simplex
[12:15] <Innochenti> Все подошли к примеру, после которого станет все ясно!
[12:15] <Innochenti> Рисунок:
[12:16] <Innochenti> Изображение
[12:16] <Innochenti> ща буду описывать, как работает алгоритм.
[12:16] <Innochenti> Вот этот convex hull, это есть результат разницы A - B.
[12:17] <Innochenti> смотрите на те пункты, что выше.
[12:17] <Innochenti> алгоритм начинает с вершины A и инициализирует множество Q = {A}.
[12:17] <Innochenti> для начальной вершины, ближняя вершина и есть сама вершина.
[12:17] <Innochenti> это пункт номер два алгоритма.
[12:18] <Innochenti> Экстремальной вершиной для вершины A будет вершина B, следовательно добавляем в множество: Q = {A,B}.
[12:19] <Innochenti> это convex hull справа на картинке
[12:19] <Innochenti> Точка в CH(Q) ближайшая к началу системы координат это C.
[12:19] <Innochenti> поскольу только через две вершины A и B необходимо выразить C как выпуклую комбинацию, обе остаются в Q.
[12:20] <Innochenti> D это экстремальная вершина в направлении C, поэтому Q = {A,B,D}.
[12:20] <Innochenti> Точка в CH(Q) ближайшая к началу системы координат теперь E.
[12:20] <Innochenti> convex hull слева внизу.
[12:20] <Innochenti> поскольку только через B и D можно выразить как выпуклою комбинацию вершин в Q, то Q = {B,D}.
[12:21] <Innochenti> экстремальная вершина в направлении E это F, которая добавляется в Q.
[12:21] <Innochenti> точка в CH(Q) ближайшая к началу системы координат теперь G.
[12:21] <Innochenti> поскольку, теперь хватает D и F  что бы выразить G как выпуклою комбинацию, => Q = {D,F}.
[12:21] <Innochenti> И завершающая стадия алгоритма:
[12:21] <Innochenti> поскольку нет  вершин лежащих ближе всего к началу системы координат
[12:21] <Innochenti> в направлении G, то G и является ближайшей точкой к центру
[12:22] <Innochenti> и алгоритм прекращает свою работу.

[12:22] <Zeux> объясни, что такое симплекс и мин. норма
[12:22] <Zeux> желательно без ссылок на wiki ^_^
[12:23] <Innochenti> симплекс это convex hull d+1 афиннонезависимых точек в d пространстве.
[12:23] <Innochenti> например
[12:23] <Innochenti> 0-simplex - точка
[12:23] <Innochenti> 1-simplex - прямая
[12:24] <Innochenti> 2-simplex - треугольник
[12:24] <Innochenti> 3-simplex - тетраэдр
[12:25] <Innochenti> так, а минимальная норма, вот в примере
[12:25] <Innochenti> например точка C
[12:26] <Innochenti> во втором convex hull
[12:26] <Innochenti> т.е. ортогональная проекция
[12:26] <Innochenti> origin на прямую
[12:27] <Innochenti> я дальше расскажу как находить эту точку минимальной нормы

Страницы: 1 2 Следующая »

11 февраля 2006 (Обновление: 12 фев. 2006)

Комментарии [1]