четверг, 31 декабря 2009 г.

2010

Я оптимизировал, как мог, исходный код сэмпла OIT11 из DX SDK и заставил его выдавать соответствующую D3D11 железу скорость.



Пока адресация заточена под базовые 640x480, поэтому не привожу fps для высоких разрешений. К тому же оптимизации не закончены. О плохом: к концу буфера кадра (внизу окна) вылязят ужасные ошибки. Не знаю, где точно проблема - то ли в read/write contention, то ли в адресации/распределении тредов. Будем бороться - у Мехи же получилось :)

На этой мажорной ноте и закончу research 2009 года. Дай бог, чтобы в следующем году у меня было хоть немного времени на все эти занятные штуковины.

Да!
C Новым Годом! С новым, так сказать, счастьем :)

понедельник, 28 декабря 2009 г.

Xerxes


Совсем недавно стало ясно, что продолжение "300 спартанцев" скорее будет, чем нет. Зак Снайдер подтвердил, что работает над приквелом с кодовым именем "Ксеркс".

Wow!

воскресенье, 27 декабря 2009 г.

Parallel Prefix Sum (Scan)

Несколько дней назад я тестировал сэмпл OIT11 из DirectX SDK и был неприятно поражён его производительностью: 12 fps в окне 320х240. Решив разобраться, в чём дело, я реализовал небольшую программу, приблизительно воспроизводящую алгоритм prefix sum из OIT11, а также проштудировал материал по теме.

Вот код программы: OIT prefix sum.
Во-первых, алгоритм сканирования реализован "в лоб". В процессе выполнения видно, что к концу сканирования он плохо параллелится - последний (единственный) тред суммирует половину фрагментов буфера кадра, что никак нельзя назвать параллельной работой. Во-вторых, асимптотическая оценка кол-ва операций этого алгоритма = O(N * log(N)), тогда как достаточно O(N) операций (более точно, этот алгоритм выполняет N * log(sqrt(N)) операций), т. е. для сколь-нибудь большого буфера кадра его производительность ниже оптимального на несколько (!) порядков.

Фактически, применённый алгоритм - это naive prefix scan, описание которого можно найти у NVIDIA. Для пробы я написал код и для него: Naive prefix sum. Асимптотическая оценка времени его выполнения тоже O(N * log(N)). Единственное отличие - для OIT11 не требуется промежуточный буфер, куда записываются результаты суммирования, а потом копируются обратно в основной буфер.

Наиболее оптимальный на сегодняшний день алгоритм был описан Guy E. Blelloch в 1990. Он состоит из двух фаз - reduce (up-sweep) и down-sweep. Алгоритм хорошо распараллеливается, т. к. каждый тред выполняет всего одно сложение (или сложение/обмен в down-sweep). Алгоритм выполняет ~(N * 2) операций, т. е. его асимптотическая оценка - O(N). Inclusive prefix sum.

P.S. Я не очень хорошо разбираюсь в CUDA и нюансах работы тредов, поэтому меня несколько смущают описанные проблемы конфликтов банков памяти при доступе из различных тредов. Я вот задумался: атомические операции в HLSL 11 призваны убрать именно эту проблему или они нужны для чего-то другого?

четверг, 24 декабря 2009 г.

Radeon HD 5770

Решил всё-таки купить новый Radeon. Подарок самому себе на Новый год, так сказать. Денег на 5800-ю серию нет (да и БП не потянет такого монстра), решил приобрести middle-end, а именно Sapphire Radeon HD 5770 1GB. Решил взять чуть подороже, зато Sapphire, чтобы быть уверенным, что производитель не втюхает мне какую-нить убогую память или ещё как-нить облапошит, подсунув законченный и совершенный low-end.  Карта мне обошлась в 202$, хотя рекомендованная цена от AMD - 160$. Барыги накручивают - в нищей стране, как известно, платят дважды.

Вот так выглядит коробка:



Внутри видеокарта в антистатическом пакете (с громким предупреждением о необходимости в дополнительном питании для платы!), переходник Molex/6-PinPCI-E, инструкция для упоротых, диск с драйверами под XP/Vista/Seven, переходник DVI/VGA и перемычка для CrossFire:



Вот сама видеокарта в исполнении Sapphire:



А это она уже в системном блоке, с подключенным питанием:



Пыльновато тут, завтра надо бы почистить трудягу. Кстати о питании. AMD рекомендует для HD 5770 и HD 5750 блоки питания как минимум 450 W. У меня 400 W, поэтому были небольшие опасения, что этого может не хватить. Хватило :) В принципе, даже в минимальные требования производителем в таких случаях закладывается определённый "запас", на случай если у пользователя на БП уже висит несколько HDD, 4 гига RAM и т. д. У меня системник этим необременён, поэтому по этому поводу я особенно не волновался.

А вот мои предыдущие видеокарты:



Слева направо: GeForce 6600 256MB (покупалась изначально с компьютером), Radeon X1300 128MB (приобретена исключительно в целях отладки OpenGL-кода), Radeon HD 2400 256MB (приобретена с целью писать код по Direct3D 10).

Значит установил я драйверы и начал тестировать сэмплы из DirectX 11 SDK.

Тесселяция работает замечательно, провалов в скорости, как это было с GS, нет. Я погонял разные демки (их в SDK 3). Например, чайник в демке PNTriangles11 показывает 1620 fps без тесселяции и 250 fps при уровне тесселяции 19. В примере SubD11 скорость падает быстрее, возможно из-за анимации или просто неоптимально написано. Но в общем при "беглом осмотре" тесселятор от AMD при грамотном программировании и без швыряния ресурсов на ветер - вполне юзабелен.

Запустил я OIT11 и закручинился. 8 fps в малюсеньком окошке.
Потом запустил HDRToneMappingCS11. Там есть опция полноэкранного блюра. в 1280x1024 через Pixel Shader получается 340 fps, через Compute Shader - 11 fps. Проблема явно в драйверах, поэтому с полноценным A-буфером и другими экспериментами в CS пока придётся обождать.

Позапускал ещё DX 10.1 сэмплы, но особенно ничего интересного в визуальном плане они не несут. HDAO этот ни к селу ни к городу, DOF 10.1, выглядящий как УГ... Кто его вообще делал???

Скачал с сайта AMD демки Mecha и Ladybug, попробовал запустить. Mecha не пошла, ругалась красным матом о невозможности создать какие-то ресурсы и т. д, рисовала чёрное окно с одним текстом. Вспомнив о проблемах с драйверами, скачал с сайта AMD декабрьские драйверы под XP/Seven, поставил. Проверил сначала OIT11 - было 8 fps, стало 12. Прогресс. Ладно, будем ждать. Зато Mecha на этот раз запустилась безо всяких проблем и показала попиксельную сортировку во всей её красе без подтормаживаний. Впрочем, fps там не отображался (от греха подальше?), надо бы каким-нить фрапсом замерить. В любом случае, там тоже используется каким-то образом CS, и работает этот driver path хорошо. Дальше я запустил Ladybug... Вау, лучший DOF который я видел! Божья коровка такая милая, ну... ну, как наша Юлька-премьерка. Детализированные текстуры, чтобы был эффект микросъёмки, и DOF на заднем плане. Новый алгоритм называется filter spreading (там в демках есть такой teaching mode, где объясняется что и как). Алгоритм был разработан совместными усилиями инженеров AMD и Калифорнийского университета в Беркли. Глядя на приятные глазу цвета, детализацию и качественный Depth-of-Field, понимаешь, что преимущества нового поколения GPU вполне реальны.

Ну вот, пожалуй, и всё на сегодня.

среда, 23 декабря 2009 г.

Аватар

Посмотрел этот 230 000 000-нный сабж. Фильм прекрасен, уплаченные за билет деньги жалко не будет. Желательно смотреть в 3D (хотя эффект временами спорный), если их есть у вас, конечно :)

P.S. Раздражают ублюдочные кинокритики, в жизни ничего хорошего не создавшие и позволяющие себе критиковать работу Мастера.

