Общий алгоритм Брезенхема

Целочисленный алгоритм Брезенхема

Алгоритм Брезенхема в том виде, как он представлен выше, требует использования арифметики с плавающей точкой и деления (для вычисления углового коэффициента и оценки ошибки). Известно, что операции с вещественными числами осуществляются гораздо медленнее, чем с целыми. Быстродействие алгоритма можно увеличить, если использовать только целочисленную арифметику и исключить деление. С этой целью в алгоритме переменные e и d умножаются на целое число 2n. Таким образом, изменив масштаб переменных и внеся корректировки в неравенства, получим целочисленную версию алгоритма Брезенхема:

x:=x1; y:=y1; n:=x2-x1; m:=y2-y1; dx:=2*m; dy:= 2*n; e:=0;

for i:=1 to n do

begin

x:=x+1; e:=e+dx

if e>n then

begin

y:=y+1; e:=e-dy

end;

PutPixel (x,y)

end

Для получения общего алгоритма растровой развертки необходимо избавиться от ограничений, которые мы до сих пор накладывали на расположение отрезка на плоскости, а именно от требования 0£k£1.

Чтобы реализация алгоритма Брезенхема была полной, необходимо обрабатывать отрезки во всех квадрантах. Модификацию легко сделать, учитывая номер квадранта, в котором лежит отрезок и его угловой коэффициент. Когда абсолютная величина углового коэффициента больше 1, y постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяющейся (на +1 или –1) координаты зависит от квадранта (рис.3).

Рис.3. Общий алгоритм Брезенхема

Таким образом, учитывая ориентацию отрезка относительно положительных направлений осей координат и меняя переменные x,y в случае k по модулю больше 1, получаем окончательную общую версию алгоритма Брезенхема, которая называется восьмисвязной разверткой отрезка.

Пример процедуры общего алгоритма Брезенхема для восьмисвязной развертки отрезка:

Procedure Line_8 (x1,y1,x2,y2: integer);

Var

x,y,s1,s2,dx,dy,e,z: integer;

change: boolean;

Begin

x:=x1; y:=y1; dx:=abs(x2-x1); dy:=abs(y2-y1);

s1:=sign(x2-x1); s2:=sign(y2-y1);

if dy>dx then

begin

z:=dx; dx:=dy; dy:=z; change:=true

end

else change:=false;

e:=2*dy-dx;

for i:=1 to dx do

begin

PutPixel (x,y,color);

While e>=0 do

begin

if change then x:=x+s1 else y:=y+s2;

e:=e-2*dx

end;

if change then y:=y+s2 else x:=x+s1;

e:=e+2*dy

end;

PutPixel (x,y,color)

End.

Функция sign возвращает значения –1,0,+1 для отрицательного, нулевого и положительного аргумента соответственно (реализована не во всех версиях Паскаля).