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). Не знаю, что получится, но поиск текстурных координат пересечения по двум матрицам - это жёстко :)