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

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

Это сообщение сгенерировано автоматически.

Хух, осилил.. Жду комментов :)

Круто, собсно.
Пока прочитал разок и пара чисто редакторских замечаний :)

> А на человеческом, геометрия должна знать, какая её точка "самая далёкая" в каждом направлении. Проиллюстрирую на примерах эллипса
> и [b]треугольника[/b], где стрелками показаны направления, а кружочками тех же цветов - экстремальные вертексы, им соответствующие.
(первая картинка)
а на картинке - четырехугольник

> Геометрия, которую пораждает мэппинг Fcso, называется [b]CSO[/b] и обладает интересными и крайне полезными для нас свойствами:
CSO, нада бы таки сказать что это значит Configuration Space Obstacle, а то вдруг будут смотреть люди не знакомые с подобной терминологией

> минимальный из всех существующих Directional Penetration Depth векторов называется просто [b]Penetration Depth(PD)[/b] и обозначает
> минимальное смещение, на которое нужно переместить одну из геометрий, чтобы они перестали пересекаться
афаик, минимальный вектор на который нужно перенести тела штоб не было коллизий называют MTD(Minimum Translation Distance)

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

ну и еще, чтоб было читать круто, абзац
> Если же геометрии пересекаются [b]настолько, что[/b] начало координат оталяется от CSO [b]настолько, что[/b] появляется ещё больше "паразинтых"
> направлений - опять же не беда - алгоритм сойдётся какому-то из них, устраняя слишком глубокое взаимопроникновение.
вот это поправить чуть, а то немного глаз режет

это пока просто ремарки по статье непосредственно, ща я профтыкаюсь душевно и буду говорить уже по теме

Вот, родился пока небольшой вопрос.

Иллюстрация (имеем CSO двух многогранников достаточно больших размеров, чтобы смещение v за итерацию было достаточно мало):

Обозначения теже, желтый - вектор PD, зеленый - вектор v, синий - вектор от саппорт поинта F(v) до пересечения плоскости с PD.
Появилось еще кое-что: это красная обводка вектора SA - величина которую мы прибавим к v чтоб получить вектор для следующей итерации. Но тут вроде как вырисовывается косяк небольшой - при достаточно большом соотношении (длина фейса/малое смещение) - мы будем несколько раз подряд получать тот же саппорт поинт F(v), что может привести к долгой сходимости, фактически неизза чего. Может, здесь целоесообразно зарулить какой-нить алго, который будет увеличивать смещение вектора v за итерацию, в случае если мы повторно попадаем на тот же саппорт ( соответственно, продумать еще алго уменьшения штоб не было косяка, и быстрее сходилось )? Этакий адаптивный механизм. Хотя, я может не дофтыкал чего.

> 2) Далее находится такой вектор [b]v[/b], что:
> F_cso([b]v[/b]) = DPD(pd);
Еще кстати, вопрос по этой ситуации - если мы будем получать два саппорта по "фейсу" сквозь который проходит PD - и будем между ними скакать, посути же так и не найдем такого, чтоб PD совпадал с саппортом v, даже с некоторой допустимой ошибкой?

Пока процесс фтыкания продолжаеца, и смотрица твой алго достаточно красиво ( если таки разьясница по поводу вопроса ), респект :)
Процесс нахождения вектора v особенно порадовал - смотрица совсем как SOR :)

P/S: ещеб саппорт маппинг по другому обозвать, а то появляюца сомнения в процессе фтыкания, что-то вроде SMap(v) или как-то так, а то Ф как-то отдаленно.

XperienS
>а на картинке - четырехугольник
вот что бывает, когда пишешь статью в четыре часа ночи :D
>CSO, нада бы таки сказать что это значит Configuration Space Obstacle, а то вдруг будут смотреть люди не знакомые с подобной терминологией
точно - я хотел потом написать расшифровку, но так и не вспомнил)
>афаик, минимальный вектор на который нужно перенести тела штоб не было коллизий называют MTD(Minimum Translation Distance)
может, просто разные терминологии? я обычно встречал именно такую.
>наверное, имелось ввиду 1e-3f
>ну и еще, чтоб было читать круто, абзац
угу, поправил
>Вот, родился пока небольшой вопрос.
Отличный вопрос, Экспо. Добавил в ремарку к termination condition'у
>ещеб саппорт маппинг по другому обозвать, а то появляюца сомнения в процессе фтыкания, что-то вроде SMap(v) или как-то так, а то Ф как-то отдаленно.
да, ты прав

