Алгоритм Вейлера-Азертона

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

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

2) отсечение по границе ближайшего к наблюдателю многоугольника, называемое сортировкой многоугольников на плоскости;

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

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

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

В качестве отсекающего многоугольника используется копия первого многоугольника из предварительного списка приоритетов по глубине. Отсекаться будут остающиеся в этом списке многоугольники, включая 1-й многоугольник. Вводятся два списка: внутренний и внешний. С помощью алгоритма отсечения Вейлера-Азертона все многоугольники отсекаются по границам отсекающего многоугольника. Та часть каждого отсекаемого многоугольника, которая оказывается внутри отсекающего, если она имеется, попадает во внутренний список. Оставшаяся часть попадает во внешний список. Этот этап является сортировкой на плоскости или xy-сортировкой. Теперь сравниваются глубины каждого многоугольника из внутреннего списка с глубиной отсекающего многоугольника. С использованием координат (х, у) вершин отсекаемых многоугольников и уравнений несущих плоскостей вычисляются глубины (координаты z) каждой вершины. Затем они сравниваются с минимальной координатой z () для отсекающего многоугольника. Если глубина ни одной из этих вершин не будет больше , то все многоугольники из внутреннего списка экранируются отсекающим многоугольником. Эти многоугольники удаляются, и изображается внутренний список. Заметим, что во внутреннем списке остался лишь отсекающий многоугольник. Работа алгоритма затем продолжается с внешним списком. Если координата z какого-либо многоугольника из внутреннего списка окажется больше, чем , то такой многоугольник по крайней мере частично экранирует отсекающий многоугольник. В подобном случае результат предварительной сортировки по глубине ошибочен. Поэтому алгоритм рекурсивно подразделяет плоскость (x, y), используя многоугольник, нарушивший порядок, в качестве нового отсекающего многоугольника. Отсечению подлежат многоугольники из внутреннего списка, причём старый отсекающий многоугольник теперь сам будет подвергнут отсечению новым отсекающим многоугольником. Подчеркнём, что новый отсекающий многоугольник является копией исходного многоугольника, а нс его остатка после первого сечения.