Реализация алгоритма обратной трассировки лучей для моделей с большим числом полигонов
Найдем вектор NT. Этот вектор противоположен по направлению вектору нормали, а длина его равна
.
Таким образом
.
Для того, что бы определить cosα2, запишем закон преломления
.
Воспользуемся тождеством
![]()
Получим
![]()
Значение для
cosα1
можно выразить
через скалярное
произведение
единичных
векторов S1
и N1
.
С учетом этого
можно записать
выражение для
вектора
NT:
![]()
Найдем вектор B. Он располагается на одной прямой с вектором A, причем
.
Найдем отношение длин векторов A и B:
.
Отсюда
![]()
.
Если подкоренное выражение отрицательно, то это соответствует полному внутреннему отражению. В этом случае преломленный луч создаваться не будет. Учтем то, что вектор S равен (0, 0,1).
![]()
![]()
![]()
2.4 Оболочки
В алгоритме трассировки лучей от 70 до 90 процентов временных затрат занимает процедура определения пересечений луча с объектами сцены. Если перебирать все объекты сцены, то время будет пропорционально Cn, где С - количество пикселей, а n - число объектов на сцене. Улучшить алгоритм можно, если каким-нибудь образом попробовать сократить число перебираемых объектов. Очень простой, но эффективной является идея иерархических оболочек. Предположим, что нам надо изобразить содержимое полки с посудой. Проведем мысленно большую сферу вокруг полки, так чтобы она включала и полку, и посуду на ней. Затем сферу вокруг каждого предмета посуды. Теперь представим себе процесс рендеринга. Проверяем, пересекается ли луч с самой большой сферой. Если нет, то это значит, что луч не пересекает внутренние оболочки, переходим к другому лучу. Если пересекает, то смотрим пересечение луча с подсферами данной сферы. Как видно из такого примера, многие лучи могут совершить всего одну проверку и отсеяться.
При построении оболочек необходимо, чтобы главная оболочка целиком включала все ее подоболочки, иначе не будет работать правило: "Если луч не пересекает главную оболочку, то он не пересекает и все ее подоболочки". Так же при построении оболочек желательно, чтобы оболочки, имеющие один порядок вложенности, пересекались по как можно меньшему объему. Это улучшит эффективность алгоритма. Метод оболочек помогает сделать время рендеринга пропорциональным Clog (n).
2.4.1 Алгоритм построения иерархических оболочек
Для начала строятся сферические оболочки вокруг всех треугольников сцены. Этим занимается процедура Obol1. Сферы выбираются таким образом, чтобы все точки треугольника лежали внутри сферы. Для построения оболочки вокруг треугольника процедура:
Находит минимальный параллелепипед, в котором находится весь треугольник.
Определяет середину параллелепипеда.
Находит расстояния от центра до каждой вершины треугольника, определяет максимальное среди них. Оно и будет являться радиусом нашей оболочки. А центром будет центр параллелепипеда.
Далее вызывается процедура Obol2. Она и занимается собственно построением иерархии. Процедура создает одну оболочку, в которую записывает номера всех треугольников, сцены и вызывает рекурсивную процедуру step с параметром 1. Это значит, что step обработает первую оболочку.
Процедура step:
Определяет центр и радиус сферы, которая включает в себя все треугольники данной оболочки.
Перемещаем мысленно систему координат в центр этой сферы. Создаем 8 оболочек, каждая оболочка отвечает за свой октант в перенесенной системе координат.
Распределяем треугольники рассматриваемой сферы, по этим 8 оболочкам (октантам) по принципу: если центр сферы вокруг треугольника лежит в октанте, то треугольник помещается в соответствующую оболочку.
Если какая-то оболочка оказалась пуста (т.е. если в нее не попал не один треугольник), то она уничтожается.
Устанавливается связь: в запись оболочки добавляются номера ее подоболочек.
Так же, в текущую оболочку записываем номера треугольников, радиус оболочки которых больше четверти радиуса текущей оболочки. Эти треугольники не должны заноситься ни в одну из подоболочек. В процессе обхода оболочек они должны обрабатываться отдельно.
Рекурсивно вызываем процедуру Step для каждой из оболочек. Процесс будет продолжаться до тех пор, пока в каждой получившейся оболочке не будет один треугольник, либо пока очередное разбиение не изменит ситуацию (в результирующей оболочке останется столько же треугольников, сколько в исходной).
То, что большие треугольники рассматриваются отдельно, дает выигрыш во времени, так как при этом оболочки, мало перекрываются. Данное соотношение размеров было подобрано экспериментально. При нем достигается наибольший выигрыш по времени.
2.4.2 Алгоритм обхода оболочек в трассировке лучей
Устанавливаем текущей первую оболочку.
Для трассируемого луча проверяется, пересекается ли он с текущей оболочкой. Если нет, то выводим цвет фона. Если да, то идем на п.3.
Пересекаем луч с большими треугольниками данной оболочки.
Если у оболочки нет подоболочек, то ищем пересечения с треугольниками этой оболочки. Если же у нее есть подоболочки, то вызываем п.2 для них всех.
При пересечении оболочек с лучом необходимо преобразовать, центры оболочек в систему координат, связанную с лучом.
При повороте или сдвиге всех объектов сцены, необходимо преобразовывать и центры оболочек. Если же совершаются преобразования не над всей сценой, а только над отдельными объектами, то необходимо произвести полный перерасчет оболочек.
2.5 Текстурирование
2.5.1. Процедуры для работы с текстурами
Для работы с текстурой предусмотрены 3 функции:
1. AddTeksture
Эта функция загружает текстуру в память. Входным данным для нее является имя файла, в котором находится текстура. Для успешной загрузки текстуры необходимо, чтобы она:
имела размеры, равные степени двойки
была в формате BMP
имела глубину цвета равную 24.
Функция возвратит true при успешной загрузке текстуры и false при неудаче.
2. CloseTex
Удаляет все ранее загруженные текстуры из памяти.
3. GetTexPoint
Эта функция позволяет получить 3 компоненты цвета точки текстуры. Входными параметрами для нее являются:
X и Y - координаты точки текстуры
Nom - номер текстуры
Первые две функции используются на этапе создания изображения. С их помощью можно легко нарисовать одну и ту же сцену с разными текстурами. При этом придется переделать всего несколько строчек.
Третья функция используется непосредственно на этапе текстурирования.
Как было сказано выше, текстурирование осуществляется в процедуре Per. Как только луч нашел пересечение с каким-либо треугольником, происходит определение цвета точки, с которой было найдено пересечение. Если у атрибутов треугольника стоит номер текстуры, равный нулю, то в качестве цвета треугольника берется цвет, записанный в атрибутах. В противном случае определяется, какая точка текстуры соответствует данной точке треугольника.
2.5.2. Собственно текстурирование
Поставим в соответствие каждому треугольнику формулы преобразования координат точек треугольника в текстурные координаты:
![]()
![]()
Определим коэффициенты a,b,c,d,e,f.
Поставим в соответствие каждой вершине треугольника нужную текстурную координату.
![]()
![]()
![]()
![]()
![]()
![]()
Мы получили две системы линейных уравнений. Системы будут иметь единственное решение в том случае, если определитель системы не равен нулю. Определим его значение.

