Bresenham Line Drawing Algorithm

What is the Bresenham Line Drawing Algorithm?

The Bresenham Line Drawing Algorithm is a fundamental algorithm used to draw straight lines on a pixel-based display such as a computer screen. It determines the points of an n-dimensional raster that should be selected to form a close approximation to a straight line between two points. It was developed by Jack E. Bresenham in 1962 and is widely used due to its efficiency and simplicity.

The Bresenham line algorithm is one of the most effective incremental techniques for scan-converting lines. It is an algorithm that chooses the locations of the points in an n-dimensional raster that should be plotted to approximate a straight line between two points. It is a raster line-generating algorithm that is accurate and effective and employs just incremental integer calculations.

Lines, circles, and other curves can be displayed using the Bresenham algorithm. The horizontal axes identify pixel columns, while the vertical axes show scan-line positions, demonstrating how the Bresenham technique can be used to draw lines on a computer screen, subtract data, and shift bits.

Deriving the Bresenham Line Drawing Algorithm

The vertical separations from the mathematical line at sample location x_k +1 are denoted by the letters d_upper and d_lower. The y coordinate on the line at x_k +1 is:

y = m * (x_k + 1) + b

So, d_upper and d_lower are given as follows:

d_lower = y - y_k

               = m * (x_k + 1) + b - y_k

d_upper = (y_k + 1) - y

                = y_k + 1 - m * (x_k +1) - b
 

These can be used to make a simple decision on which pixel is nearer the mathematical line.

The difference between the two-pixel places served as the basis for this straightforward decision:

d_lower - d_upper = 2m * (x_k +1) - 2y_k + 2b -1
 

Let’s substitute m with ∆y/∆x where ∆x and ∆y are the differences between the endpoints:

∆x * (d_lower - d_upper) = ∆x * ( (2∆y / ∆x) * (x_k + 1) - 2y_k) + (2b - 1)

                                            = 2∆y.x_k - 2∆x.y_k + 2∆y + ∆x * (2b - 1)

                                            = 2∆y.x_k - 2∆x.y_k + c
 

So, at the kth step along a line, a decision parameter p_k is given by:

p_k = ∆x * (d_upper - d_lower)

     = 2∆y.x_k - 2∆x.y_k + c
 

The sign of the decision parameter p_k and that of (d_lower – d_upper) is the same.

If p_k is negative, we select the lower pixel; otherwise, we select the upper pixel.

Because coordinate changes along the x-axis occur in unit steps, we can handle everything with integer calculations.

The decision parameter is given at step k+1 as:

p_k+1 = 2∆y.(x_k+1) - 2∆x.(y_k+1) + c
 

Subtracting p_k from this, we get:

p_k+1 - p_k = 2∆y.(x_k+1 - x_k) - 2∆x * (y_k+1 - y_k)
 

But, x_k+1 is the same as x_k +1, so:

p_k+1 = p_k +2∆y - 2∆x * (y_k+1 - y_k)
 

Where y_k+1 - y_k is either 0 or 1 depending on the sign of p_k

The initial decision parameter p₀ is evaluated at (x₀, y₀) and is written as follows:

p₀ = 2∆y - ∆x

Step Wise Algorithm

The step-wise Bresenham’s line drawing algorithm is given below:

• Input the two endpoints of the line, save the left endpoint in (x₀ , y₀)
   
• Plot the point (x₀ , y₀)
   
• Calculate the constants Δx, Δy, 2Δy, and (2Δy - 2Δx) and obtain the first value for the decision parameter as:
  p₀ = 2Δy - Δx
   
• Perform the following test at each x_k along the line, beginning at k = 0. If p_k < 0, then the next point to the plot is (x_k+1 ,  y_k ) and:
  p_k+1 = p_k + 2Δy
  Otherwise, the next point to plot is (x_k+1 , y_k+1) and: 
  p_k+1 = p_k + 2Δy - 2Δx
   
•  Repeat step 4, (Δx – 1) times

Code Implementation of Bresenham Line Drawing Algorithm

The C++ code implementation of the Bresenham Line Drawing Algorithm is given below:

• C++
• Java
• Python
• JS
• C#

C++

#include <bits/stdc++.h>
using namespace std;

// function for printing the points needed for line generation
void bresenham_line_algo(int a1, int b1, int a2, int b2)
{
	int m_new = 2 * (b2 - b1);
	int slope = m_new - (a2 - a1);
	for (int x = a1, y = b1; x <= a2; x++) {
		cout << "(" << x << "," << y << ")\n";
		// Adding slope to increment angle
		slope += m_new;
		//Slope error has reached its limit; it is time to increase y and update the slope error
		if (slope >= 0) {
			y++;
			slope -= 2 * (a2 - a1);
		}
	}
}

int main()
{
	int a1 = 5, b1 = 10, a2 = 15, b2 = 8;
	// calling Bresenham Line Algorithm function
	bresenham_line_algo(a1, b1, a2, b2);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class BresenhamLine {
    public static void bresenhamLineAlgo(int a1, int b1, int a2, int b2) {
        int m_new = 2 * (b2 - b1);
        int slope = m_new - (a2 - a1);
        
        for (int x = a1, y = b1; x <= a2; x++) {
            System.out.println("(" + x + "," + y + ")");
            slope += m_new;
            
            if (slope >= 0) {
                y++;
                slope -= 2 * (a2 - a1);
            }
        }
    }

    public static void main(String[] args) {
        int a1 = 5, b1 = 10, a2 = 15, b2 = 8;
        bresenhamLineAlgo(a1, b1, a2, b2);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def bresenham_line_algo(a1, b1, a2, b2):
    m_new = 2 * (b2 - b1)
    slope = m_new - (a2 - a1)

    x, y = a1, b1
    while x <= a2:
        print(f"({x},{y})")
        slope += m_new
        
        if slope >= 0:
            y += 1
            slope -= 2 * (a2 - a1)
        
        x += 1

# Driver code
a1, b1, a2, b2 = 5, 10, 15, 8
bresenham_line_algo(a1, b1, a2, b2)

You can also try this code with Online Python Compiler

Run Code

JS

function bresenhamLineAlgo(a1, b1, a2, b2) {
    let m_new = 2 * (b2 - b1);
    let slope = m_new - (a2 - a1);

    for (let x = a1, y = b1; x <= a2; x++) {
        console.log(`(${x},${y})`);
        slope += m_new;

        if (slope >= 0) {
            y++;
            slope -= 2 * (a2 - a1);
        }
    }
}

// Driver code
let a1 = 5, b1 = 10, a2 = 15, b2 = 8;
bresenhamLineAlgo(a1, b1, a2, b2);

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;

class BresenhamLine
{
    static void BresenhamLineAlgo(int a1, int b1, int a2, int b2)
    {
        int m_new = 2 * (b2 - b1);
        int slope = m_new - (a2 - a1);

        for (int x = a1, y = b1; x <= a2; x++)
        {
            Console.WriteLine($"({x},{y})");
            slope += m_new;

            if (slope >= 0)
            {
                y++;
                slope -= 2 * (a2 - a1);
            }
        }
    }

    static void Main()
    {
        int a1 = 5, b1 = 10, a2 = 15, b2 = 8;
        BresenhamLineAlgo(a1, b1, a2, b2);
    }
}

In the above code, we assume that the line is drawn from left to right, and a1<a2 and b1<b2. The time complexity of the code is O(a2-a1) and the space complexity is O(1).

Output:

(5, 10)
(6, 11)
(7, 12)
(8, 13)
(9, 14)
(10, 15)
(11, 16)
(12, 17)
(13, 18)
(14, 19)
(15, 20)

Advantages of the Bresenham Line Drawing Algorithm

The benefits of the Bresenham Line Drawing Algorithm are as follows:

• The implementation of the Bresenham algorithm is simple and does not require a large amount of buffer memory
• The working of this algorithm is faster and more stepwise, so it's easy to understand
• You can draw the line in any direction in the program by using the Bresenham algorithm
• It can be implemented using hardware because it does not require multiplication and division

Disadvantages of the Bresenham Line Drawing Algorithm

Some of the disadvantages of the Bresenham algorithm are given below:

• Even if it enhances the precision of the generated points, the resulting line could be smoother
• This algorithm does simple line drawing, which means it is unable to draw curves and other complex shapes
• The algorithm can only draw one-pixel-thick lines. This constraint can be an issue when thicker lines are required

Difference between DDA Algorithm and Bresenham's Line Algorithm

Frequently Asked Questions

What is the Bresenham line drawing algorithm?

Bresenham's line algorithm is an efficient raster graphics algorithm that uses only integer calculations to determine points for a straight-line path.

Why is Bresenham better than DDA?

Bresenham’s algorithm is faster and more accurate than DDA as it avoids floating-point operations, using only integer arithmetic for better performance and precision.

What is Bresenham's circle drawing algorithm?

Bresenham’s circle algorithm efficiently plots a circle using integer calculations and symmetry, minimizing computations while ensuring accurate pixel placements on a raster display.

Conclusion

We have discussed the Bresenham line drawing algorithm. This algorithm stands as a testament to the ingenuity and efficiency of computer graphics algorithms. Its elegance lies in its ability to render straight lines with precision and speed, making it a cornerstone in the field of raster graphics