вторник, 17 июля 2012 г.

Частицы. Часть третья, миллионы частиц.

Часть первая, и снова тесты
Часть вторая, если очень хочется
Часть третья, миллионы частиц
Часть четвертая, полевые испытания
В предыдущей части мы с вами разобрали основные методы визуализации частиц, так же определились что время вывода частиц является сумой времени необходимого на передачу этой частицы в видеопамять и времени, необходимом для вывода этой частицы. Но это в идеальном случае, если предположить что у нас уже имеется готовый массив с координатами. Обычно это не так.
Рассмотрим простою задачу - мы хотим сделать фонтан частиц.
Из начальных условий нам достаточно знать силу, с которой эти частицы выталкиваются, и массу этих частиц. Так же на частицы будет действовать сила притяжения. Решение нашей задачи можно записать в таком виде:
a=F/m; P(t) = P0 + V*t + (a+g)*t*t/2;
Величины F,a,P,P0,V0,g - векторные, вектор g равен (0,-10,0).
Распишем это уравнение движения по координатам:
Px:=P0x+Vy*t+ax*t*t/2;
Py:=P0y+Vy*t+(ay-10)*t*t/2;
Pz:=P0z+Vz*t+az*t*t/2;

Эти выражения нам придется применить к каждой частице. Когда их десяток это не имеет значения, но когда счет идет на тысячи, то это время уже нужно учитывать. Бывают и более сложные выражения, к примеру, если мы захотим заставить частицу подниматься по спирали, то нам потребуется вычисление квадратного корня, синус и косинус угла. Это еще более ресурсоемко, а если туда добавится еще и турбулентность, или мы захотим визуализировать решение уравнений Навье-Стокса....

Таким образом, суммарное время визуализации частицы будет определяться как:
    TotalTime = CPUTime + BusTime + RenderTime
При этом GPU большую часть времени будет простаивать (хорошо если соблюден баланс между нагрузкой CPU и GPU, и в момент подготовки данных GPU будет чем заняться, но часто это не так), и это убьет всю производительность. Какие тут возможны решения? ну во-первых считать не на каждом кадре - сделано, фпс всеравно вблизи 0, что еще можно сделать? Выполнять расчеты в нескольких потоках, сделали, загрузили все процессорные ядра, если запущена игра то даже блокнот нельзя открыть, но фпс всеравно в районе 10 кадров для 50к частиц на пустой сцене. Что можно еще сделать? Вспомним первую часть статьи, там я говорил что можно повысить производительность за счет асинхронной работы, в частности, что пока загружается новая порция геометрии мы можем рендерить уже загруженную геометрию. Здесь мы можем применить тот же принцип, но для связки CPU+BUS. Давайте разберемся как это сделать.

В первой части мы обновляли данные в видеопамяти посредством команды glBufferSubData, эта команда позволяет загрузить в видеопамять блок данных, но это не единственный способ. Кроме этого существует способ отобразить данные из видеопамяти в адресное пространство CPU, в результате мы сможем работать с видеопамятью как с обычным указателем (на чтение/запись). Для этого служит специальные команды glMapBuffer+glUnmapBuffer. Чтоб была понятна аналогия с BufferSubData вот небольшой пример функции:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
procedure UpdateVBOBuff(BuffId: integer; data: pointer; 
  offset, size: integer; MapBuffer: Boolean=false);
var p:pointer;
  i: integer;
begin
  glBindBuffer(GL_ARRAY_BUFFER, BuffId);
  if MapBuffer then begin
    p := glMapBuffer(GL_ARRAY_BUFFER, GL_WRITE_ONLY);
    for i:=0 to Size-1 do PByteArray(p)[offset+i]:=PByteArray(data)[i];
    glUnMapBuffer(GL_ARRAY_BUFFER);
  end else begin
    glBufferSubData(GL_ARRAY_BUFFER, offset, Size, data);
  end;
  glBindBuffer(GL_ARRAY_BUFFER,0);
end; 

Сама процесс отображения памяти очень ресурсоемкий, потому при необходимости обновить небольшой объем данных я бы рекомендовал использовать glBufferSubData, но достоинство отображения буфера в оперативную память в другом - здесь я специально использовал поэлементное копирование данных из буфера "data" вместо использования команды "Move", чтоб показать принципиальную возможность менять значения отдельных элементов в видеопамяти.

