Bresenham Rasterizer Calculator

Pixels of a line or circle with every error term shown.

  • All octants
  • Error term per step
  • Line and circle
A round terracotta clay stool with a grid of small square holes in its top, and a ring of small rounded clay beads laid across the grid in soft daylight.

The guide

Why a straight line has no exact pixels, and how a running error term picks the nearest ones

A line almost never passes through pixel centres. Bresenham's method keeps one whole-number error and chooses a pixel at every step with additions only, and the choices at exact ties decide more than you would expect.

  • 12 pixels the line from (0, 0) to (11, 5), with no exact tie
  • 224 of 625 short lines that change pixels when drawn from the other end
  • 112 of 625 short lines where two common Bresenham forms differ
  • 239 of 399 radii where testing d <= 0 instead of d < 0 changes the circle
  • 0.4987 largest radius error of a circle pixel, radius up to 300
Read the full guide Fold the guide 8 min · 12 sources

Take a line from the pixel at column 0, row 0 to the pixel at column 11, row 5. It climbs five rows while crossing eleven columns. At column 1 the true line sits 5/11 of a row down, about 0.45. At column 2 it sits 10/11 down, about 0.91. No pixel centre is anywhere near those heights, so the screen has to pick. The answer for this line is 12 pixels: (0,0) (1,0) (2,1) (3,1) (4,2) (5,2) (6,3) (7,3) (8,4) (9,4) (10,5) (11,5). The rest of this essay is about how a few additions produce that list, why it is right, and where two correct versions of the method disagree.

A line the grid cannot hold

Wikipedia describes rasterisation as the task of taking an image described as shapes and turning it into a raster image. A line is the smallest such shape, and it already shows the difficulty. A raster has only whole-number positions, while a line between whole-number end points passes through almost none of them. The obvious repair is to step one column at a time and add the slope to a running row value. The article on the digital differential analyzer describes exactly that: x grows by one, y grows by the slope m, and y is rounded to the nearest whole number to find the pixel. Done in floating point it needs an addition and a rounding at every step.

Jack Elton Bresenham found a way to avoid both. According to Wikipedia he developed the line algorithm in 1962 at IBM, working on a plotter attached to an IBM 1401, and it was in production use that summer. A description was accepted for the 1963 national convention of the Association for Computing Machinery in Denver, and the IBM Systems Journal printed a paper in 1965.

The article calls the result an incremental error algorithm that needs only integer addition, subtraction and bit shifting. Those were the cheap operations on the machines of the day, which is why it ended up in plotters and graphics chips. It can also be read as a digital differential analyzer whose error threshold is 0.5 instead of 0.

Turning a division into additions

Think of one pixel row as one unit of height. Rounding the true row asks a question about a fraction, and the fraction hides a division by the width of the line. Multiply every length by twice the width and the fraction disappears: the question becomes whether a whole number is above or below another whole number.

The all-octant form that Wikipedia lists does this with one number. Let dx be the distance moved in x and dy the negative of the distance moved in y, and start the error at dx + dy. At each step the line plots a pixel and doubles the error to get e2. If e2 is at least dy, the error gains dy and x moves one pixel toward the end. If e2 is at most dx, the error gains dx and y moves one pixel toward the end. That is all of it.

Follow the line from (0,0) to (11,5). Here dx is 11, dy is -5 and the error starts at 6. Step 1 plots (0,0), and e2 is 12. Since 12 is at least -5 the error becomes 1 and x moves; since 12 is not at most 11, y stays. Step 2 plots (1,0), and e2 is 2. Both tests pass, so the error becomes 1 - 5 + 11 = 7, and both x and y move. The tool prints this table for every line, step by step.

Every pixel of that line lies within 5/11 of a row of the true line, about 0.4545. In general the largest distance along the short axis is never above one half. The tool checks that with exact fractions rather than decimals, and a separate Python script, using the standard fractions module for exact rational arithmetic, confirmed it for all 625 lines from the origin to every point with coordinates from -12 to 12.

The long axis matters. A routine that steps along x only will draw the steep line from (2,1) to (6,9) as five pixels, (2,1) (3,3) (4,5) (5,7) (6,9), with rows missing between them. The general form moves along whichever axis is longer and plots max(|dx|, |dy|) + 1 pixels, here nine: (2,1) (3,2) (3,3) (4,4) (4,5) (5,6) (5,7) (6,8) (6,9). Those nine pixels are 8-connected, which Wikipedia defines as touching along an edge or at a corner. The check that every step is such a neighbour is another thing the tool verifies for the 625 lines. A line with gaps would fail it at once.

One octant is enough for a circle

Wikipedia calls the midpoint circle algorithm a generalization of Bresenham’s line algorithm. It computes only the first octant, from the point (r, 0) counterclockwise to the 45 degree line, and then mirrors that arc seven times. In that octant y goes up by one at every step, and x sometimes goes down by one.

The decision looks at the midpoint between the two candidate pixels, at x minus one half and the next row. If the midpoint is inside the circle, x stays. If it is outside, x moves in by one. The article writes the radius error as P = (x - 1/2)^2 + (y + 1)^2 - r^2 and keeps x when P is below zero.

