Алгоритм Брезенхема вычерчивания отрезков для первого октанта.

 

Алгоритм Брезенхема выбирает оптимальные растровые координаты для представления отрезка. В процессе построения отрезка одна из координат (х или у, в зависимости от углового коэффициента отрезка) на каждом шаге алгоритма изменяется на 1. Эта координата является основной координатой. Изменение другой координаты (на 0 или на 1) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки (это - дополнительная координата). Такое расстояние называется ошибкой.

Рассмотрим рисование отрезка на рис. 8 для первого октанта, т. е. для отрезка с коэффициентом наклона k 0 < k < 1. Если отрезок, выходящий из точки (0, 0), имеет k > 1/2, то точка его пересечения с прямой х = 1 будет расположена ближе к прямой у = 1, чем к прямой у = 0. Поэтому точка растра (1, 1) лучше аппроксимирует ход отрезка. Если же k < 1/2, то лучше аппроксимирует ход отрезка точка (0, 0). Для k = 1/2 предпочтительного выбора нет, алгоритм выбирает точку (1, 1).

 

Удобнее подобрать такое значение ошибки, чтобы в алгоритме достаточно было проверить лишь знак ошибки, а не ее значение. Так как проверяется только знак ошибки, то ошибка первоначально устанавливается равной -1/2. И величина ошибки в следующей точке растра может быть вычислена как e = e + k. Если е < 0, то нужно зажигать пиксел на том же горизонтальном уровне, что и предыдущий, т. е. дополнительная координата не изменяется. Если е > 0, то отрезок пройдет выше уровня 1/2, значит, дополнительную координату нужно увеличить на 1. При этом необходимо откорректировать ошибку вычитанием из нее 1. Таким образом, ошибка - это интервал, отсекаемый по оси у отрезком в каждом растровом элементе относительно -1/2.

 

Алгоритм Брезенхема для первого октанта на псевдокоде:

 

(x₁,y₁) – начальная точка

(x₂, y₂) – конечная точка

e - ошибка

dx – приращение по координате x

dy – приращение по координате y

Plot (x, y) – процедура “подсвечивания” пиксела с координатами (x,y)

 

начало

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

x = x₁

y = y₁

dx = x₂ - x₁

dy = y₂ - y₁

инициализация ошибки

e = dy/dx - 1/2

основной цикл

for i = 1 to dx

Plot (x, y)

if e>=0 then

y = y + 1 изменение дополнительной координаты

e = e - 1 коррекция ошибки

конец if

x = x + 1 изменение основной координаты

e = e + dy/dx накопление ошибки

конец

 

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

 

Инициализация ошибки	Коррекция ошибки	Накопление ошибки

 

Чтобы алгоритм был полным, необходимо его распространить на все квадранты, что и осуществляет обобщенный алгоритм Брезенхема.