33. Алгоритм, использующий список приоритетов. - chrislvt/CG GitHub Wiki

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

Далее в качестве примера будем рассматривать работу этого алгоритма на примере многоугольников P и Q.

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

Алгоритм

  1. Отсортировать многоугольники сцен в кадре в порядке возрастания Z
  2. Построить самый дальний многоугольник, если он не экранирует другие многоугольники (Zmax(A)<Zmin(B))
  3. Проверить, экранирует ли многоугольник P многоугольник Q при Zmax(P)>Zmin(Q). Если на один из тестов даётся положительный ответ P заносится в буфер кадра (P не экранирует Q). Если все -, то P и Q меняются местами, позиция Q помечается, тесты повторяются снова. Если вновь попытка менять местами, то P разрезается плоскостью, несущей Q, исходный многоугольник удаляется из списка, а его части заносятся в список. Тесты повторяются снова.
    1. верно ли, что прямоугольные объемлющие оболочки P и Q не перекрываются по X?
    2. верно ли, что прямоугольные объемлющие оболочки P и Q не перекрываются по Y?
    3. верно ли, что P целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения (рис. слева для P,Q)
    4. верно ли, что Q целиком лежит по ту сторону плоскости, несущей P, которая расположена ближе к точке наблюдения (рис. справа для P,Q)
    5. верно ли, что проекции P и Q не перекрываются

(Пример объемлющей прямоугольной оболочки для фигуры, оболочка - бирюзовая)

Работа алгоритма для изображения выше(вид сверху на объекты)

Для левого изображения Проверка (Zmax(P) < Zmin(Q) не выполняется)

Переходим к шагу 3

  1. Пересечение оболочек по оси x имеется
  2. Пересечение по y по рисунку узнать невозможно
  3. Для левого рисунка, выполняется условие 3. Следовательно, с уверенностью можно сказать, что P не может экранировать Q

Для правого рисунка:

Не выполняется и 3-я проверка, но выполняется 4 ая, аналогично P не может экранировать Q


Для проверок 3,4 можно проверять функцией f=Ax+By+Cz+D, где A, B, C – коэффициенты пробной плоскости U. В f подставляются координаты вершин испытуемого многоугольника W. Если знаки f для вершин совпадают и + или =0, то W находится с дальней стороны от плоскости U. Если знаки совпадают и отрицательны или равны 0, то W расположен с ближней стороны от U.


При циклическом экранировании (пример)

Используем алгоритм Сазерленда - ХоджМена(объясняем на примере справа). Для многоугольнка P, используем плоскость несущую Q как отсекатель, при этом, каждое ребро P отсекаем по алгоритму Кируса-Бека, в итоге получаем два многоугольника. Тот что, левее имеет приоритет над Q, тот что правее, экранируется многоугольником Q(многоугольники разделяются прерывистой линией, пример рассмотрен на многольниках справа на картинке)