Разработка модели преломляющих и отражающих объектов

Разработка модели преломляющих и отражающих объектов

Курсовая работа по курсу: «Машинная графика»

«Разработка модели преломляющих и отражающих объектов»

Москва 2012г.

Техническое задание

Основание для разработки - курсовая работа по курсу «Машинная графика».

Цель разработки - разработка модели прозрачных и отражающих объектов с использованием алгоритмов машинной графики.

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

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

Функциональные характеристики:

.        Перемещение камеры.

.        Наличие теней.

.        Наличие объекта с преломлением.

.        Наличие объекта с отражением.

.        Возможность оценки временных характеристик.

Содержание

1. Введение

.1 Алгоритм прямой трассировки лучей

.2 Алгоритм излучательности

.3 Алгоритм обратной трассировки лучей

. Конструкторская часть

.1 Поиск отражённого луча

.2 Поиск преломлённого луча

.3 Освещение и тени

.4 Алгоритм

.5 Вычисление нормалей

.5.1 Вычисление нормали к полигону

.5.2 Вычисление нормали к сфере в заданной точке

.6 Поиск пересечения с объектами

.6.1 Поиск пересечения с полигоном

.6.2 Поиск пересечения со сферой

. Технологическая часть

.1 Выбор языка программирования

.2 Структура программы

.2.1 Список модулей программы

.2.2 Структуры и классы программы

.3 Описание интерфейса программы

. Исследовательская часть

Заключение

Литература

1. Введение

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

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

.1 Алгоритм прямой трассировки лучей

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

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

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

.2 Алгоритм излучательности

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

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

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

.3 Алгоритм обратной трассировки лучей

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

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

А) Источники освещения могут только испускать лучи, но не могут отражать, поглощать и преломлять. В данной работе используются точечные источники освещения. Они излучают свет равномерно во все стороны.

Б) Для объектов со свойствами преломления не учитывается зависимость коэффициента преломления от длины волны.

В) Вводится максимальный уровень глубины рекурсии трассировки.

Эта работа посвящена методу обратной трассировки лучей.

2. Конструкторская часть

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

.1 Поиск отражённого луча

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

Будем считать, что задан радиус-вектор S, направленный на источник света, а также известен радиус-вектор нормали N. Требуется найти вектор отражённого луча. Обозначим его R.

Отражение луча

Рис. 2.1

Рассмотрим единичные вектора R₁ и N₁. Поскольку векторы нормали, падающего луча и отражённого луча находятся в одной плоскости, то можно записать ₁+S₁=N`,

где N` - это вектор, соответствующий диагонали ромба и совпадающий по направлению с нормалью. Длина вектора N` равна 2 cos.

Так как вектор N` по направлению совпадает с N₁, то