вторник, 22 декабря 2009 г.

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. Впрочем, подобный патент не выдержит ни одного судебного разбирательства, ибо никто не может запретить кому-либо передвигать биты и байты в кристалле так, как ему это заблагорассудится. Знаете о патенте на колесо австралийца Джона Кеога?

воскресенье, 20 декабря 2009 г.

Пров

Поставил безлимитку - ну и провайдер попался! amd.com и nvidia.com блокируют, code.google.com блокирует... Приходится выходить через прокси-сервер.

Не любят нас за кордоном :(

Direct3D 11 and Text Drawing

В 9 и 10 D3DX были классы для вывода текста (конкретно в 10 это ID3DXFont10). Замечательно так работали: задаём параметры шрифта (аналогично структуре LOGFONT), шрифт рендерится в текстуру, потом делаем Font->DrawText() и всё. В Direct3D 11 D3DX совершил очередной round-trip: если при переходе с 9 на 10 Effect FX перекочевал в ядро, то в 11 - обратно в D3DX :) Кроме того, фреймворк доступен в виде исходного кода, а не библиотеки (посмотрев, сколько там говна, я вообще решил не юзать FX). А вместе с изменениями в FX Microsoft убрал такие классы как ID3DXFont10, ID3DXMesh10, ID3DXSprite10 и т. д. Почти ничего этого я не использовал, но вот быстрый вывод шрифта в маленьких аппах через ID3DXFont10 был полезен.

Озадачившись выводом шрифта с новым SDK, я решил выводить его через GDI. Но напрямую GDI и D3D не дружат - текст ужасно мерцает. Полазив по SDK, я нашёл, как делать правильно.

1) При создании swap chain указываем флаг DXGI_SWAP_CHAIN_FLAG_GDI_COMPATIBLE.
2) Формат back-буфера должен быть DXGI_FORMAT_B8G8R8A8_UNORM_SRGB или DXGI_FORMAT_B8G8R8A8_UNORM (порядок RGBA не поддерживается).
3) Количество отсчётов в back-буфере должно быть равным 1.
4) Далее необходимо получить интерфейс поверхности (новый интерфейс в DXGI 1.1):

IDXGISurface1* pSurface1 = NULL;
pSwapChain->GetBuffer(0, __uuidof(IDXGISurface1), (void**)&pSurface1);

У этого интерфейса есть методы GetDC() и ReleaseDC(). Вывод текста средствами GDI можно делать между этими двумя вызовами:

HDC hDC;
pSurface1->GetDC(FALSE, &hDC);
...
//Draw on the DC using GDI
...
//When finish drawing relase the DC
pSurface1->ReleaseDC(NULL);

5) После необходимо заново прицепить render target окна, т. к. он отвязывается. У меня, если этого не делать, рантайм падает в D3D11SDKLayers.dll.

пятница, 18 декабря 2009 г.

Direct3D 11 Inspection

Нашёл несколько интересных мест в Direct3D 11.

Первое - D3D11_DEPTH_STENCIL_VIEW_DESC. У этой структуры появилось дополнительное поле UINT Flags (в 10 версии его не было). Я обнаружил это, когда прямой копипаст DX10-кода в DX11 не заработал (в дополнительном поле был мусор и рантайм возвращал ошибку). В SDK по этому поводу написано следующее:
A value that describes whether the texture is read only. Pass 0 to specify that it is not read only; otherwise, pass one of the members of the D3D11_DSV_FLAG enumerated type:

D3D11_DSV_READ_ONLY_DEPTH
Indicates that depth values are read only.
D3D11_DSV_READ_ONLY_STENCIL
Indicates that stencil values are read only.
В пояснении написано:
Limiting a depth-stencil buffer to read-only access allows more than one depth-stencil view to be bound to the pipeline simultaneously, since it is not possible to have a read/write conflicts between separate views.
Я так понимаю, это сделано для того, чтобы можно было одну и ту же depth/stencil текстуру одновременно прицепить как render target на запись и как shader resource view на чтение в шейдере, при этом разбросав чтение и запись по depth/stencil. Иначе непонятна формулировка "allows more than one depth-stencil view to be bound to the pipeline simultaneously", т. к. методы ID3D11DeviceContext::OMSetRenderTargets() и ID3D11..Context::OMSetRenderTargetsAndUnorderedAccessViews() принимают только ОДИН depth/stencil view. (кстати, о последнем методе: в SDK опять напортачили секретарши майкрософта, типы параметров отличаются от таковых в D3D11.h). К тому же неясно, зачем вообще подключать одновременно два depth/stencil view (буфера) к пайплайну. Получается, речь идёт именно о OM/PS конфликте. Но и в этом свете приведённая формулировка туманна, т. к. PS принимает именно resource view, а не depth-stencil view.

В общем, как-то всё туманно и неясно, как конкретно использовать новое преимущество. Пишем в depth, а в шейдере читаем только stencil из того же самого буфера? Пишем в stencil, в шейдере читаем только depth?

Ещё один интересный найдёныш из Direct3D 11, на этот раз в HLSL attributes. Помимо прочих, появился новый атрибут earlydepthstencil. Назначение - ФОРСИРОВАТЬ выполнение early z/stencil тестов до пиксельного шейдера. Как известно, железо может это делать только при соблюдении определённых условий (например, из шейдера не пишется глубина), а если они нарушаются, то early тесты отключаются.

Кстати, вот мои мысли, высказанные два года назад по этому поводу:


Так что мои мысли оказались в каком-то роде пророческими. Интересно, насколько новый атрибут устойчив к различного рода пакостям? Например, если попытаться писать в глубину, кто кого сломает? :)

пятница, 11 декабря 2009 г.

Inverse in PS

Я ждал, когда это случится! И наконец-то это произошло. Передо мною встала простая задача - инвертировать матрицу 3x3 в пиксельном шейдере.

Update

Нашёл в Сети и протестировал, похоже, оптимальный вариант.
Вот код: invert. Проверки det == 0 нет, для PS это роскошь.

вторник, 8 декабря 2009 г.

Пуф-ф-ф!

Всё, сдулся Larrabee...

воскресенье, 6 декабря 2009 г.

Всё, что имеет начало, имеет и конец

Наткнулся на запись боя между Дэнни Грином и Роем Джонсом младшим, который прошёл на днях:

Danny Green vs Roy Jones Jr from Sydney, Australia 02/12/09

Очень грустное зрелище, конечно. Вот так заканчивают Великие Атлеты (действительно великие), если не знают, когда пора уйти со сцены (или же не хотят этого делать).

пятница, 4 декабря 2009 г.

Ньютон

Я иногда перечитываю биографии великих физиков и математиков, стараясь понять, какие личностные качества помогали им добиваться успеха. Очень интересным оказался один случай из биографии Исаака Ньютона (вычитал в Википедии):

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

воскресенье, 29 ноября 2009 г.

Не хочется переполнять блог политическим флудом, но т. к. новые вещи пока в стадии активного research-а, и пока не придумал, чего-бы такого написать, вот замечательная статейка:

Россия сближается с Европой за счет Украины

понедельник, 23 ноября 2009 г.

Paper dragon

Вот по прошествии некоторого времени стало неясно: а чего NVIDIA вообще вылезла со своим "бумажным драконом"? Приостановить ажиотаж вокруг ATI? Грязно, товарищи, грязно. Вы же рвётесь на рынок суперкомьютеров и научных вычислений - и уже давно! ECC, double precision и унифицированные указатели - вот последние форпосты, которые мешали использовать NVIDIA GPU в кластерах и научных расчётах (Fermi, к слову, начал разрабатываться сразу после G80, т. е. в 2006 году, и один Бог ведает, что готовится сейчас на смену Fermi). Того и гляди, игровой рынок вообще пойдёт нвидии побоку - они научились делать процессоры лучше, чем Intel'овские - какие уж тут игры. За двумя зайцами не угонишься - или игры, или суперы, и не надо подрывать бизнес конкурента.

