Tutorial :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);              }  


Solution:6

Here's how I'm doing it:
I'm using fixed point values with two bits precision (we have to manage half points and square values of half points)
As mentionned in a previous answer, I'm also using square values instead of square roots.
First, I'm detecting border limit of my circle in a 1/8th portion of the circle. I'm using symetric of these points to draw the 4 "borders" of the circle. Then I'm drawing the square inside the circle.

Unlike the midpoint circle algorith, this one will work with even diameters (and with real numbers diameters too, with some little changes).

Please forgive me if my explanations were not clear, I'm french ;)

void DrawFilledCircle(int circleDiameter, int circlePosX, int circlePosY)  {      const int FULL = (1 << 2);      const int HALF = (FULL >> 1);        int size = (circleDiameter << 2);// fixed point value for size      int ray = (size >> 1);      int dY2;      int ray2 = ray * ray;      int posmin,posmax;      int Y,X;      int x = ((circleDiameter&1)==1) ? ray : ray - HALF;      int y = HALF;      circlePosX -= (circleDiameter>>1);      circlePosY -= (circleDiameter>>1);        for (;; y+=FULL)      {          dY2 = (ray - y) * (ray - y);            for (;; x-=FULL)          {              if (dY2 + (ray - x) * (ray - x) <= ray2) continue;                if (x < y)              {                  Y = (y >> 2);                  posmin = Y;                  posmax = circleDiameter - Y;                    // Draw inside square and leave                  while (Y < posmax)                  {                      for (X = posmin; X < posmax; X++)                          setPixel(circlePosX+X, circlePosY+Y);                      Y++;                  }                  // Just for a better understanding, the while loop does the same thing as:                  // DrawSquare(circlePosX+Y, circlePosY+Y, circleDiameter - 2*Y);                  return;              }                // Draw the 4 borders              X = (x >> 2) + 1;              Y = y >> 2;              posmax = circleDiameter - X;              int mirrorY = circleDiameter - Y - 1;                while (X < posmax)              {                  setPixel(circlePosX+X, circlePosY+Y);                  setPixel(circlePosX+X, circlePosY+mirrorY);                  setPixel(circlePosX+Y, circlePosY+X);                  setPixel(circlePosX+mirrorY, circlePosY+X);                  X++;              }              // Just for a better understanding, the while loop does the same thing as:              // int lineSize = circleDiameter - X*2;              // Upper border:              // DrawHorizontalLine(circlePosX+X, circlePosY+Y, lineSize);              // Lower border:              // DrawHorizontalLine(circlePosX+X, circlePosY+mirrorY, lineSize);              // Left border:              // DrawVerticalLine(circlePosX+Y, circlePosY+X, lineSize);              // Right border:              // DrawVerticalLine(circlePosX+mirrorY, circlePosY+X, lineSize);                break;          }      }  }    void DrawSquare(int x, int y, int size)  {      for( int i=0 ; i<size ; i++ )          DrawHorizontalLine(x, y+i, size);  }    void DrawHorizontalLine(int x, int y, int width)  {      for(int i=0 ; i<width ; i++ )          SetPixel(x+i, y);  }    void DrawVerticalLine(int x, int y, int height)  {      for(int i=0 ; i<height ; i++ )          SetPixel(x, y+i);  }  

To use non-integer diameter, you can increase precision of fixed point or use double values. It should even be possible to make a sort of anti-alias depending on the difference between dY2 + (ray - x) * (ray - x) and ray2 (dx² + dy² and r²)


Solution:7

If you want a fast algorithm, consider drawing a polygon with N sides, the higher is N, the more precise will be the circle.


Solution:8

I would just generate a list of points and then use a polygon draw function for the rendering.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »