Как сделать рейкастинг

Добавил пользователь Алексей Ф.
Обновлено: 04.10.2024

Raycasting (в основном на английском языке - ray casting ) - термин из компьютерной графики . Он описывает методы для быстрого представления ( визуализации ) в трехмерной сцене , но в настоящее время используется в основном в контексте с визуализацией объема . Точное определение термина варьируется в зависимости от контекста.

Raycasting в объемной визуализации

Raycasting - это метод визуализации скалярных функций в трехмерном объеме, который встречается во многих научных приложениях . В области медицины примерами являются: компьютерная томография (КТ), магнитно-резонансная томография (МРТ) или позитронно-эмиссионная томография (ПЭТ); в области численного моделирования с помощью метода конечных элементов (FEM) для вычислительной гидродинамики (CFD), в котором рассчитывается поведение потока газов и жидкостей. Полученные здесь скалярные данные, например плотность или температура , могут быть визуализированы с помощью различных методов, в том числе лучевого анализа. Различают прямые и косвенные процессы. Косвенные методы визуализируют объем с помощью полигонального промежуточного представления. Марширующие кубики - один из таких косвенных методов. Прямые методы визуализируют объем без создания таких промежуточных данных. Эти методы включают в себя raycasting и splatting . Еще одно различие проводится между процессами, ориентированными на пространство изображения (порядок изображений), и процессами, ориентированными на пространство объектов (порядок объектов).

Raycasting как процесс объемной визуализации

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

Процесс Raycasting

Raycasting отправляет визуальный луч (первичные лучи) через объем для каждого пикселя зрителя (изображения, которое нужно рассчитать). Луч отслеживается в объеме, а значения цвета и непрозрачности определяются через равные промежутки времени в точках выборки на луче. Затенение для цветовых значений во всех точках выборки также вычисляется. Вектор, полученный таким образом для линии визирования, содержит упорядоченные выборочные значения (цвет, значения непрозрачности), значения цвета, соответствующие исходному члену, и значения непрозрачности, соответствующие коэффициенту ослабления. На последнем этапе компоновка , значения цвета и непрозрачности комбинируются, и пиксель, полученный в результате прямой видимости, вычисляется в плоскости изображения.

Raycasting как простая трассировка лучей

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

Иногда рейкастинг также используется как синоним рейтрейсинга.

Raycasting в компьютерных играх

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

Были найдены различные обходные пути, призванные создать впечатление трехмерности. Двумерная графика, так называемые спрайты , используются для любых объектов, которые масштабируются и вставляются в рассчитанное изображение. В продвинутых играх, таких как Duke Nukem 3D, они выбирались в зависимости от угла, чтобы объект выглядел спереди иначе, чем сзади.

Raycasting стал популярным в первых шутерах от первого лица Catacomb , Wolfenstein 3D, Doom, Heretic и Duke Nukem 3D, так как он требует значительно меньше времени на вычисления, чем реальный 3D.

С лучевым кастингом связан алгоритм VoxelSpace , представленный в игре Comanche для визуализации полей высот . Графические движки, основанные на этом , часто просто называют воксельными движками, хотя воксели не визуализируются.

веб ссылки

Индивидуальные доказательства

Эта страница последний раз была отредактирована 7 августа 2021 в 00:52.

На прошлой неделе я разрабатывал простой алгоритм raycasting. И мне наконец удалось разобраться, как добавить текстуры и получить все работоспособное. Мне бы это понравилось. Однако даже при довольно низком разрешении 5 пикселей на вертикальную линию сканирования программа по-прежнему работает невероятно медленно. Он работает немного лучше в полноэкранном режиме, так как здесь мышь правильно работает, но все равно очень плохо.

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

Мне также понравилось бы, если бы кто-нибудь просмотрел код нормально, чтобы я мог улучшить его дальше.

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

HUD.jpg

Кровавая стена Dark.bmp

Файл Level.txt содержит 256 1 и пробелы в конфигурации 16x16, а 1 - как стены и пробелы в качестве пробелов. Но код действительно работает с сеткой любого размера. create_level() преобразует этот файл в список.

Вот содержимое файла, который я использую:

Структура папки имеет программу в одном каталоге с изображениями и текстовым файлом в подкаталоге, называемом данными, как показано:

1 ответ

Python не является быстрым языком - он торгует скоростью выполнения для гибкости и интроспективности - и вид повторяющихся численных вычислений, связанных с рендерингом ЦП, в значительной степени является наихудшим случаем для Python. Было бы гораздо разумнее использовать инструментарий 3D-рендеринга, например PyOpenGL .

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

На моем компьютере я обнаружил, что игра работает со скоростью около 18 кадров в секунду.

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

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

