11. Основы методов устранения ступенчатости. Алгоритм Брезенхема с устранением ступенчатости. Алгоритм Ву. - p1xelse/CG GitHub Wiki

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

Метод устранения искажений изображения:

Рассмотрение пикселя не как математической точки, а как некоторую конечную область.При наличии нескольких оттенков цвета внешний вид отрезка улучшается путем размывания его краев.(алгоритм Брезенхема с устранением ступенчатости)

Алгоритм Брезенхема с устранением ступенчатости

Принципиально устранить ступенчатость (лестничный эффект) невозможно. Однако применением специальных методов можно добиться того, что визуально ступеньки будут слабо заметны или практически незаметны. Излагаемый здесь способ устранения ступенчатости рассматривает пиксел не как математическую точку, а как некоторую конечную область. При наличии нескольких оттенков цвета внешний вид отрезка улучшается путем размывания его краев. Для этого интенсивность пиксела устанавливается пропорционально площади части пиксела, находящейся под отрезком. Поэтому необходимо получить выражения для вычисления этой площади. Отрезок, тангенс угла наклона m которого лежит в диапазоне 0 < m < 1 (как было указано ранее, все отрезки приводятся к такому виду), может при данном значении абсциссы пересечь один или два пиксела. В первом случае искомая площадь находится как сумма площадей прямоугольника S1 и треугольника S2:
Таким образом, в обоих случаях площадь вычисляется по одной и той же формуле. В качестве ошибки в данном алгоритме принимается часть площади пиксела, находящаяся под отрезком, то есть Yi+m/2. Вычислим значение ошибки при переходе к соседнему пикселу. Если ордината соседнего пиксела не увеличивается, то площадь, находящаяся под отрезком, увеличивается на величину площади прямоугольника со сторонами 1 и m, то есть f=f+m. Если же ордината соседнего пиксела увеличивается на единицу, то вычисленная доля площади пиксела будет содержать и площадь пиксела, через который отрезок не проходит, следовательно, необходимо вычесть величину площади пиксела, то есть единицу: f=f+m-1. Поскольку доля площади не может быть отрицательной величиной, то по сравнению с ранее рассмотренными алгоритмами Брезенхема необходимо скорректировать величину ошибки, прибавив к ней величину W=1-m. При этом начальное значение ошибки будет равно f=m-0,5+1-m=0,5, а значение ошибки будет лежать в диапазоне 0 < f < 1. Первый пиксел отрезка будет, таким образом, всегда высвечиваться интенсивностью, равной половине максимальной. Для более реалистичного изображения это значение можно изменить.

Общий алгоритм Брезенхема с устранением ступенчатости может быть записан следующим образом:

Ввод исходных данных Xн,Yн,Xк,Yк (координаты концов отрезка), I - количество уровней интенсивности.
проверка вырожденности отрезка. Если отрезок вырожден, то высвечивание отдельного пиксела и переход к п.13.
Вычисление приращений dX=Xк-Xн и dY=Yк-Yн.
Вычисление шага изменения каждой координаты: SX=sign(dX), SY=sign(dY).
Вычисление модулей приращения координат: dX=!dX!, dY=!dY!.
Вычисление модуля тангенса угла наклона m=dY/dX.
Анализ вычисленного значения m и обмен местами dX и dY при m>1:
если m>1, то выполнить
p=dX;
dX=dY;
dY=p;
m=1/m;
fl=1; если m<1, то fl=0.
(fl - флаг, определяющий факт обмена местами координат).
Инициализация начального значения ошибки f=I/2.
Инициализация начальных значений координат текущего пиксела: X=Xн, Y=Yн.
Вычисление скорректированного значения тангенса угла наклона m=mI и коэффициента W=I-m.
Высвечивание пиксела с координатами (X,Y)
интенсивностью E(f).
Цикл от i=1 до i=dX с шагом 1:
Если f<W, то
если fl=0, то X=X+SX;
если fl=1, то Y=Y+SY;
f=f+m.
Если f>W, то X=X+SX, Y=Y+SY, f=f-W.
Высвечивание пикселя с координатами (X,Y)
интенсивностью E(f).
Конец.

Алгоритм Ву

