DIP Cost Reduction

Часто такие способы отображения сцены как forward rendering и deferred lighting подвергаются критике за необходимость отрисовывать одну и ту же геометрию несколько раз. Например, в DL требуется отдельно заполнить depth/normal буфер, что увеличивает DIP count в два раза по сравнению с DS. В forward rendering-е практически обязательно делать отдельный early Z-pass... При большом кол-ве вызовов функции Draw*() программа легко может стать CPU-bound. Особенно это критично при портировании DirectX-программ на какой-нибудь Mac, где драйверы OpenGL значительно хуже оптимизированы для большого кол-ва вызовов.

Я задумался над оптимизацией early Z-pass с точки зрения нагрузки на CPU. Сразу необходимо отметить, что я не рассматриваю варианты, где возможно применение инстансинга, речь пойдёт о выводе различной геометрии с топологией triangle list. Ключевым преимуществом является то, что в early Z-pass  изменения render states минимальны, типичный сценарий отрисовки примерно такой:

for each object
{
UpdateMatrix();
SetVertexBuffer();
SetIndexBuffer();
DrawGeometry();
}

Легко видеть, что между вызовами Draw() меняются только константы (матрица WorldViewProj) и вершинный/индексный буферы. Это можно оптимизировать, если объединить все геометрические данные в одном буфере. В Direct3D 10/11 с помощью параметров StartIndexLocation и BaseVertexLocation метода ID3D11DeviceContext::DrawIndexed() можно управлять, какую порцию вершинных данных необходимо отрисовать. Тогда оптимизированный вариант может выглядить так:

SetBigVertexBuffer();
SetBigIndexBuffer();
for each object
{
UpdateMatrix();
DrawGeometry();
}

Как мешают эти матрицы! А что, если обновлять матрицы не поодиночке, а сразу массив матриц для всех объектов? Тогда возникает вопрос, каким образом применить трансформацию индивидуально к каждому объекту? К сожалению, в Direct3D из шейдера невозможно узнать номер вызова отрисовки (по примеру SV_InstanceID в режиме инстансинга), но можно ценой дополнительных усилий организовать это вручную. Допустим, нам нужно отрисовать три объекта, каждый из которых имеет 3, 4 и 8 вершин. Создадим дополнительный вершинный буфер, атрибуты которого содержат ID объекта. Если мы объединим геометрию последовательно, то дополнительный буфер должен иметь вид:

000111122222222

Если подсоединить этот буфер на дополнительный IA-слот, то в шейдере станет возможным выбирать матрицу трансформации по ID из этого буфера. Теперь оптимизированный вариант рендеринга будет выглядить так:

UpdateMatricesForAllObjects();
SetBigVertexBuffer();
SetMeshIDVertexBuffer();
SetBigIndexBuffer();
for each object
{
DrawGeometry();
}

В итоге, в цикле остались только непосредственно вызовы метода рисования. Direct3D runtime оптимизирован в том смысле, что DIP cost зависит от количества изменений на конвейере, т. е. чем меньше изменений с момента предыдущего DIP, тем дешевле следующий за ним. В последнем варианте наиболее тяжёлым будет только первый вызов, все остальные - значительно легче (насколько именно - зависит от вендора и версии драйвера).
Присутствие цикла объясняется тем, что в кадре обычно видна только часть всех объектов сцены, поэтому необходимо определять их видимость из виртуальной камеры, заносить в отдельный список и рисовать объекты только из этого списка. Если специфика игры такова, что все объекты видны в камере, цикл можно заменить единственным(!) вызовом, подготовив отдельный буфер индексов и указав IndexCount для всех объектов. Если от цикла нельзя избавиться, можно попробовать сократить кол-во его итераций: например, если какие-то объекты видны в камере и одновременно лежат в буфере линейно, вызовы отрисовки для каждого из них можно объединить в один (этакий DIP-merge).

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

Ссылка на демо: dipreduc.exe

P.S. Поразмышлять на тему оптимизации меня побудил следующий вброс: DX11 vs GL Driver Overhead
где просто предлагается сделать 100000 DIP-ов чтобы прочувствовать мощь расширений NVidia :)

Fast Ray-BV Intersection

Когда-то давно, ещё в 2009, я написал несколько функций для теста пересечения луча и ограничивающего объёма (сфера, эллипс, коробка). Эти функции могут быть полезны, например, для оптимизации трассировки лучей в пиксельном шейдере. Идея была в том, чтобы реализовать действительно оптимальные варианты функций для каждого ограничивающего объёма. Спустя несколько лет я вернулся к этим кодам и после тщательного анализа мне удалось найти способ сократить эти функции ещё на одну-две инструкции! Теперь я уверен, что реализованный функционал действительно близок к эталонному. Тогда же я решил сделать реализацию open source, т. к. сам в прошлом потратил много времени на гугл, пытаясь найти что-нибудь подходящее - увы, многие коды были громоздкими, неоптимальными и часто даже не на С/С++.

Я реализовал функции проверки пересечения луча со сферой, AABB, эллипсом и OOBB. В двух последних, более сложных случаях, используется простой трюк, при котором луч трансформируется в локальное пространство ограничивающего объёма, используя заранее просчитанную матрицу.

Кстати, если сможете написать оптимальнее - дайте знать! :)
Ссылка на пример с исходным кодом на Google Code:

raybv.zip

Удачного рэйтрейсинга!

Так закончились "лихие 90-е"

Crinkler Edition

Обновил немного код своих демок: некоторые из них не компилировались c однобайтовыми (char) строками, были другие мелкие погрешности. Из Release конфигурации решено было исключить CRT и всякие buffer security checks, т. к. реально из этого почти ничего не использовалось, а довесок в .exe получается существенным - кода из CRT вставлялось больше, чем было самого кода программы.

Также я немного поигрался с разными упаковщиками .exe файлов и выбрал Crinkler, как наиболее эффективный. Он работает на стадии компоновки и может быть использован вместо стандартного студийного link.exe. Теперь размеры .exe файлов демок занимают не 20-30 Кб, а 3-10 кб. На слабых системах с HDD диском такие программы "на глазок" стартуют легче и быстрее.

Правда, с упаковкой надо быть осторожным, т. к. время распаковки может длиться дольше, чем загрузка .exe бОльшего размера :)

Kara - Heavy Rain's Dev Trailer

Holy sh...

Проверка зрения

Bicubic Texture Filtering

Всю последнюю неделю я занимался программируемой фильтрацией текстур. А началось с того, что я решил из спортивного интереса не преобразовывать .pcx текстуры из Quake II в RGBA (моветон) и не пережимать их в BC (с потерей деталей, которых и так почти нет) а загружать  в видеопамять таблицу индексов и палитру и делать выборку из палитры прямо в шейдере. Всё бы хорошо, но при таком раскладе нельзя использовать стандартную фильтрацию текстур, т. к. в этом случае будут усредняться индексы палитры, а не сами цветовые значения, что является ошибкой. Возможное решение - сначала делать выборку из палитры, а потом вручную выполнять билинейную фильтрацию.

Решено - пишем собственную билинейную фильтрацию (а заодно и бикубическую). У NVIDIA есть .fx файл с реализацией бикубической фильтрации и пример с реализациями различных фильтраций на CUDA. Взяв их за основу и прочитав кое-какую информацию о бикубическом ресемплинге, я написал собственные реализации.

В кубической фильтрации используется формула Митчелла-Нетравали, сплайном можно управлять с помощью двух параметров - B и C. Наиболее правильная фильтрация - по Митчеллу, с параметрами B=1/3, C=1/3, но параметры можно подбирать и произвольно. Ступенчатость лучше всего сглаживается при параметрах B=1, С=0, ценой "замыливания" изображения. NVIDIA использует иную формулу, которая идентична B=0, C=3/4 при A=-3/4 (см. GPU Gems).

Некоторые заметки о ходе разработки.

Для билинейной фильтрации необходимы четыре выборки, но если использовать Gather4 из sm 5.0, можно обойтись только тремя (для RGB компонент). При сравнении аппаратной билинейной фильтрации с реализованной вручную выявилось интересная особенность: похоже, все видеокарты AMD выполняют билинейную фильтрацию со слегка сниженной точностью, т. к. на экстремально маленьких текстурах заметен бандинг. Оптимизация в принципе оправдана, т. к. на больших по размеру текстурах сниженная точность незаметна. На NVIDIA отличий между аппаратной и программной реализациями нет.

При отладке бикубической фильтрации выявились странные различия в семплировании текстур с точечной выборкой между всеми видеокартами и Reference Rasterizer. Они проявлялись в виде паразитных линий, идущих параллельно границам текселей текстуры. Первоначально отлаженный на GTX 560 шейдер работал неправильно на HD 4330, HD 48xx и HD 68xx и refrast-e. Чтобы исправить работу под старшими моделями AMD и refrast-ом, экспериментальным путём было установлено, что из текстурных координат нужно вычесть смещение в 1/512, а для серии HD 4xxx - смещение в 1/128. Само по себе это странно, и сами числа наводят на мысли - это первый случай, когда я наткнулся на такие различия. С этим надо что-то сделать. Попытка отладки шейдера в PIX-е показала, что PIX показывает финальный output пиксельного шейдера, отличный от того, что записан в render target. Приехали.

Текущая реализация бикубической фильтрации использует 16 выборок на пиксель. В CUDA-примере от NVIDIA показано, что можно уложиться в четыре выборки, но пока неясно, насколько это "честно". Есть куда копать.

И наконец, почему бикубическая фильтрация до сих пор не реализована аппаратно? (Ok, похоже, что реализована, но D3D11 доступ к ней не предоставляет). Ответ прост: она требует значительно больше вычислительных ресурсов, при этом не даёт заметного преимущества в качестве при использовании текстур большого размера. Т. к. все современные видеокарты обладают значительным количеством локальной видеопамяти, большие текстуры используются повсеместно. Впрочем, для RAGE Кармак обещал бикубическую фильтрацию (там некоторые текстуры неоправданно пожаты).

Ссылки на примеры с исходным кодом на Google Code:

cubic-plot.zip
bicubic.zip

Update Feb 25, 2012

Переписал шейдеры таким образом, чтобы семплирование текстуры осуществлялось через метод Texture.Load() вместо point-семплирования. В этом случае GPU работает чётко с целочисленными адресами, что, как и ожидалось, привело к отсутствию ошибок и идентичному результату на всех видеокартах.

bicubic-2.0.zip