A-buffer/OIT through SM 5.0

Одним из преимуществ Direct3D 11 является то, что в его рамках появляется возможность решить старую проблему компьютерной графики - вывод прозрачных поверхностей без предварительной сортировки геометрии. Возможное решение - сортировка на уровне пикселей - была недоступна на потребительском железе (FFP или программируемом), вплоть до Direct3D 10.

В Direct3D 10 появилась возможность сортировки ограниченного кол-ва пикселей с использованием stencil-routed K-buffer. Данный метод использует отдельные сэмплы текстуры для хранения данных, кол-во сохраняемых фрагментов ограничиваются максимальным уровнем MSAA. Таким образом в один пиксель можно записать до 8 различных фрагментов (цвета, глубины). Этого явно недостаточно, поэтому метод подразумевает использование дополнительных текстур и нескольких проходов по геометрии, чтобы можно было "захватить" больше фрагментов. Известный пример с зелёным драконом из NVIDIA SDK 10 использует два прохода. Кроме досадной необходимости использовать множество проходов, метод требует подготовки/копирования буфера трафарета для роутинга фрагментов, что тоже бьёт по производительности.

С использованием Compute Shader, тесно интегрированного с остальным графическим API, и поддержкой read/write операций в железе стало возможным реализовать полноценный A-буфер, т. е. буфер, способный аккумулировать неограниченное кол-во значений для одного пикселя (L. Carpenter, 1984). Говоря "неограниченное", я, конечно, подразумеваю под этим словом большое, но всё же конечное кол-во значений, т. к. размер A-буфера на практике лимитирован, ну, хотя бы доступной видеопамятью. Однако досадных ограничений вроде MSAA=8 этот метод не имеет.

В SDK доступен небольшой сэмпл, реализующий Order Independent Transparency (OIT). Рассмотрим, как он работает.

Используются новые объекты HLSL 11: RWTexture2D для операций чтения/записи с двумерными массивами и RWBuffer для операций с одномерными. Работа осуществляется в Pixel и Compute Shader. Сперва прозрачная геометрия рисуется без depth-теста в uint буфер, в котором подсчитывается overdraw для каждого фрагмента изображения:

RWTexture2D fragmentCount : register( u1 );
void FragmentCountPS( SceneVS_Output input)
{
fragmentCount[input.pos.xy]++;
}

(Что интересно, в HLSL 11 у объектов появился operator [], который можно использовать как для чтения значений (вместо Buffer.Load()), так и для записи).

Затем в Compute Shader выполняется так называемый scan получившегося буфера, а точнее - одна из его операций prefix sum. Это хорошо известный и распространённый алгоритм в GPGPU, про него можно почитать в Википедии (Prefix sum) и в GPU Gems 3 (Chapter 39. Parallel Prefix Sum (Scan) with CUDA). Смысл этой операции заключается в том, чтобы за O(n) операций найти для каждого элемента списка сумму предшествующих ему элементов. Например, у нас есть буфер, в котором каждый элемент содержит какое-то заданное значение (в рамках нашей задачи - overdraw):

После parallel prefix sum в Compute Shader получается такой буфер:

Последний элемент содержит сумму всех элементов в буфере.
Prefix sum разбит на два этапа: в первом 2D-текстура копируется в RW-буфер, во втором происходит собственно суммирование. Чтобы подсчитать prefix sum для всего буфера, используется log(N) проходов, т. е. например, для буфера 1024x1024 необходимо 19 проходов. Первое суммирование осуществляется на первом этапе (копировании), поэтому во втором выполняется только log(N)-1 проходов.

Полученные суммы используются для размещения значений цвета и глубины прозрачной геометрии в линейном "глубоком" буфере (deep buffer, или, чтобы следовать придуманной ранее терминологии, A-buffer). Память для deep-буфера конкретно в сэмпле SDK выделяется с расчётом способности хранить до 8 фрагментов на каждый пиксель (это в среднем, в реальности overdraw крайне неравномерен, т. е. для одних пикселей это 0-4, для других 8-10, для третьих 20-30 и т. д. Главное, выделять память таким образом, чтобы по возможности разместились все данные). Размещение происходит в пиксельном шейдере, fragment count буфер перед этим очищается в ноль. Код шейдера:

void FillDeepBufferPS( SceneVS_Output In )
{
uint x = In.pos.x;
uint y = In.pos.y;
uint prefixSumPos = y * FrameWidth + x;
uint deepBufPos;

if (prefixSumPos == 0)
deepBufPos = fragmentCount[In.pos.xy];
else
deepBufPos = prefixSum[prefixSumPos-1] + fragmentCount[In.pos.xy];

deepBufDepth[deepBufPos] = In.pos.z;
deepBufColor[deepBufPos] = clamp(In.color, 0, 1)*255;
fragmentCount[In.pos.xy]++;
}

Из кода легко видеть, что в deep-буфере фрагменты каждого пикселя изображения выстраиваются в виде цепочек, одна за другой.

Затем в Compute Shader каждая такая цепочка сортируется bitonic sort-ом, все её элементы смешиваются по альфе, результат записывается в пиксель, соответствующий этой цепочке.

И всё :)

P.S. Существует демо Mecha от ATI, но т. к. утилиты отладки DX11-программ только на подходе, нет возможности добраться до шейдеров этого демо. Позже я обязательно это сделаю и сравню их код с кодом в OIT11.

P.P.S. Кстати, подобный алгоритм А-буфера уже запатентован Microsoft: PREFIX SUM PASS TO LINEARIZE A-BUFFER STORAGE. Впрочем, подобный патент не выдержит ни одного судебного разбирательства, ибо никто не может запретить кому-либо передвигать биты и байты в кристалле так, как ему это заблагорассудится. Знаете о патенте на колесо австралийца Джона Кеога?