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

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

Алгоритм

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

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

1. Изобразить фон
2. Изобразить атрибуты многоугольника, соответствующие этому отрезку
3. Изобразить атрибуты многоугольника, соответствующие отрезку с MAX Z
4. sign (z1m-z2m)≠ sign (z1k-z2k) – разбить интервал точкой пересечения