Реализация алгоритма обратной трассировки лучей для моделей с большим числом полигонов (стр. 3 из 7)

3. Необходимо совершить поворот вокруг оси OX по часовой стрелке на угол β.

.

Матрица поворота, таким образом, будет равна:

Умножив M₃ на M₂, а результат на M₁ получим искомую матрицу перехода:

2.3.4 Программная реализация

Во многих функциях и процедурах в программе в качестве входных и выходных параметров выступают матрицы. Поэтому в программе введен специальный тип:

TMatrix=Array [0. .11] of real

Это массив из 12 элементов типа real. Он представляет собой последовательно записанные три верхние строчки матрицы. Я не включил последнюю строчку, так как она одинаковая у всех матриц преобразования и равна (0, 0, 0,1).

Для операций над матрицами в программе предусмотрены следующие процедуры:

1. Procedure MatrixAB (var Res: TMatrix; const M1,M2: TMatrix)

Процедура умножает матрицу M1 на матрицу M2 и помещает результат в Res.

2. Procedure ShiftMatrix (var M: TMatrix; Z: real)

Создает матрицу перехода из текущей системы координат в систему координат, сдвинутую по оси OZ на z.

Процедура перемещает систему координат, задаваемую матрицей M, по оси OZ на z.

3. Procedure SetMatrix (var M: TMatrix; dx,dy,dz,x,y,z: real) overload

Создает матрицу перехода из текущей системы координат в систему координат, находящуюся в точке (x,y,z), ось OZ которой направлена по вектору (dx,dy,dz).

4. Procedure SetMatrix (var M: TMatrix; dx,dy,dz: real) overload

Создает матрицу перехода из текущей системы координат в систему координат, ось OZ которой направлена по вектору (dx,dy,dz).

Преобразование координат

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

Для преобразования точки из одной системы координат в другую в программе существует процедура Trans (const M: TMatrix; var F: TPoint; const V: TPoint).

В V содержатся координаты точки, координаты которой надо преобразовать.

В F содержатся результат.

M - матрица преобразования.

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

Процедура находит координаты вторичного луча в новой системе координат.

Составляет матрицу перехода из текущей системы в систему, связанную с лучом (L_i+1).

Умножает матрицы M_i+1=L_i+1M_i

Вызывает рекурсивно Ray с параметром M_i+1

2.3.5 Определение пересечения луча с треугольником

Преобразуем все вершины треугольника в локальную систему координат, связанную с лучом. Луч в этой системе координат имеет координаты (0, 0,1). После этого задача сводится плоской. Необходимо определить, лежит ли точка (0, 0) внутри треугольника в проекции на плоскость OXY.

Преобразуем координату x вершин треугольника в локальную систему координат.

Проверяем, лежат ли точки треугольника все справа от нуля или все слева. Если да, то пересечения с треугольником нет. Если нет, то:

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

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

Необходимо, чтобы при обходе треугольника по часовой стрелке точка (0,0) лежала справа от каждой стороны (либо наоборот). Это можно установить, проверив одного ли знака три векторных произведения:

, , .

Если не одного знака, то пересечения нет, Если одного, то:

Преобразуем координату z вершин треугольника в локальную систему координат.

Определяем нормаль к треугольнику, для этого умножим векторно два вектора

и

В случае если, NZ равно нулю, луч параллелен оси OZ и соответственно лучу. Значит, пересечения нет. В другом случае пересечение есть.

Находим координаты пересечения.

Составим уравнение плоскости, в которой находится треугольник:

,

подставим x=0 и y=0,

2.3.4 Формирование отраженного луча

Обозначим отраженный луч через R, вектор, направленный против падающего луча - S, вектор нормали - N. Рассмотрим единичные векторы этих векторов R₁, S₁, N₁. Так как все три вектора находятся в одной плоскости, то можно записать R₁+S₁=N^’. Длина вектора N^’ равна 2cosθ. Так как векторы N^’ и N₁ сонаправленные, то можно записать:

N’=N₁2cosθ.

Таким образом

.

Поставим условие, что падающий и отраженный лучи имеют одинаковую длину.

Так как падающий луч в локальной системе координат имеет координаты (0, 0,1). То вектор S будет иметь координаты (0, 0, - 1). Подставим его координаты в выражение для отраженного луча. Получим

2.3.5 Формирование преломленного луча

Обозначим преломленный луч, имеющий единичную длину, через T₁. Единичный вектор нормали - через N₁. А вектор, направленный противоположно падающему лучу - через S₁. Разложим вектор S₁ на A и N_s, а вектор T₁ на B и N_T. Вектор равен

.

Найдем вектор N_T. Этот вектор противоположен по направлению вектору нормали, а длина его равна

.

Таким образом

.

Для того, что бы определить cosα₂, запишем закон преломления

.

Воспользуемся тождеством

Получим

Значение для cosα₁ можно выразить через скалярное произведение единичных векторов S₁ и N₁

. С учетом этого можно записать выражение для вектора

N_T:

Найдем вектор B. Он располагается на одной прямой с вектором A, причем

.

Найдем отношение длин векторов A и B:

. Отсюда

.

Если подкоренное выражение отрицательно, то это соответствует полному внутреннему отражению. В этом случае преломленный луч создаваться не будет. Учтем то, что вектор S равен (0, 0,1).

2.4 Оболочки

В алгоритме трассировки лучей от 70 до 90 процентов временных затрат занимает процедура определения пересечений луча с объектами сцены. Если перебирать все объекты сцены, то время будет пропорционально Cn, где С - количество пикселей, а n - число объектов на сцене. Улучшить алгоритм можно, если каким-нибудь образом попробовать сократить число перебираемых объектов. Очень простой, но эффективной является идея иерархических оболочек. Предположим, что нам надо изобразить содержимое полки с посудой. Проведем мысленно большую сферу вокруг полки, так чтобы она включала и полку, и посуду на ней. Затем сферу вокруг каждого предмета посуды. Теперь представим себе процесс рендеринга. Проверяем, пересекается ли луч с самой большой сферой. Если нет, то это значит, что луч не пересекает внутренние оболочки, переходим к другому лучу. Если пересекает, то смотрим пересечение луча с подсферами данной сферы. Как видно из такого примера, многие лучи могут совершить всего одну проверку и отсеяться.