Главная » Информационные системы » Компьютерная геометрия и графика » 11.Удаление невидимых линий и поверхностей Алгоритмы Варнока и Вейлера-Азертона.

11.Удаление невидимых линий и поверхностей Алгоритмы Варнока и Вейлера-Азертона.

Алгоритм Варнока (1968)

Этот вариант при удачном выборе\ разбиения пропорционален n.

Разобъем видимую часть картинной плоскости на 4 равные части. В случаях, когда часть полностью накрывается проекцией ближайшей грани и часть не накрывается проекцией ни одной грани – вопрос ясен.

В случае, когда ни одно из условий не выполнено, данная часть разбивается опять на 4 и.т.д.

v:shapes=Рисунок_x0020_398

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

  Алгоритм Вейлера-Азертона (Weiler-Atherton)

  Разбиение картинной плоскости можно производить не только прямыми, параллельными координатным осям, но и по границам проекций граней. В результате получается точное решение задачи.

Предлагаемый метод работает с проекциями граней на картинную плоскость.

В качестве первого шага производится сортировка всех граней по глубине (front-to-back).

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

Таким образом, получаются два множества граней: Fin – грани, проекции которых содержатся в проекции грани A (сюда входит и сама грань A), и Fout – грани, проекции которых не имеют общих внутренних точек с проекцией грани A.

Множество Fin обычно называют множеством граней, внутренних по отношению к A.

Однако во множестве Fin  могут быть грани, лежащие к наблюдателю ближе, чем сама грань A (это возможно, например, при циклическом наложении граней). В этом случае каждая такая грань используется для разбиения всех граней из множества Fin (включая исходную грань A). Когда рекурсивное разбиение завершится, то все грани из первого множества выводятся из набора оставшихся граней (их уже ничто не может закрывать). Затем из набора оставшихся граней Fout берется очередная грань и процедура повторяется.

  Рассмотрим простейший случай для двух граней A и B (рис. 5.18).

 

v:shapes=Рисунок_x0020_400

 

Рис. 5.18. Пример разбиения граней

  Будем  считать, что грань A расположена ближе, чем грань B. Тогда на первом шаге для разбиения используется именно грань A. Грань B разбивается на две части. Часть B1 попадает в первое множество Fin и, так как она лежит дальше грани A, удаляется.

  После этого выводится грань A и в списке оставшихся граней остается только грань B2. Так как кроме нее других граней не осталось, то эта грань выводится, и на этом работа завершается.

Алгоритм Вейлера-Азертона (Weiler-Atherton)

  Разбиение картинной плоскости можно производить не только прямыми, параллельными координатным осям, но и по границам проекций граней. В результате получается точное решение задачи.

Предлагаемый метод работает с проекциями граней на картинную плоскость.

В качестве первого шага производится сортировка всех граней по глубине (front-to-back).

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

Таким образом, получаются два множества граней: Fin – грани, проекции которых содержатся в проекции грани A (сюда входит и сама грань A), иFout – грани, проекции которых не имеют общих внутренних точек с проекцией грани A.

Множество Fin обычно называют множеством граней, внутренних по отношению к A.

Однако во множестве Fin  могут быть грани, лежащие к наблюдателю ближе, чем сама грань A (это возможно, например, при циклическом наложении граней). В этом случае каждая такая грань используется для разбиения всех граней из множества Fin (включая исходную грань A). Когда рекурсивное разбиение завершится, то все грани из первого множества выводятся из набора оставшихся граней (их уже ничто не может закрывать). Затем из набора оставшихся граней Fout берется очередная грань и процедура повторяется.

  Рассмотрим простейший случай для двух граней A и B (рис. 5.18).

 

 

Рис. 5.18. Пример разбиения граней

  Будем  считать, что грань A расположена ближе, чем грань B. Тогда на первом шаге для разбиения используется именно грань A. Грань Bразбивается на две части. Часть B1 попадает в первое множество Fin и, так как она лежит дальше грани A, удаляется.

  После этого выводится грань A и в списке оставшихся граней остается только грань B2. Так как кроме нее других граней не осталось, то эта грань выводится, и на этом работа завершается.


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.

Поделиться

Дисциплины