Алгоритм Order-Independent Transparency c использованием связных списков на Direct3D 11 и OpenGL 4

Реализацию порядко-независимой прозрачности (order-independent transparency, OIT), наверное, можно считать классической задачей программирования компьютерной графики. По сути, алгоритмы OIT решают одну простую прикладную задачу – как нарисовать набор полупрозрачных объектов так, чтобы не беспокоиться о порядке их рисования. Правила смешивания цветов при рендеринге требуют он нас, чтобы полупрозрачные объекты рисовались в порядке от дальнего к ближнему, однако этого сложно добиться в случае протяженных объектов или объектов сложной формы. Реализация одного из самых современных алгоритмов, OIT с использованием связных списков, была представлена AMD для Direct3D 11 еще в 2010 году. Скажу откровенно, производительность алгоритма на широко доступных графических картах тех лет не произвела на меня должного впечатления. Прошло 4 года, я откопал презентацию AMD и решил реализовать алгоритм не только на Direct3D 11, но и на OpenGL 4.3. Тех, кому интересно, что получилось из этой затеи, прошу под кат.

Перед тем, как начать разговор о самой реализации алгоритма, отмечу, что демка доступна широкой аудитории здесь. Проект называется Demo_OIT. Для сборки вам понадобятся Visual Studio 2012/2013 и CMake. Полезная терминология приведена в конце поста.

Краткий обзор алгоритмов OIT

Рендеринг полупрозрачных объектов имеет ряд особенностей:

1. При рендеринге непрозрачных объектов грани, которые не видны наблюдателю, обычно отбрасываются. Это позволяет сэкономить на растеризации и обработке фрагментов. В случае полупрозрачных объектов обратные грани не могут быть отброшены;
2. Тест глубины не должен проводиться среди полупрозрачных объектов, так как одни полупрозрачные объекты могут быть видны через другие. Однако, должна учитываться глубина непрозрачной части cцены, так как непрозрачный объект может частично или полностью перекрывать полупрозрачный;
3. Рисовать полупрозрачные объекты необходимо в порядке от дальнего к ближнему. Это диктуют правила смешивания цветов по альфа-каналу (alpha blending). Как уже было отмечено, алгоритмы OIT позволяют избавиться от этого ограничения.

Обобщенный алгоритм OIT можно представить следующим образом:

1. Нарисовать непрозрачные объекты сцены, сохранить буфер глубины;
2. Для каждого фрагмента полупрозрачного объекта, используя буфер глубины, полученный на шаге 1, определить, необходимо ли рисовать этот фрагмент;
3. Для каждого отображаемого полупрозрачного фрагмента сохранить его цвет, глубину и позицию на экране;
4. Для полупрозрачных фрагментов провести сортировку по значению глубины от дальнего к ближнему;
5. Рисовать полупрозрачные фрагменты в полученном порядке, смешивая их цвета по значению альфа-канала.

Основную сложность здесь представляют пункты 3 и 4, а именно, как получить фрагменты с разной глубиной, куда сохранить и как потом сортировать.

• Алгоритм Depth Peeling (и его вариации Reverse Depth Peeling, Dual Depth Peeling и т.д.) позволяет получить сцену по слоям. В первом слое хранятся фрагменты ближайшие к наблюдателю, во втором слое – вторые по близости и т.д. В классической реализации каждому слою отводится своя текстура, а полупрозрачная часть сцены рисуется столько раз, сколько необходимо слоев. Сортировка фрагментов в явном виде не нужна достаточно смешивать слои от дальнего к ближнему. К недостаткам алгоритма можно отнести многократное рисование сцены, необходимость хранения текстуры для каждого слоя (не для всех вариаций алгоритма это справедливо), выборка из множества текстур при смешивании цветов. К достоинству алгоритма можно отнести то, что его можно реализовать даже на Direct3D 9.
• Алгоритм Stencil Routed A-Buffer предполагает хранение слоев сцены в MSAA-текстуре. Этот алгоритм быстрее, избавляет от необходимости многократного рисования полупрозрачных объектов, однако лишает нас встроенного антиалиасинга. Кроме того, количество уровней MSAA ограничено (до 8x-16x на большинстве современного оборудования), а значит, ограничено и количество слоев. Я некогда реализовывал этот алгоритм, подробности, если интересно, здесь.
• Алгоритм OIT using Linked Lists, которому посвящен данный пост, лишен недостатков вышеописанных алгоритмов. Здесь полупрозрачная часть сцены рисуется однократно, возможна поддержка MSAA. Реализацию алгоритма на Direct3D 11 с использованием compute-шейдеров без поддержки MSAA можно найти здесь, там же приведено чуть более подробное описание алгоритма.

Реализация алгоритма Order-Independent Transparency using Linked Lists

Начну с того, что определю требования к реализации:

1. Алгоритм работает на Direct3D 11 и OpenGL 4.3;
2. Алгоритм не использует compute-шейдеры. Вполне достаточно фрагментного шейдера;
3. Алгоритм поддерживает MSAA.

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

1. Текстура целочисленного формата (unsigned int), совпадающая по размеру с экраном, для хранения головных элементов связных списков;
2. Буфер в памяти для хранения элементов связных списков. Минимальное содержание элемента связного списка включает цвет фрагмента, глубину и ссылку на следующий элемент (адрес в буфере);
3. Счетчик полупрозрачных фрагментов для того, чтобы определить ближайший свободный элемент в буфере.

Для лучшего понимая принципа работы, рассмотрим следующий рисунок.

На рисунке мы видим текстуру для хранения головных элементов списка, в которой хранятся адреса соответствующих фрагментов в буфере, и сам буфер. Места, в которых нет полупрозрачных фрагментов, содержат -1. Если на одну позицию на экране пришлось несколько полупрозрачных фрагментов, образуется список (фрагмент с индексом 0 содержит ссылку на фрагмент с индексом 2). Счётчик фрагментов в этой ситуации равен 5, т.е. следующий фрагмент будет записан в буфер по адресу 5, а счётчик инкрементируется.
На первый взгляд кажется, что всё просто, перейдем к деталям реализации.

Реализация на Direct3D 11

Для реализации этого алгоритма на 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 создадим:

1. Текстуру для хранения адресов головных элементов списков. Формат — DXGI_FORMAT_R32_UINT, флаги для связи с шейдерами — D3D11_BIND_UNORDERED_ACCESS | D3D11_BIND_SHADER_RESOURCE, размер эквивалентен размеру заднего буфера;
2. Структурированный буфер для хранения элементов связных списков. Каждый элемент списка на HLSL представлен следующей структурой:

   struct ListNode
   {
   	uint packedColor;
   	uint depthAndCoverage;
   	uint next;
   };

   Таким образом, каждый элемент списка занимает 12 байт. Таких элементов нужно несколько на каждый фрагмент заднего буфера. Представим себе ситуацию, когда прямо перед камерой расположено 8 параллельных полупрозрачных плоскостей, которые занимают весь экран. В этом случае для каждого фрагмента заднего буфера сформируется список из 8 элементов. Для хранения этого объема данных потребуется буфер размером 12 * W * H * 8 байт, где W,H – длина и ширина заднего буфера. Редкой компьютерной игре необходимо столько видимых полупрозрачных фрагментов в кадре, поэтому возьмем эти 8 плоскостей за предельный случай. Для разрешения заднего буфера 1920x1080 размер структурированного буфера составит приблизительно 190Мб. К этому же буферу присоединим счётчик фрагментов при помощи описанного выше флага.

Рисовать кадр будем по следующей схеме:

1. Очищаем текстуру адресов головных элементов списков значением 0xffffffff. Для этого есть специальный метод ClearUnorderedAccessViewUint. Сбрасываем счётчик фрагментов;
2. Выставляем задний буфер как нулевой render target, индекс 1 получит текстура головных элементов, индекс 2 – структурированный буфер элементов списков;
3. Рисуем непрозрачную часть сцены (в демке рисуется скайбокс и несколько непрозрачных чайников);
4. Формируем списки фрагментов полупрозрачной части сцены. Чтобы все получилось необходимо отключить отсечение обратных граней (D3D11_CULL_NONE), отключить запись новых значений в буфер глубины (но сам тест глубины не отключать), отключить запись цвета в текстуру (на этом шаге нам нечего рисовать, мы только формируем списки). Пиксельный шейдер, формирующий списки фрагментов, приведен ниже.

   #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 атомарно меняет текущее значение головного элемента списка на новое. Нетрудно видеть, что список растет с головы, а вышеописанный код — практически классическая реализация вставки в начало для односвязного списка.

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

   Цвет фрагмента = Текущий цвет фрагмента * 1 + Цвет фрагмента из шейдера * Альфа фрагмента из шейдера;

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

   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. Когда 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

Реализация на OpenGL 4.3 во многом похожа на предыдущую реализацию. Аналогом структурированных буферов здесь являются storage block’и (добавленные в стандарт как раз в версии 4.3). Для работы с текстурами, в которые можно вести чтение и запись из шейдеров, в GLSL есть специальные типы (нам потребуется uimage2D). Итого, для реализации алгоритма нам потребуется:

1. Целочисленная текстура (GL_R32UI) для хранения адресов головных элементов связных списков;
2. Буфер с типом GL_SHADER_STORAGE_BUFFER для хранения элементов связных списков. Размер буфера вычисляется так же, как и в реализации на Direct3D 11;
3. Буфер с типом GL_ATOMIC_COUNTER_BUFFER для хранения счетчика фрагментов. В отличие от Direct3D в OpenGL хранилище для атомарного счётчика создается явно;
4. Текстуры для рендеринга сцены и буфера глубины. В реализации алгоритма на OpenGL нам потребуется текстура глубины (об этом ниже). Достать стандартный буфер глубины из WGL хоть и можно, но ненадежно, поскольку формат буфера глубины-трафарета, который был выбран при инициализации окна WGL, может быть различный на разном оборудовании. Проще и безопаснее рисовать в собственноручно созданный framebuffer.

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

