Graphics: Low LevelSoftware RasterizerMedium

Bresenham's Line Drawing Algorithm

Master the fundamental concepts of software rasterizer through this focused micro-challenge.

~45 minutes Software Rasterizer Ready to learn

Topic Overview

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.

Implementation Task

Your Task

Implement Bresenham's line algorithm for all eight octants, using integer arithmetic only: no floats, no division, no slope. Rasterize lines onto an ASCII canvas and list the pixels each line covers, including lines that run off the canvas (those pixels are listed and counted, but not drawn).

Input

# starts a comment line.

c
Loading…

Algorithm

Use the single-error-term form, so every implementation produces the same pixels:

c
Loading…

Output

c
Loading…

Pixel lists show at most the first 12 pixels, followed by ... when there are more.
Counts: N pixel(s), plus , K outside the canvas when some fall off.
draw prints H rows, with # for drawn pixels and . for the rest.
Errors: canvas: W (1-64) H (1-32), line: X0 Y0 X1 Y1 (|v| <= 1000), unknown command X.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

Integer arithmetic only. The error term tracks exactly how far the ideal line is from the pixel grid.
A line with |dx| ≥ |dy| has exactly |dx| + 1 pixels, and otherwise |dy| + 1. No gaps, no double steps.

Hidden tests cover steep and shallow lines in every direction, vertical, horizontal and 45° lines, a single-point line, lines crossing the canvas edge, and a resized canvas.