Общепризнанным стандартом здесь является алгоритм Мюллера-Трумбора:
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 ChipRPU: A Programmable Ray Processing Unit for Realtime Ray TracingПост whiteambit на ompf.orgСейчас копаю эту тему. По идее, в unit space отпадает необходимость в (p - v0). Не знаю, что получится, но поиск текстурных координат пересечения по двум матрицам - это жёстко :)
