Ray casting

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

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

Использование

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

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

Концепция

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

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

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

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

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

Wolfenstein 3D

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

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

Серия Comanche

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

Внешние ссылки

• F. Permadi. [www.permadi.com/tutorial/raycast/index.html Ray-Casting Tutorial] (англ.). permadi.com. — Обширная многостраничная справка с детальным описанием технологии рейкастинга, включая математическое описание, программные методики, историю и области применения. Проверено 22 июня 2009. [www.webcitation.org/66cwwV9q0 Архивировано из первоисточника 2 апреля 2012].
• Johns Hopkins. [www.cs.jhu.edu/~cohen/RendTech99/Lectures/Ray_Casting.bw.pdf Ray Casting] (англ.). Department of Computer Science. — 10-страничная презентация, сфокусированная на математическом описании рейкастинга. Проверено 22 июня 2009. [www.webcitation.org/66cwx14M2 Архивировано из первоисточника 2 апреля 2012].
• Greg Humphreys. [www.cs.virginia.edu/~gfx/courses/2004/Intro.Fall.04/handouts/05-raycast.pdf Ray Casting] (англ.). University of Virginia (осень 2004 года). — 8-страничная презентация, сфокусированная на методиках и особенностях программирования рейкастинга. Проверено 22 июня 2009. [www.webcitation.org/66cwxRNVX Архивировано из первоисточника 2 апреля 2012].
• Laurent Cozic. [www.codeproject.com/KB/GDI-plus/RayCasting2D.aspx Ray casting in a 2D tile-based environment] (англ.). codeproject.com (15 сентября 2006 года). Проверено 22 июня 2009. [www.webcitation.org/66cwy5lyH Архивировано из первоисточника 2 апреля 2012].
• Malcolm Tatum. [www.wisegeek.com/what-is-ray-casting.htm What is Ray Casting?] (англ.). wisegeek. Проверено 22 июня 2009. [www.webcitation.org/66cwz7yO2 Архивировано из первоисточника 2 апреля 2012].
• Claudio Silva. [www.cs.sunysb.edu/~csilva/papers/rpe/node10.html Ray Casting] (англ.)(недоступная ссылка — история). cs.sunysb.edu (20 апреля 1995 года). Проверено 22 июня 2009. [web.archive.org/20081013043033/www.cs.sunysb.edu/~csilva/papers/rpe/node10.html Архивировано из первоисточника 13 октября 2008].
• Sench. [www.x-sky.ru/gamedev/gamedev_articles/mixed/5164-prostojj-i-optimizirovannyjj-ray.html Простой и оптимизированный Ray-casting эффект]. x-sky.ru (27 июня 2008 года). Проверено 22 июня 2009. [www.webcitation.org/66cwzkbv0 Архивировано из первоисточника 2 апреля 2012].
• [www.igromania.ru/print/index.php?ID=57676 Краткая история 3D Метод бросания лучей](недоступная ссылка — история). Игромания (журнал) (Журнал “Игромания” №4/139 2009). Проверено 22 июня 2009. [web.archive.org/20130824113752/www.igromania.ru/print/index.php?ID=57676 Архивировано из первоисточника 24 августа 2013].
• [pixellove.eu/wega/ Raycasting-Java-Applet by Peter Paulis]
• [wiioperasdk.com/wall.html Raycasting demonstration in JavaScript using a canvas]
• [leftech.com/raycaster.htm Raycasting demonstration in a web browser]

Отрывок, характеризующий Ray casting

