Bresenham Line Drawing Algorithm

By Priyanshu Vaish|Updated : June 16th, 2022

The Bresenham Line Drawing Algorithm is one of the popular computer graphics algorithms used to overcome the drawback of the DDA(Digital Differential Analyzer) algorithm. The Bresenham line drawing algorithm is less fast than the DDA algorithm.

The Bresenham implements the Bresenham line drawing algorithm. This algorithm is efficient because it involves the three integer operations: addition, subtraction, and multiplication. These three operations will be performed rapidly, so lines should be formed quickly. Let us discuss the need, advantages and algorithm of the Bresenham line drawing algorithm in this article.

Table of Content

What is Bresenham Line Drawing Algorithm?

The Bresenham line drawing algorithm is used to determine the points of the N-dimensional raster that will be selected to generate the close approximation to the straight line between the two coordinates or points. In the Bresenham line drawing algorithm, the integer is only for addition, subtraction, and multiplication.

The operation in the Bresenham line drawing algorithm is performed quickly so the line can be generated quickly. Suppose the line equation is y = mx + c. If the slope(m) value is 1, both the coordinate incremented, but if the slope value is less than 1, then the y coordinate may or may not be incremented. The Bresenham line drawing algorithm is used where the slope value is not equal to one.

Why do we Need the Bresenham Line Drawing Algorithm?

The Bresenham line drawing algorithm is needed to overcome the problem of floating points in the DDA (Digital Differential Analyzer) that is for the DDA algorithms, the equations are:

For X-axis  Δx = x2 – x1

For Y-axis  Δy = y2 – y1

Step = max(Δx, Δy)

Xinc = Δx/step

Yinc = Δy/step

As in the above equation, the division operation is used, which returns the float value. The float takes more time for addition, subtraction, and multiplication as compared to an integer. Therefore, the Bresenham line drawing algorithm is used to overcome the floating-point problem.

Algorithm of the Bresenham Line Drawing Algorithm

The Bresenham line drawing algorithm takes four integer values that are x1, y1, x2, and y2. The Bresenham line drawing algorithm given below is for the slope value less than one that is as follows:

Algorithm_bresenham(x1, y1, x2, y2)

{

x= x1;

y=y1;

dx = x2 – x2;

dy = y2 – y1;

p = 2dx = dy;

while(x <= x2)

{

putpixel(x,y);

x++;

if(p<0)

p=p+2dx;

else

p=p + 2dy – 2dx;

y++;

}

}

Advantages of Bresenham Line Drawing Algorithm

The advantage of the Bresenham line drawing Algorithm is that the Bresenham line drawing algorithm is easy to implement. It is very fast to execute but lesser than the DDA(Digital Differential Analyzer) algorithm and is also incremental.

The points generated by the Bresenham line drawing algorithm are more correct or accurate than DDA(Digital Differential Analyzer) Algorithm. The Bresenham line drawing algorithm uses fixed points or coordinates only.

Comments

write a comment

FAQs on Bresenham Line Drawing Algorithm

  • The Bresenham line drawing algorithm is the line drawing algorithm in computer graphics that is used to determine the points of the N-dimensional raster that will be selected to generate a close approximation to the straight line between the two coordinates or points.

  • Two algorithms are used for drawing a line over the screen: DDA (Digital Differential Analyzer) and Bresenham line drawing algorithms. The main difference between DDA and Bresenham line drawing algorithms is that the DDA algorithm is used for the floating-point values while the Bresenham line drawing algorithm is used for the integer with round-off functions.

  • The Bresenham line drawing algorithm is faster than the DDA(Digital Differential Analyzer) algorithm in line drawing because the Bresenham line drawing algorithm performs only addition and subtraction in the calculations and uses only the integer values, so it runs faster.

  • The disadvantages of the Bresenham Line Drawing Algorithm are as the Bresenham Line Drawing Algorithm is for drawing the basic line. Though it improves the accuracy of generated coordinates or points, the resulting line is still not smooth. The diminishing jaggies will not handle by the Bresenham line drawing algorithm.

  • The decision parameter calculated in the Bresenham line drawing algorithm for slope |m|>1 is as follows:

    1. Input two endpoints or coordinates of the line that is (x1,y1) and (x2,y2).

    2. The first point (x1,y1) is plotted on the graph or screen.

    3. Now calculate the difference in X and Y coordinates, that is: dx =|x2 – x1|; dy = |y2 – y1 |

    4. The initial decision parameter will be calculated aa:  p = 2*dx – dy.

    5. For I = 0 to dy in step 1.

    If p < 0 then

    the Y coordinate incremented as y1 = y1 + 1 and then plot(x1,y1).

    Calculate new decision parameter as p = p + 2dx.

    Else

    the X coordinate incremented as x1 = x1 + 1

    the Y coordinate incremented as y1 = y1 + 1

    and then plot(x1, y1)

    Calculate new decision parameter as p = p + 2dx – 2*dy

    6. END

Follow us for latest updates