المساعد الشخصي الرقمي

مشاهدة النسخة كاملة : Building a Better Circle Algorithm Than Bresenham



A7med Baraka
03-30-2009, 01:50 AM
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.
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
}
}