Это включает в себя несколько изменений в другом месте кода:

Преобразуйте текстуру в RGB после ее загрузки:

Не создавайте PixelArray (это блокирует текстуру, и нам больше не понадобится) .

Затем для каждого столбца:

Вычислить часть экрана, на которую мы будем рисовать:

Вычислить соответствующую часть текстуры:

Извлеките часть столбца из текстуры, используя subsurface :

Возьмите копию (чтобы мы не обновили оригинал) и умножим цвет с помощью fill с помощью BLEND_MULT :

Настройте его на высоту, на которой мы будем рисовать его, используя transform.scale :

Положите его на экран:

Я нахожу, что это изменение более чем удваивает частоту кадров до 40 кадров в секунду.

Как было написано выше, это изменение вызывает некоторое уродство в рендеринге стен рядом с камерой из-за того, как происходит вычисление yStart texels, чтобы выстроить линию с краем экрана. Этого можно избежать, пересчитав yStart и yHeight после colStart и colHeight , как это

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

Приведение лучей - это метод расчета CG 3D , который легко материально ускоряется специальной видеокартой.

Ускорение может быть выполнено с помощью OpenGL API , Glide (вышедшего из употребления) или Direct3D .

Он успешно использовался в начале 1990-х в видеоиграх, таких как Wolfenstein 3D или Doom . Реализация тогда была полностью программной и не требовала специального оборудования.

Резюме

Разница между raycasting и raytracing (трассировка лучей )

В некоторых работах эти два термина используются как синонимы; однако, raycasting исторически определялся по-другому, поскольку он тесно связан с первыми 3D-видеоиграми. В отличие от трассировки лучей , трассировка лучей выполняется значительно быстрее. Он использует некоторые характеристики виртуального мира:

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

Цилиндры представляют собой, например, аппроксимации с плоскими гранями. Трассировка лучей преодолевает эти ограничения, поскольку она основана на точных пересечениях с примитивами: например, сфера идеальна для трассировки лучей в том смысле, что пересечение рассчитывается аналитически в соответствии с математическим определением сферы. Это не случай с raycasting , который таким образом , представляет собой подмножество трассировки лучей и который будет подходить к сферической поверхности с плоскими гранями.

Трассировка лучей требует большей вычислительной мощности, но компенсируется несравнимым качеством изображения. Продукт лучевого литья изображает довольно угловатый блок с неприятными эффектами. Еще одно распространенное ограничение техники raycasting : поле обзора параллельно земле, невозможно иметь полностью свободную ось камеры. Это особенно заметно в ранних видеоиграх от первого лица, таких как Doom, где поле зрения всегда направлено вперед и не может смотреть на потолок или пол. Также нет возможности вращать камеру вокруг оси ( крена ).

Это потому, что raycasting - это, по сути, техника, основанная на двухмерном пространстве, а не на полном трехмерном описании мира.

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

Оптимизация Raycasting

Самый простой способ сделать raycasting - это проецировать один луч на пиксель, каждый луч ищет пространство, чтобы найти пересечение с ближайшей стеной.

Он ускорен за счет таких оптимизаций, как:

Рекурсивный бинарный поиск

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

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

Рендеринг через порталы

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

Поиск прекращается, когда субконусы зрения больше не проходят через какой-либо портал.

Таким образом, конус обзора разбивается на ряд подконусов, которые позволяют сортировать лица перед визуализацией.

Предварительный рендеринг Z- порядка

Техника, использованная в Doom . Мы бросаем только два луча для усечения лиц. Их порядок рендеринга предварительно вычисляется с помощью дерева BSP, а отсечение между гранями выполняется на одномерной оси.

Поиск лица прекращается, когда все пиксели заполнены.

Он работает быстрее, чем предыдущий, но имеет тот недостаток, что работает только со статическими пространствами.

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

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

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

Прямой объёмный рендеринг

Прямой объемный рендерер сопоставляет значению каждого воксела цвет и прозрачность. Это делается при помощи передаточной функции, которая может задаваться кусочно-линейной функцией или таблицей значений. После этого полученное RGBA значение выводится в кадровый буфер. После прорисовки всего объёма получается цельная картинка.

Объёмный рейкастинг

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

Сплэттинг

Аппаратное ускорение объемного рендеринга

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

Оптимизация

Пропуск пустого пространства

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

Ранняя остановка луча

Эта техника используется при рендеринге от ближней плоскости отображения к дальней. Фактически является поверхностным рейкастингом.

Октодерево и BSP

Использование таких иерархических структур, как октодерево и BSP-дерево, может быть полезным как при сжатии входных данных, так и при оптимизации объемного рейкастинга.

Сегментация пространства

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

Представление со множественным и адаптивным разрешением

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

Читайте также: