
Author 
Topic: what is the fastest algorithm to draw a circle? (Read 4637 times) 

lunetta

what is the fastest algorithm to draw a circle?
« on: May 14^{th}, 2004, 8:49pm » 

Hello all dear processers I'm developing a sketch that draws *lots* of circles; just the stroke, not the filling; I need to draw these circles controlling its pixels; given a radius and a center coordinate, I need to draw the pixels that make a circle. There are a thousand of ways to do this; I'm certainly employing the most awkward dumb one. Wha would be the fastest algorithm to perform this simple task? thanks!!!

« Last Edit: May 14^{th}, 2004, 9:22pm by lunetta » 




lunetta

Re: what is the fastest algorithm to draw a circle
« Reply #1 on: May 14^{th}, 2004, 10:42pm » 

here is the code I'm using, as an example: size(500,500); int x; int y; int r = 200; int px = r; int s; int cx = 200; int cy = 200; // for(int i=0;i<=r;i++) { y=i; s=(int) sqrt(r*ri*i); for(x=s;x<=px;x++) { set(cx+x,cy+y,255); set(cxx,cyy,255); set(cx+x,cyy,255); set(cxx,cy+y,255); } px=s; }




justo

Re: what is the fastest algorithm to draw a circle
« Reply #2 on: May 14^{th}, 2004, 10:44pm » 

can you not just use processing's ellipse with no fill? if not, there are, like you said, many many ways of doing this. unfortunately, many of them get bogged down in special cases, especially when clipping is involved. the fastest that i've ever implemented is bresenham's circle algorithm...i tried googling it, but i couldnt find a lot of resources for you that really explained it along with the source code...i based mine off of the superb treatment of it in "computer graphics: principals and practice." it takes advantage of the symmetry of circles (so you only have to calculate 1/8 of the actual circle), and the fact that you are drawing it on an inherently discretized surface (ie youre drawing using pixels...though this is no good for antialiasing w/o supersampling). one problem though is that youll have to do perpixel clipping, since you are only drawing single pixels and you dont want to draw off the screen (which would either wrap around or cause an ArrayIndexOutOfBoundsException). i think this is why processing uses many line segments to make up the circle (at least i assume it does, based on what happens when you use a thick line with a circle). anyway, links: http://www.gamedev.net/reference/articles/article767.asp this one's better: http://www.cc.gatech.edu/classes/AY2003/cs4451_spring/brescirc.pdf if you want, i can post the source to my circle drawing algo when i get home from work. good luck justo




lunetta

Re: what is the fastest algorithm to draw a circle
« Reply #3 on: May 14^{th}, 2004, 11:09pm » 

thanks, this is the kind of information I was looking for!




justo

Re: what is the fastest algorithm to draw a circle
« Reply #4 on: May 14^{th}, 2004, 11:20pm » 

how slow is that? i bet not too slow. another way to think of it is a circle as a continually subdivided rotated square...sin and cos may be slow, but they arent that slow...writing the pixels often ends up being the most expensive part. so, that rotated square would be: Code:line(cx + r, cy, cx, cy  r); line(cx, cy  r, cx  r, cy); line(cx  r, cy, cx, cy + r); line(cx, cy + r, cx + r, cy); 
 and subdivided once (so its a hexagon): Code:line(cx + r, cy, cx + (cos(PI / 4) * r), cy + (sin(PI / 4) * r)); line(cx + (cos(PI / 4) * r), cy + (sin(PI / 4) * r), cx, cy  r); line(cx, cy  r, cx + (cos(PI * .75) * r), cy + (sin(PI * .75) * r)); line(cx + (cos(PI * .75) * r), cy + (sin(PI * .75) * r), cx  r, cy); and etc 
 also, cx + r, for example, is equivalent to cx + cos(0) * r, so it should be obvious that this can be generalized...like you were doing with your sqrt method. Code:float iter = TWO_PI / subdivideNum; float theta; for(theta = 0.0; theta < TWO_PI; theta += iter) { line(cx + (cos(theta) * r), cy + (sin(theta) * r), cx + (cos(theta + iter) * r), cy + (sin(theta + iter) * r)); } 
 where subdivideNum is the number of sieds to the shape...the more sides, the more circlelike it is. obviously even this rather simple algorithm can be optimized quite a bit...for instance, one line's ending point is the next line's starting point. no need to calculate it twice. bresenham's algorithm is essentially this, except it uses an incremental method to travel around the circle instead of using sin and cos, which are relatively slow, especially compared to an add.




Charles Hinshaw

Re: what is the fastest algorithm to draw a circle
« Reply #5 on: May 14^{th}, 2004, 11:42pm » 

... calculating which pixels are part of the circle is only one aspect of "drawing" the circle  the other side of things, the way you are drawing your pixels, can be dramatically improved as well.

Charles Hinshaw PHAERSE
http://www.phaerse.com



Etienne Boutin Guest

