Как работает симуляция физики в играх на примере Bullet Physics

[@igordata]

> Как работает симуляция физики
> Первый этап — это найти пересечение
> Отлично, все пересечения найдены

Рисуем кружок, рисуем остаток совы. Я после такого заголовка и видео уж было ожидал осмысленного объяснения, как именно происходит борьба с O(n^2) на таком огромном числе объектов. По ссылкам информация чисто алгоритмическая. Может расскажете, как отсекаются ненужные проверки? Как это всё ускоряется?

[@sakurasun]

Тут описано три шага: Broadphase, Narrowphase, Solver. Я опустила управления памятью. Я не рассмотрела суставы и трение. Быстрый поиск поиск в статических мешах. Что ваш упрек заслуженный и я попробую исправится. AxisSweep3 это 16 битный алгоритм, который забивает большую AABB коробку на 16384 маленьких коробки и все объекты помещает в эти коробки и так и ищет. Чем то напоминает хеш таблицу. Если 16384 коробки мало, то есть bt32BitAxisSweep3 32 битный аналог.

[@evocatus]

Я слышал, что AMD вместе с Bullet делает свою альтернативу PhysX, которая будет ускоряться на «красных» GPU

[@sakurasun]

Создатель Bullet в начале работал на Havok. Потом он работал в Sony, потом в AMD. AMD как раз хотели добавить Open CL в Bullet, Open CL не использовала, не знаю. Вот видео вероятно как результат той работы. www.youtube.com/watch?v=8jGZv1YYe2c 110 тыс кубиков это очень много для симуляции в реальном времени

[@KvanTTT]

Зачем нужна полная матрица алгоритмов определения коллизий, когда достаточно треугольной, так как операции коммутативны?

[@MrShoor]

Вы же понимаете, что это таблица указателей на функции, да?

[@sakurasun]

Это скриншот из PDF

Вообще вопрос касается интересной проблемы. Ведь если мы имеем две коробки и алгоритм boxbox, то какой будет перпендикуляр касания, какая коробка первый параметр и какая коробка второй параметр. Часто так получается, что 3 сеукнды одна коробка первый параметр, и все красиво скользит потом, что где то далеко меняется, и это меняет параметры в boxbox местами и все летит в тар-тарары.

[@shus]

Интересные блики на шаре в Close-up: from below

[@inook]

Это не гладкая сфера

[@OldFisher]

Почитал список похожих публикаций. Посмотрел на список тегов. Сделал выводы.

[@Mrrl]

А зачем там lowerLimit?

[@sakurasun]

Что бы я сказала, что я понимаю, то нет. Мне кажется lowerLimit раньше не было и код был короче. Об этом и написала.

c.m_appliedImpulse — тут мы сообщаем с каким импульсом мы обработали коллизию. (Например, громкость удара)

Но получается, что если сила меньше, то ее фактически в тайне увеличивают до какого то миниума.

Зачем? Вопервых в буллет очень, хорошо борются с denormal numbers. Тут ни что не касается в ноль. (trashhold) Если интеловские процы нормально обрабатывают denormal, то многие другие например армы переходят в soft и это прерывание им стоит 100 тактов.

Во вторых? я вообще не понимаю этого кода, что тут отвечает, что нет вибраций и резонанса. Если выстроить 10 кубиков в столбик то, они спокойно стоят и эти все силы и импульсы не начинают резонировать.

[@MichaelBorisov]

Когда-то на третьем пентиуме я столкнулся с тем, что обработка денормальных чисел жутко тормозит. В десятки и сотни раз медленнее. С тех пор исправили?

[@cheremin]

Насколько я понимаю (и по воспоминаниям о своем собственном опыте): когда рассчитываешь столкновения исходя из импульсов очень важно, чтобы столкновения оставались «моментальными» — т.е. два тела, которые на предыдущем шаге не соприкасались, на этом шаге соприкасаются — на следующем шаге они должны уже снова перестать соприкасаться. Потому что если вы на текущем шаге симуляции обработали столкновение тел, поправили их импульсы, но с этими импульсами тела не успели разойтись до следующего шага, то вы получаете на следующем шагу ситуацию, когда у вас два тела по координатам сталкиваются, а по импульсам — расходятся (вы же их «отразили» на предыдущем шаге). С точки зрения импульсного подхода _эту_ ситуацию уже сложновато корректно разрулить (она просто нефизическая). В идеальном мире такого просто не должно возникать. Но в реальной симуляции с конечными шагами по времени, со внешними силами (например, гравитацией) — эта ситуация возникает часто. Поэтому, видимо, минимальный импульс был введен для того, чтобы (почти)наверняка развести тела которые сталкиваются с малой передачей импульса.

[@jakobz]

>И тут встает вопрос, если все так просто, как получается, что можно выложить в столбик кубики и они себе спокойно стоят и не разлетаются?
>Я покажу, что за всю эту магию отвечает маленький кусочек кода!

Я так понимаю этот маленький простой кусочек кода, вызывается большим и сложным куском кода, который решает какой импульс к каким объектам применить :)

[@kashey]

Самое сложное в collision detection это penetration depth. И самое веселое.

[@MichaelBorisov]

Почему веселое и сложное?

