- •А.И. Дружинин алгоритмы компьютерной графики
- •Часть 2
- •Удаление невидимых линий и поверхностей.
- •Введение
- •1. Алгоритм плавающего горизонта
- •2. Алгоритм Робертса
- •3. Алгоритм Варнока
- •4. Алгоритмы, использующие z – буфер
- •5. Алгоритм Вейлера – Азертона
- •6. Алгоритмы, использующие список приоритетов
- •7. Алгоритм Ньюэла – Ньюэла – Санча для случая многоугольников
- •Литература
- •Оглавление
4. Алгоритмы, использующие z – буфер
Алгоритм работает в пространстве изображения, и впервые был предложен Кэтмулом. Этот алгоритм является одним из самых простейших, но за все надо платить, в частности, объемом используемой памяти. z-буфер используется для запоминания глубины (координата Z) каждого пиксела на экране. Атрибуты каждого пиксела (цвет, интенсивность) запоминаются при этом в буфере кадра. В процессе работы глубина (или значение координаты Z) каждого нового пиксела сравниваются с глубиной того пиксела, который уже занесен в буфер кадра. Если сравнение показывает, что “новый” пиксел расположен впереди “старого” (по отношению к наблюдателю), то он заносится в буфер кадра и, кроме того, происходит корректировка z-буфера новым значением. Если нет, то ничего не происходит.
При этом:
сцены могут быть любой сложности;
заносить значения, то есть рассматривать элементы сцены, можно в произвольном порядке;
автоматически решается задача удаления невидимых линий и поверхностей;
автоматически можно получить сечение поверхностей, заменив сравнение
Z(X,Y) > Zбуфера(X,Y),
на сравнение
Z(X,Y) > Zбуфера(X,Y) & Z(X,Y) ≤ Zсечения,
где Zсечения - глубина искомого сечения.
Недостатки метода:
большой объем памяти;
трудоемкость устранения лестничного эффекта;
трудности при реализации эффектов прозрачности и просвечивания.
Формальная запись алгоритма:
заполнить буфер кадра фоновым значением цвета и интенсивности;
заполнить z-буфер минимальным значением;
преобразовать каждый многоугольник сцены в растровую форму в произвольном порядке;
для каждого пиксела многоугольника вычислить его глубину Z(X,Y);
сравнить глубину со значением Zбуфера(X,Y);
если Z(X,Y) > Zбуфера(X,Y), то записать атрибуты этого многоугольника в буфер кадра и заменить Zбуфера(X,Y) на Z(X,Y), иначе, никаких действий не производить.
Для уменьшения объема используемой памяти используется специальный случай использования z-буфера. В этом случае используется окно визуализации высотой в 1 сканирующую строку и ширину, равную ширине экрана. И алгоритм заключается в следующем:
заполнить буфер кадра (шириной в одну строку) фоновым значением цвета и интенсивности;
заполнить z-буфер (шириной в одну строку) минимальным значением;
вычислить пересечения сканирующей строки с двумерной проекцией каждого многоугольника (срез в горизонтальной плоскости);
эти пересечения образуют пары (см. [1]);
далее – как и в обычном алгоритме с использованием z-буфера.
Для увеличения эффективности алгоритма можно воспользоваться списком активных ребер (САР). Наконец, введя понятие интервалов можно уменьшить число вычислений. И интервальный алгоритм построчного сканирования состоит в следующем: необходимо выбрать видимый отрезок в интервалах, полученных путем деления сканирующей строки проекциями точек пересечения ребер и концов ребер. Всего возможны три варианта (рис. 4.1).
Вариант 1 (рис. 4.1, а):
интервалы 1 и 5 пусты – заполняем цветом фона;
интервалы 2 и 4 содержат только один отрезок - заполняем цветом этого отрезка;
интервал 3 содержит несколько отрезков, вычисляем ближайший (максимальное значение Z) и заполняем цветом ближайшего отрезка.
Вариант 2 (рис. 4.1, б) – концы отрезков касаются, но отрезки не проникают друг в друга. В данном случае в интервале 3 вычисляют глубины в центре интервала, находят отрезок с максимальным значением Z и затем заполняют буфер.
Вариант 3 (рис. 4.1, в) – многоугольники протыкают друг друга. Здесь учитываются не только проекции точек пересечения со сканирующей строкой, но и проекции точек их попарного пересечения. И в интервалах 3 и 4 необходимо вычисление глубины в середине интервалов.
Рис. 4.1. Интервальный алгоритм