Методика литья лучей является методологической основой твердотельного моделирования и рендеринга изображений в 3D CAD/CAM. По сути, это то же самое, что трассировка лучей для компьютерной графики, когда виртуальные световые лучи «отбрасываются» или «отслеживаются» на своем пути от фокусной точки камеры через каждый пиксель в датчике камеры, чтобы определить, что видно вдоль луча в кадре. 3D сцена. Термин «Ray Casting» был введен Скоттом Ротом, когда он работал в исследовательских лабораториях General Motors в 1978–1980 годах. В его статье «Ray Casting for Modeling Solids» [1] описываются смоделированные твердые объекты путем объединения примитивных твердых тел, таких как блоки и цилиндры, с использованием операторов множеств: объединение (+), пересечение (&) и разность (-). Общая идея использования этих бинарных операторов для твердотельного моделирования во многом принадлежит группе геометрического моделирования Фелькера и Рекичи в Рочестерском университете. [2] [3] Полный обзор методов твердотельного моделирования см . в разделе «Твердотельное моделирование». На этом рисунке справа показано U-образное соединение, смоделированное из цилиндров и блоков в бинарном дереве с использованием системы преобразования лучей Рота в 1979 году.
До создания лучей (и трассировки лучей) алгоритмы компьютерной графики проецировали поверхности или края (например, линии) из трехмерного мира на плоскость изображения, где нужно было применять логику видимости. Проекция плоскости мира на изображение — это трехмерное преобразование однородной системы координат (также известное как трехмерная проекция , аффинное преобразование или проективное преобразование ( гомография )). Рендеринга изображения таким способом сложно добиться, удалив скрытую поверхность/край. Кроме того, силуэты изогнутых поверхностей должны быть решены явно, поскольку это неявный побочный продукт преобразования лучей, поэтому нет необходимости явно решать их при каждом изменении вида.
Приведение лучей значительно упростило рендеринг изображений трехмерных объектов и сцен, поскольку линия преобразуется в линию. Таким образом, вместо того, чтобы проецировать изогнутые края и поверхности 3D-сцены на плоскость 2D-изображения, преобразованные линии (лучи) пересекаются с объектами на сцене. Однородное преобразование координат представляется матрицей 4х4. Математический метод является общим для компьютерной графики и геометрического моделирования. [4] Преобразование включает в себя вращения вокруг трех осей, независимое масштабирование по осям, перемещение в 3D и даже наклон. Преобразования легко объединяются с помощью матричной арифметики. При использовании с матрицей 4x4 точка представляется как [X, Y, Z, 1], а вектор направления — как [D x , D y , D z , 0]. (Четвертый термин предназначен для перевода и не применим к векторам направления.)
Приведение лучей — самый простой из многих алгоритмов рендеринга компьютерной графики , использующих геометрический алгоритм трассировки лучей . Алгоритмы рендеринга на основе трассировки лучей работают в порядке изображения , преобразуя трехмерные сцены в двухмерные изображения. Геометрические лучи прослеживаются от глаза наблюдателя для отбора проб света ( излучения ), идущего к наблюдателю в направлении луча. Скорость и простота распределения лучей обусловлены вычислением цвета света без рекурсивного отслеживания дополнительных лучей, которые измеряют яркость, падающую в точку, в которую попадает луч. Это исключает возможность точной визуализации отражений , преломлений или естественного затухания теней ; однако все эти элементы можно в некоторой степени подделать, творчески используя карты текстур или другие методы. Высокая скорость вычислений сделала метод raycasting удобным методом рендеринга в первых 3D-видеоиграх в реальном времени.
Идея метода луча заключается в том, чтобы проследить лучи из глаза, по одному на пиксель, и найти ближайший объект, блокирующий путь этого луча. Представьте себе изображение как дверь-ширму, где каждый квадрат на экране представляет собой пиксель. Это объект, который глаз видит через этот пиксель. Используя свойства материала и эффект освещения в сцене, этот алгоритм может определить затенение этого объекта. Делается упрощающее предположение, что если поверхность обращена к источнику света, свет достигнет этой поверхности и не будет блокироваться или находиться в тени. Затенение поверхности рассчитывается с использованием традиционных моделей затенения трехмерной компьютерной графики. Одним из важных преимуществ метода raycasting по сравнению со старыми алгоритмами развертки была его способность легко обрабатывать неплоские поверхности и твердые тела, такие как конусы и сферы . Если математическую поверхность можно пересечь лучом, ее можно визуализировать с помощью метода преобразования лучей. Сложные объекты можно создавать с помощью методов твердотельного моделирования и легко визуализировать.
Из аннотации к статье «Лучевое моделирование для моделирования твердых тел»: Для визуализации и анализа моделируемых составных твердых тел в качестве зондов используются виртуальные световые лучи. Благодаря своей простоте, метод ray casting надежен и расширяем. Самая сложная математическая задача — найти точки пересечения линии и поверхности. Таким образом, поверхности в виде плоскостей, квадрик, торов и, возможно, даже параметрических участков поверхности могут ограничивать примитивные твердые тела. Здесь рассматриваются адекватность и эффективность рейкастинга. Возможность быстрого создания изображений для интерактивного моделирования является самой большой проблемой.
Лучи света и геометрия камеры составляют основу всех геометрических рассуждений. На этом рисунке показана модель камеры-обскуры для эффекта перспективы при обработке изображений и модель параллельной камеры для массового анализа. Простая модель камеры-обскуры состоит из фокусной точки (или точки глаза) и квадратной матрицы пикселей (или экрана). Прямые лучи света проходят через массив пикселей, соединяя точку фокуса со сценой, по одному лучу на пиксель. Чтобы затенить изображения, интенсивность лучей измеряется и сохраняется в пикселях. Отражающая поверхность, отвечающая за значение пикселя, пересекает луч пикселя.
Когда фокусное расстояние, расстояние между фокусной точкой и экраном, бесконечно, тогда вид называется «параллельным», потому что все лучи света параллельны друг другу и перпендикулярны экрану. Хотя перспективный вид является естественным для создания изображений, в некоторых приложениях необходимы лучи, которые можно равномерно распределить в пространстве.
Для удобства моделирования типичная стандартная система координат камеры имеет экран в плоскости XY, сцену в полупространстве +Z и точку фокуса на оси -Z.
Луч — это просто прямая линия в трехмерном пространстве модели камеры. Его лучше всего определить как вектор направления в параметризованной форме как точку (X 0 , Y 0 , Z 0 ) и вектор направления (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 — это расстояние вдоль линии. Вектор можно легко нормализовать с помощью следующих вычислений:
Dist = √(D x 2 + D y 2 + D z 2 )Д х = Д х / Расст.D y = D y / Расст.Д z = D z / Расст.
Учитывая геометрические определения объектов, каждый из которых ограничен одной или несколькими поверхностями, результат вычисления пересечения одного луча со всеми ограниченными поверхностями на экране определяется двумя массивами:
Параметры луча: 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 × ( т [2]- т [1] + т [4]- т [3] + ∙∙∙ + т [n]- т [n-1]) / L
где L определяется как длина вектора направления. (Если оно уже нормализовано, оно равно 1.)
L = √(D x 2 + D y 2 + D z 2 )
Каждый ( t [ i ]- t [ i -1])/L представляет собой длину отрезка луча, находящегося внутри твердого тела.
На этом рисунке показаны параллелепипеды твердого тела, смоделированного с помощью метода лучевого литья. Это использование модели камеры с параллельной проекцией.
На этом рисунке показан пример бинарных операторов в дереве композиции с использованием + и –, где оценивается один луч.
Процедура преобразования лучей начинается с вершины дерева композиции твердого тела, рекурсивно спускается вниз, классифицирует луч относительно примитивных твердых тел, а затем возвращается вверх по дереву, объединяя классификации левого и правого поддеревьев.
На этом рисунке показано объединение левой и правой классификаций для всех трех бинарных операторов.
Приведение лучей — это естественный инструмент моделирования для создания затененных изображений. Система преобразования лучей в оттенках серого, разработанная Скоттом Ротом и Дэниелом Бассом из GM Research Labs, создавала изображения на цветном растровом дисплее Ramtek примерно в 1979 году. Для составления изображений система предоставляла пользователю следующие элементы управления:
На этом рисунке показана настольная сцена с тенями от двух точечных источников света.
Алгоритмы затенения, реализующие все реалистичные эффекты, требуют больших вычислительных затрат, но относительно просты. Например, на следующем рисунке показаны дополнительные лучи, которые могут быть отброшены от одного источника света.
Для одного пикселя изображения, подлежащего рендерингу, алгоритм рисует луч, начинающийся с фокусной точки, и определяет, что он пересекает полупрозрачный прямоугольник и блестящий круг. Затем необходимо пропустить дополнительный луч, начиная с этой точки, в направлении, симметрично противоположном нормали к поверхности в точке пересечения луча и поверхности, чтобы определить, что видно в зеркальном отражении. Этот луч пересекает непрозрачный треугольник. Наконец, каждая точка пересечения луча и поверхности проверяется, чтобы определить, находится ли она в тени. Луч «щупа тени» направляется из точки пересечения луча и поверхности к источнику света, чтобы определить, не блокирует ли какая-либо другая поверхность этот путь.
Тернер Уиттед называет вторичные и дополнительные лучи «рекурсивной трассировкой лучей». [5] [Визуализация комнаты с зеркалами будет дорогостоящей, поэтому разумно ограничить количество рекурсий.] Уиттед смоделировал преломление для прозрачных пленок, генерируя вторичный луч из точки видимой поверхности под углом, определяемым показателем преломления твердого тела. Вторичный луч затем обрабатывается как зеркальный луч. Формулу преломления и графические примеры см. в статье Уиттеда.
Приведение лучей квалифицируется как метод грубой силы для решения проблем. Минимальный алгоритм прост, особенно с учетом его многочисленных применений и простоты использования, но приложения обычно излучают много лучей. Миллионы лучей могут быть использованы для визуализации одного кадра анимационного фильма. Время компьютерной обработки увеличивается с увеличением разрешения экрана и количества примитивных тел/поверхностей в композиции.
Используя минимальные ограничивающие рамки вокруг тел в дереве композиции, исчерпывающий поиск пересечения луча и твердого тела напоминает эффективный бинарный поиск. Алгоритм грубого перебора выполняет исчерпывающий поиск, поскольку он всегда посещает все узлы дерева, преобразуя луч в локальные системы координат примитивов, проверяя пересечения луча и поверхности и комбинируя классификации, даже если луч явно не попадает в твердое тело. Чтобы обнаружить «явный промах», более быстрый алгоритм использует дерево двоичной композиции как иерархическое представление пространства, которое занимает твердая композиция. Но вся информация о положении, форме и размере хранится в листьях дерева, где находятся примитивные твердые тела. Верхние и промежуточные узлы дерева определяют только операторы объединения.
Характеризация пространства, которое заполняют все твердые тела, с помощью вложений дает всем узлам дерева абстрактную сводку информации о положении и размере. Затем быстрые тесты «луч пересекает вложение» направляют поиск в иерархии. Если тест не пройден в промежуточном узле дерева, луч гарантированно классифицируется как не составной, поэтому рекурсия вниз по его поддеревьям для дальнейшего исследования не требуется.
Точно оценить экономию средств от использования вложений сложно, поскольку она зависит от пространственного распределения примитивов (распределения сложности) и организации дерева композиции. Оптимальные условия:
Напротив, худшее состояние:
Ниже приведены различные улучшения производительности, сделанные в статье Рота о преобразовании лучей, но впоследствии были внесены значительные улучшения и другими авторами.
Неровные края, вызванные сглаживанием, являются нежелательным эффектом методов выборки точек и являются классической проблемой алгоритмов растрового отображения. Линейные или плавно изогнутые края будут выглядеть неровными и особенно нежелательны в анимации, поскольку при движении изображения края кажутся размытыми или похожими на маленькие движущиеся эскалаторы. Кроме того, могут быть потеряны детали сцены, меньшие, чем расстояние между лучами. Неровные края линейного рисунка можно сгладить, следуя за краем. Цель такого алгоритма — минимизировать количество строк, необходимых для рисования изображения, с точностью до одного пикселя. В результате края становятся гладкими. Линейные рисунки выше были нарисованы таким образом.
Чтобы сгладить неровные края затененного изображения с точностью до субпикселя, необходимо отбросить дополнительные лучи для получения информации о краях. (Общий подход см. в разделе «Суперсэмплинг» .) Края образуются в результате пересечения поверхностей или профиля изогнутой поверхности. Применяя «когерентность», как описано выше, посредством двоичного поиска, если видимая поверхность в пикселе (X,Y) отличается от видимой поверхности в пикселе (X+1,Y), то луч может быть сгенерирован посередине их в (X+ ½,Y) и видимая поверхность там идентифицирована. Расстояние между точками выборки может быть дополнительно разделено, но поиск не обязательно должен быть глубоким. Основная глубина поиска для сглаживания неровных краев является функцией градиента интенсивности по краю. Поскольку (1) область изображения, содержащая края, обычно составляет небольшой процент от общей площади и (2) дополнительные лучи, отбрасываемые при двоичном поиске, могут быть ограничены по глубине — глубине видимых примитивов, образующих края — стоимость сглаживание неровных краев доступно по цене.
Историю создания лучей см. в разделе « Трассировка лучей (графика)» , поскольку обе они, по сути, представляют собой одну и ту же технику под разными названиями. Скотт Рот изобрел термин «кастинг лучей» еще до того, как услышал о «трассировке лучей». Кроме того, разработка Скоттом Ротом метода распределения лучей в GM Research Labs происходила одновременно с работой Тернера Уиттеда по трассировке лучей в Bell Labs.
В ранних играх от первого лица рейкастинг использовался для эффективной визуализации трехмерного мира из двухмерного игрового поля с использованием простого одномерного сканирования по горизонтальной ширине экрана. [6] Ранние шутеры от первого лица использовали 2D-лучевое моделирование как метод создания 3D-эффекта из 2D-мира. Хотя мир выглядит трехмерным, игрок не может смотреть вверх или вниз или только под ограниченными углами с сдвиговым искажением. [6] [7] Этот стиль рендеринга устраняет необходимость запуска луча для каждого пикселя в кадре, как в случае с современными движками; как только точка попадания найдена, к текстуре поверхности применяется проекционное искажение, и из результата в кадр копируется весь вертикальный столбец. Этот стиль рендеринга также накладывает ограничения на тип рендеринга, который может быть выполнен, например, сортировка по глубине , но не буферизация глубины . То есть полигоны должны быть сплошными друг перед другом или позади них, они не могут частично перекрываться или пересекаться.
Видеоигра Wolfenstein 3D была построена на основе квадратной сетки стен одинаковой высоты, сочетающихся с однотонными полами и потолками. Чтобы нарисовать мир, для каждого столбца пикселей экрана трассировался один луч , а вертикальный фрагмент текстуры стены выбирался и масштабировался в зависимости от того, где в мире луч достигает стены и как далеко он проходит перед этим. [8]
Уровни на основе сетки преследовали двойную цель: столкновения со стенками лучей можно обнаружить быстрее, поскольку потенциальные попадания становятся более предсказуемыми, а затраты памяти уменьшаются. Однако кодирование открытых пространств требует дополнительного места.
В игре ShadowCaster от Raven Software используется улучшенный движок на основе Wolfenstein с добавленными текстурами полов и потолков и переменной высотой стен.
Движок Voxel Space , разработанный NovaLogic для игр Comanche , прослеживал луч через каждый столбец пикселей экрана и сравнивал каждый луч с точками на карте высот . Затем он преобразовывал каждый элемент карты высот в столбец пикселей, определял, какие из них видимы (то есть не перекрыты пикселями, нарисованными спереди), и рисовал их соответствующим цветом из карты текстуры. [9]
Более поздние игры для DOS, такие как DOOM от id Software, сохранили многие ограничения скорости 2.5D для raycasting, но перешли на альтернативные методы рендеринга (например, BSP ), что лишило их движков raycasting. [10]
В вычислительной геометрии проблема распределения лучей также известна как проблема стрельбы лучами и может быть сформулирована как следующая задача запроса: задан набор объектов в d -мерном пространстве, предварительно обработайте их в структуру данных так, чтобы для каждого луча запроса первоначальный объект, на который попал луч, можно быстро найти. Проблема исследовалась для различных настроек: размерность пространства, типы объектов, ограничения на лучи запроса и т. д. [11] Одним из методов является использование разреженного октодерева вокселей .