 |
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 14th, 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 14th, 2004, 9:22pm by lunetta » |
|
|
|
|
lunetta
|
Re: what is the fastest algorithm to draw a circle
« Reply #1 on: May 14th, 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*r-i*i);
for(x=s;x<=px;x++) {
set(cx+x,cy+y,255);
set(cx-x,cy-y,255);
set(cx+x,cy-y,255);
set(cx-x,cy+y,255);
}
px=s;
}
|
|
|
|
|
justo
|
Re: what is the fastest algorithm to draw a circle
« Reply #2 on: May 14th, 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 anti-aliasing w/o supersampling).
one problem though is that youll have to do per-pixel 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 14th, 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 14th, 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 circle-like 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 14th, 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 9th, 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(x-r,y,color);
DrawPixel(x,y+r,color);
DrawPixel(x,y-r,color);
DrawPixel(x+x1,y+x1,color);
DrawPixel(x+x1,y-x1,color);
DrawPixel(x-x1,y+x1,color);
DrawPixel(x-x1,y-x1,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(x-pos_x,y+pos_y,coulor);
DrawPixel(x+pos_x,y-pos_y,coulor);
DrawPixel(x-pos_x,y-pos_y,coulor);
DrawPixel(x+pos_y,y+pos_x,coulor);
DrawPixel(x-pos_y,y+pos_x,coulor);
DrawPixel(x+pos_y,y-pos_x,coulor);
DrawPixel(x-pos_y,y-pos_x,coulor);
}
}
|
|
|
|
|
Quasimondo
|
Re: what is the fastest algorithm to draw a circle
« Reply #7 on: Jun 10th, 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/103-0704706-725 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=y-radius;
int y3check=y;
int y4check=y;
int IX = 0;
int IY = radius;
int IX1 = x;
int IX2 = x;
int IX3 = x+radius;
int IX4 = x-radius;
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 11th, 2004, 11:27am by Quasimondo » |
|
Mario Klingemann | Quasimondo | Incubator | côdeazur
|
|
|
|
