Однако сравнение каждого многоугольника с каждой сканирующей строкой является неэффективным. Целесообразнее использовать список активных ребер [1, с.99]. Но в отличие от растровой развертки одного многоугольника здесь осуществляется работа со всеми многоугольниками об»екта.
Алгоритм может быть сформулирован следующим образом:
а) Создание списка активных многоугольников. Для этого определяется самая верхняя сканирующая строка, которую пересекает многоугольник, и заносится многоугольник в группу Y, соответствующую этой сканирующей строке. Для каждого многоугольника создается таблица (список), содержащая следующую информацию: коэффициенты А, В, С, D уравнения плоскости многоугольника; ymh - число сканирующих строк, пересекаемых многоугольником; атрибуты (цвет, интенсивность) многоугольника; Zn -глубину многоугольника для пиксела, соответствующего левому
-56-
ребру; Zx - приращение по Z вдоль сканирующей строки ( Z=-A/C, С<>0); Zy - приращение по Z между сканирующими строками ( Zy=-В /С, С<>0).
Если С=0, то плоскость параллельна оси Z, и линия пересечения сканирующей плоскости и рассматриваемой плоскости проецируется в точку. В этом случае значение координаты Z надо вычислить для точки пересечения сканирующей строки с ребром многоугольника, ближайшим к наблюдателю (так же, как в алгоритме Варнока и Z-буфера).
б) Создание списка активных ребер для всех негоризонтальных
ребер. Элементы списка должны быть отсортированы по группам на
основе меньшей Y-координаты (если считать, что верхней строке
экрана соответствует минимальное значение Y-координаты).
в) Запоминание по каждому ребру в виде таблицы (списка)
следующей информации: Х-координаты вершины с наименьшей Y-ко-
ординатой; X -приращения координаты X ребра при переходе к со
седней сканирующей строке; Y - количества сканирующих строк,
пересекаемых ребром; идентификатора многоугольника, показываю
щего принадлежность ребра многоугольнику.
а) Инициализация буфера кадра размером с одну сканирующую
строку дисплея для всех пикселов цветом фона.
б) Инициализация 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). И данный пиксел надо закрасить цветом об»екта с этой максимальной глубиной.
Если наблюдатель находится не в бесконечности, алгоритм усложняется несущественно. Задача сводится к построению одноточечной центральной проекции.
Центральным пунктом алгоритма явяляется процедура определения пересечений луча с поверхностью об»екта. В сцену можно включать любые об»екты, для которых можно реализовать процедуру построения пересечений: плоские многоугольники, многогранники, тела, ограниченные квадратичными или биполиномиальными параметрическими поверхностями. Эффективность данной процедуры
оказывает самое большое влияние на эффективность всего алгоритма, так как более 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