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

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

Алгоритм построен так, что требуется проверять лишь знак этой ошибки. На рис. 13.1 это иллюстрируется для отрезка в первом октанте, то есть для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0, 0) больше чем 1/2, то его пересечение с прямой x = 1 будет расположено ближе к прямой y = 1, чем к прямой y = 0. Следовательно, точка растра (1, 1) лучше аппроксимирует ход отрезка, чем точка (1, 0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента, равного 1/2, нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1, 1).

Не все отрезки проходят через точки растра. Подобная ситуация иллюстрируется на рис. 13.2, где отрезок с тангенсом угла наклона 3/8 сначала проходит через точку растра (0, 0) и последовательно пересекает три пиксела. Также иллюстрируется вычисление ошибки при представлении отрезка дискретными пикселами. Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной -1/2. Таким образом, если угловой коэффициент отрезка больше или равен 1/2, то величина ошибки в следующей точке растра с координатами (1, 0) может быть вычислена как e = e + m, где m — угловой коэффициент. В нашем случае при начальном значении ошибки -1/2 e = -1/2 + 3/8 = -1/8.

Так как e отрицательно, отрезок пройдет ниже середины пиксела. Следовательно, пиксел на том же самом горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому у не увеличивается. Аналогично вычисляем ошибку e = -1/8 + 3/8 = 1/4 в следующей точке растра (2, 0). Теперь e положительно, а значит, отрезок пройдет выше средней точки. Растровый элемент (2, 1) со следующей по величине координатой y лучше аппроксимирует положение отрезка. Следовательно, y увеличивается на единицу. Прежде чем рассматривать следующий пиксел, необходимо откорректировать ошибку вычитанием из нее единицы. Имеем e = 1/4 - 1 = -3/4.

Заметим, что пересечение вертикальной прямой x = 2 с заданным отрезком лежит на 1/4 ниже прямой y = 1. Если же перенести отрезок 1/2 вниз, мы получим как раз величину -3/4. Продолжение вычислений для следующего пиксела дает e = -3/4 + 3/8 = -3/8.

Так как e отрицательно, то y не увеличивается. Из всего сказанного следует, что ошибка — это интервал, отсекаемый по оси y рассматриваемым отрезком в каждом растровом элементе (относительно -1/2).

Приведем алгоритм Брезенхема для первого октанта, то есть для случая 0 <= Dy <= Dx.

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

Предполагается, что концы отрезка (x₁, y₁) и (x₂, y₂) не совпадают
Integer — функция преобразования в целое
x, y, Dx, Dy — целые
e — вещественное
инициализация переменных
x = x₁
y = y₁
Dx = x₂ - x₁
Dy = y₂ - y₁
инициализация е с поправкой на половину пиксела
е = Dy/Dx - 1/2
начало основного цикла
for i = 1 to Dx
     Plot(x, y)
     while (e >= 0)
        y = y + 1
        е = е - 1
     end while
     x = x + 1
     е = е + Dy/Dx
next i
finish

Пример алгоритма Брезенхема. Рассмотрим отрезок, проведенный из точки (0, 0) в точку (5, 5). Разложение отрезка в растр по алгоритму Брезенхема приводит к такому результату:
начальные установки
x = 0
y = 0
Dx = 5
Dy = 5
е = 1 - 1/2 = 1/2

Результаты пошагового выполнения основного цикла приведены в таблице.

В результате работы алгоритма Брезенхема в первом октанте получится картина, представленная на рис. 13.3. Заметим, что точка растра с координатами (5, 5) не активирована. Эту точку можно активировать путем изменения условия цикла for-next на 0 to Dx. Активацию точки (0, 0) можно устранить, если поставить оператор Рlоt непосредственно перед строкой next i.