Что нам это дает - во-первых это позволяет снизить объем обновляемых данных, обновляя только измененные элементы, тем самым разгрузив шину. Во-вторых - это позволит параллельно с вычислениями производить загрузку данных в видеопамять, тем самым существенно сократив сумму "CPUTime + BusTime", но это лишь временные меры, помогающие в определенных ситуация, но не решающие основную проблему - что делать если нужно много и со сложными законами движения.

Одним из таких способ является интерполяция значений вершинных атрибутов. В чем суть подхода - вместо того, чтоб на каждом кадре рендера решать систему диффуров мы делаем расчеты для кадра с некоторым +dt, к примеру +15 кадр, тем самым мы имеем два набора значений, текущее положение и то что будет через некоторое время dt, дальше мы просто делаем линейную интерполяцию между этими положениями:
     CurrentPos = FirstPos*(1-t)+NextPos*t;
Как только мы достигнем кадра, для которого было рассчитано положение NextPos - меняем этот массив с FirstPos и вычисляем новый массив NextPos для нового временного интервала.
Таким образом мы в 15 раз разгрузим CPU без существенного ухудшения качества анимации частиц (в крайнем случае можно уменьшить интервал интерполяции для улучшения качества анимации).

Процессор мы разгрузили, а как быть с шиной? Тут нам на помощь вновь приходят шейдеры (привыкайте, дальше мы будем к ним обращаться все чаще и становиться они будут все сложнее). Задачу интерполяции атрибутов мы можем целиком переложить на шейдер, в этом случае мы во-первых воспользуемся всеми прелести распараллеливания вычислений на шейдерных процессорах, во-вторых - полностью разгрузим CPU, в третьих - в несколько раз разгрузим шину, ведь нам теперь, вместо передачи интерполированных данных на каждом кадре, достаточно загрузить данные в видеопамять только в контрольный момент (+dt) всего несколько раз в секунду, все остальное сделает за нас GPU.

Чтоб реализовать данный подход нам достаточно лишь обеспечить одновременное нахождения в видеопамяти обоих буферов VBO (с начальной и конечной позицией), тогда второй буфер можно присоединить в качестве атрибутов первого буфера (общих или пользовательских). Рассмотрим пример:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
FrameTime:=GetTime; //сохраняем время загрузки новых данных
Data:=UpdateData(FrameTime+dt); //вычисляем новое положение для кадра + dt
UpdateVBO(buff2, Data); //загружаем в VBO данные кадра +dt
.... //основной цикл рисования
ShaderApply; //применяем шейдер
glEnableClientState( GL_VERTEX_ARRAY );
glBindBuffer( GL_ARRAY_BUFFER, buff1 ); //биндим буфер с начальными координатами
glVertexPointer( 3, GL_FLOAT, 0, nil );
glEnableClientState(GL_NORMAL_ARRAY);
glBindBuffer( GL_ARRAY_BUFFER, buff2 ); //вместо нормали конечный буфер
glNormalPointer( GL_FLOAT, 0, nil );
glDrawArray(...);//Рисуем всю геометрию с шейдром
ShaderUnApply;
if GetTime - FrameTime >= dt then begin
  temp:=buff1; buff1:=buff2; buff2:=temp; //меняем буферы местами
  UpdateVBO(buff2, Data); //загружаем в конечный буфер новые данные.
  FrameTime:=GetTime; //обновляем время
end;
...//конец цикла рисования

Здесь buff1 и buff2 соответственно идентификаторы вершинных буферов VBO для начального и конечного положения. При необходимости повторяем эту процедуру для всех меняющихся атрибутов, будь то цвет, угол поворота или текстурные координаты.

И выводим эту геометрию с таким вот простым вершинным шейдером:

uniform float t;
...
vec3 v1 = gl_Vertex.xyz;
vec3 v2 = gl_Normal.xyz;
vec3 vert = mix(v1,v2,t);
....
Остальное аналогично описанному в предыдущей части статьи. Так как оба буфера находятся в видеопамяти, то эта процедура выполнятся чрезвычайно быстро (1 инструкция GPU). При желании можно заменить линейную интерполяцию на полиномиальную, или сферическую (через кватернионы), чтоб максимально приблизить результат интерполяции к поведению частиц.


В играх, обычно в такой точности нет необходимости (так как поведение частиц часто носит хаотичный порядок), потому вполне хватает линейной интерполяции, но описанный подход открывает перед нами другие возможности - как на счет того, чтоб вообще избавиться от хранения данных в системной памяти, с последующим насилованием шины PCIEx, и перенести все расчеты траектории движения на GPU, оптимизированное для многопоточных вычислений? Было бы неплохо, но как? Использовать CUDA или OpenCL? Не в этот раз, мы обратимся к истоку технологий GPGPU, когда исходные данные передавались и выводились через текстуру, и к технологии PBO, позволяющей скопировать данные из текстуры в буфер VBO, минуя промежуточное копирование в системную память. Вместе эта технология носит название "рендеринг в вершинный буфер" или сокращенно R2VB. Частично я уже упоминал об этой технологии, когда приводил пример аппаратной тесселяции с использованием OpenGL1.4, теперь рассмотрим второе ее применение.

