34. Алгоритм построчного сканирования, использующий Z буфер. Интервальные методы построчного сканирования (основные предпосылки).

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

По факту это специальный случай Z-буффера

• Работает в пространстве изображения
• Алгоритмы построчного сканирования обрабатывают сцену в порядке прохождения строки.

Так как построчное сравнение каждого многоугольника с каждой сканирующей строкой неэффиктивно, используют "разновидность" САР.

Алгоритм

Подготовка информации.

1. Для каждого многоугольника определить самую верхнюю сканирующую строку, которую он пересекает.
2. Занести многоугольник в группу y, соответствующую этой сканирующей строке
3. Запомнить для каждого многоугольника: Δy – число строк, пересекающих этот многоугольник, список рёбер многоугольника, коэффициенты A, B, C, D уравнения плоскости многоугольника, визуальные атрибуты многоугольника

Решение задачи удаления невидимых поверхностей

1. Инициализировать буфер кадра дисплея
2. Для каждой сканирующей строки:
2.1. Инициализировать буфер кадра размером с одну сканирующую строку, заполнив его фоновым изображением
2.2. Инициализировать Z-буфер размером с одну сканирующую строку значением Zmin
2.3. Проверить необходимость добавления в список активных многоугольников (САМ) новых многоугольников
2.4. Если было добавление многоугольника в САМ, то добавить в САР соответствующие рёбра новых многоугольников
2.5. Если произведено удаление какого-либо элемента из пары рёбер САР, то проверить необходимость удаления всего многоугольника из САМ. Если он остаётся, то проверить необходимость удаления другого ребра из этой пары – если его удалять не нужно, то доукомлектовать пару (добавив недостающее левое или правое ребро)

Информация в САР

• Xл – пересечение левого ребра с текущей сканирующей строкой
• ΔXл – приращение Xл в интервале между соседними сканирующими строками
• ΔYл – число сканирующих строк, пересекаемых левым ребром
• Xп, ΔXп, ΔYп
• ΔZх = -A/C для C≠0 (иначе ΔZх=0) – приращение по Z вдоль сканирующей строке
• ΔZy = -B/C для C≠0 (иначе ΔZy=0) – приращение по Z в интервале между соседними сканирующими строками

3. Для каждой пары ребёр многоугольника из САР выполнить:
3.1. Извлечь
3.2. Инициализировать Z значением Zл
3.3. Для каждого пикселя Xл ≤ X ≤ Xп вычислить Z(x, y=const). Z1=Zл, ..., Zk = Zk-1+ ΔZх
3.4. Если Z()>Zбуф(), то Zбуф=Z и занести атрибуты многоугольника в буфер кадра

4. Записать буфер кадра сканирующей строки в буфер кадра дисплея

5. Скорректировать САР
5.1. ΔYл--, ΔYп--
5.2. Xл=Xл + ΔXл, Xп=Xп + ΔXп
5.3. Zл=Zл + ΔZхΔX + ΔZy
5.4. Если ΔYл < 0 или ΔYп < 0, то удалить соответствующее ребро из списка, пометив положение обоих рёбер в списке и породивший их многоугольник

6. Скорректировать САМ
6.1. ΔY--
6.2. Если ΔY < 0, то удалить многоугольник из САМ

Интервальное сканирование

В предыдущем алгоритме, глубина z вычисляется для каждого пикселя. Вычисления можно сократить, если ввести так называемые интервалы.

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

Всего, возможно четыре случая:

1. Пустой интервал. Просто закрасить цветом фона.
2. Интервал содержит один отрезок. Изображаются атрибуты многоугольника, соответсвующие этому многоугольнику.
3. Интервал содержит несколько непересекающихся отрезков. Изобразить атрибуты многоугольника с zmax.
4. Отрезки протыкают друг друга. Плоскость поделить ещё в точке пересечения. Провести вычисления глубины в середине каждого интервала.

Следующий вопрос: 35. Алгоритм определения видимых поверхностей путем трассировки лучей.

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