glMemoryBarrier(GL_SHADER_IMAGE_ACCESS_BARRIER_BIT | GL_ATOMIC_COUNTER_BARRIER_BIT | GL_SHADER_STORAGE_BARRIER_BIT);

Это обеспечит целостность данных между разными этапами рисования кадра.

Рисовать кадр будем по следующей схеме:

1. Очищаем текстуру с адресами головных элементов связных списков значением 0xffffffff. В OpenGL 4.3 для этого нужно вызвать шейдер, который будет для каждого фрагмента выполнять следующую операцию:

   imageStore(headBuffer, upos, uvec4(0xffffffff));
   

2. Сбрасываем счётчик фрагментов (glClearBufferSubData);
3. Выставляем framebuffer для рендеринга;
4. Рисуем непрозрачную часть сцены;
5. Формируем списки фрагментов полупрозрачной части сцены. На этом этапе есть анонсированная ранее особенность. OpenGL умеет производить ранний тест глубины только для фрагментных шейдеров без «побочных эффектов». К сожалению, к «побочным эффектам» относится запись в storage block. Важная роль раннего теста глубины для этого алгоритма обсуждалась ранее, поэтому нам ничего не остается, кроме как реализовать тест глубины самим. Часть фрагментного шейдера на GLSL приведена ниже.

   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.

6. Сортируем полученные списки фрагментов по глубине и выводим в framebuffer, смешивая по альфа-каналу. Процедура сортировки, смешивания цветов и настройки альфа-блендинга аналогичны Direct3D. Единственное исключение составляет тот факт, что после фильтрации фрагментов по маске coverage в списке не остается фрагментов, имеющих абсолютно одинаковую глубину, поэтому фрагментный шейдер несколько упрощается.

   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);
   }
   

7. Осуществляем копирование из framebuffer’а на экран при помощи функции glBlitFramebuffer.

Визуально результат, полученный при рендеринге на OpenGL 4.3, ничем не отличается от Direct3D 11.

Проблемы

У алгоритма есть 3 ключевые проблемы:

1. Величина MAX_FRAGMENTS, ограничивающая максимальное количество полупрозрачных фрагментов в списке. Мы сами можем выбирать эту величину, исходя из требуемого уровня качества и запаса времени, которое можно отдать под расчет OIT. К слову, включение MSAA увеличивает количество полупрозрачных фрагментов, особенно в районе ребер полигональных моделей. Ниже показано, что будет, если величины списка не хватит.

   

2. Размер буфера для хранения элементов списков. Я использовал буфер размером 190Мб и не смог воспроизвести переполнение на сцене из 36 чайников, однако на полигональных моделях сложной формы это возможно и очень вероятно. Размер буфера можно увеличивать, благо графические API не ограничивают явно размеры структурированных буферов и storage block’ов. Я уменьшил размер буфера в 8 раз, чтобы показать, что произойдет при переполнении.

   

3. Сложность пиксельного (фрагментного) шейдера на завершающем этапе алгоритма. С увеличением MAX_FRAGMENTS и включением MSAA шейдер становится все более тяжелым, что негативно сказывается на fillrate и может приводить к серьезным «тормозам».

Производительность

Замеры производительности велись на компьютере следующей конфигурации: AMD Phenom II X4 970 3.79GHz, 16Gb RAM, AMD Radeon HD 7700 Series, под управлением ОС Windows 8.1.

Среднее время кадра. Direct3D 11 / 1920x1080 / 400k-800k полупрозрачных фрагментов.

Среднее время кадра. OpenGL 4.3 / 1920x1080 / 400k-800k полупрозрачных фрагментов.

Среднее время кадра. Direct3D 11 / 1920x1080 / ~5000k полупрозрачных фрагментов.

Среднее время кадра. OpenGL 4.3 / 1920x1080 / ~5000k полупрозрачных фрагментов.

Нетрудно видеть, что реализация алгоритма на Direct3D 11 работает быстрее, чем на OpenGL 4.3. Причем на 5 миллионах полупрозрачных фрагментов реализация на OpenGL «умирает» при включенном MSAA и больших величинах MAX_FRAGMENTS. Результаты профилирования показали, что основную часть времени алгоритм тратит на завершающем этап, т.е. на сортировке и смешивании цветов фрагментов. Также следует учитывать, что моя видеокарта далеко не самая новая, и приведённые цифры показывают лишь динамику изменения времени кадра.

Выводы

Использование связных списков, наверное, можно считать самым современным подходом к реализации OIT. Алгоритм работает очень быстро при разумных настройках качества и сложности полупрозрачной части сцены. 5 миллионов видимых полупрозрачных фрагментов в кадре это, на мой взгляд, достаточно даже для самой современной игры (примерно 2.5 раза покрыть экран с разрешением 1920x1080 полупрозрачными фрагментами). От MSAA, который может замедлить алгоритм, при необходимости можно отказаться вовсе или заменить на другой алгоритм антиалиасинга. Алгоритм, безусловно, имеет недостатки, но все они понятны, и с ними можно бороться.

Немного о терминологии

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

Автор: rokuz

Источник