Трассировка лучей
Трассировщик красит отсчёт, проводя прямую. Прямая выходит из камеры, из лампы или из предыдущего попадания и идёт в одну сторону, пока алгоритм не решит остановиться. Первый вопрос геометрический. Какая поверхность ближе всех вдоль этой прямой? Артур Аппель в IBM в 1968 году таким тестом закрашивал твёрдые тела и отмечал области в тени. Модель Тёрнера Уиттеда 1980 года на этом не остановилась. От попадания она могла пустить луч отражения, луч преломления и теневой луч к каждой лампе. Трёхмерная компьютерная графика доводит линию до уравнения рендеринга Каджии 1986 года и до трассировки путей, где вместо жёсткого дерева лучей Уиттеда стоят случайные выборки. Свет, материалы и готовое изображение разбирает, чего эти выборки стоят и какой шум после них остаётся.
Дороже всего поиск. Когда треугольников больше, чем хочется проверять по одному, проверка каждого против каждого луча тратит время на промахи, которые отсёк бы ящик. Структура ускорения, чаще всего иерархия ограничивающих объёмов, складывает примитивы во вложенные ящики. Луч обходит те ящики, которые он правда задевает. Камера, материал и выбор следующего луча меняются вместе с алгоритмом. Обход остаётся общим.
Стивен Г. Паркер, Джеймс Биглер, Андреас Дитрих, Хайко Фридрих, Джаред Хоберок, Дэвид Любке, Дэвид Макаллистер, Морган Макгуайр, Кит Морли, Остин Робисон и Мартин Штих описали, как делить этот обход, в статье OptiX: a general purpose ray tracing engine, ACM Transactions on Graphics, том 29 (2010), 13 страниц, DOI 10.1145/1778765.1778803. Макгуайр работал и в Уильямс-колледже, и в NVIDIA. Остальные авторы были в NVIDIA. Реализация 2010 года шла на GPU Quadro, GeForce и Tesla этой компании, через CUDA. Прежние интерактивные трассировщики, в том числе OpenRT, Manta, Razor и Arauna, собирались вокруг одного рендера или одной машины. Работы, которые уже ставили трассировку на GPU, гнались за скоростью. OptiX гнался за моделью программирования.
Движок не знает, что такое лампа. Тени и отражательной способности в нём тоже нет. Это забота программы, которая его вызвала. OptiX даёт несколько маленьких программ, каждую на один луч, и компилятор на лету, который сшивает их в ядро. Рекурсию по-прежнему пишет человек, как в шейдере Уиттеда. Пакетирование, перестановка лучей и постройка структуры ускорения остаются внутри движка. Программа ближайшего попадания не распределяет работу по GPU.
Программы
Семь типов программ работают с одним лучом за раз. Программа ограничивающего ящика стоит рядом и считается не для луча, а для геометрии: структуре ускорения нужен ящик, куда вставить примитив. В статье ящик вынесен за скобки семёрки. В таблице полный набор.
| Программа | Когда срабатывает |
|---|---|
| Порождение лучей | Вход. Часто одна копия на пиксель. |
| Пересечение | Во время обхода. Касается ли примитив луча и где? |
| Ограничивающий ящик | При постройке структуры. Ящик, который заведомо вмещает примитив. |
| Ближайшее попадание | Один раз, в ближайшей точке. Шейдер поверхности. |
| Любое попадание | На каждом сообщённом попадании, в любом порядке. Может оборвать луч или пропустить попадание. |
| Промах | Луч ушёл из сцены. Ровный цвет фона или карта окружения. |
| Исключение | Луч сломался, или свой код бросил ошибку. |
| Визит селектора | На узле-селекторе. Выбирает, в какого ребёнка идти лучу. |
Порождение лучей это вход запуска. Один вызов поднимает много копий. У обычной камеры копия строит один луч на один пиксель, трассирует его и записывает цвет. Та же программа умеет сеять фотоны, запекать освещение или принимать лучи, которые уже поставил проход OpenGL. Пересечение это геометрическая проверка. Ею может быть треугольник, сфера, цилиндр или фигура вовсе без сетки. На первом рисунке статьи есть процедурное множество Жюлиа. Ящик процедурного примитива иногда лишь оценка. Оценка обязана вмещать примитив. Рыхлый ящик удлиняет обход. Картинка от этого не меняется.
Ближайшее попадание срабатывает один раз, когда ближайшее пересечение уже найдено. Это шейдер поверхности. Он может посчитать цвет, пустить новые лучи и записать результат в полезную нагрузку луча. Любое попадание срабатывает по дороге, на каждом пересечении, о котором сообщил обход, и сообщения могут прийти не по порядку. Оттуда луч можно оборвать сразу: так и надо теневому лучу, который нашёл преграду. Попадание можно и проигнорировать: так альфа-текстура пробивает дыру, не начиная поиск заново. Промах срабатывает, если внутри интервала ничего не нашлось. Там живёт ровный цвет фона или карта окружения. Исключение срабатывает, когда луч сломался: стек рекурсии перерос память, отведённую потоку, или индекс буфера вышел за край. Свой код тоже может бросить исключение. Визит селектора идёт на крупном узле и выбирает ребёнка. Обычное дело тут уровень детализации. Далёкий луч получает грубую модель.
Полезная нагрузка это запись, которую задаёт пользователь и крепит к лучу. В ней едут результат закраски и ослабление тени. Фиксированной структуры света, куда писать, нет. На первом рисунке статьи нарисованы трассировка путей, множество Жюлиа, фотонные карты, проверка прямой видимости и столкновений на большом масштабе, закраска Уиттеда для подвижной геометрии и окклюзия окружения. В аннотации названы ещё обнаружение столкновений, запросы для искусственного интеллекта и научные задачи вроде распространения звука. Луч в этой схеме это запрос. Картинка это один из ответов.
Граф сцены
Геометрия лежит в контексте, направленным графом. У узла-группы есть дети и структура ускорения. Он может быть верхом двухуровневого обхода: так двигают жёсткие предметы, не пересобирая всё дерево. Группа геометрии это лист. В ней примитивы и материалы, и своя структура ускорения. У узла преобразования один ребёнок и матрица 4 на 3, этого хватает на аффинное отображение. У узла-селектора есть дети и одна программа визита. Корнем может быть любой узел, так что луч камеры и теневой луч стартуют из разных графов. У узла бывает несколько родителей. Так устроен инстансинг: одна сетка на многих местах, один материал у фигур с разной проверкой пересечения.
Экземпляр геометрии это стык. Он связывает один геометрический объект с набором материалов. Программы пересечения и ящика висят на геометрии. Программы ближайшего и любого попадания висят на материале. Разделение нарочное. Формат треугольников, которым пользуется растеризатор, может остаться в этом формате: программа пересечения читает его там, где он уже лежит. Копия в особую сетку трассировщика больше не плата за вход.
К 2010 году формула отражения была уже старой. Открытым оставался программируемый поиск на параллельной машине, и писать его заново при каждой смене алгоритма никто не хотел. Когда компьютерная картинка стала обычной, кадр уже можно было трассировать, пока он ещё на экране.