Рэй кастинг

Лучистое изображение идеализированного карданного шарнира с тенью

Ray casting является методологической основой трехмерного моделирования CAD / CAM и визуализации изображений. По сути, это то же самое, что трассировка лучей для компьютерной графики, где виртуальные световые лучи «отбрасываются» или «прослеживаются» на своем пути от фокальной точки камеры через каждый пиксель сенсора камеры, чтобы определить, что видно вдоль луча в 3-D сцена. Термин «Ray Casting» был введен Скоттом Ротом в исследовательских лабораториях General Motors с 1978 по 1980 годы. Его статья "Ray Casting для моделирования твердых тел", ^[1]описывает смоделированные твердые объекты путем комбинирования примитивных тел, таких как блоки и цилиндры, с использованием операторов множества union (+), пересечения (&) и разницы (-). Общая идея использования этих бинарных операторов для твердотельного моделирования во многом принадлежит группе геометрического моделирования Фолькера и Реквича в Университете Рочестера. ^{[2] [3]} См. Твердотельное моделирование для получения широкого обзора методов твердотельного моделирования. На этом рисунке справа показан U-образный шарнир, смоделированный из цилиндров и блоков в двоичном дереве с использованием системы литья лучей Рота, около 1979 года.

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

Приведение лучей значительно упростило рендеринг трехмерных объектов и сцен, поскольку линия трансформируется в линию. Таким образом, вместо проецирования изогнутых краев и поверхностей в трехмерной сцене на плоскость двухмерного изображения, преобразованные линии (лучи) пересекаются с объектами в сцене. Однородное преобразование координат представлено матрицей 4x4. Математический прием является общим для компьютерной графики и геометрического моделирования. ^[4] Преобразование включает в себя вращение вокруг трех осей, независимое масштабирование по осям, перемещение в трехмерном пространстве и даже наклон. Преобразования легко объединяются с помощью матричной арифметики. Для использования с матрицей 4x4 точка представлена ​​как [X, Y, Z, 1], а вектор направления представлен как [D _x , D _y , D_z , 0]. (Четвертый термин предназначен для перевода и не применяется к векторам направления.)

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

Концепция [ править ]

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

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

Из аннотации к статье «Ray Casting for Modeling Solids»: Для визуализации и анализа смоделированных составных тел виртуальные световые лучи отбрасываются как зонды. В силу своей простоты метод ray casting надежен и расширяем. Самая сложная математическая задача - найти точки пересечения линии и поверхности. Таким образом, поверхности в виде плоскостей, квадрик, торов и, возможно, даже параметрических участков поверхности могут ограничивать примитивные тела. Здесь рассматриваются вопросы, связанные с адекватностью и эффективностью использования лучей. Возможность быстрого создания изображений для интерактивного моделирования - самая большая проблема.

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

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

Для удобства моделирования типичная стандартная система координат для камеры имеет экран в плоскости XY, сцену в полупространстве + Z и точку фокуса на оси -Z.

Луч - это просто прямая линия в трехмерном пространстве модели камеры. Лучше всего определить его как вектор направления в параметризованной форме в виде точки (X ₀ , Y ₀ , Z ₀ ) и вектора направления (D _x , D _y , D _z ). В этой форме точки на линии упорядочены и доступны через один параметр t. Для каждого значения t определяется соответствующая точка (X, Y, Z) на прямой:

 X = X 0 + t · D x Y = Y 0 + t · D y Z = Z 0 + t · D z

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

 Расст = √ (D x 2 + D y 2 + D z 2 ) D x = D x / расстояние D y = D y / Dist D z = D z / Dist

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

 Параметры луча: t [1], t [2], ..., t [n] Указатели поверхности: S [1], S [2], ..., S [n]

где n - количество пересечений лучей и поверхностей. Упорядоченный список параметров луча t [i] обозначает точки входа-выхода. Луч входит в твердое тело в точке t [1], выходит в t [2], входит в твердое тело в точке t [3] и т. Д. Точка t [1] находится ближе всего к камере, а t[n] самый дальний. В сочетании с параметрами луча указатели поверхностей содержат уникальный адрес для информации о пересекаемой поверхности. Поверхность может иметь различные свойства, такие как цвет, зеркальность, прозрачность с / без преломления, полупрозрачность и т. Д. Твердое тело, связанное с поверхностью, может иметь свои собственные физические свойства, такие как плотность. Это может быть полезно, например, когда объект состоит из набора различных материалов, и интерес представляют общий центр масс и моменты инерции.

Применение информации [ править ]

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

ЛИНИЙНЫЕ ЧЕРТЕЖИ . Чтобы нарисовать видимые края твердого тела, генерируйте по одному лучу на пиксель, двигаясь по экрану сверху вниз, влево-вправо. Оцените каждый луч, чтобы идентифицировать видимую поверхность S [1], первый указатель поверхности в отсортированном списке пересечений лучей и поверхностей. Если видимая поверхность в пикселе (X, Y) отличается от видимой поверхности в пикселе (X-1, Y), отобразите вертикальную линию длиной в один пиксель с центром в точке (X-½, Y). Точно так же, если видимая поверхность в точке (X, Y) отличается от видимой поверхности в пикселе (X, Y-1), отобразить горизонтальную линию длиной в один пиксель с центром в точке (X, Y-½). Результирующий рисунок будет состоять только из горизонтальных и вертикальных краев и будет выглядеть неровным в разрешении курса.

