Реализация в реальном времени метода трассировки лучей
Пример реализации в реальном времени метода трассировки лучей: необычные возможности и принцип работы. Оптимизация под SSE
<br/><br/>
<br/>Вступление
<br/>В данной статье рассматривается оригинальный графический движок для компьютерных игр, основанный на методе трассировки лучей - совершенно отличном от используемых в современных популярных трёхмерных играх. Соответственно, движком не используются(!) 3D-акселераторы, без которых, казалось бы, немыслима игровая графика.
<br/><br/>Речь пойдет о необычных возможностях, предоставляемых движком, и принципах его работы. Кроме того, будут рассмотрены аспекты оптимизации приложений под SIMD расширения. В первую очередь, под SSE - дополнительный набор процессорных команд, впервые реализованный в процессорах Pentium III, Celeron II. Наконец, будут приве...
Пример реализации в реальном времени метода трассировки лучей: необычные возможности и принцип работы. Оптимизация под SSE
Вступление
В данной статье рассматривается оригинальный графический движок для компьютерных игр, основанный на методе трассировки лучей - совершенно отличном от используемых в современных популярных трёхмерных играх. Соответственно, движком не используются(!) 3D-акселераторы, без которых, казалось бы, немыслима игровая графика.
Речь пойдет о необычных возможностях, предоставляемых движком, и принципах его работы. Кроме того, будут рассмотрены аспекты оптимизации приложений под SIMD расширения. В первую очередь, под SSE - дополнительный набор процессорных команд, впервые реализованный в процессорах Pentium III, Celeron II. Наконец, будут приведены показатели производительности программы на новейших процессорах.
Автор выражает надежду, что чтение данной статьи не вызовет затруднений у любого читателя iXBT.com, для которого эта статья будет не первой.
Зачем?
Действительно, зачем нужно изобретать ещё один движок, когда их и так огромное количество? Что ещё нужно, когда есть потрясающие по качеству движки Quake III и Unreal?
Возьмите в руки самую мощную базуку, развернитесь к какой-нибудь стене и стреляйте бесконечно долго. Ничего не случится: уровень современной трёхмерной игры выточен из абсолютно твёрдого тела. Это не сильно обедняет gameplay, игровой процесс, если вы спустились в эти катакомбы пострелять пару часов. А если вам тут жить? Что-то хочется достроить, что-то - расширить. Может, вам самому захочется построить себе дворец. Может, другим игровым персонажам захочется его разрушить.
Все подобные возможности должны поддерживаться графическим движком игры. Играющему дано делать только то, что позволяет движок и ничего более. А если играющий захочет всё взорвать? А если захочет выключить один светильник и включить другой в другом месте? В ответ подобным поползновениям движок лишь промолчит.
Соответственно, и игр таких в полном 3D нет. Почему так? Всё просто: чтобы быстро рисовать большие уровни, их заранее долго просчитывают и при отрисовке кадра используют записанную информацию. Например, есть комната, заранее определяется, какие другие комнаты видны из неё и, когда играющий находится внутри этой комнаты, рисуются только эта комната и видимые из неё. Это позволяет многократно уменьшить количество рисуемых за кадр треугольников. Зато, выломать стену комнаты нельзя: алгоритм даст сбой, не будет рисовать то, что открылось. Так как это не просчитано заранее.
Ладно бы были проблемы только с видимостью: рисовали бы уровни поменьше, пока ускорители недостаточно мощные. Проблема гораздо глубже. Дело в том, что нужно ещё рассчитывать тени от объектов, стен, лестниц и т.д. Чтобы сцена выглядела реалистично, она должна быть реалистично освещена. Под лестницей темновато, около окна светловато. Сломайте лестницу, закройте окно - освещение никто не изменит, поскольку его очень долго вычислять на базе современных алгоритмов рисования треугольников с помощью z-буфера. Доказывать тут нечего: если бы было легко, это давно бысделали, благо акселераторы уже весьма мощные. Источник света даже подвигать нельзя - как в таком доме жить?
Подойдём к проблеме с другой стороны. Уровень, вместе со всей предварительно просчитанной информацией, занимает весьма нехило - мегабайты. А если уровни нужно очень часто подгружать в многопользовательской игре по интернет?
Что?
Я решил создать графический движок, удовлетворяющий следующим требованиям: нет никакой предварительной обработки сцены, положение и количество источников света и объектов может меняться произвольным образом в любое время. То есть, каждый кадр рисуется как бы новая сцена. Это должно позволить создавать новые оригинальные игры и расширить известные жанры.
Ничто не даётся задаром, всегда приходится чем-то жертвовать. Я пожертвовал представлением объектов посредством треугольников. В качестве базовых примитивов были выбраны сферы. То есть, объекты будут представляться не совокупностью треугольников, а совокупностью сфер.
Ясное дело, что как из треугольников, так и из сфер можно составить любой объект. Вопрос стоит лишь в количестве необходимых примитивов. Надо стараться обойтись как можно меньшим, иначе производительность упадёт ниже нижнего.
Почему в качестве примитивных элементов выбраны именно сферы, а в качестве метода - метод трассировки лучей? Дело в том, что при полигональном представлении объектов, треугольниками, например, очень много труда уходит на рассчет тени от объекта. Существуют разные методы - см. статью "Обзор алгоритмов построения теней в реальном времени". Они либо неявно требуют предварительную информацию об объекте, как метод теневых объёмов - иначе этот метод будет страшно долго работать на сложных объектах, либо требуют многократной отрисовки объекта (в текстуру) и нещадно эксплуатируют видео-ускоритель, как методы наложения теней с помощью проективных текстур. Отмечу ещё один их существенный недостаток, который не очень заметен в различных демонстрационных программах: если объект отбрасывает тень на удалённый предмет, то тень от него будет очень угловатой. Чтобы этого не случилось, объект необходимо отрисовывать в теневую текстуру с гигантским разрешением.
к статье о трассировке лучей
Shadowcast - демонстрационная программа от NVidia. Не самая новая, GF3 не требует.
Видимо, не случайно затеняемая площадка мала. Но всё равно заметно, как с увеличением расстояния от объекта до тени, тень огрубляется.
Далее, возникают проблемы с самозатенением объекта: когда объект отбрасывает тень сам на себя, а не на отделённый от него предмет. Эти проблемы носят на самом деле фундаментальный характер, в том смысле, что они органически присущи методу визуализации посредством отрисовки треугольников и применения z-буфера.
Рассчитывать тень от сферических объектов легко, рисовать сферы методом трассировки лучей тоже относительно легко - это и определило мой выбор.
Скорость трассировки лучей
Одним из свойств алгоритмов трассировки лучей заключается в большой зависимости скорости работы от разрешения экрана. Типичная формула времени работы выглядит таким образом: c1*n*ln(n)+c2*n*n+c3*ScreenWidth*ScreenHeight. c1, c2, с3 - некоторые константы, n-количество объектов на сцене. В первую очередь, рассмотрим главный член - c2*n*n, имеющий второй порядок по количеству объектов на сцене. Его происхождение просто: это время расчёта теней. Как ни крути, в этом вопросе от квадратичной зависимости далеко не уйти. Различные методы оптимизации, кластеризация объектов и т.п., в общем случае позволяют лишь уменьшить константу c2, не более. Этот член жестко лимитирует количество объектов на сцене. Начиная с некоторого момента, незначительное увеличение числа объектов вызывает очень большое падение производительности.
Влияние первого члена на общее время работы не очень существенно. Таким образом, когда сцена заполнена объектами в наибольшем возможном количестве, на первое место выходит последний член, зависящий от разрешения экрана. Эта величина отражает скорость собственно трассировки лучей, соответствующих точкам экрана. Это константа, но гигантская! Гигантская благодаря большой величине площади экрана в пикселях. Например, 800*600=480000, 1024*768=786432. Для современных процессоров получается всего около 100 тактов на обработку луча при частоте кадров около 25.
Некоторое недоумение вызывает независимость c3 от количества объектов. Дело в том, что анализ сцены перед запуском цикла трассировки позволяет существенно оптимизировать расчёты в самом цикле. За счёт этого, сколько бы ни было объектов на сцене, будет искаться пересечение луча с фиксированным количеством объектов. В принципе, с3 зависит от n, но этой зависимостью можно пренебречь.
Одним из главных последствий существования этой константы стала невозможность осуществления трассировки лучей в реальном времени на старых персональных компьютерах, оснащённых процессорами PentiumII и ниже. Эта константа даже на маленьких разрешениях - 400х300 - полностью съедала всю мощность процессора. Но сейчас этот барьер пройден! Производительности новейших процессоров для персональных компьютеров хватает для осуществления трассировки лучей в высоких разрешениях.
Далее я приступаю к описанию созданного мною графического движка VirtualRay, умеющего рисовать только объекты из сфер, зато позволяющего радикально изменять сцену в реальном времени.
Движок VirtualRay
Рабочими разрешениями движка VirtualRay на процессорах Pentium III с SSE являются разрешения 640x480 и 800x600 с глубиной цвета 32бит, то есть, движок работает в true color.
Естественно, очень много произвольно расположенных сфер отрисовывать не получилось. С приемлемой скоростью рисуются сцены, состоящие из нескольких тысяч сфер. Соответственно, движок хорошо рисует те объекты, для которых представление сферами легко возможно. Например, космос: планеты, звёзды, космические корабли и космические станции. Чудовищ, инопланетян, иномирян и их жилища. Технические объекты. Символы, абстрактные создания и сюрреалистические миры.
Поддерживается наложение и билинейная фильтрация текстур, что обеспечивает качественное изображение.
В угоду быстродействию выбрана простейшая модель освещённости, все источники света считаются точечными.
Возможна прозрачность сфер, причём коэффициенты прозрачности могут динамически меняться, и могут быть различными для каждого цветового канала.
Источника света также могут быть цветными.
Движок может работать в произвольном разрешении, как 320x240 и ниже, так и 1600x1200 и выше. Весь вопрос в скорости работы.
Более описывать нет смысла, как говорится, лучше один раз увидеть, чем сто раз услышать. На сайте www.virtualray.ru, находится текущая демо-версия движка и скриншоты. Ввиду моих низких художественных и моделлерских способностей создать высокоэстетичную демо-версию со стильными текстурами не очень получилось, получилось - технологическую демо-программу. Однако, её можно использовать в качестве игрушечного строительного конструктора из шаров.
Для ознакомления с демкой требуется компьютер с процессором PentiumMMX и выше и видео-карточка, поддерживающая true color в 32-битном формате. (совместимости с Intel 740 нет, так как там true color только в формате 24 бита. Но практически все современные карточки поддерживают необходимый формат). Вот ссылка www.virtualray.ru/demo/demo.zip. Одно замечание: иногда формат представления цвета в видеокарте определяется неправильно и, например, небо получается желтым вместо голубого. В этом случае рекомендуется угадать и выбрать в меню более подходящий формат. Так как на больших мониторах низкие разрешения выглядят слишком зернисто, для повышения быстродействия вместо уменьшения разрешения лучше слегка уменьшить площадь экрана.
Ниже я приведу несколько скриншотов из демо-версии. Они весьма неполно передают возможности движка, так как одним из его достоинств является динамическая игра света и тени, непередаваемая статическим изображением.
к статье о трассировке лучей
Производительность
Частота кадров - показатель, на который обращают внимание в первую очередь. Мы ещё коснёмся производительности движка на различных системах, сейчас же рассмотрим показатели на системе на базе PentiumIII800EB. Отмечу, так как движок не использует видео-ускорители, его производительность практически полностью определяется мощностью процессора.
Типичная частота кадров - 20 в разрешении 800x600x32 (800x450x32). Вроде бы совсем не впечатляет на сегодняшний день. Однако, FPS движка обладает двумя очень полезными свойствами, которые отчасти компенсируют её относительно небольшую величину. Первое свойство заключается в близости минимального и среднего FPS. Среднее FPS может быть 25, а минимальное - 22. А минимальное FPS, это даже более важный параметр, чем среднее. Во многих играх когда ходишь - частота кадров около 50, а только начнётся стрельба, враги появятся, FPS сразу упадёт вдвоё и больше.
Второе важное свойство - стабильность частоты кадров. Что это такое? Допустим, есть 50 кадров в секунду. Вроде бы, много. По идее, каждый кадр отрисовывается за 20 миллисекунд. Но в реальности некоторые кадры могут рендерится значительно дольше 20 миллисекунд, а другие - соответственно быстрее. В частности, такое может быть из-за необходимости периодически кэшировать данные, например, при повороте камеры. В результате, при формально высоком среднем FPS движение может не быть плавным. Движок VirtualRay рисует кадры независимо и демонстрируемый FPS реалистичен.
В общем, для чемпионата профессиональных квакеров не подойдёт, но играть вполне возможно. Особенно в игры, жанр которых не требует исключительно стрельбы.
Хочу также отметить, что не все оптимизирующие алгоритмы проверены, не все оптимизирующие алгоритмы придуманы. Я надеюсь, что ещё удастся увеличить скорость работы движка.
Устройство Сферического движка
Сферический движок почти полностью основан на алгоритмах, хорошо известных в компьютерной графике и многократно и детально описанных в книжках, посвящённых методу трассировки лучей. Мне практически не пришлось придумывать оригинальные алгоритмы, только адаптировать известные к сферам и real-time. Я отсылаю заинтересованного читателя, например, к книжке Е.В. Шикина, А.В. Борескова "Компьютерная графика. Динамика, реалистические изображения" Москва.: "Диалог-МИФИ". В интернете можно найти достаточно примеров из этой книжки. Видимо, где-то есть и текст. Если же у вас нет трудностей при чтении английских текстов, то просто море информации о трассировке лучей к вашим услугам в англоязычном интернете. Правда, я в большей степени основывался на знаниях из учебника по аналитической геометрии.
Рассмотрим принципиальную схему работы движка. Engine разбит на две существенно различающиеся части: в первой части осуществляется предварительный анализ сцены, вторая часть - двойной цикл трассировки лучей, отвечающих точкам экрана.
На входе движок получает описание сцены: положение и свойства сфер, расположение и параметры источников света. Эти данные попадают в блок первичного анализа - первую часть блока предварительного анализа сцены. В нём происходит отсечение не попавших в кадр сфер и источников света, зоны действия которых не видны. Происходит приведение координат объектов относительно положения наблюдателя, рассчитываются часто используемые далее величины, вроде расстояний до сфер.
Далее начинает работу блок распределения сфер по областям экрана. Экран разбивается на много прямоугольных областей, для каждой из которых вычисляется массив потенциально видимых сфер. То есть тех сфер, с которыми могут пересечься лучи, отвечающие точкам экрана, составляющим данную область.
Путём измельчения областей можно добиться, что бы почти на любую область приходилось всего несколько сфер, что сильно снижает затраты в гигантском цикле трассировки лучей.
Затем осуществляется расчёт отношения затенённости. Для каждой сферы определяется, сколько источников света её освещают. Если их много, то выбираются несколько, вносящие основной вклад в освещённость.
Для каждой сферы находятся все сферы, затеняющие её. Это несложно сделать благодаря простоте геометрической формы сферы. Теперь, когда затенители определены, точка сферы в цикле трассировки проверяется на затенение лишь ограниченным кругом сфер. Информация о затеняющих сферах, как то относительное положение и расстояние, упаковывается в оптимальный для вычислений при помощи SSE. Подробно об оптимизации под SSE - позднее.
Всё, можно запускать цикл трассировки.
Замечание к реализации. Первая часть, реализующая сложные и разнообразные алгоритмы, целиком написана на языке C++. Вторая часть, исходный код которой значительно меньше в размере, полностью написана на ассемблере и имеет три варианта, написанные для различных процессоров. Варианты различаются набором используемых команд. Оптимально использование SSE, но возможна работа и на компьютерах без SSE, необходима только поддержка технологии MMX. Конечно, на стареньком Pentium166MMX программа будет работать в режиме слайд-шоу, но в маленьком окошке можно посмотреть.
Набор команд Процессоры
SSE + Enhanced MMX - Pentium III, Pentium4, Celeron II, AthlonXP
FPU + Enhanced MMX - Athlon, Duron, (K6-III, K6-2+)
FPU + MMX - Pentium MMX, Pentium II, Celeron, K6-2
Отмечу, что для работы с вещественными числами используется SSE/FPU, для работы с целыми числами и числами с фиксированной точкой используется MMX. Обычные регистры (eax, ebx, ecx, edx, esi, edi) используются для хранения и вычисления адресов и флагов.
Программа откомпилирована при помощи IntelC++Compiler4.5, встроенного в Microsoft Visual C++ 6.0.
Области применения Сферического движка
Где можно использовать столь необычный движок, очень хорошо делающий одно и крайне плохо другое? Область применения сферического движка можно разделить на две части: использование в компьютерных играх и применение в иных целях. Начнём с не совсем игровых приложений.
Очевидно узкоспециальное приложение к визуализации моделей молекул и атомов. Правда, тени там выглядят неуместными: атом ведь не шарик. Описание шара занимает даже меньше места, чем описание треугольника, а шар всё-таки более богатая фигура. Это наталкивает на мысль о применении движка в интернете. Можно рисовать и легко пересылать эмблемы, логотипы, символические анимированные сценки. Для этих целей производительности движка вполне хватит - это же не на полный экран выводить сцену с большой частотой кадров. Плюс - практически полная независимость от видео-карточки: не нужно возится с драйверами, не нужно тестировать на миллионе конфигураций, не нужно обращать внимание на поддержку операционной системой графических библиотек. Есть ли DirectX, какая версия OpenGL - все эти вопросы особой роли не играют. Обеспечивается идентичность изображения у всех пользователей, с точностью до монитора, конечно. Это не так, как у видео-ускорителей: один поддерживает одно, другой - другое. На одном тени видны, на другом - нет, на третьем видны, но жутко тормозят.
Плавно перейдём в другую область применения движка. Онлайновые игры через интернет - вот где замечательно проявляются достоинства сферического движка. Как хорошо в многопользовательских играх дать возможность участникам в полном 3D в режиме реального времени строить и разрушать игровой уровень по своему усмотрению! И относительная низость FPS не так важна - всё равно связь мешает точному прицеливанию. Да и суть многопользовательской игры не всегда полностью состоит из одной стрельбы.
Игровую вселенную можно разбить на анклавы, представленные автономными сценам, между ними организовать какие-нибудь гиперпереходы. При перемещении новая сцена будет грузиться мгновенно.
Космические симуляторы любых видов - ещё одно поле приложения движка VirtualRay. Планетные системы, астероидные поля, космические аппараты - всё это прекрасно изображается при помощи сфер. Можно составить этакую "Звезду Смерти" и взорвать её при необходимости.
Игры аркадного толка также вполне могут базироваться на Сферическом движке.
Возможны приложения в играх экзотических жанров. Например, в играх, основанных на конструировании механизмов или создании живых существ.
Заключение
Пути развития неисповедимы. Трудно заранее определённо сказать о перспективах той или иной технологии. Несомненна некоторая научная ценность движка VirtualRay. Однако, найдётся ли ему практическое применение в какой-либо области, покажет время. Быть может, некоторые идеи, заложенные в движок, продолжат своё развитие и найдут своё воплощение в совершенно иной форме.
взято с сайта ixbt.com
Опубликовано -- 25 ноября 2001 года
обсуждать здесь https://forums.overclockers.ru/viewtopic.php?t=267387
Вступление
В данной статье рассматривается оригинальный графический движок для компьютерных игр, основанный на методе трассировки лучей - совершенно отличном от используемых в современных популярных трёхмерных играх. Соответственно, движком не используются(!) 3D-акселераторы, без которых, казалось бы, немыслима игровая графика.
Речь пойдет о необычных возможностях, предоставляемых движком, и принципах его работы. Кроме того, будут рассмотрены аспекты оптимизации приложений под SIMD расширения. В первую очередь, под SSE - дополнительный набор процессорных команд, впервые реализованный в процессорах Pentium III, Celeron II. Наконец, будут приведены показатели производительности программы на новейших процессорах.
Автор выражает надежду, что чтение данной статьи не вызовет затруднений у любого читателя iXBT.com, для которого эта статья будет не первой.
Зачем?
Действительно, зачем нужно изобретать ещё один движок, когда их и так огромное количество? Что ещё нужно, когда есть потрясающие по качеству движки Quake III и Unreal?
Возьмите в руки самую мощную базуку, развернитесь к какой-нибудь стене и стреляйте бесконечно долго. Ничего не случится: уровень современной трёхмерной игры выточен из абсолютно твёрдого тела. Это не сильно обедняет gameplay, игровой процесс, если вы спустились в эти катакомбы пострелять пару часов. А если вам тут жить? Что-то хочется достроить, что-то - расширить. Может, вам самому захочется построить себе дворец. Может, другим игровым персонажам захочется его разрушить.
Все подобные возможности должны поддерживаться графическим движком игры. Играющему дано делать только то, что позволяет движок и ничего более. А если играющий захочет всё взорвать? А если захочет выключить один светильник и включить другой в другом месте? В ответ подобным поползновениям движок лишь промолчит.
Соответственно, и игр таких в полном 3D нет. Почему так? Всё просто: чтобы быстро рисовать большие уровни, их заранее долго просчитывают и при отрисовке кадра используют записанную информацию. Например, есть комната, заранее определяется, какие другие комнаты видны из неё и, когда играющий находится внутри этой комнаты, рисуются только эта комната и видимые из неё. Это позволяет многократно уменьшить количество рисуемых за кадр треугольников. Зато, выломать стену комнаты нельзя: алгоритм даст сбой, не будет рисовать то, что открылось. Так как это не просчитано заранее.
Ладно бы были проблемы только с видимостью: рисовали бы уровни поменьше, пока ускорители недостаточно мощные. Проблема гораздо глубже. Дело в том, что нужно ещё рассчитывать тени от объектов, стен, лестниц и т.д. Чтобы сцена выглядела реалистично, она должна быть реалистично освещена. Под лестницей темновато, около окна светловато. Сломайте лестницу, закройте окно - освещение никто не изменит, поскольку его очень долго вычислять на базе современных алгоритмов рисования треугольников с помощью z-буфера. Доказывать тут нечего: если бы было легко, это давно бысделали, благо акселераторы уже весьма мощные. Источник света даже подвигать нельзя - как в таком доме жить?
Подойдём к проблеме с другой стороны. Уровень, вместе со всей предварительно просчитанной информацией, занимает весьма нехило - мегабайты. А если уровни нужно очень часто подгружать в многопользовательской игре по интернет?
Что?
Я решил создать графический движок, удовлетворяющий следующим требованиям: нет никакой предварительной обработки сцены, положение и количество источников света и объектов может меняться произвольным образом в любое время. То есть, каждый кадр рисуется как бы новая сцена. Это должно позволить создавать новые оригинальные игры и расширить известные жанры.
Ничто не даётся задаром, всегда приходится чем-то жертвовать. Я пожертвовал представлением объектов посредством треугольников. В качестве базовых примитивов были выбраны сферы. То есть, объекты будут представляться не совокупностью треугольников, а совокупностью сфер.
Ясное дело, что как из треугольников, так и из сфер можно составить любой объект. Вопрос стоит лишь в количестве необходимых примитивов. Надо стараться обойтись как можно меньшим, иначе производительность упадёт ниже нижнего.
Почему в качестве примитивных элементов выбраны именно сферы, а в качестве метода - метод трассировки лучей? Дело в том, что при полигональном представлении объектов, треугольниками, например, очень много труда уходит на рассчет тени от объекта. Существуют разные методы - см. статью "Обзор алгоритмов построения теней в реальном времени". Они либо неявно требуют предварительную информацию об объекте, как метод теневых объёмов - иначе этот метод будет страшно долго работать на сложных объектах, либо требуют многократной отрисовки объекта (в текстуру) и нещадно эксплуатируют видео-ускоритель, как методы наложения теней с помощью проективных текстур. Отмечу ещё один их существенный недостаток, который не очень заметен в различных демонстрационных программах: если объект отбрасывает тень на удалённый предмет, то тень от него будет очень угловатой. Чтобы этого не случилось, объект необходимо отрисовывать в теневую текстуру с гигантским разрешением.
к статье о трассировке лучей
Shadowcast - демонстрационная программа от NVidia. Не самая новая, GF3 не требует.
Видимо, не случайно затеняемая площадка мала. Но всё равно заметно, как с увеличением расстояния от объекта до тени, тень огрубляется.
Далее, возникают проблемы с самозатенением объекта: когда объект отбрасывает тень сам на себя, а не на отделённый от него предмет. Эти проблемы носят на самом деле фундаментальный характер, в том смысле, что они органически присущи методу визуализации посредством отрисовки треугольников и применения z-буфера.
Рассчитывать тень от сферических объектов легко, рисовать сферы методом трассировки лучей тоже относительно легко - это и определило мой выбор.
Скорость трассировки лучей
Одним из свойств алгоритмов трассировки лучей заключается в большой зависимости скорости работы от разрешения экрана. Типичная формула времени работы выглядит таким образом: c1*n*ln(n)+c2*n*n+c3*ScreenWidth*ScreenHeight. c1, c2, с3 - некоторые константы, n-количество объектов на сцене. В первую очередь, рассмотрим главный член - c2*n*n, имеющий второй порядок по количеству объектов на сцене. Его происхождение просто: это время расчёта теней. Как ни крути, в этом вопросе от квадратичной зависимости далеко не уйти. Различные методы оптимизации, кластеризация объектов и т.п., в общем случае позволяют лишь уменьшить константу c2, не более. Этот член жестко лимитирует количество объектов на сцене. Начиная с некоторого момента, незначительное увеличение числа объектов вызывает очень большое падение производительности.
Влияние первого члена на общее время работы не очень существенно. Таким образом, когда сцена заполнена объектами в наибольшем возможном количестве, на первое место выходит последний член, зависящий от разрешения экрана. Эта величина отражает скорость собственно трассировки лучей, соответствующих точкам экрана. Это константа, но гигантская! Гигантская благодаря большой величине площади экрана в пикселях. Например, 800*600=480000, 1024*768=786432. Для современных процессоров получается всего около 100 тактов на обработку луча при частоте кадров около 25.
Некоторое недоумение вызывает независимость c3 от количества объектов. Дело в том, что анализ сцены перед запуском цикла трассировки позволяет существенно оптимизировать расчёты в самом цикле. За счёт этого, сколько бы ни было объектов на сцене, будет искаться пересечение луча с фиксированным количеством объектов. В принципе, с3 зависит от n, но этой зависимостью можно пренебречь.
Одним из главных последствий существования этой константы стала невозможность осуществления трассировки лучей в реальном времени на старых персональных компьютерах, оснащённых процессорами PentiumII и ниже. Эта константа даже на маленьких разрешениях - 400х300 - полностью съедала всю мощность процессора. Но сейчас этот барьер пройден! Производительности новейших процессоров для персональных компьютеров хватает для осуществления трассировки лучей в высоких разрешениях.
Далее я приступаю к описанию созданного мною графического движка VirtualRay, умеющего рисовать только объекты из сфер, зато позволяющего радикально изменять сцену в реальном времени.
Движок VirtualRay
Рабочими разрешениями движка VirtualRay на процессорах Pentium III с SSE являются разрешения 640x480 и 800x600 с глубиной цвета 32бит, то есть, движок работает в true color.
Естественно, очень много произвольно расположенных сфер отрисовывать не получилось. С приемлемой скоростью рисуются сцены, состоящие из нескольких тысяч сфер. Соответственно, движок хорошо рисует те объекты, для которых представление сферами легко возможно. Например, космос: планеты, звёзды, космические корабли и космические станции. Чудовищ, инопланетян, иномирян и их жилища. Технические объекты. Символы, абстрактные создания и сюрреалистические миры.
Поддерживается наложение и билинейная фильтрация текстур, что обеспечивает качественное изображение.
В угоду быстродействию выбрана простейшая модель освещённости, все источники света считаются точечными.
Возможна прозрачность сфер, причём коэффициенты прозрачности могут динамически меняться, и могут быть различными для каждого цветового канала.
Источника света также могут быть цветными.
Движок может работать в произвольном разрешении, как 320x240 и ниже, так и 1600x1200 и выше. Весь вопрос в скорости работы.
Более описывать нет смысла, как говорится, лучше один раз увидеть, чем сто раз услышать. На сайте www.virtualray.ru, находится текущая демо-версия движка и скриншоты. Ввиду моих низких художественных и моделлерских способностей создать высокоэстетичную демо-версию со стильными текстурами не очень получилось, получилось - технологическую демо-программу. Однако, её можно использовать в качестве игрушечного строительного конструктора из шаров.
Для ознакомления с демкой требуется компьютер с процессором PentiumMMX и выше и видео-карточка, поддерживающая true color в 32-битном формате. (совместимости с Intel 740 нет, так как там true color только в формате 24 бита. Но практически все современные карточки поддерживают необходимый формат). Вот ссылка www.virtualray.ru/demo/demo.zip. Одно замечание: иногда формат представления цвета в видеокарте определяется неправильно и, например, небо получается желтым вместо голубого. В этом случае рекомендуется угадать и выбрать в меню более подходящий формат. Так как на больших мониторах низкие разрешения выглядят слишком зернисто, для повышения быстродействия вместо уменьшения разрешения лучше слегка уменьшить площадь экрана.
Ниже я приведу несколько скриншотов из демо-версии. Они весьма неполно передают возможности движка, так как одним из его достоинств является динамическая игра света и тени, непередаваемая статическим изображением.
к статье о трассировке лучей
Производительность
Частота кадров - показатель, на который обращают внимание в первую очередь. Мы ещё коснёмся производительности движка на различных системах, сейчас же рассмотрим показатели на системе на базе PentiumIII800EB. Отмечу, так как движок не использует видео-ускорители, его производительность практически полностью определяется мощностью процессора.
Типичная частота кадров - 20 в разрешении 800x600x32 (800x450x32). Вроде бы совсем не впечатляет на сегодняшний день. Однако, FPS движка обладает двумя очень полезными свойствами, которые отчасти компенсируют её относительно небольшую величину. Первое свойство заключается в близости минимального и среднего FPS. Среднее FPS может быть 25, а минимальное - 22. А минимальное FPS, это даже более важный параметр, чем среднее. Во многих играх когда ходишь - частота кадров около 50, а только начнётся стрельба, враги появятся, FPS сразу упадёт вдвоё и больше.
Второе важное свойство - стабильность частоты кадров. Что это такое? Допустим, есть 50 кадров в секунду. Вроде бы, много. По идее, каждый кадр отрисовывается за 20 миллисекунд. Но в реальности некоторые кадры могут рендерится значительно дольше 20 миллисекунд, а другие - соответственно быстрее. В частности, такое может быть из-за необходимости периодически кэшировать данные, например, при повороте камеры. В результате, при формально высоком среднем FPS движение может не быть плавным. Движок VirtualRay рисует кадры независимо и демонстрируемый FPS реалистичен.
В общем, для чемпионата профессиональных квакеров не подойдёт, но играть вполне возможно. Особенно в игры, жанр которых не требует исключительно стрельбы.
Хочу также отметить, что не все оптимизирующие алгоритмы проверены, не все оптимизирующие алгоритмы придуманы. Я надеюсь, что ещё удастся увеличить скорость работы движка.
Устройство Сферического движка
Сферический движок почти полностью основан на алгоритмах, хорошо известных в компьютерной графике и многократно и детально описанных в книжках, посвящённых методу трассировки лучей. Мне практически не пришлось придумывать оригинальные алгоритмы, только адаптировать известные к сферам и real-time. Я отсылаю заинтересованного читателя, например, к книжке Е.В. Шикина, А.В. Борескова "Компьютерная графика. Динамика, реалистические изображения" Москва.: "Диалог-МИФИ". В интернете можно найти достаточно примеров из этой книжки. Видимо, где-то есть и текст. Если же у вас нет трудностей при чтении английских текстов, то просто море информации о трассировке лучей к вашим услугам в англоязычном интернете. Правда, я в большей степени основывался на знаниях из учебника по аналитической геометрии.
Рассмотрим принципиальную схему работы движка. Engine разбит на две существенно различающиеся части: в первой части осуществляется предварительный анализ сцены, вторая часть - двойной цикл трассировки лучей, отвечающих точкам экрана.
На входе движок получает описание сцены: положение и свойства сфер, расположение и параметры источников света. Эти данные попадают в блок первичного анализа - первую часть блока предварительного анализа сцены. В нём происходит отсечение не попавших в кадр сфер и источников света, зоны действия которых не видны. Происходит приведение координат объектов относительно положения наблюдателя, рассчитываются часто используемые далее величины, вроде расстояний до сфер.
Далее начинает работу блок распределения сфер по областям экрана. Экран разбивается на много прямоугольных областей, для каждой из которых вычисляется массив потенциально видимых сфер. То есть тех сфер, с которыми могут пересечься лучи, отвечающие точкам экрана, составляющим данную область.
Путём измельчения областей можно добиться, что бы почти на любую область приходилось всего несколько сфер, что сильно снижает затраты в гигантском цикле трассировки лучей.
Затем осуществляется расчёт отношения затенённости. Для каждой сферы определяется, сколько источников света её освещают. Если их много, то выбираются несколько, вносящие основной вклад в освещённость.
Для каждой сферы находятся все сферы, затеняющие её. Это несложно сделать благодаря простоте геометрической формы сферы. Теперь, когда затенители определены, точка сферы в цикле трассировки проверяется на затенение лишь ограниченным кругом сфер. Информация о затеняющих сферах, как то относительное положение и расстояние, упаковывается в оптимальный для вычислений при помощи SSE. Подробно об оптимизации под SSE - позднее.
Всё, можно запускать цикл трассировки.
Замечание к реализации. Первая часть, реализующая сложные и разнообразные алгоритмы, целиком написана на языке C++. Вторая часть, исходный код которой значительно меньше в размере, полностью написана на ассемблере и имеет три варианта, написанные для различных процессоров. Варианты различаются набором используемых команд. Оптимально использование SSE, но возможна работа и на компьютерах без SSE, необходима только поддержка технологии MMX. Конечно, на стареньком Pentium166MMX программа будет работать в режиме слайд-шоу, но в маленьком окошке можно посмотреть.
Набор команд Процессоры
SSE + Enhanced MMX - Pentium III, Pentium4, Celeron II, AthlonXP
FPU + Enhanced MMX - Athlon, Duron, (K6-III, K6-2+)
FPU + MMX - Pentium MMX, Pentium II, Celeron, K6-2
Отмечу, что для работы с вещественными числами используется SSE/FPU, для работы с целыми числами и числами с фиксированной точкой используется MMX. Обычные регистры (eax, ebx, ecx, edx, esi, edi) используются для хранения и вычисления адресов и флагов.
Программа откомпилирована при помощи IntelC++Compiler4.5, встроенного в Microsoft Visual C++ 6.0.
Области применения Сферического движка
Где можно использовать столь необычный движок, очень хорошо делающий одно и крайне плохо другое? Область применения сферического движка можно разделить на две части: использование в компьютерных играх и применение в иных целях. Начнём с не совсем игровых приложений.
Очевидно узкоспециальное приложение к визуализации моделей молекул и атомов. Правда, тени там выглядят неуместными: атом ведь не шарик. Описание шара занимает даже меньше места, чем описание треугольника, а шар всё-таки более богатая фигура. Это наталкивает на мысль о применении движка в интернете. Можно рисовать и легко пересылать эмблемы, логотипы, символические анимированные сценки. Для этих целей производительности движка вполне хватит - это же не на полный экран выводить сцену с большой частотой кадров. Плюс - практически полная независимость от видео-карточки: не нужно возится с драйверами, не нужно тестировать на миллионе конфигураций, не нужно обращать внимание на поддержку операционной системой графических библиотек. Есть ли DirectX, какая версия OpenGL - все эти вопросы особой роли не играют. Обеспечивается идентичность изображения у всех пользователей, с точностью до монитора, конечно. Это не так, как у видео-ускорителей: один поддерживает одно, другой - другое. На одном тени видны, на другом - нет, на третьем видны, но жутко тормозят.
Плавно перейдём в другую область применения движка. Онлайновые игры через интернет - вот где замечательно проявляются достоинства сферического движка. Как хорошо в многопользовательских играх дать возможность участникам в полном 3D в режиме реального времени строить и разрушать игровой уровень по своему усмотрению! И относительная низость FPS не так важна - всё равно связь мешает точному прицеливанию. Да и суть многопользовательской игры не всегда полностью состоит из одной стрельбы.
Игровую вселенную можно разбить на анклавы, представленные автономными сценам, между ними организовать какие-нибудь гиперпереходы. При перемещении новая сцена будет грузиться мгновенно.
Космические симуляторы любых видов - ещё одно поле приложения движка VirtualRay. Планетные системы, астероидные поля, космические аппараты - всё это прекрасно изображается при помощи сфер. Можно составить этакую "Звезду Смерти" и взорвать её при необходимости.
Игры аркадного толка также вполне могут базироваться на Сферическом движке.
Возможны приложения в играх экзотических жанров. Например, в играх, основанных на конструировании механизмов или создании живых существ.
Заключение
Пути развития неисповедимы. Трудно заранее определённо сказать о перспективах той или иной технологии. Несомненна некоторая научная ценность движка VirtualRay. Однако, найдётся ли ему практическое применение в какой-либо области, покажет время. Быть может, некоторые идеи, заложенные в движок, продолжат своё развитие и найдут своё воплощение в совершенно иной форме.
взято с сайта ixbt.com
Опубликовано -- 25 ноября 2001 года
обсуждать здесь https://forums.overclockers.ru/viewtopic.php?t=267387
Лента материалов
Правила размещения комментариев
Соблюдение Правил конференции строго обязательно!
Флуд, флейм и оффтоп преследуются по всей строгости закона!
Комментарии, содержащие оскорбления, нецензурные выражения (в т.ч. замаскированный мат), экстремистские высказывания, рекламу и спам, удаляются независимо от содержимого, а к их авторам могут применяться меры вплоть до запрета написания комментариев и, в случае написания комментария через социальные сети, жалобы в администрацию данной сети.
Сейчас обсуждают