Bresenham's Line Algorithm

Mental Model

A computer screen is a grid of discrete square pixels, but a mathematical line is continuous. When you ask a graphics system to draw a line from point A to point B, it cannot light up the infinite points along that line — it has to choose a finite set of pixels that best approximate the ideal path. That choice is called rasterization, and getting it wrong produces lines that look jagged, stair-stepped, or wandering.

Bresenham’s Line Algorithm is the classic solution, and the trick that makes it fast is integer-only math. Starting at one endpoint, it steps along the dominant axis (whichever of X or Y has the larger distance to travel) one pixel at a time. At each step, an integer decision variable $D$ tracks the cumulative drift between the ideal line and the pixel path chosen so far. When $D$ stays negative, the line is close enough to the dominant axis that only the dominant coordinate advances; when $D$ reaches zero or above, the algorithm takes a diagonal step on both axes to correct the drift. Because every update is an addition, a subtraction, or a multiply-by-two (a cheap bit shift), the algorithm runs without any floating-point arithmetic or division — which is why it became the standard rasterizer in early graphics hardware and is still taught as a foundational computer-graphics skill.

Components and Why They Exist

Pixel Grid

The grid is the screen itself — a 16×16 array of cells where the algorithm will light up pixels. The demo overlays the ideal mathematical line as a dashed reference on top of the discrete cells, then fills in the chosen pixels as colored blocks as the algorithm evaluates each step. Watching the gap between the dashed line and the colored blocks is the fastest way to see what “best approximation” means: the algorithm is always picking the pixel whose center is closest to the true line at that step.

Endpoints (Start and End Points)

The two endpoints define the line segment and everything the algorithm needs to derive: the absolute distances $\Delta x$ and $\Delta y$, the step directions $s_x$ and $s_y$ (each $+1$ or $-1$), and which axis is dominant. Drag the green start handle or the red end handle in the demo to change the line and watch the algorithm recompute — a shallow line keeps X as the dominant axis, a steep line swaps to Y, and a line going left or down simply flips the step signs without needing a different algorithm.

Decision Variable D

$D$ is the heart of the algorithm. It is a scaled error accumulator — not the slope itself — that records how far the pixel path has drifted from the ideal line. Its sign alone makes the decision: if $D < 0$, the drift is small enough that the next pixel advances only on the dominant axis; if $D \ge 0$, the drift has crossed the midpoint and the next pixel must take a diagonal step on both axes to correct it. Watch the value of $D$ in the inspector at each step and you will see it climb, trigger a diagonal step, drop back, and climb again — that oscillation is the algorithm tracking the line.

Pseudocode and Execution Log

The pseudocode panel highlights the exact line the algorithm is executing at each step, and the execution log records the coordinates, the $D$ value, and the decision that was made. Following the highlighted line and matching it to the pixel just plotted on the grid is what turns the formula into a skill: you see the cause (the $D$ update rule), the decision (step vs. diagonal step), and the effect (which pixel lit up) all in one glance.

Edge Cases and Misconceptions

• Steep Lines ($dy > dx$): A common misconception is that the algorithm only works for shallow lines. For steep lines, Y becomes the dominant axis. The algorithm operates identically, but Y increments every step while X is updated conditionally based on $D$.
• Negative Slopes and Directions: Lines moving left ($dx < 0$) or downward ($dy < 0$) do not require special algorithms. Bresenham’s handles them by computing direction sign offsets ($s_x = -1$ or $s_y = -1$) and using the absolute values of $\Delta x$ and $\Delta y$ for error calculations.
• D is Not the Slope: The decision variable $D$ is not the slope ($m$) itself. It is a scaled error accumulator. The slope is constant, but $D$ is updated incrementally at each step to reflect the drift.
• Integer-Only is Exact, Not Approximate: The grid display is an approximation because of pixel layout, but the math used by Bresenham’s algorithm to choose the closest pixel is mathematically exact. It does not introduce rounding errors.