BRESENHAM’S LINE ALGORITHM

1.      Explain the Bresenham’s line drawing algorithm with example. (AU MAY/JUNE 2012 IT)

BRESENHAM’S LINE ALGORITHM

1. Input the two line endpoints and store the left end point in (x0,y0)

2. load (x0,y0) into frame buffer, ie. Plot the first point.

3. Calculate the constants Δx, Δy, 2Δy and obtain the starting value for the decision parameter as P0 = 2Δy-Δx

4. At each xkalong the line, starting at k=0 perform the following test

If Pk< 0, the next point to plot is(xk+1,yk) and

 Pk+1 = Pk+ 2Δy

Otherwise, the next point to plot is (xk+1,yk+1) and

Pk+1 = Pk+ 2Δy - 2Δx 5. Perform step4 Δx times.

Implementation of Bresenham Line drawing Algorithm

voidlineBres (int xa,intya,intxb, int yb)

 {

int dx = abs( xa – xb) , dy = abs (ya - yb);

int p = 2 * dy – dx;

inttwoDy = 2 * dy, twoDyDx = 2 *(dy - dx);

int x , y, xEnd; /* Determine which point to use as start, which as end * /

if (xa> x b )

{

x = xb;

y = yb;

xEnd = xa;

}

else

{

x = xa;

y = ya;

xEnd = xb;

}

setPixel(x,y);

while(x<xEnd)

{

x++;

if (p<0) p+=twoDy;

else

{

y++;

p+=twoDyDx;

}

setPixel(x,y);

} }

Example : Consider the line with endpoints (20,10) to (30,18)

The line has the slope m= (18-10)/(30-20)=8/10=0.8

     Δx = 10Δy=8

The initial decision parameter has the value p0 = 2Δy- Δx = 6

and the increments for calculating successive decision parameters are

                                          2Δy=16                2Δy-2 Δx= -4

We plot the initial point (x0,y0) = (20,10) and determine successive pixel positions along the line path from the decision parameter as

TABULATION:

k	pk	(xk+1, yK+1)
0	6	(21,11)
1	2	(22,12)
2	-2	(23,12)
3	14	(24,13)
4	10	(25,14)
5	6	(26,15)

6	2	(27,16)
7	-2	(28,16)
8	14	(29,17)
9	10	(30,18)

RESULT:Advantages

1.      Algorithm is Fast

2.      Uses only integer calculations

Disadvantages

It is meant only for basic line drawing