34. Алгоритм, использующий список приоритетов (алгоритм Художника)

В основе алгоритма способ изображения сцены от дальних объектов к ближним.

Алгоритм

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? по Y?
   2. верно ли, что P целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения
   3. верно ли, что Q целиком лежит по ту сторону плоскости, несущей P, которая расположена ближе к точке наблюдения
   4. верно ли, что проекции P и Q не перекрываются

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