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

в 20:52, , рубрики: GPU вычисления, Алгоритмы, Анимация и 3D графика, высокая производительность, система частиц, метки: ,

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. Извиняюсь за отсутствие кода и демок. Понимаю что читать рассматривая картинки — интереснее, но версии старого кода не сохранились, писал можно сказать по памяти своих «исканий». Соответственно старых скриншотов/видео/демок нет, ну а текущее видео можно найти на сайте заказчика. В следующих статьях постараюсь исправиться.

Автор: MrShoor

Поделиться

* - обязательные к заполнению поля