Алгоритмы Варнока, 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) – разбить интервал точкой пересечения