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