Variant with integer-based arithmetic

Just as with Bresenham's line algorithm, this algorithm can be optimized for integer-based math. Because of symmetry, if an algorithm can be found that only computes the pixels for one octant, the pixels can be reflected to get the whole circle.

We start by defining the radius error as the difference between the exact representation of the circle and the center point of each pixel (or any other arbitrary mathematical point on the pixel, so long as it's consistent across all pixels). For any pixel with a center at ${\displaystyle (x_{i},y_{i})}$, the radius error is defined as:

${\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+y_{i}^{2}-r^{2}\right\vert }$

For clarity, this formula for a circle is derived at the origin, but the algorithm can be modified for any location. It is useful to start with the point ${\displaystyle (r,0)}$ on the positive X-axis. Because the radius will be a whole number of pixels, clearly the radius error will be zero:

${\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+0^{2}-r^{2}\right\vert =0}$

Because it starts in the first counter-clockwise positive octant, it will step in the direction with the greatest travel, the Y direction, so it is clear that ${\displaystyle y_{i+1}=y_{i}+1}$. Also, because it concerns this octant only, the X values have only 2 options: to stay the same as the prior iteration, or decrease by 1. A decision variable can be created that determines if the following is true:

${\displaystyle RE(x_{i}-1,y_{i}+1)<RE(x_{i},y_{i}+1)}$

If this inequality holds, then plot ${\displaystyle (x_{i}-1,y_{i}+1)}$; if not, then plot ${\displaystyle (x_{i},y_{i}+1)}$. So, how to determine if this inequality holds? Start with a definition of radius error:

${\displaystyle {\begin{aligned}RE(x_{i}-1,y_{i}+1)&<RE(x_{i},y_{i}+1)\\\left\vert (x_{i}-1)^{2}+(y_{i}+1)^{2}-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}+1)^{2}-r^{2}\right\vert \\\left\vert (x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert \\\end{aligned}}}$

The absolute value function does not help, so square both sides, since a square is always positive:

${\displaystyle {\begin{aligned}\left[(x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}&<\left[x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}\\\left[(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})\right]^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\\left(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right)^{2}+2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<0\\\end{aligned}}}$

Since x > 0, the term ${\displaystyle (1-2x_{i})<0}$, so dividing gets:

${\displaystyle {\begin{aligned}2\left[(x_{i}^{2}+y_{i}^{2}-r^{2})+(2y_{i}+1)\right]+(1-2x_{i})&>0\\2\left[RE(x_{i},y_{i})+Y_{\text{Change}}\right]+X_{\text{Change}}&>0\\\end{aligned}}}$

Thus, the decision criterion changes from using floating-point operations to simple integer addition, subtraction, and bit shifting (for the multiply by 2 operations). If ${\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}>0}$, then decrement the x value. If ${\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0}$, then keep the same x value. Again, by reflecting these points in all the octants, a full circle results.

We may reduce computation by only calculating the delta between the values of this decision formula from its value at the previous step. We start by assigning ${\displaystyle E}$ as ${\displaystyle 3-2r}$ which is the initial value of the formula at ${\displaystyle (x_{0},y_{0})=(r,0)}$, then as above at each step if ${\displaystyle E>0}$ we update it as ${\displaystyle E=E+2(5-2x+2y)}$ (and decrement X), otherwise ${\displaystyle E=E+2(3+2y)}$ thence increment Y as usual.

Jesko's Method

The algorithm has already been explained to a large extent, but there are further optimizations.

The new presented method^[4] gets along with only 5 arithmetic operations per step (for 8 pixels) and is thus just for low-performate systems best suitable. In the "if" operation, only the sign is checked (positive? Yes or No) and there is a variable assignment, which is also not considered an arithmetic operation. The initialization in the first line (shifting by 4 bits to the right) is only due to beauty and not really necessary.

So we get countable operations within main-loop:

1. The comparison x >= y (is counted as a substraction: x - y >= 0 )
2. y=y+1 [y++]
3. t1 + y
4. t1 - x
   1. The comparison t2 >= 0 is NOT counted as no real arithmetic takes place. In Two's-complement representation of the vars only the sign bit has to be checked.
5. x=x-1 [x--]

Operations: 5

t1 = r / 16
x = r
y = 0
Repeat Until x < y
    Pixel (x, y) and all symmetric pixels are colored (8 times)
    y = y + 1
    t1 = t1 + y
    t2 = t1 - x
    If t2 >= 0
        t1 = t2
        x = x - 1