Трассировка лучей (графика)

Не путать с трассировкой лучей (физика) .

Эта рекурсивная трассировка лучей отражающих цветных сфер на белой поверхности демонстрирует эффекты малой глубины резкости , «площадных» источников света и диффузного взаимного отражения . ( ок. 2008 г. )

В 3D-компьютерной графике трассировка лучей — это метод моделирования переноса света , используемый в самых разных алгоритмах рендеринга для создания цифровых изображений .

С точки зрения вычислительных затрат и визуальной точности методы рендеринга на основе трассировки лучей, такие как литье лучей , рекурсивная трассировка лучей , трассировка распределения лучей , картирование фотонов и трассировка пути , как правило, медленнее и более точны, чем методы рендеринга строк развертки . Таким образом, трассировка лучей была впервые применена в приложениях, где можно было допустить относительно длительное время рендеринга, таких как неподвижные изображения CGI (VFX) фильмов и телевидения , а также визуальные эффекты , но она менее подходила для приложений реального времени, таких как видеоигры. , где скорость имеет решающее значение при рендеринге каждого кадра .

Однако с 2019 года аппаратное ускорение трассировки лучей в реальном времени стало стандартом для новых коммерческих видеокарт, и графические API последовали этому примеру, позволяя разработчикам использовать гибридную трассировку лучей и рендеринг на основе растеризации в играх и других приложениях реального времени с меньшее влияние на время рендеринга кадров.

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

Методы рендеринга на основе трассировки лучей, включающие выборку света по области, генерируют артефакты шума изображения , которые можно устранить путем отслеживания очень большого количества лучей или использования методов шумоподавления .

История

«Рисунок, делающий перспективный рисунок лежащей женщины» Альбрехта Дюрера, возможно, 1532 года, изображает мужчину, использующего сетку для создания изображения. Немецкому художнику эпохи Возрождения приписывают первое описание этой техники.

Гравюра Дюрера на дереве по изобретению Якоба де Кейзера. С помощью устройства де Кейзера точка зрения художника фиксировалась с помощью крючка для глаз, вставленного в стену. Он был соединен шелковой веревкой с инструментом в виде прицела с заостренным вертикальным элементом спереди и глазком сзади. Художник нацелился на объект и обвел его контур на стекле, держа окуляр на одной линии с веревкой, чтобы сохранить правильный угол зрения.

Идея трассировки лучей возникла еще в 16 веке, когда ее описал Альбрехт Дюрер , которому приписывают ее изобретение. Дюрер описал несколько методов проецирования трехмерных сцен на плоскость изображения. Некоторые из них проецируют геометрию на плоскость изображения, как это происходит сегодня с растеризацией . Другие определяют, какая геометрия видна вдоль данного луча, как это делается с помощью трассировки лучей.

Использование компьютера для трассировки лучей для создания затененных изображений было впервые осуществлено Артуром Аппелем в 1968 году. Аппель использовал трассировку лучей для первичной видимости (определяя ближайшую к камере поверхность в каждой точке изображения), прослеживая луч через каждую точку, которая должна быть затенена на сцене, чтобы идентифицировать видимую поверхность. Ближайшая поверхность, которую пересекал луч, была видимой. Этот нерекурсивный алгоритм рендеринга на основе трассировки лучей сегодня называется « приведение лучей ». Затем его алгоритм проследил вторичные лучи до источника света от каждой затеняемой точки, чтобы определить, находится ли эта точка в тени или нет.

Позже, в 1971 году, Гольдштейн и Нагель из MAGI (Mathematical Applications Group, Inc.) опубликовал «3-D Visual Simulation», в котором трассировка лучей использовалась для создания затененных изображений твердых тел. В найденной точке пересечения луча и поверхности они вычислили нормаль к поверхности и, зная положение источника света, вычислили яркость пикселя на экране. В их публикации описывается короткий (30-секундный) фильм, «снятый с использованием дисплейного оборудования Университета Мэриленда, оснащенного 16-миллиметровой камерой. В фильме показан вертолет и простая наземная артиллерийская установка. Вертолет был запрограммирован на серию маневров, включая развороты, взлеты, посадки и т. д., пока в конечном итоге не был сбит и не разбился». CDC 6600 Использовался компьютер . В 1974 году компания MAGI выпустила анимационное видео под названием MAGI/SynthaVision Sampler .

Раскладная книга, созданная в 1976 году в Калифорнийском технологическом институте.

Еще один ранний пример применения лучей произошел в 1976 году, когда Скотт Рот создал анимацию в виде раскладывающейся книги на Боба Спроулла курсе компьютерной графики в Калифорнийском технологическом институте . Отсканированные страницы показаны в виде видео справа. Компьютерная программа Рота отмечала крайнюю точку в месте пикселя, если луч пересекал ограниченную плоскость, отличную от плоскости его соседей. Конечно, луч мог пересекать несколько плоскостей в пространстве, но видимой была отмечена только точка поверхности, ближайшая к камере. Платформой была DEC PDP-10 , дисплей Tektronix с трубкой хранения и принтер, который создавал изображение дисплея на рулонной термобумаге. Рот расширил концепцию, ввел термин «кастинг лучей» в контексте компьютерной графики и твердотельного моделирования и в 1982 году опубликовал свою работу в GM Research Labs.

