#### How To Implement Bresenham’s Line Drawing Algorithm In C?

by

, 04-17-2011 at 10:13 AM (76279 Views)
The Bresenham’s algorithm offers the following four advantages over the other line drawing algorithms:

1) It involves simple addition and does not perform any multiplication or division. As a result, it consumes less time and memory during execution.

2) It involves simple integer arithmetic and not real or floating-point arithmetic.

3) Its calculations use simple constants instead of complex first- or second-order equations.

To draw a line between two endpoints, the Bresenham’s algorithm evaluates all the intermediate points nearest the line, instead of simply rounding the attained value. Following Figure shows a line drawn up to the point (xn, yn), with the next point (xn+1, yn+1) yet to be evaluated:

This figure shows the line drawn up to the point (xn, yn). The next point is decided between (xn+1, yn) and (xn+1, yn+1).

After plotting the current point, the Bresenham’s algorithm calculates the value of the successive point. In Figure after you plot (xn, yn), the next point chosen is (xn+1, yn) and (xn+1, yn+1), whichever is nearest to the line. The next point is determined by checking if the midpoint D, whose value is (xn+1, yn+1/2), lies above or below the line. If D lies above the line, as it does in above Figure, the point (xn+1, yn) is closest to the line; if D lies below the line, (xn+1, yn+1) is closest to the line. For example, the equation of the line for the function g(x, y) is:

A point (xk, yk) lies on the line if g(xk, yk) = 0, below the line if g(xk, yk) > 0, and above the line if g(xk, yk) < 0. These relationships enable you to decide the position of point D and to select the next point to be plotted.g(x, y) = Lx + My + N ....(1)

The equation of the line in the slope-intercept form is:

To evaluate the values of L, M, and N in equation (1), compare the equation with equation (2). As a result,y = m x + c

= (Δy/Δx) x + c.

=> Δx . y = Δy . x + Δx . c

As a result, g(x, y) = Δy . x - Δx . y + Δx . c = 0. ....(2)

To draw a line using Bresenham’s algorithm:L = Δy, M = - Δx and N = Δx.c

1) Enter the values of the two endpoints of the line, (x1, y1) and (x2, y2).

2) Calculate Δx and Δy from these endpoints.

3) To determine the next pixel, check whether the sign of g(D) is plus or minus. You can determine this using the value of g(xn+1, yn+1/2) denoted by pn:

4) Choose the next pixel depending on the value of pn. If pn < 0, choose pixel (xn+1, yn); if > 0, choose pixel (xn+1, yn+1); and if pn = 0, choose either pixel.pn = g(xn+1, yn+1/2)

= L (xn+1) + M (yn+ 1/2) + N.

5) If you choose pixel (xn+1, yn), determine the next pixel from the sign of (xn+2, yn+ 1/2) ded by pn+1:

If you choose pixel (xn+1, yn+1), determine the next pixel from the sign of (xn+2, yn+ 3/2) denoted by pn+1:pn+1 = g(xn+2, yn+1/2)

= L (xn+2) + M (yn+1/2) + N

The increment in p is Δp1 = pn+1 - pn = L = Δy.

6) To draw the line, first calculate p0. The first pixel is (x1, y1) and the first midpoint D is at (x1+1, y1+ 1/2):pn+1 = g(xn+2, yn+3/2)

= L (xn+2) + M (yn+3/2) + N

The increment in p is, Δp2 = pn+1 - pn = L + M = Δy - Δx.

7) Multiply p0, p1 and p2 by 2 to remove the fraction. In all subsequent calculations for the Bresenham’s algorithm, you need only their sign. To remove the fraction:=> p0 = g(x1+1, y1+ 1/2)

= L (x1 + 1) + M (y1 + ½) + N

= L x1 + M y1 + N + L + M / 2

= g(x1, y1) + L + M / 2

Because (x1, y1) is a point on the line, as a result, g(x1, y1) = 0:

=> p0 = L + M / 2 = Δy - Δx/ 2.

8) To draw a line, start with (x1, y1) and initialize p to 0. After plotting the pixel (x1, y1), increment the value of p by p0. For subsequent pixels, check the value of p. If p < 0, choose (xn+1, yn) as the next pixel and increment p by Δp1. If p > 0, choose pixel (xn+1, yn+1) and increment p by Δp2. If p = 0, choose either. Plot the subsequent pixels until you reach (x2, y2).p0 = 2 . Δy - Δx,

Δp1 = 2 . Δy,

and Δp2 = 2 ( Δy - Δx)

Following Example shows how to draw a line with 0 <= slope <= 1, using the Bresenham’s algorithm:

The example above uses the Turbo C as the compiler.Code:#include<stdio.h> #include<conio.h> #include<math.h> #include<graphics.h> void draw_line(float,float,float,float); main() { int driver,mode; float x1,y1,x2,y2; clrscr(); printf("Enter the two endpoints of the line:"); printf("\nx1 ="); scanf("%f",&x1); printf("y1 ="); scanf("%f",&y1); printf("x2 ="); scanf("%f",&x2); printf("y2 ="); scanf("%f",&y2); clrscr(); driver = DETECT; initgraph(&driver,&mode,"\\tc\\bgi"); \\path of bgi can be different in your case draw_line(x1,y1,x2,y2); getch(); closegraph(); } void draw_line(float x1,float y1,float x2,float y2) { float dy,dx; float x,y; float p,p0,dp1,dp2; dy = y2-y1; dx = x2-x1; p0 = 2 * (dy - dx); dp1 = 2 * dy; dp2 = 2 * (dy - dx); putpixel(x1,y1,EGA_WHITE); p = p0; for(x=x1+1,y=y1;x<x2;x++) { if(p < 0) { p = p+dp1; putpixel(x,y,EGA_WHITE); } else { p = p+dp2; y++; putpixel(x,y,EGA_WHITE); } } }