Midpoint circle algorithm
[1][2][3] This algorithm draws all eight octants simultaneously, starting from each cardinal direction (0°, 90°, 180°, 270°) and extends both ways to reach the nearest multiple of 45° (45°, 135°, 225°, 315°).
The reason for using these angles is shown in the above picture: As x increases, it neither skips nor repeats any x value until reaching 45°.
Because in a continuous function, the function for a sphere is the function for a circle with the radius dependent on z (or whatever the third variable is), it stands to reason that the algorithm for a discrete (voxel) sphere would also rely on the midpoint circle algorithm.
Instead, a circle of the same radius needs a different determinant, to allow the curve to come in slightly closer to the center or extend out farther.
At each step, the path is extended by choosing the adjacent pixel which satisfies
Since the candidate pixels are adjacent, the arithmetic to calculate the latter expression is simplified, requiring only bit shifts and additions.
Keep in mind that a left bitshift of a binary number is the same as multiplying with 2.
The fast direction here (the basis vector with the greater increase in value) is the
: Because of the continuity of a circle and because the maxima along both axes are the same, clearly it will not be skipping x points as it advances in the sequence.
Usually it stays on the same x coordinate, and sometimes advances by one to the left.
These frequent integer additions do not limit the performance much, as those square (root) computations can be spared 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
The frequent computations of squares in the circle equation, trigonometric expressions and square roots can again be avoided by dissolving everything into single steps and using recursive computation of the quadratic terms from the preceding iterations.
, the radius error is defined as: For clarity, this formula for a circle is derived at the origin, but the algorithm can be modified for any location.
Because the radius will be a whole number of pixels, clearly the radius error will be zero: Because it starts in the first counter-clockwise positive octant, it will step in the direction with the greatest travel, the Y direction, so it is clear that
Also, because it concerns this octant only, the X values have only 2 options: to stay the same as the prior iteration, or decrease by 1.
A decision variable can be created that determines if the following is true: If this inequality holds, then plot
, so dividing gets: Thus, the decision criterion changes from using floating-point operations to simple integer addition, subtraction, and bit shifting (for the multiply by 2 operations).
Again, by reflecting these points in all the octants, a full circle results.
The algorithm has already been explained to a large extent, but there are further optimizations.
The new presented method[4] gets along with only 5 arithmetic operations per step (for 8 pixels) and is thus best suitable for low-performate systems.
Yes or No) and there is a variable assignment, which is also not considered an arithmetic operation.
The initialization in the first line (shifting by 4 bits to the right) is only due to beauty and not really necessary.
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.
If the angles are given as slopes, then no trigonometry or square roots are necessary: simply check that
It is also possible to use the same concept to rasterize a parabola, ellipse, or any other two-dimensional curve.