Очень хорошая статья, хотя и непонятная мне с первого раза....Картинок по-больше, алгоритм в виде псевдокода или блок-схемы написать - и будет замечательная статья по этой теме.

А. Ещё бы для 3Д написать, а то я когда-то 2Д реализовал, легко показалось, стал в 3Д переделывать - появилось много проблем...

Станислав
Да, с переводом в 3д тут действительно всё совсем не так просто и изящно, как в 2д.. Но, к сожалению, я пока морально не готов поделиться 3д реализацией, выкладывая, фактически все свои козыри :)

Suslik
А как обычно задают supportmapping в 3d (и 2d)?

Нашел ошибку для этого саппорт маппинга неправильная картинка:
s_c(v) = max(s_a(v), s_b(v))

почему эллипс плавно перетекает в квадрат? Точки которые в этом плавном переходе(на рисунке) не

принадлежат ни квадрату, ни эллипсу.

тут повторение получается:
>Мы будем использовать итеративный алгоритм приближения PD-вектора, стартуя с некоторого исходного значения - например, центральной разницы геометрий или значения PD с предыдущего шага симуляции.
>1) Изначально значение PD инициализируется каким-то "не слишком далёким" значением, к примеру, центральной разницей двух геометрий или значением PD с предыдущего кадра нашей физической симуляции

>3) ... то возвращаем значение PD = pd
если я правильно разобрался в терминологии, то нужно PD = DPD(pd)

>их DID'ы примерно одинакового порядка малости.
что такое DID? или опечатка от DPD?

>начало координат оталяется от CSO настолько
отдаляется.
и, наверно, тут нужно уточнить, что удаляется оно от поверхности CSO, то есть вглубь.

>К сожалению, на момент написания статьи я всё ещё не разглашаю 3д версию этого алгоритма, но 2д постараюсь изложить.
либо нужно написать "Рассмотрим нахождение этого вектора в 2Д" либо вообще ничего не писать, потому что вся остальная статья все равно в 2D.

>возвращать результат можно в случае, если мы не можем укоротить вектор OA, скажем, четыре итерации подряд
надо вектор SA, а не OA?

В конце первой страницы как-будто лишнее предложение:
>утверждается, что алгоритм сходится

по второй странице no comments...

id-mikle
функция, которая принимает параметром вектор (направление, по которому нужна экстремальная точка) и возвращает вектор - эту точку.

gexogen
>>функция, которая принимает параметром вектор (направление, по которому нужна экстремальная точка) и возвращает вектор - эту точку.
Определение я читал)) вопрос в том как эта функция работает чтобы она за O(1) давала нужную точку

gexogen
А про элипс с квадратом - думаю max - берется по координатно, так что не обязательно такие точки должны быть в A или B).

id-mikle
>Определение я читал)) вопрос в том как эта функция работает чтобы она за O(1) давала нужную точку
А разве где-то написано, что для произвольной геометрии саппорт мэппинг будет O(1)?
для сферы s(v) = O + R*v (если v нормализован)
для бокса s(v) = (sign(v.x) * hw, sign(v.y) * hh, sign(v.z) * hl) (hw - полширины, hh - полвысоты, hl - полдлины)
и для подобных (конус, цилиндр, и т.п.) типа того - просто расчет по формуле.
для произвольных многогранников использовать hill climbing - http://www.gamedev.ru/community/gamedev_lecture/articles/?id=16&page=2, тут посложнее O(1)

>А про элипс с квадратом - думаю max - берется по координатно, так что не обязательно такие точки должны быть в A или B)
хм, тогда понятно.

gexogen
Я думал что фишка в том что вместо геометрии хранится какая то структура данных которая за O(1) выдает нужную точку.

gexogen
Большое спасибо за ремарки - меры будут приняты.

Скажу только по поводу мэппинга с рисунком - это не сумма минковского, а выпуклая оболочка. Для неё мэппинг выглядит именно так - посмотри формулу.

>по второй странице no comments...
в смысле? всё так плохо?