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

Так как приращения координат, как правило, не являются целой степенью двойки, то в ЦДА-алгоритме (см. предыдущий пункт) требуется выполнение деления, что не всегда желательно, особенно при аппаратной реализации.

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

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

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

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

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

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

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

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

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

Е₂ = Е₂ - 1.

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

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

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

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

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

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

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

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

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. Для других случаев алгоритм строится аналогичным образом.

Разработаны алгоритмы цифрового генератора для окружностей и других конических сечений.