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

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

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

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

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

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

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

История

На этой гравюре Альбрехта Дюрера 1525 года изображена дверь Дюрера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Расчет лучей для прямоугольного окна просмотра

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

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

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

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

{\ displaystyle {\ vec {t}} = TE, \ qquad {\ vec {b}} = {\ vec {v}} \ times {\ vec {t}}}

{\ displaystyle {\ 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}}

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

{\ displaystyle 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}}}

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

{\ displaystyle {\ 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}}

Расчеты: note and ray so ${\ Displaystyle P_ {ij} = E + {\ vec {p}} _ {ij}}$ ${\ Displaystyle {\ vec {R}} _ {ij} = P_ {ij} -E = {\ vec {p}} _ {ij}}$

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

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

Вышеупомянутая формула была протестирована в этом проекте javascript (работает в браузере).

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

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

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

Алгоритм Ray casting

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

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

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

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

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

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

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

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

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

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

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

Недостатки

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

{\ Displaystyle \ mathbf {x} = \ mathbf {s} + т \ mathbf {d},}

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

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

Пусть для простоты; тогда ${\ Displaystyle \ mathbf {v} \ {\ stackrel {\ mathrm {def}} {=}} \ \ mathbf {s} - \ mathbf {c}}$

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

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

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

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

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

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

{\ Displaystyle т = {\ гидроразрыва {- (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})}}.}.

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

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

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

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

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

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

где - найденная ранее точка пересечения. Направление отражения может быть найдено с помощью отражения от относительно , то есть ${\ Displaystyle \ mathbf {y} = \ mathbf {s} + т \ mathbf {d}}$ ${\ displaystyle \ mathbf {d}}$ ${\ Displaystyle \ mathbf {п}}$

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

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

{\ Displaystyle \ mathbf {x} = \ mathbf {y} + и \ 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.

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

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

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

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

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

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

Первой реализацией интерактивного трассировщика лучей была компьютерная графическая система LINKS-1, созданная в 1982 году на Инженерной школе Осакского университета профессорами Омурой Коити, Сиракавой Исао и Каватой Тору с 50 студентами. Это было массовым параллелизмом обработки компьютерной системой с 514 микропроцессорами (257 Zilog Z8001s и 257 iAPX 86S ), используемых для рендеринга реалистичных 3D компьютерной графики с трассировки лучей с высокой скоростью. По данным Общества обработки информации Японии : «Ядро рендеринга трехмерных изображений - это вычисление яркости каждого пикселя, составляющего визуализированную поверхность, с заданной точки обзора, источника света и положения объекта. Система LINKS-1 была разработана для реализации методология рендеринга изображений, при которой каждый пиксель может обрабатываться параллельно независимо с использованием трассировки лучей. Разработав новую методологию программного обеспечения специально для высокоскоростной рендеринга изображений, LINKS-1 смогла быстро рендерить очень реалистичные изображения ». Он использовался для создания раннего 3D- видео неба, похожего на планетарий, полностью сделанного с использованием компьютерной графики. Видео было представлено в павильоне 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 году команда из Университета Юты под руководством Стивена Паркера продемонстрировала интерактивную трассировку лучей вживую на Симпозиуме по интерактивной 3D-графике 1999 года. Они визуализировали модель из 35 миллионов сфер с разрешением 512 на 512 пикселей, работающую со скоростью примерно 15 кадров в секунду на 60 процессорах.

Проект OpenRT включал высокооптимизированное программное ядро для трассировки лучей вместе с API-интерфейсом, подобным OpenGL , чтобы предложить альтернативу текущему подходу, основанному на растеризации, для интерактивной 3D-графики. Оборудование для трассировки лучей , такое как экспериментальный модуль обработки лучей, разработанный Свеном Вупом из Саарландского университета , было разработано для ускорения некоторых вычислительно-ресурсоемких операций трассировки лучей. 16 марта 2007 года Саарский университет представил реализацию высокопроизводительного движка трассировки лучей, который позволяет рендерить компьютерные игры с помощью трассировки лучей без интенсивного использования ресурсов.

Воспроизвести медиа

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

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 предоставляет семь программируемых точек входа в конвейере трассировки лучей, что позволяет настраивать камеры, пересечения лучей, шейдеры, затенение и т. Д. хвостовая рекурсия. Средства визуализации на основе OptiX используются в Autodesk Arnold, Adobe AfterEffects , Bunkspeed Shot, Autodesk Maya , 3ds max и многих других средствах визуализации.

Imagination Technologies предлагает бесплатный API под названием OpenRL, который ускоряет алгоритмы рендеринга на основе хвостовой рекурсивной трассировки лучей и вместе с их запатентованным оборудованием трассировки лучей работает с Autodesk Maya, чтобы обеспечить то, что 3D World называет «трассировкой лучей в реальном времени для обычных художников».

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

Nvidia предлагает аппаратно-ускоренную трассировку лучей в своих графических процессорах GeForce RTX и Quadro RTX, в настоящее время основанных на архитектуре Ampere . Аппаратное обеспечение Nvidia использует отдельный функциональный блок, публично называемый «ядром RT». Этот блок несколько сравним с текстурным блоком по размеру, задержке и интерфейсу с ядром процессора. Устройство включает обход BVH, декомпрессию сжатого узла BVH, тестирование пересечения лучей и AABB и тестирование пересечения лучей и треугольников.

AMD предлагает интерактивную трассировку лучей поверх OpenCL на видеокартах Vega через Radeon ProRender . В октябре 2020 года компания представила серию Radeon RX 6000 , свои графические процессоры Navi второго поколения с поддержкой аппаратно-ускоренной трассировки лучей на онлайн-мероприятии.

PlayStation 5 , Xbox серии X и серии S поддерживают специализированные трассировки луча аппаратных компонентов в своих графических процессоров в режиме реального времени трассировки лучей эффектов.

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

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

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

Languages

In other projects