Трассиро́вка луче́й ( англ. Ray tracing ; рейтре́йсинг ) — один из методов геометрической оптики — исследование оптических систем путём отслеживания взаимодействия отдельных лучей с поверхностями. В узком смысле — технология построения изображения трёхмерных моделей в компьютерных программах, при которых отслеживается обратная траектория распространения луча (от экрана к источнику).

Трассировка лучей в компьютерных играх — это решение для создания реалистичного освещения, отражений и теней, обеспечивающее более высокий уровень реализма по сравнению с традиционными способами рендеринга . Turing от Nvidia стала первой архитектурой (лето 2018), позволяющей проводить трассировку лучей в реальном времени на GPU . Другие области применения трассировки лучей — это аурализация и высокочастотные технологии.

Происхождение и значение

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

Первое изображение с трассировкой лучей было отображено на экране, подобном осциллографу , в Университете Мэриленда в 1963 году. В качестве разработчиков алгоритма трассировки лучей часто упоминают Артура Аппеля, Роберта Голдштейна и Роджера Нагеля, опубликовавших в конце 1960-х годов алгоритм. Другими исследователями, которые в то время занимались методами трассировки лучей, были Херб Стейнберг, Марти Коэн и Юджин Трубецкой. Трассировка лучей основана на геометрической оптике, где под светом понимается группа лучей. Методы, используемые при трассировке лучей, использовались гораздо раньше, в том числе производителями оптических систем. Сегодня многие средства визуализации (компьютерные программы для создания изображений из 3D-сцен) используют трассировку лучей, возможно, в сочетании с другими процессами.

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

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

Достоинства и недостатки текущих реализаций метода

Достоинства

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

Недостатки

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

Методы трассировки лучей для теплообмена

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

В системах с простой геометрией при отсутствии экранов угловые коэффициенты рассчитываются по формуле 1. В отсутствие поглощающей и рассеивающей среды угловой коэффициент с поверхности на поверхность :

${\displaystyle F_{1,2}={1 \over \pi A_{1}}\int _{A1}^{}\int _{A2}^{}{cos(\theta _{1})cos(\theta _{2}) \over R^{2}}dA2dA1}$ (1)

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

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

${\displaystyle F_{1,2}={1 \over \pi A_{1}}\sum _{i.}\sum _{j.}{cos(\theta _{1})cos(\theta _{2}) \over {R_{i,j}}^{2}}v_{i,j}\Delta A_{2,j}\Delta A_{1,i}}$ (2)

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

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

Итак,

1) В большинстве систем имеются препятствия, которые блокируют прохождение излучения;

2) Вычисление угловых коэффициентов без учета экранирования излучения приводит к погрешностям до 100 % при определении температур и тепловых потоков;

3) Учет экранирования излучения требует на несколько порядков больше времени, чем расчет радиационного теплообмена без экранирования.

Ограничивающие объемы и иерархия ограничивающих объемов

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

Следующим значительным шагом в ускорении трассировки лучей является построение иерархии ограничивающих объемов: для каждой группы ограничивающих объемов строится свой ограничивающий объем «более высокого уровня». Получающаяся структура данных называется иерархией ограничивающих объемов (BVH – Bounding Volume Hierarchy) и хранится в виде двоичного дерева.

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

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

Двоичное разбиение пространства

Метод двоичного разбиения пространства также использует ограничивающие объемы, содержащие все объекты геометрии, и иерархическую структуру в виде дерева, которое называют BSP деревом (BSP – Binary Space Partitioning – двоичное разбиение пространства).

Свойства метода:

1) BSP дерево всегда строится сверху вниз;

2) Делится на две части не группа объектов (ограничивающих объемов), а пространство;

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

Ускорение трассировки лучей достигается за счет способа прохода по дереву и выборочной проверки пересечения луча с параллелепипедами. Существует несколько таких способов, однако наиболее распространенным способом, применяемым как для BSP дерева, так и для иерархии ограничивающих объемов, является следующий алгоритм:

1) Проверяется пересечение луча с главным параллелепипедом (ограничивающим объемом). Если пересечения нет, то луч не пересекается ни с одним из экранов.

2) Если луч пересекается с параллелепипедом, то проверяется пересечение с первым дочерним параллелепипедом. Если пересечения нет, то луч должен пересекаться с другим дочерним параллелепипедом. Если пересечение с первым дочерним параллелепипедом есть, то для него определяется список дочерних параллелепипедов, и проверяется пересечение с ними.

3) Шаг 2 повторяется, пока не будет найдена точка пересечения с каким-либо экраном. Если таких точек несколько, то определяется ближайшая к началу луча точка пересечения.

Равномерная и иерархическая сетка

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

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

При трассировке лучей последовательно определяются номера ячеек, через которые проходит луч :

1) Если в текущей ячейке нет объектов, то определяется номер следующей ячейки.

2) Если в текущей ячейке находятся объекты, каждый из них проверяется на пересечение с лучом

3) Если луч пересекается с одним или несколькими объектами в текущей ячейке, то определяется ближайшая к началу луча точка пересечения и соответствующий объект, на этом трассировка данного луча заканчивается.

4) Если луч не пересекается ни с одним объектом или ячейка сетки пуста, то повторяется процесс по пунктам 1-3.

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

Использование неравномерной объемной сетки

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

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

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

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

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

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

Программное обеспечение

Свободное

• BRL-CAD
• Cycles ( Blender )
• LuxRender
• YafaRay
• POV-Ray

Проприетарное

• Arnold
• Brazil R/S
• (плагин к 3DS MAX)
• finalRender
• (интерактивный рейтрейсер)
• Indigo Renderer
• Kerkythea
• (как часть пакета Houdini)
• Maxwell Render
• mental ray
• RenderMan (PhotoRealistic или PRMan)
• V-Ray
• bCAD
• SolidWorks

См. также

• Трассировка пути

Примечания

Ссылки

• Дмитрий Чеканов. (неопр.) Tom's Hardware (7 сентября 2009). Дата обращения: 7 сентября 2009.
• Лев Дымченко. (неопр.) 6. (13 декабря 2009). Дата обращения: 21 марта 2010. 8 февраля 2012 года.
• (рус.)
• — Статьи по трассировке лучей + рейтрейсер на CUDA (рус.)
• — короткие статьи и ссылки (англ.)
• (англ.) /вебархив/

Литература

• J. Mahan Robert., 2016 The Monte Carlo Ray-Trace Method in Radiation Heat Transfer and Applied Optics, John Wiley & Sons Limited
• Cosenza, B., 2008. “A Survey on Exploiting Grids for Ray Tracing”, Eurographics Italian Chapter Conference.
• Modest, M.F., 2003, Radiative Heat Transfer, Second Edition, Academic Press.
• Wald, I., Mark, W.R., Gunther, J., Boulos, S., Ize, T. et al. 2009. “State of the Art in Ray Tracing Animated Scenes”, Computer graphics forum, 28(6), pp. 1691-1722.
• Hapala, M., Havran, V., 2011. “Review: Kd-tree Traversal Algorithms for Ray Tracing”, Computer graphics forum, 30(1), pp. 199-213.
• Kolingerova, I.: 3D - Line Clipping Algorithms - A Comparative Study, The Visual Computer, Vol.11, No.2, pp.96-104, 1994.
• Skala,V., Kolingerova, I., Blaha, P.: A comparison of 2d line clipping algorithms, Machine Graphics&Vision, Vol.3,No.4, pp.625-633, 1995.

Программное обеспечение

• — a Physically Based Raytracer
• от 12 сентября 2006 на Wayback Machine
• — realtime raytracing library
• — Brook GPU realtime raytracing