Тернер Уиттед был первым, кто продемонстрировал рекурсивную трассировку лучей для зеркального отражения и преломления через полупрозрачные объекты с углом, определяемым показателем преломления твердого тела, и использовал трассировку лучей для сглаживания . Уиттед также продемонстрировал тени с трассировкой лучей. Он продюсировал фильм с рекурсивной трассировкой лучей под названием «Совершенный рыболов». в 1979 году, когда работал инженером в Bell Labs. Глубоко рекурсивный алгоритм трассировки лучей Уиттеда превратил рендеринг из вопроса определения видимости поверхности в вопрос транспортировки света. Его статья вдохновила других на серию последующих работ, которые включали трассировку распределения лучей и, наконец, трассировку несмещенных путей , которая обеспечивает структуру уравнений рендеринга , которая позволяет сгенерированным на компьютере изображениям быть верными реальности.

На протяжении десятилетий глобальное освещение в крупных фильмах с использованием компьютерных изображений аппроксимировалось дополнительным освещением. Рендеринг на основе трассировки лучей в конечном итоге изменил ситуацию, включив физический перенос света. К ранним художественным фильмам, полностью созданным с использованием трассировки пути, относятся «Дом монстров» (2006), «Облачно, возможны осадки в виде фрикаделек» (2009), и Университет монстров (2013).

Обзор алгоритма

Алгоритм трассировки лучей создает изображение, распространяя лучи по сцене и отражая их от поверхностей к источникам света, чтобы аппроксимировать значение цвета пикселей.

Иллюстрация алгоритма трассировки лучей для одного пикселя (до первого отскока)

Трассировка оптических лучей описывает метод создания визуальных изображений, созданных в средах трехмерной компьютерной графики , с большей фотореалистичностью, чем методы лучевого анализа или развертки . Он работает, прослеживая путь от воображаемого глаза через каждый пиксель виртуального экрана и вычисляя цвет объекта, видимого через него.

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

Обычно каждый луч необходимо проверять на пересечение с некоторым подмножеством всех объектов сцены. Как только ближайший объект будет идентифицирован, алгоритм оценит падающий свет в точке пересечения, исследует свойства материала объекта и объединит эту информацию для расчета окончательного цвета пикселя. Определенные алгоритмы освещения, а также отражающие или полупрозрачные материалы могут потребовать повторного попадания в сцену большего количества лучей.

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

Таким образом, при трассировке лучей проще всего предположить, что данный луч пересекает рамку обзора. После достижения максимального количества отражений или после прохождения луча определенного расстояния без пересечения луч перестает двигаться, и значение пикселя обновляется.

Рассчитать лучи для прямоугольного видового экрана

На входе имеем (в расчете используем векторную нормализацию и векторное произведение ):

• $E\in \mathbb {R^{3}}$ положение глаз
• $T\in \mathbb {R^{3}}$ целевая позиция
• $\theta \in [0,\pi ]$ поле зрения - для человека, можно предположить $\approx \pi /2{\text{ rad}}=90^{\circ }$
• $m,k\in \mathbb {N}$ количество квадратных пикселей в окне просмотра по вертикали и горизонтали
• $i,j\in \mathbb {N} ,1\leq i\leq k\land 1\leq j\leq m$ количество реальных пикселей
• ${\vec {v}}\in \mathbb {R^{3}}$ вертикальный вектор, который указывает, где находится верх и низ, обычно ${\vec {v}}=[0,1,0]$ - компонент вращения , определяющий вращение области просмотра вокруг точки C (где осью вращения является сечение ET)

Идея состоит в том, чтобы найти положение центра каждого пикселя области просмотра. $P_{ij}$ что позволяет нам найти линию, идущую от глаза $E$ через этот пиксель и, наконец, получить луч, описываемый точкой $E$ и вектор ${\vec {R}}_{ij}=P_{ij}-E$ (или его нормализация ${\vec {r}}_{ij}$). Сначала нам нужно найти координаты нижнего левого пикселя области просмотра. $P_{1m}$ и найдите следующий пиксель, сделав сдвиг в направлениях, параллельных окну просмотра (векторы ${\vec {b}}_{n}$ я ${\vec {v}}_{n}$), умноженный на размер пикселя. Ниже мы вводим формулы, включающие расстояние $d$ между глазом и окном просмотра. Однако это значение будет уменьшено во время нормализации лучей. ${\vec {r}}_{ij}$ (так что вы могли бы также принять это $d=1$ и исключить его из расчетов).

Предварительные расчеты: найдем и нормализуем вектор ${\vec {t}}$ и векторы ${\vec {b}},{\vec {v}}$ которые параллельны окну просмотра (все изображены на рисунке выше)