Как интересно, сделана тесселяция в новом чипе - дополнительными транзисторами, или всё через CUDA в драйвере? А если аппаратно, то становится интересно - что, чипы так и будут, вместе с тесселятором и останками fixed-function pipe стоять в кластерах? Или NVIDIA запустит несколько веток, где Tesla не будет содержать ничего, кроме CUDA ядер? В общем, интересно, как одна и та же архитектура будет позиционироваться для совершенно разных прикладных задач.

А стоить новые монстры будут по 600$, после торжественного выхода... весной. Зачем бумажный дракон?

вторник, 17 ноября 2009 г.

Ray-Tracing Super Sampling

После поисков в Гугле решил пока оставить процедурное сглаживание и реализовал SSAA. Идея проста: Сначала делается стандартный 1x проход, в дополнительный буфер пишутся ID треугольников. Потом запускается kernel 3x3 и пиксели с различными ID маскируются в стенсель-буфере. Затем запускается "тяжёлый" шейдер, который выпускает несколько лучей в одном пикселе по заданному паттерну смещений. Стенсель тест реджектит выполнение этого шейдера вне маски. Полученный результат усредняется и записывается в буфер кадра. Примеры:

Aliased render:

Edge mask detection:

Ordered grid 4x:

Rotated grid 4x:

Optimal N-rook 8x:

Что интересно, на этом маленьком примере падение скорости не от множества лучей в маске, а от прохода, ищущего эту самую маску.

воскресенье, 15 ноября 2009 г.

Ну очень крутой рендер

Не предел совершенства, конечно, но видна профессиональная рука:



Особенно мне понравился эффект "испорченного сигнала" монитора.

пятница, 13 ноября 2009 г.

О всяком

Реализовал двусторонние преломления с использованием двоичного поиска по буферу глубины, как я и хотел ещё летом. Для референса использовал трансформации в world space и линейный двоичный поиск, затем реализовал non-linear binary search in texture space. Функция получилась весьма эффективной, цикл занимает 14 инструкций, conservative - чуть больше. Последний я пока не использую, т. к. для выпуклых линз он необязателен. Вообще binary search штука замечательная, очень быстро сходится в нужной точке, а с float depth buffer так вообще сказка. С реализацией пришлось повозиться, конечно, зато теперь я уверен, что трёхмерный вариант работает аналогично тестовым двумерным. Полноэкранный шейдер на моей колымаге ковыляет со скоростью ~ 30 fps.

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

Вчера пришла идея, как реализовать антиалиазинг при рэйтрейсинге (зачем мне этот антиалиазинг? - ну не могу я смотреть на эти лесенки!). Рендер в более высокое разрешение с последующим резолвом не годится - скорость. Но можно попробовать использовать тот факт, что наши рёбра - процедурные. Ведь сглаживают же процедурные текстуры (зебра, chekerboard) с помощью производных. Есть идея попробовать использовать барицентрические координаты для определения coverage пикселя. Рассмотрим процедуру рисования. Берём центр пикселя (или любое другое положение в пикселе, неважно, главное, чтобы оно было одинаковым для всех пикселей), это начало нашего луча. Ребро нашего треугольника - идеальный отрезок, алиазинг же происходит из-за двоичной природы теста на пересечение - луч попал/не попал. Очень часто может быть так, что треугольник покрывает часть пикселя, но центр пикселя не попадает в треугольник - не закрашиваем. А надо бы. Идея проста - смотрим, насколько далеко центр пикселя от ребра треугольника, и каким-то образом рассчитываем на основе этого coverage. А дальше, на основе coverage, смешиваем цвет на границе треугольника с цветом в буфере. Мне почему-то кажется, что это сработает. Я ещё покопаю сабж по процедурному сглаживанию и для пробы создам простую CPU реализацию.

Посмотрел "Письма с Иводзимы" Клинта Иствуда. Мораль такова: "Ты должен умереть за императора, и ниипёт".

среда, 11 ноября 2009 г.

Raycaster and MIP-filtering

На днях реализовал MIP-фильтрацию при рэйкастинге.

Вообще, я полагал что tex.Sample() правильно рассчитывает LOD текстуры только при содействии растеризатора. На самом деле это неправда! Оказалось, что LOD рассчитывается по производным правильно и в том случае, если рассчитанные при рэйкасте текстурные координаты приблизительно совпадают с интерполированными координатами из вершинного шейдера. При интерполяции через барицентрические координаты это именно так. Единственное, что не работает - выборка на рёбрах треугольника, т. к. производные от текстурных координат там неправильные. Представьте, что ребро треугольника проходит по центру квада 2x2. В одном пикселе мы получили пересечение и посчитали текстурные координаты, в другом пикселе - пересечения нет и текстурные координаты, скажем, равны 0. Тогда уже не получается правильно посчитать производные от текстурных координат к площади экрана, а значит, и степень наклона поверхности к экрану, и выбрать правильный LOD тоже нельзя. Получаются некрасивые "зазубрины" на рёбрах треугольников:



Не знаю, как эту ситуацию обрабатывает растеризатор, возможно, берётся LOD соседнего пикселя, или каким-то образом производные "достраиваются" в граничном кваде. Я заборол это следующим образом: считаю ddx() и ddy() от текстурных координат вне условия и проверяю abs значения. Если оно выше чем заданный эпсилон - производные неверные, мы на ребре треугольника. Тогда я просто делаю tex.SampleLevel() из нулевого MIP'а, иначе обычную выборку с анизотропной фильтрацией. Такой хак практически не виден даже при больших углах обзора:



[update]
Перечитал про производные и нашёл способ, гарантированно находящий неправильные производные на открытых рёбрах треугольников. Надо будет как-нить написать отдельный пост про это.

PS. И всё же, как растеризатор считает LOD на открытых рёбрах?

воскресенье, 8 ноября 2009 г.

NVidia OptiX

I'm waiting for Pacman and Space Invaders raytraced (this Pohl guy from Intel should port _them_ on LRB)

:)

70 и Бог

Решил утром прогуляться.

Взбираюсь на горку, тут меня останавливают мужчина с женщина средних лет. Первая реакция - хотят что-то втюхать, или может агитация за выборы... Нет, Свидетели. А вы верите в Бога, молодой человек? Нет, не верю - отвечаю я. Почему? А откуда, вы думаете, появился человек? И пошло-поехало. Первая реакция - надо валить но решил всё-таки задержаться. Рассказал вкратце им про материализм и научный метод. Затем понесло меня на геронтологиию, умпомянул про M-Prize и исследования в области старения клеток. Сказал, что если учёные со временем добьются успеха в этой области, Бог нам уже не понадобится. На сим категорично прервал беседу и пошёл дальше. Пускай подумают над этим, "свидетели" никем не виденного Бога. Впрочем и я, гуляя, тоже немало над этим поразмышлял...

суббота, 31 октября 2009 г.

Column-major vs Row-major

Теперь жалею, что когда-то решил использовать column-major матрицы в своей математической библиотеке. Во-первых, теперь приходится транспонировать их при передаче в D3D-шейдер, чтобы умножение вектора на матрицу можно было записывать как mul(v, M) (Direct3D), а не mul(M, v) (OpenGL). В первом случае это ложится на четыре красивые dp4 инcтрукции, во-втором - на комбинацию mul/mad. Во-вторых, для column-major матриц приходится записывать перемножение по правилу "post-multiplying":

WorldViewProj = Proj * View * World
HPos = WorldViewProj * Pos

Я не араб, и меня этот способ начал со временем напрягать. Придётся переписывать всю матричную библиотеку - ошибки молодости :( Думаю через шаблоны сделать возможность указать, какая именно матрица собирается использоваться - row-major или column-major, и если идёт присваивание матриц с разным порядком записи, чтобы осуществлялось автоматическое траспонирование:

Mat4< column_major > m1 = GetWorldViewProj();
Mat4< row_major > m2( m1 ); // transpose

среда, 28 октября 2009 г.

Ray-BV Intersection

Сегодня весь день обдумывал, в какую сторону двигаться дальше.

[Здесь была неверная инфа :)].
Полдня лазания по Гуглу и отладки кода, и в шейдеры легли максимально эффективные функции, тестирующие пересечения. Пересечение с боксом просто как две копейки. А люди выдумывают какие-то извраты через координаты Плюкера...

