Midpoint circle algorithm

From Wikipedia, the free encyclopedia

In computer graphics, the midpoint circle algorithm is an algorithm used to determine the points needed for drawing a circle. The algorithm is a variant of Bresenham's line algorithm, and is thus sometimes known as Bresenham's circle algorithm, although not actually invented by Bresenham.

Rasterisation of a circle by the Bresenham algorithm

The algorithm is related to work by Pitteway ^[1] and van Aken.^[2]

[edit] The algorithm

This article may be confusing or unclear to readers. Please help clarify the article; suggestions may be found on the talk page. (February 2009)

The algorithm starts accordingly with the circle equation x² + y² = r². We consider first only the first octant and draw a curve which starts at point (r,0) and proceeds upwards and to the left, reaching the angle of 45°.

The "fast" direction here is the y direction. The algorithm always does a step in the positive y direction (upwards), and every now and then also has to do a step in the "slow" direction, the negative x direction.

The frequent computations of squares in the circle equation, trigonometric expressions or square roots can again be avoided by dissolving everything into single steps and recursive computation of the quadratic terms from the preceding ones.

From the circle equation we obtain the transformed equation 0 = x² + y² − r², with r² to be computed only a single time during initialization:

and accordingly for the y-coordinate. Additionally we need to add the midpoint coordinates when setting a pixel. These frequent integer additions do not limit the performance much, as we can spare those square (root) computations in the inner loop in turn. Again the zero in the transformed circle equation is replaced by the error term.

The initialization of the error term is derived from an offset of ½ pixel at the start. Until the intersection with the perpendicular line, this leads to an accumulated value of r in the error term, so that this value is used for initialization.

A possible implementation of the Bresenham Algorithm for a full circle in C. Here another variable for recursive computation of the quadratic terms is used, which corresponds with the term 2n + 1 above. It just has to be increased by 2 from one step to the next:

  void rasterCircle(int x0, int y0, int radius)
  {
    int f = 1 - radius;
    int ddF_x = 1;
    int ddF_y = -2 * radius;
    int x = 0;
    int y = radius;
 
    setPixel(x0, y0 + radius);
    setPixel(x0, y0 - radius);
    setPixel(x0 + radius, y0);
    setPixel(x0 - radius, y0);
 
    while(x < y)
    {
      assert(ddF_x == 2 * x + 1);
      assert(ddF_y == -2 * y);
      assert(f == x*x + y*y - radius*radius + 2*x - y + 1);
      if(f >= 0) 
      {
        y--;
        ddF_y += 2;
        f += ddF_y;
      }
      x++;
      ddF_x += 2;
      f += ddF_x;    
      setPixel(x0 + x, y0 + y);
      setPixel(x0 - x, y0 + y);
      setPixel(x0 + x, y0 - y);
      setPixel(x0 - x, y0 - y);
      setPixel(x0 + y, y0 + x);
      setPixel(x0 - y, y0 + x);
      setPixel(x0 + y, y0 - x);
      setPixel(x0 - y, y0 - x);
    }
  }

Note: There is correlation between this algorithm and the sum of first N odd numbers, which this one basically does. That is,

 So.
 When we compare sum of N odd numbers to this algorithm we have.
 ddF_y = -2 * radius       is connected to last member of sum of N odd numbers.
                           This member has index equal to value of radius (integral). 
                           Since odd number is 2*n + 1 there is 1 handled elsewhere
                           or it should be -2*radius - 1
 ddF_x = 0                 should be 1. Because difference between two consecutive odd numbers is 2.
                           If so f += ddF_y + 1 is f+= ddF_y. Saving one operation.
 f = - radius + 1          Initial error equal to half of "bigger" step. 
                           In case of saving one addition it should be either -radius or -radius + 2.
 In any case there should be addition of 1 driven out of outer loop.
 So.
 f += ddF_y                Adding odd numbers from Nth to 1st. 
 f += ddF_x                Adding odd numbers from 1st to Nth. 1 is missing because it can be moved outside of loop.

[edit] Drawing incomplete octants

The implementations above always only draw complete octants or circles. To draw only a certain arc from an angle α to an angle β, the algorithm needs first to calculate the x and y coordinates of these end points, where it is necessary to resort to trigonometric or square root computations (see Methods of computing square roots). Then the Bresenham algorithm is run over the complete octant or circle and sets the pixels only if they fall into the wanted interval. After finishing this arc, the algorithm can be ended prematurely.

Note that if the angles are given as slopes, then no trigonometry or square roots are required: one simply checks that y / x is between the desired slopes.

[edit] Ellipses

By scaling the drawn x and y values (and horizontal or vertical line expansion, respectively) the algorithm can produce ellipses parallel to the x or y axis. For this, we use the circle algorithm with the smaller ellipse axis as radius and add a value in the other direction, which again is computed through another Bresenham line algorithm increasing from the pole to the equator. As the ellipse has to be elongated into the longer axis direction, the algorithm cannot set single pixels any more, but has to draw lines (though simple ones, only horizontal or vertical) from the previous to the next point.

A general ellipse can be derived from such an axis-parallel one by application of a shear mapping on it. Again an additional Bresenham line algorithm is used to compute the offset increasing in one of the axis directions and to let it contribute to every drawn coordinate.

[edit] References