${\vec {t}}=T-E,\qquad {\vec {b}}={\vec {t}}\times {\vec {v}}$

${\vec {t}}_{n}={\frac {\vec {t}}{||{\vec {t}}||}},\qquad {\vec {b}}_{n}={\frac {\vec {b}}{||{\vec {b}}||}},\qquad {\vec {v}}_{n}={\vec {t}}_{n}\times {\vec {b}}_{n}$

обратите внимание, что центр области просмотра $C=E+{\vec {t}}_{n}d$, затем мы вычисляем размеры области просмотра $h_{x},h_{y}$ разделить на 2, включая обратное соотношение сторон ${\frac {m-1}{k-1}}$

$g_{x}={\frac {h_{x}}{2}}=d\tan {\frac {\theta }{2}},\qquad g_{y}={\frac {h_{y}}{2}}=g_{x}{\frac {m-1}{k-1}}$

а затем мы вычисляем векторы сдвига следующего пикселя $q_{x},q_{y}$ вдоль направлений, параллельных окну просмотра ( ${\vec {b}},{\vec {v}}$) и центр левого нижнего пикселя $p_{1m}$

${\vec {q}}_{x}={\frac {2g_{x}}{k-1}}{\vec {b}}_{n},\qquad {\vec {q}}_{y}={\frac {2g_{y}}{m-1}}{\vec {v}}_{n},\qquad {\vec {p}}_{1m}={\vec {t}}_{n}d-g_{x}{\vec {b}}_{n}-g_{y}{\vec {v}}_{n}$

Расчеты: примечание $P_{ij}=E+{\vec {p}}_{ij}$ и луч ${\vec {R}}_{ij}=P_{ij}-E={\vec {p}}_{ij}$ так

${\vec {p}}_{ij}={\vec {p}}_{1m}+{\vec {q}}_{x}(i-1)+{\vec {q}}_{y}(j-1)$

${\vec {r}}_{ij}={\frac {{\vec {R}}_{ij}}{||{\vec {R}}_{ij}||}}={\frac {{\vec {p}}_{ij}}{||{\vec {p}}_{ij}||}}$

Подробное описание компьютерного алгоритма трассировки лучей и его происхождения.

Что происходит в природе (упрощенно)

Смотрите также: Электромагнетизм и квантовая электродинамика.

В природе источник света излучает луч света, который в конечном итоге достигает поверхности, прерывая его движение. Этот «луч» можно представить как поток фотонов, движущихся по одному и тому же пути. В идеальном вакууме этот луч будет прямой линией (без учета релятивистских эффектов ). С этим световым лучом может произойти любая комбинация четырех вещей: поглощения , отражения , преломления и флуоресценции . Поверхность может поглощать часть светового луча, что приводит к потере интенсивности отраженного и/или преломленного света. Он также может отражать весь луч света или его часть в одном или нескольких направлениях. Если поверхность имеет какие-либо прозрачные или полупрозрачные свойства, она преломляет часть светового луча в себя в другом направлении, поглощая при этом часть (или весь) спектра ( и, возможно, изменяя цвет). Реже поверхность может поглощать некоторую часть света и флуоресцентно переизлучать свет более длинноволнового цвета в случайном направлении, хотя это достаточно редко, поэтому его можно не учитывать в большинстве приложений рендеринга. Необходимо учитывать весь поступающий свет между поглощением, отражением, преломлением и флуоресценцией, и не более того. Поверхность не может, например, отражать 66% падающего светового луча и преломлять 50%, поскольку в сумме эти два показателя составят 116%. Отсюда отраженные и/или преломленные лучи могут попадать на другие поверхности, где их поглощающие, преломляющие, отражательные и флуоресцентные свойства снова влияют на распространение входящих лучей. Некоторые из этих лучей движутся таким образом, что попадают в наши глаза, заставляя нас видеть сцену и тем самым внося свой вклад в окончательное визуализированное изображение.

Алгоритм приведения лучей

Основная статья: Рэй-кастинг

Идея метода распределения лучей, предшественника рекурсивной трассировки лучей, заключается в том, чтобы отслеживать лучи из глаза, по одному на пиксель, и находить ближайший объект, блокирующий путь этого луча. Представьте себе изображение как дверь-ширму, где каждый квадрат на экране представляет собой пиксель. Это и есть объект, который глаз видит через этот пиксель. Используя свойства материала и эффект освещения в сцене, этот алгоритм может определить затенение этого объекта. Делается упрощающее предположение, что если поверхность обращена к источнику света, свет достигнет этой поверхности и не будет блокироваться или находиться в тени. Затенение поверхности рассчитывается с использованием традиционных моделей затенения трехмерной компьютерной графики. Одним из важных преимуществ метода луча по сравнению со старыми алгоритмами развертки была его способность легко обрабатывать неплоские поверхности и твердые тела, такие как конусы и сферы . Если математическую поверхность можно пересечь лучом, ее можно визуализировать с помощью преобразования лучей. Сложные объекты можно создавать с помощью методов твердотельного моделирования и легко визуализировать.

