Russian Qt Forum

Добрый день

Уже неск лет используем движок Bullet (физика твердого тела). Пользователь задает 3D объекты, жмет бубочку "симуляция", и объекты начинают падать, летать, сталкиваться, отскакивать - все очень здорово. Но аппетиты растут - и вот потребовалась поддержка сцен с реально большим кол-вом объектов: 100K и более.

Ну что, написал я генератор и задал ему испускать чайники. Первые 50 фреймов - полет нормальный. Не real-time конечно, но сносно (еще мало объектов). Следующие 20 - уже минут 20. потом уже 40, потом ...ну мне машина нужна была работать, не дождался. В общем затык уже на 300 чайниках  :'( Понятно что это объект сложный, на простых (сфера, кубик) будет пошустрее, но все равно хотя бы до 100K далеко как до небес. А юзвери губы раскатали уже и на мульен  :'(

На форум тамошний я конечно зашел и спросил - ну обычный рез-т, т.е. нулевой. Точно такой же был для всех моих попыток в прошлом. Формально ответы были, типа "у меня тоже эта проблема" или "капитаны очевидность", но по существу там ничего не почерпнуть. Документация разумеется про/пере читана.

"Ну вот откуда я могу знать что делать? Это же Bullet, физика. Вот если бы я этим занимался...". Думается что вопрос все-таки ближе к программированию. Берутся open-source, интегрируются в приложение, и (иногда) даже успешно работают. А через какое-то время раз - и проблема, и хз что делать.

Как бы Вы поступили в таком случае?

Спасибо

100к падающих, летающих, отскакивающих 3D объектов. Судя по всему, софт, который справлялся бы с такой задачей без лагов, заработал бы миллиарды, если не более.

PS Вам не кажется, что тут затык в ресурсах, а не в программе?

Я с буллетом совсем немного работал, он меня не особо впечатлил честно говоря. Но тут я не спец, так что может сам накосячил. В любом случае, есть же уже аппаратная поддержка физики, например, у NVidia. Как насчет их решений?
Опять же, я в этой области совсем не спец, так что советовать ничего не могу, только предлагать.

Таки и я не спец, но интересовался этой темой давненько, года два-три назад. Более 5к объектов с физикой без тормозов создать я не смог.

PS 100к объектов сожрут любой ПК, за исключением суперкомпьютеров вроде ватсона. 

А я что, спец? :) Я же не стал физиком от того что "прикрутил" готовый движок. Ну, допустим, наняли физика - и что он должен делать? В том-то и дело что эти проблемы ложатся на программиста.

Если все объекты уникальны - то очень может быть. Но обычно они одинаковы (напр сыплющийся песок, дождь, снег) и, разумеется, объекты шарят свою геометрию, а то и вовсе юзают аналитическую форму. Поэтому расход может даже меньше чем у QGtaphicsItem

В общем виде это предложение "Давайте возьмем др движок". Не исключено что в конце-концов так и придется поступить. Но это весьма затратно в любом случае (как замены так и "2 движка")

В общем да - я бы тоже взял несколько движков и выяснил, какой из них наиболее подходит для конкретной задачи. А баги везде будут, мы же не в Нарнии)

А давайте чуть "сменим декорации" - предположим тормозит QGraphicsScene c 500K QGraphicsItem, не думаю что такое предположение слишком уж смело/фантастично. Тогда Ваш совет выглядел бы так
Получилась, на мой взгляд, полная фигня :) Легковесность и, Вы уж простите, хвастливость такого подхода бросаются в глаза. А что же с тоннами написанного Qt кода? А если его оставить то как срастить 2 фреймворка? Да, и сколько времени Вам понадобится на изучение "нескольких фреймворков"? Тут люди годами грызут букварь, а Вы вот так "взял и выяснил" :)

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

   

Отображение мое, результаты симуляции автоматически записываются и могут "проигрываться" отдельно, уже без запуска движка. Время показа кадра не превышает 0.5 сек. Тоже не блеск, но сейчас это не актуально.

[OFF]
"Дифуры"..... еще в политехе были НИРС и УИРС (какая-то там "Работа Студентов") - но все неизменно сводилось к одному: выходил докладчик и рисовал эти самые "дифуры" :) Мои попытки "вникнуть" имели примерно тот же успех как с темплейтами - да, что-то понял, но быстро устаю и "теряю нить". Видимо за истекшие много лет ничего не изменилось, и по-прежнему долбятся "дифуры"  :)
[/OFF]

Так вот, никаких (аналитических) дифуров в движке нет, а есть тупой, но бессмертный метод Эйлера. т.е. делаем шажок, проверяем граничные условия и.т.д. Сначала собираются все "contact pair(s)", т.е. 2 объекта находятся на критическом расстоянии и, вероятно, должны оттолкнуться. Профайлер показывает что время жрется на сборку контактов и их resolving. Ну и это еще начало "большого пути", там еще много чего (разрешение связок - constraint) - но до этого дело просто не дошло.

Лучше же Рунге-Кута 4-го порядка. :)

Неоптимальные места есть в любой программе, НО. Я вам так скажу, десктопный процессор сбособен обработать тысяч 200 сообщений в секунду (если эта обработка хоть что-то делает, например, пробежаться по всем полям и сложить сообщения в мапу). И то после определенных оптимизаций. Чтобы ещё увеличить производительность, надо отказаться от генерик кода и писать частные случаи - напирмер, мы читаем только 10е и 11е поля.
3д объект вещь несколько болеее сложная, чем сообщение с 20ю полями. Так что делайте вывыводы.
ЗЫ: я не говорю, что не надо оптимизировать, но есть некий предел, выше которого не перепрыгнешь.

Моё мнение, что 100к объектов в реалтайме без тормозов  на текущих мощностях вы не сделаете.

PS хотя на мой взгляд, если провести рассчёты заранее, вполне возможно.

Ну я это и имел в виду..Конечно немного странно, что в булете используют Эйлеровский метод, поскольку он самый неустойчивый.. Рунге-Кутта 4, как уже заметили, гораздо лучше, хоть и медленее.. (кстатии, это всё есть в бусте)

 
Но коли дело в отображалке, в этом механизме, то и думать нужно в этом направлении.. Что то упрощать, где то схитрить и т.д. во многом зависит от предметной части..
А чего Вы ещё хотели услышать?  :)

Ну "реалтайм" задача и не стоит, нужно получить скорость с которой время симуляции "приемлемо". Напр порядка секунды (на расчет 1 кадра) при 100K объектов. Это все равно не быстро, т.к. кадров может быть много. Но худо-бедно работать можно.

С эрудицией и умением поддержать разговор все нормально :) Но "перевод Bullet на дуст" как-то не привлекает..
Наоборот, я только заметил что она могла быть и лучше - но дело совсем не в ней (см мой предыдущий пост)
Я удивлен что пока не услышал вопроса который, на мой взгляд, должен быть задан немедленно  :)  Тем более что вопрос этот 100% программистский, к физике отношения не имеет

Посмотрел видео http://www.youtube.com/watch?v=PfezSJB21vk: на сцене 10000 планочек симулируются 50 секунд/кадр.
Вряд-ли вы с булетом сможете получить даже для 10К объектов кадр в секунду.

Именно Bullet и используется в Blender как движек физики.

Ну да. :)

А я вот что то совсем напротив, не удивлён  :)

Ну так за это и отвечают те самые дифуры + гран. условия.. Или всё же отображалка? Или как? Я просто не специалист в этих вопросах..

От себя хочу добавить.. Есть задачи: сейчас сам одной занимаюсь - есть кластер, всего 80 атомов (80*3 = 240 степеней свободы) и считается конфигурация с наименьшей энергией очень и очень прилично по времени.. (ну в зависимосчти от параметров). Я понимаю, что это не совсем та механика, что в булете, но..  

Ну что Вы тормозите на ровном месте? Отображалка ни при чем, забудьте про нее. И какая разница "дифуры" или нет? Если без дифуров ну никак низзя, то пусть они там будут - мне все равно  :)

Тут конечно кое-какие наметки имеются, правда совсем не густо. Простейшая задача: если объект улетел "куда-то далеко" его нужно удалить. Напр скатился с плоскости и продолжает падать под действием гравитации, и вот уже y = -1.0e+9. Отсечка таких объектов - простейшая оптимизация, но ее никто не отменял. Какие опции дать юзеру чтобы он мог удобно контролировать это "далеко"?

Вроде бы так: пусть юзер назначит "вмещающий объект" (часто кубик), все объекты за его границами автоматычно удаляются. Но такой объект неприятно виден (путается под ногами) в UI. Плюс Bullet поймет его как тело имеющее объем, и все что туда попало будет являться "пересечением". Придется расшивать стенки делая каждую объектом и.т.д. Как-то возни много, нет ли лучшего решения?

Ну вот, наступило дружное молчание :) Ладно, зайдем с др стороны. Ну хорошо, оставим без внимания мои потуги что-то оптимизировать конкретно, так сказать "алгоритмически". Примем песенку Верес'а "ну откуда же я могу это знать?"  :'(

Но позвольте Вас спросить - а какой вообще главный (современный, магистральный и.т.п.) метод ускорения программ в наше время? Причем не так себе, отгрызть  5% на inline (типа крутой знаток asm), а принципиально, в разы и больше? Или Ваш код и так весьма крут и никаких ускорений не требует?  :)

[OFF]
Наверное Хокс в отпуске
[/OFF]

Просто эти потуги так наивны, что уже и не смешно. :)

А вы думаете такие методы существуют для любых программ? :)

Вы давно замеряли сколько времени сортируются 100K double на одном ядре?

Если размышлять в контексте Bullet, то основной способ его ускорить  - это заюзать OpenCL (с использованием видеокарты или 2х)

Я все ждал, когда же спросят типа
Не дождался :) Так вот на ОДНОМ. Формально multi-threading был, но как-то optional. Т.е. в числе демосов (2.76 потом 2.81) был и пример с multi, но остальные демки без него. И в комментах так осторожно "можете попробовать multi (класс) из фолдера Extras"

Но в последнем билде (2.83.4) никаких multi уже нет, вместо этого, да, OpenCL. Видимо это становится стандартом для приличного софта. Однако портирование на OpenCL - дело совсем непростое, а проект никто не финансирует (ну это я так понял). Результат (за примерно 2 года работы): пока OpenCL реализация работает только на двух "high-end" картах. Когда на остальных (и будет ли) хз. И у меня незавидный выбор

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

- бросаться самому доводить OpenCL. С моим нулевым опытом в этой области выглядит нереально

- ничего не делать (часто самое мудрое решение) в смысле аппаратного ускорения, сидеть на 1 ядре. Уповать что в конце-концов Эрвин доделает. Но так меня будут бить за провальную скорость, и, возможно, ногами

Жду Ваших умных советов  :)

А разве это сможет решить ваши проблемы?
Если у вас скорость начинает проваливаться после 300 чайников на сцене. Даже задействовав еще 7 ядер вы сможете обработать 100K?

Вы бы попросили заказчика побить вас за скорости интернет соединений, уже давно хочется скачивать контент со скоростью 100 гигабайт в секунду... Может вы броситесь сюда и доведете здесь.

Алгоритмически, можно оптимизировать проведя все типы всех расчетов всех объектов заранее. Тогда останется только отображение. Но даже так, 100к объектов в реалтайме не получится :)

Скорость отображения меня сейчас не волнует. Для этого есть OpenGL который напр умеет рендеоить "инстансами", возможно 100K объектов (несложных конечно) даже будет и realtime (юзер же платил за карту сотни баксов). Но даже если нет, я просто выведу в мувик - вот и все.

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

Да, и вот еще о чем хотелось бы поговорить: а что значит "спец" в данном случае? Какими знаниями/умениями должен обладать такой спец? И я вот затрудняюсь ответить. Примерный ход мысли

Qt - ну здесь оно вообще никаким боком
std/boost - да в общем тоже. Может в бусте и есть что-то с похожими именами, но шансы это задействовать призрачны. (Во блин, учил-учил, а оно не пригодилось  :'()

физика...  казалось бы это все объясняет, типа
Увы, привлечение людей "от науки" малоэффективно. Да. физик расскажет массу интересных вещей, причем Вы с удивлением обнаружите что многое и сами это знали из школьного курса (хотя бы масса, сила, ускорение). Но никаких решений он не предложит, в алгоритмах и (тем более) реализациях разбираться не будет, не говоря уж об аппаратном ускорении.

Математика(и)... грубо говоря это примитивная попытка заморочить яйца "дифурами". То есть вот есть "дифуры" - они все и делают. И вообще вся природа вокруг нас - это все дифуры. Ну и опять песенка та же - мол, есть "некто" дающий дифуры/формулы, а программист только их реализует.

Так кем же он должен быть, этот легендарный "спец" - или это просто миф, таких нету  ???

Именно такая проблема как-то раз у нас и возникла. Пришлось отказаться от QGraphicsScene. Сделали свою имплементацию (грубо говоря, свой редактор айтемов) и проблема решилась :)