Войти
ПрограммированиеФорумФизика

MPR-тест и подсчет глубины проникновения по нужному вектору

Страницы: 1 2 Следующая »
#0
10:25, 21 апр. 2020

Доброго времени суток.

Нужна помощь в изобретение велосипеда.

Использую физическую библиотеку (libccd), в которой есть MPR-тест (Minkowski Portal Refinement) столкновения двух выпуклых объектов.
Функция принимает пару объектов и возвращает разделяющую ось, глубину проникновения и точку касания.
Вопрос в том, как имея эти данные, получить глубину проникновения по нужной мне оси (для того чтобы правильно "вытолкнуть" движущийся объект не по вектору разделяющий оси, а по вектору скорости этого объекта), а не по разделяющей оси.
Я понимаю что это уже давно решено, но нагуглить не получается. Теория, примеры - мне все пойдет.


#1
14:28, 21 апр. 2020

MikeNew
> для того чтобы правильно "вытолкнуть" движущийся объект не по вектору
> разделяющий оси, а по вектору скорости этого объекта
так тебе надо правильно, или по вектору скорости? правильно — это именно по mtd вектору, который тебе возвращает mpr.

#2
4:31, 22 апр. 2020

Suslik
> так тебе надо правильно, или по вектору скорости? правильно — это именно по mtd
> вектору, который тебе возвращает mpr.
Я это понимаю, но тем не менее как-то же расталкивают в играх по произвольному вектору. Пример на картинке, шар на большой скорости ударяется о коробку и прилипает к ней.

1. Шар до столкновения (черный)
2. Шар, столкнувшийся с коробкой (красный)
3. Шар, вытолкнутый по mtd-вектору (синий)
4. Шар, вытолкнутый по вектору скорости (зеленый)

Изображение

Интересует:
1. Возможно ли рассчитать позицию зеленого шара, изпользуя данные возвращаемые mpr-алгоритмом (с учетом того что это могут быть не обязательно шар и коробка, а любые произвольные выпуклые меши).
2. Если предыдущий пункт технически невозможен, то какие есть обходные пути? Делают же это в играх как-то.

Получается, нужно как-то рассчитать длину фиолетового отрезка, чтобы растолкнуть объекты в нужном направлении.

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

#3
5:41, 22 апр. 2020

MikeNew
> 1. Возможно ли рассчитать позицию зеленого шара, изпользуя данные возвращаемые mpr-алгоритмом (с учетом того что это могут быть не обязательно шар и коробка, а любые произвольные выпуклые меши).
то, что ты пытаешься сделать, реализуется вовсе не через "выталкивание в направлении скорости", а через одно из двух — либо convex cast, либо через подсчёт time to impact. если либе collision detection дать только положение красной сферы и сказать : "решай", она при всём желании не сможет тебе дать положение зелёной, так как ты ей не сообщаешь, какой скоростью это тело обладает. и рассчитать это после того, как она отработала, невозможно, потому что если вместо нижнего бокса будет какая-то другая геометрия, результат будет другой.

я пробежался по интерфейсу libccd и не заметил в нём функций, необходимых для, собственно, ccd, лол. обычно такие функции принимают позиции, скорости и возвращают точку контакта (для зелёного положения) и время, через которое система окажется в этом положении.

однако, для стандартных алгоритмов, котрые используют support mapping(gjk, epa, mpr), часто используют один из двух подходов, чтобы приближённо считать ccd:
1) можно модифицировать сами геометрии, прибавив к ним по минковскому величину \(\vec v \ctimes dt\). таким образом ты их "растягиваешь" в направлении движения, и твоя чёрная сфера, например, превращается в капсулу, которая идёт от чёрной сферы до красной. это не даст определение tti или более точной точки контакта, но оно с меньшей вероятностью пропустит контакты из-за больших скоростей.
2) точку контакта и tti ищут просто бинарным делением времени. делишь время dt пополам, смотришь, пересекались ли тела в этот момент. если пересекались, снова делишь пополам отрезок слева, иначе — справа. этот подход комбинируют с 1), чтобы не допускать туннелирования.

вместо бинарного деления можно также использовать итерации ньютона, чтобы метод быстрее сходился, для этого считаешь, что нормаль в точке контакта совпадает с mtd вектором и высчитываешь промежуточную точку не как dt/2, а через \(\frac{\left|\vec{v}\right|}{\vec {mtd} \cdot \vec v}\)

