Candide

Скоро у нас будет новый кандид:

Вместо стандартного рисования линий средствами OpenGL ES я решил расчитывать сглаженную линию в шейдере. Для этого вокруг каждой линии рисуется "конвертик"из triangle-strip и в шейдер передаются начало и конец отрезка и его толщина. В шейдере рассчитывается расстояние от фрагмента до центра линии, плюс добавлен суперсемплинг 16x для максимально сглаженного результата. Вся геометрия рисуется одним вызовом.

Сначала "конвертики" рисовались с включенным аддитивным блендингом, чтобы линии нормально накладывались друг на друга. Но это приводит к всеобщей распространнённой проблеме ярких "узелков", где сходится больше двух линий:

В итоге было решено задействовать расширение EXT_shader_framebuffer_fetch которое доступно начиная с iPhone 6. Благодаря заточенности железа под тайловый рендеринг, в шейдере вы можете получить цвет фрагмента из render target-а, что недоступно на десктопных графических картах в силу их не-тайловой архитектуры. Имея доступ к цвету в памяти, вы можете сложить его с цветом полученным в шейдере так, как вам удобно - получив по сути программируемый блендинг. Сделав так, чтобы суммарная яркость не превышала уже существующий порог, можно избавиться от ярких "узелков".

На FullHD экране телефона новый кандид выглядит очень здорово!

Looksery Inc

Теперь я работаю в этом стартапе:

И у меня появился реальный шанс сесть на трактор!

:)

Теперь всем ясно что...

Вот так работает большинство программ

Procedural Textures

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

diffuse + normalmap + phong lighting

Pixar's ToyBall

Вся мякотка в том, чтобы рассчитывать сглаженные переходы между границами разных цветов, иначе будет видна попиксельная лесенка. smoothstep, fwidth, frac и floor в помощь. Колдовать приходится много, но сглаженный результат того стоит.

Недостатком таких текстур является отсутствие фильтрации mip-уровней, из-за чего при удалении начинает сказываться point семплирование. Как решение можно написать вручную собственную фильтрацию с множеством процедурных выборок, как сделано в этом шейдере от Inigo Quilez. Врочем, писать свою фильтрацию придётся и в случае с обычными текстурами, т. к. железо делает её в fixed function на основе экранных деривативов, а при рей-трейсинге это нужно делать вручную.

Depth of Field Ray-Traced

Набросал за час демку рей-трейсинга Depth of Field эффекта. В сущности отличий мало от AA-метода, только лучи не параллельны друг другу, а сходятся в точке, где луч-centroid пересекается с фокальной плоскостью. Радиус Circle of Confusion можно легко варьировать.

Метод даёт правдивые результаты, но не отличается быстродействием. Нужно множество лучей (на скриншотах - 32 + jittering), чтобы снизить шум, т. е. сцена семплируется много раз.

Если у вас не простые сферки с фонгом, а что-то потяжелее, то в реал-тайме работать уже не сможет. В сущности, комбинация нескольких нечётких эффектов может замедлять рендеринг в геометрической прогрессии. Например, пиксель содержит пенумбру тени, которую считаем по 16 семплам. Но это для pinhole камеры. Если тот же самый пиксель нужно отобразить для камеры с большой апертурой, например с 32 семплами для DoF, то получится что к солнцу нужно пустить 32x16=512 лучей, и это при скромных начальных условиях. Для production quality рендера количество лучей будет измеряться тысячами.

AA Edge Detection

На выходных возился с оптимизацией оверсемплинга при рейтрейсинге. Идея старая: запускать множество лучей не в каждом пикселе, а только там, где наблюдается лестница алиасинга. Для этого, например, в deferred-renderer-e ищутся контуры объектов, а затем либо по stencil test либо по discard в шейдере запускается множество лучей только для тех пикселей, которые входят в контур. Вопрос как искать эти самые контуры? Путей несколько:

Для пробы я написал шейдер, который берёт depth в camera space (t на луче), определяет дельты между соседними пикселами и по threshold решает быть тут контуру или нет. Это не работает как нужно из-за того, что t меняется нелинейно в screen space, из-за этого вдалеке дельты рано или поздно становятся больше критического значения и маска заливает весь объект. Для корректной работы нужен linear z в screen space, Humus как-то писал на эту тему: A couple of notes about Z. Для этого нужно писать в depth z/w, который интерполируется растеризатором в screen space, тогда деривативы будут давать константный шаг, но в рейтрейсере так сделать не получится.

