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

• Алгоритмы, использующие список приоритетов, пытаются получить преимущество предварительной сортировкой по глубине или приоритету.
• На выходе (после сортировки) получаем окончательный список элементов сцены, упорядоченных по приоритету глубины, основанному на расстоянии от точки наблюдения.
• Если список окончателен, то никакие два элемента не будут перекрывать друг друга.
• Эффекты прозрачности можно включить в состав алгоритма путем частичной корректировки содержимого буфера кадра.
• Такие алгоритмы работают как в пространстве объекта, так и в пространстве изображения.

Основная проблема

• Для простых сцен, список приоритетов мы можем получить сразу.
• Однако, есть сцены, для которых невозможно получить результат простой сортировкой по z.
• Может случится так, что объекты циклические прерывают друг друга.

Решение проблемы (не циклического прерывания)

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

Алгоритм (из Роджерса)

Называется алгоритмом Ньюэла - Ньюэла - Санча.

1. Сформировать предварительный список приоритетов по глубине, используя в качестев
   ключа сортировки zmin, для каждого многоугольника. Первый многоугольник в списке -
   с минимальным zmin. Он будет лежать дальше всех от точки наблюдения. Обозначим его P,
   следующий в списке - Q.
2. Для каждого P из списка проверить отношение с Q.
   2.1. Если ближайшая вершина P(P zmax) дальше от точки наблюдения чем самая удаленная
        Q(Qzmin) (Qzmin >= Pzmax), то никая часть P не может экранировать Q. Занести P
        в буффер кадра.
   2.2. Иначе (если Qzmin < Qzmax), то P потенциальное экранирует не только Q, но и любой
        другой многоугольника типа Q из списка для которого Qzmin < Pzmax. Образуется
        множество { Q }. Однако, P может фактически и не экранировать ни один из этих 
        многоугольников. Если последнее верно, то P заносим в буфер кадра. Для ответа 
        на этот вопрос, используется серия тестов. Если ответ на любой вопрос положительный,
        то P не может экранировать { Q }, P заносится в буффер кадра.

Те самые тесты

Расположены эти тесты по возрастанию их вычислительной сложности.

Тут вообще можно дохуя всего написать по поводу этих тестов. Но я не буду, это пиздец какой то.

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

Тут нужно разбиение. Для разбиения многоугольников вдоль линии пересечения несущих этих многоугольников можно воспользоваться алгоритмом Сазерланда - Ходжмена.

РАССМАТРИВАЕМ КАРТИНКУ РАСПОЛОЖЕННУЮ СПРАВА.

Плоскость, несущая Q, используется как секущая. Каждое ребро Р отсекается Q (полностью), при этом формируются два новых многоугольника. Для поиска пересечения можно воспользоваться алгоритмом Кируса-Бека.

Тот, что слева, имеет приоритет над Q. А справа - наоборот, экраниризируется Q.

Оценка эффективности

• Может нехватить мощности ЭВМ для динамического вычисления.
• В большинстве случаев, картинка статична. Можно предварительно вычислять некоторые более общие приоритетные характеристики (алгоритм Шумейкера, там вообще шок какой-то).

Следующий вопрос: 34. Алгоритм построчного сканирования, использующий Z буфер. Интервальные методы построчного сканирования (основные предпосылки).

Предыдущий вопрос: 32. Алгоритм, использующий Z буфер.