ещё хинт — никто не считает ccd для всех тел всегда. это жутко медленно и имеет свои артефакты. обычно ccd включают только для тех тел, для которых нельзя допускат туннелирование или для особо быстрых тел вроде мяча в футболе. добавление каждого следующего ccd тела в систему может замедлять её экспоненциально, потому что вместо одного dt вся система будет вынуждена считаться для кучи промежуточных шагов, определяемых через минимальный tti каждого из ccd тел, который вполне может быть околонулевым.

#4
7:15, 22 апр. 2020

Suslik
> то, что ты пытаешься сделать, реализуется вовсе не через "выталкивание в
> направлении скорости", а через одно из двух — либо convex cast, либо через
> подсчёт time to impact...........
Исчерпывающая информация, это и хотел узнать. Буду реализовывать.

Suslik
> 1) можно модифицировать сами геометрии, прибавив к ним по минковскому величину
> [cht]\vec v \ctimes dt[/cht]. таким образом ты их "растягиваешь" в направлении
> движения, и твоя чёрная сфера, например, превращается в капсулу
Здесь пришло в голову вот что: любой меш описать сферой, тогда капсулу можно представить как пара сфер плюс цилиндр между ними (в примерах libccd есть быстрая шикарная support-функция для цилиндра). Такая проверка (две сферы плюс цилиндр) должна работать быстро, а то быстродействие сильно беспокоит.

Suslik
> точку контакта и tti ищут просто бинарным делением времени. делишь время dt
> пополам, смотришь, пересекались ли тела в этот момент. если пересекались
..... или если глубина проникновения меньше определенного значения  - считаем что не пересеклись, опять же для быстродействия, все равно визуально видно не будет (или не должно быть видно , проверять надо).
Update: Хотя если без глубины проникновения можно использовать более быстрый тест, только на сам факт столкновения.. надо сравнивать.

Спасибо, Suslik, на тебе весь физический раздел здесь держится.

#5
7:24, 22 апр. 2020

MikeNew
> тогда капсулу можно представить как пара сфер плюс цилиндр между ними
капсула эффективно описывается как сумма минковского сферы и отрезка. цилиндр для физ.двига рассчитать гораздо сложнее (потому что физ.двигу неудобно стабильно аппроксимировать контактную площадку для его круглых граней).

#6
7:48, 22 апр. 2020

Suslik
> капсула эффективно описывается как сумма минковского сферы и отрезка. цилиндр
> для физ.двига рассчитать гораздо сложнее (потому что физ.двигу неудобно
> стабильно аппроксимировать контактную площадку для его круглых граней).
Ясно. Сумма Минковского для меня пока темный лес, пошел читать теорию.
В саму же mpr-функцию не придется лезть чтобы это реализовать?

#7
8:14, 22 апр. 2020

MikeNew
> В саму же mpr-функцию не придется лезть чтобы это реализовать?
нет. ясное дело, все алгоритмы gjk, epa и mpr предполагается использовать as-is.

#8
20:50, 22 апр. 2020

http://noregret.org/tutor/n/collision/
Здесь хорошо описаны столкновения.

#9
8:33, 29 апр. 2020

Осознал принцип разницы Минковского.
Сделал для себя вывод, что использовать бинарное деление времени для медленно движущихся объектов (которые на дадут туннелинг) только для того чтобы вытолкнуть объект по вектору скорости - крайне неоптимально.
Нашел интересную статью
https://blog.hamaluik.ca/posts/swept-aabb-collision-using-minkowski-difference/
про столкновение двух AABB, в которой делается то что мне нужно, но только для AABB.
Возник вопрос - возможна ли модификация MPR-теста путем передачи в него вектора скорости, дающая возможность получать глубину проникновения по этому самому вектору, для 3D и произвольных выпуклых мешей? (просто "да/нет," понимаю что расписывать подробно вряд ли кто будет :) )

#10
9:05, 29 апр. 2020