Это условие соответствует тому, что три точки треугольника лежат на одной прямой. Если это так, то треугольник не текстурируем.
В противном случае определяем коэффициенты. Точка пересечения треугольника и луча имеет во вспомогательной системе координат нулевые координаты X и Y.
Поэтому XT=C и YT=F. Имеет смысл искать только коэффициенты С и F.
![]()

Далее вызывается, описанная выше процедура GetTexPoint, с текстурными координатами round (C) и round (F). Получаем цвет нужной нам точки треугольника.
2.6 Закраска Фонга
В программе есть возможность сгладить выборочно нужные треугольники. Для этого в атрибутах треугольника есть флаг PaintType. Если он равен True, совершается сглаживание Фонга. Если равен False, то треугольник не сглаживается. Для удобства в программе введены две константы Const_Paint_Fong и Const_Paint_Flat, равные соответственно True и False. Наличие такого флажка, делает возможным строить практически любые по форме тела.
Закраска Фонга заключается в следующем:
Определяются нормали в вершинах грани
Определяются внешние нормали у всех граней, содержащих данную вершину
Нормаль в вершине равна среднему значению нормалей прилежащих граней
Билинейной интерполяцией вычисляется нормаль в каждом пикселе.
В данной программе первый шаг алгоритма не осуществляется. Необходимо еще при моделировании сцены определить значение нормалей в вершинах. Второй шаг алгоритма использует метод использованный в текстурировании. Мы ставим в соответствие каждому треугольнику формулы преобразования координат точек треугольника в x,y,z компоненты нормали:
![]()
![]()
![]()
Опуская вычисления, определим с, f, e.
![]()

