4.7. Алгоритмы построчного сканирования

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

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

Алгоритм построчного сканирования, использующий z-буфер
Одним из простейших алгоритмов построчного сканирования, который решает задачу удаления невидимых поверхностей, является специальный случай алгоритма z-буфера - алгоритм построчного сканирования с z-буфером. Используемое в этом алгоритме окно визуализации имеет высоту в одну сканирующую строку и ширину во весь экран. Как для буфера кадра, так и для z-буфера требуется память высотой в 1 бит, шириной в горизонтальное разрешение экрана и глубиной в зависимости от требуемой точности. Концептуально этот алгоритм достаточно прост. Для каждой сканирующей строки буфер кадра инициализируется с фоновым значением интенсивности, а z-буфер - с минимальным значением z. Затем определяется пересечение сканирующей строки с двумерной проекцией каждого многоугольника сцены, если они существуют. Эти пересечения образуют пары. При рассмотрении каждого пиксела на сканирующей строке в интервале между концами пар его глубина сравнивается с глубиной, содержащейся в соответствующем элементе z-буфера. Если глубина этого пиксела больше глубины из z-буфера, то расссматриваемый отрезок будет текущим видимым отрезком. И следовательно, атрибуты многоугольника, соответствующего данному отрезку, заносятся в буфер кадра в позиции данного пиксела; соответственно корректируется и z-буфер в этой позиции. После o6pаботки всех многоугольников сцены буфер кадра размером в одну сканирующую строку содержит решение задачи удаления невидимых поверхностей для данной сканирующей строки. Он выводится на экран дисплея в порядке, определяемом растровым сканировани ем, т.е. слева направо. В этом алгоритме можно использовать методы устранения ступенчатости, основывающиеся как на пре-, так и на постфильтрации.

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

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