Улучшение качества аппроксимации векторов

Выше было отмечено, что растровая генерация отрезков имеет следующие недостатки:

• неточное расположение начала и конца,

• ступенчатый вид отрезка,

• яркость зависит от наклона и длины.

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

Наиболее заметно ухудшает качество изображения ступенчатость. Имеется следующие способы борьбы со ступенчатостью :

 увеличение пространственного разрешения за счет усовершенствования аппаратуры,

 трактовка пиксела не как точки, а как площадки конечного размера, яркость которой зависит от размера площади пиксела, занятой изображением отрезка,

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

Простой метод устранения лестничного эффекта

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

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

Если к ошибке в исходном алгоритме Брезенхема добавить величину w = 1 - m, то есть ввести преобразование e' = e + w, то 0 <= e' <= 1. Модифицированный алгоритм Брезенхема с устранением ступенчатости для первого квадранта выглядит следующим образом.

отрезок проводится из (x1, y1) в (x2, y2) I — число доступных уровней интенсивности все переменные целого типа инициализация переменных

x = x1 y = y1 x = x2 - x1 y = y2 - y1 m = (I * y)/x w = I - m e' = I/2 Plot (x, y, m/2) while (x < x2) if e' < w then x = x + 1 e' = e' + m else x = x + 1 y = y + 1 e' = e' - w end if Plot (x, y, e') end while finish

Интенсивность для первого пиксела предполагает, что отрезок начинается с адреса пиксела. Результаты для отрезка с тангенсом угла наклона m = 5/8 и восемью уровнями интенсивности представлены на рис. 16.1c. Распространить работу алгоритма на другие октанты можно тем же способом, что и для основного алгоритма Брезенхема.

Растровая развертка в реальном времени Заполнение многоугольника в порядке сканирования строк

Можно разработать более эффективный тест на принадлежность внутренней части, если воспользоваться тем фактом, что соседние пикселы, вероятно, имеют одинаковые характеристики (кроме пикселов граничных ребер). Это свойство называется пространственной когерентностью. Для растровых графических устройств соседние пикселы на сканирующей строке, вероятно, имеют одинаковые характеристики. Это когерентность растровых строк.