![]()
Вычисленные значения являются значениями нормали в точке пересечения луча и треугольника.
Закраска Фонга является очень трудоемкой, она намного медленнее закраски Гуро, так как приходится интерполировать три величины и приходится каждый раз совершать пересчет освещенности. Но она является наиболее качественной, так как дает реалистичные блики и качественные плавные изменения яркости на гладких телах. К недостаткам метода можно отнести то, что при создании последовательных кадров закраска может заметно меняться от кадра к кадру.
2.7 Освещение
2.7.1. Модель освещения Уиттеда
В данной программе я применил модель освещения Уиттеда. Она задается следующей формулой:
![]()
Ka - коэффициент рассеянного отражения.
Kd - коэффициент диффузного отражения.
Ks - коэффициент зеркальности.
Kr - коэффициент отражения.
Kt - коэффициент преломления.
Ia - интенсивность фонового освещения.
Id - интенсивность, учитываемая для диффузного рассеивания.
Is - интенсивность, учитываемая для зеркальности.
Ir - интенсивность излучения, приходящего по отраженному лучу.
It - интенсивность излучения, приходящего по преломленному лучу.
С - цвет поверхности.
Фактически формула представляет собой сумму всех световых потоков, отраженных и преломленных в данной точке и попавших в глаз наблюдателя.
При расчете освещенности, необходимо посчитать не одну формулу, а три (по каждой компоненте света: красной, синей и зеленой). При этом вместо С используется нужная компонента цвета поверхности, вместо Ir и It нужные компоненты излучения, приходящего по отраженному и преломленному лучу. Эти значения будут возвращены процедурами Ray, вызванными для преломленного и отраженного лучей.
2.7.2 Диффузное отражение
Этот вид отражения присущ матовым поверхностям. Матовой можно считать такую поверхность, размер шероховатостей которой уже настолько велик, что падающий луч рассеивается равномерно во все стороны. Такой тип отражения характерен, например, для гипса, песка, бумаги. Диффузное отражение описывается законом Ламберта, согласно которому интенсивность отраженного света пропорциональна косинусу угла между направлением на точечный источник света и нормалью к поверхности.
,
где θ
- угол между
нормалью и
направлением
на источник.
Косинус угла между двумя векторами можно посчитать по формуле:
.
Соответственно cos (θ) можно посчитать по формуле
.
Так как нормаль - это единичный вектор, то

Поэтому, для расчета диффузной интенсивности в формуле Уиттеда необходимо просуммировать все Icosθ для каждого, видимого из данной точки, источника.
2.7.3 Зеркальное отражение
Падающий луч, попадая на слегка шероховатую поверхность реального зеркала порождает, не один отраженный луч, а несколько лучей, рассеиваемых по различным направлениям. Зона рассеивания зависит от качества полировки и может быть описана некоторым законом распределения. Как правило, форма зоны рассеивания симметрична относительно линии идеального зеркально отраженного луча. К числу простейших, но достаточно часто используемых, относится эмпирическая модель распределения Фонга, согласно которой интенсивность зеркально отраженного излучения пропорциональна cospα. α - угол отклонения от линии идеально отраженного луча. Показатель p находится в диапазоне от 1 до 200 и зависит от качества полировки.
.
α - угол между вектором наблюдения и вектором отражения луча из данного источника (R и S).
Но можно поступить наоборот. Можно найти угол между отражением S и L, он будет равен первому. Но в данной процедуре выгодно искать угол между S и L. Это дает экономию в расчетах. Так как во вспомогательной системе координат падающий луч (S) и ось OZ совпадают. Поэтому отраженный луч (W) ищется очень просто:
Wx=-Nx*Ny
Wy=-Ny*Nz
Wz=0,5-Nz2
Поэтому

Для расчета зеркальности в формуле Уиттеда необходимо просуммировать все Icospα для каждого, видимого из данной точки, источника.
2.7.4 Фоновая освещенность
Постоянная рассеянного света вводится для того, чтобы учесть фоновую освещенность, образующуюся при вторичных и третичных отражениях.
Полностью формула Уиттеда будет выглядеть:

Интенсивности
излучений,
приходящих
по отраженному
и преломленному
лучу умножаются
на
,
где R - расстояние,
пройденное
лучом в среде,
а δ -
коэффициент
затухания света
в среде. Таким
образом, я
предусматриваю
затухание света
в среде.
2.7.5 Прозрачность
В программе есть возможность для разного моделирования прозрачности. Для включения той или иной модели необходимо нажать соответствующую кнопку в опциях.
Простая модель.
Если включена простая модель, то при попадании луча на прозрачный объект формируется не преломленный луч, а луч параллельный падающему. Коэффициенты пропускания и отражения берутся из свойств объекта.
Модель преломления.
Если включена эта модель, то при попадании луча на прозрачный объект формируется преломленный луч. В этой модели коэффициент пропускания и отражения в сумме дают
1-Kd-Ks-Ka (Part).
Если коэффициент преломления объекта, в который входит луч больше 10000, то формируется только отраженный луч, поскольку преломленный луч в такой оптически плотной среде будет иметь очень малую интенсивность. Коэффициент отражения в этом случае равен Part, вся энергия пойдет на отражение.
Если коэффициент преломления объекта меньше 10000, то определяем, соответствует ли угол падения луча углу полного внутреннего отражения.
Если это угол полного внутреннего отражения, то преломленный луч не формируется, формируется только отраженный луч, с коэффициентом отражения, равным Part.
Если это не угол полного внутреннего отражения, то формируются и преломленный, и отраженный луч. Зависимость между энергией преломленного и отраженного луча выражает формула Френеля:

