Vectorized Ray-Triangle Intersection

Существуют различные алгоритмы для теста пересечения луча и треугольника. Изначально они написаны в рачёте не CPU, т. е. пытаются отложить деление и используют SSE оптимизации.

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

Я решил опробовать три метода:
1) Барицентрический (Moller-Trumbore intersection algorithm).
2) Единичный тест (unit test) (Sven Woop).
3) Перпендикулярных плоскостей (Yet Faster Ray-Triangle Intersection).

Барицентрический тест можно свести к следующей HLSL функции: intersect. Она компилируется в 13 dxasm инструкций. Для этого треугольник хранится в памяти как опорная вершина и два вектора-ребра, убрана проверка на culling и деление, отсутствует двойная проверка (u > 1.0f, u + v > 1.0f). Реализация единичного теста у меня получилась на 1 dxasm инструкцию длиннее, а тест перпендикулярных плоскостей - ещё на 3 инструкции длиннее, главным образом потому, что в dxasm нет встроенной инструкции sign, она разворачивается в несколько сравнений (если придумаете, как её реализовать одной инструкцией, буду премного благодарен).

Чтобы протестировать производительнось функций, я написал простой ray-cast тест: 256 треугольников торуса тестируется в цикле на пересечение с лучом. При первом положительном результате цикл прерывается. Иерархические структуры не используются, но первый тест луча происходит со сферой, окружающей торус. Крайне неэффективный способ рисования, зато позволяет минимизировать latency от прыжков по памяти (в виду линейного чтения) и хорошо оценить синтетическую производительность GPU.

На Radeon HD 7990 в разрешении 720p и фиксированном положении геометрии к камере я получил следующие цифры:

barycentric: 3.73 ms
unit test: 3.85 ms
precomputed planes: 3.94 ms

Все три алгоритма имеют приблизительно схожую производительность, но барицентрический тест быстрее всех (классика!). На этом казалось бы можно и остановиться, но перед этим я наткнулся на описание оптимизации барицентрического теста применительно к GPU:

GPU Ray Tracing – Comparative Study of Ray-Triangle Intersection Algorithms

Основная идея - тестировать луч на пересечение с четырьмя треугольниками за раз, реализовав в своём роде Super-SIMD. Несмотря на то, что GPU с рождения шейдеров применяют векторизацию, не всегда удаётся задействовать все слоты ALU.

Рассмотрим операцию скалярного произведения в HLSL:

bary.x = dot(t, p);

Векторизованная форма примет вид:

vec4 bary4x = (t4x * p4x) + (t4y * p4y) + (t4z * p4z);

Аналогично с векторным произведением и любыми другими операциями - работа идёт с четвёрками данных. Руководствуясь этой идеей, я написал векторизованные варианты трёх функций и промерил их длины в инструкциях dxasm. Барицентрический тест компилируется в 32 asm инструкции, т. е. примерно 8 инструкций на треугольник (против 13 в обычном варианте). Тест с перпендикулярными плоскостями компилируется в 40 asm инструкций, главным образом из-за отсутствия встроенного sign, но всё равно это 10 инструкций на треугольник против 17 в невекторизованном варианте. Я подготовил геометрические данные в памяти нужным образом и получил обновлённые результаты:

vectorized barycentric: 3.23 ms
vectorized unit test: 3.77 ms
vectorized precomputed planes: 3.52 ms

Ускорение практически на ровном месте! Единственный недостаток подхода - необходимо всегда делать padding в памяти до четырёх треугольников.

И последний шаг - квантование вершинных данных из FP32 в FP16. До этого данные размещались в cbuffer, но он может хранить только данные полной вещественной точности, поэтому пришлось использовать tbuffer. Эти два конвейера подачи данных в Shader Core отличаются в железе: tbuffer ближе всего к выборке из 1D-текстуры без фильтрации, cbuffer похоже кэшируется специальным образом для быстрейшего доступа (отсюда ограничения на формат данных из размеры буфера). На Radeon HD tbuffer оказывается медленнее cbuffer в линейном доступе при одинаковом объёме данных. Новые результаты:

vectorized fp16 barycentric: 3.08 ms
vectorized fp16 unit test: 3.64 ms
vectorized fp16 precomputed planes: 3.4 ms

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