Детальное описание и демку, выводящую до миллиона частиц, вы можете найти в этой статье:
http://2ld.de/gdc2004/
Так же этот материал продублирован в демках NVidia (NV SDK 9, GPU Particles):
http://developer.download.nvidia.com/SDK/9.5/Samples/samples.html#gpu_particles
Есть более основательная статья от ATI:
Real-Time_Particles_Systems_on_the_GPU_in_Dynamic_Environments(Siggraph07).pdf 

Претендовать на более полное изложения я не могу и не стану, потому лишь приведу основные этапы реализации.

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

Рис.1. Хранение информации о частицах в текстурах

Так как в шейдере нельзя одновременно читать и писать в одну текстуру, то придется реализовать технику "ping-pong" - хранить два набора текстур и переключаться между ними:
Первая итерация: Читаем из пакета текстур №1, пишем в пакет текстур №2
Вторая итерация: Читаем из пакета текстур №2, пишем в пакет текстур №1
Третья итерация: Читаем из пакета текстур №1, пишем в пакет текстур №2
и т.д.

Теперь собственно пишем наш шейдер, на входе у него будут константы (к примеру параметры коллайдеров, коэффициент трения и прочее), наши текстурные сэмплы со значениями позиции, скорости и другими параметрами, а так же интервала времени, прошедшего с прошлого кадра.  Прочитав из текстур наши P0 и V0, по приведенным в начале статьи формулам (их можно усложнить, добавив вращение, коэффициенты трения, упругость, добавив проверку столкновений и прочее), вычисляем новое значение позиции, скорости, цвета и прочих параметров частиц и сохраняем их текстурные таргеты (через gl_FragData).

Рендеринг осуществляется в два прохода, на первом проходе мы создаем буфер кадра (FBO), прикрепляем к нему пакет текстур для записи (MRT), соответствующий текущей итерации, и отрисовываем скринквад, с применением описанного шейдера, передав в него все необходимые данные.
Допустим это первая итерация, для записи используется пакет2, для чтения пакет1, тогда в пакет2 у нас будут находиться обновленные вершинные атрибуты. Но чтоб вывести наши спрайты требуется преобразовать текстуру в вершинный буфер, делается это при помощи специального объекта Pixel Buffer Object (PBO), благодаря чему можно на стороне GPU скопировать данные из текстуры в буфер VBO.

На втором проходе мы  биндим полученные буферы VBO и рисуем квады с применением описанного ранее шейдера (восстановление координат вершин спрайта).

В следующих статьях данный пример будет разобран более детально, включая код шейдеров каждого этапа.
Рис.2. Пример вывода более миллиона текстурированных частиц через рендеринг в вершинный буфер

К данной методике можно сделать несколько замечаний, во-первых мы можем вычислять движение частиц не только по формулам, но и по произвольной траектории, для этого достаточно передать массив с коэффициентами интерполяционного полинома. Во-вторых - при таком подходе усложняется сортировка частиц по глубине, так как для этого требуются многопроходные шейдеры и количество итераций может быть равно количеству частиц (в приведенной выше статье рассматривается вариант с многопроходной сортировкой частиц на GPU), потому этот подход рекомендуется использовать для адитивного/мультипликативного блендинга или для непрозрачных частиц с альфатестом. В третьих - желательно уменьшить количество используемых текстурных таргетов, иначе можно получить боттлнек на пропускной способности видеопамяти. В четвертых - разумно выбирайте тип текстур, не злоупотребляйте текстурами в формате RGBA32F. В четвертых - по возможности пакуйте данные в одну текстуру, к примеру если нужно передать вектор скорости (x,y,z) и угол поворота (a), то их можно поместить в один буфер RGBA16F, в этом случае отпадет необходимость в копировании двух буферов VBO и вместо двух чтений из текстуры мы будем делать только одно. Аналогичным образом можно упаковать пару Offset+Scale для текстурных координат (хотя, если текстурный атлас однородный, то лучше передать индекс текстуры, а Offset/Scale уже вычислится в вершинном шейдере).

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

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

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

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


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

Комментариев нет:

Отправить комментарий