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

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

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

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

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

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

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

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

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

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

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

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

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