Поскольку самый приоритетный многоугольник может оказаться «маленьким» и не будет закрывать все остальные многоугольники, то необходимо выполнить второй шаг алгоритма.
В качестве отсекателя используется копия самого приоритетного многоугольника из списка, полученного на первом шаге. Отсекаются все остающиеся в приоритетном списке многоугольники (в том числе и первый). С помощью алгоритма отсечения Вейлера-Азертона [1, с.315] проводится отсечение по границам отсекателя, в результате чего формируются два списка - внутренних и внешних многоугольников.
Фактически отсечение проводится с проекциями на плоскость XOY отсекателя и отсекаемого многоугольника (двумерная операция отсечения). Часть отсекаемого многоугольника (если она есть), попавшая внутрь отсекателя, добавляется к списку внутренних
-43-
многоугольников. Оставшаяся часть (находящаяся за пределами от-секателя) добавляется к списку внешних многоугольников.
Этот шаг представляет собой сортировку на плоскости или XY -сортировку.
На этом шаге алгоритма сравниваются глубины каждого многоугольника из внутреннего списка с глубиной отсекающего многоугольника. Сначала для каждого многоугольника определяются коэффициенты уравнения несущей плоскости. Для каждой вершины каждого многоугольника с помощью полученных уравнений плоскостей вычисляются глубины (значения координаты Z). Полученные значения сравниваются с минимальным значением координаты Z (ZoTc.min) отсекающего многоугольника. Если глубина ни одной из вершин многоугольников из внутреннего списка не больше ZoTc.min, то все эти многоугольники экранируются отсекающим многоугольником. И в итоге должен быть изображен отсекающий многоугольник.
Затем аналогично рассматривается внешний список многоугольников.
Если же найдутся многоугольники, частично экранирующие наиболее приоритетный многоугольник в списке, то необходимо выполнить четвертый шаг алгоритма.
Если координата Z какого-либо отсекаемого многоугольника окажется больше, чем ZoTc.min, то такой многоугольник частично экранирует отсекающий многоугольник. В таком случае результат предварительной сортировки ошибочен, и алгоритм рекурсивно под-
разделяет плоскость (X,Y), используя многоугольник, нарушивший порядок, в качестве нового отсекающего многоугольника. Отсечению подвергаются многоугольники из внутреннего списка, причем старый отсекающий многоугольник сам подвергается отсечению.
Новый отсекающий многоугольник является копией исходного многоугольника, а не его остатка после предыдущего отсечения.
Дополнительно следует рассмотреть случай циклического перекрывания многоугольника и отсекающего многоугольника. Все экранируемое циклическим многоугольником удаляется на первом шаге отсечения, необходимо лишь произвести отсечение исходного многоугольника по границам циклического многоугольника, а затем изобразить полученный результат.
Для пересекающихся многоугольников с целью избежания зацикливания при построении приоритетного списка в качестве от-секателя следует брать часть многоугольника, ограниченную линией пересечения многоугольников. В этом случае получим два списка - внутренних и внешних многоугольников, для которых зацикливание не происходит.
6.4. АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ СПИСОК ПРИОРИТЕТОВ
Основная идея этого алгоритма заключается в упорядочении многоугольников в соответствии с их удаленностью от точки зрения и получении списка многоугольников, в котором бы никакие два элемента не перекрывали бы друг друга.
В этом случае все многоугольники можно последовательно разложить в растр, начиная просмотр списка с наиболее удаленных многоугольников. Ближайшие к наблюдателю многоугольники преоб-
разуются в растровую форму в последнюю очередь и закрывают более удаленные многоугольники, поскольку записываются в буфер кадра (или изображаются на экране) поверх старых.
Рассматриваемый алгоритм называют еще алгоритмом художника, поскольку он аналогичен тому способу, которым художник создает картину. Сначала художник рисует фон, затем предметы, лежащие на среднем расстоянии и в последнюю очередь - передний план. Таким образом художник решает задачу об удалении невидимых поверхностей путем построения картины в порядке обратного приоритета. Алгоритм состоит из трех основных шагов.
На этом шаге алгоритма формируется приоритетный список многоугольников. Упорядочение можно проводить либо в соответствии с возрастанием максимального значения координаты Z многоугольника, либо по возрастанию минимального значения координаты Z. Предполагается, что такой многоугольник лежит дальше всех от точки наблюдения.
Будем считать для определенности, что плоскости упорядочены по возрастанию минимального значения координаты Z. Обозначим через Р плоскость, стоящую в приоритетном списке на первом месте (она имеет min Zmini), а через Q - плоскость, стоящую на втором месте.
Тогда возможна ситуация, при которой плоскость Р полностью или частично экранирует Q. Неопределенность возникает при циклическом перекрывании плоскостей, например, Р находится
впереди Q, причем Q лежит впереди R, a R в свою очередь находится перед Р. Неопределенность возникает также и при протыкании многоугольников.
В отмеченных случаях окончательный список приоритетов не удается установить сразу. Для проверки правильности сформированного списка следует для каждого многоугольника Р проверить его отношение с Q. Многоугольник Р не может экранировать многоугольник Q, если его ближайшая к наблюдателю вершина (Pzmax) лежит дальше, чем самая удаленная вершина Q(Qzmin), т.е. Qzmin>Pzmax.
Если же Qzmin<Pzmax, то многоугольник Р потенциально может экранировать многоугольник Q и любой другой многоугольник, подобный Q, для которого выполняется приведенное соотношение. Если же Р фактически не экранирует Q, то Р можно заносить в буфер кадра.
Для выяснения фактического взаимного расположения многоугольников Р и Q необходимо выполнить проверку, представляющую собой тест из пяти шагов. Эти тестовые проверки упорядочены по возрастанию сложности их выполнения, причем при получении положительного ответа на очередном шаге теста многоугольник Р можно сразу преобразовать в растровую форму и дальнейшие проверки не проводить.
Пятью тестами являются следующие:
1. Х-оболочки многоугольников не перекрываются, поэтому
сами многоугольники также не перекрываются, положительный от
вет здесь получается, если истинно следующее выражение:
(Pxmax<Qxmin) (Qxmax<Pxmin).
2. Y-оболочки многоугольников не перекрываются, поэтому
-47-
сами многоугольники также не перекрываются. Положительный ответ в этом тесте получается, если истинно соотношение (Pymax<Qymin) (Qymax<Pymin)
3. Р целиком лежит с той стороны от плоскости Q, которая
дальше от точки расположения наблюдателя. Для выполнения этого
теста необходимо определить коэффициенты в уравнении плоскости
Затем в полученное уравнение подставить поочередно координаты всех вершин многоугольника Р. Если знаки результатов для всех вершин совпадают и совпадают со знаком результата при подстановке координат пробной точки, заведомо лежащей за плоскостью Q, то ответ на тест дается положительный. Если при подстановке координат точек получаемые значения равны нулю, то многоугольник Р лежит на плоскости Q.
4. Q целиком находится с той стороны от плоскости Р, ко
торая ближе к точке расположения наблюдателя. Для реализации
этого теста необходимо выполнить действия, аналогичные тем,
которые выполняются в предыдущем тесте. Надо, во-первых, опре
делить коэффициенты А, В, С, D уравнения плоскости, проходящей
через многоугольник Р. Во-вторых, подставить координаты всех
вершин многоугольника Q в полученное уравнение и определить
знаки полученных результатов. Если знаки всех результатов оди
наковы и совпадают со знаком результата при подстановке проб
ной точки, заведомо лежащей перед плоскостью Р, то ответ на
этот тест дается утвердительный. Если получаемые значения рав
ны нулю, то многоугольник Q лежит на плоскости Р.
5. Проекции многоугольников на плоскость XOY (экран) не
-48-
перекрываются. Выполнение этого теста фактически означает проведение теста на внешность и может выполняться, как в алгоритме Варнока (например, с бесконечным лучом).
Все указанные тесты должны применяться к каждой плоскости типа Q. Если во всех пяти тестах ролучен отрицательный ответ, то предполагается, что Р действительно закрывает Q, поэтому Р и Q меняют местами в списке. При этом необходимо отметить, что многоугольник Q был перемещен на новое место.
Для измененного списка повторяются указанные тесты. В некоторых случаях изменение порядка плоскостей в списке может привести к правильному результату. Если же имеется взаимное экранирование нескольких плоскостей или их протыкание, то перестановка к успеху не приводит. Именно в этом случае придем к необходимости новой перестановки многоугольника Q, что и будет означать факт перекрытия или протыкания (рис.).