Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
, 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
Bresenham's line algorithm
The Bresenham line algorithm is an algorithm which determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points...
, and is thus sometimes known as Bresenham's circle algorithm, although not actually invented by Bresenham. The algorithm can be generalized to conic section
Conic section
In mathematics, a conic section is a curve obtained by intersecting a cone with a plane. In analytic geometry, a conic may be defined as a plane algebraic curve of degree 2...
s.
The algorithm is related to work by Pitteway and Van Aken.
A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....
equation . So, the center of the circle is located at (0,0). We consider first only the first octant and draw a curve which starts at point and proceeds upwards and to the left, reaching the angle of 45°.
The "fast" direction here is the direction. The algorithm always does a step in the positive direction (upwards), and every now and then also has to do a step in the "slow" direction, the negative direction.
The frequent computations of squares in the circle equation, trigonometric
Trigonometry
Trigonometry is a branch of mathematics that studies triangles and the relationships between their sides and the angles between these sides. Trigonometry defines the trigonometric functions, which describe those relationships and have applicability to cyclical phenomena, such as waves...
In mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x...
s 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 , where is computed only a single time during initialization)
Let the points on the circle be a sequence of coordinates of the vector to the point (in the usual basis). Let n denote which point to be looked at, starting at the one on the horizontal axis, on the first quadrant.
Then for each point also holds:
Likewise for the next point:
That is:
Likewise for the next point:
In general, it is true that:
So we refashion our next-point-equation into a recursive one by substituting :
Because of the continuity of the circle and because is is a circle (i.e. maximum along both axes is the same) we know we will not be skipping x points as we advance in the sequence. Mostly we will either stay on the same x coordinate or advance by one.
Additionally we need to add the midpoint coordinates when setting a pixel. These frequent integer additions do not limit the performance
Performance tuning
Performance tuning is the improvement of system performance. This is typically a computer application, but the same methods can be applied to economic markets, bureaucracies or other complex systems. The motivation for such activity is called a performance problem, which can be real or anticipated....
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 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 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;
Note: There is correlation between this algorithm and the sum of first 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.
Optimization
The following adaption of the circle algorithm is useful for machines where registers are scarce. Only three variables are needed in the main loop to perform the calculation. Although written in C, the code has been written to better reflect how it might be implemented in assembly code.
// 'cx' and 'cy' denote the offset of the circle centre from the origin.
void circle(int cx, int cy, int radius)
{
int error = -radius;
int x = radius;
int y = 0;
// The following while loop may altered to 'while (x > y)' for a
// performance benefit, as long as a call to 'plot4points' follows
// the body of the loop. This allows for the elimination of the
// '(x != y') test in 'plot8points', providing a further benefit.
//
// For the sake of clarity, this is not shown here.
while (x >= y)
{
plot8points(cx, cy, x, y);
error += y;
++y;
error += y;
// The following test may be implemented in assembly language in
// most machines by testing the carry flag after adding 'y' to
// the value of 'error' in the previous step, since 'error'
// nominally has a negative value.
if (error >= 0)
{
error -= x;
--x;
error -= x;
}
}
}
void plot8points(int cx, int cy, int x, int y)
{
plot4points(cx, cy, x, y);
if (x != y) plot4points(cx, cy, y, x);
}
// The '(x != 0 && y != 0)' test in the last line of this function
// may be omitted for a performance benefit if the radius of the
// circle is known to be non-zero.
void plot4points(int cx, int cy, int x, int y)
{
setPixel(cx + x, cy + y);
if (x != 0) setPixel(cx - x, cy + y);
if (y != 0) setPixel(cx + x, cy - y);
if (x != 0 && y != 0) setPixel(cx - x, cy - y);
}
Drawing incomplete octants
The implementations above always only draw complete octants or circles. To draw only a certain arc
Arc (geometry)
In geometry, an arc is a closed segment of a differentiable curve in the two-dimensional plane; for example, a circular arc is a segment of the circumference of a circle...
from an angle to an angle , the algorithm needs first to calculate the and coordinates of these end points, where it is necessary to resort to trigonometric or square root computations (see Methods of computing square roots
Methods of computing square roots
There are several methods for calculating the principal square root of a nonnegative real number. For the square roots of a negative or complex number, see below.- Rough estimation :...
). 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.
In mathematics, the slope or gradient of a line describes its steepness, incline, or grade. A higher slope value indicates a steeper incline....
s, then no trigonometry or square roots are required: one simply checks that is between the desired slopes.
Ellipses
It is possible to generalize the algorithm to handle ellipse
Ellipse
In geometry, an ellipse is a plane curve that results from the intersection of a cone by a plane in a way that produces a closed curve. Circles are special cases of ellipses, obtained when the cutting plane is orthogonal to the cone's axis...
s (of which circles are a special case). These algorithms involve calculating a full quadrant of the ellipse, as opposed to an octant as explained above, since non-circular ellipses lack the x-y symmetry of a circle.
The algorithm is related to work by Pitteway and Van Aken.
. So, the center of the circle is located at (0,0). We consider first only the first octant and draw a curve which starts at point 
and proceeds upwards and to the left, reaching the angle of 45°.
direction. The algorithm always does a step in the positive 
direction (upwards), and every now and then also has to do a step in the "slow" direction, the negative 
direction.
, where 
is computed only a single time during initialization)
:
in the error term, so that this value is used for initialization.
above. It just has to be increased by 2 from one step to the next:
odd numbers, which this one basically does. That is,
to an angle 
, the algorithm needs first to calculate the 
and 
coordinates of these end points, where it is necessary to resort to trigonometric or square root computations (see Methods of computing square roots
is between the desired slopes.