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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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