4) охватывающий многоугольник (область целиком лежит внутри
многоугольника).
Внешние многоугольники не оказывают влияния на принятие решения о визуализации окна. Внешняя часть пересекающего многоугольника может рассматриваться как внешний многоугольник. Внутренняя часть пересекающего многоугольника обрабатывается так же, как и внутренний многоугольник.
В следующих четырех случаях можно непосредственно принять решение относительно окна и не выполнять дальнейшего его разбиения:
1. Все многоугольники являются внешними по отношению к окну;
область можно закрасить цветом фона.
2. Имеется только один внутренний или только один пересекаю
щий многоугольник. В этом случае сначала окно закрашива
ется цветом фона, а затем многоугольник преобразуется в
растровую форму. Для пересекающего многоугольника сначала
-36-
следует выполнить отсечение и результат (внутренний многоугольник) преобразовать в растровую форму. Для преобразования в растровую форму может применяться один из алгоритмов нижнего уровня или примитив, имеющийся в составе графической библиотеки языка программирования.
3. Имеется единственный охватывающий многоугольник и нет ни
каких других многоугольников. Область закрашивается цве
том этого охватывающего многоугольника.
4. Имеется несколько пересекающих, внутренних и охватываю
щих многоугольников. В этом случае делается попытка най
ти охватывающий многоугольник, расположенный впереди
всех других многоугольников. При нахождении такого мно
гоугольника область закрашивается цветом охватывающего
многоугольника.
Для выявления такого охватывающего многоугольника применяется следующий тест: вычисляются Z-координаты плоскостей всех охватывающих, пересекающих и внутренних многоугольников в четырех угловых точках рассматриваемой области. Если существует охватывающий многоугольник, для которого все четыре вычисленные Z -координаты больше (ближе к наблюдателю), чем любые из других вычисленных Z-координат, то этот охватывающий многоугольник лежит перед всеми другими многоугольниками в рассматриваемой области, следовательно, область закрашивается цветом охватывающего многоугольника. Проверяемое в этом случае условие является достаточным, но не необходимым, чтобы охватывающий многоугольник был расположен ближе других к наблюдателю.
Если исследуемая ситуация не приводится ни к одному из этих четырех случаев, то проводится разбиение области. При этом
следует проверять лишь внутренние и пересекающие многоугольники. Охватывающие и внешние многоугольники для исходной области останутся таковыми по отношению и к любому из получаемых подокон. Процесс разбиения завершается, когда размер области совпадает с одним пикселом (достигается разрешение экрана).
Если ни один из четырех случаев не обнаруживается и для области размером с пиксел, то вычисляется глубина в этой точке для всех многоугольников, связанных с областью (внутренних, пересекающих, охватывающих), и пиксел закрашивается цветом многоугольника с максимальной Z-координатой.
Для вычисления глубины плоскости в точке с известными координатами (xl,yl) можно воспользоваться уравнением плоскости Ax+By+Cz+D=0, откуда получить Axl+Byl+D
С
Если же С=0, то плоскость параллельна оси Z. В этом случае глубина находится из уравнений ребер многоугольника, которые могут пересекать прямую, параллельную оси Z и проходящую через точку (xl,yl). В качестве глубины берется глубина той точки пересечения, у которой координата Z оказалась максимальной.
Области удобнее брать квадратными с размерами сторон (в пикселах), представляющими степень двойки. Для выполнения этого условия можно взять область, несколько превышающую по размерам экран дисплея. При этом подобласти, лежащие за пределами экрана, анализировать не надо (чтобы не проводить ненужных вычислений). Ошибки не будет, если такие области будут проанализирова-
-38-
ны обычным порядком, так как при их изображении координаты не будут соответствовать допустимым и изображаться ничего не будет.
Другим вариантом является разбиение относительно вершины многоугольника (если существует вершина, попадающая в область). Этим делается попытка избежать ненужных разбиений.
Следует отметить, что не существует единого алгоритма Вар-нока. Конкретные реализации этого алгоритма различаются в деталях. В простейшем варианте алгоритма Варнока любое окно размером больше пиксела всегда разбивается, если оно не пусто. В этой версии алгоритма для идентификации внешних многоугольников используется простой габаритный тест с прямоугольной оболочкой для областей, размер которых больше одного пиксела. Лишь для окон размером с пиксел выполняется более сложный тест на внешность.
Более сложные варианты алгоритма используют перечисленные тесты. При этом целесообразно иметь три списка многоугольников: 1)охватывающих; 2)внешних; 3)пересекающих и внутренних. При построении этих списков запоминается уровень (шаг разбиения), на котором многоугольник попал в тот или иной список.
Рассмотрим тесты, позволяющие распознать тип многоугольника. Простой габаритный тест выявляет факт внешности многоугольника по отношению к прямоугольному окну на основе сравнения координат окна с координатами прямоугольной оболочки многоугольника. Если Хл, Хп - абсциссы левой и правой границ, а yh, yb - ординаты нижней и верхней границ области, a Xmin, Xmax, Ymin, Ymax - координаты аналогичных границ оболочки, то многоугольник внешний, если истинно следующее выражение:
-39-
(Xmin>Xn) (Хтах<Хл) (Утт>Ув) (Утах<Ун)
Многоугольник будет внутренним, если его об»емлющая оболочка лежит внутри области, т.е. должно быть истинным выражение
(Xmin> Хл)&(Хтах< Xn)&(Ymin> Ун)&(Утах< yb).
Для определения пересекающих многоугольников можно подставить координаты вершин окна в пробную функцию, представляющую собой уравнение прямой, несущей ребро многоугольника. Эта функция имеет вид
f=Ax+By+C,
где А, В, С - коэффициенты уравнения прямой.
Если знак этой функции не зависит от выбора вершины окна, то все его вершины лежат по одну сторону от несущей прямой и на ней нет точек пересечения с рассматриваемой областью. Если ни одно из ребер многоугольника не пересекает окна, то этот многоугольник является либо внешним, либо охватывающим окно. При проведении этого теста надо учитывать тот факт, что используется уравнение бесконечной прямой, а не конечного отрезка. Поэтому для ребра, которое может пересекаться с окном, надо дополнительно вычислить координаты точки пересечения со сторонами окна. Если полученная точка принадлежит ребру, то многоугольник пересекает окно. В противном случае он является либо внешним, либо охватывающим (внутренние многоугольники к этому моменту уже определены).
На основе теста с прямоугольной оболочкой и теста с пробной функцией выявляются внутренние, пересекающие и часть внешних многоугольников. Часть внешних многоугольников (например, огибающих угол окна) не может быть отделена от охватывающих многоугольников. Поэтому требуются дополнительные тесты для
выявления внешних и охватывающих многоугольников (рис.).
В первом тесте проводится луч из любой точки окна (удобно из вершины) в бесконечность. Затем подсчитывается количество пересечений луча с многоугольником. При четном (или равным нулю) количестве пересечений многоугольник является внешним, при нечетном - охватывающим.
При прохождении луча через вершину многоугольника возникает неопределенность. Ее можно устранить, если считать касание за два пересечения, а протыкание - за одно.
Во втором тесте осуществляется подсчет угла. Из произвольной точки окна (лучше из центра) проводятся лучи в начало и конец каждого ребра многоугольника. При этом находится сумма углов, образованных такими лучами для каждого ребра. Обход по ребрам многоугольника совершается по или против часовой стрелки. Полученная сумма интерпретируется следующим образом:
ALFAi=0 - многоугольник внешний по отношению к окну.
(ALFAi - угол, образованный лучами, проведенными в конец 1-го ребра).
ALFAi=360m - многоугольник охватывает окно m раз (многоугольник без самопересечений может охватить точку только один раз).
Процесс вычисления суммы можно упростить, так как нет нужды подсчитывать углы с высокой точностью (достаточно ограничиться приращениями по 45 , т.е. считать целые октанты, покрытые отдельными углами). Октанты нумеруются от 0 до 7. Они получаются, если считать стороны окна бесконечными прямыми). Число целых октантов, покрытых углом, равно разности между но-
мерами октантов, в которых лежат концы его ребер. При этом ALFA= ALFA-8, если ALFA>4 ALFA= ALFA +8, если ALFA<-4
Если ALFA=+4, то сторона окна расщепляет ребро многоугольника, поэтому ребро в этом случае надо разбить на два стороной окна (в противном случае получаются одинаковые результаты для внешнего и охватывающего многоугольника).
На основе суммирования вкладов отдельных ребер получим О - многоугольник внешний по отношению к окну S= ALFAi =
Для выпуклых тел целесообразно предварительно удалить нелицевые грани, как это делается в алгоритме Робертса.
6.3. АЛГОРИТМ ВЕЙЛЕРА-АЗЕРТОНА
Алгоритм Вейлера-Азертона развивает идеи алгоритма Варнока в направлении минимизации количества шагов при разбиении окон на подокна. Основой алгоритма служит алгоритм отсечения многоугольников на плоскости тех же авторов. Для повышения точности алгоритм работает в об»ектном пространстве, выходными данными являются многоугольники, поэтому его можно использовать как для удаления невидимых линий, так и для удаления невидимых поверхностей.
Алгоритм удаления невидимых поверхностей состоит из четырех шагов:
-42-
В результате выполнения этого шага многоугольники упорядочиваются в порядке уменьшения максимального значения координаты Z и образуют некоторый приоритетный список. Считается, что наблюдатель располагается в бесконечности на положительной полуоси Z, поэтому многоугольник с наивысшим приоритетом окажется ближайшим к наблюдателю. В простейшем случае (если ближайший многоугольник не пересекается другими многоугольниками или полностью лежит ближе всех других многоугольников) он заслоняет все остальные многоугольники или их части. Поэтому область экрана, на которую проецируется первый многоугольник, можно закрасить цветом этого многоугольника.