Bresenham's Line Drawing Algorithm

The Problem: Which Pixels Form a Line?

In 1962, Jack Bresenham developed an algorithm to draw straight lines on a pixel grid. Given endpoints (x0, y0) and (x1, y1), which pixels best approximate the ideal line?

The naive approach uses y = mx + b, computing and rounding y for each integer x. That requires floating-point multiply and divide on every pixel.

Integer Error Tracking

Bresenham's insight: track an integer error term instead of computing y directly. For slopes between 0 and 1:

c
Loading…

For example, drawing from (0,0) to (7,3) uses only integer addition and subtraction. Other octants swap x/y or reverse step direction, but the error-term logic stays the same.

No floating point: works on MCUs without an FPU
Per-pixel decision: choose the pixel closest to the ideal line
Ancestor of scanline fill: edge walking in triangle rasterization builds on this

For This Exercise

You will implement Bresenham's algorithm for a line with slope between 0 and 1, printing each plotted pixel coordinate. This task asks you to output the full pixel list for endpoints read from stdin. The integer-only path you write here is still used inside Cairo, Skia's software backend, and embedded displays.

The Problem: Which Pixels Form a Line?

In 1962, Jack Bresenham developed an algorithm to draw straight lines on a pixel grid. Given endpoints (x0, y0) and (x1, y1), which pixels best approximate the ideal line?

The naive approach uses y = mx + b, computing and rounding y for each integer x. That requires floating-point multiply and divide on every pixel.

Integer Error Tracking

Bresenham's insight: track an integer error term instead of computing y directly. For slopes between 0 and 1:

Loading…

For example, drawing from (0,0) to (7,3) uses only integer addition and subtraction. Other octants swap x/y or reverse step direction, but the error-term logic stays the same.

No floating point: works on MCUs without an FPU

Per-pixel decision: choose the pixel closest to the ideal line

Ancestor of scanline fill: edge walking in triangle rasterization builds on this

For This Exercise

Write a C program that implements Bresenham's line algorithm for the first octant (0 <= slope <= 1).

Requirements:

Implement the algorithm for a line from (x0, y0) to (x1, y1) where x1 > x0 and y1 >= y0 and (y1-y0) <= (x1-x0)
Use only integer arithmetic: no floats, no division in the loop
Plot each pixel coordinate on stdout in the format "(x, y)"
Calculate and print the total number of pixels drawn
Verify that the number of pixels equals (x1 - x0 + 1)
Test with the line from (2, 3) to (12, 7)
Also test with a horizontal line (5, 5) to (15, 5) and a 45-degree line (0, 0) to (8, 8)
Print the decision variable (error term) at each step to show how it evolves
Include a brief explanation of why floating-point is avoided

Topic Overview

The Problem: Which Pixels Form a Line?

Integer Error Tracking

For This Exercise

Implementation Task

Progressive Hints

Resources

Open Source

Bresenham's Line Drawing Algorithm

Topic Overview

The Problem: Which Pixels Form a Line?

Integer Error Tracking

For This Exercise

Implementation Task

Progressive Hints

Resources

Open Source