Лекции по компьютерной графике

2.4.          Алгоритм Брезенхема рисования линии.

В 1965 году Брезенхеймом был предложен простой целочисленный алгоритм для растрового построения отрезка. В алгоритме используется управляющая переменная d_i, которая на каждом шаге пропорциональна разности между s и t (см. рис.2.4.1). На рис.2.4.1 приведен i-ый шаг, когда пиксел P_i-1 уже найден как ближайший к реальному изображаемому отрезку, и теперь требуется определить, какой из пикселов должен быть установлен следующим: T_i или S_i.

Если s<t, то S_i ближе к отрезку и необходимо выбрать его; в противном случае ближе будет T_i. Другими словами, если s-t<0, то выбирается S_i; в противном случае выбирается T_i.

рис. 2.4.1.

Изображаемый отрезок проводится из точки (x₁, y₁) в точку (x₂, y₂). Пусть первая точка находится ближе к началу координат, тогда перенесем обе точки, T(x₁, y₁) так, чтобы начальная точка отрезка оказалась в начале координат, тогда конечная окажется в (D x, D y), где D x= x₂- x₁ , D y= x₂- x₁. Уравнение прямой теперь имеет вид y=x× D y/Dx. Из рисунка следует, что

поэтому

помножим на D x:

так как D x>0, величину D x(s-t) можно использовать в качестве критерия для выбора пиксела. Обозначим эту величину d_i :

так как r = x_i-1, q = y_i-1, получаем:

Известно, что x_I - x_i-1=1.

Если d_i >= 0, то выбираем T_i, тогда

Если d_i <0, то выбираем S_i, тогда

Таким образом, мы получили итеративную формулу для вычисления критерия d_i.
Начальное значение d₁=2D y-D x.

Можно построить блок схему алгоритма:

рис. 2.4.2

Линейная интерполяция по яркости при построении отрезка по алгоритму Брезенхема получается параметрическим способом, т.е. , где N – длина отрезка в пикселях.