Если обнаружено проникновение — значит где-то в момент времени между предыдущим и текущим шагом симуляции произошло столкновение. В первом приближении можно округлить момент столкновения до предыдущего или текущего и применить правила взаимодействия. Или это слишком грубое приближение?

Еще как вариант — попытаться найти момент столкновения более точно, интерполируя движение данных конкретных тел между шагами симуляции. Или это слишком затратно по ресурсам?

[@MrShoor]

В первом приближении можно округлить момент столкновения до предыдущего или текущего и применить правила взаимодействия. Или это слишком грубое приближение?

Еще как вариант — попытаться найти момент столкновения более точно, интерполируя движение данных конкретных тел между шагами симуляции. Или это слишком затратно по ресурсам?

Это ничего не даст. Суть penetration depth — найти точку к которой нужно приложить силу, и глубину проникновения, чтобы знать какую именно силу приложить (а с учетом трения — там вообще сказка вырисовывается). Я когда сам писал свой физический двиг — уперся именно в этот момент. Стек предметов у меня либо вибрировал, либо проминался и был меньшей высоты, чем надо. Ну и в довесок были проблемы с трением.

[@sakurasun]

Я вот в поисках версии буллета где было комментов по больше, боюсь солгать, но мне кажется, что про солвер было сказано, что он получен эксперементально перебором. Если глубину проникновения двух сфер легко получить, а глубину проникновения двух кубов уже сложней, тогда вопрос: Что считать глубиной? Напрашивается ответ, нам нужно расстояние на которое следует вытолкнуть тело из коллизии,

и тут мы начинаем думать, а ведь начальная скорость не всегда ноль, и после того как мы приложим импульс, какую скорость мы хотим получить.

И наш алгоритм не должен подменять трение. Трение там отдельно реализовано.

Если рассматривать самый простой вариант башня из 10 кубов, что бы она держалась, какая должна быть скорость кубов, ведь у нас всего 30-60 симуляции в секунду. Если первый куб чуть просел и его пихнули вверх, то он немного вибрирует, если нет дампинга, а куб который лежит на этом кубе уже вибрирует на вибрирующей поверхности, легко может случиться что его часто это резонансная частота. (резонанс зависит только от массы, а она может быть любой)

Самый похожий код на код дампинга это

 const btScalar deltaVel1Dotn	=	c.m_contactNormal.dot(body1.internalGetDeltaLinearVelocity()) 	+ c.m_relpos1CrossNormal.dot(body1.internalGetDeltaAngularVelocity()); 

[@MichaelBorisov]

А зачем знать величину силы? У нас процесс столкновения быстротекущий, силы там действуют огромные, а главное — для реальных тел их сложно рассчитать, так как надо учитывать деформацию тел, скорость звука и кучу всего сложного. Вместо расчета самих сил можно рассчитать результат их действия — то есть изменение импульса тел. Ведь F=dp/dt, соответственно p2-p1 = integral(F*dt). При этом неважно, как именно изменялась сила в процессе взаимодействия и сколько времени длился этот процесс, а значение имеют только импульсы.

Глубина проникновения зависит от того, насколько мы «промахнулись» по времени, определяя момент столкновения. То есть, если объекты столкнулись где-то между предыдущим и текущим шагом симуляции, то глубина проникновения будет тем больше, чем ближе момент столкновения к предыдущему шагу. Если мы уменьшим шаг симуляции по времени — то у нас будут получаться меньшие глубины проникновения. Также, если нам повезет, и момент столкновения окажется почти точно равен текущему времени t — то тела проникнут друг в друга на совсем малую глубину. Таким образом, эта величина скорее зависит от параметров симуляции, чем от реального движения тел в непрерывном времени, поэтому мне непонятно, как и почему ее можно использовать для расчета сил взаимодействия. Ведь в реальном мире (и в его непрерывной ньютоновской модели) силы не зависят от того, что мы что-то там дискретно симулируем.

Что же касается точки приложения силы — то если важно точно знать ее местоположение — то конечно придется более точно найти время столкновения тел и найти соответствующие ему координаты. Это наверно можно вычислить из глубины проникновения.

[@sakurasun]

1. Время симуляции всегда одно и по умолчанию 60 кадров в секунду. Сила ~ Импульс
BulletDynamics/Dynamics/btDiscreteDynamicsWorld.h:

virtual int	stepSimulation( btScalar timeStep,int maxSubSteps=1, btScalar fixedTimeStep=btScalar(1.)/btScalar(60.));

2. Практически все о чем мы говорим реализовано в этих строчках, что я привела в статье.

[@MrShoor]

А зачем знать величину силы?

Вы же сами через два предложения написали функцию от силы:

Ведь F=dp/dt, соответственно p2-p1 = integral(F*dt).

[@Mrrl]

При столкновении dt может быть сколь угодно малым, а сила, соответственно, сколь угодно большой. А вот импульс и энергия изменяются на конечную величину.

[@MichaelBorisov]

Сила нужна не сама по себе, а для того, чтобы найти новые скорости тел, используя второй закон Ньютона. Но новые скорости тел можно найти и не прибегая к силам и ускорениям, а используя расчеты в терминах импульса. Рассчитать импульсы тел до и после удара, а от импульсов легко перейти к скоростям.

[@ankh1989]

Годные теги :)