5. Алгоритм Вейлера – Азертона

В этом алгоритме сделана попытка минимизации количества шагов в алгоритме типа Варнока путем разбиения окна вдоль границ многоугольника. Основа этого алгоритма - алгоритм Вейлера – Азертона для отсечения многоугольников [1]. Алгоритм работает в пространстве объекта и его легко использовать как для удаления невидимых линий, так и невидимых поверхностей. Алгоритм состоит из четырех шагов:

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

• отсечение по границе ближайшего к наблюдателю многоугольника;

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

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

Предварительная сортировка по глубине необходима для формирования списка приблизительных приоритетов. Если точка наблюдения расположена в бесконечности на положительной полуоси z, то ближайшим многоугольником будет считаться многоугольник с максимальным значением z. В качестве отсекающего многоугольника используется копия первого многоугольника из предварительного списка по глубине. Отсекаться будут оставшиеся в этом списке многоугольники, в том числе и первый. С помощью алгоритма отсечения многоугольников Вейлера – Азертона все многоугольники отсекаются по границам отсекающего многоугольника. Вводится два списка: внутренний и внешний. Та часть отсекаемого многоугольника, которая оказывается внутри отсекающего, попадает во внутренний список, оставшаяся часть – во внешний список. Пример сцены и ее проекции на плоскость XY приведены на рис. 5.1, a и 5.1, б соответственно, а на рис. 5.2 – внутренний и внешний списки.

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

Если глубина z какого – либо многоугольника из внутреннего списка окажется больше Zmin (рис. 5.3), то такой многоугольник может частично экранировать отсекающий многоугольник. В этом случае результат предварительной сортировки по глубине ошибочен и алгоритм рекурсивно использует новый отсекающий многоугольник. Отсечению подлежат многоугольники из внутреннего списка, причем отсекающий многоугольник является копией исходного, а не его остатком во внешнем списке.

Рис. 5.1. Пример сцены для алгоритма Вейлера - Азертона

Рис. 5.2. Внутренний и внешний списки многоугольников

Рис.5.3. Условие возникновения ошибочного результата в предварительной сортировке по z

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

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

Для исключения ненужного рекурсивного разбиения используется список многоугольников, которые уже использовались в качестве отсекающих многоугольников.