Bresenham’s Line Algorithm

Bresenham’s Line Algorithm

Bresenham's line-drawing algorithm uses an iterative scheme. A pixel is plotted at the starting coordinate of the line, and each iteration of the algorithm increments the pixel one unit along the major, or x-axis. The pixel is incremented along the minor, or y-axis, only when a decision variable (based on the slope of the line) changes sign. A key feature of the algorithm is that it requires only integer data and simple arithmetic. This makes the algorithm very efficient and fast.

Bresenham's algorithm determines which of these two pixel locations is nearer to the actual line by calculating the distance from each pixel to the line, and plotting that pixel with the smaller distance. Using the familiar equation of a straight line, y = mx + b, the y value corresponding to xi + 1 is y=m(xi+1) + b

The two distances are then calculated as:

d1 = y- yi

d1= m(xi + 1) + b- yi

d2 = (yi+ 1)- y

d2 = (yi+ 1) - m(xi + 1)- b

and,

d1 - d2 = m(xi+ 1) + b - yi - (yi + 1) + m(xi + 1) + b

d1 - d2 = 2m(xi + 1) - 2yi + 2b - 1

Multiplying this result by the constant dx, defined by the slope of the line m = dy/dx, the equation becomes:

dx(d1-d2)= 2dy(xi)- 2dx(yi) + c

where c is the constant 2dy + 2dxb - dx. Of course, if d2 > d1, then (d1-d2) < 0, or conversely if d1 > d2, then (d1-d2) >0. Therefore, a parameter pi can be defined such that

pi = dx(d1-d2)

                                                             Figure

pi = 2dy(xi) - 2dx(yi) + c

If pi > 0, then d1 > d2 and yi + 1 is chosen such that the next plotted pixel is (xi + 1, yi). Otherwise, if pi < 0, then d2 > d1 and (xi + 1, yi + 1) is plotted. (See Figure3.5 .) Similarly, for the next iteration, pi + 1 can be calculated and compared with zero to determine the next pixel to plot. If pi +1 < 0, then the next plotted pixel is at (xi + 1 + 1, Yi+1); if pi + 1< 0, then the next point is (xi + 1 + 1, yi + 1 + 1). Note that in the equation for

pi + 1, xi + 1 = xi + 1.

pi + 1 = 2dy(xi + 1) - 2dx(yi + 1) + c.

Subtracting pi from pi + 1, we get the recursive equation: pi + 1 = pi + 2dy - 2dx(yi + 1 - yi)

Note that the constant c has conveniently dropped out of the formula. And, if pi < 0 then

yi + 1= yi in the above equation, so that:

pi + 1 = pi + 2dy

or, if pi > 0 then yi + 1 = yi + 1, and

pi + 1 = pi + 2(dy-dx)

To further simplify the iterative algorithm, constants c1 and c2 can be initialized at the beginning of the program such that c1 = 2dy and c2 = 2(dy-dx). Thus, the actual meat of the algorithm is a loop of length dx, containing only a few integer additions and two compares.

Steps for bresenham’s line drawing algorithm

1. Input the two line endpoint & store the left endpoint in (Xo, Yo)

2. Load (Xo, Yo) into the frame buffer that is plotting of first point.

3. Calculate constants dx, dy, 2dy & 2dy – 2dx, & obtain the starting value for the decision parameter as:

P k+1 = Pk + 2dy

Otherwise, the next point to plot is (xk+1, yk +1) & Pk+1 = Pk + 2dy –2dx

4. Repeat step 4 dx times.