Тест на пересечение со сферой - 6 слотов инструкций:



Тест на пересечение с эллипсом - 14 инcтрукций:



Branchless тест на пересечение с AABB - 14 инcтрукций (включая одно деление):



При этом мне не нужно само пересечение, а только булево значение, а значит, нет необходимости в квадратном корне.

вторник, 27 октября 2009 г.

HD 2400 is slow

В общем провёл я предварительные тесты на производительность. Конкретно для Radeon HD 2400 результаты неутешительные - скорость падает приблизительно линейно с возрастанием кол-ва треугольников... Если для квада из двух треугольников получается ~100 fps, то для кубика из 12 треугольников - 20 fps. Для двух кубиков - 11... Скорость мало зависит от площади кадра, которую покрывают кубики, и от типа кушаемых данных - вещественные или байты, хотя при вещественных скорость снижается.

Понятно, откуда линейное падение скорости - от линейного увеличения длины цикла. Я не считал точно, но на глазок длина цикла ~60 инструкций (весь шейдер - 120). 24 треугольника требуют выполнить ~1440 + 60 = ~1500 инструкций. Боттлнек в недостатке вычислительной способности при тупом переборе циклом. Можно взять high-end видеокарту, но это только отодвинет верхнюю границу, после которой симптомы будут аналогичны.

В принципе результаты не так уж плохи (в расчёте на high-end), таким способом можно рассчитывать на возможность играться с несколькими десятками треугольников (мне нужно даже меньше). К тому же на HD 2400 динамический бранчинг нифига не фурычит, а только просаживает скорость :( Хотя очевидно, что он должен давать прирост, например, при cull-инге back-faced треугольников. На нормальном железе с нормальным бранчингом должен быть заметный выигрыш.

Очевидный резерв для таких забав на растеризаторах - использование какого-нить иерархического дерева для геометрии, с обязательным условием, что динамический бранчинг работает эффективно. Это позволит снизить кол-во вычислений, связанных с тестом на пересечение луча и геометрии, правда, появятся затраты на обход дерева. Честно говоря, мне сложно представить, как это можно впихнуть в пиксельный шейдер, и стоит ли - очень быстро всё равно не получится.

Вот как-то так. Но всё же я надеялся на чуть лучшие результаты.

PS. Ну, а что можно сделать с несколькими треугольниками? Поверьте, в умелых руках - очень многое :)

PPS. Вот перед сном думал, как можно ускорить.
1) Я делаю рэйкастинг для всех пикселей фреймбуфера, очевидно что это худший случай. Рэйкастинг - это потому что простейшая реализация. Для рэйтрейсинга легче. Если у нас есть рефрактор, не занимающий всю площадь экрана, то растеризатором сначала рисуем front-faced треугольники, а потом выполняем рэйтрейсинг.
2) Early stencil rejection. Делаем рэйтрейсинг в малю-ю-юсенький render target, разблуриваем получившуюся маску, "натягиваем" её на фреймбуфер и помечаем в стенсиле. Затем делаем нормальный рэйтрейсинг, стенсил тест отбрасывает ненужные фрагменты вне маски.
3) Почему-то подумалось об oct-tree со сферами, описывающими кубики-узлы. Тест на пересечение со сферой тривиален.

понедельник, 26 октября 2009 г.

Raycaster vs Rasterizer

It has begun... Первая реализация рэйкастера на DirectX 11!
Два текстурированных треугольника, диффуз + спекуляр, Radeon HD 2400, окно 1024x768, без мультисэмплинга.

Растеризатор, FPS ~= 390:


Рэйкастинг, FPS ~= 114:


Растеризатор, FPS ~= 490:


Рэйкастер, FPS ~= 123:



Два (нет, три) отличия этого метода от растеризатора - нельзя напрямую использовать MIP-фильтрацию и не работает мультисэмплинг. Ну и скорость :) Шейдер для рэйкастинга + шейдинга занимает сейчас около 100 инструкций. Я ещё пооптимизирую что можно, потом буду мерять, во что это выливается.

Дальше - сжатие данных и тесты. Посмотрим, сколько треугольников удастся отобразить, прежде чем FPS на моём лоу-энде упадёт до отметки 20.

How to pack normal into just 2 bytes

Необходимость в жёсткой оптимизации по чтению из памяти привели меня к упаковке предрасчитанных данных и вершин. Хотел было написать, как мне удалось реализовать упаковку нормали в unorm2 с потерей одного бита точности для хранения z sign. Но, порыскав по гуглу, нашёл великолепный анализ методов сжатия нормалей от Aras Pranckevičius (я и не думал, что их столько, видать deferred техники здорово включают изобреталку:):

Compact Normal Storage for small G-Buffers

Все представленные алгоритмы упаковывают нормаль в unorm2 и восстанавливают потерянную информацию, используя квадратный корень. Метод простой упаковки xy с последующей реконструкцией z оказался наименее качественным (зато наиболее быстрым). Видимо из-за dot(n.xy, n.xy), который усиливает ошибку квантования (а для world нормалей придётся пожертвовать ещё одним битом точности). Любопытый обзор, вероятно лучший в Сети - для поклонников deferred shading-a будет весьма ценнен. Я же собираюсь использовать наиболее быстрый вариант, т. к. у меня нормали будут интерполироваться по треугольнику, и каждую надо распаковать... Сойдёт и удовлетворительное качество, главное - минимум чтений из памяти.

четверг, 22 октября 2009 г.

Woop's unit triangle intersection test

После курения пейпров и вникания в кудовские кернелы реализовал и этот алгоритм. Математика - это вещь! Диву даёшься, как только получается реализовать полную проверку такого пересечения в несколько инструкций.

Кстати я не знаю точно, кто именно автор алгоритма. S. Woop указан в качестве соавтора пейпра, в котором рассматривается математика алгоритма, это правда. Но там же идут отсылки к более ранней работе J. Arenberg 1988 года, и говорится что это просто его расширенная версия. Но везде (презентации, на форумах) упоминается именно Woop.

Моя идея с матрицей преобразования хороша, но не пригодна. Впрочем, преобразование из одной системы координат в другую матрицей афинного преобразования - задача не новая, алгоритм Woop-a использует эту же идею. Проблема в том, что кроме самих текстурных координат мне нужны ещё как минимум интерполированные позиция и нормаль (растеризатор-то теперь мне ничего интерполировать не будет), и искать её удобно через те же барицентрические координаты. И алгоритм Мюллера, и алгоритм Вупа делают проверку через поиск барицентрических координат, а раз они уже есть, то использовать их для интерполяции вершинных значений - наиболее разумное решение.

Пока я фигачил тестовые реализации для этого тормоза CPU, в голове крутились мысли, как это должно быть реализовано на GPU класса DX10/11. Во-первых, зачем таскать текстурные координаты (а в перспективе - и нормали) вместе c precomputed данными? Ведь для поиска самого пересечения они не нужны, а требуются лишь тогда, когда найдено пересечение с треугольником и его индекс известен. Нужно отделить данные для интерполяции от precomputed данных для поиска пересечения, разнести их по двум буферам. Тогда буфер precomputed данных ужмётся до минимума, а значит, и фетчинг данных при линейном поиске по массиву пойдёт быстрее. А когда треугольник найден, то по индексу делаем выборку атрибутов вершин из второго буфера. Хотя тут и есть скачок по памяти, но он всего один на пиксель.

Тогда структура для алгоритма Мюллера должна быть такой:
struct prec_tri
{
float3 v0;
float3 e0;
float3 e1;
};

Тут к сожалению, в cbuffer пропадает впустую 3 вещественных, а это 12 байт из 48. Один из вариантов - использовать Buffer < float3 > и Load(). Для алгоритма Вупа достаточно матрицы 4x3 (четыре столбца по 3 элемента - поворот и перенос). Это те же 48 байт. А вот если мне нужна позиция в точке пересечения (для L, V), то не обязательно тащить вершины - можно попробовать найти по O + t * D, хотя неясно что будет с точностью и визуальным качеством. Но это так, мысли наперёд.

А вот вопрос, как именно фетчить: через cbuffer, tbuffer или Load() - очень интересен. Судя по описаниям в SDK, tbuffer оптимизирован для случайного доступа, cbuffer - для последовательного. Может оказаться, что это "шило на мыло". Можно упереться не в память, а в расчёты, kd-tree то не планирую, цикл соответственно будет только расти с ростом кол-ва треугольников. Да и моя HD 2400 очень тормозная железяка, грех на ней рэйтресингом баловаться, а может заниматься оптимизациями - в самый раз? :). Думаю, не купить ли на последние деньги HD 4770 или 4850, в районе 100$ сейчас...

Кстати, привет от компайлера шейдеров! Что-то вроде такого он пережёвывает секунд 10:

#define MAX_TRIANGLES 200

[loop]
for (int i = 0; i less than MAX_TRIANGLES; ++i)
{
prec_tri t = g_buf[ i ];
// Дальше куча расчётов.
}

Если взять, скажем, 500 - думает секунд 40. Ассемблерный листинг показывает, что цикл не разворачивается. Может компайлер проверяет валидность i для всех итераций цикла? Пробовал разные флаги подсовывать, убирать оптимизацию - бесполезно. Единственное, что помогло - замена compile-time MAX_TRIANGLES на значение из буфера констант. Тормоза пропадают. Какой из этого вывод? Незнание - это блаженство (с) The Matrix.

вторник, 20 октября 2009 г.

GPU Ray-Triangle Intersection

Общепризнанным стандартом здесь является алгоритм Мюллера-Трумбора:

Fast, Minimum Storage Ray/Triangle Intersection.

Написан давно (1997 г), но хорош и подходит для GPU. Принцип работы - поиск барицентрических координат пересечения u и v, имея которые, можно легко найти точку пересечения или её текстурные координаты:
w = 1 - u - v
tc = tc0 * w + tc1 * u + tc2 * v
В CPU версии на вход подаются начало луча, его направление и три вершины треугольника. На выходе - скаляр t на луче (наименьший означает ближайший треугольник), и uv. После этого, проверив (t < min_t), надо найти собственно сами текстурные координаты точки пересечения, для этого нужны текстурные координаты вершин треугольника.

Одними из факторов, серьёзно ударяющих по производительности RTI, являются фетчинг данных для треугольника и загруженность регистров (регистрового файла GPU):

Основная трудность трассировки лучей на GPU

И хотя это становится проблемой при больших массивах трассируемых данных, это своего рода указатель и для ограниченного случая. Что касается фетчинга данных, то статические треугольники должны браться из буфера констант (идём тупым перебором по всему массиву, упаси господи юзать какие-то kd-tree). В базовом варианте нам нужно:
struct tri
{
float3 v0;
float3 v1
float3 v2;
float2 tc0;
float2 tc1;
float2 tc2;
};
Для буферов констант важен alignment, поэтому предъявляется требование к выравниванию вектора по границе, кратной 16 байт (float4) (NOTE: Более точно, данные вектора не должны пересекать границу, кратную 16 байтам). Поэтому размер структуры - sizeof(float4) * 5 = 80 байт (два float2 группируются в один float4). Много, хотя хорошо укладываемся в 16-byte alignment. Попробуем сжать.

Как видно из кода алгоритма (ссылку приводил в начале), из трёх вершин треугольника используется только один, остальные нужны для нахождения векторов рёбер треугольника:
edge1 = v1 - v0
edge2 = v2 - v0
В структуру вместо вершин! Заодно осводождаем два слота инструкций. Третьи текстурные координаты распихиваем по w компонентам векторов рёбер. Итого получаем:
struct prec_tri
{
float3 v0;
float4 e0;
float4 e1;
float4 tc0tc1;
};
Укладываемся в 64 байта.

В героической попытке придумать алгоритм покороче и избавиться от поиска барицентрических координат, я решил искать текстурные координаты через матрицу трансформации. Представим, что e0 и e1 формируют не ортонормированный базис в object space, тогда:
t0 = tc1 - tc0
t1 = tc2 - tc0
формируют базис в пространстве текстуры. Третий орт не нужен, т. к. текстурная плоскость совпадает с плоскостью треугольника. Тогда:
Muv = Mobj * Mx
откуда:
Mx = Mobj^-1 * Muv
(запись для row-major матриц). Из-за того, что наш треугольник представлен в object space, нужно переводить точку пересечения в локальные координаты треугольника, а потом переводить в локальные текстурные координаты:
tc = (p - v0).xy * Mx + tc0
Достаточно оперировать матрицами второго порядка, т. к. фактически из всех афинных преобразований используются поворот и масштабирование на плоскости. Но это не всё. Т. к. оси Oy и Ot в Direct3D направлены в разные стороны, нужна матрица преобразования координаты t:
t = t * (-1) + 1
Кроме того, можно не хранить текстурные tc0, а записать их как translation в матрицу 2x3.
Итого:
Muv * Mflip = Mobj * Mx
Mx = Mobj^-1 * Muv * Mflip
tc = ((p - v0).xy, 1) * Mx
Естественно, что матрица предрассчитывается и заливается в буфер констант. Матрица 2x3 займёт 2 * 4 * 4 = 32 байта (NOTE: Впрочем, матрица 2x2 укладывается во float4, и если tc0 дополнить какими-то полезными данными до float4, матрицу 2x3 использовать нет смысла). Я протестировал этот метод в случае, если известны координаты пересечения луча с треугольником - работает отлично. Единственное, что ускользнуло от меня - вместо матрицы флипа t = t * (-1) + 1 удаётся использовать t = t * (-1). Загадка :)

Недостаток этого метода - необходима точка пересечения луча с треугольником, p, которая ищется по алгоритму Мюллера через те же самые барицентрические координаты, а значит, выигрыш мы здесь не получим.

Одной из самых перспективных альтернатив алгоритму Мюллера является Woop’s unit triangle test. Вот что удалось накопать по этой теме:

Realtime Ray Tracing of Dynamic Scenes on an FPGA Chip
RPU: A Programmable Ray Processing Unit for Realtime Ray Tracing
Пост whiteambit на ompf.org

Сейчас копаю эту тему. По идее, в unit space отпадает необходимость в (p - v0). Не знаю, что получится, но поиск текстурных координат пересечения по двум матрицам - это жёстко :)

Hybrid approach for refractions

Я представляю себе рендеринг преломлений как комбинацию binary search/cubemap sample и ray-tri intersection. Пока остальные товарищи с ompf.org всеми правдами и неправдами выжимают из ПЕЧи все соки (вместо того чтобы подождать декаду, пока не появится соотв. железо), мы пойдём другим путём. Для сложной геометрии, которая должна искажаться, я планирую применять binary search z-буфера. Но желателен и вариант с пересечением луча и треугольника, там где треугольников мало. Например, дисплей in-game компьютера можно представить всего двумя текстурированными треугольниками (или чуть побольше, чтобы представить объём и т. д.). Или другую мелочь... Вообще, пока я не хочу раскрывать, какие сцены у меня крутятся в голове, это секрет :). Но уже сейчас понятно, что ограниченный RTI нужно реализовывать, z-буфер слишком негибок для качественных преломлений простой геометрии.

четверг, 15 октября 2009 г.

How antialiasing works. Part 4.

Ранее я писал про антиалиасинг на GPU:

Part 1
Part 2
Part 3

Но тема охвачена не полностью, ещё есть что изучать. По мере сил я и дальше буду выкладывать в блоге что-нибудь интересное по ней. Тогда я оставил невыясненным вопрос, что происходит, если фрагментный шейдер пишет в SV_Depth (gl_FragDepth в OpenGL, регистр oDepth в asm). У меня самого до сих пор не стояла задача изменять глубину вручную.

