Collision Detection для геометрий, заданных SupportMapping'ом (комментарии) (3 стр)

id-mikle
аа, все понял, ну я и протупил. Это ж надо процекцию на ось брать и смотреть

gexogen
Я вот тока не понял почему суслик нормализует

SMap_sphere(dir, R_sphere, x_sphere) = Normalize(dir) * R_sphere + x_sphere;

т. е. для
>даны два круга радиуса 1 у одного центр в (-100;0), а у другого в (100;0)
саппортмапы в CSO будут
SMap₁(dir) = Normalize(-dir) + vector2(-100, 0);
SMap₂(dir) = Normalize( dir) + vector2( 100, 0);
SMap_CSO(dir) = SMap₂ - SMap₁;

С увеличением расстояния между сферами ЦСО менять свою форму не будет, будет лишь отдаляца от точки (0, 0, 0) - ориджина.

XperienS
Он не так делал, так то понятно.
Тогда не понятно почему если брать max то для двух кругов, если все точки одного имеют отрицательные координаты а другого положительные, получится выпуклая оболчка? Ведь все точки после применения max() будут положительные

id-mikle
в своём посте 21 я накосил. запись
>SMap1(v) = (v + Vector2( 100.0f, 0)).GetNorm();
неверна, XperienS написал верный вариант саппорт мэппинга сферы со смещённым центром

Всё остальное, вроде, верно.
>Тогда не понятно почему если брать max то для двух кругов, если все точки одного имеют отрицательные координаты а другого положительные, получится выпуклая оболчка? Ведь все точки после применения max() будут положительные
Не забывай, что мы выбираем максимальную проекцию. Ну вот две крайние точки:

SMap_c(Vector2(1, 0)) = (SMap_a(Vector2(1, 0)) * Vector2(1, 0) > SMap_b(Vector2(1, 0)) * Vector2(1, 0)) ? SMap_a(Vector2(1, 0)) : SMap_b(Vector2(1, 0))
равносильно
SMap_c(Vector2(1, 0)) = (Vector2(-99, 0) * Vector2(1, 0) > Vector2(101, 0) * Vector2(1, 0)) ? Vector2(-99, 0) : Vector2(101, 0)
равносильно
SMap_c(Vector2(1, 0)) = (-99 > 100) ? Vector2(-99, 0) : Vector2(101, 0)
сдедовательно,
SMap_c(Vector2(1, 0)) = Vector2(101, 0)

аналогично получаем
SMap_c(Vector2(-1, 0)) = Vector2(-101, 0)

Алгоритм хорош, но он находит только локальный минимум.
При неудачном выборе начального направления от может ТАК сойтись, что не дай Бог

Кстати, Suslik, пытался строго доказать сходимость?
Интересно, алгоритм поиска "хитрого вектора из п.2" был найден в статье, доказан или выведен
чисто практически?

Shalom
>Алгоритм хорош, но он находит только локальный минимум.
К счастью, локальный минимум при небольших пенетрейшнах совпадает с глобальным, а при больших - пофиг, найти бы хоть какой-нибудь :)

>При неудачном выборе начального направления от может ТАК сойтись, что не дай Бог
опять же, при малом пенетрейшне допустимо отклонять initialCase на угол, близкий к pi / 2, то есть лишь бы сторону, в которую искать, правильно выбрать - и то вперёд.

>Интересно, алгоритм поиска "хитрого вектора из п.2" был найден в статье, доказан или выведен чисто практически?
я мог бы его доказать, это не так трудно, но, думаю, здесь не оценят. Главный его плюс в том, что он строит манифолд, корректный для любого локального минимума, то есть для любого локального минимума при "плохом" пенетрейшне он всё равно построит непустой манифолд с корректными для данного PD нормалями, точками и прочей лабудой. То есть две части алгоритма разрабатывались исключительно друг для друга :)

//в двумерности он сходится вообще всегда, при выборе вообще любого initialCase, это ерунда. некоторые траблы есть в трёхмерности, когда иногда для более-менее быстрой сходимости приходится генерить чуть больше точек, чем хотелось бы.

Вопрос по генерации Contact Manifold'a

