Алгоритм определения видимых поверхностей путем трассировки лучей

Трассировка лучей является методом грубой силы (не учитывающим особенности обрабатываемых объектов), работающим в объектном пространстве. Метод основывается на идее о том, что наблюдатель видит объект за счет света, испускаемого некоторым источником, который дошел до него после взаимодействия с объектом. Свет может достичь наблюдателя, отразившись от поверхности, преломившись или пройдя через нее. Очевидно, что большинство лучей, испускаемых источником, не доходит до наблюдателя и прослеживать их путь нет необходимости. Аппель предложил отслеживать (трассировать) лучи в обратном направлении, т. е. от наблюдателя к объекту.

Наблюдатель считается расположенным на положительной полуоси Z. Если расстояние до него бесконечно, то лучи доходящие до него параллельны этой полуоси. Картинная (проекционная) плоскость перпендикулярна оси Z. Наложив на картинную плоскость образ сетки растра и считая, что лучи проходят через центры ячеек, можно определить количество и положение исследуемых лучей. Более сложная ситуация возникает если расстояние до наблюдателя конечно. Ее иллюстрирует рисунок 8.14. Задача сводится к построению одноточечной центральной проекции на картинную плоскость.

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

Наиболее важным элементом алгоритма определения видимых поверхностей путем трассировки лучей, является процедура определения пересечений. В состав сцены можно включать любой объект, для которого можно создать процедуру построения пересечений. Объекты сцены могут состоять из набора плоских многоугольников, многогранников или тел, ограниченных или определяемых квадратичными или полиномиальными параметрическими поверхностями. Очевидным путем повышения эффективности поиска пересечений является исключение из рассмотрения объектов удаленных от луча на значительное расстояние и, следовательно, не имеющих пересечений с ним. Для этого используют объемлющие оболочки объектов. Если луч не пересекает оболочку, следовательно, он никаким образом не может пересечь заключенный в нее объект. В качестве оболочки можно использовать прямоугольный параллелепипед или сферу. Факт пересечения трехмерного луча со сферой определяется очень просто. В частности, если расстояние от центра сферической оболочки до луча превосходит радиус этой сферы, то луч не пересекает оболочки. Поиск пересечений луча с прямоугольным параллелепипедом более сложен, однако задачу можно существенно упростить, если повернуть оболочку и луч так чтобы последний совпал с осью Z. Если пересечение существует, то начало координат попадет в проекцию оболочки на плоскость XOY.

Рисунок 8.15 Объемлющие оболочки

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

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

· Создать список объектов. Для каждого объекта описать его тип, характеристики поверхности, и т. п. Задать сферическую оболочку: центр и радиус. Если необходимо, задать прямоугольную оболочку.

· Для каждого трассируемого луча:

· Выполнить для каждого объекта тест на пересечение со сферической оболочкой Если луч пересекает эту сферу, то занести объект в список активных объектов.

· Если список активных объектов пуст, то изобразить данный пиксель с фоновым значением интенсивности. В противном случае, перенести и повернуть луч так, чтобы он совместился с осью z. Запомнить это комбинированное преобразование.

· Для каждого объекта из списка активных объектов:

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

· Если пересечения с лучом нет, то перейти к следующему объекту.

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

· Если список пересечений пуст, то изобразить данный пиксель с фоновым значением интенсивности.

· В противном случае определить пересечение, имеющее максимальное значение Z..

· Вычислить преобразование, обратное комбинированному преобразованию.

· Используя это обратное преобразование, определить точку пересечения в исходной системе координат.

· Изобразить данный пиксель, используя атрибуты пересеченного объекта и соответствующую модель освещенности.

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

Приведем несколько путей повышения эффективности алгоритма:

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

Использование регулярных сеток. Объекты сцены связываются с ячейками сетки. Поиск пересечений ведется только среди объектов связанных с ячейками, которые пересекает луч. Рисунок 8.16 иллюстрирует данный подход.

Рисунок 8.16 Применение регулярной сетки.

Применение Binary Space Partitioning (BSP) Tree -б инарного дерева каждый из узлов которого хранит информацию о плоскости, делящей пространство узла на 2 части. Пример структурирования сцены показан на рис. 8.17.

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