Если мы не пишем в depth из шейдера, то это значение рассчитывается fixed-function pipeline интерполяцией по треугольнику. В случае MSAA, каждый сэмпл фрагмента получает своё индивидуальное значение глубины, и тест глубины проводится отдельно для каждого сэмпла. Фрагментный шейдер исполняется для фрагмента только один раз, и одинаковые значения цвета записываются только в те сэмплы, который прошли индивидуальный depth test. Благодаря fine-grained depth test, в местах пересечения геометрии получается сглаженная лесенка:
Если шейдер пишет в SV_Depth, то посколько он исполняется только один раз, то и значение глубины (как и цвета) получается одинаковым для всех сэмплов. И хотя depth test продолжает выполняться на уровне сэмплов, отличия проявляются только на фрагментном уровне. Эффект сглаживания, конечно, пропадает:
Direct3D 10.1 вводит такую возможность как per-sample fragment shader evaluation, подобную функциональность предоставляет и расширение GL_ARB_sample_shading (если с расширением всё ясно, то в Direct3D пока не нашёл, как включать). Данная возможность может быть использована при рендеринге растительности с альфа-тестом. Вероятно, можно решить и приведённую выше проблему, т. к. теперь для каждого сэмпла можно записывать (или нет) depth, рассчитанный интерполятором до шейдера - но я не пробовал (железа под рукой нет :().

среда, 14 октября 2009 г.

Conservative Binary Search

Реализовал поиск пересечения с backfaced поверхностью через двоичный поиск.

Можно задавать два критерия глубины поиска: максимальное кол-во делений на луче и дельту расстояния до поверхности от текущей позиции поиска. В 3D-случае можно дополнительно запоминать предыдущие текстурные координаты сэмпла и сравнивать их с новыми, если они лежат в пределах одного пикселя - дальше делить нет смысла. Для более точных и быстрых результатов желательно, чтобы исходный диапазон поиска был как можно меньшим. Для простоты я брал луч длиной чуть больше диаметра линзы. Скриншоты:

Глубина поиска - 5 шагов:


Видно, что найденные точки "пляшут" вокруг поверхности. При движении линзы неточности поиска видны ещё более явно.

7 шагов:Уже лучше, но при движении заметно "дрожание" точек.

12 шагов:

Начиная с 10 шагов, поиск становится почти точным. Нужно понимать, что кол-во шагов для каждого луча - это кол-во выборок из depth-текстуры для каждого обрабатываемого фрагмента в 3D-случае. Большое кол-во выборок на пиксель создаёт большую нагрузку при увеличении разрешения, поэтому важно делать их как можно меньше. Можно применять комбинацию последовательного поиска с последующим уточнением двоичным, но при малых величинах (~10) выигрыш сомнителен. В случае с линзой проще за начало луча брать не его пересечение с лицевой поверхностью, а позицию на преломлённом луче, отодвинутую от начала на 1/2-1/3 диаметра линзы - можно сэкономить пару шагов при двоичном поиске.

Как бы то ни было, основная задача - попиксельная точность пересечения луча с backfaced геометрией. Вообще, как я считаю, в задаче real-time refraction главным является предельная точность и аккуратная обработка результатов, внимание к мелочам, что поможет создать правдоподобную иллюзию объёма и искажения, а не очередную поделку "на шейдерах".

People Can Fly

People Can Fly

Помню финальную серию 1998 года: Chicago Bulls - Utah Juzz. Был настоящий драйв, и Бог баскетбола выделывал иногда такое...

воскресенье, 11 октября 2009 г.

Fresnel Reflection

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

Кто занимается графикой, знает, что в эпоху Shader Model 2.0 были очень популярны различные аппроксимации уравнений Френеля, например, аппроксимация Шлика. Если поискать, можно легко их найти в "старых" шейдерах, реализующих там воду или стекло. Не знаю, как в Крайзисе считается, но в эпоху Shader Model 4.0/5.0 уже пора завязывать с этими аппроксимациями и считать подобные вещи честно. На самом деле вычислений здесь - кот наплакал. Если подразумевается использование преломлённого луча, то это значит что у нас уже есть косинусы углов падения и преломления. Придётся сделать всего семь умножений, два деления, плюс пять арифметических операций сложения/вычитания, чтобы получить коэффициент для неполяризованного света. Если преломления не считаются, а есть только угол падения, придётся использовать вариант с трансцендентными функциями. В этом случае формулу лучше запечь в текстуру и делать в шейдере выборку. Впрочем, первый вариант тоже является кандидатом на запекание в текстуру: cами по себе расчёты не сложны и не займут много инструкций (по нынешним меркам), но по моим предварительным оценкам, сложный шейдер, реализующий правдоподобный эффект преломления, выльется этак в 400-500 инструкций. В этих условиях целесообразнее сделать дополнительную выборку из текстуры, заодно и соотношение ALU/TEX будет выполняться получше.

Я написал тест, чтобы проверить, как распространяется эффект Френеля на энергию луча (и отладить математику, отлаживать её в прямо в шейдере - то ещё удовольствие). Вот скриншоты, показывающие преломление/отражение для воздуха и стекла:

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

Немного увеличим угол, эффект Френеля всё ещё не заметен:

При значительных углах видно, что отражённый луч получает все большую долю энергии падающего луча:

Почти предельный случай: почти вся энергия луча вкладывается в отражения (первое и второе).

А вот графики функций для стекла (по оси абсцисс - угол падения, по оси ординат - значение коэффициента). Для s-polarized (синий цвет) и p-polarized (красный):



А вот усреднённое значение для неполяризованного света:


Заметьте, что коэффициент в последнем случае никогда не равен нулю, т. е. во всех случаях часть энергии луча уходит в отражение, что подтверждает первый скриншот.

Думаю, с Френелем всё понятно (для CG-случая, физическая сторона вопроса очень глубока).

P. S. Реализовал трассировку луча для линзы, наполненной водой. Вот как это выглядит:

Хорошо видны две "мертвые зоны" по бокам обзора. Также хорошо видно, как странно ведёт себя луч рядом с этими зонами. Поэкспериментируйте - налейте в стеклянную бутыль воды и посмотрите, как искажается изображение на мониторе. А потом сравните с картинкой. Я сравнивал - всё правильно :)

Math terms

Если вам доводилось писать комплексные BRDF в шейдере, то наверняка вставала задача, как оптимально разбить вычисление компонентов формулы и как назвать переменные, которые бы хранили промежуточный результат расчётов.

Часто можно встретить названия переменных вроде amb, что означает "a minus b". Между тем, немногие знают, что существует достаточно богатая, исторически сложившаяся терминология, применяемая к компонентам математических выражений. Простейший пример, известный всем: числитель (numerator) и знаменатель (denominator). Но есть и термины, известные только узкому кругу математиков.

Вот я нашёл прекрасный толковый словарь математических терминов, составленный Pat Ballew:

MATH WORDS, AND SOME OTHER WORDS, OF INTEREST

А вот список терминов, которые я "накопал" - они могут (теоретически) применяться в обозначении того или иного term'а формулы:

Addend
Subtrahend
Minuend
Residue
Multiplicand
Multiplier
Product
Mean
Magnitude
Divident (Numerator)
Divisor (Denominator)

В словаре толкуется историческое происхождение этих и многих других математических терминов, в основном это корни древних латыни и греческого языков. Думаю, многим будет интересно узнать происхождение слова "compute" :)

среда, 7 октября 2009 г.

Research In Refraction

Ранее я уже писал, что хочу заняться преломлениями и отражениями. Поэтому я начал собственный research в этой области, т. к. задача нетривиальная. В перспективе это должно вылиться в кульное DX11-demo.

Сначала разберёмся с физической стороной проблемы. Преломление - это изменение направления следования светового луча, возникающее на границе двух прозрачных сред с различной плотностью. В вакууме скорость света c составляет приблизительно 299 800 км в секунду. Когда луч путешествует в среде с ненулевой плотностью, его скорость замедляется. Замедление является функцией от длины волны и материала, из которого состоит среда. Чем выше плотность, тем сильнее замедляется луч. Это не проходит бесследно, видимый эффект заключается в изменение угла между нормалью преломляющей поверхности и направлением движения луча. Попав опять в вакуум, луч света приобретает прежнюю скорость с, а угол восстанавливается.

Преломление света описывается законом Снелла.

