In computer graphics, the midpoint circle algorithm is an algorithm used to determine the points needed for rasterizing a circle. It is a generalization of Bresenham's line algorithm. The algorithm can be further generalized to conic sections.

Summary

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°). It can determine where to stop because, when = , it has reached 45°. The reason for using these angles is shown in the above picture: As increases, it neither skips nor repeats any value until reaching 45°. So during the while loop, increments by 1 with each iteration, and decrements by 1 on occasion, never exceeding 1 in one iteration. This changes at 45° because that is the point where the tangent is =. Whereas before and after.

The second part of the problem, the determinant, is far trickier. This determines when to decrement . It usually comes after drawing the pixels in each iteration, because it never goes below the radius on the first pixel. Because in a continuous function, the function for a sphere is the function for a circle with the radius dependent on (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. But when looking at a sphere, the integer radius of some adjacent circles is the same, but it is not expected to have the same exact circle adjacent to itself in the same hemisphere. 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.

Algorithm

The objective of the algorithm is to approximate a circle.

The "fast" direction in the first octant (the basis vector-direction (see differentiation of trigonometric functions.

best satisfies the circle equation. The full iteration for the first octant is as follows:

is met.

Variant with integer-based arithmetic

Just as with the parent Bresenham's line algorithm:

term, the radius error can be computed recursively:

becomes

is found by approximation:

This optimized algorithm can be implemented in Python as follows:

Jesko's method

An improved midpoint circle algorithm only requires 5 arithmetic operations per step (for 8 pixels) and is thus best suitable for low-performance systems. The counted operations in the main loop are:

1. The comparison x >= y (is counted as a subtraction: x - y >= 0)

2. y=y+1 [y++]

3. t1 + y

4. t1 - x

   1. The comparison t2 >= 0 is not counted as no real arithmetic takes place. In two's complement representation of the variables, only the sign bit has to be compared.

   x=x-1 [x--]

Operations: 5

t1 = r / 16
x = r
y = 0
Repeat Until x < y
    Pixel (x, y) and all symmetric pixels are colored (8 times)
    y = y + 1
    t1 = t1 + y
    t2 = t1 - x
    If t2 >= 0
        t1 = t2
        x = x - 1

Drawing incomplete octants

The implementations above always draw only complete octants or circles. To draw only a certain arc 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 is between the desired slopes.

Generalizations

It is also possible to use the same concept to rasterize a parabola, ellipse, or any other two-dimensional curve.

References

External links

• Drawing circles - An article on drawing circles, that derives from a simple scheme to an efficient one

• Midpoint Circle Algorithm in several programming languages

de:Rasterung von Kreisen#Midpoint-Algorithmus