Алгоритм Брезенхема


При построении растрового изображения отрезка всегда выбирается ближайший по вертикали пиксель. Алгоритм выбирает оптимальные растровые координаты для представления отрезка. Так если одна из координат в процессе работы изменяется на 1, то изменение другой может быть различным (0 или 1) и зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Это расстояние называют ошибкой. Суть работы алгоритма заключается в проверке знака ошибки. Рассмотрим построение отрезка в первом октанте (угловой коэффициент в диапазоне от 0 до 1). Из Рис.4 видно, что если угловой коэффициент (D=D y/D x) отрезка из т.(0,0) > 1/2, то точка его пересечения с прямой х=1 будет ближе к прямой y=1, чем y=0. Т.о. для построения очередной точки лучше использовать т.(1,1), чем (1,0). Если D<1/2, то наоборот. Если D=1/2 то выбор падает на т.(1,1).

Некоторые отрезки не проходят точно через точки растра (например, на Рис. 5 показана ситуация, когда пересекаются три пикселя, или дискретные пиксели). В этом случае также вычисляется результирующая ошибка (исходная e = -1/2): D рез=D исх+ D. Если значение отрицательно, то отрезок пройдет ниже середины пикселя (координата Y не меняется), а если >0, то выше (координата Y увеличится). Алгоритм Брезенхема для разложения отрезка в растр можно на псевдокоде описать так:

Предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают

Integer — функция преобразования в целое

x, y, D x, D y — целые

e — вещественное

инициализация переменных

x = x1, y = y1, D x = x2 — x1, Dy = y2 — y1

инициализация e с поправкой на половину пиксела

e = D y/D x — 1/2

начало основного цикла

for I = 1 to D x

Plot (x, y)

while (e ? 0)

y = y + 1

e = e — 1

end while

x = x + 1

e = e + D y/D x

next I

finish

Примечание! В данном способе имеются неудобства (арифметика с плавающей точкой и операции деления) при вычислении углового коэффициента и оценке ошибки. Поэтому в 1965 году Брезенхемом предложен простой алгоритм, использующий целочисленную арифметику. Суть в следующем.

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

= 2?е?Dx. Затем подставим его в алгоритм для первого октанта (рассмотренный ранее):

. . .

инициализируем с поправкой на половину пикселя

= 2 * D y — D x

начало основного цикла

for I = 1 to D x

Plot (x, y)

while ( ? 0)

y = y + 1

= — 2 * D x

end while

x = x + 1

= + 2 * D y

next I

finish

Модифицируем алгоритм для обработки отрезка в любом октанте. Определим номер квадранта (где находится отрезок) и угловой коэффициент. Если последний > 1, то y изменяется на 1. Критерий ошибки Брезенхема используется для установления x. Величина (1 или -1) определится номером квадранта.