Will Perone

Building a Better Circle Algorithm Than Bresenham

Here is the Bresenham Circle Algorithm, generally accepted as the most optimized circle algorithm.
void CircleBresenham(int xc, int yc, int r, int color)
{
    int x = 0; 
    int y = r; 
    int p = 3 - 2 * r;
    if (!r) return;     
    while (y >= x) // only formulate 1/8 of circle
    {
        drawpixel(xc-x, yc-y, color);//upper left left
        drawpixel(xc-y, yc-x, color);//upper upper left
        drawpixel(xc+y, yc-x, color);//upper upper right
        drawpixel(xc+x, yc-y, color);//upper right right
        drawpixel(xc-x, yc+y, color);//lower left left
        drawpixel(xc-y, yc+x, color);//lower lower left
        drawpixel(xc+y, yc+x, color);//lower lower right
        drawpixel(xc+x, yc+y, color);//lower right right
        if (p < 0) p += 4*x++ + 6; 
              else p += 4*(x++ - y--) + 10; 
     } 
}

Another algorithm is called the midpoint algorithm. This algorithm can't explicitly draw the 4 cardinal points so we draw them before the algorithm then take the 1st and 2nd derivative to incrementalize.
void CircleMidpoint(int xc, int yc, int r, int color)
{
    int   x= 0, y= r;
    int   d= 1-r;
    int   dE= 3;
    int   dSE= 5 - 2*r;

    if (!r) return;
    drawpixel(xc-r, yc, color);
    drawpixel(xc+r, yc, color);
    drawpixel(xc, yc-r, color);
    drawpixel(xc, yc+r, color);
      
    while (y > x)    //only formulate 1/8 of circle
    {
        if (d < 0) 
        {
            d+= dE;
            dE+=2, dSE+=2;
        } else {
            d+=dSE;
            dE+=2, dSE+=4;
            y--;
        }
        x++;
 
        drawpixel(xc-x, yc-y, color);//upper left left
        drawpixel(xc-y, yc-x, color);//upper upper left
        drawpixel(xc+y, yc-x, color);//upper upper right
        drawpixel(xc+x, yc-y, color);//upper right right
        drawpixel(xc-x, yc+y, color);//lower left left
        drawpixel(xc-y, yc+x, color);//lower lower left
        drawpixel(xc+y, yc+x, color);//lower lower right
        drawpixel(xc+x, yc+y, color);//lower right right
     }
}

At first glance, it looks like we've taken a step back because midpoint circle is actually more code than bresenham but if we inverse the logic for the midpoint algorithm to do spans instead of a check every iteration (just like we did for The Bresenham Line then we can get something much more optimized than either midpoint or bresenham.
// this code was originally written in 2000
void CircleOptimized(int xc, int yc, int r, int color)
{
    unsigned int x= r, y= 0;//local coords     
    int          cd2= 0;    //current distance squared - radius squared

    if (!r) return; 
    drawpixel(xc-r, yc, color);
    drawpixel(xc+r, yc, color);
    drawpixel(xc, yc-r, color);
    drawpixel(xc, yc+r, color);
 
    while (x > y)    //only formulate 1/8 of circle
    {
        cd2-= (--x) - (++y);
        if (cd2 < 0) cd2+=x++;

        drawpixel(xc-x, yc-y, color);//upper left left
        drawpixel(xc-y, yc-x, color);//upper upper left
        drawpixel(xc+y, yc-x, color);//upper upper right
        drawpixel(xc+x, yc-y, color);//upper right right
        drawpixel(xc-x, yc+y, color);//lower left left
        drawpixel(xc-y, yc+x, color);//lower lower left
        drawpixel(xc+y, yc+x, color);//lower lower right
        drawpixel(xc+x, yc+y, color);//lower right right
     } 
}
41 Comments
harry23 78 39
In CircleBresenham program, why do you assign p = 3 - 2*r; ?
Asger Joergensen 137 27
Yes Your code is fast, but it also have less quality!!
coyote 137 58
Midpoint is actually slightly faster like this:
...
diff_dSE_dE = dSE - dE ;
...
if( d < 0 ) {
d += dE ;
dE += 2 ;
x++ ;
} else {
d += dE + diff_dSE_dE ;
dE += 2 ;
diff_dSE_dE += 2 ;
y-- ;
x++ ;
}

I intentionally wrote all instructions within the "if" statement just to make clear that for moving right (E) it now takes 3 add instructions and moving right and down (SE) now takes 6 add instructions.

However, since for the second octant there are more E passes than SE passes then it is a bit more efficient then the regular midpoint algorithm which uses 4 add instructions for E pass and 5 add instructions for SE pass.
Will 34 29
Thanks for the tip coyote!
Tony Barrera 2010/12/03 Contact Me7 18
WE have just succeded with a four connected circle algorithm with 2 increments per pixel. It is not published yet but we are working on it.
Will 2010/12/03 Contact Me8 16
Cool, let me know when you publish it and I'll put it up here if you want.
2011/01/21 Contact Me2 1
We have a four connected circle algorithm with work 2 add/sub per8:th pixel and a Eight connected circle algorithm with 3 add/sub per 8:th pixel. we are working ob the publishing at the moment. It could be fun to put the algorithms her when we are ready.
Will 2011/01/21 Contact Me4 11
Sure that would be great :)
Tony Barrera 2011/05/13 Contact Me3 14
The new circle algorithms will be presented at Centre of image analysis Uppsala University 2011 Friday 13:th may 14.15 Sweden.
Will 2011/05/132 11
Will there be a whitepaper available from the presentation?
Tony Barrera 2011/05/20 Contact Me12 1
Will 2011/05/2021 10
A whitepaper is a research article that is published on the findings (helpful for people who can't attend the presentation in person)
Tony Barrera 2011/05/30133 3
we have a paper wich we are working on for publication.
Will 2011/05/313 133
Awesome, let me know when it's published!
Mickey 2011/07/08 Contact Me3 133
You cludonÂ’t pay me to ignore these posts!
tony barrera 2011/07/09 Contact Me0 0
Willperone your ideas of swapping coordinates is very good i also
hve beeing similar things for some algorithms. Could you explaine more of what you are doing.
Regina 2011/07/09 Contact Me1 0
Now I'm like, well duh! Truly thafknul for your help.
Josef 2012/07/15 Contact Me3 2
Hi,
what would be the best way of making the circle thicker than one pixel? I have tried to draw multiple circles each one pixel smaller, that was a fail has heaps of holes in it.
Will 2012/07/157 16291
Off the top of my head, the best approach might be to draw 2 circles then floodfill between them...
Aziz 2012/09/11 Contact Me6 104
There was an issue on rhel4 where if a tracing psceors didn't call ptrace detach that the thread group leader would stay in traced state. If someone sent it a SIGCONT the thread group leader would continue and all the child threads would go into a traced state (T in ps). A second SIGCONT would bring it back to normal. Between the two signals a ps ax would show only the thread group leader status. Be sure to check the threads in ps to make sure none of them are in a traced state.
bob 2012/09/21 Contact Me2 2
@Josef: There are many optimizations that can be applied, but you can start with
a rectangular area and run through the all x,y coordinates and check whether the point lies outside the larger ellipse and within the smaller ellipse and if so the point is not part of the ring.
bob 2012/09/21 Contact Me0 0
@ author of OptimizedCircle algorithm.
The OptimizedCircle algorithm appears to be more optimized than the MidPointCircle algorithm. However it is not true in terms of memory access. Of course you may argue that all variables can be put on the registers, but in terms of pipelining, the intructions within the innerloop of MidPointCircle algorithm can be paired and executed in parallel which makes it faster than your so called OptimizedCircle.
bob 2012/09/21 Contact Me3403 7086
In general, all Nth degree polynomials take N calculations(or cycles) to plot each iteration when executed in serial. However, in parallel, it can be reduced to just two cycles for any degree polynomial given that there are enough execution pipes to handle independent instructions.

To make independent the calculations of the derivatives, instead of:
eg. polynomial a = x^4.
x = x^4
dx = 4x^3
ddx = 12x^2
dddx = 24x
ddddx = 24
for( a = x downto 0)
{ x = x - dx
dx = dx - ddx
ddx = ddx - dddx
dddx = dddx - ddddx
}


Do as follows for parallelism:
eg. polynomial a = x^4.
x = x^4
dx = 4x^3
ddx = 12x^2
dddx = 24x
ddddx = 24
for( a = x downto 0)
{ x = x - dx
ddx = ddx - dddx

dx = dx - ddx
dddx = dddx - ddddx
}
// by reordering the instructions which update the derivatives by calculating all odd degree deltas first then the even degree deltas second, then the chain of data dependancy is reduced to just one node of dependancy therefore it is possible to execute in just two cycles in parallel.

This of course will require initialization of the deltas differently. I leave this to the thinkers to try and work it out.
If interested contact me.

Finally, a circle formula has two parametric parameters of 2nd degree polynomial. Namely, x^2 and y^2. It then should theoretically and practically take 4 instruction cycles per iteration for a circle algorithm to run through the coordinates. CPUs/ALUs which fetch ahead and write back there is no time dependency and can reduce further down to just one cycle per parameter. In conclusion the circle algorithm needs only two instruction cycles per iteration.
richa 2013/01/27 Contact Me3 1
i want bresenhame circle algorithm for two circles and perform dry run on five points also see on which point is not working
soumya 2013/11/138 3
bresenham has less time complexity.....why?
Tony Barrera 2015/06/150 0
Our SuperCircle algorithm requiring 2.5 add/sub per 8 pixel (no multiplication at all!) Is now beeing published in Journal of Computer Mathematics! The fastest circle algorithm in the world!!!
Anon 2015/06/290 0
Hi Tony Barrera,

Where can we find it?

Thanks!
2015/10/180 0
http://www.researchgate.net/publication/277975077_A_Chronological_and_Mathematical_Overview_of_Digital_Circle_Generation_Algorithms_-_Introducing_Efficient_4_and_8-Connected_Circles

Hi! Yes the super-circle algorithm has now been published! - Tony Barrera.
2015/10/190 0
Tony.barrera@galaxyhit.com
Tony Barrera 2015/11/15 Contact Me0 0
Tony Barrera here!
See:
https://plus.google.com/u/0/100507551400981078302

Barrera Science Lab
Tony Barrera 2015/11/17 Contact Me0 0
Ok! Boys/girls here is the Super-Circle algorithms (T.Barrera et al..)!

//////////// Supercircle 8-connected //////////
R:=101;
x:=0;
y:=R;
d:=(-R) div 2;

while x<=y do
begin
plot8(x,y,255,255,55);
if d<=0 then
begin
x:=x+1;
d:=d+x;
end
else
begin
x:=x+1;
y:=y-1;
d:=d+x-y;
end;
end;

///////////////// Supercircle 4-connected /////////
R:=101;
x:=0;
y:=R;
d:=(-R) div 2;

while x<=y do
begin
plot8(x,y,255,55,55);
if d<=0 then
begin
x:=x+1;
d:=d+x;
end
else
begin
y:=y-1;
d:=d-y;
end;
end;
Tony Barrera 2015/11/17 Contact Me0 0
Pure mathematics!
Will 2016/01/01 Contact Me0 0
Congrats on the publication. For the 8-connected, it looks like it could be optimized like so:

for (x= 1, y= r, d= -r/2; x<=y; x++) {
drawpixel(x,y);
d+=x;
if (d > 0) y--, d-=y;
}

you could then further optimize it by writing the horizontal span of pixels of length predicted by calculating when y will decrement.
2016/01/020 0
Yes further optimizations might go but the mathematics of reducing the number of multiplications remains. Great Will! T. Barrera.
2016/01/060 0
Hey, Will your optimization does'nt seem to do a correct circular trace. So while you are working on that we will present an completely mathemaically optimized (Small) circle, the Ultra Circle:

begin{verbatim}
x:=0;y:=r;d:=1;
while x<y do
begin
if d>=0 then begin d:=d-y;y:=y-1;end;
Plot8(x,y);
d:=d+x;
x:=x+1;
end;
end{verbatim}
Tony Barrera 2016/01/060 0
Ultra Circle!
Tony Barrera 2016/01/06 Contact Me0 0
Welll send you a email with the derivation! (Secret at the moment)
Tony Barrera 2016/01/06 Contact Me0 0
The Ultra Circle derivation has been sent to Will Perone -Tony Barrera, Barrera Science Lab.
2016/01/060 0
i have problem with the browser. Ultra Circle mathematics derivation, by Tony Barrera.
Tony Barrera 2016/07/31 Contact Me0 0
Hi! Will! We have been contacted by Jack Bresenham himself! He interested in our latest circle algorithm! Send us a mail, we have ideas of the optimisation of large circles, how to calculate the spans! So you can make an even faster large circle. Ton Barrera/Ewert Bengtsson and Anders Hast.
Jamesjeake 2016/12/10 Contact Me0 0
qy3622 http://buy-propecia-online.pw buy proscar finasteride 5mg jb2400js9336er875 qy8879ci756br4931

<- for private contact