Комментарии 25
> Как работает симуляция физики
> Первый этап — это найти пересечение
> Отлично, все пересечения найдены
Рисуем кружок, рисуем остаток совы. Я после такого заголовка и видео уж было ожидал осмысленного объяснения, как именно происходит борьба с O(n^2) на таком огромном числе объектов. По ссылкам информация чисто алгоритмическая. Может расскажете, как отсекаются ненужные проверки? Как это всё ускоряется?
> Первый этап — это найти пересечение
> Отлично, все пересечения найдены
Рисуем кружок, рисуем остаток совы. Я после такого заголовка и видео уж было ожидал осмысленного объяснения, как именно происходит борьба с O(n^2) на таком огромном числе объектов. По ссылкам информация чисто алгоритмическая. Может расскажете, как отсекаются ненужные проверки? Как это всё ускоряется?
Тут описано три шага: Broadphase, Narrowphase, Solver. Я опустила управления памятью. Я не рассмотрела суставы и трение. Быстрый поиск поиск в статических мешах. Что ваш упрек заслуженный и я попробую исправится. AxisSweep3 это 16 битный алгоритм, который забивает большую AABB коробку на 16384 маленьких коробки и все объекты помещает в эти коробки и так и ищет. Чем то напоминает хеш таблицу. Если 16384 коробки мало, то есть bt32BitAxisSweep3 32 битный аналог.
Я слышал, что AMD вместе с Bullet делает свою альтернативу PhysX, которая будет ускоряться на «красных» GPU
Создатель Bullet в начале работал на Havok. Потом он работал в Sony, потом в AMD. AMD как раз хотели добавить Open CL в Bullet, Open CL не использовала, не знаю. Вот видео вероятно как результат той работы. www.youtube.com/watch?v=8jGZv1YYe2c 110 тыс кубиков это очень много для симуляции в реальном времени
Зачем нужна полная матрица алгоритмов определения коллизий, когда достаточно треугольной, так как операции коммутативны?
Вы же понимаете, что это таблица указателей на функции, да?
Это скриншот из PDF
Вообще вопрос касается интересной проблемы. Ведь если мы имеем две коробки и алгоритм boxbox, то какой будет перпендикуляр касания, какая коробка первый параметр и какая коробка второй параметр. Часто так получается, что 3 сеукнды одна коробка первый параметр, и все красиво скользит потом, что где то далеко меняется, и это меняет параметры в boxbox местами и все летит в тар-тарары.
Вообще вопрос касается интересной проблемы. Ведь если мы имеем две коробки и алгоритм boxbox, то какой будет перпендикуляр касания, какая коробка первый параметр и какая коробка второй параметр. Часто так получается, что 3 сеукнды одна коробка первый параметр, и все красиво скользит потом, что где то далеко меняется, и это меняет параметры в boxbox местами и все летит в тар-тарары.
Интересные блики на шаре в Close-up: from below
Почитал список похожих публикаций. Посмотрел на список тегов. Сделал выводы.
А зачем там lowerLimit?
Что бы я сказала, что я понимаю, то нет. Мне кажется lowerLimit раньше не было и код был короче. Об этом и написала.
c.m_appliedImpulse — тут мы сообщаем с каким импульсом мы обработали коллизию. (Например, громкость удара)
Но получается, что если сила меньше, то ее фактически в тайне увеличивают до какого то миниума.
Зачем? Вопервых в буллет очень, хорошо борются с denormal numbers. Тут ни что не касается в ноль. (trashhold) Если интеловские процы нормально обрабатывают denormal, то многие другие например армы переходят в soft и это прерывание им стоит 100 тактов.
Во вторых? я вообще не понимаю этого кода, что тут отвечает, что нет вибраций и резонанса. Если выстроить 10 кубиков в столбик то, они спокойно стоят и эти все силы и импульсы не начинают резонировать.
c.m_appliedImpulse — тут мы сообщаем с каким импульсом мы обработали коллизию. (Например, громкость удара)
Но получается, что если сила меньше, то ее фактически в тайне увеличивают до какого то миниума.
Зачем? Вопервых в буллет очень, хорошо борются с denormal numbers. Тут ни что не касается в ноль. (trashhold) Если интеловские процы нормально обрабатывают denormal, то многие другие например армы переходят в soft и это прерывание им стоит 100 тактов.
Во вторых? я вообще не понимаю этого кода, что тут отвечает, что нет вибраций и резонанса. Если выстроить 10 кубиков в столбик то, они спокойно стоят и эти все силы и импульсы не начинают резонировать.
Когда-то на третьем пентиуме я столкнулся с тем, что обработка денормальных чисел жутко тормозит. В десятки и сотни раз медленнее. С тех пор исправили?
Насколько я понимаю (и по воспоминаниям о своем собственном опыте): когда рассчитываешь столкновения исходя из импульсов очень важно, чтобы столкновения оставались «моментальными» — т.е. два тела, которые на предыдущем шаге не соприкасались, на этом шаге соприкасаются — на следующем шаге они должны уже снова перестать соприкасаться. Потому что если вы на текущем шаге симуляции обработали столкновение тел, поправили их импульсы, но с этими импульсами тела не успели разойтись до следующего шага, то вы получаете на следующем шагу ситуацию, когда у вас два тела по координатам сталкиваются, а по импульсам — расходятся (вы же их «отразили» на предыдущем шаге). С точки зрения импульсного подхода _эту_ ситуацию уже сложновато корректно разрулить (она просто нефизическая). В идеальном мире такого просто не должно возникать. Но в реальной симуляции с конечными шагами по времени, со внешними силами (например, гравитацией) — эта ситуация возникает часто. Поэтому, видимо, минимальный импульс был введен для того, чтобы (почти)наверняка развести тела которые сталкиваются с малой передачей импульса.
>И тут встает вопрос, если все так просто, как получается, что можно выложить в столбик кубики и они себе спокойно стоят и не разлетаются?
>Я покажу, что за всю эту магию отвечает маленький кусочек кода!
Я так понимаю этот маленький простой кусочек кода, вызывается большим и сложным куском кода, который решает какой импульс к каким объектам применить :)
>Я покажу, что за всю эту магию отвечает маленький кусочек кода!
Я так понимаю этот маленький простой кусочек кода, вызывается большим и сложным куском кода, который решает какой импульс к каким объектам применить :)
Самое сложное в collision detection это penetration depth. И самое веселое.
Почему веселое и сложное?
Если обнаружено проникновение — значит где-то в момент времени между предыдущим и текущим шагом симуляции произошло столкновение. В первом приближении можно округлить момент столкновения до предыдущего или текущего и применить правила взаимодействия. Или это слишком грубое приближение?
Еще как вариант — попытаться найти момент столкновения более точно, интерполируя движение данных конкретных тел между шагами симуляции. Или это слишком затратно по ресурсам?
Если обнаружено проникновение — значит где-то в момент времени между предыдущим и текущим шагом симуляции произошло столкновение. В первом приближении можно округлить момент столкновения до предыдущего или текущего и применить правила взаимодействия. Или это слишком грубое приближение?
Еще как вариант — попытаться найти момент столкновения более точно, интерполируя движение данных конкретных тел между шагами симуляции. Или это слишком затратно по ресурсам?
В первом приближении можно округлить момент столкновения до предыдущего или текущего и применить правила взаимодействия. Или это слишком грубое приближение?
Еще как вариант — попытаться найти момент столкновения более точно, интерполируя движение данных конкретных тел между шагами симуляции. Или это слишком затратно по ресурсам?Это ничего не даст. Суть penetration depth — найти точку к которой нужно приложить силу, и глубину проникновения, чтобы знать какую именно силу приложить (а с учетом трения — там вообще сказка вырисовывается). Я когда сам писал свой физический двиг — уперся именно в этот момент. Стек предметов у меня либо вибрировал, либо проминался и был меньшей высоты, чем надо. Ну и в довесок были проблемы с трением.
Я вот в поисках версии буллета где было комментов по больше, боюсь солгать, но мне кажется, что про солвер было сказано, что он получен эксперементально перебором. Если глубину проникновения двух сфер легко получить, а глубину проникновения двух кубов уже сложней, тогда вопрос: Что считать глубиной? Напрашивается ответ, нам нужно расстояние на которое следует вытолкнуть тело из коллизии,
и тут мы начинаем думать, а ведь начальная скорость не всегда ноль, и после того как мы приложим импульс, какую скорость мы хотим получить.
И наш алгоритм не должен подменять трение. Трение там отдельно реализовано.
Если рассматривать самый простой вариант башня из 10 кубов, что бы она держалась, какая должна быть скорость кубов, ведь у нас всего 30-60 симуляции в секунду. Если первый куб чуть просел и его пихнули вверх, то он немного вибрирует, если нет дампинга, а куб который лежит на этом кубе уже вибрирует на вибрирующей поверхности, легко может случиться что его часто это резонансная частота. (резонанс зависит только от массы, а она может быть любой)
Самый похожий код на код дампинга это
и тут мы начинаем думать, а ведь начальная скорость не всегда ноль, и после того как мы приложим импульс, какую скорость мы хотим получить.
И наш алгоритм не должен подменять трение. Трение там отдельно реализовано.
Если рассматривать самый простой вариант башня из 10 кубов, что бы она держалась, какая должна быть скорость кубов, ведь у нас всего 30-60 симуляции в секунду. Если первый куб чуть просел и его пихнули вверх, то он немного вибрирует, если нет дампинга, а куб который лежит на этом кубе уже вибрирует на вибрирующей поверхности, легко может случиться что его часто это резонансная частота. (резонанс зависит только от массы, а она может быть любой)
Самый похожий код на код дампинга это
const btScalar deltaVel1Dotn = c.m_contactNormal.dot(body1.internalGetDeltaLinearVelocity()) + c.m_relpos1CrossNormal.dot(body1.internalGetDeltaAngularVelocity());
А зачем знать величину силы? У нас процесс столкновения быстротекущий, силы там действуют огромные, а главное — для реальных тел их сложно рассчитать, так как надо учитывать деформацию тел, скорость звука и кучу всего сложного. Вместо расчета самих сил можно рассчитать результат их действия — то есть изменение импульса тел. Ведь F=dp/dt, соответственно p2-p1 = integral(F*dt). При этом неважно, как именно изменялась сила в процессе взаимодействия и сколько времени длился этот процесс, а значение имеют только импульсы.
Глубина проникновения зависит от того, насколько мы «промахнулись» по времени, определяя момент столкновения. То есть, если объекты столкнулись где-то между предыдущим и текущим шагом симуляции, то глубина проникновения будет тем больше, чем ближе момент столкновения к предыдущему шагу. Если мы уменьшим шаг симуляции по времени — то у нас будут получаться меньшие глубины проникновения. Также, если нам повезет, и момент столкновения окажется почти точно равен текущему времени t — то тела проникнут друг в друга на совсем малую глубину. Таким образом, эта величина скорее зависит от параметров симуляции, чем от реального движения тел в непрерывном времени, поэтому мне непонятно, как и почему ее можно использовать для расчета сил взаимодействия. Ведь в реальном мире (и в его непрерывной ньютоновской модели) силы не зависят от того, что мы что-то там дискретно симулируем.
Что же касается точки приложения силы — то если важно точно знать ее местоположение — то конечно придется более точно найти время столкновения тел и найти соответствующие ему координаты. Это наверно можно вычислить из глубины проникновения.
Глубина проникновения зависит от того, насколько мы «промахнулись» по времени, определяя момент столкновения. То есть, если объекты столкнулись где-то между предыдущим и текущим шагом симуляции, то глубина проникновения будет тем больше, чем ближе момент столкновения к предыдущему шагу. Если мы уменьшим шаг симуляции по времени — то у нас будут получаться меньшие глубины проникновения. Также, если нам повезет, и момент столкновения окажется почти точно равен текущему времени t — то тела проникнут друг в друга на совсем малую глубину. Таким образом, эта величина скорее зависит от параметров симуляции, чем от реального движения тел в непрерывном времени, поэтому мне непонятно, как и почему ее можно использовать для расчета сил взаимодействия. Ведь в реальном мире (и в его непрерывной ньютоновской модели) силы не зависят от того, что мы что-то там дискретно симулируем.
Что же касается точки приложения силы — то если важно точно знать ее местоположение — то конечно придется более точно найти время столкновения тел и найти соответствующие ему координаты. Это наверно можно вычислить из глубины проникновения.
1. Время симуляции всегда одно и по умолчанию 60 кадров в секунду. Сила ~ Импульс
BulletDynamics/Dynamics/btDiscreteDynamicsWorld.h:
2. Практически все о чем мы говорим реализовано в этих строчках, что я привела в статье.
BulletDynamics/Dynamics/btDiscreteDynamicsWorld.h:
virtual int stepSimulation( btScalar timeStep,int maxSubSteps=1, btScalar fixedTimeStep=btScalar(1.)/btScalar(60.));
2. Практически все о чем мы говорим реализовано в этих строчках, что я привела в статье.
А зачем знать величину силы?Вы же сами через два предложения написали функцию от силы:
Ведь F=dp/dt, соответственно p2-p1 = integral(F*dt).
При столкновении dt может быть сколь угодно малым, а сила, соответственно, сколь угодно большой. А вот импульс и энергия изменяются на конечную величину.
Сила нужна не сама по себе, а для того, чтобы найти новые скорости тел, используя второй закон Ньютона. Но новые скорости тел можно найти и не прибегая к силам и ускорениям, а используя расчеты в терминах импульса. Рассчитать импульсы тел до и после удара, а от импульсов легко перейти к скоростям.
Годные теги :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как работает симуляция физики в играх на примере Bullet Physics