# 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 } }

harry2376 38Asger Joergensen137 27coyote136 58...

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.

Will32 29Tony Barrera2010/12/03Contact Me7 18Will2010/12/03Contact Me8 162011/01/21Contact Me2 1Will2011/01/21Contact Me4 11Tony Barrera2011/05/13Contact Me3 14Will2011/05/132 11Tony Barrera2011/05/20Contact Me12 1Will2011/05/2021 10Tony Barrera2011/05/30133 3Will2011/05/313 133Mickey2011/07/08Contact Me3 133tony barrera2011/07/09Contact Me0 0hve beeing similar things for some algorithms. Could you explaine more of what you are doing.

Regina2011/07/09Contact Me1 0Josef2012/07/15Contact Me3 2what 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.

Will2012/07/157 16291Aziz2012/09/11Contact Me6 104bob2012/09/21Contact Me2 2a 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.

bob2012/09/21Contact Me0 0The 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.

bob2012/09/21Contact Me3403 7086To 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.

richa2013/01/27Contact Me3 1soumya2013/11/138 3Tony Barrera2015/06/150 0Anon2015/06/290 0Where can we find it?

Thanks!

2015/10/180 0Hi! Yes the super-circle algorithm has now been published! - Tony Barrera.

2015/10/190 0Tony Barrera2015/11/15Contact Me0 0See:

https://plus.google.com/u/0/100507551400981078302

Barrera Science Lab

Tony Barrera2015/11/17Contact Me0 0//////////// 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 Barrera2015/11/17Contact Me0 0Will2016/01/01Contact Me0 0for (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 02016/01/060 0begin{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 Barrera2016/01/060 0Tony Barrera2016/01/06Contact Me0 0Tony Barrera2016/01/06Contact Me0 02016/01/060 0Tony Barrera2016/07/31Contact Me0 0