Bresenham’s Line Drawing Algorithm

Bresenham’s Line Drawing Algorithm is one of the most important algorithms in computer graphics for drawing a straight line between two given points. In a graphical display system, a line is mathematically continuous, but the screen is made up of discrete pixels. Therefore, the primary objective of this algorithm is to convert a continuous line into a sequence of discrete pixel positions that best represent the actual line.

The fundamental idea behind Bresenham’s algorithm is to determine, at each step of the drawing process, which pixel lies closest to the true mathematical line. Instead of calculating exact real-number positions, the algorithm incrementally selects the most appropriate pixel based on a decision parameter that measures the deviation from the ideal line.

A key characteristic of Bresenham’s algorithm is that it uses only integer calculations throughout the process. This eliminates the need for floating-point arithmetic, making the algorithm faster and more efficient compared to methods like the DDA algorithm. Because of this efficiency and accuracy, Bresenham’s algorithm is widely used in raster graphics systems for line generation.

When drawing a line:

• We move step-by-step along x-direction (for gentle slope)
• At each step, we decide:

Should we go:

• Straight (E → x+1, y) OR
• Diagonal (NE → x+1,  y+1)

This decision is made using a decision parameter Pk

Algorithm (Standard Case: 0 ≤ m ≤ 1)

Step 1:

Calculate ΔX and ΔY from the given input.

These parameters are calculated as:

• ΔX = X_n – X₀
• ΔY =Y_n – Y₀

Step 2:

Calculate the decision parameter P_k.

It is calculated as: P_k = 2ΔY – ΔX

Step 3:

Suppose the current point is (X_k, Y_k) and the next point is (X_k+1, Y_k+1).

Find the next point depending on the value of decision parameter P_k.

Case 1: If P_k < 0

Choose E (East)

• X_k+1 = X_k+1
• Y_k+1 = Y_k
• P_k+1 = P_k + 2ΔY

Case 2: If P_k ≥ 0

Choose NE (North-East)

• X_k+1 = X_k+1
• Y_k+1 = Y_k+1
• P_k+1 = P_k + 2ΔY − 2ΔX

Step 6: Repeat

Repeat until End point reached or Iterations = ΔX - 1.

Numerical Example

Problem 1

Calculate the points between the starting coordinates (9, 18) and ending coordinates (14, 22).

Solution:

Given,

• Starting coordinates = (X₀, Y₀) = (9, 18)
• Ending coordinates = (X_n, Y_n) = (14, 22)

Step 1:

Calculate ΔX and ΔY from the given input.

• ΔX = X_n – X₀ = 14 – 9 = 5
• ΔY =Y_n – Y₀ = 22 – 18 = 4

Step 2:

Calculate the decision parameter.

• P_k = 2ΔY – ΔX
• P_k = 2 x 4 – 5
• P_k = 3

So, decision parameter P_k = 3

Step 3:

As P_k >= 0, so Case: 2 is satisfied.

Thus,

• P_k+1 = P_k + 2ΔY – 2ΔX = 3 + (2 x 4) – (2 x 5) = 1
• X_k+1 = X_k + 1 = 9 + 1 = 10
• Y_k+1 = Y_k + 1 = 18 + 1 = 19

Similarly, Step: 3 is executed until the end point is reached or number of iterations equals to 4 times.

(Number of iterations = ΔX – 1 = 5 – 1 = 4) 

Table:

Final points: (9, 18), (10, 19), (11, 20), (12, 20), (13, 21), (14, 22)

Problem 2:

Calculate the points between the starting coordinates (20, 10) and ending coordinates (30, 18).

Solution:

Given,

• Starting coordinates = (X₀, Y₀) = (20, 10)
• Ending coordinates = (X_n, Y_n) = (30, 18)

Step 1:

Calculate ΔX and ΔY from the given input.

• ΔX = X_n – X₀ = 30 – 20 = 10
• ΔY =Y_n – Y₀ = 18 – 10 = 8

Step 2:

Calculate the decision parameter.

• P_k = 2ΔY – ΔX
• Pk = 2 x 8 – 10
• Pk = 6

So, decision parameter P_k = 6

Step 3:

As P_k >= 0, so case-02 is satisfied.

Thus,

• P_k+1 = P_k + 2ΔY – 2ΔX = 6 + (2 x 8) – (2 x 10) = 2
• X_k+1 = X_k + 1 = 20 + 1 = 21
• Y_k+1 = Y_k + 1 = 10 + 1 = 11

Similarly, Step 3 is executed until the end point is reached or number of iterations equals to 9 times.

(Number of iterations = ΔX – 1 = 10 – 1 = 9)

Table:

Problem 3:

To solve the line from (0,0) to (-8,-4) using Bresenham’s Line Drawing Algorithm, we first observe that both x and y are decreasing, so this is a negative direction line.

The slope is:

m = −4−0 / −8−0 = −4 / −8 = 0.5

Since: 0 ≤ m ≤ 1

we can use the standard Bresenham logic, but instead of increasing x and y, we will decrease them.

Step 1: Given Points

Starting Point: (x₁, y₁) = (0,0)

Ending Point: (x₂, y₂) = (−8,−4)

Step 2: Calculate Δx and Δy

Δx = |x₂ − x₁| = |−8 − 0| = 8

Δy = |y₂ − y₁| = |−4 − 0| = 4

Step 3: Initial Decision Parameter

P₀ = 2Δy − Δx = 2(4) − 8 = 2(4) - 8 = 8−8 = 0 

Step 4: Apply Bresenham Iterations

Since the line moves toward negative direction:

• x decreases by 1
• y decreases only when P_k ≥ 0

Iteration Table

Final Plotted Points: 

(0,0) (−1,−1) (−2,−1) (−3,−2) (−4,−2) (−5,−3) (−6,−3) (−7,−4) (−8,−4) 

Important Concept

The standard Bresenham algorithm normally assumes:

• x increases toward right

But here:

• x decreases toward left
• y decreases downward

So we simply:

• decrement x instead of incrementing
• decrement y when diagonal movement is needed

The decision parameter logic remains exactly the same.

Practice Problems

Try solving these:

1. Draw a line from (2, 3) to (9, 6) using Bresenham’s algorithm.
2. Consider the line from (5, 5) to (13, 9), use the Bresenham's algorithm to rasterize the line.
3. Draw a line from (4, 6) to (15, 10) using Bresenham’s algorithm.
4. Draw a line from (20, 10) to (30, 18).
5. Draw a line from (10, 6) to (3, 2).
6. Draw a line from (2, 2) to (6, 12).
7. Consider the line from (0, 0) to (-8, -4), use the Bresenham's algorithm to rasterize the line.

Advantages

• Uses integer arithmetic only
• Faster execution
• More accurate than DDA
• Incremental approach 

Disadvantages

• Only basic version handles 0 ≤ m ≤ 1
• Not smooth (aliasing problem)
• Needs modification for other slopes