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

• Сформировать предварительный список приоритетов по глубине, используя в качестве ключа сортировки значение z_min для каждого многоугольника. Первым в списке будет многоугольник с минимальным значением z_min. Этот многоугольник лежит дальше всех от точки наблюдения, расположенной в бесконечности на положительной полуоси z. Обозначим его через P, а следующий в списке многоугольник — через Q.
• Для каждого многоугольника P из списка надо проверить его отношение с Q:
• если ближайшая вершина P (Р_Zmax) будет дальше от точки наблюдения, чем самая удаленная вершина Q (Q_Zmin), то есть Q_Zmin >= P_Zmax, то никакая часть P не может экранировать Q. Занести P в буфер кадра рис. 22.1a;
• если Q_Zmin < P_Zmax то P потенциальное экранирует не только Q, но также и любой другой многоугольник типа Q из списка, для которого Q_Zmin < P_Zmax. Тем самым образуется множество {Q}. Однако P может фактически и не экранировать ни один из этих многоугольников. Если последнее верно, то P можно заносить в буфер кадра. Для ответа на этот вопрос используется серия тестов, следующих по возрастанию их вычислительной сложности. Эти тесты ниже формулируются в виде вопросов. Если ответ на любой вопрос будет положительным, то P не может экранировать {Q}. Поэтому P сразу же заносится в буфер кадра. Вот эти тесты:
• Верно ли, что прямоугольные объемлющие оболочки P и Q не перекрываются по x?
• Верно ли, что прямоугольные оболочки P и Q не перекрываются по y?
• Верно ли, что P целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения (рис. 22.3a)?
• Верно ли, что Q целиком лежит по ту сторону плоскости, несущей P, которая ближе к точке наблюдения (рис. 22.3b)?
• Верно ли, что проекции P и Q не перекрываются?

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

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

Взятые вместе, первые два из приведенных выше вопросов образуют обычный габаритный тест для прямоугольных оболочек. Поскольку многие сцены не являются квадратными, то прямоугольные объемлющие оболочки будут с большей вероятностью перекрываться в одном из двух возможных направлений. Когда многоугольники преимущественно горизонтальны или вертикальны, то использование одного из этих двух тестов оказывается более эффективным. В алгоритме в той форме, в которой он записан выше, предполагается, что ширина сцены больше ее высоты, то есть многоугольники преимущественно являются горизонтальными. Если высота сцены больше ее ширины, то тесты следует поменять местами. Если же сцена является квадратной или ее структура изоморфна, то порядок применения этих тестов не имеет значения.

Третий и четвертый тесты можно реализовать с использованием некоторых из ранее обсуждавшихся тестов видимости. Поскольку уравнение несущей плоскости или нормаль к ней часто известны для каждого многоугольника, то удобно применить простой тест подстановки. Если исследуется отношение многоугольника Q к многоугольнику P, то координаты вершин Q подставляются в уравнение плоскости, несущей P. Если все знаки результатов подстановки совпадают, то Q целиком лежит по одну сторону от P. Здесь, так же как и в других алгоритмах удаления невидимых поверхностей, обсуждавшихся ранее, если это нужно, производится предварительное удаление нелицевых граней. Более полно эти соображения проиллюстрирует пример 1 для случая многоугольников, конфликтующих в пространстве.

Пример 1. Проверка отношений между многоугольниками, конфликтующими в пространстве. Рассмотрим три треугольника: P, Q₁ и Q₂ (рис. 22.4). Вершины этих треугольников таковы:
Р: (1, 1, 1), (4, 5, 2), (5, 2, 5)
Q₁: (2, 2, 0.5), (3, 3, 1.75), (6, 1, 0.5)
Q₂: (0.5, 2, 5.5), (2, 5, 3), (4, 4, 5).

Требуется определить, верно ли, что Q₁ и Q₂ целиком лежат по одну сторону от P. Три ортогональные проекции, показанные на рис. 22.4, не дают ясного ответа. Уравнение плоскости треугольника P имеет вид
15x - 8y - 13z + 6 = 0.

Пробная функция Т.F. равна
T.F. = 15x - 8y -13z + 6.

Подстановка вершин Q₁ в пробную функцию дает:
T.F.₁ = 15(2) - 8(2) - 13(0.5) + 6 = 13.5 > 0
T.F.₂ = 15(3) - 8(3) - 13(1.75) + 6 = 4.25 > 0
T.F.₃ = 15(6) - 8(1) - 13(0.5) + 6 = 81.5 > 0.

Поскольку знаки всех пробных функций положительны, то треугольник Q₁ целиком лежит по одну сторону от P.

Подставляя вершины Q₂ в пробную функцию, имеем:
T.F.₄ = 15(0.5) - 8(2) - 13(5.5) + 6 = -74 < 0
T.F.₅ = 15(2) - 8(5) - 13(3) + 6 = -43 < 0
T.F.₆ = 15(4) - 8(4) - 13(5) + 6 = -31 < 0.

Вновь знаки всех пробных функций совпали; поэтому треугольник Q₂ целиком лежит по одну сторону от Р.

На рис. 22.4d хорошо видно, что Q₁ лежит по ту сторону от плоскости треугольника P, которая дальше от точки наблюдения, расположенной в бесконечности на положительной полуоси z. Следовательно, Q₁ частично экранируется P. На рис. 22.4d также хорошо видно, что Q₂ лежит по ту сторону от плоскости треугольника P, которая ближе к указанной точке наблюдения. Поэтому Q₂ частично экранирует P.

