The Bresenham Line Algorithm:

The Bresenham Line Algorithm:

The Bresenham algorithm is another incremental scan conversion algorithm The big advantage of this algorithm is that it uses only integer calculations
The Big Idea
Move across the x axis in unit intervals and at each step choose between two different y coordinates

For example, from position (2, 3) we have to choose between (3, 3) and (3, 4)
We would like the point that is closer to the original line





At sample position xk+1 the vertical separations from the mathematical line are labelled dupper and dlower The y coordinate on the mathematical line at xk+1 is:








So, a decision parameter pk for the kth step along a line is given by:




The sign of the decision parameter pk is the same as that of dlower – dupper
If pk is negative, then we choose the lower pixel, otherwise we choose the upper pixel .
Remember coordinate changes occur along the x axis in unit steps so we can do everything with integer calculations
At step k+1 the decision parameter is given as:



Subtracting pk from this we get:














Bresenham Example



Bresenham s algorithm is generalized to lines with arbitrary slope by considering the symmetry between the various octants and quadrants of the xy plane. For a line with positive slope greater than 1, we interchange the roles of the x and y directions. That is, we step along they direction in unit steps and calculate successive x values nearest the line path. Also, we could revise the program to plot pixels starting from either endpoint. If the initial position for a line with positive slope is the right endpoint, both x and y decrease as we step from right to left. For negative slopes, the procedures are similar, except that now one coordinate decreases as the other increases.
Table 3.7 can be used to determine the octant of the slope. Given a line segment from (x1, y1) to (x2, y2), first reorder the points, if necessary, such that x1 ? x2, then use the table. The top row of the table reads: If ?y ? 0 and ?x ? ?y, then the slope is positive and is less than or equal 1. The octant is either 1 or, if the points had to be swapped, it is 5.


























General Bresenham s algorithm for all Octants
Inputs: Start point ( X1 , Y1 ) , End point ( X2 , Y2 )
Begin
X=X1
Y=Y1
?X =Abs (X2-X1)
?Y =Abs(Y2-Y1)
S1=Sign (X2-X1)
S2=Sign (Y2-Y1)
If ?Y > ?X Then
T= ?X , ?X = ?Y , ?Y =T , Interchange=1
Else
Interchange =0
End If
E= 2 ?Y - ?X
A= 2 ?Y
B= 2?Y - 2?X
Plot (X,Y)
For i=1 to ?X
If ( E < 0)
If Interchange=1 Then Y= Y + S2
Else X=X+S1
E= E +A
Else
Y=Y + S2
X=X + S1
E = E + B
End If
Plot (X,Y)
End for
End

Note : Sign function returns : -1 if its argument is < 0
: 0 if its arguments is = 0
: +1 if its arguments is > 0
Ex: Sign(-10) = -1 Sign (5) = 1



Example 2: Draw the line from (0,0) to (-8,-4) using General
Bresenham algorithm
Solution : X=0 , Y=0 , ?X =8 , ?Y=4 , A=2?Y= 8 , B=2?Y-2?X=-8 , S1=-1 , S2=-1
Because ?X > ?Y then Interchange=0 , E=0
Iteration E X Y Plot
0 0 0 (0,0)
1 -8 -1 -1 (-1,-1)
2 0 -2 -1 (-2,-1)
3 -8 -3 -2 (-3,-2)
4 0 -4 -2 (-4,-2)
5 -8 -5 -3 (-5,-3)
6 0 -6 -3 (-6,-3)
7 -8 -7 -4 (-7,-4)
8 0 -8 -4 (-8,-4)