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

Вейлер и Азертон попытались минимизировать количество шагов в алгоритме разбиения типа алгоритма Варнока путем разбиения окна вдоль границ многоугольника. Выходными данными этого алгоритма, который для достижения необходимой точности работает в пространстве объекта, служат многоугольники. Поскольку выходом являются многоугольники, то алгоритм можно легко использовать для удаления как невидимых линий, так и невидимых поверхностей. Алгоритм удаления невидимых поверхностей состоит из четырех шагов. 1. Предварительная сортировка по глубине. 2. Отсечение по границе ближайшего к наблюдателю многоугольника, называемое сортировкой многоугольников на плоскости. 3. Удаление многоугольников, экранированных многоугольником, ближайшим к точке наблюдения. 4. Если требуется, то рекурсивное подразбиение и окончательная сортировка для устранения всех неопределенностей.

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

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

Если координата z какого-либо многоугольника из внутреннего списка окажется больше, чем z_{c min}, то такой многоугольник по крайней мере частично экранирует отсекающий многоугольник. В подобном случае результат предварительной сортировки по глубине ошибочен. Поэтому алгоритм рекурсивно подразделяет плоскость (х,y), используя многоугольник, нарушивший порядок, в качестве нового отсекающего многоугольника. Отсечению подлежат многоугольники из внутреннего списка, причем старый отсекающий многоугольник теперь сам будет подвергнут отсечению новым отсекающим многоугольником. Подчеркнем, что новый отсекающий многоугольник является копией исходного многоугольника, а не его остатка после первого отсечения. Использование копии неотсеченного многоугольника позволяет минимизировать число разбиений.

Обобщение: отсечение отрезка выпуклым окном

отсечение параметрически заданного отрезка прямоугольным окном

Параметрическое уравнение отрезка от Р1 до Р2 имеет вид P(t) = P1 + (P2 - P1)t      0 <= t <= 1 где t - параметр. Если 0 ≤ t ≤ 1, то получается отрезок, а не бесконечная прямая. В двумерной декартовой системе координат x(t) = x1 + (х2 - x1)t      0 <= t <= 1       y(t) = y1 + (y2 - y1)t      0 <= t <= 1  

Для прямоугольного отсекающего окна :

одна из координат пересечения отрезка с каждой стороной известна.

Нужно вычислить только вторую координату:

t = (Р(t) - Р1) / (P2 - P1).

Если решения дают значения t за пределами интервала 0 ≤ t≤ 1,

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

Свето-теневой анализ. Модификации методов

Метод теневого буфера.

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

Алгоритм позволяет изображать сцены с полным затенением

1. Сцена рассматривается из точки расположения источника света в соответствующей системе координат. Итогом построения является полностью заполненный теневой буфер.

2. Сцена рассматривается с точки зрения наблюдателя, применяется обычный метод Z-буфера с небольшим дополнением:

   • Если точка является видимой в этой системе координат, то вычисляются ее координаты в системе, связанной с источником света - ,

   • затем проверяется, является ли точка видимой с этой позиции. Для этого значение сравнивается со значением, содержащимся в теневом буфере для этой точки, и в случае видимости значение интенсивности заносится в буфер кадра в точке.

Модификации алгоритма Вейлера-Азертона

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

1. Определяются грани, видимые из точки расположения источника света. Запоминается информация только о видимых гранях. Поскольку анализ выполняется в системе координат, связанной с источником света, то полученные видимые многоугольники затем заново приводятся к исходной системе координат. Многоугольники связываются с гранями, которым они принадлежат

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