Алгоритмы, использующие список приоритетов

При реализации всех обсуждавшихся алгоритмов удаления невидимых линий и поверхностей устанавливались приоритеты, т. е. глубины объектов сцены или их рас­стояния от точки наблюдения. Алгоритмы, использующие список приоритетов, пытаются получить преимущество посредством предварительной сортировки по глубине или приоритету. Цель такой сортировки состоит в том, чтобы получить окончательный список элементов сцены, упорядоченных по приоритету глубины, основанному на рас­стоянии от точки наблюдения. Если такой список окончателен, то никакие два элемента не будут взаимно перекрывать друг друга. Тогда можно записать все эле­менты в буфер кадра поочередно, начиная с элемента, наиболее удаленного от точки наблюдения. Более близкие к наблюдателю элементы будут затирать информацию о более далеких элементах в буфере кадра. Поэтому задача об удалении невидимых поверхностей реша­ется тривиально. Эффекты прозрачности можно включить в состав алгоритма путем не полной, а частичной корректировки содержимого буфера кадра с учетом атрибутов про­зрач­ных элементов.

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

Рис. 4.13 Установление приоритетов для многоугольников

Для простой сцены, вроде той, что показана на рис. 5.13а, окончательный список приори­тетов можно полу­чить непосредственно. Например, эти многоугольники можно упорядочить по их максимальному или минималь­ному значению координаты z. Однако уже для сцены, показанной на рис. 5.13b, окончательный список приорите­тов по глубине невозможно получить простой сортировкой по z. Если P и Q с рис. 5.13b упорядочены по мини­мальному значению координаты z (z _min), окажется, что Р в списке приоритетов по глубине будет стоять перед Q. Если их записать в буфер кадра в таком порядке, то полу­чится, что Q частично экранирует P. Однако фактически P частично экранирует Q. Пра­вильный порядок в списке приоритетов будет тогда, когда P и Q поменяются мес­тами.

Другие трудности показаны на рис. 5.14. Здесь многоугольники циклически перекры­вают друг друга. На рис. 5.14а P находится впереди Q, который лежит впереди R, кото­рый в свою очередь находится впереди P. На рис. 5.14b P экранирует Q, a Q экранирует P. Аналогичное циклическое экранирование возникает при протыкании многоугольни­ков; например, на рис. 5.12 показано, как треугольник протыкает прямоугольник. Там прямоугольник экранируется треугольником, и наоборот, В обоих примерах окончатель­ный список приоритетов невозможно установить сразу. Выход из положения заключается в циклическом разрезании многоугольников по линиям, образованным пе­ресечениями их плоскостей до тех пор, пока не будет получен окончательный список приоритетов. Такие линии показаны пунктиром на рис. 5.14.

Рис. 4.14 Циклически перекрывающие многоугольники

Ньюэл М., Ньюэл Р. и Санча предложили специальный метод сортировки для разрешения конфликтов, возни­кающих при создании списка приоритетов по глубине. Этот метод включен в состав алгоритма Ньюэла - Ньюэла - Санча, который излагается ниже. В алгоритме динамически вычисляется новый список приоритетов перед об­работкой каждого кадра сцены. Не накладывается никаких ограничений на сложность сцены и на тип многоугольников, используемых для описания элементов сцены. Перво­начальный алгоритм Ньюэла - Ньюэла - Санча был предназначен для обработки трех­мерных тел. Это расширение не ограничено рамками многогранни­ков. Оно может, кроме того, обрабатывать тела смешанных типов в рамках одной сцены.