Трассировка лучей
Трассировщик лучей определяет цвет отсчёта, прослеживая прямую линию. Линия начинается в камере, в источнике света или в точке предыдущего попадания и идёт в одном направлении, пока алгоритм не решит остановиться. Первый вопрос геометрический: какая поверхность ближе всего вдоль этой линии? Артур Аппель в IBM в 1968 году использовал такую проверку, чтобы затенять твёрдые тела и отмечать области в тени. Модель Тёрнера Уиттеда 1980 года пошла дальше. Из точки попадания она могла выпустить луч отражения, луч преломления и теневой луч к каждому источнику света. Трёхмерная компьютерная графика продолжает эту историю до уравнения рендеринга Каджии 1986 года и до трассировки путей, где фиксированное дерево лучей Уиттеда заменили случайные отсчёты. Свет, материалы и готовое изображение это заметка о том, чего стоят эти отсчёты и какой шум после них остаётся.
Больше всего ресурсов уходит на поиск. Когда в сцене больше треугольников, чем кому-либо захочется проверять по одному, проверка каждого треугольника для каждого луча тратит большую часть времени на промахи, которые можно было бы отсечь с помощью ограничивающего параллелепипеда. Структура ускорения, чаще всего иерархия ограничивающих объёмов (BVH), упаковывает примитивы во вложенные параллелепипеды. Луч обходит только те из них, которые действительно пересекает. Модели камеры, материалы и выбор следующего луча меняются от алгоритма к алгоритму. А обход у них общий.
Стивен Г. Паркер, Джеймс Биглер, Андреас Дитрих, Хайко Фридрих, Джаред Хоберок, Дэвид Любке, Дэвид Макаллистер, Морган Макгуайр, Кит Морли, Остин Робисон и Мартин Штих описали способ сделать этот обход общим в статье 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 предлагает несколько небольших программ, каждая из которых пишется для одного луча, и JIT-компилятор, который объединяет их в ядро. Рекурсию по-прежнему пишет программист, так же как в шейдере Уиттеда. Пакетная обработка, переупорядочивание лучей и построение структуры ускорения остаются внутри движка. Программа ближайшего попадания не занимается планированием работы GPU.
Программы
Семь типов программ работают с одним лучом за раз. Рядом с ними стоит программа ограничивающего параллелепипеда, которая работает не с лучом, а с геометрией, чтобы у структуры ускорения был параллелепипед, который можно в неё вставить. В статье эта программа рассматривается отдельно. В таблице приведён полный набор.
| Программа | Когда выполняется |
|---|---|
| Порождение лучей | Точка входа. Часто одна копия на пиксель. |
| Пересечение | Во время обхода. Пересекает ли этот примитив луч, и если да, то где? |
| Ограничивающий параллелепипед | При построении структуры. Параллелепипед, который заведомо вмещает примитив. |
| Ближайшее попадание | Один раз, в ближайшей точке попадания. Шейдер поверхности. |
| Любое попадание | При каждом найденном попадании, в любом порядке. Может остановить луч или пропустить попадание. |
| Промах | Луч покинул сцену. Цвет фона или карта окружения. |
| Исключение | Луч дал сбой, или пользовательский код выбросил исключение. |
| Посещение селектора | На узле-селекторе. Выбирает, в какой дочерний узел пойдёт луч. |
Порождение лучей это точка входа при запуске. Один вызов запускает множество копий. В обычной камере каждая копия строит один луч для одного пикселя, трассирует его и сохраняет цвет. Программа того же типа может испускать фотоны, запекать освещение или принимать запросы на лучи, которые уже поставил в очередь проход OpenGL. Пересечение это геометрическая проверка. Примитивом может быть треугольник, сфера, цилиндр или что-то вообще без сетки. На рисунке 1 статьи есть процедурное множество Жюлиа. Ограничивающий параллелепипед процедурного примитива может быть лишь приблизительной оценкой. Но эта оценка обязательно должна вмещать примитив. Слишком просторный параллелепипед удлиняет обход. Изображение от этого не меняется.
Программа ближайшего попадания выполняется один раз, когда ближайшее пересечение уже известно. Это шейдер поверхности. Она может рассчитать цвет, выпустить новые лучи и записать результат в полезную нагрузку луча. Программа любого попадания выполняется по пути к нему, один раз для каждого пересечения, о котором сообщает обход, и сообщения могут приходить в произвольном порядке. Из этой программы луч можно сразу остановить, что правильно для теневого луча, который нашёл препятствие. А можно проигнорировать попадание, и именно так альфа-текстура проделывает дыру, не запуская поиск заново. Программа промаха выполняется, когда в пределах интервала ничего не найдено. Здесь задаётся однородный цвет фона или карта окружения. Программа исключения выполняется, когда с лучом что-то пошло не так: стек рекурсии превысил память, отведённую потоку, или индекс буфера вышел за допустимые пределы. Пользовательский код тоже может выбросить своё исключение. Программа посещения селектора выполняется на узле-селекторе и выбирает дочерний узел. Самое очевидное применение это уровни детализации. Далёкий луч получает упрощённую модель.
Полезная нагрузка это структура данных, которую задаёт пользователь и прикрепляет к лучу. В ней передаются результаты затенения и ослабление тени. Никакой фиксированной структуры для освещения, в которую нужно записывать данные, нет. На первом рисунке статьи показаны трассировка путей, множество Жюлиа, фотонные карты, проверки прямой видимости и столкновений в больших масштабах, затенение по Уиттеду для динамической геометрии и затенение окружающим светом. В аннотации названы также обнаружение столкновений, запросы для искусственного интеллекта и научные задачи вроде моделирования распространения звука. Луч в такой схеме это запрос. А изображение лишь один из видов ответа.
Граф сцены
Геометрия хранится в контексте в виде направленного графа. У узла-группы есть дочерние узлы и структура ускорения, и он может быть вершиной двухуровневого обхода, распространённого способа перемещать твёрдые объекты, не перестраивая всё дерево. Группа геометрии это лист. Она содержит примитивы и материалы и имеет собственную структуру ускорения. У узла преобразования один дочерний узел и матрица 4 на 3, которой достаточно для аффинного преобразования. У узла-селектора есть дочерние узлы и одна программа посещения. Корнем может быть любой узел, поэтому луч камеры и теневой луч могут начинаться в разных графах. У узла может быть несколько родителей. Это и есть инстансинг: одна сетка во многих местах и один материал у фигур с разными проверками пересечения.
Экземпляр геометрии служит связующим звеном. Он связывает один геометрический объект с набором материалов. Программы пересечения и ограничивающего параллелепипеда привязаны к геометрии. Программы ближайшего и любого попадания привязаны к материалу. Это разделение сделано намеренно. Формат треугольников, который использует растеризатор, может оставаться прежним, потому что программа пересечения читает данные там, где они уже лежат. Чтобы начать работу, больше не нужно копировать их в специальную сетку трассировщика.
К 2010 году формула отражения была уже давно известна. Открытым оставался вопрос о программируемом поиске на параллельной машине, который не пришлось бы писать заново для каждого нового алгоритма. Когда компьютерная картинка стала обычной, кадр уже можно было трассировать прямо во время показа.