Алгоритм объемного луча

Основная статья: Объемное преобразование лучей

В методе объемного литья лучей каждый луч отслеживается так, что цвет и/или плотность можно отбирать вдоль луча, а затем объединять в окончательный цвет пикселя. Это часто используется, когда объекты невозможно легко представить с помощью явных поверхностей (например, треугольников), например, при рендеринге облаков или 3D-медицинских сканированиях.

Визуализация алгоритма марширования лучей SDF

Алгоритм марширования лучей SDF

Основная статья: Лучевой марш § Лучевой марш на расстоянии

При маршировании лучей SDF или трассировке сфер каждый луч трассируется в несколько этапов для аппроксимации точки пересечения луча и поверхности, определяемой функцией расстояния со знаком (SDF). SDF оценивается для каждой итерации, чтобы иметь возможность делать как можно большие шаги, не пропуская ни одной части поверхности. Порог используется для отмены дальнейшей итерации при достижении точки, достаточно близкой к поверхности. Этот метод часто используется для трехмерного фрактального рендеринга.

Алгоритм рекурсивной трассировки лучей

Трассировка лучей позволяет создавать фотореалистичные изображения.

Помимо высокой степени реализма, трассировка лучей позволяет имитировать эффекты камеры за счет глубины резкости и формы апертуры (в данном случае шестиугольника ).

Количество отражений или отскоков, которые может сделать «луч», и то, как на него влияет каждый раз, когда он сталкивается с поверхностью, контролируется настройками программного обеспечения. На этом изображении каждому лучу разрешили отразиться до 16 раз. Таким образом, в этих сферах можно увидеть множественные «отражения отражений». (Изображение создано с помощью Cobalt .)

Количество преломлений, которые может совершить «луч», и то, как на него влияет каждый раз, когда он сталкивается с поверхностью, допускающей передачу света , контролируется настройками программного обеспечения. Здесь каждый луч был настроен на преломление или отражение («глубину») до 9 раз . отражения Френеля Были использованы каустики , и видны . (Изображение создано с помощью V-Ray .)

Более ранние алгоритмы отслеживали лучи из глаза в сцену до тех пор, пока они не попадали на объект, но определяли цвет луча без рекурсивного отслеживания большего количества лучей. Рекурсивная трассировка лучей продолжает этот процесс. Когда луч попадает на поверхность, могут возникнуть дополнительные лучи из-за отражения, преломления и тени:

• Луч отражения прослеживается в направлении зеркального отражения. Ближайший объект, с которым он пересекается, — это то, что будет видно в отражении.
• Преломляющий луч, проходящий через прозрачный материал, работает аналогичным образом, с тем дополнением, что преломляющий луч может входить в материал или выходить из него. Тернер Уиттед расширил математическую логику лучей, проходящих через прозрачное твердое тело, включив в него эффекты преломления.
• Теневой луч прослеживается к каждому источнику света. Если между поверхностью и источником света обнаружен какой-либо непрозрачный объект, поверхность находится в тени и свет ее не освещает.

Эти рекурсивные лучи добавляют больше реализма изображениям с трассировкой лучей.

Преимущества перед другими методами рендеринга

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

Недостатки

Серьезным недостатком трассировки лучей является производительность (хотя теоретически она может быть быстрее, чем традиционный рендеринг строк развертки, в зависимости от сложности сцены и количества пикселей на экране). До конца 2010-х годов трассировка лучей в реальном времени обычно считалась невозможной на потребительском оборудовании для решения нетривиальных задач. Алгоритмы развертки и другие алгоритмы используют согласованность данных для разделения вычислений между пикселями, в то время как трассировка лучей обычно запускает процесс заново, обрабатывая каждый глазной луч отдельно. Однако такое разделение дает и другие преимущества, такие как возможность снимать больше лучей по мере необходимости для выполнения пространственного сглаживания и улучшения качества изображения там, где это необходимо.

Рекурсивная трассировка лучей в стиле Уиттеда обрабатывает взаимное отражение и оптические эффекты, такие как преломление, но, как правило, не является фотореалистичной . Улучшение реализма достигается при полной оценке уравнения рендеринга , поскольку оно концептуально включает в себя все физические эффекты светового потока. Однако это неосуществимо, учитывая необходимые вычислительные ресурсы и ограничения на точность геометрического и материального моделирования. Трассировка пути — это алгоритм оценки уравнения рендеринга, который обеспечивает более высокую точность моделирования реального освещения.

Обратное направление обхода сцены лучами

Процесс направления лучей от глаза к источнику света для рендеринга изображения иногда называют обратной трассировкой лучей , поскольку на самом деле фотоны движутся в противоположном направлении. Однако в этой терминологии существует путаница. Ранняя трассировка лучей всегда выполнялась глазами, и ранние исследователи, такие как Джеймс Арво, использовали термин « обратная трассировка лучей» , означая съемку лучей от источников света и сбор результатов. Таким образом, более четко различать трассировку лучей на основе глаз и трассировку лучей на основе света .

