Бесплатная реклама

Автор: Евгений Коростелев «kore3d»

Опубликовано: 21.04.2010

Изменено: 21.04.2010

Постоянная ссылка

Комментарии [13]

Порядко-независимая прозрачность на GPU с использованием динамических списков


В статье рассматриваются существующие технологии визуализации полупрозрачных объектов с использованием графических процессоров и предлагается модифицированный метод порядко-независимой прозрачности с использованием динамических списков слоев прозрачности.



Страницы: 1 2

Содержание

1. Введение
2. Общая концепция метода
3. Реализация метода
4. Результаты
5. Заключение
6. Демонстрационное приложение
7. Литература

В статье рассматриваются существующие технологии визуализации полупрозрачных объектов с использованием графических процессоров и предлагается модифицированный метод порядко-независимой прозрачности с использованием динамических списков слоев прозрачности. Метод эффективно реализуется на современном аппаратном обеспечении и использует атомарные операции и память с произвольным доступом на чтение-запись. Для тестирования реализации используется визуализация различных объектов на аппаратном решении бюджетного уровня последнего поколения видеокарт (ATI Radeon HD 5670).


Рисунок 1. Результат визуализации с использованием технологии и без нее

1. Введение

В современных системах виртуальной реальности, таких как игры и виртуальные тренажеры, визуализируются объекты, обладающие различными свойствами. Часть из свойств определяется материалами, из которых состоит реальная копия синтезируемого объекта. Некоторые из них позволяют свету свободно проникать внутрь и, таким образом, дают возможность стороннему наблюдателю видеть внутреннюю структуру и то, что располагается позади объекта. Это свойство часто учитывают при визуализации стеклянных поверхностей и природных явлений (рис. 2) с применением систем частиц.


Рисунок 2. Визуализация дыма и огня в системе частиц Magic Particles

Полупрозрачные объекты также встречаются в системах автоматизированного проектирования (САПР). Использование полупрозрачности облегчает разработку новых конструкторских решений, позволяя проектировщику видеть внутренние элементы проектируемого изделия (рис. 3).


Рисунок 3. Элементы интерфейса системы автоматизированного проектирования T-FLEX

Визуализация полупрозрачных элементов трехмерных сцен обычно реализуется через концепцию альфа-смешивания – суммирование значений цветов (формула 1) перекрывающихся пикселей, прошедших растеризацию. Далее приводится формула, в которой используются следующие обозначения: dest – текущее значение в буфере цвета, src – смешиваемое с ним значение.

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

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

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


Рисунок 4. Пример неправильной визуализации пересекающихся полупрозрачных объектов

Более десяти лет назад вместо сортировки по объектам было предложено сортировать растеризуемые графическим процессором пиксели. Это позволяет устранить зависимость от порядка растеризации примитивов. Поэтому такие методы обычно называют методами "порядко-независимой прозрачности" (order independent transparency). Кроме этого, они позволяют получать правильный результат и в случае пересекающихся объектов.

Одним из ранних методов порядко-независимой прозрачности является «расслоение глубины» (depth peeling) [1]. Его описание и базовая реализация доступны в NVIDIA SDK 9.x. Кроме нее в различных источниках встречаются его модифицированные версии: Dual depth peeling [2], Reverse Depth Peeling [3] и другие. Каждая из модификаций предлагает варианты снижения ресурсоемкости, основными источниками которой являются дополнительные проходы визуализации и резервирование памяти под слои прозрачности. Использование проходов применяется для разделения на слои растеризуемых полупрозрачных пикселей (рис. 5) и отрицательно сказывается на производительности метода в случае анимированных объектов и большого числа переключений состояний конвейера во время визуализации (например, смены текстур).


Рисунок 5. Концепция расслоения по глубине

В методах отложенного освещения (deferred shading) для визуализации полупрозрачных примитивов иногда используется чересстрочная визуализация [4] – полупрозрачные объекты чересстрочно визуализируются поверх изображения непрозрачных. Далее, на этапе пост-обработки, производится фильтрация полученного изображения. Такой подход использует запись в буфер глубины и соответствующий тест, что позволяет визуализировать только ближайший слой прозрачности.

В ходе развития современных графических процессоров были предложены и другие методы порядко-независимой прозрачности. Часть из них невозможно реализовать и на текущий момент ([5-7]). Причиной является отсутствие аппаратной поддержки атомарного исполнения блоков инструкций графического процессора. В DirectX11-совместимых видеокартах поддерживаются только простейшие атомарные операции над целочисленными типами данных. Примером простейших атомарных операция являются: атомарный инкремент (InterlockedIncrement), атомарный обмен (InterlockedExchange) и другие.

