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

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

При наличии нескольких интенсивностей, то есть полутонов серого или оттенков цвета, внешний вид ребра или отрезка может быть улучшен размыванием краев. Простой эвристический метод состоит в том, чтобы устанавливать интенсивность пиксела на ребре пропорционально площади части пиксела, находящейся внутри многоугольника. Эта простая форма устранения ступенчатости иллюстрируется на рис. 16.1, на котором изображено одно ребро многоугольника с тангенсом угла наклона 5/8. Внутренняя часть многоугольника расположена справа. На рис. 16.1a представлено ребро, разложенное в растр с помощью стандартного алгоритма Брезенхема с использованием только двух уровней интенсивности. Изображение имеет характерный зазубренный или ступенчатый вид. На рис. 16.1b для выбора одного из восьми (от 0 до 7) уровней интенсивности используется площадь части пиксела, находящейся внутри многоугольника. Заметим, что так как эта площадь для некоторых пикселов меньше одной восьмой, то некоторые пикселы, полностью черные на рис. 16.1a, окрашены в белый цвет на рис. 16.1b.

В результате простой модификации алгоритма Брезенхема можно получить аппроксимацию площади части пиксела, находящейся внутри многоугольника. Эту аппроксимацию можно использовать для модуляции интенсивности. Как показано на рис. 16.2, при пересечении пиксела и отрезка с тангенсом угла наклона m (0 <= m <= 1) может быть задействован либо один, либо два пиксела. Если пересекается только один пиксел (рис. 16.2a), то площадь (далее везде, где говорится о площади пиксела, имеется в виду площадь его части, которая находится внутри многоугольника) правее и ниже отрезка равна у_i + m/2. Если же надо рассмотреть два пиксела (рис. 16.2b), то площадь нижнего пиксела составляет 1 - (1 - y_i)²/2m, а верхнего — (y_i - 1 + m)²/2m. Для отрезка в первом октанте с тангенсом угла наклона 0 <= m <= 1 площадь верхнего пиксела может быть достаточно мала для того, чтобы ее можно было проигнорировать в вышеописанном эвристическом методе, например, для пиксела (1, 1) на рис. 16.2b. Однако объединение этой площади с площадью нижнего пиксела позволит более реалистично представить ребро многоугольника. Суммарная площадь для двух пикселов равна y_i + m/2.

Если к ошибке в исходном алгоритме Брезенхема добавить величину w = 1 - m, то есть ввести преобразование e' = e + w, то 0 <= e' <= 1. Теперь ошибка е' — это мера площади той части пиксела, которая находится внутри многоугольника, то есть y_i + m/2. В связи с этими модификациями начальное значение ошибки равно 1/2, поэтому для первого пиксела алгоритм, приводившийся на рис. 16.1, всегда будет выдавать значение интенсивности, равное половине максимальной. Более реалистичное значение для первого пиксела дает перемещение оператора активирования пиксела на другое место. Более того, можно получить непосредственно значение интенсивности, а не десятичную дробь от ее максимума с помощью умножения на максимальное число доступных уровней интенсивности I следующих величин: тангенса угла наклона (m), весового коэффициента (w) и ошибки е'. Модифицированный алгоритм Брезенхема с устранением ступенчатости для первого квадранта выглядит следующим образом.

отрезок проводится из (x₁, y₁) в (x₂, y₂)
I — число доступных уровней интенсивности
все переменные целого типа
инициализация переменных
x = x₁
y = y₁
Dx = x₂ - x₁
Dy = y₂ - y₁
m = (I * Dy)/Dx
w = I - m
e' = I/2
Plot (x, y, m/2)
while (x < x₂)
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. Распространить работу алгоритма на другие октанты можно тем же способом, что и для основного алгоритма Брезенхема.