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

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

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

Один из вариантов алгоритма Брезенхэма ([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). Этот алгоритм восьмисвязный, т.е. при вычислении приращений координат для перехода к соседнему пикселу возможны восемь случаев:

									incY=-1
								incX=-1	incX=1
									incY=1

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

									incY=-1
								incX=-1	incX=1
									incY=1