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

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

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

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

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

Вычисление глубины z

Многоугольник описывается уравнением: Ax + By + Cz + D = D, отсюда получаем:
z = -(Ax + By + D) / C При с = 0 - многоугольник для наблюдателя вырождается в линию.
Ясно, что для сканирующей строки y = const. Поэтому, можем рекуретно считать z' для каждого х' = x + dx.

z' - z = -(ax' + d) / c + (ax + d) / c = a(x - x') / c, откуда z' = z - (a / c), потому что (x - x') = dx = 1 (единичый шаг растра)

Глубина пикселя, являющегося пересечением сканирующей строки с ребром многоугольника

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

Глубину определяют по соотношению:

z3 = z2 + (y3 - y2) / (y2 - y1) * (z2 - z1), где

• (y1, z1), (y2, z2) - координаты вершин проекции ребра на плоскость YOZ.
• (x3, z3) - координаты проекции точки пересечения на ту же плоскость.

Оценка эффективности

Плюсы:

• Сцены могут быть произвольной сложности.
• Не нужна сортировка, как в других алгоритмах.
• Трудоемкость линейно зависит от числа рассматриваемых поверхностей

Недостатки:

• Большой объем памяти (под буфферы).
• Трудоемкость устранения лестничного эффекта.
• Трудность реализации эффектов прозрачности.

Псевдокод (алгоритм)

1. Инициализация буффера кадра фоновым значением.
2. Инициализация z-буффера минимальным значеним Z.
3. Растровая развертка каждого многоугольника (в произвольном порядке).
4. Вычисление глубины z = (x, y) для каждого пикселя, принадлежащего многоугольнику.
5. Сравнение полученой глубины z со значеним z, лежащей в буфере (для пикселя (х, у)).
   если полученая глубина больше значения в буфере, то записать атрибут многоугольника
   в буфер кадра и заменить значение в Z-буфере на полученное значение

Для невыпуклых многогранников, предварительно надо удалить нелицевые грани.

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

Следующий вопрос: 33. Алгоритм, использующий список приоритетов.

Предыдущий вопрос: 31. Алгоритм Вейлера Азертона удаления невидимых линий и поверхностей.