Система лучей Рота генерировала изображения твердых объектов справа. Для оптимизации использовались боксы, динамическое ограничение и согласованность. Для каждого изображения на экране была сделана выборка с плотностью около 100x100 (например, 10 000) лучей, и новые края были обнаружены с помощью двоичного поиска. Затем все края сопровождались нанесением дополнительных лучей с шагом в один пиксель на двух сторонах краев. Каждое изображение было нарисовано на трубке Tektronix с разрешением 780x780.

ТЕНЁННЫЕ КАРТИНЫ . Чтобы сделать закрашенное изображение, снова пролейте на экран один луч на пиксель. Однако на этот раз используйте указатель видимой поверхности S [1] на каждом пикселе, чтобы получить доступ к описанию поверхности. Исходя из этого, вычислите нормаль к поверхности в видимой точке t [1]. Значение пикселя, отображаемая интенсивность света, пропорционально косинусу угла, образованного нормалью к поверхности и вектором источника света к поверхности. Обработка всех пикселей таким образом дает растровое изображение сцены.

ВЫЧИСЛЕНИЕ ОБЪЕМА И МОМЕНТОВ ИНЕРЦИИ . Объем (и аналогичные свойства) твердого тела, ограниченного криволинейными поверхностями, легко вычислить методом интегрирования «аппроксимирующих сумм», аппроксимируя твердое тело набором прямоугольных параллелепипедов. Это достигается за счет «углубленного» снимка твердого тела в параллельном виде. Если лучи проходят через экран в твердое тело, твердое тело разбивается на объемные элементы. Два измерения параллелепипедов постоянны, что определяется двумерным расположением лучей на экране. Третье измерение является переменным и определяется вычисленной точкой входа-выхода. В частности, если расстояние между лучами на экране по горизонтали и вертикали равно S, то объем, «обнаруживаемый» каждым лучом, равен

 S × S × ( t [2] - t [1] + t [4] - t [3] + ∙∙∙ + t [n] - t [n-1]) / L

где L определяется как длина вектора направления. (Если уже нормализовано, это равно 1.)

 L = √ (D x 2 + D y 2 + D z 2 )

Каждый ( t [ i ] - t [ i -1]) / L - это длина сегмента луча, который находится внутри твердого тела.

На этом рисунке показаны параллелепипеды для смоделированного твердого тела с использованием метода лучевого литья. Это использование модели камеры с параллельной проекцией.

Классификация лучей In-Out [ править ]

На этом рисунке показан пример бинарных операторов в дереве композиции с использованием + и -, где оценивается один луч.

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

На этом рисунке показано объединение левой и правой классификаций для всех трех бинарных операторов.

Реалистичные закрашенные изображения [ править ]

Ray casting - естественный инструмент моделирования для создания затемненных изображений. Система оттенков серого, разработанная Скоттом Ротом и Дэниелом Бассом из GM Research Labs, производила изображения на цветном растровом дисплее Ramtek примерно в 1979 году. Для компоновки изображений система предоставляла пользователю следующие элементы управления:

 Вид • Направление и положение обзора • Фокусное расстояние: ширина-угол от перспективы до параллели • Коэффициент масштабирования

 Освещение • Количество источников света • Расположение и сила света • При желании тень • Интенсивность окружающего света и фона

 Поверхностное отражение •% отражено диффузно •% отражено зеркально •% передано

На этом рисунке показана сцена на столе с тенями от двух точечных источников света.

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

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

Тернер Уиттед называет вторичный и дополнительный лучи «Рекурсивной трассировкой лучей». ^[5] [Комната с зеркалами будет дорого стоить для рендеринга, поэтому разумно ограничить количество рекурсий.] Белое моделирование преломления для прозрачных пленок путем генерации вторичного луча из точки видимой поверхности под углом, определяемым показателем преломления твердого тела. Затем вторичный луч обрабатывается как зеркальный луч. Формулу преломления и наглядные примеры см. В статье Уиттеда.

Вложения и эффективность [ править ]

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

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

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

Точно оценить экономию затрат при использовании вложений сложно, потому что это зависит от пространственного распределения примитивов (распределения сложности) и от организации дерева композиции. Оптимальные условия:

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

Напротив, худшее состояние:

• Все примитивные вложения взаимно перекрываются

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

