Алгоритм Ньюэла-Ньюэла-Санча для случая многоугольников

Сформировать предварительный список приоритетов по глубине, используя в качестве ключа сортировки значение zmin для каждого многоугольника. Первым в списке будет многоугольник с минимальным значением zmin. Этот многоугольник лежит дальше всех от точки наблюдения, расположенной в бесконечности на положительной полуоси z. Обозначим его через P, а следующий в списке многоугольник - через Q. Для каждого многоугольника P из списка надо проверить его отношение с Q.

Если ближайшая вершина Р ( ) будет дальше от точки наблюдения, чем самая удаленная вершина Q ( ), т. е. ≥ никакая часть P не может экранировать Q. Занести Р в буфер кадра (см. рис. 8.14, а).

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

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

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

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

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

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

 

z
x
z
x
P
Q
P
Q
b
a

Рис. 8.16. Тесты для перекрывающихся многоугольников

Каждый из этих тестов применяется к каждому элементу {Q}. Если ни один из них не дает положительного ответа и не заносит Р в буфер кадра, то Р может закрывать Q.

Поменять Р и Q местами, пометив позицию Q в списке. Повторить тесты с новым списком. Это дает положительный результат для сцены с рис. 8.14, b.

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