Хотя прямое освещение, как правило, лучше всего измеряется с помощью трассировки лучей на основе глаз, некоторые косвенные эффекты могут быть улучшены за счет лучей, генерируемых источниками света. Каустики — это яркие узоры, вызванные фокусировкой света от широкой отражающей области на узкой области (почти) диффузной поверхности. Алгоритм, который направляет лучи непосредственно от источников света на отражающие объекты, прослеживая их путь к глазу, лучше исследует это явление. Эта интеграция лучей, основанных на глазах и свете, часто выражается как двунаправленная трассировка пути, при которой пути прослеживаются как от глаза, так и от света, а пути впоследствии соединяются соединительным лучом после некоторой длины.

Фотонное картирование — это еще один метод, в котором используется трассировка лучей как на основе света, так и на основе глаз; На начальном этапе энергичные фотоны отслеживаются вдоль лучей от источника света, чтобы вычислить оценку лучистого потока как функции трехмерного пространства (сама одноименная фотонная карта). При последующем проходе лучи прослеживаются от глаза до сцены для определения видимых поверхностей, а карта фотонов используется для оценки освещенности в точках видимой поверхности. Преимущество картирования фотонов по сравнению с двунаправленным отслеживанием пути заключается в возможности добиться значительного повторного использования фотонов, сокращая объем вычислений за счет статистической погрешности.

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

Изображение, показывающее рекурсивно генерируемые лучи от «глаза» (и через плоскость изображения) к источнику света после встречи с двумя диффузными поверхностями.

Справа находится изображение, показывающее простой пример пути лучей, рекурсивно генерируемых от камеры (или глаза) к источнику света с использованием приведенного выше алгоритма. Рассеянная поверхность отражает свет во всех направлениях.

Сначала луч создается в точке глаза и проходит через пиксель в сцену, где он попадает на диффузную поверхность. От этой поверхности алгоритм рекурсивно генерирует луч отражения, который проходит через сцену и попадает на другую диффузную поверхность. Наконец, генерируется еще один луч отражения, который проходит через сцену, где он попадает на источник света и поглощается. Цвет пикселя теперь зависит от цвета первой и второй диффузной поверхности и цвета света, излучаемого источником света. Например, если источник света излучал белый свет, а две рассеивающие поверхности были синими, то результирующий цвет пикселя будет синим.

Пример

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

В векторных обозначениях уравнение сферы с центром $\mathbf {c}$ и радиус $r$ является

$\left\Vert \mathbf {x} -\mathbf {c} \right\Vert ^{2}=r^{2}.$

Любая точка луча, начинающаяся с точки $\mathbf {s}$ с направлением $\mathbf {d}$ (здесь $\mathbf {d}$ — единичный вектор ) можно записать как

$\mathbf {x} =\mathbf {s} +t\mathbf {d} ,$

где $t$ это его расстояние между $\mathbf {x}$ и $\mathbf {s}$. В нашей проблеме мы знаем $\mathbf {c}$, $r$, $\mathbf {s}$ (например, положение источника света) и $\mathbf {d}$, и нам нужно найти $t$. Поэтому мы заменяем на $\mathbf {x}$:

$\left\Vert \mathbf {s} +t\mathbf {d} -\mathbf {c} \right\Vert ^{2}=r^{2}.$

Позволять $\mathbf {v} \ {\stackrel {\mathrm {def} }{=}}\ \mathbf {s} -\mathbf {c}$ для простоты; затем

$\left\Vert \mathbf {v} +t\mathbf {d} \right\Vert ^{2}=r^{2}$

$\mathbf {v} ^{2}+t^{2}\mathbf {d} ^{2}+2\mathbf {v} \cdot t\mathbf {d} =r^{2}$

$(\mathbf {d} ^{2})t^{2}+(2\mathbf {v} \cdot \mathbf {d} )t+(\mathbf {v} ^{2}-r^{2})=0.$

Зная, что d является единичным вектором, мы можем сделать это небольшое упрощение:

$t^{2}+(2\mathbf {v} \cdot \mathbf {d} )t+(\mathbf {v} ^{2}-r^{2})=0.$

Это квадратное уравнение имеет решения

$t={\frac {-(2\mathbf {v} \cdot \mathbf {d} )\pm {\sqrt {(2\mathbf {v} \cdot \mathbf {d} )^{2}-4(\mathbf {v} ^{2}-r^{2})}}}{2}}=-(\mathbf {v} \cdot \mathbf {d} )\pm {\sqrt {(\mathbf {v} \cdot \mathbf {d} )^{2}-(\mathbf {v} ^{2}-r^{2})}}.$

Два значения $t$ найденные в результате решения этого уравнения, являются двумя такими, что $\mathbf {s} +t\mathbf {d}$ — это точки, в которых луч пересекает сферу.

Любое отрицательное значение лежит не на луче, а в противоположной полупрямой (т. е. той, которая начинается с $\mathbf {s}$ с противоположным направлением).

Если величина под корнем ( дискриминант ) отрицательна, то луч не пересекает сферу.

Предположим теперь, что существует хотя бы положительное решение, и пусть $t$ быть минимальным. Кроме того, предположим, что сфера — это ближайший объект на нашей сцене, пересекающий наш луч, и что она сделана из отражающего материала. Нам нужно найти, в каком направлении отражается луч света. Законы отражения гласят, что угол отражения равен и противоположен углу падения падающего луча на нормаль к сфере.

Нормаль к сфере просто

$\mathbf {n} ={\frac {\mathbf {y} -\mathbf {c} }{\left\Vert \mathbf {y} -\mathbf {c} \right\Vert }},$

где $\mathbf {y} =\mathbf {s} +t\mathbf {d}$ это точка пересечения, найденная ранее. Направление отражения можно найти отразив , $\mathbf {d}$ относительно $\mathbf {n}$, то есть

$\mathbf {r} =\mathbf {d} -2(\mathbf {n} \cdot \mathbf {d} )\mathbf {n} .$

Таким образом, отраженный луч имеет уравнение

$\mathbf {x} =\mathbf {y} +u\mathbf {r} .\,$

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

Адаптивный контроль глубины

Адаптивное управление глубиной означает, что средство рендеринга прекращает генерировать отраженные/проходящие лучи, когда вычисленная интенсивность становится меньше определенного порога. Всегда должна быть установлена ​​максимальная глубина, иначе программа будет генерировать бесконечное количество лучей. Но не всегда необходимо идти на максимальную глубину, если поверхности не обладают высокой отражающей способностью. Чтобы проверить это, трассировщик лучей должен вычислить и сохранить произведение глобальных коэффициентов и коэффициентов отражения при трассировке лучей.

Пример: пусть Kr = 0,5 для набора поверхностей. Тогда от первой поверхности максимальный вклад равен 0,5, для отражения от второй: 0,5×0,5 = 0,25, третьей: 0,25×0,5 = 0,125, четвертой: 0,125×0,5 = 0,0625, пятой: 0,0625×0,5 = 0,03125 и т. д. Кроме того, мы могли бы ввести коэффициент ослабления на расстоянии, например 1/D2, что также уменьшит вклад интенсивности.

Для прошедшего луча мы могли бы сделать нечто подобное, но в этом случае расстояние, пройденное через объект, приведет к еще более быстрому снижению интенсивности. В качестве примера Холл и Гринберг обнаружили, что даже для очень отражающей сцены использование максимальной глубины 15 привело к средней глубине дерева лучей 1,7.

Граничные объемы

Включение групп объектов в наборы иерархических ограничивающих объемов уменьшает объем вычислений, необходимых для трассировки лучей. Литой луч сначала проверяется на пересечение с ограничивающим объёмом , а затем, если пересечение есть, объём рекурсивно делится до тех пор, пока луч не встретится с объектом. Лучший тип ограничивающего объема будет определяться формой лежащего в основе объекта или объектов. Например, если объекты длинные и тонкие, то сфера будет заключать в себе преимущественно пустое пространство по сравнению с коробкой. Кроме того, в блоках проще создавать иерархические ограничивающие объемы.

Обратите внимание, что использование такой иерархической системы (при условии, что это делается осторожно) меняет время вычисления пересечения с линейной зависимости от количества объектов на нечто среднее между линейной и логарифмической зависимостью. Это связано с тем, что в идеальном случае каждый тест на пересечение делит возможности на два и приводит к структуре типа двоичного дерева. Методы пространственного подразделения, обсуждаемые ниже, пытаются достичь этой цели.

Кей и Каджия приводят список желаемых свойств для иерархических ограничивающих объемов:

• Поддеревья должны содержать объекты, находящиеся рядом друг с другом, и чем дальше по дереву, тем ближе должны быть объекты.
• Объем каждого узла должен быть минимальным.
• Сумма объемов всех ограничивающих объемов должна быть минимальной.
• Больше внимания следует уделять узлам возле корня, поскольку обрезка ветки возле корня удалит больше потенциальных объектов, чем одна, расположенная дальше по дереву.
• Время, затраченное на построение иерархии, должно быть намного меньше времени, сэкономленного при ее использовании.

Интерактивная трассировка лучей

См. также: Оборудование трассировки лучей.