Она определяет долю отраженной энергии. Доля пропущенной энергии равна 1-F. Соответственно, коэффициент отражения устанавливается равным Part*F, а преломления Part* (1-F).
Данная модель дает наиболее качественные результаты, поскольку происходит плавный, переход в область полного внутреннего отражения.
2.7.6 Процедуры расчета освещенности
Расчет диффузной и зеркальной составляющих осуществляет процедура Elluminaty.
Elluminaty (const M: TMatrix; MaxN: integer; NX, NY, NZ, RX, RY, RZ: real; BodyR, BodyG, BodyB: byte; var DifR, DifG, DifB, BlikR, BlikG, BlikB: real)
Параметры функции:
BodyR, BodyG, BodyB - компоненты цвета поверхности
DifR, DifG, DifB - возвращаемые функцией компоненты диффузного света
BlikR, BlikG, BlikB - возвращаемые функцией компоненты зеркального света
NX, NY, NZ - нормаль к поверхности, посчитанная в системе координат, где Z направлен по ходу луча, падающего на поверхность.
RX, RY, RZ - отражение падающего на поверхность луча (вектора наблюдателя).
MaxN - номер треугольника, на котором находится рассматриваемый пиксел.
M - матрица преобразования исходной системы координат в систему координат, где Z направлен по ходу луча, падающего на Поверхность.
Процедура Elluminaty перебирает все источники света и определяет вклад каждого источника в итоговую освещенность точки.
Для каждого источника она определяет его координаты во вспомогательной системе координат (T. x, T. y, T. z). Cоставляет матрицу преобразования к системе координат, в которой ось OZ совпадает с направлением на источник.
Эта матрица передается в функцию Per2, которая определяет, затенена ли точка данным источником. Если точка затенена, то данный источник ничего не вкладывает в итоговую освещенность. Если же точка не затенена, то считаем диффузную освещенность и зеркальные блики, создаваемые данным источником.
Функция Per2 возвращает коэффициент, равный доле света, который дошел от источника до точки. Она перебирает треугольники, лежащие между источником и рассматриваемой точкой. Если встречается непрозрачный треугольник, то функция завершается со значением 0. При встрече с прозрачным объектом результирующий коэффициент умножается на прозрачность треугольника.
3. Технологическая часть
3.1 Выбор языка программирования и обоснование выбора
Для разработки программы использовался язык Object Pascal. В качестве среды разработки использовалась среда Borland Delphi 6. Выбор именно Delphi 6 был обусловлен тем, что данная среда обладает богатыми возможностями для отладки программ, а так же тем, что она обладает большим собранием визуальных компонент, позволяющим сделать качественный интерфейс.
3.2 Модульная структура программы
Программа написана с помощью структурного подхода.
В ней содержится 6 модулей.4 модуля относятся к модулям форм. Это модули
Main, Model, Options, Figure. Главной формой в программе является Main. В поле этой формы выводится изображение, так же с помощью нее осуществляется вызов, других форм. Форма Model служит для преобразований над сценой, камерой, источниками света. С помощью формы Options осуществляется настройка опций рендеринга. Форма Figure, служит для параметрического задания первой модели. Так как главная форма управляет всеми остальными формами, то модули этих форм должны быть подключены к Main. Но помимо этого все подформы должны иметь доступ к главной форме. Поэтому я установил двустороннюю связь между Main и модулями подформ.
Модуль Engine - это модуль для создания и построения трехмерных изображений. Он содержит функции для формирования сцены, рендеринга сцены, для изменения параметров источников света, камеры и сцены. Поскольку все модули используют его, то его необходимо подключить его ко всем модулям.
Модуль DataControl подключается к тем модулям, в которых осуществляется ввод данных с клавиатуры. Модуль содержит функции для проверки правильности ввода данных. Это функции IsReal и IsInt. Они проверяют, является ли переданная им строка числом с плавающей точкой или целым. Поскольку ввод данных осуществляется во всех формах кроме Main, то модуль подключен ко всем ним.
Полная структура связей выглядит так:

3.3 Интерфейс программы
Вывод изображения в программе осуществляется в поле главной формы. При изменении разрешения картинки форма автоматически изменит свои размеры.
Меню главной формы состоит из пунктов: "Преобразования", "Фигура", "Опции", "Рендеринг".
При выборе пункта "Рендеринг", произойдет просчет изображения с текущими параметрами источников света, камеры и вывод его на экран.
При выборе пункта "Фигура", можно выбрать из развернувшегося списка сцену, которую необходимо изобразить.
При выборе пункта "Преобразования" на экране появится форма, с помощью которой можно повернуть или сместить объекты сцены, изменить положение камеры, а так же менять выполнять различные действия над источниками света.
При выборе пункта "Опции" на экране, так же появится форма, в которой можно менять параметры рендеринга.

Форма
преобразований: