Ray casting

Ray casting, рейкастинг, метод «бросания лучей» (англ. ray casting — бросание лучей) — один из методов рендеринга в компьютерной графике, при котором сцена строится на основе замеров пересечения лучей с визуализируемой поверхностью. Этот термин впервые использовался в компьютерной графике в 1982 году в публикации Скотта Рота (англ. Scott Roth), который применил его для описания метода рендеринга CSG-моделей^[1].

Хотя термины «ray casting» (метод бросания лучей) и «ray tracing» (трассировка лучей) часто использовались как синонимы в ранней литературе^[2], посвящённой компьютерной графике, в современной компьютерной графике эти термины различны и описывают разные методики, которые, тем не менее, имеют много общего^[3].

Рейкастинг может относиться к:

• Общая проблема определения первого пересечения объекта с лучом^[4].
• Методика для удаления невидимых поверхностей, основанная на поиске первого пересечения луча, который проектируется из точки обозрения к каждому пикселю изображения.
• Нерекурсивный вариант трассировки лучей, при котором «бросаются» только первичные лучи.
• Метод прямого объёмного рендеринга, также называемый «volume ray casting^[англ.]».

Рейкастинг не является синонимом к рейтрейсингу (обратной трассировке лучей), но он может быть представлен как сокращённая и существенно более быстрая версия алгоритма обратной трассировки лучей. Оба алгоритма являются «image order» и используются в компьютерной графике для рендеринга трёхмерных сцен на двухмерный экран с помощью проекционных лучей, которые проецируются от глаз наблюдателя к поверхности, отражающей или излучающей свет. Метод «бросания лучей» не вычисляет отражения лучей света, которые возникают после того, когда луч, проецирующийся от глаза к источнику света, пересечётся с поверхностью. Эта особенность делает невозможным реалистичный рендеринг отражений, преломлений и естественной проекции теней с помощью рейкастинга. Однако все эти особенности могут быть добавлены с помощью «фальшивых» (обманных, аппроксимационных) методик, например, через использование текстурных карт или другие методы. Высокая скорость вычисления сделала рейкастинг удобным методом рендеринга в ранних компьютерных играх с трёхмерной графикой реального времени.

В реальной природе источник света испускает луч света, который, «путешествуя» по пространству, в конечном счёте «натыкается» на какую-либо преграду, которая прерывает распространение этого светового луча. Луч света можно представить в виде потока фотонов, который движется вдоль вектора луча. В какой-либо точке пути с лучом света может случиться любая комбинация трёх вещей: поглощение, отражение и преломление. Поверхность может отразить весь световой луч или только его часть в одном или нескольких направлениях. Поверхность может также поглотить часть светового луча, что приводит к потере интенсивности отраженного и/или преломлённого луча. Если поверхность имеет свойства прозрачности, то она преломляет часть светового луча внутри себя и изменяет его направление распространения, поглощая некоторый (или весь) спектр луча (и, возможно, изменяя цвет). Суммарная интенсивность светового луча, которая была «потеряна» вследствие поглощения, преломления и отражения, должна быть в точности равной исходящей (начальной) интенсивности этого луча. Поверхность не может, например, отразить 66 % входящего светового луча, и преломить 50 %, так как сумма этих порций будет равной 116 %, что больше 100 %. Отсюда вытекает, что отраженные и/или преломлённые лучи должны «стыкаться» с другими поверхностями, где их поглощающие, отражающие и преломляющие способности снова вычисляются, основываясь на результатах вычислений входящих лучей. Некоторые из лучей, сгенерированных источником света, распространяются по пространству и, в конечном счете, попадают на область просмотра (глаз человека, объектив фото- или видеокамеры и т. д.). Попытка симулировать физический процесс распространения света путём трассировки световых лучей, используя компьютер, является чрезмерно расточительной, так как только незначительная доля лучей, сгенерированных источником света, попадает на область просмотра.

Первый алгоритм рейкастинга (не рейтрейсинга), используемый для рендеринга, был представлен Артуром Аппелем (англ. Arthur Appel) в 1968 году^[5]. В основе рейкастинга стои́т идея испускать лучи из «глаз» наблюдателя, один луч на пиксель, и находить самый близкий объект, который блокирует путь распространения этого луча. Используя свойства материала и эффект света в сцене, алгоритм рейкастинга может определить затенение данного объекта. Предположение в упрощении основано на том, что если поверхность размещена перед светом, то свет достигнет поверхности и не будет блокирован или находиться в тени. Затенение поверхности вычисляется, используя алгоритмы затенения традиционной компьютерной трёхмерной графики. Одним из преимуществ рейкастинга является способность легко обрабатывать неплоские поверхности и сплошные тела вроде сферы или конуса. Если математическая поверхность может быть пересечена лучом, то она может быть отрендерена, используя рейкастинг. Сложные объекты могут быть созданы с использованием методов моделирования сплошных тел и легко отрендерены.

Рейкастинг для создания компьютерной графики впервые был применён учёными из Mathematical Applications Group, Inc.^[англ.] (MAGI) из Элмсфорда, Нью-Йорк (англ. Elmsford, New York). Эта компания была создана в 1966 году для проведения вычислений по радиологической экологии для Министерства обороны США. Программное обеспечение разработки MAGI не только вычисляло то, как гамма-лучи отражаются от поверхностей (рейкастинг для радиации был сделан ещё в 1940-х), но и то, как проникают и преломляются внутри материалов. Под руководством доктора Филиппа Миттелмана (англ. Dr. Philip Mittelman) учёные разработали метод генерирования изображений, взяв за основу то же самое программное обеспечение. В 1972 году MAGI стала коммерческой студией по созданию анимации. Она использовала рейкастинг для генерирования трёхмерной компьютерной анимации телевизионных реклам, образовательных фильмов, и, в конечном счете, для художественных кинофильмов. Компания MAGI ответственна за создание большей части анимации в научно-фантастическом фильме «Трон». Для создания анимации использовался исключительно метод рейкастинга. В 1985 году MAGI обанкротилась.

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

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

Для игр серии «Comanche» компания NovaLogic разработала отдельный движок, называемый «Voxel Space» (с англ. — «воксельное пространство»). Этот движок прослеживает луч, исходящий через каждый столбец пикселей экрана и проверяет каждый луч против точек на карте высот. Далее движок трансформирует каждый элемент карты высот в столбец пикселей, определяя, какие из них видимы и отрисовывает их с соответствующим цветом, который берётся из текстурной карты^[7].

• F. Permadi. Ray-Casting Tutorial (англ.). permadi.com. — Обширная многостраничная справка с детальным описанием технологии рейкастинга, включая математическое описание, программные методики, историю и области применения. Дата обращения: 22 июня 2009. Архивировано из оригинала 2 апреля 2012 года.
• Johns Hopkins. Ray Casting (англ.). Department of Computer Science. — 10-страничная презентация, сфокусированная на математическом описании рейкастинга. Дата обращения: 22 июня 2009. Архивировано из оригинала 2 апреля 2012 года.
• Greg Humphreys. Ray Casting (англ.). University of Virginia (осень 2004). — 8-страничная презентация, сфокусированная на методиках и особенностях программирования рейкастинга. Дата обращения: 22 июня 2009. Архивировано из оригинала 2 апреля 2012 года.
• Laurent Cozic. Ray casting in a 2D tile-based environment (англ.). codeproject.com (15 сентября 2006). Дата обращения: 22 июня 2009. Архивировано из оригинала 2 апреля 2012 года.
• Malcolm Tatum. What is Ray Casting? (англ.). wisegeek. Дата обращения: 22 июня 2009. Архивировано из оригинала 2 апреля 2012 года.
• Claudio Silva. Ray Casting (англ.). cs.sunysb.edu (20 апреля 1995). Дата обращения: 22 июня 2009. Архивировано из оригинала 13 октября 2008 года.
• Sench. Простой и оптимизированный Ray-casting эффект  (неопр.). x-sky.ru (27 июня 2008). Дата обращения: 22 июня 2009. Архивировано из оригинала 6 июля 2009 года.
• Краткая история 3D Метод бросания лучей  (неопр.). Игромания (журнал) (Журнал “Игромания” №4/139 2009). Дата обращения: 22 июня 2009. Архивировано из оригинала 24 августа 2013 года.
• Raycasting-Java-Applet by Peter Paulis