Реализация алгоритма обратной трассировки лучей для моделей с большим числом полигонов (стр. 4 из 7)
При построении оболочек необходимо, чтобы главная оболочка целиком включала все ее подоболочки, иначе не будет работать правило: "Если луч не пересекает главную оболочку, то он не пересекает и все ее подоболочки". Так же при построении оболочек желательно, чтобы оболочки, имеющие один порядок вложенности, пересекались по как можно меньшему объему. Это улучшит эффективность алгоритма. Метод оболочек помогает сделать время рендеринга пропорциональным 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.
Вычисленные значения являются значениями нормали в точке пересечения луча и треугольника.
Закраска Фонга является очень трудоемкой, она намного медленнее закраски Гуро, так как приходится интерполировать три величины и приходится каждый раз совершать пересчет освещенности. Но она является наиболее качественной, так как дает реалистичные блики и качественные плавные изменения яркости на гладких телах. К недостаткам метода можно отнести то, что при создании последовательных кадров закраска может заметно меняться от кадра к кадру.