Другой вариант - брать косинус угла (dot) между соседними нормалями и если он больше некоего threshold то помечать здесь контур. Это неплохо работает, но с оговорками: например, нормали могут совпадать у геометрически разных объектов в некоторых участках изображения, тогда контур определён не будет. Или например в случае bump-mapping'а или похожих алгоритмов может давать "фальшивые" контуры. По-видимому, надёжный алгоритм должен быть многогранным и оперировать всей информацией, которая вносит вклад в создание discontinuities, как на рисунке вверху. Я решил что для стартового варианта лучше всего записывать ObjectID в отдельный канал, и если normal test ничего не дал, проверять контур по ID. В принципе на простых объектах сам ID-тест работает лучше чем тест нормалей, но предсказуемо будет давать ошибки на сложных объектах, части которых могут перекрываться на экране. Поэтому комбинация нескольких тестов тут практически обязательна.

Interview with Nvidia engineer about DirectX 12

ВНЕЗАПНО архитектура GCN лучше подходит для DX12, чем Maxwell/Kepler.

Simple Ray-Tracing

Написал для разминки простую демку рей-трейсинга.

В сцене 40 треугольников, включая "солнце". В пиксельном шейдере брутфорсом ищется пересечение для закастованных лучей. Потом строится второй луч по направлению к солнцу и ищется пересечение с любым блокером - получается тень. Геометрия трансформируется в world space в compute-шейдере перед проходом рейтрейсинга.

На моей старенькой ATI занимает около 3-4 мс в разрешении 512x512.

AdBlock

У меня в Хроме стоит Adblock Plus, и я всё чаще стал замечать, как на различных сайтах вывешиваются жалобы с просьбой отключить эту штуковину. Видимо, статистика кликов по баннерам серьёзно упала, раз многие стали плакать крокодильими слезами. "Внезапно" на 3DNews появилась аналогичная жалоба, значит их тоже прижало. К счастью (а для кого-то к несчастью), окно браузера - это не зомбоящик, где рекламодатели могут втюхивать рекламу с выкрученным на максимум звуком, всё режется также просто как и добавляется. Что интересно, так это посмотреть чем эта война закончится:

1. Сайт вынудит меня добавить их в список исключений
2. Заставят искать другой похожий ресурс
3. Найдут иной способ монетизации
4. Будут показывать рекламу только домохозяйкам, которые не слышали про баннерорезки
5. Загнутся

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

Windows 10 is a flop

Поставил на виртуалку Windows 10 Build 10240. Немного поюзал, запустил новый MS Edge, метро-приложения, магазин...

Убила новая морда у окошек - выглядит вырвиглазно, потеряна какая-то строгость и чёткость UI, которая была в Windows XP/7. Всё какое-то новомодное и неуклюжее. Разнобой в интерфейсах, начиная от меню Пуск, продолжаясь в Проводнике и Панели управления и кончая метро-приложеними, просто поражает. Это какая-то сборная солянка из MFC, .NET и XAML, части которой делали разные отделы внутри корпорации и в разное время, а потом всё это собрали в один билд и назвали Windows 10. Что-то сломалось внутри Microsoft, и недавние перестановки в топ-менеджменте это только подтверждают. В общем желания ставить новую Виндоуз основной ОС не возникает, по крайней мере до широкого распространения DirectX 12 в играх.

P. S. Браузер Edge действительно неплохо оптимизирован, например на старом ноутбуке с Intel Core M фильмы с video.mail.ru в нём воспроизводятся плавнее, чем в Chrome.

Dynamic BVH

Первая рабочая реализация BVH дерева для skinned моделей:

Структура дерева предрассчитывается и размещается в нескольких GPU-буферах. Меш модели скинится, и описывающие объёмы дерева рассчитываются динамически в compute shader-e под геометрию меша.

Skinned модель и её BVH

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

Трассировка отдельного луча на CPU

Кроме рекурсивной трассировки, я набросал на CPU итеративную версию алгоритма, т. к. DX11-шейдеры не поддерживают рекурсию. Итеративная версия использует std::stack, и практически аналогична по смыслу рекурсивной. На GPU такой стэк можно реализовать в виде фиксированного массива в шейдере (SM 4.0 indexable temp) и индекса в этом массиве. Вероятно, возможны другие варианты итеративного алгоритма, это станет предметом рассмотрения в будущем. 

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

Pixar Releases Free Non-Commercial RenderMan

RenderMan

Закон Амдала

При чтении IT ресурсов наткнулся на так называемый Закон Амдала. Он описывался ещё на заре появления многоядерных процессоров в десктопных конфигурациях, например здесь:

Программное обеспечение многоядерных систем

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

Недавно на 3Dnews появилась любопытная статья:

Эксперимент: 12-ядерный процессор в десктопе, 

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

Итак, что же мы имеем? 

1) Тактовая частота CPU застряла где-то в районе 4-5 ГГц;

2) Cкорость вычислений на отдельном ядре почти не растёт; 

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

4) Со стороны ПО масса проблем. Даже последние игры с поддержкой DX11, грубо говоря - однопоточны, т. к.однопоточен сам DirectX. Даже видеокодеки x265 плохо масштабируются после определённого барьера.

5) 12-ядерный процессор в десктопных конфигурациях лишён смысла.

Неудивительно теперь, почему Intel медлит с выпуском мультиядерных процессоров в обычный пользовательский сегмент. Себестоимость производства таких кристаллов обойдётся дороже, а значит и стоковая стоимость будет выше. А когда пользователи увидят результаты тестов этих процессоров, они зададутся вопросом - за что они платят, покупая новую модель? Неудивительно, что Intel бросились в энергоэффективность - уменьшают нормы техпроцесса, поют на каждом шагу про TDP, добавляют AVX, AVX2, AVX 3 и ещё Бог знает какие инструкции... А правда тут одна - развитие процессоров заходит (или уже зашло) в тупик, и трудно сказать, как будет действовать Intel (и другие), и что их ждёт в будущем.

Fastest memcpy

В Сети полно тредов с обсуждением, можно ли обогнать memcpy из С lib. Из спортивного интереса я тоже решил поэкспериментировать с этим, зная что многие пытаются использовать SSE для копирования памяти через регистры xmm. Сделаем несколько допущений:

1) Большой кусок памяти (мегабайты).
2) Память выровненна по границе 16 байт.
3) Таргет CPU с обязательным наличием SSE2.
4) Соревнуемся с memcpy из VS 2012.

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

После различных попыток я в конце-концов остановился на комбинации SSE интринсиков _mm_stream_load_si128 / _mm_stream_si128 для копирования блоков памяти и _mm_prefetch(_MM_HINT_NTA) для указания процессору о том, что не нужно загрязнять кэш данными, так как они используются только короткое время. В x64 используются дополнительные регистры xmm8-xmm15, чтобы сократить кол-во блоков (итераций цикла) копирования. Тестовая программа состоит из 1000 циклов копирования кусков памяти размером 16Mb. Каждый цикл повторяется 10 раз чтобы удостовериться в правильности времени выполнения.

Результаты для процессора AMD FX-8320, release x86 и x64:

Судя по тому, что время отличается незначительно для x64, можно сделать вывод что CRT версия проигрывает из-за универсальности. Если бы не было 1000 циклов, эффект от ускорения был-бы несущественным. В x86 ускорение уже значительное, возможно Microsoft не удосужились оптимизировать runtime для архитектуры Bulldozer.

Кроме этого, я решил реализовать мультипоточную версию функции копирования и посмотреть, исполняется ли она эффективнее на многоядерном процессоре. Мультипоточная версия очень проста: она использует функции API Windows CreateThread/Semaphore, а также WaitForMultipleObjects для ожидания окончания работы множества потоков основным потоком. Это обеспечивает ясность над процессом распределения инструкций. Блок памяти делится на равные (по возможности) части и каждая часть копируется отдельным потоком.

Результаты для x64.
2 потока:

4 потока:

 8 потоков:

Как видно, использование самописного SSE и двух потоков в сумме даёт прирост в скорости около 40%. Дальнейшее увеличение кол-ва потоков практически не имеет смысла, т. к. прирост ни разу не линейный, а ядра становятся заняты. Уже после того, как код был написан и протестирован, выяснилось, что обычная память не допускает одновременного доступа к разным адресам, и что это умеет делать только Dual Port RAM.

Для чистоты эксперимента - x86 build, 8 потоков:

Максимальный прирост в скорости копирования - приблизительно двукратный. Да, x86 memcpy оказалась медленнее всего!

Наконец проверим загруженность ядер CPU копированием через xmm регистры.
2 потока:

 4 потока:

 8 потоков:

Масштабирование идеальное.
Выводы:

1) Обогнать memcpy из MSVCR (на AMD) можно.
2) В общем случае многопоточное копирование всё же имеет смысл.
3) Задействование большого кол-во ядер (> 2-4) бессмысленно, из-за того что память не допускает одновременного доступа к разным ядресам.

Update.

Результаты на Core i7-4790:

Результаты на Core i7-3770:

GPU Technology Conference 2015

NVIDIA GPU Technology Conference 2015

XNAMath

На днях ради фана имплементил софтверный скиннинг моделей на CPU (на GPU проще). Для этого пришлось поглубже залезть в исходники XNAMath, которую использую вместо старой самописной мат. библиотеки.

Оказалось, что скиннинг можно ускорить, если не привязываться к SSE2, который для XNAMath в минимальных требованиях, а использовать дополнительные инструкции из SSE4 и относительно нового AVX. Давненько я не лазил по интринсикам :) А зря, там появилось много вкусненького! Такие функции как XMVector3Transform, XMVector3TransformNormal и XMMatrixMultiply могут быть ускорены использованием _mm_fmadd_ps (fused multiply-add) из AVX. _mm_dp_ps, который появился аж в 4(!) инкарнации SSE (AOS вместо SOA), можно использовать в функциях нормализации и поиска длины вектора. Если надо поточно конвертировать float->half и обратно, скажем, для замапленного буфера вершин, то можно использовать _mm_cvtps_ph и _mm_cvtph_ps из AVX, а не привязываться к софтверной реализации в XMConvertFloatToHalf. Также часто бывает что по ходу мат. вычислений нужно вставить/извлечь какой-нить float в/из XMVECTOR, и для этого есть удобные _mm_insert_ps/_mm_extract_ps. Наконец, добило меня то, что XMVector3Cross написана на SSE2 неоптимально, и можно обойтись только тремя шаффлами. После этого я решил дописать к XNAMath расширение с собственными функциями и предпочтительно использовать их, а саму библиотеку оставить как базу для всего остального, некритичного к производительности.

Ссылки:

DirectXMath: SSE4.1 and SSE4.2
DirectXMath: F16C and FMA
DirectXMath: AVX
Vector Cross Product using SSE Code

P.S.
Из забавного оказалось, что AMD подогнали собственный набор команд SSE вроде multiply-accumulate и  horizontal add/sub, которые, конечно, опять никто не будет использовать (как было с 3DNow!) Update : похоже, эти инструкции будут удалены из архитектуры Zen, как бесперспективные.

BOINC

Некоторое время назад начал участвовать в проекте Poem@Home (Protein Optimization w/ Energy Methods) на базе платформы BOINC. 

Многие научные проекты, испытывающие нехватку финансирования, не могут позволить себе арендовать суперкомпьютер, поэтому используют платформу открытых распределённых вычислений. Помимо исследовательской ценности, Poem представляет собой пример удачного использования вычислительной мощности современных GPU. В первую очередь приветствуются видеокарты AMD с архитектурой GCN, способные выполнять OpenCL 1.1-1.2. Авторами утверждается, что расчёты на AMD Radeon R9 290X в 13 раз быстрее расчётов на процессоре AMD Opteron 6380.

Присутствует здесь и соревновательный элемент. Например, можно вступать в команды и просматривать свои внутрикомандные рейтинги. Т. к. на работе двухголовая HD 7990, то я весьма быстро продвигаюсь по лестнице "счётчиков". Можно сказать, что у CPU-юзеров прирост баллов весьма скромный, а GPU-фермы снимают все сливки.

