значально этот алгоритм разрабатывался для решения проблемы удаления невидимых поверхностей. Трассировка лучей создает образ, исходя из тех же законов, что и наше зрение. Есть несколько объектов: источник света, наблюдатель и план наблюдения.Чтобы воспользоваться трассировкой лучей для создания натуральных образов, нам придется использовать миллиарды световых лучей из источника света, а затем рассматривать каждый из них, надеясь, что он попадет в план наблюдения и примет участие в создании образа. Возникает вопрос - а зачем трассировать каждый возможный луч? На самом деле, нас интересуют только те лучи, которые достигают плана просмотра. Что же будет, если трассировать лучи в обратном направлении? Проследим движение лучей для каждого из пикселей на экране, а затем посмотрим, где эти лучи пересекаются с планом просмотра. Отметив пересечение, мы останавливаемся и окрашиваем соответствующий пиксель в нужный цвет. Это называется первичной трассировкой лучей.Данная техника позволяет создавать трехмерные образы, но при этом не видны такие эффекты, как тени, рефракция и рефлексия. Чтобы воссоздать перечисленные эффекты, мы должны принять в рассмотрение специальные вторичные лучи, которыеисходят из точек пересечения. Это все делается рекурсивно до достижения некоторого уровня детализации. Затем полученные по всем лучам результаты складываются, и соответствующему пикселю присваивается вычисленный цвет.Трассировка лучей - это один из наиболее насыщенных вычислениями методов расчета трехмерных изображений, но зато и результаты получаются впечатляющими. Есть, правда, и одна проблема: для решения этой задачи в реальном времени не хватаетмощности даже самого быстродействующего компьютера. Потому нам придется учесть данное обстоятельство и применить идею трассировки лучей для создания другого метода. Он будет более ограничен, но позволит нормально работать с трехмерными мирами на обычном ПК. Исходя из этого, был реализован упрощенный вариант трассировки лучей, использующий только первичные лучи для генерации изображения. С последующими оптимизациями возможно достижение производительности для рендеринга изображения в режиме реального времени.Краткое описание упрощенного алгоритма.Освещение создаётся при помощи точечного источника. При рендеринге в режиме "без освещения" все объекты считаются освещёнными и теней не отбрасывают.В случае рендеринга с освещением для каждой прорисовываемой точки выполняется процедура расчета освещения её источником света. Сначала проверяется наличие, пересечения луча из точки в источник света с любым другим объектом из сцены. Если такое пересечение было найдено, то точка не освещена данным источником. Иначе, точка получает прирост освещённости по цвету и интенсивности, зависящий от источника и угла между отрезком и нормалью к треугольнику, которому принадлежит рассматриваемая точка (см. рис.1). Таким образом, создаются тени - области без дополнительного освещения. Для усиления теней рекомендуется выбирать в качестве базовых цветов модели тёмные оттенки, а для источников освещения - более яркие.Рис. 3. Освещенность точки.P - рассматриваемая точкаN - нормаль к поверхностиZ - вектор, ведущий от рассматриваемой точки к источнику освещения.Обоснование выбора алгоритма.Алгоритм трассировки лучей позволяет получить наиболее реалистичные изображения объектов сцены. Одним из свойств алгоритмов трассировки лучей заключается в большой зависимости скорости работы от разрешения экрана. Одним из главных последствий существования этой зависимости стала невозможность осуществления трассировки лучей в реальном времени на старых персональных компьютерах, оснащённых процессорами PentiumII и ниже. Эта константа даже на маленьких разрешениях - 400х300 - полностью съедала всю мощность процессора. Но сейчас этот барьер пройден. [3] Для обеспечения резкого ускорения скорости работы алгоритма необходимо использовать специальные библиотеки арифметических вычислений, оптимизированные под команды SSE. Например, уже достаточно давно доступна библиотека Small Matrix Library от компании Intel. В ней реализован класс матрица и класс вектор. По данным iXBT [3] время выполнения вычислений с учетом использования данной библиотеки на PIII 800EB выглядит следующим образом:|
Операция | SSE/FPU | Время выполнения (в тактах процессора) | | 3x3 * 3x1 | FPU | 31 | | 3x3 * 3x1 | SSE | 29 | | Transpose (3x3) * 3x1 | SSE | 23 | | 4x4 * 4x1 | FPU | 53 | | 4x4 * 4x1 | SSE | 31 | | Transpose (4x4) * 4x1 | SSE | 27 | | 3x3 * 3x3 | FPU | 79 | | 3x3 * 3x3 | SSE | 59 | | 4x4 * 4x4 | FPU | 172 | | 4x4 * 4x4 | SSE | 90 | | 6x6 * 6x1 | FPU | 113 | | 6x6 * 6x1 | SSE | 60 | | 6x6 * 6x6 | FPU | 652 | | 6x6 * 6x6 | SSE | 307 | | 4x4 * 4x4 (general case) | SSE | 529 | | Inverse 4x4 | FPU | 392 | | Inverse 4x4 | SSE | 209 | | Inverse 6x6 | FPU | 1118 | | Inverse 6x6 | SSE | 600 | | |
Ускорение получается до двух раз и даже больше. Результаты реализации без применения оптимизированных библиотек так же подчеркивают архитектурные особенности современных компонентов компьютеров, о чем будет сказано позднее. Таким образом, алгоритм трассировки лучей на текущий момент позволяет получить наиболее качественный расчет освещения в сочетании с достаточной скоростью при использовании оптимизированных под SSE библиотек, что и должно явиться следующим этапом развития программного продукта. 1.1.4 Схема выбранной последовательности преобразованийВ результате проведения анализа алгоритмов была выбрана следующая последовательность проведения преобразований:27 1.2 Объекты сцены1.2.1 Источник освещенияВ связи со спецификой требований к программному продукту, т.е. необходимости реализации естественного (Солнечного) освящения. Источник освещения сцены мы считаем точечным и удалённым от прорисовываемых объектов.Поэтому, источник задаётся двумя углами (азимутальным и зенитным), а также цветом.1.2.2 Прорисовываемые объектыКаждому прорисовываемый объекту в программе назначены следующие глобальные параметры: имя (не изменяется), координаты в пространстве, собственный угол азимутального поворота, цвет, пункт назначения.Каждый объект загружается из файла в виде списка треугольников, либо четырехугольников. Треугольник, выбранный в данной программе единицей аппроксимации, задаётся в виде трёх вершин.Задача нахождения пересечения треугольника и отрезка разбита на несколько этапов:нахождение точки пересечения прямой, содержащей отрезок, и плоскости, содержащий треугольник.проверка принадлежности найденной точки отрезку.проверка на принадлежность этой точки треугольнику.Если все проверки дали положительный результат, то считаем, что пересечение имеется (его координаты при этом являются избыточными итоговыми данными). 2. Технологическая часть2.1 Выбор языка программирования и среды разработкиВ качестве языка реализации программного комплекса был выбран Object Pascal, а средой разработки - Delphi 7. При данном выборе учитывались следующие моменты:Поддержка объектно-ориентированного программирования, что облегчает создание сложных систем.Предоставление средств визуального программирования для создания удобного интерфейса.Обеспечение необходимой функциональности и читаемость кода программы.Delphi был выбран оптимальной средой реализации как наиболее широко используемый и полнофункциональный компилятор на основе языка Pascal.2.2 Структуры данных2.2.1 Структура программного комплексаНа рисунке 2 представлена схема взаимодействия классов программы, на которой отображены основные вызовы. Стрелками с кружочком показаны включения методов в классы, а обычными стрелками - их вызовы.27 Рис. 4 Структура программы2.2.2 Класс объектаКласс объекта хранит следующие данные о нём:Точка "Центра объекта" - некоторая точка, перемещаемая при изменении координат объекта. Все координаты вершин вычисляются относительно этой точки.Точка "Место назначения" - точка, необходимая для указания места назначения при движении объекта.Цвет объекта - как и все цвета в программе задаётся в формате RGB.Собственный угол поворота объекта.Список треугольников, составляющих объект.Также класс объекта предоставляет следующие методы:Прорисовка. Выполняется прорисовка изображения в Bitmap и запись данных о глубине в массив Z-величин.Прорисовка с освещением. Производятся вычисления аналогичные прорисовки, но используется дифференциальное освещение.Загрузка из файла. Производится чтений фигуры из файла установленного стандарта.Поворот. Фигура поворачивается на заданные зенитные и азимутальные углы. Все повороты производятся относительно "Центра объекта".Масштабирование. Расчет производится относительно "Центра объекта".Поворот при перемещении. Производится расчет угла между текущим направлением объекта и направлением к точке "Место назначения". В случае необходимости происходит изменение угла с учетом заданной скорости поворота объекта.Перемещение. Производится расчет следующего местоположения на пути к точке "Место назначения" с учетом скорости объекта. Результат присваивается точке "Центра объекта".2.2.3 Интерфейсный классНа уровне методов формы реализованы:Расчет сцены. Внутри этого метода производится выбор способа расчета (с освещением, или без) в зависимости от настроек.Очистка экрана. Очищается экран изображения и Z-буфер.Масштабирование всех объектов с заданным коэффициентом.2.2.4 Структуры данныхВ виде глобальных переменных хранятся:Массив объектов, включает в себя всё объекты. Динамический массив, изменяется каждый раз, когда мы создаём новый объект.Источник освещения.Данные о необходимом количестве просчитываемых кадров.Сведения о скорости работы программы, необходимые для тестирования скоростных показателей программы.Данные о полигонах в объектах хранятся в виде односвязных списков полигонов. Каждый полигон - набор из трех вершин.2.2.5 Независимые процедурыЗаданы следующие независимые процедуры:Проверка видимости. Проверяет пересечение отрезка с любым объектом сцены. Применяется при учёте освещения.Скалярное произведение векторов.Векторное произведение векторов.Нахождение угла между векторами.Нахождение третьей координаты точки на треугольнике по её проекции на плоскость экрана.Преобразование строки заданного формата ввода в треугольник.Вычисление цвета от затенения.Вычисление цвета от освещения. 3. Использование системы3.1 Системные требованияпрограмму добавлена интеллектуальная функция тестирования, которая определяет оптимальные параметры и дает рекомендации по работе с программой. Минимальная конфигурация для работы программы должна отвечать требованиям установки Windows XP.3.2 Работа с программой3.2.1 Общие сведеньяИнтерфейс программы создавался в расчете на быстрое обучение человека, который никогда ранее не работал с подобными продуктами. Все кнопки объединены в группы элементов. Выделено 3 основные группы: Объекты, Сцена, Освещение. Каждая из групп включает в себя элементы, выполняющие возможные над объектами действия. Конечно, в соответствии с современными стандартами, добавлено выпадающее меню и интерфейс в стиле Windows XP. При выделении объекта, посредством клика на таблице, он перекрашивается в зеленый цвет.Общий вид окна программы 3.2.2 Панель "Объекты"Вид панели "Объекты"При выборе объекта, посредством клика на таблице, поля координат принимают текущие значения для данного объекта, а он выделяется зеленым цветом в отображаемой сцене. Кнопки перемещения позволяют перемещать объект без ввода новых координат. Если же возникла необходимость переместить объект в заданную точку, то необходимо его выделить в таблице и, задав свойства, нажать кнопку "Применить". Если указать точку назначения ("Путь"), то после запуска циклического рендеринга кадров, объект начнет движение в заданном направлении. Кнопка "Загрузить" служит для загрузки объекта из файла. "Удалить" - удаляет выбранный в таблице объект. "-> bmp" - делает снимок экрана. 3.2.3 Панель "Сцена"Вид панели "Сцена"Позволяет осуществлять поворот, сдвиг сцены и настраивать масштабирование изображения. Кнопка "Рендеринг" выполняет просчет текущего изображения. "Видео" - запускает анимацию объектов в квазиреальном времени. Функция "Видео - > bmp" сделана специально для обладателей недостаточно мощных компьютеров, либо для записи и последующего отложенного воспроизведения видеороликов. Кнопка "Просмотр" позволяет просмотреть ранее записанное видео.3.2.4 Панель "Сцена" и выпадающее менюВид панели "Освещение"Позволяет включать обработку сцены с условием освещения, перемещать источник освещения в пространстве и выбирать цвет источника. В выпадающем меню дублируются функции с панелей, помимо функции тестирования и выхода. 3.3 Анализ результатов тестированияВходе тестирования программного продукта на разных системах с использованием встроенного бенчмарка были получены следующие результаты: |
Процессор | Режим без теней | Итоговый результат | | AMD Athlon XP 2000+ (1.6 Ghz) | Отлично | 4161 | | P4 Northwood 2.6 GHz | Отлично | 3277 | | AMD Athlon 64 3000+ 939 (1.8Ghz) | Отлично | 5677 | | PIII 733Mhz | Недостаточна | 1628 | | P4 Prescott 3.0 GHz | Отлично | 2697 | | Core 2 Duo E4500 (2.2Ghz) | Отлично | 4500 | | Core 2 Duo E4400@ (3.29Ghz) | Отлично | 7700 | | AMD Turion TL-52 (1.8 Ghz) | Отлично | 4100 | | |
Из сводной таблицы, что программа ощутимо быстрее выполняется на процессорах фирмы AMD. В чем же причина? В процессорах от AMD традиционно, начиная с архитектуры K7, применяется очень быстрый блок вычислений с плавающей точкой. (FPU) [4] [5] Поэтому мы видим, что Athlon XP 2000+, который вышел на рынок в 2002 работает почти на равнее с современным процессором от Intel - Core 2 Duo E4400 и в 1.5 раза обгоняет P4 3.0Ghz на ядре Prescott. Интересна разница между P4 Northwood 2.6 GHz и P4 Prescott 3.0 GHz. Известно, что в ядро Prescott могло обеспечить ускорение в операциях с плавающей запятой при сравнении с Northwood только при использовании оптимизированных под SSE3 компиляторов, что ярко и отображается на результатах. Второй вывод, который можно сделать - программа очень сильно зависит от скорости работы с памятью. Этого стоило ожидать при выборе алгоритма Z - буфера. Так AMD Athlon 64 3000+ 939 (1.8Ghz) становится вторым по скорости работы после разогнанного Core 2 Duo E4400@ (3.29Ghz). Причина - интегрированный контроллер памяти, работающий в двухканальном режиме, который позволяет значительно снизить задержки при обращении к памяти и увеличить скорость обмена данными. [4] Однако, мы видим, что Turion TL-52 достаточно сильно проигрывает настольному одночастотному коллеге. TL-52 использует память типа DDRII 633, которая обладает в два и более раза большими задержками, в сравнении с DDRI 400 и одноканальный режим работы. Однако, DDRII позволяет увеличить производительность, но при работе на достаточно больших частотах. Разгон E4400 на 62% позволил превзойти процессор с изначальной частотой на 200Mhz большей на 71%. Однако, причина такого прироста не только в росте частоты процессора. Шина процессора была разогнана на 80%, а память работает на частоте в 864Mhz. Мы видим реальный существенный рост скорости работы программы при увеличении скорости обмена данными с памятью, тогда как частота процессора влияет на результаты намного меньше. ВыводыВ работе реализованы базовые алгоритмы машинной графики: Z-буфер, трассировка лучей, алгоритм закраски флагом, взятый из курса двумерной графики. Поэтому, эта работа являет собой отчёт об усвоении курса Машинной Графики МГТУ им Н.Э. Баумана. Хотя достичь реального времени и не удалось, но примененные алгоритмы позволяют заметно ускорить выполнение программы путем перехода на использование современных программных библиотек, оптимизированных под выполнение с применением поддерживаемых наборов инструкций процессора, например SSE. В ходе проведения тестирования так же были получены и подтверждены важные знания по архитектурам современных настольных систем. Стало очевидно, почему при аппаратной реализации алгоритм Z-буфера будет выполняться намного быстрее остальных. Программа может применяться как для моделирования перемещений группировок морских кораблей, так и в учебных целях, для наглядного демонстрирования зависимости скорости выполнения расчетов от выбранных методов и архитектуры аппаратной составляющей демонстрационного стенда. ЛитератураД. Роджерс, Дж. Адамс. Математические основы машинной графики. - М: изд-во "Мир", 2001. - 277с. С.М. Авдеева, А.В. Куров. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ ПО ДИСЦИПЛИНЕ "МАШИННАЯ ГРАФИКА" Москва 1995 Сайт "iXBT" [эл. ресурс]. - режим доступа http://www.ixbt.com/video/rt-raytracing. shtml Сайт "iXBT" [эл. ресурс]. - режим доступа http://www.ixbt.com/cpu/amd-hammer-family2. shtml Сайт "Ф-центр" [эл. ресурс]. - режим доступа http://www.fcenter.ru/online. shtml? articles/hardware/processors/5847
Страницы: 1, 2
|
