Skip to content

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

Jump to bottom
Dmitry edited this page Jun 23, 2022 · 2 revisions

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

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

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

Алгоритм

  1. Отсортировать многоугольники сцен в кадре в порядке возрастания Z_min
  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(многоугольники разделяются прерывистой линией, пример рассмотрен на многольниках справа на картинке)

Clone this wiki locally