Курсовая работа: Реализация алгоритма обратной трассировки лучей для моделей с большим числом полигонов
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.