Сделай Сам Свою Работу на 5

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

Алгоритм, использующий 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 objects

for all covered pixels

compare z

 

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

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

(xa, y, za)
(x1, y1, z1)
(x, y, z)
(x2, y2, z2)
(x3, y3, z3)
(xb, y, zb)

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

Для рисунка y меняется от y1 до y2 и далее до y3, при этом для каждой строки определяется xa, za, xb, zb:

xa = x1 + (x2 - x1 ;

xb = x1 + (x3 - x1 ;

za = z1 + (z2 - z1 ;

zb = z1 + (z3 - z1 .

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

z = za + (zb - za

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

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

 

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

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

 

 

 

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

 

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

 

 

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

Методы трассировки лучей

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

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

for all pixels

for all objects

compare z

 

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

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

Поверхность может отразить весь световой луч или только его часть в одном или нескольких направлениях. Поверхность может также поглотить часть светового луча, что приводит к потере интенсивности отраженного и/или преломлённого луча. Если поверхность имеет какие-либо свойства прозрачности, то она преломляет часть светового луча внутри себя и изменяет его направление распространения, поглощая некоторый (или весь) спектр луча (и, возможно, изменяя цвет). Суммарная интенсивность светового луча, которая была «потеряна» вследствие поглощения, преломления и отражения, должна быть в точности равной исходящей (начальной) интенсивности этого луча. Далее отраженные и/или преломлённые лучи достигают других поверхностей, где их поглощающие, отражающие и преломляющие способности снова вычисляются, основываясь на результатах вычислений входящих лучей. Таким образом, луч, пропущенный через пиксель картиной плоскости, образует сложный разделяющийся путь.

Рис. 8.13. Обратная трассировка лучей

Как отмечено в [7], если проследить за лучами света, выпущенным источником света, то можно убедиться, что весьма немногие дойдут до наблюдателя. Следовательно, этот процесс вычислительно неэффективен. Поэтому было предложено отслеживать (трассировать) лучи в обратном направлении, т.е. от наблюдателя к объекту и далее к источнику освещения (рис. 8.13). При этом, интенсивность в пикселе, через который проходит луч, рассчитывалась бы интегрально с учетом всех слагаемых: пересечения, отражения, преломления луча с разными объектами и характеристик источников света. Такой подход получил название метод обратной трассировки лучей (ray tracing).



©2015- 2019 stydopedia.ru Все материалы защищены законодательством РФ.