Трассировка лучей (Mjgvvnjkftg lrcyw)

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

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

Другие области применения трассировки лучей — это аурализация и высокочастотные технологии.

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

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

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

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

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

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

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

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

Достоинства

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

Недостатки

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

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

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

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

$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, с умноженный на функцию видимости:

$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³). В такой ситуации важнейшую роль играют методы ускорения трассировки лучей, которые не требуют проверки пересечения луча с каждым экраном.

Итак:

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
• Sunflow
• YafaRay
• POV-Ray

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

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

См. также

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

Ссылки

• Дмитрий Чеканов. Метод трассировки лучей против растеризации: новое поколение качества графики?  (неопр.) Tom's Hardware (7 сентября 2009). Дата обращения: 7 сентября 2009.
• Лев Дымченко. Проблемы трассировки лучей — из будущего в реальное время  (неопр.) 6. Мир nVidia (13 декабря 2009). Дата обращения: 21 марта 2010. Архивировано 8 февраля 2012 года.
• Интерактивная трассировка лучей c использованием SIMD инструкций (рус.)
• ray-tracing.ru — Статьи по трассировке лучей + рейтрейсер на CUDA (рус.)
• The Ray Tracing News — короткие статьи и ссылки (англ.)
• Games using realtime raytracing  (англ.) /вебархив/

Литература

• 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.

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

• PBRT — a Physically Based Raytracer
• Tachyon Архивная копия от 12 сентября 2006 на Wayback Machine
• Rayshade
• OpenRT — realtime raytracing library
• Raster3D
• interactive kd-tree ray tracing — Brook GPU realtime raytracing
• Zemax
• More ray tracing source code links