Bresenham’s Line algorithm :-

Bresenham’s line algorithm uses only integer addition and subtraction and multiplication by 2, and we know that the computer can perform the operations of integer addition and subtraction very rapidly. The computer is also time-efficient when performing integer multiplication by powers of 2. Therefore, it is an efficient method for scan-converting straight lines.

Although developed originally for use with digital plotters, Bresenham's algorithm is equally suited for use with CRT raster devices. The basic principle of Bresenham's line algorithm is to select the optimum raster locations to represent a straight line. To accomplish this, the algorithm always increments either x or y by one unit depending on the slope of line. The increment in the other variable is determined by examining the distance between the actual line location and the nearest pixel. This distance is called decision variable or the error. This is illustrated in the Fig. below.

As shown in the figure above, the line does not pass through all raster points (pixels). It passes through raster point (0, 0) and subsequently crosses three pixels. It is seen that the intercept of line with the line x = 1 is closer to the line y = 0, i.e. pixel (1, 0) than to the line y = 1 i.e. Pixel (1, 1). Hence, in this case, the raster point at (1, 0) better represents the path of the line than that at (1. 1). The intercept of the line with the line x = 2 is close to the line y = 1. i.e. pixel (2, 1) than to the line y = 0. i.e. pixel (2,0). Hence, the raster point at (2, 1) better represents the path of the line, as shown in the figure above.

In mathematical terms error or decision variable is defined as

                                     e = DB - DA    or   DA - DB

Let us define e = DB - DA.Now if e > 0,then it implies that DB > DA, i.e.the pixel above the line is closer to the true line. If DB < DA (i.e. e < 0) then we can say that the pixel below the line is closer to the true line. Thus by checking only the sign of error term it is possible to determine the better pixel to represent the line path.

The error term is initially set as

                                  e  =  2 Δy - Δx

           where            Δy =  y2 - y1, and  Δx = x2 - x1

Then according to value of e following actions are taken,

while ( e ≥ 0) 
 {
    y = y + 1 
    e = e - 2 * Δx 
}
    x = x + 1 
    e = e + 2 * Δy

when e ≥ 0, error is initialized with e = e - 2 * Δx. This is continued till error is negative. In each iteration y is incremented by 1.

when e < 0, error is initialized to e = e + 2 * Δy. In both the cases x is incremented by 1.

Let us see the Bresenham's line drawing algorithm.

Bresenham’s Line algorithm for |(m = Δy / Δx)| < 1 :-

1. Read the line end points (x1, y1) and (x2,y2) such that they are not equal. 
    [ if equal then plot that point and exit ] 
2.  Δx  = |x2 - x1|    and  Δy  = |y2 - y1| 
3. [Initialize starting point]
     x  =  x1 and  y  =  y1 

4. e = 2  * Δy - Δx 
    [Initialize value of decision variable or error to compensate for nonzero intercepts]

5. i=1[ Initialize counter ]

6. Plot(x , y) 

7. whi1e( e ≥ 0) 
    {
      y = y + 1 
      e = e - 2 * Δx
    }
      x = x + 1 
      e = e + 2 * Δy

8. i = i + 1 

9. if(i ≤ Δx) then go to step6.

10. Stop.

Problem: - Consider the line from (5, 5) to (13, 9). Use the Bresenham's algorithm to rasterize the line.

Solution :-

Evaluating steps 1 through 4 in the Bresenham’s algorithm we have,

Given: -
step 1 :- x1 = 5 , y1 = 5 and x2 = 13 , y2 = 9 .

step 2 :- Δx = | 13 - 5| =8 Δy = | 9 - 5 | = 4

step 3 :- x = 5 , y = 5

step 4 :- e = 2 * Δy - Δx = 2 * 4 - 8 = 0 .

Tabulating the results of each iteration in the step 5 through 10.

The results are plotted as shown in Fig. below