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

    imageРеализацию порядко-независимой прозрачности (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 полупрозрачных фрагментов.
    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, который может замедлить алгоритм, при необходимости можно отказаться вовсе или заменить на другой алгоритм антиалиасинга. Алгоритм, безусловно, имеет недостатки, но все они понятны, и с ними можно бороться.

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


    Так сложилось, что терминология компьютерной графики практически полностью иностранная. Ниже под спойлером я привел ряд терминов, которые могут быть полезны при прочтения поста.
    Термины
    Рендеринг – процесс рисования трёхмерной сцены на двумерном носителе (экране, текстуре).
    Шейдер – программа для графического процессора (GPU), позволяющая контролировать один этапов графического конвейера. Вершинный шейдер оперирует вершинами, геометрический – примитивами (треугольниками, линиями и т.д.), пиксельный(фрагментный) – формируемыми на выходе пикселами.
    Растеризация – процесс формирования растрового изображения по векторному представлению объекта.
    Тест глубины – тест, полученных при рендеринге фрагментов, который позволяет отсекать фрагменты в зависимости от глубины уже нарисованной части сцены. Обычно в буфер глубины записывается глубина ближайшего к наблюдателю фрагмента.
    MSAA (multi-sampling antialiasing) – один из алгоритмов антиалиасинга, реализованный как в OpenGL, так и в Direct3D.
    MSAA-текстура – текстура для рендеринга с антиалиасингом. Имеет специальный формат, тип и набор операций в шейдерах.
    Render target – то, куда осуществляется рендеринг. Термин обычно используется при рисовании сцены в текстуру.
    MRT (multiple render targets) – технология, позволяющая осуществлять рендеринг сразу в несколько render target’ов.
    Compute-шейдер – программа для GPU, призванная решать задачу общего назначения (возможно не относящуюся к компьютерной графике).
    Задний буфер (back buffer) – в многобуферной модели рендеринга тот буфер, в который обычно осуществляется рендеринг, и который меняется местами с передним буфером (front buffer) после завершения рисования кадра.
    Framebuffer – специальный объект в OpenGL, который позволяет объединять несколько render target’ов и буфер глубины.
    Fillrate – грубо скорость заполнения экрана пикселами.
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 16
    • +4
      Нетрудно видеть, что реализация алгоритма на Direct3D 11 работает быстрее, чем на OpenGL 4.3.

      Скорее всего из-за того, что используется discard в шейдере.
      Пробовали ли найти причину?
      • +1
        Я сомневаюсь, что причина кроется в использовании discard, на HLSL я, например, использую clip. На небольших-средних объемах реализация на OpenGL почти не уступает, проблемы начинаются на больших объемах. Как я писал, существенно бОльшая часть времени кадра в этом случае тратится на сортировку и смешивание фрагментов, так что у меня единственное предположение — это перегруженный фрагментный шейдер и, как следствие, низкий fillrate. Перегрузка шейдера возникает, скорее всего, из-за большого количества используемых временных регистров и обращений к storage block'у с произвольным доступом. Произвольный доступ, к слову, еще и кэш гробит. Ну, и последнее, вполне возможно, что оптимизатор компилятора HLSL чуть лучше.
        А почему вы считаете, что discard может быть проблемой?
        • +4
          Опыт показывает, что замедление происходит в основном в 3 случаях:
          1. Много переключений между буферами
          2. discard
          3. Неправильно построенный шейдер. К примеру в плане if-конструкций, когда много временных переменных внутри блока.

          Я с Direct3D и HLSL вообще не знаком и на сколько мне подсказывает поиск, clip и discard далеко не тоже самое. Тут есть интересный ответ.
          • 0
            Спасибо за ссылку, действительно интересно, подумаю над этим :)
      • +1
        Интересная статья. Чисто с точки зрения познавательности. За это в карму плюсик.

        ИМХО данный метод еще долго(может быть никогда?) не пойдет глобально в продакшн.
        В повседневных геймдев задачах очень редко встает необходимость делать пересекающиеся полупрозрачные объекты.
        И как правило полупрозрачные объекты имеют простые формы с минимумом пересечений — оконные стекла, посуда.
        А эти ситуации вполне решаются ручной сортировкой без потери производительности.
        • 0
          ИМХО данный метод еще долго(может быть никогда?) не пойдет глобально в продакшн.

          Тут вы ошибаетесь. Как раз работаю над продуктом, не игра, где это очень нужно. Но мы пока не используем OIT, т.к. модели очень деталезированны и имеют очень много полигонов. Не на каждом устройстве хватает производительности, а нужно поддерживать большой спектр.
          • 0
            НЕ игры — это другое дело.
            И, наверняка, будут отдельные игры, в которых это реально будет нужно.
            Ну там какая нибудь детская игра с кучей мыльных пузырей.

            Я имею ввиду глобальное использование, например, как стало с бампом. Единственный шанс стать глобальным инструментом — это вынести функционал на уровень конвеера, чтобы он работал автоматически без телодвижений программиста. Потому что программистам в 99% случаев такой функционал не нужен.
            • 0
              Теперь вас понял. Тут-то соглашусь.
              Конечно было бы круто, если бы это все автоматически происходило.
          • +1
            Я бы сказал что в игровой идустрии уже применяются похожие методы. Обычно используют фоллбеки — шейдеры попроще, которые заменяют более продвинутые в случае если драйвер не умеет или производительность не позволяет.
            • 0
              Задача блендинга кучи полупрозрачного и неотсортированного в геймдеве повсеместна: партиклы например, или волосы персонажей.

              И там похожие методы используют, только хитрее кладут их на железо. Например сортируют только 4 ближайших объекта, остальное блендят как придется. При это буфер под каждый список получается фиксированного размера — меньше дорогих переходов по «указателям».
              • 0
                волосы очень легко сортируются с минимумом артефактов еще на момент построения модели.

                по поводу системы частиц — с одной стороны согласен, с другой — эмиттеры легко сортируются, а внутри эмиттера разные типы частиц просто отображаются в правильном порядке, как правило дополнительная сортировка не нужна.
            • 0
              Есть ещё одно относительно простое решение этой задачи Weighted, Blended Order-Independent Transparency
              • 0
                Вопрос.
                У вас написано: «Выставляем задний буфер как нулевой render target, индекс 1 получит текстура головных элементов, индекс 2 – структурированный буфер элементов списков;»
                Почему Backbuffer первый? Это же то, что мы выводим на экран.
                Почему он не должен рендериться в последнюю очередь, по завершению всех вычислений?
                • 0
                  Обратите внимание на дальнейшие шаги: полупрозрачная часть рисуется поверх при помощи полноэкранного квада. Поэтому в данном случае, непрозрачную часть можно рисовать в системный BB сразу.
                  • 0
                    Спасибо за быстрый ответ!
                    Теперь, если я правильно понял:
                    0-й пасс. Мы рисуем только непрозрачные объекты. В Backbuffer, формат текстуры R8G8B8A8_UNorm, флаги RenderTarget | ShaderResource. Тест глубины есть, по Z-buffer-у, все как обычно. Для чистоты эксперимента, я хочу от этого пасса отказаться.

                    1-й пасс. Рисуем прозрачные объекты в Unordered текстуру (или в Backbuffer?). Шейдер с флагом [earlydepthstencil]. Формат R32_Uint, флаги ShaderResource | Unordered Access. Размер по размеру экрана. Но дальше тест глубины без Z-буффера?

                    2-й пасс. Рисуем в структурированный буфер? (SizeInBytes = 30000000, ShaderResource | UnorderedAccess, StructureByteStride = 12, OptionFlag = BufferStructured) Заполняет его тот самый шейдер, который выполняет сортировку фрагментов insertionSort(index, sortedFragments, counter) и выводит float4(color, alpha). Оно не выводит на экран ничего, что не удивительно. Как это все дорисовать в Backbuffer?

                    И еще вопрос по: RWTexture2D headBuffer; каким образом шейдер знает, что нужно записывать значения именно в ту unordered текстуру, которую я ему выделил?
                    • 0
                      Смотрите, непрозрачную часть вы должны нарисовать до того, как начинаете работать с полупрозрачной, так как непрозрачная часть должна заполнить буфер глубины. Без этого полупрозрачные объекты не смогут быть перекрыты непрозрачными. earlydepthstencil отбрасывает такие фрагменты до обработки, а шейдер строит списки связности. Затем вы начинаете рисовать экранный квад, в котором читаете из текстуры, хранящей в списки связности, получаете N фрагментов, сортируете и смешиваете. Результирующий цвет рисуется прямо на BB в случае DX11.

                      >каким образом шейдер знает, что нужно записывать значения именно в ту unordered текстуру, которую я ему выделил?

                      Вы выставляете ее как render target.

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