Midpoint circle algorithm
Under the screening of circles is understood in computer graphics drawing ( rasterizing ) a circle on the grid point of a raster image or a raster graphics device by coloring corresponding pixels. There is permissible for both algorithms for monochrome raster as well as for anti-aliasing.
Monochrome screening
Simple algorithms
An easy way to draw circles, based on the parametric representation of circles:
For each 0 to the (x, y) coordinates is calculated at predetermined intervals in accordance with this formula, and the respective colored pixel. Circuits with arbitrary center can be drawn by a simple coordinate shift. This method is very inefficient because it uses the slow cosine and sine functions.
Another possibility is to coordinate the equation of the circle () solved for:
Here, for each between and calculated. This method is due to the root also inefficient and allows for close gaps.
The algorithm just described may be improved by the use of symmetry properties. In fact, each pixel has on the circle seven more symmetrical pixels, which can be calculated trivially. It is sufficient, therefore, only to draw eighth circle and instead of just one pixel to color the following eight pixels:
This method also solves the problem of gaps in the method just described.
Method of Metzger
An early method for screening of circles was presented by Metzger in 1969. Here, starting from the current pixel of coordinates between the two pixels that are outside and inside the circle selected. If the distance between the inner and outer distance of the pixel to the center of the circle, so the one pixel is selected, the distance of which is closer to the radius of the circle. For example, the exterior pixel is selected, if necessary.
Using the theorem of Pythagoras can reshape latter condition follows:
Using the triangle inequality, which is valid for all here, we have:
To implement the squaring however slow multiplications are required. These would be eliminated by the incremental computation of the condition, however, Metzger did not formulate such a solution.
Method of Horn
An algorithm using only additions and subtractions, was introduced in 1976 by horn. In Horns process the inked pixels are within a one pixel wide region around the ideal circular arc. If the current pixel is, then the position of the pixel directly above it with the right edge of this region is compared. It is within the area, that pixel is selected. If the pixel is outside, so the left- pixels is selected. In the latter case can be with the introduction of the control variable test as follows:
An incremental algorithm is due to the consideration of the difference in the two possible cases. At each step shall be increased by; if the left pixel is selected, you subtract. Is the initial value of the control variable, but can be rounded for circles with integer center points and radii.
The complete algorithm is thus:
D = -r x = r y = 0 Repeat until y > x Pixel (x, y) and symmetric pixel to color d = d 2 × y 1 y = y 1 If d> 0 d = d - 2 × x 2 x = x - 1 Midpoint Algorithm
1964 and 1977, Bresenham another algorithm (see also Bresenham algorithm). Similar to butcher it selects pixels on the basis of their distance from the circle center. A simpler, equivalent algorithm uses the midpoint formulation, wherein the center is considered between the next two pixels.
The midpoint algorithm scans the arc starting from the pixel with the greatest y -coordinate. The starting point is an implicit form of the Cartesian equation of the circle:
Is 0 on the circle, positive outside and negative inside the circle. At each step between the " east " and " south-east " is selected pixels. In this equation, the coordinates of the center are used:
In pixel O is selected, otherwise SO.
Again, an incremental algorithm is possible. The change of the control variable is dependent on the choice of starting pixel:
Is the initial value of the control variable. For the integer raster, the break can be avoided by withdrawing from d. Thus, the initial value and the comparison of changes in which can be explained by rounding to convert.
The resulting algorithm is very similar horn method.
(See rasterization of lines) are in contrast to the midpoint algorithm for lines and not constant, but depend on the current position. It is therefore possible to look at differences " second order " are in and even calculated incrementally. With this algorithm, the initialization is complex; inside the loop you save an addition in the case of election of SO. In this method, IBM, Bresenham's employer at the time, filed software patents in several countries, including in 1982 the European Patent Office.
Others
The number of arithmetic operations in Bresenham's algorithm can be further reduced. There are other, faster methods have been presented for screening which draw more than one pixel at a time. Wu and Rokne presented in 1987 before a double step process, will be colored in which each pass through the loop two pixels. Yao and Rokne showed 1995 as whole rows of pixels can be colored at once and in the screening of circles.
There are several methods to draw filled circles. A trivial method is to draw not only one pixel per time through the loop, but all pixels of a row when drawing a octants. The symmetry of the entire circuit is filled. It is also possible to draw a minimum number of rectangles; Disadvantage here is that many pixels are repeatedly dyed.
Instead of defining a circle by its center and its radius, it is also possible to specify a center point and any point lying on the circle. However, it must be noted that certain points of the grid do not lie on a circle with integer radius. Algorithms that draw circles according to this scheme must test for invalid start points.
Antialiasing
Field presented a method for antialiasing of circles by means of unweighted area sampling, in which the circle for each pixel is approximated by a cone. The surface portion of the trapezoid within a square with a pixel edge length determines the color value. Thanks incremental calculation, the algorithm requires only multiplications and additions.
And the Gupta, Sproull algorithm for lines can be extended to circuits. In contrast to the value of the smoothing kernel lines depends not only on the distance to the curve, but also on the radius. Therefore, various tables for different radii are required. For larger circuits, a single table may be used, in which the curvature is neglected.