Из приведенного примера следует, что:

• если знаки пробной функции для всех вершин некоего многоугольника совпадают и положительны или равны нулю, то этот многоугольник находится с дальней (невидимой) стороны от плоскости P;
• если знаки пробной функции для всех вершин некоего многоугольника совпадают и отрицательны или равны нулю, то этот многоугольник расположен с ближней (видимой) стороны от плоскости P;
• если значения пробной функции для каждой вершины многоугольника равны нулю, то этот многоугольник лежит на плоскости P.

Последний тест из приведенной серии особенно сложен с вычислительной точки зрения, поскольку требует точного определения того факта, что проекции P и Q не пересекаются.

Если имеет место циклическое экранирование, то для разбиения многоугольников вдоль линии пересечения несущих эти многоугольники плоскостей можно воспользоваться алгоритмом отсечения многоугольников Сазерленда-Ходжмена. Здесь плоскость, несущая Q, используется как секущая. Каждое ребро P отсекается плоскостью Q, при этом формируются два новых многоугольника.

В алгоритме Ньюэла-Ньюэла-Санча делается попытка решить задачу удаления невидимых поверхностей динамически, путем обработки всех многоугольников сцены для каждого искомого кадра. Если же сцена сложна, а частота кадров велика, как у систем моделирования в реальном времени, то вычислительной мощности обычных универсальных ЭВМ может не хватить. Однако во многих случаях моделирования в реальном времени, например, при имитации посадки самолета, сцена статична, а меняется только точка наблюдения.

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

В алгоритме Шумейкера в сцене допустимы только выпуклые многоугольники. Такие многоугольники группируются в кластеры, которые являются линейно разделимыми. Кластеры считаются линейно разделимыми, если существует такая разделяющая плоскость, которая проходит между ними, не пересекая их. Несколько двумерных кластеров показано на рис. 22.5a. Разделяющие плоскости помечены буквами a и b. Они разбивают сцену на четыре области A, B, C, D. Точка наблюдения может располагаться в любой из этих областей. На рис. 22.5b показана древовидная структура, устанавливающая приоритеты кластеров в сцене. Эти приоритеты можно вычислить заранее для любой точки наблюдения в двумерной плоскости. Подстановка координат точки наблюдения в уравнения разделяющих плоскостей порождает соответствующий узел дерева кластерных приоритетов. Затем для каждого кластера в обратном порядке приоритетов решается задача удаления невидимых поверхностей.

Пример 2. Кластерные приоритеты. Предположим, что разделяющие плоскости a и b, показанные на рис. 22.5, пересекаются в начале координат. Далее предположим, что a — это плоскость y = 0, a b — плоскость y = x; обе плоскости перпендикулярны плоскости чертежа. Уравнения этих плоскостей и соответствующие им пробные функции таковы:
a: y = 0 (T.F.)₁ = y
b: y - x = 0 (T.F.)₂ = y - x

Точка наблюдения, лежащая на прямой 2y - x = 0, например (20, 10), дает:
(T.F.)₁ = 10 > 0
(T.F.)₂ = 10 - 20 = -10 < 0.

Значит, эта точка наблюдения лежит в области D. Из рис. 22.5b видно, что список кластерных приоритетов таков: 3, 1, 2.

Кластеры используются для разбиения сцены. Простейшим кластером является единственный многоугольник. Кластеры могут представлять собой сложные полигональные или неполигональные поверхности и тела, для каждого типа которых существуют свои методы удаления невидимых линий.

В рамках кластеров некоторых типов приоритеты отдельных многоугольников не зависят от положения точки наблюдения. Это обстоятельство является одним из основных достоинств алгоритма Шумейкера. Оно позволяет заранее вычислять полный список приоритетов. На рис. 22.6a показан двумерный кластер, для которого можно заранее вычислить индивидуальные приоритеты многоугольников. Приоритет каждого многоугольника устанавливается в зависимости от возможности экранирования данным многоугольником любого другого многоугольника для произвольной точки наблюдения. Чем большее число многоугольников может экранировать данный многоугольник, тем выше его приоритет. При установлении приоритетов многоугольников в рамках кластера для заданной точки наблюдения прежде всего удаляются нелицевые многоугольники. Оставшиеся многоугольники располагаются затем в приоритетном порядке, как показано на рис. 22.6b и рис. 22.6c.

Алгоритмы, использующие список приоритетов, работают как в пространстве объекта, так и в пространстве изображения. В частности, формирование списка приоритетов ведется в пространстве объекта, а результат заносится в буфер кадра в терминах пространства изображения. Использование буфера кадра является критическим для данного алгоритма.

Алгоритмы, строящие список приоритетов, использующие z-буфер и относящиеся к типу Варнока, могут также применяться и для удаления невидимых линий. При их использовании в этом качестве ребра каждого многоугольника заносятся в буфер кадра с одним атрибутом, причем внутренняя область каждого многоугольника заносится в буфер кадра с атрибутом фона. При таком подходе многоугольники, которые находятся ближе к точке наблюдения, «заслоняют» ребра многоугольников, которые расположены дальше от нее.