Алгоритм Вейлера— Азертона | MetodPro.ru

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

Алгоритм Вейлера— Азертона


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

  • Предварительная сортировка по глубине.
  • Отсечение по границе ближайшего к наблюдателю многоуголь­ника, называемое сортировкой многоугольников на плоскости.
  • Удаление многоугольников, экранированных многоугольником, ближайшим к точке наблюдения.
  • Если требуется, то рекурсивное подразбиение и окончательная сортировка для устранения всех неопределенностей.

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

 

Рис. 4.44. Отсечение многоугольников по приоритетам для алгоритма удаления невидимых поверхностей Вейлера — Азертона.

В качестве отсекающего многоугольника используется копия первого многоугольника из предварительного списка приоритетов по глубине. Отсекаться будут остающиеся в этом списке многоугольники, включая и первый многоугольник. Вводятся два списка: внутренний и внешний.

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

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

Более полной иллюстрацией этого алгоритма послужит следую­щий простой пример

Рис. 4.46. Условие возникновения ошибочного результата в предварительной сортировке по z.

 

Заслуживает внимание еще одна дополнительная деталь этого алгоритма. Когда некоторый многоугольник циклически перекрывается с отсекающим, т. е. когда он лежит как впереди, так и позади отсекающего (рис. 4.48, а), то в рекурсивном разбиении необходимости нет. Дело в том, что все экранируемое циклическим многоугольником уже было удалено на предыдущем шаге отсечения. Необходимо лишь произвести отсечение исходного многоугольника по границам циклического многоугольника и изобразить результат. Ненужное рекурсивное разбиение можно предотвратить, если создать список многоугольников, которые уже использовались как отсекающие. Тогда, если при рекурсивном разбиении текущий отсекающий многоугольник появляется в этом списке, значит, обнаружен циклически перекрывающийся многоугольник. Следовательно, не требуется никакого дополнительного разбиения. Заметим, что данный алгоритм непосредственно обрабатывает случаи циклического перекрытия сразу нескольких многоугольников, как показано на рис. 4.48, b.



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

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