Предварительная сортировка по глубине.

В результате выполнения этого шага многоугольники упорядо­чиваются в порядке уменьшения максимального значения координаты Z и образуют некоторый приоритетный список. Считается, что наб­людатель располагается в бесконечности на положительной полуоси Z, поэтому многоугольник с наивысшим приоритетом окажется бли­жайшим к наблюдателю. В простейшем случае (если ближайший мно­гоугольник не пересекается другими многоугольниками или пол­ностью лежит ближе всех других многоугольников) он заслоняет все остальные многоугольники или их части. Поэтому область эк­рана, на которую проецируется первый многоугольник, можно зак­расить цветом этого многоугольника.

Поскольку самый приоритетный многоугольник может оказаться «маленьким» и не будет закрывать все остальные многоугольники, то необходимо выполнить второй шаг алгоритма.

2.       Отсечение по границе ближайшего к наблюдателю много­угольника (сортировка многоугольников на плоскости).

В качестве отсекателя используется копия самого приори­тетного многоугольника из списка, полученного на первом шаге. Отсекаются все остающиеся в приоритетном списке многоугольники (в том числе и первый). С помощью алгоритма отсечения Вейлера-Азертона [1, с.315] проводится отсечение по границам отсекате­ля, в результате чего формируются два списка - внутренних и внешних многоугольников.

Фактически отсечение проводится с проекциями на плоскость XOY отсекателя и отсекаемого многоугольника (двумерная операция отсечения). Часть отсекаемого многоугольника (если она есть), попавшая внутрь отсекателя, добавляется к списку внутренних

-43-

многоугольников. Оставшаяся часть (находящаяся за пределами от-секателя) добавляется к списку внешних многоугольников.

Этот шаг представляет собой сортировку на плоскости или XY -сортировку.

3.        Удаление многоульников, экранированных многоульником,
ближайшим к точке наблюдения.

На этом шаге алгоритма сравниваются глубины каждого много­угольника из внутреннего списка с глубиной отсекающего многоу­гольника. Сначала для каждого многоугольника определяются коэф­фициенты уравнения несущей плоскости. Для каждой вершины каждого многоугольника с помощью полученных уравнений плоскос­тей вычисляются глубины (значения координаты Z). Полученные значения сравниваются с минимальным значением координаты Z (ZoTc.min) отсекающего многоугольника. Если глубина ни одной из вершин многоугольников из внутреннего списка не больше ZoTc.min, то все эти многоугольники экранируются отсекающим многоугольни­ком. И в итоге должен быть изображен отсекающий многоугольник.

Затем аналогично рассматривается внешний список многоу­гольников.

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

4.       Рекурсивное подразбиение и окончательная сортировка для
устранения неопределенностей.

Если координата Z какого-либо отсекаемого многоугольника окажется больше, чем ZoTc.min, то такой многоугольник частично экранирует отсекающий многоугольник. В таком случае результат предварительной сортировки ошибочен, и алгоритм рекурсивно под-

-44-

разделяет плоскость (X,Y), используя многоугольник, нарушивший порядок, в качестве нового отсекающего многоугольника. Отсече­нию подвергаются многоугольники из внутреннего списка, причем старый отсекающий многоугольник сам подвергается отсечению.

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

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

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

6.4. АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ СПИСОК ПРИОРИТЕТОВ

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

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

-45-

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

Рассматриваемый алгоритм называют еще алгоритмом художни­ка, поскольку он аналогичен тому способу, которым художник соз­дает картину. Сначала художник рисует фон, затем предметы, ле­жащие на среднем расстоянии и в последнюю очередь - передний план. Таким образом художник решает задачу об удалении невиди­мых поверхностей путем построения картины в порядке обратного приоритета. Алгоритм состоит из трех основных шагов.

1.         Упорядочение всех многоугольников в соответствии с их
наибольшим (или наименьшим) значением Z координаты.

На этом шаге алгоритма формируется приоритетный список многоугольников. Упорядочение можно проводить либо в соответс­твии с возрастанием максимального значения координаты Z многоу­гольника, либо по возрастанию минимального значения координаты Z. Предполагается, что такой многоугольник лежит дальше всех от точки наблюдения.

2.        Разрешение неопределенностей, вызванных перекрытием
Z-оболочек.

Будем считать для определенности, что плоскости упорядо­чены по возрастанию минимального значения координаты Z. Обоз­начим через Р плоскость, стоящую в приоритетном списке на пер­вом месте (она имеет min Zmini), а через Q - плоскость, стоящую на втором месте.

Тогда возможна ситуация, при которой плоскость Р пол­ностью или частично экранирует Q. Неопределенность возникает при циклическом перекрывании плоскостей, например, Р находится

-46-

впереди 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:

Ax+By+Cz+D=0

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

4. Q целиком находится с той стороны от плоскости Р, ко­
торая ближе к точке расположения наблюдателя. Для реализации
этого теста необходимо выполнить действия, аналогичные тем,
которые выполняются в предыдущем тесте. Надо, во-первых, опре­
делить коэффициенты А, В, С, D уравнения плоскости, проходящей
через многоугольник Р. Во-вторых, подставить координаты всех
вершин многоугольника Q в полученное уравнение и определить
знаки полученных результатов. Если знаки всех результатов оди­
наковы и совпадают со знаком результата при подстановке проб­
ной точки, заведомо лежащей перед плоскостью Р, то ответ на
этот тест дается утвердительный. Если получаемые значения рав­
ны нулю, то многоугольник Q лежит на плоскости Р.

5. Проекции многоугольников на плоскость XOY (экран) не

-48-

перекрываются. Выполнение этого теста фактически означает про­ведение теста на внешность и может выполняться, как в алгорит­ме Варнока (например, с бесконечным лучом).

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

Для измененного списка повторяются указанные тесты. В не­которых случаях изменение порядка плоскостей в списке может привести к правильному результату. Если же имеется взаимное экранирование нескольких плоскостей или их протыкание, то пе­рестановка к успеху не приводит. Именно в этом случае придем к необходимости новой перестановки многоугольника Q, что и будет означать факт перекрытия или протыкания (рис.).

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

Для разбиения многоугольника вдоль линии пересечения не­сущих эти многоугольники плоскостей можно использовать алго­ритм Сазерленда-Ходжмена (если отсекатель выпуклый) или алгоритм Вейлера-Азертона в общем случае. Многоугольник Q ис­пользуется как отсекатель. Многоугольник Р разбивается на два новых. Для нахождения точек пересечения ребер многоугольника Р с отсекателем Q можно использовать алгоритм Кируса-Бека [ ].