Данный проект натолкнул меня на мысль, что распределённые вычисления "в облаке" являются будущим HPC.

GTX 970

Реакция Гитлера на новую GTX 970:

Интервью с инженером из nVidia:

Санкции

В голову пришла фраза:

Бесплатный крым бывает только в мышеловке.

Vectorized Ray-Bounding Intersection

В прошлый раз я уже описывал идею векторизации в тесте пересечении луча и треугольника. В этот раз я решил пойти дальше и применить векторизацию в тесте луча и ограничивающих объёмов: сферы и прямоугольника. Дело в том, что в классических функциях, написанных с расчётом на выполнение на обычном CPU, есть скалярные операции, и это неэффективно ложится на HLSL. Так, например, для сферы необходимо 6 dxasm инструкций, а для прямоугольника - 13, чтобы найти бинарный ответ пересекает-да/нет. Вроде неплохо, но желательно сократить длину процедуры поиска пересечений до минимума.

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

Я написал две тестовые HLSL функции для сферы и прямоугольника: ray_intersects_vectorized. Промерив кол-во dxasm инструкций на выхлопе, получаем 3 для сферы и ~6 для прямоугольника, или 12 и 25 для их чётвёрок.

 Рис. 1. Vectorized ray-sphere test

Рис. 2. Vectorized ray-box test

Недостатком оптимизации является то, что у нас в BVH или любой другой структуре не всегда под рукой может быть 4 ограничивающих объёма - их может быть 3, или 5, и тогда придётся "подбивать" структуры пустыми данными и тратить на них вычислительные ресурсы. Если же иерархическая структура настроена на поставку четвёрок объёмов за раз, то данный подход представляется оптимальным.

Если взглянуть на функцию пересечения с прямоугольником, можно отметить что выражения

(lo-o)*inv_dir 

(hi-o)*inv_dir

ложатся на dxadm как add+mul, при этом превратить их в mad не представляется возможным из-за порядка операторов. Однако, если мы делаем трассировку лучей в ортографической проекции или от направленного источника света (Солнца), мы можем переписать это в виде

lo*inv_dir-o*inv_dir

hi*inv_dir-o*inv_dir 

где (lo/dir, hi/dir) предвычисляются заранее. Это возможно сделать по той причине, что все лучи имеют одинаковое направление, и рассчитывать деления отдельно для каждого луча не имеет смысла. После этого связки add+mul могут быть заменены на mad (или FMA в новых архитектурах) и функция сократится ещё на шесть инструкций, всего до 19 или ~5 на один примитив.

Рис. 3. Пересечение луча с 4-мя прямоугольниками в ортографической проекции, приблизительно 19 dxasm инструкций. 

Ray/Tri Intersection for Directional Light

Анализируя код пересечения луча и треугольника из Fast, Minimum Storage Ray/Triangle Intersection, я понял что применительно к ортографической проекции или построению теней от направленного источника света (Солнца) путём трассировки лучей, мы можем оптимизировать функцию пересечения. Идея оптимизации основана на том, что все лучи от направленного источника имеют одно направление, в отличие от, скажем, точечного источника. Зная, что вектора dir, edge1 и edge2 являются константами для всего примитива, вектор p и параметр det можно предрассчитать заранее и хранить в памяти вместе с вершинными данными. В противном случае, для каждого пикселя тени будут рассчитываться cross и dot операции с одинаковым результатом. Здесь встаёт вопрос о tradeoff между чтением из памяти и вычислениями, но мне была интересна хотя бы теоретическая возможность вычислительной оптимизации.

Я написал шейдер и демо, которые применяют эту идею. Если использовать самый радикальный, векторизованный вариант пересечения луча и 4-х треугольников, на выхлопе получается 28 dxasm инструкций, т. е. 7 инструкций на треугольник. Думается, это рекордный показатель среди всех функций пересечения с треугольником (конечно, беря во внимание ограничения, свойственные методу).

Думается, метод подойдёт для статичной геометрии (например, здания города, отбрасывающие тени от Солнца). В случае, если солнце должно двигаться (меняется вектор dir), нужно делать отдельный проход, в котором значения пересчитываются для каждого треугольника и сохраняются в памяти перед проходом теней.