Bresenham's Circle

Every screen you have ever looked at is a grid of square pixels. Drawing a straight line on that grid is already a small puzzle — Bresenham's line algorithm solved it in 1962 using only integer arithmetic. A circle is harder: its equation is $x^{2} + y^{2} = r^{2}$, and solving for $y$ at each $x$ involves a square root — an expensive floating-point operation that early hardware simply did not have.

In 1977, Jack Bresenham published a midpoint (or decision-variable) approach that removes the square root entirely. The key insight has two parts:

1. 8-way symmetry. A circle is symmetric about both axes and both diagonals, so computing one pixel in the first octant ($x \geq 0$, $y \geq x \geq 0$) immediately gives you seven more pixels for free.
2. Integer decision variable. Instead of computing $y = \sqrt{r^{2} - x^{2}}$ at each step, you maintain an integer $d$ that tells you whether the next pixel should step straight right or diagonally down-right. Updating $d$ costs only addition and subtraction — never a multiply or divide.

The result is one of the fastest circle-drawing routines ever devised, and it still powers the rasterizers embedded in GPUs and font renderers today.

Choose a radius and watch the midpoint algorithm place pixels one octant at a time, then mirror them across all eight symmetry axes simultaneously.

<div class="controls">
  <label for="radius-slider">{{lbl_radius}} <span id="radius-val">40</span></label>
  <input id="radius-slider" type="range" min="10" max="80" value="40" step="1">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-play" type="button">{{btn_play}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="360" height="280"></canvas>
<div id="status" class="status"></div>
<div id="dvar" class="dvar"></div>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem; margin-bottom: .5rem; }
label { font-size: .88rem; color: #444; white-space: nowrap; }
input[type=range] { flex: 1 1 120px; min-width: 80px; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; background: #f4f6f8; border-radius: 8px; border: 1px solid #dde3ea;
         max-width: 100%; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-top: .4rem; color: #1d3557; }
.dvar   { font-size: .82rem; color: #555; min-height: 1.2em; font-family: ui-monospace, monospace; }

// Code not found

Notice that the algorithm only ever computes pixels in the first octant (top-right arc, where $y \geq x \geq 0$). For each pixel $(x, y)$ it finds there, it immediately lights up the seven symmetric copies: $(\pm x, \pm y)$ and $(\pm y, \pm x)$. The decision variable $d$ starts at $1 - r$ and is updated with one addition per step — no square roots, no trigonometry, no floating point at all.

The core of the midpoint algorithm fits in a dozen lines. Here is the idea in pseudocode:

x = 0,  y = r,  d = 1 - r
while x <= y:
    plot(x, y)   // + 7 symmetric copies
    x += 1
    if d < 0:
        d += 2*x + 1          // move right only
    else:
        y -= 1
        d += 2*(x - y) + 1    // move right and down

Why does this work?

• Define the circle function $F(x, y) = x^{2} + y^{2} - r^{2}$. It is zero on the circle, negative inside, positive outside.
• $d$ is the value of $F$ at the midpoint between the two candidate pixels. If $d < 0$ the midpoint is inside the circle, so the higher pixel $(x+1, y)$ is closer; if $d \geq 0$ the lower pixel $(x+1, y-1)$ is closer.
• Moving from $(x, y)$ to $(x+1, y)$ changes $F$ by $2x + 3$ — a constant computable from $x$ alone.
• Moving from $(x, y)$ to $(x+1, y-1)$ changes $F$ by $2x - 2y + 5$ — computable from $x$ and $y$.

Both increments are integers, so $d$ stays an integer throughout. The algorithm runs in $O(r)$ time with no multiplication after initialization and no floating point at all.

Comparison to the naive approach. Computing $y = \sqrt{r^{2} - x^{2}}$ for each $x$ from $0$ to $r$ also visits $O(r)$ pixels, but requires $O(r)$ square-root evaluations. Even if we use a cheaper approximation, rounding errors accumulate and gaps or overlaps appear in the circle. The midpoint method is exact by construction.

The midpoint circle algorithm was designed for hardware with no floating-point unit. That constraint turned out to be a permanent advantage:

• Early framebuffers and retro games. 8-bit and 16-bit microprocessors had no FPU and integer multiply was slow. Bresenham's method drew circles in tight inner loops without touching the math coprocessor.
• Font rendering and hinting. TrueType and PostScript outlines are curves, but the final step that fills pixels uses scan-line rasterizers built on the same integer-increment idea. Crisp circle-shaped glyphs (like the letter "O") depend on it.
• GPU hardware rasterizers. Modern rasterizers work in fixed-point integer arithmetic for determinism across hardware. The midpoint principle — compare a mid-sample to a boundary, branch, update — maps directly onto triangle rasterization and anti-aliasing coverage masks.
• Embedded and microcontroller displays. IoT devices and small LCD drivers still use integer-only circle drawing because it requires no libm and fits in a few dozen bytes of code.
• Medical and scientific imaging. Circular region-of-interest (ROI) selection in MRI software and astronomical image analysis tools rasterize circles the same way.

The deeper lesson is algorithmic: whenever a continuous equation has a neat incremental update structure, replacing it with an integer decision variable turns a costly function evaluation into a cheap addition. The same idea underlies Bresenham's line algorithm and many scan-line fill routines.

Bresenham's midpoint circle algorithm is a small masterpiece of applied mathematics. It takes the equation $x^{2} + y^{2} = r^{2}$, which naively demands a square root at every pixel, and replaces the whole computation with a single integer $d$ that is updated by one addition per step.

Two ideas make it work. Eight-fold symmetry means only one-eighth of the circle needs to be computed — the other seven arcs come for free. The midpoint decision variable turns the question "which pixel is closer to the true circle?" into a sign test on an integer that is kept perfectly in sync by cheap increments.

The algorithm has been running on hardware for nearly fifty years. The next time you see a circular button, a pie chart, or the letter "O" rendered on screen, there is a good chance that somewhere down the rendering stack, a decision variable is ticking from one integer to the next — no square roots required. For more integer-arithmetic algorithms in the same spirit, see Bresenham's line algorithm.