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

Построчный алгоритм Уоткинса

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

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

Последовательность шагов алгоритма:

· построение списка ребер,

· построение списка многоугольников,

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

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

Удаление невидимых (скрытых) поверхностей в алгоритме трассировки лучей выполняется следующим образом:

· сцена преобразуется в пространство изображения,

· из точки наблюдения в каждый пиксел экрана проводится луч и определяется какие именно объекты сцены пересекаются с лучом,

· вычисляются и упорядочиваются по Z координаты точек пересечения объектов с лучом. В простейшем случае для непрозрачных поверхностей без отражений и преломлений видимой точкой будет точка с максимальным значением Z-координаты. Для более сложных случаев требуется сортировка точек пересечения вдоль луча.

При использовании прямоугольной оболочки определяется преобразование, совмещающее луч с осью Z. Оболочка подвергается этому преобразованию, а затем попарно сравниваются знаки Xmin с Xmax и Ymin с Ymax. Если они различны, то есть пересечение луча с оболочкой (см. рис.)

Рис. 21: Определение пересечения луча и оболочки

При использовании сферической оболочки для определения пересечения луча со сферой достаточно сосчитать расстояние от луча до центра сферы. Если оно больше радиуса, то пересечения нет. Параметрическое уравнение луча, проходящего через две точки P1(x1,y1,z1) и P2(x2,y2,z2), имеет вид:

x x x x

y y y y

P(t) = P1 + (P2 - P1)×t

Минимальное расстояние от точки центра сферы P0(x0,y0,z0) до луча равно:

d² = (x-x0)² + (y-y0)² + (z-z0)²

Этому соответствует значение t:

t = (x2-x1)·(x1-x0) + (y2-y1)·(y1-y0) + (z2-z1)·(z1-z0) (x2-x1)² + (y2-y1)² + (z2-z1)²

Если d2 > R2, то луч не пересекает объекты, заключенные в оболочку.

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

1. Понятие текстуры и текстурирования.

Текстура – изображение, накладываемое на объект.

Задача текстурирования формулируется следующим образом: есть грань (согласно предположениям, треугольная) с линейно наложенной на нее текстурой (то есть – каждая точка грани окрашена цветом соответствующей ей точки в текстуре); есть точка экрана с координатами (sx, sy), принадлежащая проекции грани. Требуется - найти цвет точки текстуры, соответствующей этой точке экрана; то есть найти “координаты текстуры” для точки, проекцией которой на экране является точка (sx, sy).

2. Виды текстурирования.