– Так! Я знала это! Слава богу, – проговорила Соня. – Он будет жив!
Соня была взволнована не меньше своей подруги – и ее страхом и горем, и своими личными, никому не высказанными мыслями. Она, рыдая, целовала, утешала Наташу. «Только бы он был жив!» – думала она. Поплакав, поговорив и отерев слезы, обе подруги подошли к двери князя Андрея. Наташа, осторожно отворив двери, заглянула в комнату. Соня рядом с ней стояла у полуотворенной двери.
Князь Андрей лежал высоко на трех подушках. Бледное лицо его было покойно, глаза закрыты, и видно было, как он ровно дышал.
– Ах, Наташа! – вдруг почти вскрикнула Соня, хватаясь за руку своей кузины и отступая от двери.
– Что? что? – спросила Наташа.
– Это то, то, вот… – сказала Соня с бледным лицом и дрожащими губами.
Наташа тихо затворила дверь и отошла с Соней к окну, не понимая еще того, что ей говорили.
– Помнишь ты, – с испуганным и торжественным лицом говорила Соня, – помнишь, когда я за тебя в зеркало смотрела… В Отрадном, на святках… Помнишь, что я видела?..
– Да, да! – широко раскрывая глаза, сказала Наташа, смутно вспоминая, что тогда Соня сказала что то о князе Андрее, которого она видела лежащим.
– Помнишь? – продолжала Соня. – Я видела тогда и сказала всем, и тебе, и Дуняше. Я видела, что он лежит на постели, – говорила она, при каждой подробности делая жест рукою с поднятым пальцем, – и что он закрыл глаза, и что он покрыт именно розовым одеялом, и что он сложил руки, – говорила Соня, убеждаясь, по мере того как она описывала виденные ею сейчас подробности, что эти самые подробности она видела тогда. Тогда она ничего не видела, но рассказала, что видела то, что ей пришло в голову; но то, что она придумала тогда, представлялось ей столь же действительным, как и всякое другое воспоминание. То, что она тогда сказала, что он оглянулся на нее и улыбнулся и был покрыт чем то красным, она не только помнила, но твердо была убеждена, что еще тогда она сказала и видела, что он был покрыт розовым, именно розовым одеялом, и что глаза его были закрыты.
– Да, да, именно розовым, – сказала Наташа, которая тоже теперь, казалось, помнила, что было сказано розовым, и в этом самом видела главную необычайность и таинственность предсказания.
– Но что же это значит? – задумчиво сказала Наташа.
– Ах, я не знаю, как все это необычайно! – сказала Соня, хватаясь за голову.
Через несколько минут князь Андрей позвонил, и Наташа вошла к нему; а Соня, испытывая редко испытанное ею волнение и умиление, осталась у окна, обдумывая всю необычайность случившегося.
В этот день был случай отправить письма в армию, и графиня писала письмо сыну.
– Соня, – сказала графиня, поднимая голову от письма, когда племянница проходила мимо нее. – Соня, ты не напишешь Николеньке? – сказала графиня тихим, дрогнувшим голосом, и во взгляде ее усталых, смотревших через очки глаз Соня прочла все, что разумела графиня этими словами. В этом взгляде выражались и мольба, и страх отказа, и стыд за то, что надо было просить, и готовность на непримиримую ненависть в случае отказа.
Соня подошла к графине и, став на колени, поцеловала ее руку.
– Я напишу, maman, – сказала она.
Соня была размягчена, взволнована и умилена всем тем, что происходило в этот день, в особенности тем таинственным совершением гаданья, которое она сейчас видела. Теперь, когда она знала, что по случаю возобновления отношений Наташи с князем Андреем Николай не мог жениться на княжне Марье, она с радостью почувствовала возвращение того настроения самопожертвования, в котором она любила и привыкла жить. И со слезами на глазах и с радостью сознания совершения великодушного поступка она, несколько раз прерываясь от слез, которые отуманивали ее бархатные черные глаза, написала то трогательное письмо, получение которого так поразило Николая.


На гауптвахте, куда был отведен Пьер, офицер и солдаты, взявшие его, обращались с ним враждебно, но вместе с тем и уважительно. Еще чувствовалось в их отношении к нему и сомнение о том, кто он такой (не очень ли важный человек), и враждебность вследствие еще свежей их личной борьбы с ним.
Но когда, в утро другого дня, пришла смена, то Пьер почувствовал, что для нового караула – для офицеров и солдат – он уже не имел того смысла, который имел для тех, которые его взяли. И действительно, в этом большом, толстом человеке в мужицком кафтане караульные другого дня уже не видели того живого человека, который так отчаянно дрался с мародером и с конвойными солдатами и сказал торжественную фразу о спасении ребенка, а видели только семнадцатого из содержащихся зачем то, по приказанию высшего начальства, взятых русских. Ежели и было что нибудь особенное в Пьере, то только его неробкий, сосредоточенно задумчивый вид и французский язык, на котором он, удивительно для французов, хорошо изъяснялся. Несмотря на то, в тот же день Пьера соединили с другими взятыми подозрительными, так как отдельная комната, которую он занимал, понадобилась офицеру.
Все русские, содержавшиеся с Пьером, были люди самого низкого звания. И все они, узнав в Пьере барина, чуждались его, тем более что он говорил по французски. Пьер с грустью слышал над собою насмешки.
На другой день вечером Пьер узнал, что все эти содержащиеся (и, вероятно, он в том же числе) должны были быть судимы за поджигательство. На третий день Пьера водили с другими в какой то дом, где сидели французский генерал с белыми усами, два полковника и другие французы с шарфами на руках. Пьеру, наравне с другими, делали с той, мнимо превышающею человеческие слабости, точностью и определительностью, с которой обыкновенно обращаются с подсудимыми, вопросы о том, кто он? где он был? с какою целью? и т. п.
Вопросы эти, оставляя в стороне сущность жизненного дела и исключая возможность раскрытия этой сущности, как и все вопросы, делаемые на судах, имели целью только подставление того желобка, по которому судящие желали, чтобы потекли ответы подсудимого и привели его к желаемой цели, то есть к обвинению. Как только он начинал говорить что нибудь такое, что не удовлетворяло цели обвинения, так принимали желобок, и вода могла течь куда ей угодно. Кроме того, Пьер испытал то же, что во всех судах испытывает подсудимый: недоумение, для чего делали ему все эти вопросы. Ему чувствовалось, что только из снисходительности или как бы из учтивости употреблялась эта уловка подставляемого желобка. Он знал, что находился во власти этих людей, что только власть привела его сюда, что только власть давала им право требовать ответы на вопросы, что единственная цель этого собрания состояла в том, чтоб обвинить его. И поэтому, так как была власть и было желание обвинить, то не нужно было и уловки вопросов и суда. Очевидно было, что все ответы должны были привести к виновности. На вопрос, что он делал, когда его взяли, Пьер отвечал с некоторою трагичностью, что он нес к родителям ребенка, qu'il avait sauve des flammes [которого он спас из пламени]. – Для чего он дрался с мародером? Пьер отвечал, что он защищал женщину, что защита оскорбляемой женщины есть обязанность каждого человека, что… Его остановили: это не шло к делу. Для чего он был на дворе загоревшегося дома, на котором его видели свидетели? Он отвечал, что шел посмотреть, что делалось в Москве. Его опять остановили: у него не спрашивали, куда он шел, а для чего он находился подле пожара? Кто он? повторили ему первый вопрос, на который он сказал, что не хочет отвечать. Опять он отвечал, что не может сказать этого.
– Запишите, это нехорошо. Очень нехорошо, – строго сказал ему генерал с белыми усами и красным, румяным лицом.
На четвертый день пожары начались на Зубовском валу.
Пьера с тринадцатью другими отвели на Крымский Брод, в каретный сарай купеческого дома. Проходя по улицам, Пьер задыхался от дыма, который, казалось, стоял над всем городом. С разных сторон виднелись пожары. Пьер тогда еще не понимал значения сожженной Москвы и с ужасом смотрел на эти пожары.
В каретном сарае одного дома у Крымского Брода Пьер пробыл еще четыре дня и во время этих дней из разговора французских солдат узнал, что все содержащиеся здесь ожидали с каждым днем решения маршала. Какого маршала, Пьер не мог узнать от солдат. Для солдата, очевидно, маршал представлялся высшим и несколько таинственным звеном власти.
Эти первые дни, до 8 го сентября, – дня, в который пленных повели на вторичный допрос, были самые тяжелые для Пьера.

