Алгоритм, использующий z буфер

Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом. Работает этот алгоритм в пространстве изображения. Идея z-буфера является простым обобщением идеи о бу­фере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пиксела в простран­стве изображения, z-буфер - это отдельный буфер глубины, используемый для запоминания координаты z или глубины каждого видимого пиксела в пространстве изображения. В процессе работы глубина или значение z ка­ждого нового пиксела, который нужно зане­сти в буфер кадра, сравнивается с глубиной того пиксела, который уже занесен в z-бу­фер. Если это сравнение показывает, что новый пиксел расположен впереди пиксела, на­ходя­щегося в буфере кадра, то новый пиксел заносится в этот буфер и, кроме того, про­изводится корректировка z-бу­фера новым значением z. Если же сравнение дает противоположный результат, то никаких действий не произво­дится. По сути, алгоритм является поиском по х и у наибольшего значения функции z (х, у).

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

Основной недостаток алгоритма - большой объем требуемой памяти. Если сцена под­вергается видовому преоб­разованию и отсекается до фиксированного диапазона коорди­нат z значений, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (х, y); обычно бывает достаточно 20 бит. Буфер кадра разме­ром 512х512х24 бит в комбинации с z-буфером размером 512х512х20 бит требует почти 1.5 мегабайт памяти. Однако снижение цен на память делает экономически оправданным создание специализированных запоминающих уст­ройств для z-буфера и связанной с ним аппаратуры.

Альтернативой созданию специальной памяти для z-буфера является использование для этой цели оперативной или массовой памяти. Уменьшение требуемой памяти достигается разбиением пространства изображения на 4, 16 или больше квадратов или полос. В предельном варианте можно использовать z-буфер размером в одну строку раз­вертки. Для последнего случая имеется интересный алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование z-бу­фера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены. Однако сортировка на плоскости, позволяющая не обрабатывать все многоуголь­ники в каждом из квадратов или полос, может значительно сократить этот рост.

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

Формальное описание алгоритма z-буфера таково:

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

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

3. Преобразовать каждый многоугольник в растровую форму в произвольном по­рядке.

4. Для каждого Пиксел(x,y) в многоугольнике вычислить его глубину z(x,y).

5. Сравнить глубину z(х,у) со значением Zбуфер(х,у), хранящимся в z-буфере в этой же позиции.

Если z(х, у) > Zбуфер (х,у), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер(х,у) на z(х,у). В противном случае никаких действий не производить.

На псевдокоде алгоритм можно представить так: