- PVSM.RU - https://www.pvsm.ru -
Реализацию порядко-независимой прозрачности (order-independent transparency [1], OIT), наверное, можно считать классической задачей программирования компьютерной графики. По сути, алгоритмы OIT решают одну простую прикладную задачу – как нарисовать набор полупрозрачных объектов так, чтобы не беспокоиться о порядке их рисования. Правила смешивания цветов при рендеринге требуют он нас, чтобы полупрозрачные объекты рисовались в порядке от дальнего к ближнему, однако этого сложно добиться в случае протяженных объектов или объектов сложной формы. Реализация одного из самых современных алгоритмов, OIT с использованием связных списков, была представлена AMD [2] для Direct3D 11 еще в 2010 году. Скажу откровенно, производительность алгоритма на широко доступных графических картах тех лет не произвела на меня должного впечатления. Прошло 4 года, я откопал презентацию AMD и решил реализовать алгоритм не только на Direct3D 11, но и на OpenGL 4.3. Тех, кому интересно, что получилось из этой затеи, прошу под кат.
Перед тем, как начать разговор о самой реализации алгоритма, отмечу, что демка доступна широкой аудитории здесь [3]. Проект называется Demo_OIT. Для сборки вам понадобятся Visual Studio 2012/2013 и CMake [4]. Полезная терминология приведена в конце поста.
Рендеринг полупрозрачных объектов имеет ряд особенностей:
Обобщенный алгоритм OIT можно представить следующим образом:
Основную сложность здесь представляют пункты 3 и 4, а именно, как получить фрагменты с разной глубиной, куда сохранить и как потом сортировать.
Начну с того, что определю требования к реализации:
Основная суть алгоритма заключается в следующем: для каждого отображаемого полупрозрачного фрагмента мы формируем связный список фрагментов, которые располагаются в этой же позиции на экране. Сформировать такой набор связных списков позволяет возможность современного графического оборудования вести произвольную запись в выделенный блок памяти прямо из шейдеров. Имея такие связные списки для каждого полупрозрачного фрагмента, можно производить сортировку фрагментов по глубине и затем смешивать цвета в правильном порядке.
Для реализации алгоритма нам потребуются:
Для лучшего понимая принципа работы, рассмотрим следующий рисунок.
На рисунке мы видим текстуру для хранения головных элементов списка, в которой хранятся адреса соответствующих фрагментов в буфере, и сам буфер. Места, в которых нет полупрозрачных фрагментов, содержат -1. Если на одну позицию на экране пришлось несколько полупрозрачных фрагментов, образуется список (фрагмент с индексом 0 содержит ссылку на фрагмент с индексом 2). Счётчик фрагментов в этой ситуации равен 5, т.е. следующий фрагмент будет записан в буфер по адресу 5, а счётчик инкрементируется.
На первый взгляд кажется, что всё просто, перейдем к деталям реализации.
Для реализации этого алгоритма на Direct3D 11 нам потребуются так называемые Unordered-Access ресурсы: текстура (RWTexture2D) и структурированный буфер (RWStructuredBuffer). Особенность этих ресурсов заключается в том, что чтение и запись для них доступны в шейдерах. Для них существует специальный набор команд в Direct3D API, например, чтобы связать UA-ресурсы с переменными в шейдерах служит метод OMSetRenderTargetsAndUnorderedAccessViews. Этот метод упомянут не случайно. Организация Direct3D 11 такова, что UA-ресурсы конкурируют с render target’ами при образовании связки с пиксельными шейдерами, т.е. если оборудование обеспечивает MRT в 8 текстур, и 2 слота занимают render target’ы, то на UA-ресурсы остается не более 6 слотов. Работа с UA-ресурсами должна производиться при помощи атомарных операций, что обусловлено высоко параллельной архитектурой GPU.
Счетчик фрагментов будет реализован при помощи флага D3D11_BUFFER_UAV_FLAG_COUNTER для структурированного буфера. Direct3D 11 позволяет прикреплять атомарный счетчик к структурированному буферу, в нашем случае логично использовать буфер для хранения элементов связных списков.
Для реализации алгоритма на Direct3D 11 создадим:
struct ListNode
{
uint packedColor;
uint depthAndCoverage;
uint next;
};
Таким образом, каждый элемент списка занимает 12 байт. Таких элементов нужно несколько на каждый фрагмент заднего буфера. Представим себе ситуацию, когда прямо перед камерой расположено 8 параллельных полупрозрачных плоскостей, которые занимают весь экран. В этом случае для каждого фрагмента заднего буфера сформируется список из 8 элементов. Для хранения этого объема данных потребуется буфер размером 12 * W * H * 8 байт, где W,H – длина и ширина заднего буфера. Редкой компьютерной игре необходимо столько видимых полупрозрачных фрагментов в кадре, поэтому возьмем эти 8 плоскостей за предельный случай. Для разрешения заднего буфера 1920x1080 размер структурированного буфера составит приблизительно 190Мб. К этому же буферу присоединим счётчик фрагментов при помощи описанного выше флага.
Рисовать кадр будем по следующей схеме:
#include <common.h.hlsl>
#include <pscommon.h.hlsl>
struct ListNode
{
uint packedColor;
uint depthAndCoverage;
uint next;
};
globallycoherent RWTexture2D<uint> headBuffer;
globallycoherent RWStructuredBuffer<ListNode> fragmentsList;
uint packColor(float4 color)
{
return (uint(color.r * 255) << 24) | (uint(color.g * 255) << 16) | (uint(color.b * 255) << 8) | uint(color.a * 255);
}
[earlydepthstencil]
float4 main(VS_OUTPUT input, uint coverage : SV_COVERAGE, bool frontFace : SV_IsFrontFace) : SV_TARGET
{
float4 color = computeColorTransparent(input, frontFace);
uint newHeadBufferValue = fragmentsList.IncrementCounter();
if (newHeadBufferValue == 0xffffffff) { return float4(0, 0, 0, 0); }
uint2 upos = uint2(input.position.xy);
uint previosHeadBufferValue;
InterlockedExchange(headBuffer[upos], newHeadBufferValue, previosHeadBufferValue);
uint currentDepth = f32tof16(input.worldPos.w);
ListNode node;
node.packedColor = packColor(float4(color.rgb, color.a));
node.depthAndCoverage = currentDepth | (coverage << 16);
node.next = previosHeadBufferValue;
fragmentsList[newHeadBufferValue] = node;
return float4(0, 0, 0, 0);
}
Рассмотрим самые интересные места в этом коде. Модификатор [earlydepthstencil] играет очень важную роль. Дело в том, что фрагментные тесты (тест глубины, трафарета и т.д.) в обычной ситуации проводятся на завершающем этапе графического конвейера, после исполнения пиксельных шейдеров. В нашем случае это недопустимо, так как все рисуемые на этом этапе фрагменты попадают в связные списки. Чтобы отсечь лишние фрагменты до попадания в списки, необходимо провести ранний тест глубины (до пиксельного шейдера).
Нетрудно видеть, что цвет фрагмента хранится в структуре как uint. Упаковка float4 значения в uint позволяет сэкономить 12 байт. 32-битная глубина пакуется в 16-битную, а свободные 16 бит используются для хранения значения coverage (необходимо для реализации MSAA).
Метод IncrementCounter вычисляет новый адрес для головного элемента списка, а функция InterlockedExchange атомарно меняет текущее значение головного элемента списка на новое. Нетрудно видеть, что список растет с головы, а вышеописанный код — практически классическая реализация вставки в начало для односвязного списка.
Цвет фрагмента = Текущий цвет фрагмента * 1 + Цвет фрагмента из шейдера * Альфа фрагмента из шейдера;
Те, кто знакомы с классической формулой альфа-блендинга [10], возможно, удивятся, увидев такое. По факту мы используем классическую формулу, просто часть этой формулы реализована в шейдере, а приведенная выше формула – завершающий этап смешивания с цветом фрагментов, уже нарисованных на экране.
В качестве алгоритма сортировки используем сортировку вставками [11]. Для небольших наборов данных этот примитивный алгоритм достаточно эффективен, кроме того данный алгоритм устойчив, т.е. не меняет порядок уже отсортированных элементов. При рендеринге полупрозрачных фрагментов мы теоретически можем получить частично-упорядоченные по глубине списки, для этого надо дополнительно отсортировать полупрозрачные объекты по расстоянию до наблюдателя и рисовать объекты в этом порядке. В некоторых случаях это позволит уменьшить количество перестановок сортируемых элементов в памяти.
Код для сортировки фрагментов в пиксельном шейдере приведен ниже.
void insertionSortMSAA(uint startIndex, uint sampleIndex, inout NodeData sortedFragments[MAX_FRAGMENTS], out int counter)
{
counter = 0;
uint index = startIndex;
for (int i = 0; i < MAX_FRAGMENTS; i++)
{
if (index != 0xffffffff)
{
uint coverage = (fragmentsList[index].depthAndCoverage >> 16);
if (coverage & (1 << sampleIndex))
{
sortedFragments[counter].packedColor = fragmentsList[index].packedColor;
sortedFragments[counter].depth = f16tof32(fragmentsList[index].depthAndCoverage);
counter++;
}
index = fragmentsList[index].next;
}
}
for (int k = 1; k < MAX_FRAGMENTS; k++)
{
int j = k;
NodeData t = sortedFragments[k];
while (sortedFragments[j - 1].depth < t.depth)
{
sortedFragments[j] = sortedFragments[j - 1];
j--;
if (j <= 0) { break; }
}
if (j != k) { sortedFragments[j] = t; }
}
}
Здесь же уместно будет упомянуть о реализации MSAA в Direct3D 11 [12]. Когда MSAA включен, для каждого фрагмента формируется набор точек (выборок) внутри фрагмента с немного отличающимися позициями. Число таких точек соответствует количеству уровней MSAA (обычно 2, 4, 8, 16). Для каждой точки проверяется ее принадлежность треугольнику (coverage test), и если хоть одна точка находится внутри треугольника, то пиксельный шейдер выполняется для текущего фрагмента, а результат интерполируется между всеми прошедшими тест выборками. Для того чтобы понять какие из выборок находятся внутри треугольника (т.е. прошли тест и оказывают влияние на результирующий цвет фрагмента), формируется маска, которая называется coverage. Именно это значение мы и сохраняли для каждого полупрозрачного фрагмента на предыдущем шаге.
Теперь при рендеринге мы можем выбрать из списка фрагменты, которые соответствуют конкретной выборке при помощи простого условия coverage & (1 << sampleIndex) != 0. Также следует обратить внимание на константу MAX_FRAGMENTS. Эффективно сортировать связные списки не просто даже на CPU, на GPU мы еще более ограничены. Поэтому перед сортировкой связный список копируется в массив фиксированной длины, что ограничивает количество полупрозрачных фрагментов в цепочке.
Интересно, что после фильтрации фрагментов по маске coverage в списке остаются фрагменты, имеющие абсолютно одинаковую глубину и незначительно отличающийся цвет. Это приводит к образованию артефактов на ребрах полигональной модели, особенно при низком качестве MSAA. Для того чтобы устранить артефакт, необходимо произвести усреднение цвета фрагментов с одинаковой глубиной. Так как выходной список фрагментов отсортирован по глубине, то фрагменты с одинаковым значением глубины идут подряд. Остается их только посчитать и собрать. Полный код шейдера скрыт под спойлером.
#include <tpcommon.h.hlsl>
float4 main(VS_OUTPUT input, uint sampleIndex : SV_SAMPLEINDEX) : SV_TARGET
{
uint2 upos = uint2(input.position.xy);
uint index = headBuffer[upos];
clip(index == 0xffffffff ? -1 : 1);
float3 color = float3(0, 0, 0);
float alpha = 1;
NodeData sortedFragments[MAX_FRAGMENTS];
[unroll]
for (int j = 0; j < MAX_FRAGMENTS; j++)
{
sortedFragments[j] = (NodeData)0;
}
int counter;
insertionSortMSAA(index, sampleIndex, sortedFragments, counter);
// resolve multisampling
int resolveBuffer[MAX_FRAGMENTS];
float4 colors[MAX_FRAGMENTS];
int resolveIndex = -1;
float prevdepth = -1.0f;
[unroll(MAX_FRAGMENTS)]
for (int i = 0; i < counter; i++)
{
if (sortedFragments[i].depth != prevdepth)
{
resolveIndex = -1;
resolveBuffer[i] = 1;
colors[i] = unpackColor(sortedFragments[i].packedColor);
}
else
{
if (resolveIndex < 0) { resolveIndex = i - 1; }
colors[resolveIndex] += unpackColor(sortedFragments[i].packedColor);
resolveBuffer[resolveIndex]++;
resolveBuffer[i] = 0;
}
prevdepth = sortedFragments[i].depth;
}
// gather
[unroll(MAX_FRAGMENTS)]
for (int i = 0; i < counter; i++)
{
[branch]
if (resolveBuffer[i] != 0)
{
float4 c = colors[i] / float(resolveBuffer[i]);
alpha *= (1.0 - c.a);
color = lerp(color, c.rgb, c.a);
}
}
return float4(color, alpha);
}
Результаты работы алгоритма, реализованного средствами Direct3D 11, можно видеть ниже.
Реализация на OpenGL 4.3 во многом похожа на предыдущую реализацию. Аналогом структурированных буферов здесь являются storage block’и (добавленные в стандарт как раз в версии 4.3). Для работы с текстурами, в которые можно вести чтение и запись из шейдеров, в GLSL есть специальные типы (нам потребуется uimage2D). Итого, для реализации алгоритма нам потребуется:
Процедура рендеринга кадра имеет одну ключевую особенность. OpenGL предлагает нам вручную управлять синхронизацией операций чтения-записи. Для этого существует специальная функция glMemoryBarrier, которую мы будем вызывать следующим образом:
glMemoryBarrier(GL_SHADER_IMAGE_ACCESS_BARRIER_BIT | GL_ATOMIC_COUNTER_BARRIER_BIT | GL_SHADER_STORAGE_BARRIER_BIT);
Это обеспечит целостность данных между разными этапами рисования кадра.
Рисовать кадр будем по следующей схеме:
imageStore(headBuffer, upos, uvec4(0xffffffff));
void main()
{
outputColor = vec4(0);
uint newHeadBufferValue = atomicCounterIncrement(fragmentsListCounter);
if (newHeadBufferValue == 0xffffffff) discard;
ivec2 upos = ivec2(gl_FragCoord.xy);
float depth = texelFetch(depthMap, upos, 0).r;
if (gl_FragCoord.z > depth) discard;
vec4 color = computeColorTransparent(gl_FrontFacing);
uint previosHeadBufferValue = imageAtomicExchange(headBuffer, upos, newHeadBufferValue);
uint currentDepth = packHalf2x16(vec2(psinput.worldPos.w, 0));
fragments[newHeadBufferValue].packedColor = packColor(vec4(color.rgb, color.a));
fragments[newHeadBufferValue].depthAndCoverage = currentDepth | (gl_SampleMaskIn[0] << 16);
fragments[newHeadBufferValue].next = previosHeadBufferValue;
}
Запись в буферы глубины и цвета, а также отсечение обратных граней должны быть отключены на этом этапе аналогично реализации на Direct3D.
void main()
{
ivec2 upos = ivec2(gl_FragCoord.xy);
uint index = imageLoad(headBuffer, upos).x;
if (index == 0xffffffff) discard;
vec3 color = vec3(0);
float alpha = 1.0f;
NodeData sortedFragments[MAX_FRAGMENTS];
for (int i = 0; i < MAX_FRAGMENTS; i++)
{
sortedFragments[i] = NodeData(0, 0.0f);
}
int counter;
insertionSort(index, gl_SampleID, sortedFragments, counter);
for (int i = 0; i < MAX_FRAGMENTS; i++)
{
if (i < counter)
{
vec4 c = unpackColor(sortedFragments[i].packedColor);
alpha *= (1.0 - c.a);
color = mix(color, c.rgb, c.a);
}
}
outputColor = vec4(color, alpha);
}
Визуально результат, полученный при рендеринге на OpenGL 4.3, ничем не отличается от Direct3D 11.
У алгоритма есть 3 ключевые проблемы:
Замеры производительности велись на компьютере следующей конфигурации: AMD Phenom II X4 970 3.79GHz, 16Gb RAM, AMD Radeon HD 7700 Series, под управлением ОС Windows 8.1.
Среднее время кадра. Direct3D 11 / 1920x1080 / 400k-800k полупрозрачных фрагментов.
MSAA / MAX_FRAGMENTS | 8 | 16 | 32 |
---|---|---|---|
0 | 1.4835ms | 1.67446ms | 2.1275ms |
2x | 3.49895ms | 6.66149ms | 8.52533ms |
4x | 5.78841ms | 12.3358ms | 15.7224ms |
8x | 8.93051ms | 18.4825ms | 24.8538ms |
Среднее время кадра. OpenGL 4.3 / 1920x1080 / 400k-800k полупрозрачных фрагментов.
MSAA / MAX_FRAGMENTS | 8 | 16 | 32 |
---|---|---|---|
0 | 3.25259ms | 4.10712ms | 16.8482ms |
2x | 5.06972ms | 7.16611ms | 33.6713ms |
4x | 7.22944ms | 12.3625ms | 62.5776ms |
8x | 11.2621ms | 19.0938ms | 115.026ms |
Среднее время кадра. Direct3D 11 / 1920x1080 / ~5000k полупрозрачных фрагментов.
MSAA / MAX_FRAGMENTS | 8 | 16 | 32 |
---|---|---|---|
0 | 4.94471ms | 5.73306ms | 7.95545ms |
2x | 9.91625ms | 26.6783ms | 40.4808ms |
4x | 16.653ms | 50.7367ms | 77.038ms |
8x | 28.3847ms | 91.0873ms | 143.419ms |
Среднее время кадра. OpenGL 4.3 / 1920x1080 / ~5000k полупрозрачных фрагментов.
MSAA / MAX_FRAGMENTS | 8 | 16 | 32 |
---|---|---|---|
0 | 16.2532ms | 22.0057ms | 139.678ms |
2x | 22.1646ms | 35.0568ms | 275.324ms |
4x | 30.4289ms | 56.7788ms | 536.241ms |
8x | 46.6934ms | 197.024ms | 1009.09ms |
Нетрудно видеть, что реализация алгоритма на Direct3D 11 работает быстрее, чем на OpenGL 4.3. Причем на 5 миллионах полупрозрачных фрагментов реализация на OpenGL «умирает» при включенном MSAA и больших величинах MAX_FRAGMENTS. Результаты профилирования показали, что основную часть времени алгоритм тратит на завершающем этап, т.е. на сортировке и смешивании цветов фрагментов. Также следует учитывать, что моя видеокарта далеко не самая новая, и приведённые цифры показывают лишь динамику изменения времени кадра.
Использование связных списков, наверное, можно считать самым современным подходом к реализации OIT. Алгоритм работает очень быстро при разумных настройках качества и сложности полупрозрачной части сцены. 5 миллионов видимых полупрозрачных фрагментов в кадре это, на мой взгляд, достаточно даже для самой современной игры (примерно 2.5 раза покрыть экран с разрешением 1920x1080 полупрозрачными фрагментами). От MSAA, который может замедлить алгоритм, при необходимости можно отказаться вовсе или заменить на другой алгоритм антиалиасинга. Алгоритм, безусловно, имеет недостатки, но все они понятны, и с ними можно бороться.
Так сложилось, что терминология компьютерной графики практически полностью иностранная. Ниже под спойлером я привел ряд терминов, которые могут быть полезны при прочтения поста.
Автор: rokuz
Источник [13]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/news/60792
Ссылки в тексте:
[1] order-independent transparency: http://en.wikipedia.org/wiki/Order-independent_transparency
[2] была представлена AMD: http://developer.amd.com/wordpress/media/2012/10/OIT%20and%20Indirect%20Illumination%20using%20DX11%20Linked%20Lists_forweb.ppsx
[3] здесь: https://github.com/rokuz/GraphicsDemo
[4] CMake: http://www.cmake.org/
[5] Depth Peeling: http://steps3d.narod.ru/tutorials/depth-peel-tutorial.html
[6] Reverse Depth Peeling: http://orenk2k.blogspot.ru/2010/10/oit-order-independent-transparency-3.html
[7] Dual Depth Peeling: http://developer.download.nvidia.com/SDK/10/opengl/src/dual_depth_peeling/doc/DualDepthPeeling.pdf
[8] здесь: http://www.uraldev.ru/articles/40
[9] здесь: http://www.uraldev.ru/articles/36
[10] альфа-блендинга: http://en.wikipedia.org/wiki/Alpha_compositing
[11] сортировку вставками: http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8
[12] реализации MSAA в Direct3D 11: http://msdn.microsoft.com/en-us/library/windows/desktop/cc627092(v=vs.85).aspx
[13] Источник: http://habrahabr.ru/post/224003/
Нажмите здесь для печати.