Алгоритмы, использующие список приоритетов

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

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

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

Основной недостаток алгоритма – большой объём требуемой памяти.

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

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

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

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

- для каждого пиксела (x,y) в многоугольнике вычислить его глубину z (x,y);

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

- если z (x,y) > Z-буфера (x,y), то записать атрибут пиксела этого многоугольника (интенсивность, цвет) в буфер кадра и заменить Z-буфер (x,y) на z (x,y);

- в противном случае никаких действий не производить.

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

Если такой список окончателен, то никакие два элемента не будут взаимно перекрывать друг друга. Тогда можно записать все элементы в буфер кадра поочерёдно, начиная с элемента, наиболее удалённого от точки наблюдения. Более близкие к наблюдателю элементы будут затирать информацию о более далёких элементах в буфере кадра. Поэтому задача об удалении невидимых поверхностей решается тривиально.

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

Алгоритм работает как в пространстве объекта, так и в пространстве изображения. В частности, формирование списка приоритетов ведётся в пространстве объекта, а результат заносится в буфер кадра в терминах пространства изображения.