14. Алгоритм Кэтмула

Данный алгоритм представляет собой буфер кадра. Обычный буфер кадра хранит коды цвета.

Идея алгоритма состоит в том, чтобы дополнительно для каждого пикселя хранить координату z(глубину). При занесении очередного пикселя в буфер файла значение его z корд. сравнивается с координатами пикселя кот.уже находится в буфере. Если z координата нового пикселя > чем координата старого, т.е. он ближе к наблюдателю, то атрибуты нового пикселя и его z координаты заносятся в буфер. Если нет, то ничего не изменяется. Этот алгоритм наиболее простой из всех алгоритмов удаления поверхностей, но требует большого объема памяти. Время работы не зависит от сложности сцен. Основной недостаток алгоритма – это дополнительные затраты памяти. Для их уменьшения можно разбивать изображение на неск.многоуг. или полос. Др.недостатком явл. то как пикселы заносятся в буфер (в произвольном порядке). В связи с чем возникают трудности с реализацией эффекта прозрачности или просвечивания и устранение лестничного эффекта. В целом данный алгоритм можно записать в след.виде:

1. Заполнить буфер кадра знач.цвета;

2. Зап-ть z буфер миним. знач. глубины;

3. Преобраз. изображение объекта в растр. форму в произв. порядке;

4. Для каждого объекта:

4.1. для каждого пиксела образа вычислить его глубину;

4.2. сравнить знач.глубины пиксела со знач. глубины хранящ. в z буфере этой же позиции;

4.3. Если знач.глубины пиксела > знач.глубины хранящ. в z буфере, то занести атрибуты пиксела в атрибуты кадра и заменить знач. глубины в z буфере на знач. глубины в z пикселе в противном случае никаких действий не производить.

15. Алгоритм Вейлера-Азертона

Данный алгоритм работает в объектном пространстве и рез-м его работы явл. многоуг. В общем виде он состоит из 4 шагов:

1. Предварительная сортировка по глубине;

2. Отсечение по границе ближайшего к точке наблюдения многоуг. наз-ая сортировкой многоуг. на плоскости.

3. Удаление многоуг. экранируемых более близкими к точке наблюдения многоуг;

4. Если требуется, то рекурсивное разбиение и новая сортировка.

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

16. Алгоритм Робертса

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

Идентификация i-й грани заключается в оценке угла видимости _i= N_i S_i между векторами наблюдателя S_i и внешней нормали N_i. Ячейка является лицевой при остром угле видимости, и это быстро определяется из условия N_i ◦ S_i > 0 без вычисления самого угла. Порядок вывода лицевых граней произволен.

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

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

Незамкнутая выпуклая каркасная поверхность также может быть изображена модифицированным методом Робертса, если внутренним сторонам ячеек присвоить высший приоритет и определять их видимость по правилу N_i ◦ S_i < 0, где N_i – внешняя нормаль к плоскости i-й ячейки.