34. Алгоритм построчного сканирования, использующий Z буфер. Интервальные методы построчного сканирования (основные предпосылки). - chrislvt/CG GitHub Wiki
Алгоритмы Варнока, Z-буфера и строящего список приоритетов обрабатывают элементы сцены в порядке, который не связан с процессом визуализации. Алгоритмы построчного сканирования обрабатывают сцену в порядке прохождения сканирующей строки. Работают в пространстве изображения
Алгоритм
1. Подготовка информации
a) Для каждого многоугольника определить самую верхнюю сканирующую строку, которую он пересекает. b) Занести многоугольник в группу y, соответствующую этой сканирующей строке c) Запомнить для каждого многоугольника: Δy – число строк, пересекающих этот многоугольник, список рёбер многоугольника, коэффициенты A, B, C, D уравнения плоскости многоугольника, визуальные атрибуты многоугольника
2. Решение задачи удаления невидимых поверхностей
a) Инициализировать буфер кадра дисплея b) Для каждой сканирующей строки 1. Инициализировать буфер кадра размером с одну сканирующую строку, заполнив его фоновым изображением 2. Инициализировать Z-буфер размером с одну сканирующую строку значением Zmin 3. Проверить необходимость добавления в список активных многоугольников (САМ) новых многоугольников 4. Если было добавление многоугольника в САМ, то добавить в САР соответствующие рёбра новых многоугольников 5. Если произведено удаление какого-либо элемента из пары рёбер САР, то проверить необходимость удаления всего многоугольника из САМ. Если он остаётся, то проверить необходимость удаления другого ребра из этой пары – если его удалять не нужно, то доукомлектовать пару (добавив недостающее левое или правое ребро)
c) В САР должна храниться следующая информация:
- Xл – пересечение левого ребра с текущей сканирующей строкой
- ΔXл – приращение Xл в интервале между соседними сканирующими строками
- ΔYл – число сканирующих строк, пересекаемых левым ребром
- Xп, ΔXп, ΔYп
- ΔZх=-A/C для C≠0 (иначе ΔZх=0) – приращение по Z вдоль сканирующей строке
- ΔZy=-B/C для C≠0 (иначе ΔZy=0) – приращение по Z в интервале между соседними сканирующими строками
d) Для каждой пары ребёр многоугольника из САР выполнить:
- Извлечь
- Инициализировать Z значением Zл
- Для каждого пикселя Xл≤X≤Xп вычислить Z(x,y=const). Z1=Zл, ..., Zk=Zk-1+ ΔZх
- Если Z()>Zбуф(), то Zбуф=Z и занести атрибуты многоугольника в буфер кадра
e) Записать буфер кадра сканирующей строки в буфер кадра дисплея
f) Скорректировать САР
- ΔYл--, ΔYп--
- Xл=Xл+ΔXл, Xп=Xп+ΔXп
- Zл=Zл+ΔZхΔX+ΔZy
- Если ΔYл<0 или ΔYп<0, то удалить соответствующее ребро из списка, пометив положение обоих рёбер в списке и породивший их многоугольник
g) Скорректировать САМ
- ΔY--
- Если ΔY<0, то удалить многоугольник из САМ
Пример
Результат
Интервальные методы построчного сканирования
В алгоритме построчного сканирования с использованием Z-буфера глубина многоугольника вычисляется для каждого пикселя на сканирующей строке. Количество вычислений можно сократить, если использовать понятие интервалов. Решение задачи удаления невидимых поверхностей сводится к выбору видимых отрезков в каждом интервале, полученном путём деления сканирующей строки проекциями точек пересечения ребёр
1. Изобразить фон
2. Изобразить атрибуты многоугольника, соответствующие этому отрезку
3. Изобразить атрибуты многоугольника, соответствующие отрезку с MAX Z
4. sign (z1m-z2m)≠ sign (z1k-z2k) – разбить интервал точкой пересечения