Bresenham's Line Algorithm in Computer Graphics

Bresenham's Line Algorithm is an efficient method used to draw a straight line between two points in computer graphics.
The primary goal of this algorithm is to determine which points (or pixels) should be plotted to best approximate the straight line between two specified endpoints.
It is particularly useful because it relies entirely on integer arithmetic,
making it faster and simpler to implement on hardware where floating-point operations are slow or unavailable.

Key Concept Raster Graphics and Pixel Grids

In raster graphics, the screen is divided into a grid of tiny square units called pixels. When drawing lines, curves, or shapes, the computer decides which pixels should be lit to create the desired visual appearance.
However, since pixels are discrete units, drawing a straight line, which is continuous in nature, requires approximations.
Bresenham's Line Algorithm is designed to minimize the error in this approximation.

Problem Definition

Given two points x_0, y_0 and x_1, y_1 the task is to determine which pixels best approximate the straight line that connects these two points.
The challenge is particularly significant when the slope of the line is not exactly 0, 1, or infty, i.e., when the line isn't perfectly horizontal, vertical, or diagonal.

Principles of the Algorithm

Bresenham’s algorithm works by iteratively determining which pixel, from the two possible options at each step, is closer to the true mathematical line.
At each step, it must decide whether to move horizontally or diagonally to the next pixel based on the current error.
To understand this, consider that the line's equation in slope-intercept form is: y = mx + c
However, since the algorithm operates in pixel space (discrete steps), we approximate this continuous line using a decision variable to track the vertical error from the actual line.

Slope Considerations

Slope (m < 1\): The line is more horizontal than vertical, so the algorithm increments \(x\) at each step and decides whether to increment y.
Slope m > 1: The line is more vertical than horizontal, so the algorithm increments y at each step and decides whether to increment x

Step-by-Step Breakdown

1. Initialization
The algorithm starts at the first point \((x_0, y_0)\) and computes the differences in the x and y coordinates:

1Delta x = x_1 - x_0 \quad \text{and} \quad \Delta y = y_1 - y_0

This helps determine the line's slope.

2. Decision Parameter: A decision variable \(d\) is used to determine the pixel placement. Initially, it is set as: d = 2Delta y - Delta x

This variable helps decide whether to move the line vertically or diagonally.

3. Loop through each x-coordinate: For each step in the x-direction, the algorithm checks the decision variable d. If (d > 0), the next pixel will be above the current one, and \(d\) is updated as:

d = d + 2(\Delta y - \Delta x)

If \(d \leq 0\), the next pixel will be directly to the right, and \(d\) is updated as:

d = d + 2\Delta y

In either case, the algorithm increments \(x\) (and sometimes \(y\)) and repeats until \(x_1\) is reached.

Example of Bresenham’s Line Algorithm

Let's understand Bresenham's Line Algorithm with an example as follows:-

Example: Drawing a Line from (1, 1) to (6, 4)

1
2
3Initialization:
4
5x_0 = 1, y_0 = 1
6x_1 = 6, y_1 = 4
7
8dx = x_1 - x_0 = 5
9dy = y_1 - y_0 = 3
10
11y = y_0 = 1
12
13Decision Parameter:
14
15P_0 = 2 * dy - dx 
16
17= 2 * 3 - 5 = 1
18
19Drawing the Line:
20
21For x = 1:
22    Plot the pixel at (1, 1) because P is positive.
23    Update P = 1 + 2 * 3 = 7.
24
25For x = 2:
26    Do not plot a pixel because P is negative.
27    Update P = 7 - 10 = -3.
28
29For x = 3:
30    Plot the pixel at (3, 2) because P is positive.
31    Update P = -3 + 2 * 3 = 3.
32
33For x = 4:
34    Do not plot a pixel because P is negative.
35    Update P = 3 - 10 = -7.
36
37For x = 5:
38    Plot the pixel at (5, 3) because P is positive.
39    Update P = -7 + 2 * 3 = -1.
40
41
42For x = 6:
43    Plot the pixel at (6, 4) because P is positive.
44    Update P = -1 + 2 * 3 = 5.
45

Initialization

Given two points (x_0, y_0) and (x_1, y_1), initialize variables:
dx = x_1 - x_0
dy = y_1 - y_0
y = y_0 (initializing the starting point)

Decision Parameter

Calculate the decision parameter P_0 = 2 * dy - dx.
If P_0 is positive, the next pixel is above the line; otherwise, it is below.

Drawing the Line

For each x from x_0 to x_1:
Plot the pixel at (x, y)

If P is positive, increment y by 1 and update P

P = P + 2 * dy - 2 * dx * increment_y
where increment_y is 0 or 1 based on the decision parameter.

Otherwise, just update P:

P = P + 2 * dy
Resulting Plot: The plotted points are (x, y) forming a line segment.

Video explanation

Efficiency of the Algorithm

Bresenham's Line Algorithm is highly efficient because it only requires addition, subtraction, and bit-shifting operations, avoiding slow floating-point calculations.

This makes it ideal for real-time rendering applications, where speed is critical.

Conclusion

Bresenham's Line Algorithm is an elegant solution to the problem of drawing straight lines on a pixel grid.
It efficiently computes which pixels should be illuminated by considering only integer operations, making it suitable for real-time applications and systems with limited computational resources.

Table of contents