Распределение интенсивности пикселя в зависимости от расстояния до идеальной линии Алгоритм Ву — это алгоритм разложения отрезка в растр со сглаживанием. Горизонтальные и вертикальные линии не требуют никакого сглаживания, поэтому их рисование выполняется отдельно. Для остальных линий алгоритм Ву проходит их вдоль основной оси, подбирая координаты по не основной оси аналогично алгоритму Брезенхема. Отличие состоит в том, что в алгоритме Ву на каждом шаге устанавливается не одна, а две точки.
Например, если основной осью является Х, то рассматриваются точки с координатами (х, у) и (х, у+1). В зависимости от величины ошибки, которая показывает как далеко ушли пиксели от идеальной линии по не основной оси, распределяется интенсивность между этими двумя точками. Чем больше удалена точка от идеальной линии, тем меньше ее интенсивность. Значения интенсивности двух пикселей всегда дают в сумме единицу, то есть это интенсивность одного пикселя, в точности попавшего на идеальную линию. Такое распределение придаст линии одинаковую интенсивность на всем ее протяжении, создавая при этом иллюзию, что точки расположены вдоль линии не по две, а по одной.

Реализация в псевдокоде из википедии(только для линии по x):

function plot(x, y, c) is
    // рисует точку с координатами (x, y)
    // и яркостью c (где 0 ≤ c ≤ 1)

function ipart(x) is
    return целая часть от x

function round(x) is
    return ipart(x + 0.5) // округление до ближайшего целого

function fpart(x) is
    return дробная часть x

function draw_line(x1,y1,x2,y2) is
   if x2 < x1 then
       swap(x1, x2)
       swap(y1, y2)
   end if
  
   dx := x2 - x1
   dy := y2 - y1
   gradient := dy ÷ dx
  
   // обработать начальную точку
   xend := round(x1) 
   yend := y1 + gradient × (xend - x1)
   xgap := 1 - fpart(x1 + 0.5)
   xpxl1 := xend  // будет использоваться в основном цикле
   ypxl1 := ipart(yend)
   plot(xpxl1, ypxl1, (1 - fpart(yend)) × xgap)
   plot(xpxl1, ypxl1 + 1, fpart(yend) × xgap)
   intery := yend + gradient // первое y-пересечение для цикла
        
   // обработать конечную точку
   xend := round(x2)
   yend := y2 + gradient × (xend - x2)
   xgap := fpart(x2 + 0.5)
   xpxl2 := xend  // будет использоваться в основном цикле
   ypxl2 := ipart(yend)
   plot(xpxl2, ypxl2, (1 - fpart(yend)) × xgap)
   plot(xpxl2, ypxl2 + 1, fpart(yend) × xgap)
     
   // основной цикл
   for x from xpxl1 + 1 to xpxl2 - 1 do
           plot(x, ipart(intery), 1 - fpart(intery))
           plot(x, ipart(intery) + 1, fpart(intery))
           intery := intery + gradient
   repeat
end function

Вопросы по защите:

Как выглядит отрезок, построенный по алг. Брезенхема с устр. ступ., где его использовать?
Брезенхем с устранением ступенчатости преимущественно используется для построения рёбер многоугольников, т.к. одна из сторон прямой получается сглаженной. Если дальше фигуру штриховать, то лесенки на несглаженной стороне исчезнут и в итоге получится фигура с гладкими рёбрами. Используется для построения многоугольников.
КАК определяются расстояния от пикселя до точки на отрезке алг. ВУ?
Вводится дополнительная переменная которая на каждой итерации цикла увеличивается на величину, равную тангенсу угла наклона прямой. Дробная часть этой переменной определяет расстояние от центра пикселя до идеальной прямой. В зависимости от того, как далеко ушли пиксели от идеальной линии по неосновной оси, распределяется интенсивность между этими двумя точками. Чем больше удалена точка от идеальной линии, тем меньше её интенсивность.
Основные принципы сглаживания в алг. Брезенхема и ВУ
Горизонтальные и вертикальные линии не требуют никакого сглаживания, поэтому их рисование выполняется отдельно. Для остальных линий алгоритм Ву проходит их вдоль основной оси, подбирая координаты по не основной оси аналогично алгоритму Брезенхема. Отличие состоит том, что в алгоритме Ву на каждом шаге устанавливается не одна, а две точки. Например, если основной осью является Х, то рассматриваются точки с координатами (х, у) и (х, у+1). В зависимости от величины ошибки, которая показывает, как далеко ушли пиксели от идеальной линии по не основной оси, распределяется интенсивность между этими двумя точками. Чем больше удалена точка от идеальной линии, тем меньше её интенсивность. Значения интенсивности двух пикселей всегда дают в сумме единицу, то есть это интенсивность одного пикселя точности попавшего на идеальную линию.
Что рассм. в качестве ошибки в алг. Брезенхема с устр. ступенчатости?
Мера площади той части пикселя, что внутри многоугольника, используемого в алгоритме.
Почему Брезенхем с устр. работает почти так же быстро как и без устр.?
Брезенхем с устранением работает почти так же быстро, как без устранения, так как на каждой итерации объем вычислений в обоих алгоритмах одинаков, а передача значения интенсивности для высвечивания пикселя, используемая в брезенхеме с устранением, выполняется быстро.