Для того, чтобы рассчитать, как луч будет преломляться на границе двух сред, используются индексы рефракции материалов, из которых эти среды состоят. Индекс рефракции n определяется по формуле:
n = c/v
где с - скорость распространения света в вакууме, v - скорость распространения в материале.

Индекс рефракции в вакууме равен 1, а это значит, что индекс рефракции любого материала всегда больше 1. Чем выше плотность, тем сильнее замедляется луч, тем выше становится индекс рефракции. Наименьшие индексы имеют различные газы, наибольшие - кристаллы. Вот пожалуй и всё по теории.

Раскопав таблицы индексов рефракции, я реализовал схематическое преломление луча для плоского стекла и для выпуклой линзы из различных материалов, чтобы разобраться в математике. Плоское стекло:

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

А вот я начал играться с линзой из различных материалов. К сожалению, линза не "отшлифована" как следует - вершины задавал на глазок, поэтому чёткий фокус получить не удалось. Тем не менее видно, что всё вычисляется корректно. Стекло:

Кварц:

Рубин:

Алмаз (диамант):

Проверка математики, если в линзе воздух:

А вот так свет будет преломляться, если в линзе будет воздух и она (линза) будет помещена в воду:

воскресенье, 4 октября 2009 г.

Shader Model 5.0 Dynamic Linking

Интересно стало, как же устроена данная фича. Во-первых: работает только в SM 5.0. Т. е. это не просто какая-то заумная идея замены #ifdef в шейдерах, а реализована посредством поддержки в железе. Во-вторых: ни в SDK, ни в MSDN нет описания ассемблера Shader Model 5.0. Четвёртого есть, пятого - нет, поэтому остаётся только догадываться, что означает та или иная запись/команда. Во всем Гугле есть только одна ссылка касательно ассемблера пятой модели - какой-то японец тоже активно копает эту тему. Думаю скоро Google проиндексирует и этот пост :)

Разобравшись с механизмом подачи инстансов реализаций в шейдер, я набросал простенький код и несколько вариаций на тему, чтобы понять, как всё работает. Исходный код:
interface IColor
{
float3 Get();
};

class Red : IColor
{
float x;
float3 Get() { return float3(1.0, 0.0, 0.0); }
};

class Green : IColor
{
float x;
float3 Get() { return float3(0.0, 1.0, 0.0); }
};

IColor g_Color;

cbuffer cbClassInstances
{
Red g_Red;
Green g_Green;
}

float4 VS(float4 vPos : POSITION) : SV_Position
{
return vPos;
}

float3 PS(float4 vPos : SV_Position) : SV_Target
{
return g_Color.Get();
}

Есть переменная абcтрактного типа и два инстанса реализаций. Данный вариант назовём условно 1x2. Ассемблерный выхлоп:
ps_5_0
dcl_globalFlags refactoringAllowed
dcl_function_body fb0
dcl_function_body fb1
dcl_function_table ft0 = {fb0}
dcl_function_table ft1 = {fb1}
dcl_interface fp0[1][1] = {ft0, ft1}
dcl_output o0.xyz
dcl_temps 1
fcall fp0[0][0]
mov o0.xy, r0.xyxx
mov o0.z, l(0)
ret
label fb0
mov r0.xy, l(0,1.000000,0,0)
ret
label fb1
mov r0.xy, l(1.000000,0,0,0)
ret

Видно что объявляются прототипы функций (dcl_function_body). Далее мои фантазии. Ниже, объявляется таблица функций с "указателями" на адреса (метки). Каждая таблица содержит в фигурных скобках перечисление имён функций (меток), принадлежащих конкретной реализации интерфейса. Ещё строкой ниже - наш интерфейс, который связывается с одной из перечисленных в фигурных скобках таблицей функций. Какой именно - зависит от того, какой инстанс передать при вызове ID3D11DeviceContext::PSSetShader(). Функции ::Get() реализованы после основного кода шейдера как пары label/ret, легко проследить что кому принадлежит. Вызов нужного метода по установленному адресу (метке) производится новой командой fcall.

Вариант 1x3 отличается тем, что добавлена третья реализация IColor, Blue:
ps_5_0
dcl_globalFlags refactoringAllowed
dcl_function_body fb0
dcl_function_body fb1
dcl_function_body fb2
dcl_function_table ft0 = {fb0}
dcl_function_table ft1 = {fb1}
dcl_function_table ft2 = {fb2}
dcl_interface fp0[1][1] = {ft0, ft1, ft2}
dcl_output o0.xyz
dcl_temps 1
fcall fp0[0][0]
mov o0.xyz, r0.xyzx
ret
label fb0
mov r0.xyz, l(0,0,1.000000,0)
ret
label fb1
mov r0.xyz, l(0,1.000000,0,0)
ret
label fb2
mov r0.xyz, l(1.000000,0,0,0)
ret

Часть кода из варианта 2x2:
IColor g_Color0;
IColor g_Color1;

float3 PS(float4 vPos : SV_Position) : SV_Target
{
return g_Color0.Get() + g_Color1.Get();
}

Ассемблер 2x2:
ps_5_0
dcl_globalFlags refactoringAllowed
dcl_function_body fb0
dcl_function_body fb1
dcl_function_body fb2
dcl_function_body fb3
dcl_function_table ft0 = {fb0}
dcl_function_table ft1 = {fb1}
dcl_function_table ft2 = {fb2}
dcl_function_table ft3 = {fb3}
dcl_interface fp0[1][1] = {ft0, ft1}
dcl_interface fp1[1][1] = {ft2, ft3}
dcl_output o0.xyz
dcl_temps 2
fcall fp0[0][0]
fcall fp1[0][0]
mov r0.z, l(0)
mov r1.z, l(0)
add o0.xyz, r0.xyzx, r1.xyzx
ret
label fb0
mov r0.xy, l(0,1.000000,0,0)
ret
label fb1
mov r0.xy, l(1.000000,0,0,0)
ret
label fb2
mov r1.xy, l(0,1.000000,0,0)
ret
label fb3
mov r1.xy, l(1.000000,0,0,0)
ret

И ассемблер 2x3:
ps_5_0
dcl_globalFlags refactoringAllowed
dcl_function_body fb0
dcl_function_body fb1
dcl_function_body fb2
dcl_function_body fb3
dcl_function_body fb4
dcl_function_body fb5
dcl_function_table ft0 = {fb0}
dcl_function_table ft1 = {fb1}
dcl_function_table ft2 = {fb2}
dcl_function_table ft3 = {fb3}
dcl_function_table ft4 = {fb4}
dcl_function_table ft5 = {fb5}
dcl_interface fp0[1][1] = {ft0, ft1, ft2}
dcl_interface fp1[1][1] = {ft3, ft4, ft5}
dcl_output o0.xyz
dcl_temps 2
fcall fp0[0][0]
fcall fp1[0][0]
add o0.xyz, r0.xyzx, r1.xyzx
ret
label fb0
mov r0.xyz, l(0,0,1.000000,0)
ret
label fb1
mov r0.xyz, l(0,1.000000,0,0)
ret
label fb2
mov r0.xyz, l(1.000000,0,0,0)
ret
label fb3
mov r1.xyz, l(0,0,1.000000,0)
ret
label fb4
mov r1.xyz, l(0,1.000000,0,0)
ret
label fb5
mov r1.xyz, l(1.000000,0,0,0)
ret

Как видим, код каждой реализаций дублируется столько раз, сколько у нас объявлено интерфейсов. Очевидно, что весь этот код не участвует в работе шейдера (а только тот, который вызывается), но он пожирает слоты инструкций и дольше загружается в кэш. По каким-то причинам два одинаковых интерфейса не могут вызывать функцию по одному и тому же "адресу", и они плодятся как кролики :) Возможно, так получается эффективнее в случае потоковой архитектуры GPU.

И последнее. Пускай наш интерфейс продиктует необходимость реализации ещё нескольких незамысловатых функций:
interface IColor
{
float3 Get();
float Alpha();
float Intensity();
};

