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

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

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

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

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

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

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

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

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

 

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

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

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

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