С появлением аппаратных решений с поддержкой DirectX версии 10 было предложено еще одно решение для визуализации полупрозрачности – метод К-буфера, управляемого значениями буфера трафарета (stencil routed k-buffer [8-9]). Основой этого метода является использование К-буфера – абстрактной структуры памяти для хранения в каждом пикселе буфера кадра ровно К слоев прозрачности. Отличие такого подхода, по сравнению с методами расслоения по глубине, заключается в том, что используется не К различных буферов, а один буфер с ячейками под К слоев. В эти ячейки записываются соответствующие пиксели, прошедшие стадию растеризации. Определение положения внутри ячейки осуществляется за счет использования значений из буфера трафарета. Реализуется описанная концепция посредством применения субпиксельной визуализации (multi sampling) и маскирования тестом трафарета (stencil test) субпикселей, позволяющим определить в какой субпиксель следует записать текущее значение. Таким образом, все полупрозрачные пиксели раскладываются в некотором произвольном порядке в субпиксели буфера кадра. Кроме цвета обычно в них еще дополнительно добавляется информация о глубине, что позволяет, в дальнейшем, сортировать и смешивать их в правильном порядке. В качестве алгоритма сортировки, в статье [8] предпочтение отдается алгоритму битонической сортировки [10].

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

В книге GPU Pro от AK Press предлагается другой вариант [11] визуализации полупрозрачности, объединяющий упомянутые ранее концепции: расслоение по глубине и К-буфер [12]. Для расслоения применяется разбиение пространства на К диапазонов (абстракция «корзин»), в которые помещается по одному пикселю (рис. 6). Также от кадра к кадру производится перерасчет диапазонов. Корректировка их границ производится операциями «минимум/максимум» и в качестве памяти используются буферы кадра (Multiple Render Targets). Таким образом, алгоритм представляет собой аналог сортировки вычерпыванием (bucket sort).


Рисунок 5. Метод расслоения по глубине с использование корзинной сортировки

Более эффективный метод визуализации полупрозрачных объектов реализуется с помощью DirectX 11. Функциональные возможности нового графического API позволяют реализовывать концепцию А-буфера [13], линеаризуемого с помощью префиксной суммы. А-буфер, в данном методе, используется вместо К-буфера для обработки произвольного числа слоев прозрачности. Их последовательное хранение в памяти, чтобы уменьшить ее потребление, достигается за счет алгоритма линеаризации, описанного в одном из патентов компании Microsoft [14].

В DirectX SDK за август 2009-го приводится пример реализации метода [15]. Представленная реализация, как показано в [16], является неэффективной и может быть ускорена в десятки раз. Для этого достаточно воспользоваться более эффективными алгоритмами сортировки и настроить соответствующим образом графический процессор. В целом же, алгоритм довольно прост для понимания (алгоритм 1) и включает в себя несколько основных шагов. Каждый такой шаг является отдельным проходом визуализации.

Алгоритм 1. Расчет прозрачности с использованием линеаризованного методом префиксной суммы А-буфера
1. Рассчитать в каждом элементе буфера кадра число перекрывающихся пикселей.
Визуализируем все полупрозрачные без материалов и считаем число операций записи в каждом пикселе буфера кадра. Для этого используем инкремент значения в буфере кадра, эффективно реализуемый через аппаратное альфа-смешивание.
2. Вычислить смещения по линейной памяти для первого слоя в каждом пикселе.
Используем алгоритм префиксной суммы, описанный в [14]. Префиксная сумма (рис. 7) – это частичная сумма значений в предыдущих пикселях (в случае линейного массива данных со значениями числа слоев).
3. Визуализировать все полупрозрачные объекты как обычно: с включенным тестом глубины и выключенной записью глубины.
При каждой записи в А-буфер (глубины и цвета) используем буфер со значениями смещений и их атомарный инкремент, что гарантирует запись следующего пикселя в незанятую ячейку памяти.
4. Отсортировать слои прозрачности и произвести альфа-смешивание.
После окончания визуализации полупрозрачных объектов полученные слои сортируются и смешиваются в правильном порядке. Для этого используется пост-обработка – квад на весь экран с пиксельным шейдером или вычислительный шейдер.


Рисунок 7. Пример результата расчета префиксной суммы

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

2. Общая концепция метода

В рамках продвижения новых аппаратных решений (видеокарт серии HD5xxx) компания AMD представила новый эффективный метод порядко-независимой прозрачности. Новая технология демонстрируется в приложении «AMD Demo – Mecha» [17] и использует возможности современных видеокарт. При этом не поставляется никакой документации, описывающей ее, что затрудняет изучение деталей. Детали реализации открываются благодаря программному продукту PerfStudio, который предоставляет дампы выполняемых графическим процессором команд.

В статье рассматривается реализация с нуля, включающая ряд оптимизаций. Основа метода заключается в построении поверх линейной памяти динамических списков. Формируемые списки обеспечивают хранение слоев прозрачности и строятся в момент визуализации полупрозрачных объектов трёхмерной сцены. По завершению этой стадии, производится сортировка каждого списка и смешивание записанных в список значений. Этот проход аналогичен 4-ому шагу алгоритма линеаризованного А-буфера (алгоритм 1).

Для работы метода требуются минимум три буфера и один глобальный счетчик:
  · память под адреса (смещение) начала списков – W*H:[R32_UINT]
  · память под значения глубины и указателя на следующий элемент списка – kW*kH:[R32G32_UINT]
  · память под цвет (rgba) – kW*kH:[R32_UINT]
  · счетчик занятой памяти – атомарный счетчик:[StructuredBuffer hidden counter]
где W и H – размеры буфера кадра, k – коэффициент объема памяти под слои

В качестве оптимизации, далее используется один дополнительный буфер под запись длины списка:
  · память под счетчики длины списков – W*H:[R32_UINT]

Память под указанные буферы на видеокарте выделяется в виде объектов 2D-текстур. Этот вид взаимодействия с памятью, как показали тесты производительности, является более эффективным, чем через объекты Buffer или StructuredBuffer. Применение двухмерных текстур также обуславливается тем, что максимальное разрешение текстуры по любой из осей в Direct3D11 составляет 16384 текселей. Кроме этого, в реализации для доступа на запись используются технология UAV (Unordered Access View) и атомарные операции для синхронизации операций между потоками. Например, применяется атомарный обмен и инкремент, которые впервые появились в пятой модели шейдеров HLSL (Shader Model 5 [18]).

Далее рассматривается схема построения динамических списков. Пусть имеем простой случай – изображение разрешения 2 на 2 пикселя, и сцена такова, что в среднем на 1 пиксель приходится 2 перезаписи (overdraw) Тогда в инициализированном состоянии используемые буферы выглядят, как показано в таблице 1.


Таблица 1. Пример используемых буферов

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

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

Далее приводится алгоритм заполнения буферов. Предполагается, что текущий обрабатываемый пиксель имеет цвет RGBA и соответствующее ему значение глубины равно Z (SV_position.z). В этом случае алгоритм записывается следующим образом:

Алгоритм 2. Построение динамического списка прозрачности
1. Увеличить счетчик занятой памяти.
Атомарно увеличиваем на единицу счетчик занятой памяти и запоминаем предыдущее значение. Считаем, что оно равно offset. Так как используем скрытый счетчик структурированного буфера (StructuredBuffer), для инкремента достаточно вызвать его метод IncrementCounter().
2. Обновить буфер начала списков.
Атомарно записываем значение offset в буфер начала списков (по адресу SV_Position.xy) и одновременно читаем предыдущее значение. Для определенности, пусть прочитанное значение равно next.
3. Записать в линейную память цвет, глубину и адрес следующего элемента.
Записываем цвет в буфер цвета по смещению offset. Биты значения z записываем в uint регистр и, далее, по смещению offset пишем uint2(asuint(z), next) в буфер глубины и адреса.

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

Сформированные списки прозрачности обрабатываются отдельным проходом. На этом этапе происходит сортировка элементов внутри каждого списка и применяется альфа-смешивание. В качестве сортировки могут быть выбраны различные алгоритмы. Например, сортировка вставками, пузырьковая, битоническая или другой вариант. В приложении «AMD Demo – Mecha» предпочтение отдается сортировке вставками. Данная сортировка не является оптимальной, поскольку требует выполнения большого числа операций сравнения и обмена.

Для параллельных архитектур существуют различные сортирующие сети [19], реализуемые с минимальным числом компараторов – блоков сравнения-обмена (рис. 8). В предлагаемой в статье реализации используется сортировка методом «чет-нечет» Батчера [20]. Такое решение применяется, поскольку метод дает сортирующие сети, обладающие хорошим свойством – сеть с большим числом входов использует сеть с меньшим числом. Кроме этого, получаемые сети обладают и недостатком – сортируются только последовательности из элементов, число которых равно степени двойки. Но это ограничение не существенно.


Рисунок 8. Схема работы компаратора

В качестве оптимизации, предлагается использовать развернутые варианты сетей (рис. 9). То есть применяется не общий (рекурсивный вид алгоритма), а функции с жестко связанными компараторами. Число компараторов в случае 16 входов равно 63, в случае 32 – 191, в случае 64 – 543 [21]. Таким образом, из-за того, что число компараторов при 64 сортируемых элементах велико, может наблюдаться существенное падение производительности. Как показано в работе [22], существуют сети с меньшим числом компараторов, которые, например, могут быть получены алгоритмом Бозе-Нельсона (Bose-Nelson). Но они не обладают указанным ранее свойством и поэтому не реализованы. Также стоит отметить, для сравнения, что при использовании битонической сортировки число компараторов составляет: при 16 входах – 80, при 64 – 672.


Рисунок 9. Пример сортирующей сети для 8 значений

В качестве дополнительной оптимизации используется упаковка значений глубины и цветов в 32-битное беззнаковое целое. Упакованные значения используются и при сравнении в компараторах, что допустимо, так как значение глубины обрабатываемых пикселей лежит в диапазоне [0,1]. Использование запакованных значений позволяет сократить число обменов значений регистров – вместо четырех, в случае обмена, необходимо обработать только по одному регистру. Такой прием полезен, поскольку графические процессоры имеют скалярную архитектуру.

 
Страницы: 1 2