Остальной код я не привожу, думаю от понятен. Ассемблерный выхлоп для 1x2:
ps_5_0
dcl_globalFlags refactoringAllowed
dcl_function_body fb0
dcl_function_body fb1
dcl_function_body fb2
dcl_function_body fb3
dcl_function_body fb4
dcl_function_body fb5
dcl_function_table ft0 = {fb0, fb2, fb4}
dcl_function_table ft1 = {fb1, fb3, fb5}
dcl_interface fp0[1][3] = {ft0, ft1}
dcl_output o0.xyzw
dcl_temps 2
fcall fp0[0][0]
fcall fp0[0][1]
fcall fp0[0][2]
mov r0.z, l(0)
mul o0.xyzw, r0.xyzw, r1.xxxx
ret
...
...

пятница, 2 октября 2009 г.

GT300, игры и борьба с пиратством

NVIDIA пошла на досрочное разглашение подробностей нового поколения своих GPU... Видимо пытаются подогреть интерес из-за проблем с выпуском годных чипов. Если всё, что они понаписывали - правда, и новый чип может исполнять хоть в каком-то виде код C++ - то Intel пора хвататься за голову. Можно представить себе, как в 2012 выйдёт новый универсальный потоковый процессор от NVIDIA на её же материнской плате, выполняющий через эмулятор код старых x86 программ в 10 раз быстрее какого-нибудь 8-ядерного Intel Core i10... Помните, что случилось с Silicon Graphics?

PS. А пока что NVIDIA показывает фейковые прототипы с отпиленной (ножовкой) PCB. Интересно, был ли хоть чип под системой охлаждения? Совсем обнаглели.

Ещё одна интересная тема - а зачем, собственно, делать новые видеокарты, если рынок PC-игр, похоже, верно загибается? Всякая шняга, конечно, на нём всегда будет присутствовать, но на новые крупные многомиллионные тайтлы (способные показать "красу" и утилизировать мощь топовых видеокарт) придётся закатать губу. Crytek фичекатят енджин под дряхлый PS3 - "больше никаких эксклюзивов на PC". Есть правда Rage... Думаю, что чем больше распиарят новые DirectX 11 игры, тем быстрее их повзламывают и повыкладывают на торрентах. Замкнутный круг. Пока отсутствие софта не скажется на спросах на железо, которое этот самый софт должно запускать, HW-вендоры, похоже, проблему нелицензионного копирования решать не намерены.

Вот пришла интересная идея, как ограничить запуск одной лицензионной копии игры одной аппаратной конфигурацией. Основана, как и прошлая идея с "remote function execution", на том, что пользователь получает в своё распоряжение не весь код игры, а только часть - на этот раз, без шейдеров :). Для реализации необходимо, чтобы в GPU видеокарты был встроен механизм криптования бинарных шейдеров (та часть, что отвечает за дешифровку) и зашит уникальный ключ для дешифровки. Механизм защиты следующий:

Шейдеры в виде исходных кодов хранятся только на сервере издателя. В процессе первого запуска игры юзер подключается к серверу издателя игры (нужен интернет), вводит серийный номер с диска и задаёт свои уникальные имя/пароль, игра отсылает их на сервер. Если сервер подтверждает уникальность серийного номера копии игры, то дальше игра отсылает модель GPU, уникальный GPUID, версию установленного видеодрайвера и т. д. Затем на сервере хранящиеся там шейдеры компилируется в бинарные блобы, подходящие под GPUID и видеодрайвер пользователя и шифруются ключом (на сервере хранится таблица пар GPUID/ключ). Получается такой shader cache из зашифрованных бинарных шейдеров, который единожды передаётся и инсталлируется на машине игрока. В таком виде шейдеры загружаются в видеокарту, а там GPU использует свой ключ для их дешифровки перед загрузкой кода в видеопамять. Предполагается, что прочитать из видеопамяти расшифрованный бинарник невозможно.

Всё. Полученный shader cache будет работать только с тем GPU, ключ которого соответствует ключу, использованного при его шифровании. Если пользователь сменил аппаратную конфигурацию, то процедуру получения нового кэша придётся повторить, при этом введя свои имя/пароль и серийный номер диска. При этом "аккаунт" для старой железки становится невалидным.

четверг, 1 октября 2009 г.

Луна 2112

Посмотрел камрип. Зачётное кино! Люблю такую фантастику.
PS. Если что - камрип это потому, что у нас его не показывают в кинотеатрах. А так бы сходил.

вторник, 29 сентября 2009 г.

"Программистcкий" английский

Многие программисты, как я обнаружил, очень легкомысленно относятся к англоязычным терминам и вместо того, чтобы посмотреть правильное произношение того или иного слова, выдумывают собственное. Понятно что каждый выдумывает что-то своё и в итоге получается дикий разнобой в произношениях. Я же взял себе в привычку стараться правильно произносить термины и аббревиатуры, т. к. считаю это признаком хорошего тона и уважения к своей профессии.

Например, CPU и GPU. Многие произносят их как "Цэ-Пэ-У" и "Гэ-Пэ-У". Я так не могу! Путём некоторых усилий у меня выработалась привычка произносить эти аббревиатуры правильно: "Си-Пи-Ю" и "Джи-Пи-Ю".

Или вот другой пример. Популярное словечко "deferred" я раньше произносил с ударением на второй слог. Мой лид - с ударением на первый. При этом оба произношения можно было записать как "Дэферред". Я решил заглянуть в Google Dictionary и обнаружил, что звучит это слово на самом деле примерно как "Ди'фё(у)р(д)" (ударение на второй слог, "d" практически не слышно):
deferred. Круто.

Сделал вывод: надо не лениться и почаще заглядывать в Google Dictionary, а то стыдно сыпать доморощенными произношениями.

четверг, 24 сентября 2009 г.

ID3D11CommandList

Занятно, что в D3D 11 появился этот интерфейс (в 10 его не было, в 9 были какие-то функции для записи/воспроизведения стейтов), в то время как в OpenGL 3.2 дисплейные списки убрали. Слышал, что парни из NVIDIA недовольны таким решением - ещё бы, после стольких лет отладки этих самых списков! Тред на эту тему можно почитать здесь: Siggraph Asia 2008 slides suggestions for OpenGL.

Вся беда в том, что хоть у NVIDIA они и отлажены, но в целом это дикая штуковина. Вот пример:
glNewList(42, GL_COMPILE);
glVertex3f(0,1,0);
glColor3f(1,0,0);
glVertex3f(1,1,1);
glEnd();
glEndList();

glBegin();
glColor3f(0,1,0);
glVertex3f(0,0,0);
glColor3f(0,0,1);
glCallList(42);
// note the lack of glEnd() - it's in the display list!

В общем, комитет отправил эту хрень в преисподнюю, вслед за immediate mode.

В Direct3D 11 схема работы следующая: можно создать один immediate контекст, для которого вызовы складываются в command buffer и выполняются, а можно в дополнение создать множество deferred контекстов, для которых вызовы складываются во внутренний command list, и после вызова ID3D11DeviceContext::FinishCommandList() вы получаете указатель на объект интерфейса ID3D11CommandList, в котором записаны все команды, поданные со времени предыдущего вызова ::FinishCommandList() или со времени создания контекста. Затем этот command list можно выполнить на immediate контексте вызовом ID3D11DeviceContext::ExecuteCommandList().

Сначала я недоумевал, почему есть Finish функция, но нет Begin. Ответ прост - сами по себе любые вызовы для deferred контекста не имеют никакого значения, они не идут в command buffer, а значит, и обрамляющая пара Begin/End - не нужна.

Судя по тому, что написано в SDK, command lists формируются очень быстро (не так медленно, как скажем, стейты через ::Create*State()), их можно формировать каждый кадр, параллельно, на нескольких ядрах в многоядерной системе. Если же драйвер/железо не поддерживают это, то command lists всё равно полезны как средство формирования command buffer, скажем, перед циклом рендеринга. Правда, пока неясно, что именно туда можно складывать - помните, сколько было ограничений в OpenGL с этим: "Certain commands, when called while compiling a display list, are not compiled into the display list but are executed immediately."