To get rid of the one half, the article starts from 1.25 - r and rounds to 1 - r. The tool calls the running value d and starts it at 1 - r. Each step adds 2y + 1 when x stays, or 2(y - x) + 1 after x moves in. Nothing but whole numbers appears. Radius 5 has 28 pixels, radius 10 has 56 and radius 100 has 564, because a pixel on an axis or on the 45 degree line appears in fewer mirror images than the rest and the tool counts each pixel once. For radii up to 300 no pixel centre is farther than 0.4987 from the true radius.

There is a stronger statement hiding here. For every radius from 1 to 399 the octant equals what you get by rounding x = sqrt(r^2 - y^2) to the nearest whole number on each row. The cheap incremental test and the expensive square root give the same picture. The independent check uses Python’s integer square root, which the documentation defines as the floor of the exact root, and whole-number comparisons.

Ties and the strict test

A tie happens when the true line passes exactly halfway between two pixels. The line from (0,0) to (8,3) does it at column 4, where the true row is 1.5. Rounding has several conventions for such halves, and Wikipedia lists round half up among them. Any rule is acceptable, but a rule must be chosen.

The all-octant form settles a tie toward the end the line is heading to. Draw the same line from the other end and the same tie is settled toward the other end. So the two drawings can differ, and 224 of 625 short lines from the origin do. Every differing pixel is a tie pixel. The tool counts the ties, names them in the table and lists the differing pixels in its compare card.

The octant-zero form in the same Wikipedia article keeps the row on a tie and swaps the end points so that the long axis always increases. It gives identical pixels from both ends for all 625 lines. It also differs from the all-octant form on 112 of 625, always at a tie. Both are Bresenham’s method. The label covers a family, and the tie rule is the part that varies.

The circle has a tie rule of its own, and it is not a matter of taste. The midpoint can never lie exactly on the circle, because (2x - 1)^2 + 4y^2 is odd and 4r^2 is even. With the one half removed, d equals P minus 1/4, so d = 0 means P = 1/4: the midpoint lies just outside, and x must move in. The test has to be d < 0, strictly.

Use d <= 0 instead and the picture changes for 239 of 399 radii, the radii from 1 to 399, beginning with 1, 4, 6, 9, 11 and 14. At radius 4 the midpoint at x = 3.5 and y = 2 is at 16.25 in squared distance, past 16, so the correct octant is (4,0) (4,1) (3,2) (3,3). The loose test draws (4,2) in place of (3,2), a pixel that is farther from the true radius.

The Python listing printed on the Wikipedia page when this tool was checked moves x only when p is above zero. Run for radii 1 to 399, it draws the same pictures as the loose test. The article’s prose says to keep x when P is below zero and to step when it is above, which agrees with the strict rule, and the difference comes only from dropping the 1/4. I do not know whether the listing was written that way on purpose.

What the method leaves out

Bresenham’s method draws jagged lines on purpose: each pixel is either on or off. Wikipedia’s article on Wu’s algorithm explains that Bresenham’s method does not antialias and cannot handle end points that fall between grid points, while Wu’s method draws pairs of pixels shaded by their distance from the line and is slower. This tool covers neither of those.

It also leaves out thick lines, ellipses, filled shapes and clipping. Coordinates stop at 100,000 either way and the radius at 50,000, so the largest line has 200,001 pixels and the largest circle 282,844. A table shows at most 2,000 steps; a longer run lists the first and last 100.

The large cases are exercised on purpose. The self-check recomputes every pixel of two lines at the coordinate caps with BigInt, which MDN describes as the type for whole numbers too large for the ordinary number type, and compares the result with the fast path. The heavy work runs in a Web Worker, a background thread, so the page stays responsive.

Try it. Load the line from (0,0) to (8,3) and switch on the other-end drawing to see the tie. Load the circle of radius 4 with the d <= 0 picture to see the pixel that should not be there. Then load radius 50,000 and check the grid window: you are looking at 120 columns of a circle with over two hundred and eighty thousand pixels.

Sources

Every source consulted for this guide. Links checked November 11, 2026.

  1. Bresenham's line algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  2. Midpoint circle algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  3. Jack Elton Bresenham - Wikipedia Wikipedia (CC BY-SA 4.0)
  4. Digital differential analyzer (graphics algorithm) - Wikipedia Wikipedia (CC BY-SA 4.0)
  5. Xiaolin Wu's line algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  6. Rasterisation - Wikipedia Wikipedia (CC BY-SA 4.0)
  7. Pixel connectivity - Wikipedia Wikipedia (CC BY-SA 4.0)
  8. Rounding - Wikipedia Wikipedia (CC BY-SA 4.0)
  9. BigInt - JavaScript | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  10. Web Workers API - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  11. math - Mathematical functions - Python 3.13 documentation Python Software Foundation (PSF License Version 2)
  12. fractions - Rational numbers - Python 3.13 documentation Python Software Foundation (PSF License Version 2)