Bresenham Line Drawing Algorithm

The Bresenham line drawing algorithm is a computer graphics algorithm used to draw a straight line between two points in a rectangular grid. It is named after its inventor, Jack Bresenham.

The algorithm works by calculating the coordinates of the pixels that should be colored to approximate the line. It uses integer arithmetic and avoids using floating-point operations, making it more efficient than other line-drawing algorithms.

The basic idea behind the algorithm is to incrementally move from the start point to the endpoint, plotting pixels along the way. At each step, the algorithm decides whether to increment the x-coordinate or the y-coordinate of the current pixel, based on which decision results in a closer approximation of the line. This is done by comparing the distances between the ideal line and the two possible next pixels and selecting the one that is closer to the ideal line.

The Bresenham algorithm can also be extended to draw lines with different line styles, such as dashed or dotted lines. It is widely used in computer graphics applications, such as CAD software and video games.

Rules of Bresenham Line Drawing Algorithm

ΔX = Xn – X0
ΔY =Yn – Y0
Pk = 2ΔY – ΔX

Repeat until reach to the endpoint
if Pk < 0 then
Pk+1 = Pk+2ΔY
Xk+1 = Xk+1
Yk+1 = Yk

if Pk >= 0 then
Pk+1 = Pk+2ΔY-2ΔX
Xk+1 = Xk+1
Yk+1 = Yk+1

Example

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

Step 1

ΔX = X_n – X₀ = 14-9 = 5

ΔY = Y_n – Y₀ = 22-18 = 4

P_k = 2ΔY – ΔX = 2*4 – 5 = 3

Step 2

comparing Pk with 0 then Pk >= 0

P_k+1 = P_k+2ΔY-2ΔX = 3+2*4-2*5 = 3+8-10 = 1

X_k+1 = X_k+1 = 9+1 = 10

Yk+1 = Yk+1 = 18+1 = 19

Step 3

comparing Pk with 0 then Pk >=0

P_k+1 = P_k+2ΔY-2ΔX = 1+2*4-2*5 = 1+8-10 = -1

X_k+1 = X_k+1 = 10+1 = 11

Yk+1 = Yk+1 = 19+1 = 20

Step 4

comparing Pk with 0 then Pk <0

P_k+1 = P_k+2ΔY = -1+2*4 = 7

X_k+1 = X_k+1 = 11+1 = 12

Y_k+1 = Y_k = 20

Step 5

comparing Pk with 0 then Pk >= 0

P_k+1 = P_k+2ΔY – 2ΔX = 7 + 2* 4 – 2*5 = 7+8-10 = 5

X_k+1 = X_k+1 = 12+1 = 13

Y_k+1 = Y_k+1 = 20+1 = 21

Step 6

Comparing Pk with 0 then Pk >= 0

P_k+1 = P_k+2ΔY – 2ΔX = 5+2*4-2*5 = 5+8-10 = 3

X_k+1 = X_k+1 = 13+1 = 14

Y_k+1 = Y_k+1 = 21+1 = 22

Pk	Pk+1	Xk+1	Yk+1
		9	18
3	1	10	19
1	-1	11	20
-1	7	12	20
7	5	13	21
5	3	14	22

Advantages of the Bresenham line drawing algorithm:

1. Efficiency: The Bresenham algorithm is more efficient than other algorithms for line drawing because it uses integer arithmetic and avoids using expensive floating-point operations.
2. Accuracy: The algorithm produces accurate and precise results, especially for lines with small slopes, as it calculates the coordinates of the pixels that should be colored to approximate the line.
3. Flexibility: The algorithm can be easily adapted to draw lines with different styles, such as dashed or dotted lines, by modifying the decision-making process for selecting the next pixel to plot.
4. Easy to implement: The Bresenham algorithm is relatively easy to implement and does not require a large amount of memory or processing power.

Disadvantages of the Bresenham line drawing algorithm:

1. Limited to straight lines: The algorithm can only draw straight lines, and cannot be used to draw curved or irregular shapes.
2. Limited to a rectangular grid: The algorithm is designed to work on a rectangular grid, so it may not be suitable for applications that require drawing lines on non-rectangular grids.
3. Limited to 2D: The algorithm is limited to two-dimensional (2D) graphics and cannot be used for three-dimensional (3D) graphics or more complex visualizations.
4. Aliasing: The algorithm can produce jagged or stair-stepped lines, especially for lines with large slopes, which can be visually unappealing. However, this can be mitigated by using anti-aliasing techniques.