Х
8 го сентября в сарай к пленным вошел очень важный офицер, судя по почтительности, с которой с ним обращались караульные. Офицер этот, вероятно, штабный, с списком в руках, сделал перекличку всем русским, назвав Пьера: celui qui n'avoue pas son nom [тот, который не говорит своего имени]. И, равнодушно и лениво оглядев всех пленных, он приказал караульному офицеру прилично одеть и прибрать их, прежде чем вести к маршалу. Через час прибыла рота солдат, и Пьера с другими тринадцатью повели на Девичье поле. День был ясный, солнечный после дождя, и воздух был необыкновенно чист. Дым не стлался низом, как в тот день, когда Пьера вывели из гауптвахты Зубовского вала; дым поднимался столбами в чистом воздухе. Огня пожаров нигде не было видно, но со всех сторон поднимались столбы дыма, и вся Москва, все, что только мог видеть Пьер, было одно пожарище. Со всех сторон виднелись пустыри с печами и трубами и изредка обгорелые стены каменных домов. Пьер приглядывался к пожарищам и не узнавал знакомых кварталов города. Кое где виднелись уцелевшие церкви. Кремль, неразрушенный, белел издалека с своими башнями и Иваном Великим. Вблизи весело блестел купол Ново Девичьего монастыря, и особенно звонко слышался оттуда благовест. Благовест этот напомнил Пьеру, что было воскресенье и праздник рождества богородицы. Но казалось, некому было праздновать этот праздник: везде было разоренье пожарища, и из русского народа встречались только изредка оборванные, испуганные люди, которые прятались при виде французов.
Очевидно, русское гнездо было разорено и уничтожено; но за уничтожением этого русского порядка жизни Пьер бессознательно чувствовал, что над этим разоренным гнездом установился свой, совсем другой, но твердый французский порядок. Он чувствовал это по виду тех, бодро и весело, правильными рядами шедших солдат, которые конвоировали его с другими преступниками; он чувствовал это по виду какого то важного французского чиновника в парной коляске, управляемой солдатом, проехавшего ему навстречу. Он это чувствовал по веселым звукам полковой музыки, доносившимся с левой стороны поля, и в особенности он чувствовал и понимал это по тому списку, который, перекликая пленных, прочел нынче утром приезжавший французский офицер. Пьер был взят одними солдатами, отведен в одно, в другое место с десятками других людей; казалось, они могли бы забыть про него, смешать его с другими. Но нет: ответы его, данные на допросе, вернулись к нему в форме наименования его: celui qui n'avoue pas son nom. И под этим названием, которое страшно было Пьеру, его теперь вели куда то, с несомненной уверенностью, написанною на их лицах, что все остальные пленные и он были те самые, которых нужно, и что их ведут туда, куда нужно. Пьер чувствовал себя ничтожной щепкой, попавшей в колеса неизвестной ему, но правильно действующей машины.