Базовые растровые алгоритмы

Лекция 11

Базовые растровые алгоритмы

Алгоритмы вывода прямой линии

Пусть заданы координаты (x1,y1) и (x2,y2) концов отрезка прямой линии. Для вывода линии необходимо закрасить в определенный цвет все пикселы вдоль линии. Для того чтобы закрасить каждый пиксел, необходимо знать его координаты.

Наиболее просто нарисовать отрезок горизонтальной линии (y1=y2): для x от x1 до x2 с шагом 1 закрашиваются соседние пикселы (x, y1). (Эта операция достаточно проста и применяется в алгоритмах закрашивания полигонов.)

Аналогично изображается отрезок вертикальной линии.

Горизонтали и вертикали представляют собой частный случай линий. Рассмотрим линию общего вида. Известно несколько методов расчета координат точек линии.

Прямое вычисление координат. Пусть заданы координаты конечных точек отрезка. Координаты внутренней точки отрезка вычисляются следующим образом:

x=f(y):              x=x₁+(y-y₁)(x₂-x₁)/(y₂-y₁)

Рекомендуемые материалы

или

y=F(x):             y=y₁+(x-x₁)(y₂-y₁)/(x₂-x₁).

В зависимости от угла наклона прямой выполняется цикл по оси x  (если |x₂-x₁|>|y₂-y₁|) или по оси y (в противном случае).

Для того чтобы свести к минимуму вычисления в цикле, все операции над константами выносятся из тела цикла:

k=(y₂-y₁)/(x₂-x₁),   yy=y₁-x₁*k.

В цикле вычисляется     y=yy+x*k.

Если учесть, что вычисления выполняются как итеративный процесс, где x на каждом   шаге увеличивается на единицу, то вычисления в данном алгоритме еще более упрощаются:

k=(y₂-y₁)/(x₂-x₁),   y=y₁.

Для  x  от  x₁  до  x₂  с шагом 1 вычисляется  y=y+k.

С учетом того, что вычисление дробей в компьютере происходит с определенной погрешностью, возможно ситуация, когда на последнем шаге цикла x окажется не равным x₂. Это необходимо учитывать при использовании алгоритма.

Положительные черты алгоритма прямого вычисления координат:

· простота, ясность построения алгоритма;

· возможность работы с нецелыми значениями координат отрезка.

Недостатки:

· использование операций с дробными числами или целочисленных операций умножения и деления обуславливает малую скорость;

· при вычислении координат путем добавления приращений может накапливаться ошибка.

Инкрементные алгоритмы

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

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

Один из вариантов алгоритма Брезенхэма ([12, с. 100-101]):

xerr:=0; yerr:=0;

dx:=x2-x1; dy:=y2-y1;

Если dx>0, то incX:=1;

dx=0, то incX:=0;

dx<0, то incX:=-1;

Если dy>0, то incY:=1;

dy=0, то incY:=0;

dy<0, то incY:=-1;

dx:=|dx|; dy:=|dy|;

Если dx>dy, то d:=dx  иначе d:=dy;

x:=x1; y:=y1;

Закрасить пиксел с координатами (x, y);

Выполнить d раз цикл:

xerr:=xerr+dx;

yerr:=yerr+dy;

Если xerr>=d, то xerr:=xerr-d,  x:=x+incX;

Если yerr>=d, то yerr:=yerr-d,  y:=y+incY;

Закрасить пиксел с координатами (x, y).

Рассмотрим пример работы приведенного выше алгоритма Брезенхэма для отрезка (2;3) - (8;6). Этот алгоритм восьмисвязный, т.е. при вычислении приращений координат для перехода к соседнему пикселу возможны восемь случаев:

Известны также четырехсвязные алгоритмы. Они более просты, но генерируют менее качественное изображение линий за большее количество тактов работы. Для приведенного примера четырехсвязный алгоритм работает 10 тактов, а восьмисвязный - только 7:

Алгоритм вывода окружности

Для вывода контура круга можно использовать соотношение между координатами X и Y для точек окружности X²+Y²=R²  и построить алгоритм прямого вычисления координат. Однако в этом случае необходимо вычислять квадратный корень (как элемент бесконечной последовательности приближений).

Приведем запись инкрементного алгоритма Брезенхэма:

r2:=radius*radius;

dst:=4*r2;

dxt:=radius/1.414213562373;

t:=0;

s:=-4*r2*radius;

e:=(-s/2)-3*r2;

ca:=-6*r2;

cd:=-10*r2;

x:=0; y:=radius;

Закрасить пиксел (xc,yc+radius);

Закрасить пиксел (xc,yc-radius);

Закрасить пиксел (xc+radius,yc);

Закрасить пиксел (xc-radius,yc);

Для indx от 1 до dxt с шагом 1:

x:=x+1;

Если e>=0 то e:=e+t+ca иначе y:=y-1, e:=e+t-s+cd, s:=s+dst; t:=t-dst;

Закрасить пиксел (xc+x,yc+y);

Закрасить пиксел (xc+y,yc+x);

Закрасить пиксел (xc+y,yc-x);

Закрасить пиксел (xc+x,yc-y);

Закрасить пиксел (xc-x,yc-y);

Закрасить пиксел (xc-y,yc-x);

Закрасить пиксел (xc-y,yc+x);

Закрасить пиксел (xc-x,yc+y).

В этом алгоритме используется симметрия круга - в основном цикле вычисляются координаты точек окружности только для одного октанта и сразу рисуются восемь симметрично расположенных пикселов.

Алгоритм вывода эллипса

Инкрементный алгоритм для эллипса подобен алгоритму для круга, но несколько сложнее его:

a:=|enx-xc|; b:=|eny-yc|;

a2:=a*a; b2:=b*b;

dds:=4*a2; ddt:=4*b2; dxt:=a2/sqrt(a2+b2);

t:=0;

s:=-4*a2*b;

e:=(-s/2)-2*b2-a2;

ca:=-6*b2;

cd:=ca-4*a2;

x:=xc;  y:=yc+b;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y);

Для indx от 1 до dxt с шагом 1:

x:=x+1;

Если e>=0 то e:=e+t+ca иначе y:=y-1, e:=e+t-s+cd,

s:=s+dds;  t:=t-ddt;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y);

dxt:=|y-yc|;

e:=e-(t/2+s/2+b2+a2);

ca:=-6*a2;

cd:=ca-4*b2;

Для indx от 1 до dxt с шагом 1:

y:=y-1;

Если  e<=0  то  e:=e-s+ca  иначе  x:=x+1, e:=e-s+t+cd,

6 - Регулирующая и направляющая аппаратура - лекция, которая пользуется популярностью у тех, кто читал эту лекцию.

t:=t-ddt;  s:=s+dds;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y).

В этом алгоритме использована симметрия эллипса по квадрантам. Алгоритм состоит из двух циклов. Сначала для x от 0 до dxt,  где   а потом цикл до точки x=a, y=0.