• Ранние выходы . Если оператор в составном узле в дереве - или & и луч классифицируется как выходящий из левого субтвердого тела, тогда луч будет классифицирован как выходящий из составного, независимо от классификации луча по отношению к правому субтвердому телу. твердый. Таким образом, в классификации луча относительно правильного субтвердого тела нет необходимости, и этого следует избегать для повышения эффективности.
• Преобразования . Первоначально комбинируя преобразование экрана в сцену с преобразованием примитива из сцены в локальное и сохраняя результирующие преобразования экрана в локальные в структурах данных примитива, устраняется одно преобразование луча на пересечение луча и поверхности.
• Рекурсия . Учитывая глубокое дерево композиции, рекурсия может быть дорогостоящей в сочетании с выделением и освобождением памяти. Рекурсию можно моделировать, используя статические массивы в виде стеков.
• Динамическое ограничение . Если должны отображаться только видимые края твердого тела, алгоритм преобразования лучей может динамически ограничить луч, чтобы прервать поиск. То есть, обнаружив, что луч пересекает субтвердое тело, алгоритм может использовать ближайшую к экрану точку пересечения, чтобы ужесточить границу глубины для теста «прямоугольник пересечения лучей». Это работает только для + части дерева, начиная с вершины. С помощью - и & соседние «входящие» части луча могут позже стать «выходящими».
• Согласованность . Принцип согласованности заключается в том, что поверхности, видимые в двух соседних пикселях, скорее всего, будут одинаковыми, чем разными. Разработчики компьютерной графики и систем машинного зрения применили эту эмпирическую истину для повышения эффективности и производительности. Для штриховых рисунков область изображения, содержащая края, обычно намного меньше, чем общая область изображения, поэтому отбрасывание лучей должно быть сосредоточено вокруг краев, а не в открытых областях. Это может быть эффективно реализовано путем редкой выборки на экране лучей и последующего определения местоположения, когда соседние лучи идентифицируют различные видимые поверхности, края посредством двоичного поиска.

Сглаживание [ править ]

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

Чтобы сгладить неровные края затененного изображения с точностью до субпикселей, необходимо использовать дополнительные лучи для получения информации о краях. (См. Суперсэмплингдля общего подхода.) Края образуются пересечением поверхностей или профилем криволинейной поверхности. Применяя «Когерентность», как описано выше, с помощью двоичного поиска, если видимая поверхность в пикселе (X, Y) отличается от видимой поверхности в пикселе (X + 1, Y), то луч может быть сгенерирован на полпути в (X + ½, Y) и идентифицированная видимая поверхность. Расстояние между точками выборки можно разделить дальше, но поиск необязательно должен быть глубоким. Первичная глубина поиска для сглаживания неровных краев зависит от градиента интенсивности по краю. Так как (1) область изображения, содержащая края, обычно составляет небольшой процент от общей площади, и (2) дополнительные лучи, отбрасываемые при двоичном поиске, могут быть ограничены по глубине (то есть видимых примитивов, образующих края), стоимость для сглаживание неровных краев доступно.

История лучей [ править ]

Историю использования трассировки лучей см. В разделе Трассировка лучей (графика), потому что оба они в основном одно и то же. Скотт Рот изобрел термин «трассировка лучей» до того, как услышал о «трассировке лучей». Разработка Скоттом Ротом методов трассировки лучей в GM Research Labs произошла одновременно с работой Тернера Уиттеда по трассировке лучей в Bell Labs.

Кастинг лучей в ранних компьютерных играх [ править ]

Wolfenstein 3D [ править ]

Мир в известной видеоигре Wolfenstein 3D был построен из квадратной сетки стен с одинаковой высотой и одноцветных полов и потолков. Чтобы нарисовать мир, для каждого столбца пикселей экрана был трассирован один луч, и вертикальный фрагмент текстуры стены был выбран и масштабирован в соответствии с тем, где в мире луч падает на стену и как далеко он проходит до этого. ^[6]

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

Серия команчей [ править ]

Вокселей Космический двигатель , разработанный NovaLogic для команч игр прослеживается луч через каждую колонку экранных пикселей и проходит каждый луч от точек в высотах . Затем он преобразовал каждый элемент карты высот в столбец пикселей, который определил, какие из них являются видимыми (то есть не были перекрыты пикселями, которые были нарисованы впереди), и нарисовал их соответствующим цветом из карты текстуры. ^[7]

Настройка вычислительной геометрии [ править ]

В вычислительной геометрии проблема преобразования лучей также известна как проблема съемки лучей и может быть сформулирована как следующая проблема запроса: для заданного набора объектов в d- мерном пространстве их предварительная обработка в структуру данных, чтобы для каждого луча запроса, первоначальный объект, на который попал луч, можно найти быстро. Проблема была исследована для различных настроек: размерность пространства, типы объектов, ограничения на лучи запроса и т. Д. ^[8] Один из методов - использовать разреженное октодерево вокселей .

См. Также [ править ]

• Объемное лучевое литье
• 2.5D

Ссылки [ править ]

Внешние ссылки [ править ]

• Пример Raycasting в браузере. (недоступен)
• Самолеты Raycasting в WebGL с исходным кодом
• Интерактивный Raycaster для Commodore 64 в 254 байтах (с исходным кодом)
• Интерактивный Raycaster для MSDOS в 64 байта (с исходным кодом)