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

Реклама на сайте

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


Это представитель класса алгоритмов основанных на точной сортировке по глубине. Если удается получить точно отсортированный список, то никакие два объекта не будут взаимно перекрывать друг друга.

 

  • Сформировать предварительный список приоритетов по глубине, используя в качестве ключа сортировки значение zmin для каждого многоугольника. Первым в списке будет многоугольник с минимальным значением zmin. Этот многоугольник лежит дальше всех от точки наблюдения, расположенной в бесконечности на положительной полуоси z. Обозначим его через Р, а следующий в списке многоугольник - через Q.
  • Для каждого многоугольника Р из списка надо проверить его отношение с Q:
  1. если ближайшая вершина Р (Рzmax) будет дальше от точки наблюдения, чем самая удаленная вершина Q (Qzmin), т.е. Qzmin >= Рzmax и никакая часть Р не может экранировать Q. Занести Р в буфер кадра (рис.1, а);
  2. если Qzmin < Рzmax потенциально P экранирует не только Q, но также и любой другой многоугольник типа Q из списка, для которого Qzmin < Рzmax. Тем самым образуется множество [Q]. Однако Р может фактически и не экранировать ни один из этих многоугольников. Если последнее верно, то Р можно заносить в буфер кадра. Для ответа на этот вопрос используется серия тестов, следующих по возрастанию их вычислительной сложности.

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

Вот эти тесты:

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

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

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

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

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

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

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

 

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

 

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

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

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



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем