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.

كود:

---

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
    }

---

}