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

Брезенхем в работе [] предложил алгоритм, не требующий деления, как и в алгоритме несимметричного ЦДА, но обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка, как в алгоритме обычного ЦДА. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. а), а если угловой коэффициент > 1/2, то - в позицию (1,1) (рис. б). Для принятия решения куда заносить очередной пиксел вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки.

Рис. 0.2.3: Алгоритм Брезенхема генерации отрезков

Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.

Для вычисления Е без ограничения общности упрощающе положим, что рассматриваемый вектор начинается в точке (0,0) и проходит через точку (4, 1.5) (см. рис. 0.3в), т.е. имеет положительный наклон меньший 1.

Из рис. 0.3в видно, отклонение для первого шага:

Е₁ = Py/Px - 1/2 < 0,

поэтому для занесения пиксела выбирается точка (1,0).

Отклонение для второго шага вычисляется добавлением приращения Y-координаты для следующей X-позиции (см. рис. 0.3в):

Е₂ = Е₁ + Py/Px > 0,

поэтому для занесения пиксела выбирается точка (2,1). Так как отклонение считается от Y-координаты, которая теперь увеличилась на 1, то из накопленного отклонения для вычисления последующих отклонений надо вычесть 1:

Е₂ = Е₂ - 1.

Отклонение для третьего шага:

Е₃ = Е₂ + Py/Px < 0,

поэтому для занесения пиксела выбирается точка (3,1).

Суммируя и обозначая большими буквами растровые точки, а маленькими - точки вектора, получаем:

Е₁ = y₁ - 1/2 = dY/dX - 1/2.

Возможны случаи:

Е₁ > 0	E₁ Ј 0
ближайшая точка есть:
X₁ = X₀ + 1; Y₁ = Y₀ + 1;	X₁ = X₀ + 1; Y₁ = Y₀;
E₂ = Е₁ + Py/Px - 1;	E₂ = E₁ + Py/Px.

Так как интересует только знак Е, то можно избавиться от неудобные частных умножением E на 2×Px:

	E₁ = 2×Py - Px
E₁ > 0:	E₂ = E₁ + 2×(Py - Px)
E₁ Ј 0:	E₂ = E₁ + 2×Py

Таким образом получается алгоритм, в котором используются только целые числа, сложение, вычитание и сдвиг:
X= x1;
Y= y1;
Px= x2 - x1;
Py= y2 - y1;
E= 2*Py - Px;
i= Px;
PutPixel(X, Y); /* Первая точка вектора */
while (i= i- 1 і 0) {
if (E і 0) {
X= X + 1;
Y= Y + 1;
E= E + 2*(Py - Px);
} else
X= X + 1;
E= E + 2*Py;
PutPixel(X, Y); /* Очередная точка вектора */
}

Этот алгоритм пригоден для случая 0 Ј dY Ј dX. Для других случаев алгоритм строится аналогичным образом.

На рис. приведен пример генерации по алгоритму Брезенхема того же самого отрезка, что и показанного на рис. 0.2 для генерации по алгоритму несимметричного ЦДА. Из сравнения рисунков видно, что результаты различны.