` = N₁2 cos,

Отсюда найдём единичный вектор отражённого луча:₁=N₁2 cos- S₁= N/|N|2 cos-S/|S|

Найдём cos, используя скалярное произведение векторов N и S:

 = N*S/(|N|*|S|)

Подставим это значение в выражение для R1:

₁ = N*2*N*S/(|N²|*|S|) - S/|S|

Полагая, что искомый вектор отражённого луча будет иметь такую же длину, что и вектор падающего луча, то есть R=|S|R₁, получим

= N*2*N*S/|N²|-S                  (2.1)

2.2 Поиск преломлённого луча

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

Пусть заданы два единичных вектор: S₁- это радиус-вектор, направленный на источник, и N₁ - радиус-вектор нормали к границе раздела двух сред. Также должны быть известны два коэффициента преломления для данных сред n₁ и n₂.

Преломление луча

Рис. 2.2

Требуется найти единичный радиус-вектор преломлённого луча T₁. Искомый вектор равен сумме двух векторов:

₁ = N_T+B

Найдём вначале вектор N_T. Он противоположен по направлению вектору нормали, а его длина равна |T₁|cosα₂ = cosα₂ (так как по условию задачи T₁ - единичный). Отсюда следует, что N_T = -N₁cosα₂

Необходимо найти cosα_2. Запишем закон преломления n₁sinα₁ = n₂sinα₂ в виде:

sinα₂ = nsinα₁,

где n = n₁/n₂.

Воспользуемся тождеством cos²+sin² = 1.

Тогда:

cosα₂ = √ 1 - sin²α₂ = √ 1 - n² sin²α₁

или

cosα₂ = √ (1 + n² (cos²α₁ - 1).

Значение cosα₁ можно выразить через скалярное произведение единичных векторов S₁ и N₁, то есть cosα₁ = S₁N₁. Тогда мы можем записать такое выражение для вектора N_T:

_T = -N₁√1+n²((S₁N₁)² - 1).

Осталось найти выражение для вектора B. Он располагается на одной прямой с вектором A, причем A = S₁ - N_S. Учитывая, что N_S равен N₁cosα₁, то:

= S₁ - N₁cosα₁.

Так как cosα₁ = S₁N₁, то= S₁ - N₁ (S₁N₁).

Поскольку длина вектора A равна sinα₁, а длина вектора B равна sinα₂, то

Откуда |B| = n|A|. Учитывая взаимное расположение векторов A и B, получим:

= -nA =n(N₁(S₁*N₁)-S₁)

Теперь мы можем записать искомое выражение для единичного вектора луча преломления T₁:

₁ = nN₁ (S₁N₁) - nS₁ - N₁√1 + n² ((S₁N₁)² - 1).               (2.2)

После определения направления отражённого или преломлённого луча происходит рекурсивный вызов функции трассировки для нового луча.

.3 Освещение и тени

В данной работе используется модель освещения Уиттеда.

Согласно модели Уиттеда цвет некоторой точки объекта определяется суммарной интенсивностью

(l)=Ka*Ia(l)C(l) + Kd*Id(l)*C(l) +Ks*Is(l) + Kr*Ir(l) +Kt*It(l),      (2.3)

где l - длина волны, C(l) - заданный исходный цвет точки объекта, Ka, Kd, Ks, Kr и Kt - коэффициенты, учитывающие свойства конкретного объекта параметрами фоновой подсветки, диффузного рассеивания, зеркальности, отражения и прозрачности.- интенсивность фоновой подсветки,- интенсивность, учитываемая для диффузного рассеивания, - интенсивность, учитываемая для зеркальности,- интенсивность излучения, пришедшая по отраженному лучу,- интенсивность излучения, пришедшая по преломленному лучу.

Интенсивность фоновой подсветки (Ia) для некоторого объекта обычно константа.

В данной работе диффузное рассеивание и фоновая подсветка не учитываются.

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

.4 Алгоритм

. Выбрать необработанный пиксел на элементе отображения(picturebox).

. Задать вектор направления взгляда.

. Вызвать функцию определения интенсивности пиксела.

. При превышении глубины рекурсии перейти на шаг 12.

. Ищем точку пересечения луча с ближайшим объектом.

. Точка найдена?

А) Нет - устанавливаем фоновую интенсивность пиксела. Перейти на шаг 12.

Б) Да - запоминаем с каким объектом было найдено пересечение.

. Перебираем все источники освещения и проверяем, лежит ли между объектом и источником другой объект.

А) Между точкой пересечения и источником освещения лежит другой объект - заносим нулевое значение в переменную “shade”.

Б) Точка пересечения не перекрывается от источника освещения ни одним из объектов - заносим в переменную “shade” значение «1».

. Если значение переменной “shade” больше нуля - вычисляем локальную интенсивность пиксела. Под «локальной» интенсивностью понимается интенсивность с учётом диффузно отражённого света.

. Если достигнута максимальная глубина рекурсии, то принять интенсивности отражённого и преломлённого света нулевыми. Перейти на шаг 12. Иначе перейти на следующий шаг.

. Если объект обладает свойствами зеркального отражения, то вычисляем вектор отражённого луча. Запуск рекурсии для нахождения интенсивности отражённого луча (переход на шаг 3).

. Если объект обладает свойствами преломления, то вычисляем вектор преломлённого луча. Запуск рекурсии для нахождения интенсивности преломлённого луча (переход на шаг 3).

. Возвращаемся в точку вызова функции определения интенсивности пиксела.

Если шёл расчёт первичного луча, то в буфер кадра помещаем пиксел вычисленного цвета. Если интенсивность превышает максимальную, то устанавливаем максимальную интенсивность. Переходим к следующему пикселу(шаг 1).

графика модель прозрачный отражающий

2.5 Вычисление нормалей

В данной работе присутствует два вида примитивов, используемых в построении сцены. Это полигон (треугольник) и эллипсоид.

.5.1 Вычисление нормали к полигону

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

Пусть задан треугольник ABC и мы знаем координаты всех его вершин.

_AB = X_B - X_AAB = X_B - X_AAB = X_B - X_A                                                                        (2.4)_AC = X_C - X_AAC = X_C - X_AAC = X_C - X_A

Найдём векторное произведение векторов: N = ABxAC

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

_n = Y_ABZ_AC - Y_ACZ_ABn = X_ABZ_AC - X_ACZ_AB                                                 (2.5)_n = X_ABY_AC - X_ACY_AB

.5.2 Вычисление нормали к сфере в заданной точке

Для вычисления нормали к точке на сфере, необходимо вычесть координаты

центра сферы, из координат точки поиска.

= Px - Ox,= Py - Oy,= Pz - Oz,

где N - вектор нормали, P - точка к которой надо найти нормаль, O - центр сферы.

Полученный вектор необходимо нормализовать. Поделим вектор N на радиус сферы.

В итоге мы получим нормаль к сфере в заданной точке.

.6 Поиск пересечения с объектами

Важнейшей частью алгоритма обратной трассировки лучей является определение пересечения. Способ определения точки пересечения зависит от того, какой это объект, и каким образом он представлен. Для ускорения поиска пересечения рекомендуется использовать метод оболочек. Каждый объект полностью помещается в оболочку, нахождение пересечения с которой быстрее, чем с объектом. Например, в сферу. Если луч пересёк оболочку, то необязательно, что этот луч пересечёт и объект. Необходимо продолжить поиск пересечения луча с объектом.

Любая точка луча удовлетворяет уравнению:

= A+Vt,                                                                       (2.11)

где R- радиус-вектор произвольной точки, принадлежащей лучу, A - радиус-вектор начальной точки луча, V - вектор направления луча, t - параметр.

.6.1 Поиск пересечения с полигоном

Поиск пересечения с треугольником состоит из двух этапов: поиск пересечения луча с плоскостью треугольника и определение нахождения точки внутри него.

Запишем уравнение плоскости:

Q(x, y, z) = Ax + By + Cz +D = 0.                                        (2.12)

Коэффициенты A, B, C совпадают с координатами нормали к этой плоскости. Координаты нормали плоскости совпадают с координатами нормали треугольника. Нормаль треугольника была рассчитана при инициализации сцены.

Выразим свободный член D:

= -Ax -By - Cz                                                             (2.13)

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

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

Теперь для нахождения точки пересечения подставим уравнения луча (2.11) в

уравнение плоскости (2.12):

(x₁ + at) + B (y₁ + bt) + C (z₁ + ct) + D = 0                           (2.14)

Следовательно:

= - (Ax₁ + By₁ + Cz₁ + D) / (Aa + Bb + Cc)                          (2.15)

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

Иначе, для нахождения координат точки пересечения надо подставить найденное значение параметра t в уравнение луча (2.11). Назовем точку пересечения D. Мы получим координаты x_D, y_D, z_D.

Необходимо определить, попала ли точка D внутрь треугольника. Найдем координаты векторов AB, BC, CA и координаты векторов AD, BD, CD.

Определим три векторых произведения:

= AB x AD,= BC x BD,                                                        (2.16)= CA x CD.

Если все три вектора сонаправлены, то точка D лежит внутри треугольника.

Для проверки на сонаправленность, проверяет знаки соответствующих координат всех векторов.

Данный алгоритм может быть ускорен различными тестами. Одним из таких тесов является габаритный тест. Необходимо проверить лежит ли проекция точки D левее, правее, выше или ниже проекции каждой вершины треугольника. Если да, то точка D лежит снаружи.

.6.2 Поиск пересечения со сферой

Для нахождения точки пересечения луча, заданного уравнением

= A + Vt,                                                           (2.17)

которое можно записать в виде:

= x₁+at,= y₁+bt,                                                           (2.18)= z₁+ct

со сферой, заданной уравнением:

(x-x₀)²         +(y-y₀)²+(z-z₀)² = r²                                                      (2.19)        

нужно подставить в уравнение сферы вместо x, y и z соответствующие уравнения луча. После раскрытия всех скобок и приведения подобных мы получим квадратное уравнение относительно параметра t.

Если дискриминант квадратного уравнения меньше нуля, то луч и поверхность второго порядка общих точек пересечения не имеют. В противном случае можно будет вычислить два значения параметра t. Дискриминант может быть равен нулю - это соответствует предельному случаю касания луча поверхности, и мы получим два совпадающих значения параметра t.

Для нахождения координат точек пересечения луча и поверхности достаточно подставить найденные значения параметра t в уравнения луча (2.17).

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

Если одно или оба значения параметра t получились отрицательными, это означает, что точка пересечения лежит «сзади» относительно точки начала луча, на половине прямой, находящейся «по нашу сторону» относительно картинной плоскости. Такие точки при поиске пересечения отбрасываются.

3. Технологическая часть

.1 Выбор языка программирования

Для выполнения работы был выбран язык C++ в среде программирования Microsoft Visual Studio 2010 с использованием CLR.

Язык является наиболее гибким и эффективным для решения сложных задач.

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

Среда MSVS является одной из основных сред разработки на языки C. Обновления, техническая поддержка, надёжность и удобство работы - основные плюсы данного выбора.

.2 Структура программы

.2.1 Список модулей программы- файл формы главного окна. Содержит реализацию класса формы, методы для работы с интерфейсом.- содержит константы и вспомогательные структуры данных.- функции для работы с векторами.- содержит описание сцены, параметры заданной сцены, методы для добавления объектов, поиска пересечений, поиска нормалей.- содержит описание примитивов проекта, функции для работы с ними.- содержит основной алгоритм программы - «обратную трассировку лучей», функции для работы с типом «Луч», камеру и её методы.

3.2.2 Структуры и классы программыCol      - описывает цвет по трём составляющим (RGB).Cord - описывает координату в трёхмерном пространстве (x, y, z).vector3 - описывает вектор трёхмерного пространства и основные методы для работы с ним.Material - описывает материал объекта, его основные свойства и цвет.Light - используется для описания источников освещения. Содержит позицию источника и цвет излучения.Vertex - описывает вершину в трёхмерном пространстве.Primitive - базовый класс, хранит информацию о материале объекта и прототипы методов проверки на пересечения и поиски нормали.Trian - описывает полигон(треугольник). Потомок класса Primitive. Хранит три вершины и координаты нормали. Обладает собственными методами проверки на пересечение и поиска нормали.Sphere - описывает сферу. Потомок класса Primitive. Хранит координаты центра и радиус. Обладает собственными методами проверки на пересечение и поиска нормали.Scene - описывает сцену. Хранит количество примитивов, количество источников освещения, указатели на массивы вершин, примитивов и источников освещения.Engine - основной класс программы. Содержит методы трассировки лучей, поиска пересечения.Ray - описывает луч. Содержит текущее положение, направление. Методы доступа и изменения положения и направления.

3.3 Описание интерфейса программы

Основной вид программы:

Рис. 3.1

Главное меню программы имеет пункты:

Главное меню

Рис. 3.2

А) «О программе» - содержит информацию о разработчике.

Б) «Выход» - осуществляет завершение работы программы.

Основной интерфейс сосредоточен непосредственно на форме.

Рис. 3.3

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

Вкладка «Ручной ввод»:

Рис. 3.4

Позволяет нам быстрей перейти к нужным координатам. Для удобства пользователя выводятся текущие координаты. Кнопка «Рендеринг» - начинает генерацию нового кадра.

При нажатии на эту кнопку проверяются все введённые данные. В случае неправильного ввода выдаётся соответствующее предупреждение. Введены ограничения на значения координат. Это сделано для того, чтобы пользователь не ушёл за пределы сцены и не возникло ошибок переполнения.

Ниже холста(picturebox), на котором отображается изображение, располагается информация о времени генерации изображения:

Рис. 3.5

В самом низу окна расположен прогресс бар, отображающий текущий статус генерации изображения.

Рис. 3.6

4. Исследовательская часть

Исследование проводилось на компьютере с конфигурацией:Core i5-2400, 3.1 GHzRadeon HD 6900M Series

Gb RAM7 64x

Была исследована зависимость скорости генерации кадра от эффекта. Генерировался кадр со сферой и задним фоном. Свойства сферы менялись в каждом опыте, но её размер и положение оставались постоянными. В итоге было проведено четыре опыта:

О1 - опыт без использования отражения и преломления.

О2 - опыт с использованием отражения.

О3 - опыт с использованием преломления.

О4 - опыт с использованием преломления и отражения.

Без использования эффектов:       Отражение:

Рис. 4.1                         Рис. 4.2

Преломление:               Преломление и отражение:

Рис. 4.3                         Рис. 4.4

Каждый опыт повторялся несколько раз

Из результатов экспериментов следует, что использование обоих эффектов(преломления и отражения), замедляет генерацию кадра примерно в 2,5 раза.

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

Заключение

В ходе выполнения работы был успешно реализован алгоритм обратной трассировки лучей. Данный алгоритм позволил выполнить поставленную задачу. А именно: были построены объекты со свойствами преломления и отражения, было использовано наложение теней, была создана камера, позволяющая перемещаться и поворачиваться.

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

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

Литература

2.      Порев В.Н. «Компьютерная графика» - СПБ: издательство «БХВ-Петербург», 2002. - 432с.

.        Ламот А. «Программирование трёхмерных игр для Windows. Советы профессионалов по трёхмерной графике и растеризации» - М: издательский дом «Вильямс», 2004. - 1424с.