fast algorithm for drawing filled circles?

Question

I am using Bresenham's circle algorithm for fast circle drawing. However, I also want to (at the request of the user) draw a filled circle.

Is there a fast and efficient way of doing this? Something along the same lines of Bresenham?

The language I am using is C.

Solution 1

Having read the Wikipedia page on Bresenham's (also 'Midpoint') circle algorithm, it would appear that the easiest thing to do would be to modify its actions, such that instead of

setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);

and similar, each time you instead do

lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);

That is, for each pair of points (with the same y) that Bresenham would you have you plot, you instead connect with a line.

Solution 2

Just use brute force. This method iterates over a few too many pixels, but it only uses integer multiplications and additions. You completely avoid the complexity of Bresenham and the possible bottleneck of sqrt.

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);

Solution 3

Here's a C# rough guide (shouldn't be that hard to get the right idea for C) - this is the "raw" form without using Bresenham to eliminate repeated square-roots.

Bitmap bmp = new Bitmap(200, 200);

int r = 50; // radius
int ox = 100, oy = 100; // origin

for (int x = -r; x < r ; x++)
{
    int height = (int)Math.Sqrt(r * r - x * x);

    for (int y = -height; y < height; y++)
        bmp.SetPixel(x + ox, y + oy, Color.Red);
}

bmp.Save(@"c:\users\dearwicker\Desktop\circle.bmp");

Solution 4

You can use this:

void DrawFilledCircle(int x0, int y0, int radius)
{
    int x = radius;
    int y = 0;
    int xChange = 1 - (radius << 1);
    int yChange = 0;
    int radiusError = 0;

    while (x >= y)
    {
        for (int i = x0 - x; i <= x0 + x; i++)
        {
            SetPixel(i, y0 + y);
            SetPixel(i, y0 - y);
        }
        for (int i = x0 - y; i <= x0 + y; i++)
        {
            SetPixel(i, y0 + x);
            SetPixel(i, y0 - x);
        }

        y++;
        radiusError += yChange;
        yChange += 2;
        if (((radiusError << 1) + xChange) > 0)
        {
            x--;
            radiusError += xChange;
            xChange += 2;
        }
    }
}

Solution 5

I like palm3D's answer. For being brute force, this is an amazingly fast solution. There are no square root or trigonometric functions to slow it down. Its one weakness is the nested loop.

Converting this to a single loop makes this function almost twice as fast.

int r2 = r * r;
int area = r2 << 2;
int rr = r << 1;

for (int i = 0; i < area; i++)
{
    int tx = (i % rr) - r;
    int ty = (i / rr) - r;

    if (tx * tx + ty * ty <= r2)
        SetPixel(x + tx, y + ty, c);
}

This single loop solution rivals the efficiency of a line drawing solution.

            int r2 = r * r;
            for (int cy = -r; cy <= r; cy++)
            {
                int cx = (int)(Math.Sqrt(r2 - cy * cy) + 0.5);
                int cyy = cy + y;

                lineDDA(x - cx, cyy, x + cx, cyy, c);
            }

View more solutions

Comments

[dmckee --- ex-moderator kitten]

Or loop on y and draw horizonal lines. Occasionally there is a reason to choose one or the other, but in most cases it does not matter. Either way you use the same Bresenham logic to find the endpoints quickly.

[dmckee --- ex-moderator kitten]

If he has implemented Bresenham for the open version, he is working at a lower layer then using an API...either for learning purposes or to implement an API.

[Daniel Earwicker]

No, but you can use Bresenham to avoid that. The basic idea is to "join the dots" between the upper and lower points at each x coordinate covered by the circle.

[colithium]

Profile to see which is best. If there's a difference at all, going horizontal should be better. It gets rid of a multiplication by stride and may result in fewer faults.

[Daniel Earwicker]

@AakashM - have you tried it? I find it makes almost no measurable difference whether I compute the Math.Sqrt or not. (Obviously I've eliminated the SetPixel as well, which accounts for ALL the time in the complete program; I just add x and y to a counter variable to ensure they're used).

[Daniel Earwicker]

"All those Math.Sqrts aren't going to be especially fast" - the disassembly shows that the C#/JIT combo emits the inlined SQRTSD instruction on my 64-bit machine, and so it's little wonder that it runs blazingly fast. I can't measure a different between Math.Sqrt and a simple addition. So I think your comment is probably based on pre-FP instruction set guessing!

[Daniel Earwicker]

This is surprising to me too, as it's been a while since I've had to use Sqrt for anything, so I've blogged it here: smellegantcode.wordpress.com/2009/07/29/square-roots-are-slo‌​w

[AakashM]

That perennial problem - what to do with one's carefully-tuned educated-guesswork engine when the fundamentals change?

[Daniel Earwicker]

Well, depends if you want to learn about history or get the job done - personally I enjoy both! :)

[Dwight]

I like this answer because it solves the problem in a very direct way. The only problem with this is that it generates a different circle than the midpoint circle algorithm. These circles are "thinner" than the equivalent in midpoint, which appear to be the more correct shape. Any way to fix that?

[Dwight]

This sounds horrible, but I found that in most cases I can get the exact same circle from this algorithm as midpoint if I modify the check slightly. Those times it doesn't exactly match up, it's pretty close. The modification to the check is: x * x + y * y <= range * range + range * 0.8f

[AJed]

does that really work ? i tried it .. it doesn't totally fill the circle. Am I missing something ? In any case, there are some correct answers below.

[AakashM]

@AJed To know if you're missing something, we'd need to see your code, in a new question of your own

[Tommy]

Wouldn't this cause scan lines in the 2nd/3rd and 6th/7th quadrants to be repeated? In those x changes at every step and the decision variable governs y.

[Spikolynn]

this would probably require some kind of hardware acceleration to be fastest

[Vikram Bhat]

@AakashM ok it seems I have misread the answer , it seems like a scan line algorithm which would do. I dont remember exactly but i think had connected the symmetric point 180 deg apart to make the lines and that doesnt work as lot of them overlap. Make some edit to answer so that I can remove by downvote.

[Marcin]

I had the same issue as Dwight, but to avoid the float cast just replaced the if statement with this one: if(x*x+y*y < radius*radius + radius) also to get just the circle (ring) you can do this if(x*x+y*y > radius*radius - radius && x*x+y*y < radius*radius + radius)

[ALex]

I am trying to have for border a color, and for fill another color. I to exactly what you said and after i construct the border with the basic command for the algorithm. the problem is that in the upper and bottom parts of the circle, the border is covered by the fill color, Any idea why ?

[AakashM]

@Loki that sounds like a new question really, but sounds like you want the setPixel commands in normal Bresenham and a lineFrom command that omits the end pixels.

[ALex]

@AakashM i solved it. When i am drawing the lines i use drawLines(circle.center, p, q-1);

[Florian Prud'homme]

I'm a bit surprised that your solution is faster than palm3d. Did you measure it ? do you have numbers ?

[JSmith]

hi, any clue how to have the same kind of algorithm without line overlapping?

[AakashM]

@JSmith not sure what you mean, sounds like you need to ask a new question

[JSmith]

well I'm using this algorithm but I see that this algorithm draw twice even three times the same pixel, also when it does'nt I have at the top of the circle 3 lines overlapping of different width (I'm drawing squares I'm not using pixel's screen) I'll probably ask a new question. But if you have a clue I'll take it . Thanks

[mid]

Yup, looping on y makes more sense when blitting on a framebuffer.

[Brandon]

This algorithm draws less pixels than the original. For a radius of 10, it does 41 loops less.. On my laptop, running 100,000,000 tests of this function and the original, we get: ORIGINAL: 43ns. THIS: 42ns on a good run.. On a bad run: ORIGINAL: 87ns. THIS: 54ns.. but these are nano-seconds so in terms of efficiency, there's virtually no difference. Tested on: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz

[AlexGeorg]

Hmm, am quite confused to where this is supposed to be faster.. Am currently trying all variants in quick-bench.com/VtgMOwU8IQoa7biFNHFZ2ws5hlk and it is much, much slower. That doe snot really surprise me though because divisions are often very slow.

[AlexGeorg]

Congrats, according to my tests on quick-bench, your solution is by far the fastest! quick-bench.com/mwTOodNOI81k1ddaTCGH_Cmn_Ag

[Slight]

@Marcin To avoid the float cast you added a whole new branch and 5 new arithmetic operations and that's supposed to be faster?

[Marcin]

@Slight There are no extra operations, replaced <= with < and radius * 0.8f with + radius the other if statement is unrelated (for when you want just an outline).