Миллион партиклов. Часть 1

imageХочу рассказать как я создавал, и потом переводил собственную систему частиц на GPU. Как я наивно думал просто будет сделать (мол чо там, двигать частицы, тююю). На самом деле о нюансах, возникающих при реализации, можно говорить очень много и долго, поэтому далее я расскажу только об решении проблем «узких» мест.

История вопроса


Заказчик разрабатывает динамические музыкальные фонтанные комплексы, которые управляются через dmx контроллеры по сценарию. Редактор сценариев он сделал самостоятельно. Но на практике создавать сценарии оказалось неудобным, потому что для того, чтобы видеть как получается нужно иметь целиком построенный и запущенный фонтан. Кроме того, если вдруг дизайнеру хореографу захотелось добавить дополнительные сопла для фонтана — то этого сделать уже практически невозможно. Поэтому заказчик захотел обзавестись модулем для моделирования фонтанов, чтобы хореограф мог без настоящего фонтана разрабатывать сценарии. В целом у меня вышло что-то в таком духе: вот видео того что было смоделировано Hawaii50.wmv, а вот то, что вышло в реале после конструирования фонтана: H5OClip.wmv


Требования


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

Первый блин


Сначала я сделал на ЦПУ простое создание частиц, потом все это дело ехало в вершинный буфер, который рендерился. При тестах это все работало отлично, на практике оказалось непригодным. Если вы посмотрите на видео H5OClip.wmv, то обратите внимание, сколько источников света светится одновременно. Часто число доходит до сотни и более. При этом один источник часто «покрывает» сразу несколько струй фонтанов, а ведь каждая струя — это по сути эмиттер. А теперь представьте, что 150-200 струй одновременно создают частицы. Сколько надо частиц для того, чтобы изобразить одну струю? На практике было установлено, что для сносного отображения одной струи, бьющей в полную мощь нужно в среднем 5к частиц. И того для 150 струй получаем 750000 частиц. Понятно что надо закладываться на минимум на 150 струй.

Первая версия работала так. Сначала шел процесс создания частиц. Для каждой частицы было поле, в котором хранилась миллисекунда, в которую частица умрет. Определяем количество частиц, которые создал эмиттер за прошедший кадр, и бежим с начала массива до тех пор, пока не создадим все частицы. Если встречаем мертвую частицу (текущее время > времени смерти), то заполняем её новым временем смерти, задаем начальные координаты и начальную скорость. По сути частица создана. Если массив заканчивался, и не все частицы еще созданы, то выделяем дополнительно еще кусок памяти. Если создали все частицы, то бежим до конца буфера и запоминаем индекс последней живой частицы. Если индекс последней живой частицы много меньше длинны массива, то укорачиваем массив. Этот индекс пригодится нам в дальнейшем, чтобы не бегать по всему буферу.
Далее шел одновременный процесс движения частицы, и заполнения VBO (Vertex Buffer Object). Бежим по массиву, если частица жива — двигаем её и заполняем её в VBO, иначе пропускаем. Проверяем не весь массив, а до индекса последней живой частицы.
Итак VBO готов, рендерим его. На практике (а у меня тогда был Athlon 64 x2 3800, это 2.0 Гц ядро), если мне не изменяет память, то выходило около 100-150к частиц при 25-30FPS, что неуд.
Поэтому условимся, что нам нужно как-то манипулировать в пике с 750к частиц, либо придумывать альтернативу. Поэтому переходим ко второму блину.

Второй блин


Анализ

Сначала я провел тесты, что именно сжирает финальный FPS. Итак, нагрузки, которые явно видно:
  1. Создание/смерть новых частиц
  2. Движение частиц
  3. Заполнение вершинного буфера
  4. Рендер частиц

Самым «тормознутым» оказалось конечно же движение частиц. На втором месте шло создание/смерть новых частиц. На третьем заполнение вершинного буфера. Что же касается рендера — то тут все было шатко. Поскольку фонтаны в 3д, то они могут быть на разном расстоянии от камеры, и частицы надо масштабировать по глубине. Если камеру направить сверху вниз, так, чтобы струи били прямо в камеру, то фпс падал. Оно и понятно, ведь частицы были огромными, и филлрейт соответственно был огромный. В обычном же случае камеру никто так никогда не направлял (в будущем я провел оптимизации и для таких случаев) и на FPS рендер практически не влиял, потому что GPU выводит изображение асинхронно, и со своей работой успевал справляться за время время работы CPU.

Попытка оптимизации

Первым же делом я решил оптимизировать математику перемещений. Но математика была настолько проста, что оптимизировать там оказалось практически нечего. Компилятор прекрасно оптимизировал все это дело в asm код. Далее возникла мысль не бегать по массиву дважды, а создавать, двигать частицы и заполнять буфер за один проход. Сказано — сделано. Но прирост скорости можно было разглядеть только под микроскопом. С заполнением вершинного буфера никаких оптимизаций в голову не приходило. Можно конечно было попробовать использовать один буфер для VBO и для вершин, но тогда надо было бы мертвые вершины выводить за viewport, и этот вариант мне казался еще более тормозным. Да и накладные расходы на заполнение VBO были мизерными. Теоретически (по флопсам) был еще большой запас, но за теми синтетическими цифрами угнаться ну никак не получалось.
Можно было конечно решить это так же в лоб, распараллелить на 4 потока, поставить в минимальных системных требованиях к программе CPU с 4-мя ядрами, и частотой на ядро в 2.5ГГц, но мне этот путь категорически не нравился.

Удачная попытка оптимизации

Итак, надо уменьшать количество частиц. Понятно, что фонтаны расположенные далеко, не нуждаются в большом количестве частиц. Можно рисовать меньшее количество частиц чуть крупнее, но если камера резко приблизится к фонтану, то мы должны показывать больше частиц, кажется все логично и понятно, но проблема заключается в том, что эти самые невидимые частицы мы должны как-то двигать. Иначе при приближении они у нас будут в начальной точке. И опять упираемся в то, что на CPU нам надо манипулировать со всеми частицами. А что если нам вообще не двигать частицу, а просто вычислять её позицию по уравнению движения.
Простейшее уравнение движения: x = x0 + v0*t + 0.5*a*t*t. Это был бы действительно отличный вариант, если бы не одно но. Заказчик захотел «трение о воздух», потому что для струй с низким углом к горизонту результат при моделировании сильно разнился с реальным результатом. Сила вязкого трения F = -bV, для одной среды, одинаковых по размеру и форме капель грубо можно сказать что ускорение от трения это a = kV, где k некоторый коэффициент. В итоге наше простое уравнение движения превращается в монстра (текущая формула в шейдере: NewCoord = ((uAirFriction*aVel + G)*(exp(uAirFriction*dt)-1.0)/uAirFriction — G*dt)/uAirFriction + aCoord;). И несмотря на дикую формулу я уже получил ощутимый прирост производительности только за счет того, что я считал позицию только тех вершин, которые я действительно буду рисовать. Для фонтанов, расположенных на расстоянии N от камеры мы берем каждую вторую частицу, для фонтанов расположенных на расстоянии 2N каждую четвертую и т.д. В итоге получилось что-то порядка 500-700к живых частиц при 20-30FPS, что вполне неплохо. Приведенная цифра на самом деле вышла сильно плавающей, и все зависело от расположения фонтанов в кадре, но в целом производительность вполне удовлетворяла потребности.

Третий блинчик


Не смотря на то, что задача была уже реализована, и заказчик был доволен, ради собственного спортивного интереса я решил переписать рассчеты на GPU. Итак, мне понадобился рендер в вершинный буфер. По вершинному буферу с начальными значениями (начальная позиция, начальная скорость, начальное время, конечное время) делаем рендер в вершинный буфер, хранящий только текущие координаты. Потом используя полученный буфер рендерим собственно сами частицы. Простая реализация влоб (без уменьшения кол-ва частиц в зависимости от расстояния) дала 1кк частиц при 40-50FPS на моей GF250. Теперь на CPU нам нужно только «рождать» частицу, и таких частиц на каждый кадр получается довольно мало. А вот сделать разное количество частиц, в зависимости от расстояния тут уже не так тривиально. Ведь у нас получается не цельный массив частиц, а массив с «дырками» (дырками из мертвых частиц). Я вижу пару решений для данного случая, но реализовать не успел из-за нехватки времени. Если хабрасообществу будет интересно посмотреть на дальнейшие реализации, то при появлении свободного времени постараюсь испечь четрвертые и пятые блины (да еще с демками).

Выводы


  • В системах частиц узкое место отнюдь не шина, как я полагал изначально (не знаю как для AGP, но для PCIe16 оно не ощутимо), а перемещение частиц.
  • Филлрейт в системах частиц может существенно «сожрать» производительность. Рекомендуется оптимизировать этот момент.
  • Задачи, которые хорошо параллелятся зачастую «в лоб» решаются на GPU быстрее, и подобные узкие места всегда лучше перевести на GPU (но это не значит что на GPU надо все делать в лоб).
  • Самый главный вывод, сначала думать, потом делать. Оцени я сначала количество частиц — я бы сразу думал об оптимизации, и первого блина бы просто не было.


p.s. Извиняюсь за отсутствие кода и демок. Понимаю что читать рассматривая картинки — интереснее, но версии старого кода не сохранились, писал можно сказать по памяти своих «исканий». Соответственно старых скриншотов/видео/демок нет, ну а текущее видео можно найти на сайте заказчика. В следующих статьях постараюсь исправиться.

upd. Залил вышеупомянутое видео на YouTube



upd2. Скрин без потерь качества:

Верхний скрин — попытка добавить гидравлические удары и сделать красивее и реалистичнее. Считаю попытку неудачной из-за сильного падения производительности.
Нижний скрин — посути третий блин в выше описанной статье.
Поделиться публикацией
Комментарии 35
    +2
    Ох, лучше видео выложить на youtube
      +1
      Присоединяюсь. У меня оно так и не открылось толком.
      +1
      Глупый вопрос, а не проще ли было параболами их рисовать?
        0
        Парабола для GPU — это ломаная линия, а это несколько вершин. Ломаную линию точно так же пришлось бы рассчитывать в реалтайме. Так что я думаю что не проще
        +3
        Это просто потрясающе. Спасибо.
          +1
          Интересное сравнение. А в какой среде, на каком языке все это делалось?
          PS танец реальных фонтанов заметно «грязнее» получился :-)
            +2
            Сам модуль с частицами написан на Delphi. Работа с модулем шла из программы, написанной на vb.net через COM. Грязнее вышло прежде всего из-за компрессии видео. В окне оно смотрится значительно чище. К сожалению видео записывал не я. Конечно 100% реализма получить не удалось, но то что уже вышло — уже удовлетворяет заказчика. Я бы лично еще хотел сюда добавить решение с гидравлическими ударами. Их хорошо заметно на втором ролике на красных фонтанах, когда струя резко меняет свою мощность. По падающей воде происходит гидравлический удар от набирающей силы струи, получается довольно красивый эффект, и много много мелких капель вокруг.
              0
              Еще показалось, что грязнее из-за того, что в реальных условиях больше случайности в плане высоты и разброса частиц. Но заказчику виднее, устраивает — значит гуд :-)

              Ого, бэйсик! А зачем такие сложности, если не секрет? Почему не сразу все на дельфи? Или программу на VB писали не вы и до появления вашего модуля?
                0
                Да, программу на VB писал не я, а сам заказчик. И нужно было добавить визуализатор. VB я знаю только на уровне синтаксиса, а Delphi очень хорошо, кроме того я знал COM и соединить Delphi и VB для меня большого труда не представляло. Поэтому именно такой выбор.
            0
            Что за музыка?
              +2
              midomi подсказывает что это The Ventures — Hawaii Five-O
              0
              Здорово. А на какой системе проводились измерения FPS?
              Заказчик ведь может сделать апгрейд процессора и памяти и тогда FPS внезапно возрастет.
                0
                CPU версии (первые два блина из статьи) проводились на AMD Athlon 64 x2 3800 (2.0ГГц на ядро). Видеокарта если мне не изменяет память — была такая же как и сейчас, GF250.
                GPU верисия писалась и тестировалась уже на AMD Athlon II X4 630 (2.8ГГц на ядро), и на той же видеокарточке GF250.
                Не было цели провести точные рассчеты производительности, было лишь требование, чтобы оно работало комфортно на современном железе. Ведь ПО нужно было не для продажи в офисы, но и суперкомпьютер собирать для этих целей было бы глупо. Так что пусть растет FPS от апгрейдров, я не против.
                +1
                Клёво вышло!
                  0
                  В CPU версии вы использовали пул частиц или выделил память в Realtime?
                    0
                    Ну в реалтайме память выделять — это самоубиство. Конечно же что-то типа пула. Поскольку частицы рождаются и умерают в процессе полета, некоторые раньше, некоторые позже, то посреди массива частиц образуются уже мертвые частицы. Я пробегаю по массиву, и оживляю частицы. Такой вот пул. Ну а если не хватает «трупов» частиц, то выделяю дополнительно кусок памяти, равный 20% от размера текущего массива частиц.
                      0
                      Понятно, на всякий случай спросил. Сегодня сяду вечером, гляну сколько может Ogre выдать с вычислениями на CPU, интересно стало.
                        0
                        Поделитесь потом цифрами? Мне тоже любопытно
                          0
                          Конечно. Ещё бы интересно глянуть на fxpression — платный редактор частиц и плагин к Ogre (€19.95 не так много).
                    0
                    Очень здорово! Спасибо автору за статью. Только недавно любовался свето-музыкальным фонтаном, и стало интересно, как их моделируют.
                      0
                      Как Вы реализовали разбегание частиц в струе?
                      Я имею в виду, что из трубы (форсунки, сопла) все частицы вылетают приблизительно в одном направлении и с одной скоростью.
                      Потом, по мере взлета они замедляются и струя распадается (зонтиком, воронкой), частицы раздетаются в стороны и начинают падать.
                      Я не увидел этой составляющей в уравнении движения. В моем понимании, уравнение должно быть трехмерным, и оперировать с X, Y и Z. Или как минимум с X и Y, а результирующая вращаться вокруг оси Z.
                      Для разбегания частиц использовался рандом?
                        0
                        Ну в уравнении движения этой составляющей и не будет. Просто вектор начальной скорости задается с некоторым разбросом, и у каждой частицы своя начальная скорость.
                          0
                          Вектор изначально разный у каждой частицы… понятно, оригинально!
                          А почему практически не видно падающих на землю частиц? Они исчезают к концу первой трети полета вниз.
                            0
                            В первом варианте они падали на землю, но в реальных фонтанах падающую воду видно хуже, и так пожелал именно заказчик. Поэтому мы решили, что после прохождения верхней точки у частиц надо увеличивать прозрачность, чтобы постепенно они стали невидимыми.
                              0
                              Прозрачность… гениально. Я думал мне так на мониторе кажется, что они как бы растворяются))
                                0
                                Монетезируйте немедленно.
                                Соберите все в одну программу (думаю, найдутся еще программисты с музыкальным образованием, вроде меня) которые с удовольствием перепишут на Delphi модуль с VB.
                                Или все переписать на JAVA.

                                И мы разукрасим наши города поющими фонтанами!
                                И может быть вернули бы это чудо к жизни. Кто постарше, то наверно помнит, каким он был "золотым"…
                                Как это было бы хорошо…
                                  +1
                                  Программа же используется для моделирования, а не для того чтобы произвести вау эффект на обычного пользователя. Так что от просто визуализатора толку мало. Это надо заниматься разработкой самих фонтанов. А для этого надо разбираться во всей этой гидравлике, связать все это с dmx контроллером и написать редактор сценариев для dmx контроллера. Монетизировать тут пока нечего, да и потом, сам визуализатор лично для меня итак «монетизирован». Я же не за спасибо писал его ;)
                          0
                          Потрясающе!
                          Вот бы еще такой плагин для Синемы… Эх.
                            0
                            CINEMA 4D из коробки может смоделировать куда более красивые частицы…
                            0
                            опа
                            Винницкий фонтан
                              0
                              H5OClip хочу поставить себе на скринсейвер
                                0
                                Поздравляю! Вы проделали долгий путь и добились превосходного результата.
                                  0

                                  Извините может не по теме, но как достигается разная высота струи на одном контуре? ШИМ на клапан сброса?

                                    0
                                    Не могу сказать точно. Знаю только что управляется оно все через программируемый dmx контроллер. Могу лишь предположить что дальше с помощью таких штук: https://www.amazon.com/s/ref=nb_sb_noss?url=search-alias%3Daps&field-keywords=Electric+Solenoid+Valve
                                      0
                                      Да я знаю что там клапана 2 на каждой форсунке. Один открывается другой закрывается и наоборот. Но вот не понятно как на каждую форсунку разный делают столб. Наверно всетаки ШИМ на сбросном клапане. Нужно погуглить. Думал ты в курсе.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое