Bresenham’s Line Drawing Algorithm
Explanation of Bresenham’s Line Drawing Algorithm with examples
We talked about the basics of line drawing in computer graphics and the DDA Line Drawing algorithm in the previous article. In this article, I am going to explain another popular scan conversion line algorithm, Bresenham’s line drawing algorithm.
Read my previous article if you want to know more about scan converting a line.
Finding the next pixel in Bresenham’s algorithm
Similar to the DDA algorithm, we need two endpoints, P and Q, to draw a line using Bresengham’s algorithm.
Bresenham’s algorithm only uses integer values, integer comparisons, and additions. This makes Bresenham’s algorithm more efficient, fast, and easier to calculate than the DDA algorithm.
Once we choose a pixel, we have two possible pixels to select as the next pixel.
- Right side pixel (East — E)
- Upper right pixel (North East — NE)
Assume current pixel coordinates are (x, y)
Select E as next pixel — increment only X value by 1 - (x+1, y)
Select NE as next pixel — increment both X and Y values by 1 - (x+1, y+1)
To select the next pixel, we are using a decision parameter based on the slope error. If the slope error is greater than 0.5, the actual line is near the NE. The line is closer to E when the slope error is less than 0.5.
At each step, we need to calculate the decision variable incrementally by adding △E or △NE depending on the choice of the pixel.
Let’s try to get a better understanding of the algorithm.
Bresenham’s Algorithm
Assume starting point is (x1, y1) and the ending point is (x2, y2)
Scenario: x1 < x2 and 0 < slope < 1
First, we need to calculate dx and dy
We use dx and dy values to calculate the initial decision variable (d). value of the decision variable is changed on each step.
Similarly, we need to calculate △E and △NE values. After the first initiation, these values are not changed.
Now we have to decide what is the best pixel to choose next, NE or E. We are using the sign of decision parameter to take that decision.
Case 1: d ≤ 0
We are going to select pixel E if the decision variable is negative or zero. In this scenario, we only increment the x value by 1 and calculate the new decision variable using △E. Remember to keep y value as it is.
Case 2: d > 0
When the decision variable is positive, select NE as the next pixel. In addition to calculating the new decision variable and increment the x value, need to increment the y value by 1.
Continue until x = x2
Let’s try this algorithm with an example.
Example
I am going to take the same example I used in the DDA algorithm tutorial so that we can compare the results.
Assume x1 < x2 and 0 < slope < 1
Draw a line from (2, 1) to (8, 5)
X1 = 2, X2 = 8, Y1 = 1 and Y2 = 5
Before calculating the decision variable, we need to find the difference between X and Y coordinate values, dx and dy.
Now we can calculate the initial decision variable, △E, and △NE values using dx and dy.
Follow case 1 and case 2 to find the next best pixel for the line.
If you compare these results with the results of the DDA algorithm, you can see that we have got the same results as the DDA algorithm.
As I mentioned before, Bresenham’s algorithm involves simple calculations, which makes this algorithm efficient and faster than the DDA algorithm.
Bresenham’s algorithm provides more accurate results than the DDA algorithm due to the involvement of integer arithmetic computations.
Up to now we only talked about the general scenario of this algorithm, where x1 < x2 and 0<slope<1. There are three other scenarios we need to consider.
Case 1: x1 > x2
In this case, we should draw the line from left to right. Take (X2, Y2) as the starting point and (X1, Y1) as the endpoint, then continue the Bresenham’s algorithm.
Case 2: slope < 0
In the case of a negative slope, we can get the line with a positive slope by reflecting the original line around the X-axis. We perform Bresenham’s algorithm to the line with a positive slope and reflect back around the X-axis to get the pixels.
Example
Draw a line from (x1, y1) to (x2, y2). In this scenario, we assume that the slope is negative.
Now, instead of using Bresenham from (x1, y1) to (x2, y2), use the algorithm on (x1, -y1) to (x2, -y2). After calculating all the pixels from (x1, -y1) to (x2, -y2), we change the sign of the y values of all the pixels to get the pixels for the original line.
Case 3: slope > 1
In the case of the slope is greater than 1, we can use Bresenham’s algorithm by exchanging the x and y values. after the calculations, exchange the x and y values back to get the pixels to display on the line.
Example
Draw a line from (x1, y1) to (x2, y2). Assume that the slope is greater than 1.
Use Bresenham’s algorithm on (y1, x1) to (y2, x2). Calculate the pixels of the line as previously. Then convert all the pixels back by exchanging x and y values.
GitHub link to Bresenham’s algorithm — https://github.com/anushaihalapathirana/Bresenham-line-drawing-algorithm
npm package for Bresenham’s line algorithm — https://www.npmjs.com/package/bresenham-line-algorithm