MikeNew
> возможна ли модификация MPR-теста путем передачи в него вектора скорости,
> дающая возможность получать глубину проникновения по этому самому вектору
я уже говорил, что никто не ищет то, что ты называешь глубиной проникновения по вектору скорости. её можно посчитать, но она не несёт никакого физического смысла в общем случае, потому что если тела находятся в покое друг на друге, то у них скорость будет случайно флуктуировать вокруг нуля, поэтому вектор направления скорости будет непредсказуемо меняться, а вместе с ним и твоя величина. создаётся иллюзия, что эта величина имеет какой-то смысл только в твоём тесте для движущихся боксов, по-нормальному же нужен именно convex cast, который возвращает время (столкновения), а не глубину. причём всегда сначала ищется обычный mtd через алгоритм вроде epa, а если он зафейлился, то для тел с CCD делается ещё convex cast.

convex cast можно сделать аналитически для всяких боксов и сфер, также можно его посчитать итерационными схемами вроде GJK, но эти алгоритмы не очень просто понимать и писать, если до этого не имел с ними дела. если есть особое желание, разберись с GJK, MPR и тогда я могу тебе дать выдержку из своего диссера для поиска directional penetration — это итерационная схема, которая ищет глубину проникновения вдоль заданного вектора (в твоём случае скорости), которая как раз используется для установления time of impact. важный момент, что directional penetration используется не для того, чтобы расталкивать тела, а чтобы рассчитать по нему time of impact. я всё ещё не знаю, изобрёл ли я её сам, либо переизобрёл, но я не встречал публикаций с ней.

#11
11:04, 29 апр. 2020

Suslik
> я уже говорил, что никто не ищет то, что ты называешь глубиной проникновения по
> вектору скорости. её можно посчитать, но она не несёт никакого физического
> смысла в общем случае, потому что если тела находятся в покое друг на друге
Разумеется, я не собираюсь ее считать для случаев неподвижных тел, но уже то что ее можно посчитать - уже радует.
Suslik
> причём всегда сначала ищется обычный mtd через алгоритм вроде epa, а если он
> зафейлился, то для тел с CCD делается ещё convex cast.
Зафейлился - значит не совпал по направлению с вектором скорости?
Suslik
> по-нормальному же нужен именно convex cast
Мне несколько стыдно признаться, но я не смог нагуглить вменяемого определения convex cast, везде он упоминается как часть движков, определения никто не дает.
Можно пожалуйста вкратце определение его сути своими словами? Или может он как-то по другому может называться и поэтому не удалось нагуглить?
Suslik
> если есть особое желание, разберись с GJK, MPR и тогда я могу тебе дать
> выдержку из своего диссера для поиска directional penetration — это
> итерационная схема, которая ищет глубину проникновения вдоль заданного вектора
У меня особое желание использовать наиболее быстрый способ. Если вычисление directional penetration заметно быстрее алгоритма бинарного деления(что я очень сильно подозреваю) - желание его постичь крайне большое.
По GJK и MPR пока поверх прошелся и уже голова перегрелась, завтра продолжу как остынет.

#12
10:09, 15 мая 2020

Почитал, как оно делается и решил что ну его нафиг (по крайней мере пока что), лучше и правда делать через tti, заодно не будет проблем с вращениями и некоторыми другими моментами.

#13
6:45, 19 мая 2020

MikeNew
> и как это значение применять к вектору скорости?
откатываешь систему в это состояние во времени, запускаешь солвер контактов.

#14
10:46, 22 мая 2020

Suslik
> откатываешь систему в это состояние во времени, запускаешь солвер контактов.
Принцип работы этой итерации - чем больше угол между скоростью и вектором минимального проникновения, тем на большее значение откатываем систему - я понял, есть вопрос и некоторое непонимание по значениям, которые эта формула выдает.
Возьмем простейший случай, для простоты, вектор скорости совпал с проникновением и проникновение ровно "посередине", при значении скорости в 10 - касание будет при значении 5:

Изображение

тогда \(\frac{\left|\vec{v}\right|}{\vec {mtd} \cdot \vec v}\) будет равно 0.2.

При изменение величины проникновения от нуля(точнее, чуть больше нуля) до ста процентов от скорости, значение  \(\frac{\left|\vec{v}\right|}{\vec {mtd} \cdot \vec v}\) меняется в диапазоне от 1000+++ до 0.1
И я не понимаю как применять такой диапазон для отката в данном случае. Вот при значение 0.2 надо откатываться ровно на середину от 10-ти (на 5), как?

Страницы: 1 2 Следующая »
ПрограммированиеФорумФизика

Тема в архиве.