Удаление невидимых поверхностей.

а) Инициализация буфера кадра размером с одну сканирующую
строку дисплея для всех пикселов цветом фона.

б) Инициализация Z-буфера размером с одну сканирующую строку
путем занесения в него значения Zmin.

в) Проверка для очередной сканирующей строки появления новых
многоугольников (соответствующая Y-группа должна быть не пус­
та). Добавление новых многоугольников к списку активных много­
угольников.

-57-

г) Проверка появления новых многоугольников в списке актив­
ных многоугольников. Добавление всех пар  ребер новых
многоугольников к списку активных ребер.

д) Проверка удаления ребра из списка активных ребер. Провер­
ка сохранения многоугольника в списке активных многоугольни­
ков. Укомплектование пары активных ребер многоугольника в
списке активных ребер при сохранении многоугольника в списке
активных многоугольников.

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

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

- извлечение пары ребер многоугольника из списка активных
ребер;

- инициализация Z со значением Zn;

- вычисление глубины для каждого пиксела, лежащего в ин­
тервале Хл<Х<Хп (Хл, Хп -абсциссы точек пересечения левого и
правого ребер пары со сканирующей строкой): для очередной точ­
ки текущей сканирующей строки Zx+ x=Zx- Zx;

- сравнение глубины Z(x) с величиной Z6y<|)(x) для те­
кущей строки. При Z(x)>Z6y<|)(x) занесение атрибутов многоуголь­
ника в буфер кадра для сканирующей строки и замена Z6y4>(x) на
Z(x);

- запись буфера кадра для сканирующей строки в буфер кад­
ра дисплея.

- коррекция списка активных ребер:

-58-

¥л=¥л-1; Yn= Yn-1. При ¥л<0 или Yn<0 удаление соот­ветствующего ребра из списка; индикация обоих ребер и соот­ветствующего многоугольника;

- вычисление новых абсцисс точек пересечения:
Хл=Хл+ Хл; Хп=Хп+ Хп;

- вычисление глубины многоугольника на левом ребре с
помощью уравнения плоскости многоугольника:

Zn= Zn- Zx* Х- Zy;

- удаление многоугольника из списка активных многоуголь­
ников при Умн<0.

Перед началом работы алгоритма целесообразно удалить не­лицевые грани.

6.7.АЛГОРИТМ ОПРЕДЕЛЕНИЯ ВИДИМЫХ ПОВЕРХНОСТЕЙ ПУТЕМ ТРАССИРОВКИ ЛУЧЕЙ

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

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

Если наблюдать лучи, выпущенные источником, то можно убе­диться, что лишь малое их количество дойдет до наблюдателя, поэтому такой подход в вычислительном плане весьма неэффекти-

-59-

вен. Более эффективным является подход, при котором лучи отс­леживаются (трассируются) в обратном направлении, т.е. от наб­людателя к об»екту.

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

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

Лучи, идущие от наблюдателя, параллельны в этом случае оси Z. Необходимо проследить траекторию луча, чтобы определить об»екты сцены, с которыми этот луч пересекается, и вычислить глубину пересечения с каждым об»ектом для каждого пиксела (лу­чей будет столько, сколько пикселей на экране). Из всех об»ек-тов, с которыми пересекается луч, видимым для данного пиксела будет тот, пересечение с которым имеет наибольшую глубину (максимальное значение координаты Z). И данный пиксел надо закрасить цветом об»екта с этой максимальной глубиной.

Если наблюдатель находится не в бесконечности, алгоритм усложняется несущественно. Задача сводится к построению одно­точечной центральной проекции.

Центральным пунктом алгоритма явяляется процедура опреде­ления пересечений луча с поверхностью об»екта. В сцену можно включать любые об»екты, для которых можно реализовать процеду­ру построения пересечений: плоские многоугольники, многогран­ники, тела, ограниченные квадратичными или биполиномиальными параметрическими поверхностями. Эффективность данной процедуры

-60-

оказывает самое большое влияние на эффективность всего алго­ритма, так как более 75% всего времени затрачивается на опре­деление пересечений.

Для исключения ненужного поиска пересечений в алгоритме предлагается искать сначала пересечение луча с об»емлющей обо­лочкой об»екта. Если луч не пересекает оболочку, то он не пе­ресекает и сам об»ект.

В качестве оболочек удобнее всего использовать сферу или прямоугольный параллелепипед.

Использование сферы может оказаться неэффективным, так как об»ем описанной сферы может существенно превышать об»ем об»екта. Но тест со сферической оболочкой чрезвычайно прост: достаточно определить расстояние от центра сферы до луча. При использовании параметрического представления прямой, проходя­щей через точки Pl(xl,yl,zl) и P2(x2,y2,z2), получим P(t)=Pl+(P2-Pl)t

или  x=xl+(x2-xl)t=xl+at у=у 1 +(у2-у 1 )t=y I +bt z=zl+(z2-zl)t=zl+ct

Если центр сферы лежит в точке с координатами Po(Xo,Yo,Zo), то квадрат расстояния от него до прямой:

d =(Xl+at-Xo) + (Yl+bt-Yo) + (Zl+ct-Zo). Значение параметра t, при котором это расстояние мини­мально, находится из условия

dd(t)

-=0