The Bresenham Line Algorithm

A straight line on paper is trivial — on a pixel grid it is not. Pixels sit on integer coordinates, but a line from (0, 0) to (5, 3) has a slope of 0.6, and no pixel lies exactly on that path except the endpoints. Something has to decide, for every column, which row comes closest.

The naive approach evaluates y = mx + b for every x using floating-point math. It works, but floating-point multiplication and rounding are slower than they need to be for an operation that may run millions of times per frame. Bresenham's algorithm, published by Jack Bresenham at IBM in 1965, gets the identical result using only integer addition, subtraction, and bit shifts — no multiplication, no division, no rounding.

The idea

Consider a line with a slope between 0 and 1, going from (x0, y0) to (x1, y1). Since the slope is shallow, the line advances by exactly one pixel in x for every step, and y either stays the same or increases by one. The algorithm never needs to know the real-valued y — it only needs to decide, at each step, whether to increase y or not.

That decision is made with an error term: a running tally of how far the ideal (real-valued) line has drifted from the current pixel row. Each step adds the slope to the error. When the error exceeds half a pixel, the algorithm moves to the next row and subtracts one full pixel's worth back out. Everything here can be expressed with integers by scaling the error term by 2 * dx, which is where the characteristic 2*dy and 2*dy - 2*dx constants in the implementation come from.

Implementation

The version below handles all slopes and directions by normalizing the octant first: it swaps x/y for steep lines and swaps the endpoints for lines going right-to-left, then always steps in the same simple pattern.

#include "plot.hpp"
#include <stdlib.h>

void bresenham_line(int x0, int y0, int x1, int y1) {
    int steep = abs(y1 - y0) > abs(x1 - x0);

    if (steep) {
        int tmp = x0; x0 = y0; y0 = tmp;
        tmp = x1; x1 = y1; y1 = tmp;
    }
    if (x0 > x1) {
        int tmp = x0; x0 = x1; x1 = tmp;
        tmp = y0; y0 = y1; y1 = tmp;
    }

    int dx = x1 - x0;
    int dy = abs(y1 - y0);
    int error = dx / 2;
    int ystep = (y0 < y1) ? 1 : -1;
    int y = y0;

    for (int x = x0; x <= x1; x++) {
        if (steep) {
            PlotPixel(y, x);
        } else {
            PlotPixel(x, y);
        }
        error -= dy;
        if (error < 0) {
            y += ystep;
            error += dx;
        }
    }
}

void frame() {
    PlotBackground(250, 250, 250);
    PlotColor(30, 100, 200);
    bresenham_line(50, 400, 600, 80);
}

frame() just calls the algorithm with PlotPixel as the drawing primitive instead of printf. Press the button above to compile this exact code and try different endpoints yourself.

error here is the classic Bresenham error term scaled down by a factor of two compared to some textbook versions (dx/2 instead of 2*dy - dx) — both are equivalent, this form just avoids one multiplication at the start.

Walking through an example

For the line from (0, 0) to (5, 3): dx = 5, dy = 3, ystep = 1, error starts at 2.

The resulting pixels are (0,0) (1,1) (2,1) (3,2) (4,2) (5,3) — a reasonable staircase approximation of the ideal line, never off by more than half a pixel from the true path.

Why it still matters

Modern GPUs rasterize triangles, not individual lines, and use their own fixed-point rasterization rules. But Bresenham's algorithm — and its extensions for circles and general conics — still shows up wherever lines need to be drawn without a GPU: terminal UIs, embedded displays, plotting libraries, retro-style games, and any software rasterizer written for learning or for constrained hardware. It is also a good example of a recurring trick in low-level graphics code: replacing a real-valued computation with an equivalent integer one by tracking accumulated error instead of the value itself.

Conclusion

Bresenham's algorithm turns "which pixel is closest to this line" into a running integer comparison, updated once per step with only an addition and an occasional subtraction. It is a small piece of code, but a good illustration of how much can be gained by picking the right representation for a problem before writing the loop.