CODEWITHSUNDEEP
c#c++geometry
Mr. Smith
Mr. Smith

Reputation: 4506

What algorithm is used for computing a circle with floating point radius?

The midpoint circle algorithm is well suited for computing circles when their radius is an integer.

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

For example, when passed r=1 and r=2 the outputs are as follows respectively:

.....  .XXX.
..X..  X...X
.X.X.  X...X
..X..  X...X
.....  .XXX.
 r=1    r=2

However, I need a couple more steps between r=1 and r=2. Perhaps (hypothetically) r=1.33 and r=1.66 which might look like this:

.....  .....  ..X..  .XXX.
..X..  .XXX.  .X.X.  X...X
.X.X.  .X.X.  X...X  X...X
..X..  .XXX.  .X.X.  X...X
.....  .....  ..X..  .XXX.
r=1.0  r=1.3  r=1.6  r=2.0

However, when I try to adapt the algorithm above to use floating point arithmetic (with or without rounding), it loses its symmetry and generates discontinuous paths (resulting in some very odd shapes).

Is there a more suited algorithm for my purposes?

Upvotes: 0

Views: 3125

Answers (3)

Y.AL
Y.AL

Reputation: 1793

I think that Taylor approximation may be useful

  • calculate the x in x^2= r^2- y^2 using the first order Taylor approximation (sqrt(u^2 + a) = u + a / 2u)

Upvotes: 0

AProgrammer
AProgrammer

Reputation: 52294

If you are only interested in simple fractions (like 4/3 and 5/3), I'd oversample (i.e. use subpixels, here 9 sub-pixels per pixels, so compute circles with radius 4 and 5 subpixels) and then deduce a good value of the pixel from the sub-pixels. If you deduce to something else than ON, OFF you are doing anti-aliasing.

Upvotes: 2

Mashton
Mashton

Reputation: 6415

Basic circle drawing ...

public void DrawCircle(float stepSize, float radius, int colour)
{
    float x, y;
    float angle;

    while (angle < 2*Math.PI)
    {
        x = radius * cos(angle);
        y = radius * sin(angle);
        // decide how to round your floating point X,Y here ...
        drawpixel(x,y,colour);
        angle += stepSize;
    }
}

Upvotes: 0

Related Questions