Буфер глубины (depth buffer).

Алгоритм, использующий 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 (х,у ). В противном случае никаких действий не производить.

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

for all covered pixels

compare z

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

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

Рис. 8.11. Сканирующая строка по грани

Для рисунка y меняется от y 1 до y 2 и далее до y 3 , при этом для каждой строки определяется x a , z a , x b , z b :

x a = x 1 + (x 2 - x 1)× ;

x b = x 1 + (x 3 - x 1)× ;

z a = z 1 + (z 2 - z 1)× ;

z b = z 1 + (z 3 - z 1)× .

На сканирующей строке x меняется от x a до x b и для каждой точки строки определяется глубина z :

z = z a + (z b - z a )×

Реализация алгоритма вдоль сканирующей строки позволяет совместить алгоритм z -буфера с алгоритмами растровой развертки ребер и алгоритмами закраски грани.

Проиллюстрируем работу алгоритма на примере для рис. 8.12.

Рис. 8.12. Протыкающий треугольник

В начале в буфере кадра и в z -буфере содержатся нули. После растровой развертки прямоугольника содержимое буфера кадра будет иметь вид

Содержимое z -буфера таково:

При обработке треугольника преобразование его в растровую форму и сравнение по глубине дает новое значение буфера кадра:

Новое содержимое z -буфера таково.

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

Для реализации метода используются две области памяти: буфер глубины (Z -буфер) и буфер кадра (хранящий информацию о состоянии пикселов экрана компьютера). Буфер длины используется для хранения координаты Z (глубины) каждого видимого на данной стадии анализа изображения пиксела картинной плоскости. В буфере кадра запоминаются атрибуты (интенсивность и цвет) соответствующего пикселя.

Формально описание метода таково. Предположим, что сцена представлена в виде объединения многоугольников (возможно, пересекающихся). Построим ортогональную проекцию сцены на картинную плоскость .

Предполагается следующая последовательность шагов:

14.Особенности проекций гладких отображений

1-й случай

Заданная поверхность плоскость, описываемая уравнением Z = X и проектируемая на плоскость X = 0 (рис. 1).

Записав ее уравнение в неявном виде X-Z=0, Вектор L , вдоль которого осуществляется проектирование, имеет координаты

Вычислим координаты нормального вектора:

Скалярное произведение этих двух векторов отлично от нуля:

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

2-й случай

Заданная поверхность параболический цилиндр с уравнением Z = X2 или, что то же, X2 - Z = 0. Нормальный вектор ортогонален вектору проектирования L в точках оси Y. Это вытекает из того, что .

Здесь, в отличие от первого случая, точки плоскости X = 0 разбиваются на три класса: к первому относятся точки (Z > 0), у которых два прообраза (на рис. 2 этот класс заштрихован); ко второму те, у которых прообраз один (Z = 0);

к третьему классу относятся точки, у которых прообразов на цилиндре нет вовсе. Прямая X = 0, Z = 0является особой. Вдоль нее векторы N ρ и L ρ ортогональны. Особенность этого типа называется складкой .

3-й случай

Рассмотрим поверхность, заданную уравнением X 3 + XY - Z = 0.

Пусть Y = 1 . Тогда Z = X 3 + X (рис. 3).

При Y = 0 имеем: Z = X 3 (рис. 4).

рис.3

рис. 4

Наконец, при Y = 1 получаем: Z = X 3 - X (рис. 5).

рис. 5

Построенные сечения дают представление обо всей поверхности. Поэтому нарисовать ее теперь уже несложно (рис. 6).

16.Растровая развертка отрезка

Для горизонтальных, вертикальных и наклоненных под углом 45°. отрезков выбор растровых элементов очевиден. При любой другой ориентации выбрать нужные пиксели труднее. Общие требования к изображению отрезка:

· концы отрезка должны находиться в заданных точках;

· отрезки должны выглядеть прямыми,

· яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона.

Ни одно из этих условий не может быть точно выполнено на растровом дисплее в силу того, что изображение строится из пикселей конечных размеров, а именно:

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

· отрезок аппроксимируется набором пикселей и лишь в частных случаях вертикальных, горизонтальных и отрезков под 45  они будут выглядеть прямыми

· яркость для различных отрезков и даже вдоль отрезка в общем случае различна, так как, например, расстояние между центрами пикселей для вертикального отрезка и отрезка под 45  различно

Алгоритмы генерации отрезка:

1) Цифровой дифференциальный анализатор. Решается дифференциальное уравнение вида dY/dX = Py/Px, где Py = Yk - Yn - приращение координат отрезка по оси Y, а Px = Xk - Xn - приращение координат отрезка по оси X. При этом ЦДА формирует дискретную аппроксимацию непрерывного решения этого дифференциального уравнения. В обычном ЦДА, используемом, как правило, в векторных устройствах, тем или иным образом определяется количество узлов N, используемых для аппроксимации отрезка. Затем за N циклов вычисляются координаты очередных узлов. Получаемые значения X i , Y i преобразуются в целочисленные значения координаты очередного подсвечиваемого пикселя либо округлением, либо отбрасыванием дробной части. Генератор векторов, использующий этот алгоритм, имеет тот недостаток, что точки могут прописываться дважды, что увеличивает время построения. Кроме того из-за независимого вычисления обеих координат нет предпочтительных направлений и построенные отрезки кажутся не очень красивыми.

2) Алгоритм Брезенхема. Так как приращения координат, как правило, не являются целой степенью двойки, то в ЦДА-алгоритме требуется выполнение деления, что не всегда желательно, особенно при аппаратной реализации. Брезенхем предложил алгоритм, не требующий деления, как и в алгоритме несимметричного ЦДА, но обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка, как в алгоритме обычного ЦДА. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. а), а если угловой коэффициент > 1/2, то - в позицию (1,1) (рис. б). Для принятия решения куда заносить очередной пиксел вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки. Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.

3) Модифицированный алгоритм Брезенхема. Основная идея алгоритма состоит в том, чтобы для ребер многоугольника устанавливать яркость пикселя пропорционально площади пикселя, попавшей внутрь многоугольника.

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

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

В методах затравочного заполнения предполагается, что известна некоторая точка (затравка) внутри замкнутого контура. В алгоритмах ищут точки, соседние с затравочной и расположенные внутри контура. Если соседняя точка расположена не внутри контура, то значит, обнаружена граница контура. Если же точка расположена внутри контура, то она становится затравочной точкой и поиск продолжается рекурсивно. Подобные алгоритмы применимы только к растровым устройствам.

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

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

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

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

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

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

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

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

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

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

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

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

· Если , то занести атрибуты пикселя в буфер кадра и заменить . В противном случае никаких действий не производить.

Алгоритм, использующий Z-буфер, можно также применять для построения сечений поверхностей. Изменится только оператор сравнения:

где - глубина искомого сечения.

Методы приоритетов (художника, плавающего горизонта)

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

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

Пусть поверхность задана уравнением

В качестве картинной плоскости выберем плоскость . В области задания функции на осях координат построим сетку узлов:

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

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

Рис. 7.4. Простое каркасное изображение с поверхности

Рис. 7.5. Каркасное изображение диагональными ребрами

Алгоритм художника можно применять для полностью закрашенной сцены, а для каркасного изображения, когда объект представляется в виде набора кривых или ломаных линий, он непригоден. Для этого случая предложен еще один метод, весьма эффективный - метод плавающего горизонта . Вернемся к предыдущему примеру изображения поверхности. Каркасное изображение получается путем изображения кривых, получаемых при пересечении этой поверхности плоскостями и (рис. 7.4).

На самом деле мы будем рисовать четырехугольник и одну диагональ. В процессе рисования нам понадобятся два целочисленных массива: (нижний горизонт) и (верхний горизонт) размерностью, соответствующей горизонтальному размеру экрана в пикселях. Они нужны для анализа видимости участков изображаемых отрезков. Сначала мы инициализируем верхний горизонт нулем, а нижний - максимальным значением вертикальной координаты на экране. Каждая выводимая на экран точка может закрывать другие точки, которые "скрываются за горизонтом". По мере рисования нижний горизонт "опускается", а верхний "поднимается", постепенно оставляя все меньше незакрытого пространства. В отличие от метода художника, здесь мы продвигаемся от ближнего угла к дальнему. Теперь опишем алгоритм подробнее.

Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом. Работает этот алгоритм в пространстве изображения.

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

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

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

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

1) заполнить буфер кадра фоновым значением интенсивности или цвета;
2) заполнить z-буфер минимальным значением z;
3) преобразовать каждый многоугольник в растровую форму в произвольном порядке;
4) для каждого Пиксел(x, y) в многоугольнике вычислить его глубину z(x, y);
сравнить глубину z(x, y) со значением Zбуфер(x, y), хранящимся в z-буфере в этой же позиции;
5) если z(x, y) > Zбуфер(x, y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер(x, y) на z(x, y);
6) в противном случае никаких действий не производить.

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

Оптимизация алгоритма

Одним из наиболее распространённых модификаций алгоритма z-буфера является алгоритм иерархического z-буфера. Назовём грань скрытой (невидимой) по отношению к z-буферу, если для всех её точкек их глубины не меньше соответствующих значений в z-буфере (при попытке вывести такую грань в z-буфер ничего не изменится). Куб (прямоугольный параллелепипед) назовём скрытым по отношению к z-буферу, если все его лицевые грани являются скрытыми. Теперь объединим несколько граней сцены и обведём вокруг них куб. Для вывода этих граней в z-буфер проверяется, является ли этот куб скрытым по отношению к z-буферу. Если это так, что и все грани, объединённые кубом являются скрытыми по отношению к z-буферу и не выводятся в него, сокращая количество вычислений и ненужных операций сравнения. Если же это не так, то всё равно не все грани, объединённые кубом являются видимыми и этот куб разбивается на части, а затем для каждой части выполняются такие же операции сравнения. Таким образом реализация данного алгоритма может выглядеть следующим образом. Вокруг всей сцены описывается куб, он разбивается на 8 частей (тоже кубы), а каждая из частей, в свою очередь, разбивается ещё на 8 частей и так до тех пор, пока количество граней в кубе не станет меньше заданного числа, при котором уже нет смысла в дальнейшей разбивке на части. Далее для вывода очередного куба в z-буфер для него проверяется, является он скрытым или нет. Если да, то все грани, объединённые этим кубом игнорируются, а если нет, то соответствующая проверка выполняется для всех его частей и т.д

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