Re: what is the fastest algorithm to draw a circle
« Reply #6 on: Jun 9^{th}, 2004, 9:45pm » 

Hi, I think I have the fastest way to draw a circle. That's my own creation. In the loop, it doesn't need multiplication, division, float operations or sinus. Try it and please send me a comment on it. ////////////////////////////////////////////////////// //FONCTIN DrawCircle // For drawing a circle ////////////////////////////////////////////////////// void DrawCircle(int x, int y, int r, int color) { int pos_x, pos_y = r, tx = 0, ty = 4*r, a = 0, b = 2*ty+9, x1 = int(r*0.707010678 + 0.5); DrawPixel(x+r,y,color); DrawPixel(xr,y,color); DrawPixel(x,y+r,color); DrawPixel(x,yr,color); DrawPixel(x+x1,y+x1,color); DrawPixel(x+x1,yx1,color); DrawPixel(xx1,y+x1,color); DrawPixel(xx1,yx1,color); for(pos_x = 1;pos_x < x1;pos_x++) { a += 8; tx += a; if(tx > ty) { pos_y++; b = 8; ty += b; } DrawPixel(x+pos_x,y+pos_y,coulor); DrawPixel(xpos_x,y+pos_y,coulor); DrawPixel(x+pos_x,ypos_y,coulor); DrawPixel(xpos_x,ypos_y,coulor); DrawPixel(x+pos_y,y+pos_x,coulor); DrawPixel(xpos_y,y+pos_x,coulor); DrawPixel(x+pos_y,ypos_x,coulor); DrawPixel(xpos_y,ypos_x,coulor); } }




Quasimondo

Re: what is the fastest algorithm to draw a circle
« Reply #7 on: Jun 10^{th}, 2004, 10:41pm » 

As I just love to optimize code, I had to give it a try, too. My basic algorithm is based on Jim Blinn's optimized version of the Bresenham, which can be found in "Jim Blinn's corner"  http://www.amazon.com/gp/reader/1558603875/ref=sib_dp_pt/1030704706725 3424 , a very inspiring collection of his IEEE articles). I spiced it up with a fast way to access the pixels[] array which includes a bounds check if needed. So Etienne, as I don't have access to your DrawPixels routine I cannot say how fast that might be, but when I replace all your DrawPixel() with set() in order to compare them, my following method is about 3 times faster: Code: void drawCircle(int x,int y,int radius,int col){ int IG = (radius<<1)  3; int IDGR = 6; int IDGD = (radius<<2)  10; int w=width; int h=height; int y1check=y+radius; int y2check=yradius; int y3check=y; int y4check=y; int IX = 0; int IY = radius; int IX1 = x; int IX2 = x; int IX3 = x+radius; int IX4 = xradius; int IY1 = y1check*w; int IY2 = y2check*w; int IY3 = y3check*w; int IY4 = IY3; if (IX4>=0 && IX3<w && y2check>=0 && y1check<h){ while (IY > IX){ pixels[IX1+IY1]=pixels[IX1+IY2]=pixels[IX2+IY1]=pixels[IX2+IY2]=pixels[IX3+IY3]=pixels[IX4+IY4]=pixels[IX3+IY4]=pixels[IX4+IY3]=col; if (IG<0){ IG = IG+IDGD; IDGD = 8; IY; IY1=w; IY2+=w; IX3; IX4++; } else { IG += IDGR; IDGD =4; } IDGR = 4; IX++; IX1++; IX2; IY3=w; IY4+=w; } } else { while (IY >IX){ if (IX1>=0 && IX1<w){ if (y1check>=0 && y1check<h) pixels[IX1+IY1]=col; if (y2check>=0 && y2check<h) pixels[IX1+IY2]=col; } if (IX2>=0 && IX2<w){ if (y1check>=0 && y1check<h) pixels[IX2+IY1]=col; if (y2check>=0 && y2check<h) pixels[IX2+IY2]=col; } if (IX3>=0 && IX3<w){ if (y3check>=0 && y3check<h) pixels[IX3+IY3]=col; if (y4check>=0 && y4check<h) pixels[IX3+IY4]=col; } if (IX4>=0 && IX4<w){ if (y3check>=0 && y3check<h) pixels[IX4+IY3]=col; if (y4check>=0 && y4check<h) pixels[IX4+IY4]=col; } if (IG<0){ IG = IG+IDGD; IDGD = 8; IY1=w; IY2+=w; y1check; y2check++; IX3; IX4++; IY; } else { IG += IDGR; IDGD =4; } IDGR = 4; IX++; IX1++; IX2; IY3=w; IY4+=w; y3check; y4check++; } } } 
 There is still some room for improvement  for example if a circle is completely off the canvas the routine should immediately return. Now what would be nice it to add filling, antialiasing and some optional blend methods to this. [note] I have updated the code and removed a bug [/note]

« Last Edit: Jun 11^{th}, 2004, 11:27am by Quasimondo » 

Mario Klingemann  Quasimondo  Incubator  côdeazur