Первой реализацией интерактивного трассировщика лучей стала система компьютерной графики LINKS-1, построенная в 1982 году в Осаки профессорами Омурой Коичи, Сиракавой Исао и Каватой Тору с 50 студентами. Инженерной школе Университета Это была система с массовой параллельной обработкой компьютерная с 514 микропроцессорами (257 Zilog Z8001 и 257 iAPX 86 ), используемая для трехмерной компьютерной графики с высокоскоростной трассировкой лучей. По данным Общества обработки информации Японии : «В основе рендеринга трехмерных изображений лежит вычисление яркости каждого пикселя, составляющего визуализированную поверхность, с учетом заданной точки обзора, источника света и положения объекта. Система LINKS-1 была разработана для реализовать методологию рендеринга изображений, в которой каждый пиксель может обрабатываться независимо друг от друга параллельно с использованием трассировки лучей. Разработав новую методологию программного обеспечения специально для высокоскоростного рендеринга изображений, LINKS-1 смог быстро визуализировать очень реалистичные изображения». Он использовался для создания раннего трехмерного , видео неба, похожего на планетарий полностью созданного с помощью компьютерной графики. Видео было представлено в павильоне Fujitsu на Международной выставке 1985 года в Цукубе ». Это была вторая система, сделавшая это после Evans & Sutherland Digistar в 1982 году. В 1984 году дизайнеры объявили LINKS-1 самым мощным компьютером в мире.

Следующий интерактивный трассировщик лучей, первый из которых, как известно, был назван «в реальном времени», был отмечен на конференции по компьютерной графике SIGGRAPH 2005 года как инструменты REMRT/RT, разработанные в 1986 году Майком Мууссом для системы твердотельного моделирования BRL-CAD . Первоначально опубликованный в 1987 году на сайте USENIX , трассировщик лучей BRL-CAD представлял собой раннюю реализацию параллельной сетевой распределенной системы трассировки лучей, которая обеспечивала производительность рендеринга несколько кадров в секунду. Такая производительность была достигнута с помощью высокооптимизированного, но независимого от платформы механизма трассировки лучей LIBRT в BRL-CAD и использования твердой неявной геометрии CSG на нескольких параллельных машинах с общей памятью в стандартной сети. Трассировщик лучей BRL-CAD, включая инструменты REMRT/RT, по-прежнему доступен и разрабатывается сегодня как программное обеспечение с открытым исходным кодом .

С тех пор были предприняты значительные усилия и исследования по реализации трассировки лучей на скоростях в реальном времени для различных целей в автономных конфигурациях настольных компьютеров. Эти цели включают интерактивные трехмерные графические приложения, такие как постановки демосцен , компьютерные и видеоигры , а также рендеринг изображений. Некоторые программные 3D-движки реального времени, основанные на трассировке лучей, разрабатываются программистами- любителями с конца 1990-х годов.

В 1999 году команда из Университета Юты под руководством Стивена Паркера продемонстрировала интерактивную трассировку лучей вживую на Симпозиуме 1999 года по интерактивной 3D-графике. Они визуализировали 35-миллионную сферическую модель с разрешением 512 на 512 пикселей и частотой примерно 15 кадров в секунду на 60 процессорах.

Проект Open RT включал высокооптимизированное программное ядро ​​для трассировки лучей, а также API-интерфейс, подобный OpenGL , чтобы предложить альтернативу текущему подходу, основанному на растеризации, для интерактивной трехмерной графики. Аппаратное обеспечение трассировки лучей , такое как экспериментальный блок обработки лучей, разработанный Свеном Вупом из Саарского университета , было разработано для ускорения некоторых вычислительно-интенсивных операций трассировки лучей.

Quake Wars: Трассировка лучей

Идея о том, что видеоигры могут отслеживать графику в реальном времени, привлекла внимание средств массовой информации в конце 2000-х годов. За это время исследователь по имени Даниэль Пол под руководством профессора графики Филиппа Слусаллека и в сотрудничестве с Эрлангенским университетом и Саарским университетом в Германии оснастил Quake III и Quake IV движком , который он запрограммировал сам, который Саарский университет затем продемонстрировал на выставке ЦеБИТ 2007. Intel , покровитель Саара, была настолько впечатлена, что наняла Пола и приступила к исследовательской программе, посвященной графике с трассировкой лучей, которая, по ее мнению, оправдывала увеличение количества ядер ее процессоров. 12 июня 2008 года Intel продемонстрировала специальную версию Enemy Territory: Quake Wars под названием Quake Wars: Ray Traced , использующую трассировку лучей для рендеринга и работающую в базовом разрешении HD (720p). ETQW работал со скоростью 14–29 кадров в секунду на 16-ядерной (4 процессора, 4 ядра) системе Xeon Tigerton, работающей на частоте 2,93 ГГц.

На SIGGRAPH 2009 компания Nvidia анонсировала OptiX , бесплатный API для трассировки лучей в реальном времени на графических процессорах Nvidia. API предоставляет семь программируемых точек входа в конвейер трассировки лучей, что позволяет использовать пользовательские камеры, пересечения лучей, шейдеры, затенение и т. д. Такая гибкость обеспечивает двунаправленную трассировку пути, передачу света Metropolis и многие другие алгоритмы рендеринга, которые невозможно реализовать с помощью хвостовая рекурсия. Рендереры на основе OptiX используются в Autodesk Arnold, Adobe AfterEffects , Bunkspeed Shot, Autodesk Maya , 3ds max и многих других рендерерах.

В 2014 году демо-версия для PlayStation 4 видеоигры The Tomorrow Children , разработанная Q-Games и Japan Studio , продемонстрировала новые методы освещения, разработанные Q-Games, в частности, каскадную воксельную трассировку конусных лучей, которая имитирует освещение в реальном времени и использует более реалистичные отражения, а не отражения в пространстве экрана .

Nvidia представила свои графические процессоры GeForce RTX и Quadro RTX в сентябре 2018 года, основанные на архитектуре Turing , которая обеспечивает аппаратно-ускоренную трассировку лучей. Аппаратное обеспечение Nvidia использует отдельный функциональный блок, публично называемый «ядро RT». Этот блок в некоторой степени сравним с текстурным блоком по размеру, задержке и интерфейсу с ядром процессора. Модуль обеспечивает обход BVH , декомпрессию сжатого узла BVH, тестирование пересечения лучей и AABB и тестирование пересечений лучей и треугольников. GeForce RTX в виде моделей 2080 и 2080 Ti стала первой ориентированной на потребителя видеокартой, способной выполнять трассировку лучей в реальном времени. а в ноябре 2018 года от Electronic Arts стала Battlefield V первой игрой, воспользовавшейся возможностями трассировки лучей, которых она достигает с помощью нового API Microsoft DirectX Raytracing . AMD, которая уже предлагала интерактивную трассировку лучей поверх OpenCL через свой Radeon ProRender , В октябре 2020 года на онлайн-мероприятии представила серию Radeon RX 6000 , графические процессоры Navi второго поколения с поддержкой аппаратно-ускоренной трассировки лучей. С тех пор появились последующие игры, которые визуализировали графику такими средствами, что было связано с улучшениями в аппаратном обеспечении и усилиями по созданию большего количества API и игровых движков, совместимых с этой технологией. Современные домашние игровые консоли реализуют в своих графических процессорах специальные аппаратные компоненты трассировки лучей для создания эффектов трассировки лучей в реальном времени, которые начались с девятого поколения консолей PlayStation 5 , Xbox Series X и Series S.

4 ноября 2021 г. компания Imagination Technologies анонсировала графический процессор IMG CXT с аппаратно-ускоренной трассировкой лучей. 18 января 2022 года Samsung анонсировала SoC Exynos 2200 AP с аппаратно-ускоренной трассировкой лучей. 28 июня 2022 года компания Arm анонсировала Immortalis-G715 с аппаратно-ускоренной трассировкой лучей. 16 ноября 2022 года Qualcomm анонсировала Snapdragon 8 Gen 2 с аппаратно-ускоренной трассировкой лучей. 12 сентября 2023 года Apple анонсировала свой Apple A17 с аппаратно-ускоренной трассировкой лучей.

Вычислительная сложность

Для некоторых формулировок задачи трассировки лучей были доказаны результаты различной сложности. В частности, если вариант решения задачи трассировки лучей определяется следующим образом – учитывая начальное положение и направление светового луча, а также некоторую фиксированную точку, достигает ли луч в конечном итоге этой точки, тогда в указанной статье доказываются следующие результаты:

• Трассировка лучей в трехмерных оптических системах с конечным набором отражающих или преломляющих объектов, представленных системой рациональных квадратных неравенств, неразрешима .
• Трассировка лучей в трехмерных оптических системах с конечным набором преломляющих объектов, представленных системой рациональных линейных неравенств, неразрешима.
• Трассировка лучей в трехмерных оптических системах с конечным набором прямоугольных отражающих или преломляющих объектов неразрешима.
• Трассировка лучей в трехмерных оптических системах с конечным набором отражающих или частично отражающих объектов, представленных системой линейных неравенств, некоторые из которых могут быть иррациональными, неразрешима.
• Трассировка лучей в трехмерных оптических системах с конечным набором отражающих или частично отражающих объектов, представленных системой рациональных линейных неравенств, является PSPACE -трудной.
• Для любой размерности, равной или превышающей 2, трассировка лучей с конечным набором параллельных и перпендикулярных отражающих поверхностей, представленных рациональными линейными неравенствами, находится в PSPACE.

См. также

• Трассировка луча
• Трассировка конуса
• Распределенная трассировка лучей
• Глобальное освещение
• Растушевка по Гуро
• Список программного обеспечения для трассировки лучей
• Параллельные вычисления
• Отслеживание пути
• Затенение Фонга
• Прогрессивная доработка
• Затенение
• Зеркальное отражение
• Тесселяция
• Попиксельное освещение
• GPUОткрыть
• NVIDIA GameWorks
• Металл (API)
• Вулкан
• ДиректХ

Внешние ссылки

• Интерактивная трассировка лучей: замена растеризации?
• Настоящий рыболов (1978)
• Написание простой трассировки лучей (scratchapixel)
• Луч, отслеживающий тор
• Трассировка лучей в серии книг One Weekend