Не понятен 2-ой пункт, а именно как искать саппорт пойнт в направлении, что это? Так понимаю что это какая-то ближайшая вершина?
И ещё, для нахождения контактов  в случае произвольной выпуклой геометрии как следует применять этот алгоритм?

так:

или так:

ValLer
>а именно как искать саппорт пойнт в направлении, что это?
в самом начале статьи написано. саппорт пойнт - это функция, характеризующая геометрию(многоугольник в твоём случае). для каджого направления она знает саппорт пойнт - "самую далёкую" в этом направлении точку многоугольника.

>И ещё, для нахождения контактов в случае произвольной выпуклой геометрии как следует применять этот алгоритм?
идём по статье:
2) Наклоним вектор axis на delta градусов против часовой стрелки, и возьмём в этом направлении саппорт пойнт нижнего бокса, обозначим её a1. Далее повернём тот же axis на ту же delta по часовой стрелке, вновь возьмём саппорт пойнт того же бокса и обозначим получившуюся точку b1. Далее инвертируем вектор axis, и, вновь поворачивая его ан угол delta, берём два саппорт пойнта верхнего бокса - a2 и b2. Может получиться так, что какие-то из этих точек совпадут - ничего страшного, это совершенно нормально.

если угол delta брать небольшим, градусов 15, то точки a1-b1 на твоём чертеже будут концами синего отрезка, а точки a2-b2 совпадут и будут лежать в самой верхней точке нижнего многоугольника, куда показывает стрелка. таким образом коллижн будет один - та самая единственная точка будет выталкиваться в направлении синего отрезка.
если же угол delta брать больше, на глаз, градусов 30, то картина будет как на твоём первом рисунке - отрезки выталкиваются в направлении PD.

> Проецируем точку a1 в направлении axis на прямую a2-b2

Подскажите, пожалуйста, как спроецировать вектор в направлении axis? Точнее в любом направлении, а не просто опустить перпендикуляр от одного вектора к другому, это я знаю как сделать.

plztea4mef8
> Подскажите, пожалуйста, как спроецировать вектор в направлении axis? Точнее в
> любом направлении, а не просто опустить перпендикуляр от одного вектора к
> другому, это я знаю как сделать.
пусть прямая задана точкой p и направлением dir. точку point проецируем в направлении axis.
смещая point на расстояние m в направлении axis, она должна попасть на нашу прямую. уравнение прямой: p + dir * t
p + dir * t = point + axis * m
домножаем с обеих сторон на dir:
dot(p, dir) + dot(dir, dir) * t = dot(point, dir) + dot(dir, axis) * m  (1)
пусть dot(dir, dir) = 1, вектор направления нормализован.

теперь домножаем точно так же на axis:
dot(p, axis) + dot(dir, axis) * t = dot(point, axis) + dot(axis, axis) * m  (2)
dot(axis, axis) также равен 1.

из первого выражения выделяем t = dot(point - p, dir) + dot(dir, axis) * m
подставляем во второе:
dot(dor, axis) * dot(point - p, dir) + sqr(dot(dir, axis)) * m = dot(point - p, dir) + dot(dir, axis) * m;
прямым образом выражаем m, выпишешь уж сам.

ну и всё, подставляем m в уравнение прямой, искомая точка проекции: point + axis * m

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

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

в последней строчке после знака равно должно быть dot(point-p,axis) + m

Спасибо за потраченное время! Очень помогли!

Не ясно следующее. Допустим имеем две сферы одинакового радиуса:
SMap_a(v) = v * r+ C_a
SMap_b(v) = v * r+ C_b
CSO(v) = SMap_a(v) - SMap_b(v) = v * r + C_a - v * r+ C_b =  C_a - C_b = const

Т.е. константа, даже не зависящая от радиуса окружностей. Что за фигня?

Возможно в статье ошибка, и CSO(v) =  SMap_a(v) - SMap_b(-v) на самом деле?

Ferlan кажется, ты прав, и минус я действительно упустил. исправил.

Не хочу показаться занудой,

SMap_c(v) = - SMap_a(v)

тут тоже должен быть минус перед аргументом.
И главное, по поводу поиска PD. Цитата.

Если угол между вектором pd и v меньше некоего порогового значения, скажем, 1e-3fрад, то возвращаем значение PD = pd и выходим, иначе присваем pd = v и идём снова выполнять пункт 2