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

Начало данного алгоритма – алгоритм художника.

Основная схема алгоритма:

1. для каждого полигона сцены ищем zmin и zmax

2. сортируем все полигоны в порядке возрастания zmin

3. назовем самый первый левый полигон P, следующий – Q

4.

если <, то P и Q не перекрываются, выводим в растр P.

5. иначе >, если такие полигоны есть, то они образуют список, в этом списке полигоны Q могут экранировать полигоны P. Для выявления этой ситуации предлагается 5 тестов, на которые необходимо ответить да или нет.

Если в любом тесте будет дан ответ да, P выводим в растр.

Тесты:

1. верно ли, что габариты P и Q не пересекаются по оси x

2. верно ли, что габариты P и Q не пересекаются по оси y

3.

верно ли, что P целиком лежит по ту сторону плоскости, в которой лежит Q, которая находится дальше от камеры.

4.

верно ли, что полигон Q лежит целиком до плоскости, в которой лежит P

для выполнения 3, 4 теста необходимо воспользоваться тестовой функцией плоскости.

Пусть плоскость задана уравнением вида

Ax +By+Cz+D=0

T= Ax +By+Cz+D, подставляем координаты точки, если T>=0, то точка за плоскостью, иначе перед ней.

5. верно ли, что проекции полигонов P и Q не пересекаются

Если ни один из тестов не дает ответ “да”, то меняют местами в списке P и Q. После этого выполняют 5 тестов. Иногда это помогает. Если в этом случае не помогло, то произошло зацикливание. В этом случае P разбивает Q на 2 части P1 и P2. После разбиения переходим к первому пункту алгоритма.

Для повышения эффективности данного алгоритма необходимо предварительно убирать нелицевые полигоны.