Алгоритм Ньюэла-Ньюэла-Санча

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

Для простых элементов сцены этот метод иногда называют алгоритмом художника, так как он похож на способ, каким художник создает картину. Сначала художник рисует фон, затем предметы, лежащие на среднем расстоянии, и, наконец, передний план. Тем самым художник решает задачу об удалении невидимых поверхностей, или задачу видимости, путем построения картины в порядке обратного приоритета.

Алгоритм Ньюэла, Ньюэла, Санча состоит из трех шагов:

• 1. Формирование предварительного списка приоритетов по глубине. В качестве ключа сортировки используется значение z_min каждого многоугольника. Первым в списке будет многоугольник с минимальным значением z_min. Этот многоугольник лежит дальше всех от точки наблюдения, расположенной в бесконечности на положительной полуоси z.
• 2. Разрешение всех противоречий и построение окончательного списка многоугольников.
• 3. Преобразование многоугольников в растровую форму и вывод их в порядке увеличения расстояния от наблюдателя.

Наиболее сложным и трудоемким является второй этап. В сложных сценах предварительная сортировка может давать много ошибок. Так многоугольник, имеющий меньшее значение z_min может экранировать многоугольник, имеющий большее значение z_min. Подобная ситуация приведена на рисунке 8.5, где многоугольник Р частично экранирует многоугольник Q и следовательно должен попасть в буфер кадра позже его.

Рисунок 8.6 Экранирование многоугольников.

Существуют и более сложные ситуации, которые не могут быть решены простой перестановкой многоугольников. Рисунок 8.6 показывает случаи циклического и взаимного перекрытия многоугольников. Решение в данном случае лежит в разбиении исходных многоугольников на части. Например, при взаимном перекрытии, многоугольник d может быть рассечен на две части плоскостью несущей многоугольник e.

Рисунок 8.6 Циклическое и взаимное экранирование многоугольников

Наличие экранирования определяется с помощью серии тестов проводящихся на основе списка полученного при предварительной сортировке. Для тестов выбираются два многоугольника P и Q. Через Р обозначается самый удаленный многоугольник, а через Q следующий в списке многоугольник. Для каждого многоугольника Р из списка надо проверить его отношение с Q:

1. если ближайшая вершина Р (Рz_max) будет дальше от точки наблюдения, чем самая удаленная вершина Q (Qz_min), т.е. Qz_min >= Рz_max то никакая часть Р не может экранировать Q. Занести Р в буфер кадра (рис. 8.7, а);

2. если Qz_min < Рz_max потенциально P экранирует не только Q, но также и любой другой многоугольник типа Q из списка, для которого Qz_min < Рz_max. Тем самым образуется множество [Q]. Однако, Р может фактически и не экранировать ни один из этих многоугольников. Если последнее верно, то Р можно заносить в буфер кадра. Для ответа на этот вопрос используется серия тестов, следующих по возрастанию их вычислительной сложности. Эти тесты ниже формулируются в виде вопросов. Если ответ на любой вопрос будет положительным, то Р не может экранировать Q и Р может быть занесен в буфер кадра. Тесты формулируются следующим образом:

a. Верно ли, что прямоугольные объемлющие оболочки Р и Q не перекрываются по х ?

b. Верно ли, что прямоугольные оболочки Р и Q не перекрываются по у ?

c. Верно ли, что Р целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения (рис.8.7,б).

d. Верно ли, что Q целиком лежит по ту сторону плоскости, несущей P, которая ближе к точке наблюдения (рис. 8.7, в).

e. Верно ли, что проекции Р и Q не перекрываются?

Рисунок 8.7 Проверка экранирования.

• Если на все вопросы получены отрицательные ответы то предполагается, что Р закрывает Q. Многоугольники Р и Q меняются местами и отмечается факт постановки многоугольника Q в позицию P. Все тесты выполняются повторно.
• Если, в ходе дальнейшей работы алгоритма, делается попытка повторно установить некоторый многоугольник в позицию P, то это говорит о наличии циклического или взаимного экранирования. В этом случае Р разрезается плоскостью, несущей Q, исходный многоугольник Р удаляется из списка, а его части заносятся в список. Затем тесты повторяются для нового списка. Этот шаг предотвращает зацикливание алгоритма.

Поиск по сайту: