Grid of circles

Under the screening of circles is understood in the computer graphics drawing ( rasters ) of a circle at the point grid of a raster image or a raster graphic device by coloring the appropriate pixels . There are algorithms for monochrome rasterization as well as for anti-aliasing .

Monochrome halftone

Simple algorithms

A simple way to draw circles is based on parametric drawing of circles:

${\displaystyle (x,\,y)=(r\cos \varphi ,\,r\sin \varphi )}$

For each between 0 and the ( x , y ) -coordinates are calculated according to this formula at certain intervals and the corresponding pixels are colored. Circles with any center point can be drawn by simply shifting coordinates. This method is very inefficient because it uses the slow cosine and sine functions. ${\displaystyle \varphi }$ ${\displaystyle 2\pi }$

Another possibility is to solve the coordinate equation of the circle ( ) for : ${\displaystyle x^{2}+y^{2}=r^{2}}$ ${\displaystyle y}$

${\displaystyle y=\pm {\sqrt {r^{2}-x^{2}}}}$

Here is calculated for each between and . This method is also inefficient because of the root and also leaves for close gaps. ${\displaystyle x}$ ${\displaystyle 0}$ ${\displaystyle r}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle r}$

The algorithms just described can be improved by using symmetry properties. In fact, every pixel on the circle has seven other symmetrical pixels that can be calculated trivially. It is therefore sufficient to draw only an eighth circle and color the following eight pixels instead of just one pixel:

( x , y )

( y , x )

( y , - x )

( x , - y )

(- x , - y )

(- y , - x )

(- y , x )

(- x , y )

This method also solves the problem of gaps in the method just described.

Method of butcher

Choice of the closest pixel in Metzger's method

An early method of rasterizing circles was introduced by Metzger in 1969. Starting from the current pixel, the coordinates between the two pixels that are outside and inside the circle are selected. If the distance between the inner and the outer pixel is to the center of the circle, the pixel is selected whose distance is closer to the radius of the circle. For example, the outer pixel is chosen, if . ${\displaystyle (x_{i},\,y_{i})}$ ${\displaystyle (x_{i},\,y_{i}+1)}$ ${\displaystyle (x_{i}-1,\,y_{i}+1)}$ ${\displaystyle R_{I}}$ ${\displaystyle R_{A}}$ ${\displaystyle (r-R_{I})>(R_{A}-r)}$

Using the Pythagorean Theorem, the latter condition can be transformed as follows:

${\displaystyle 2r>{\sqrt {x_{i}^{2}+(y_{i}+1)^{2}}}+{\sqrt {(x_{i}-1)^{2}+(y_{i}+1)^{2}}}}$.

With the help of the triangle inequality , which is valid here for all , we get: ${\displaystyle r>1{,}25}$

${\displaystyle 4r^{2}>(x_{i}-1)^{2}+(2y_{i}+2)^{2}}$.

However, slow multiplications are required to implement the squarings . These could be avoided by calculating the condition incrementally; However, Metzger formulated no such solution.

Horn's method

Rasterize a circle using Horn's method

An algorithm using only additions and subtractions was introduced by Horn in 1976. In Horn's method, the pixels to be colored are located within a one-pixel-wide area around the ideal circular arc. If is the current pixel, then the position of the pixel immediately above is compared to the right edge of that area. If it is within the range, that pixel is selected. If the pixel is outside, the pixel on the left is selected. The latter case can be tested as follows by introducing the control variable: ${\displaystyle (x_{i},\,y_{i})}$ ${\displaystyle (x_{i},\,y_{i}+1)}$ ${\displaystyle (x_{i}-1,\,y_{i}+1)}$ ${\displaystyle d}$

${\displaystyle \textstyle d_{i}=(x_{i}-{\frac {1}{2}})^{2}+y_{i}^{2}-r^{2}>0}$.

An incremental algorithm results from considering the difference in both possible cases. At each step, is to increase; if the left pixel is chosen, one subtracts . The initial value of the control variable is , but can be rounded up for circles with integer centers and radii . ${\displaystyle d_{i+1}-d_{i}}$ ${\displaystyle d}$ ${\displaystyle 2y_{i}+1}$ ${\displaystyle 2x_{i}-2}$ ${\displaystyle \textstyle -r+{\frac {1}{4}}}$ ${\displaystyle -r}$

The complete algorithm is thus:

d = −r
x = r
y = 0
Wiederhole bis y > x
    Pixel (x, y) sowie symmetrische Pixel einfärben
    d = d + 2×y + 1
    y = y + 1
    Wenn d > 0
        d = d - 2×x + 2
        x = x - 1

Optimization for the step : If you swap the line with the one above, you can save the operation . So if you previously decreased by 1, this is automatically included. From is deducted in both versions. 1 In spite of swapping the lines, the end result remains the same. For changing now but something like this: Instead of using the simple is in this line with the reduced by 1 worked with . From is now deducted: Remove brackets, corresponds to: So you can see that the same value is calculated as in the unoptimized version. This shows that the end result does not algorithmically differ from the unoptimized version. ${\displaystyle d>0}$
${\displaystyle x=x-1}$ ${\displaystyle +2}$
${\displaystyle x}$ ${\displaystyle +2}$
${\displaystyle x}$ ${\displaystyle x}$
${\displaystyle d}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle (x-1)}$ ${\displaystyle d}$ ${\displaystyle 2*(x-1)=(2x-2)}$

${\displaystyle d=d-(2x-2)}$



${\displaystyle d=d-2x+2}$

${\displaystyle d}$

Optimized it looks like this:

d = −r
x = r
y = 0
Wiederhole bis y > x
    Pixel (x, y) sowie symmetrische Pixel einfärben
    d = d + 2×y + 1
    y = y + 1
    Wenn d > 0
        x = x - 1
        d = d - 2×x

Midpoint algorithm

Choice of the next pixel in the midpoint algorithm

In 1964 and 1977 Bresenham presented another algorithm (see also Bresenham algorithm ). Similar to Metzger, he selects pixels based on their distance from the center of the circle. A simpler, equivalent algorithm makes use of the midpoint formulation, in which the midpoint between the next two pixels is considered.

The midpoint algorithm rasterizes the circular arc starting from the pixel with the largest y coordinate. An implicit form of the coordinate equation of the circle is assumed:

${\displaystyle F(x,y)=x^{2}+y^{2}-r^{2}}$.

${\displaystyle F}$is 0 on the circle, positive outside and negative inside the circle. At each step, a choice is made between the "east" and the "south-east" pixel. The coordinates of the center are inserted into this equation:

${\displaystyle \textstyle d_{i}=F(x_{i}+1,y_{i}-{\frac {1}{2}})=(x_{i}+1)^{2}+(y_{i}-{\frac {1}{2}})^{2}-r^{2}}$.

At pixel O is selected, in the other case SO. ${\displaystyle d_{i}<0}$

An incremental algorithm is also possible here. The change in the control variable depends on the choice of pixel:

${\displaystyle \textstyle \Delta _{O}=d_{i+1}-d_{i}=F(x_{i}+2,y_{i}-{\frac {1}{2}})-d_{i}=2x_{i}+3}$

${\displaystyle \textstyle \Delta _{SO}=d_{i+1}-d_{i}=F(x_{i}+2,y_{i}-{\frac {3}{2}})-d_{i}=2x_{i}-2y_{i}+5}$.

The initial value of the control variable is . For integer rasterization, the fraction can be avoided by subtracting from d . This changes the initial value to and the comparison to , which can be converted to by rounding . ${\displaystyle \textstyle {\frac {5}{4}}-r}$ ${\displaystyle \textstyle {\frac {1}{4}}}$ ${\displaystyle 1-r}$ ${\displaystyle d_{i}<0}$ ${\displaystyle \textstyle d_{i}<-{\frac {1}{4}}}$ ${\displaystyle d_{i}<0}$

The resulting algorithm is very similar to Horn's method.

In contrast to the midpoint algorithm for lines (see rasterization of lines ) and are not constant, but depend on the current position. It is therefore possible to consider “second order” differences in which and are calculated incrementally. With this algorithm the initialization becomes more complex; If SO is selected, an addition is saved within the loop . In this process has IBM , Bresenham's employer at the time, in several states software patents filed, including 1,982 at the European Patent Office . ${\displaystyle \Delta _{O}}$ ${\displaystyle \Delta _{SO}}$ ${\displaystyle \Delta _{O}}$ ${\displaystyle \Delta _{SO}}$

Others

The number of arithmetic operations in Bresenham's algorithm can be further reduced. Other, faster methods of rasterizing that draw multiple pixels at once were also introduced. In 1987, Wu and Rokne presented a two-step process in which two pixels are colored per loop pass. Yao and Rokne showed in 1995 how entire rows of pixels can be colored at once when circles are rasterized.

There are several methods of drawing filled circles. A trivial method is to draw an octant not just one pixel per loop, but all pixels in a row. The whole circle is filled by the symmetry. It is also possible to draw a minimum number of rectangles; The disadvantage here is that many pixels are colored several times.

Instead of defining a circle by its center point 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 an integral radius. Algorithms that draw circles according to this scheme must test for invalid starting points.

Antialiasing

Field introduced a method for antialiasing circles using unweighted area scanning, in which the circle is approximated with a trapezoid for each pixel . The area portion of the trapezoid within a square with one pixel edge length determines the color value. Thanks to the incremental calculation, the algorithm only needs multiplications and additions.

The Gupta-Sproull algorithm for lines can also be extended to circles. In contrast to lines, the value of the smoothing kernel depends not only on the distance to the curve, but also on the radius. Therefore different tables are necessary for different radii. A single table can be used for larger circles, neglecting the curvature.

literature

• James D. Foley et al. A .: Computer Graphics: Principles and Practice in C . Addison-Wesley, Reading MA 1995, ISBN 978-0-201-84840-3 .
• David F. Rogers: Procedural Elements for Computer Graphics . WCB / McGraw-Hill, Boston 1998, ISBN 978-0-07-053548-0 .
• James F. Blinn : How Many Ways Can You Draw a Circle? In: IEEE Computer Graphics and Applications , 7, 8 (August 1987), pp. 39-44, ISSN  0272-1716

Individual evidence

1. ^ Richard A. Metzger: Computer generated graphic segments in a raster display. In: AFIPS Conference Proceedings . Vol. 34, Spring Joint Computer Conference 1969. pp. 161-172. AFIPS Press, Montvale 1969
2. ^ BKP Horn: Circle Generators for Display Devices . In: Computer Graphics and Image Processing , 5, 2, June 1976, pp. 280–288, ISSN  0146-664X , csail.mit.edu (PDF; 580 kB)
3. ^ Jack Bresenham: A linear, incremental algorithm for digitally plotting circles. Technical Report TR02.286, IBM General Products Division, San José CA, January 27, 1964
4. ^ Jack Bresenham: A linear algorithm for incremental digital display of circular arcs . In: Communications of the ACM , 20, 2, 1977, pp. 100-106, ISSN  0001-0782
5. ↑ For the history of the publication of this algorithm see tog.acm.org ( Memento of the original of December 23, 2007 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
6. ↑ James D. Foley et al. A .: Computer Graphics: Principles and Practice in C . Pp. 83-87
7. ↑ Patent US4371933 . ‌
8. ↑ Patent JP57064778 . ‌
9. ↑ Patent EP0049360 . ‌
10. ^ Yevgeni P. Kuzmin: An Efficient Circle-Drawing Algorithm. Computer Graphics Forum 9, 4 (December 1990): 333-336, ISSN  0167-7055
11. ↑ X. Wu, JG Rokne: Double-Step Incremental Generation of Lines and Circles . In: Computer Vision, Graphics, and Image Processing , 37, 3, March 1987, pp. 331-344, ISSN  0734-189X
12. ↑ Chengfu Yao, Jon G. Rokne: Hybrid Scan-Conversion of Circles . In: IEEE Transactions on Visualization and Computer Graphics , 1, 4, December 1995, pp. 311-318, ISSN  1077-2626
13. ^ M. Doros: Algorithms for Generation of Discrete Circles, Rings, and Disks . In: Computer Graphics and Image Processing , 10, 1979, pp. 366-371
14. ↑ NI Badler: Disk Generators for a Raster Display Device . In: Computer Graphics and Image Processing , 6, 1977, pp. 589-593
15. ^ Marek Doros: On Some Properties of the Generation of Discrete Circular Arcs on a Square Grid . In: Computer Vision, Graphics, and Image Processing , 28, 3, December 1984, pp. 377-383
16. ↑ D. Field: Algorithms for Drawing Anti-Aliased Circles and Ellipses . In: Computer Vision, Graphics, and Image Processing , 33, 1, January 1986, pp. 1-15
17. ↑ James D. Foley et al. A .: Computer Graphics: Principles and Practice in C . Pp. 969-971