Rastern von Kreisen

Unter der Rasterung von Kreisen versteht man in der Computergrafik das Zeichnen (Rastern) eines Kreises auf dem Punktraster einer Rastergrafik oder eines Raster-Grafikgeräts durch Einfärben entsprechender Pixel. Es gibt hierfür sowohl Algorithmen zur einfarbigen Rasterung als auch zum Antialiasing.

Einfarbige Rasterung

Einfache Algorithmen

Eine einfache Möglichkeit, Kreise zu zeichnen, basiert auf der Parameterdarstellung von Kreisen:

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

Für jedes $\varphi$ zwischen 0 und 2π werden in bestimmten Abständen die (x, y)-Koordinaten gemäß dieser Formel berechnet und die entsprechenden Pixel eingefärbt. Kreise mit beliebigem Mittelpunkt können durch eine einfache Koordinatenverschiebung gezeichnet werden. Diese Methode ist sehr ineffizient, da sie die langsamen Cosinus- und Sinusfunktionen verwendet.

Eine andere Möglichkeit ist, die Koordinatengleichung des Kreises (x² + y² = r²) nach y aufzulösen:

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

Hier wird für jedes x zwischen 0 und r y berechnet. Diese Methode ist wegen der Wurzel ebenfalls ineffizient und lässt zudem für x nahe r Lücken.

Die soeben beschriebenen Algorithmen können durch die Nutzung von Symmetrieeigenschaften verbessert werden. Tatsächlich besitzt jedes Pixel auf dem Kreis sieben weitere symmetrische Pixel, die sich trivial berechnen lassen. Es genügt demnach, nur einen Achtelkreis zu zeichnen und anstatt nur einem Pixel folgende acht Pixel einzufärben:

(x, y)

(y, x)

(y, −x)

(x, −y)

(−x, −y)

(−y, −x)

(−y, x)

(−x, y)

Diese Methode löst außerdem das Problem der Lücken bei der eben beschriebenen Methode.

Methode von Metzger

Wahl des nächsten Pixels bei der Methode von Metzger

Eine frühe Methode zum Rastern von Kreisen wurde 1969 von Metzger vorgestellt.^[1] Hierbei wird ausgehend vom aktuellen Pixel der Koordinaten $(x_i,\,y_i)$ zwischen den beiden Pixeln, die sich außerhalb $(x_i,\,y_i+1)$ und innerhalb $(x_i-1,\,y_i+1)$ des Kreises befinden, gewählt. Wenn R_I der Abstand des inneren und R_A der Abstand des äußeren Pixels zum Kreismittelpunkt ist, so wird dasjenige Pixel gewählt, dessen Abstand näher am Kreisradius liegt. Beispielsweise wird das äußere Pixel gewählt, falls (r − R_I) > (R_A − r).

Unter Anwendung des Satzes des Pythagoras lässt sich letztere Bedingung folgendermaßen umformen:

$2r > \sqrt{x_i^2+(y_i+1)^2} + \sqrt{(x_i-1)^2+(y_i+1)^2}$.

Mit Hilfe der Dreiecksungleichung, die hier für alle r > 1,25 gültig ist, ergibt sich:

4r² > (x_i − 1)² + (2y_i + 2)².

Zur Umsetzung der Quadrierungen sind allerdings langsame Multiplikationen erforderlich. Diese würden sich durch die inkrementelle Berechnung der Bedingung vermeiden lassen, Metzger formulierte allerdings keine derartige Lösung.

Methode von Horn

Rastern eines Kreises mit der Methode von Horn

Ein Algorithmus, der nur Additionen und Subtraktionen verwendet, wurde 1976 von Horn vorgestellt.^[2] Bei Horns Verfahren befinden sich die einzufärbenden Pixel innerhalb eines ein Pixel breiten Bereichs um den idealen Kreisbogen. Wenn $(x_i,\,y_i)$ das aktuelle Pixel ist, dann wird die Position des direkt darüberliegenden Pixels $(x_i,\,y_i+1)$ mit dem rechten Rand dieses Bereichs verglichen. Liegt es innerhalb des Bereichs, wird dieses Pixel gewählt. Liegt das Pixel außerhalb, so wird das links liegende Pixel $(x_i-1,\,y_i+1)$ gewählt. Auf letzteren Fall lässt sich unter Einführung der Kontrollvariable d folgendermaßen testen:

$\textstyle d_i = (x_i-\frac{1}{2})^2+y_i^2-r^2 > 0$.

Ein inkrementeller Algorithmus ergibt sich durch die Betrachtung der Differenz d_{i + 1} − d_i bei beiden möglichen Fällen. Bei jedem Schritt wird d um 2y_i + 1 erhöht; wenn das linke Pixel gewählt wird, subtrahiert man 2x_i − 2. Der Anfangswert der Kontrollvariable beträgt $\textstyle -r+\frac{1}{4}$, kann aber für Kreise mit ganzzahligen Mittelpunkten und Radien auf − r gerundet werden.

Der komplette Algorithmus lautet damit:

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

Midpoint-Algorithmus

Wahl des nächsten Pixels beim Midpoint-Algorithmus

1964 und 1977 stellte Bresenham einen weiteren Algorithmus vor^[3][4][5] (siehe auch Bresenham-Algorithmus). Ähnlich wie Metzger wählt er Pixel auf der Basis ihrer Entfernung zum Kreismittelpunkt aus. Ein einfacherer, äquivalenter Algorithmus bedient sich der Midpoint-Formulierung, bei der der Mittelpunkt zwischen den beiden nächsten Pixeln betrachtet wird.^[6]

Der Midpoint-Algorithmus rastert den Kreisbogen ausgehend vom Pixel mit größter y-Koordinate. Ausgegangen wird von einer impliziten Form der Koordinatengleichung des Kreises:

F(x,y) = x² + y² − r².

F ist 0 auf dem Kreis, positiv außerhalb und negativ innerhalb des Kreises. Bei jedem Schritt wird zwischen dem „östlichen“ und dem „südöstlichen“ Pixel gewählt. In diese Gleichung werden die Koordinaten des Mittelpunkts eingesetzt:

$\textstyle d_i = F(x_i+1,y_i-\frac{1}{2}) = (x_i+1)^2 + (y_i-\frac{1}{2})^2 - r^2$.

Bei d_i < 0 wird Pixel O gewählt, im anderen Fall SO.

Auch hier ist ein inkrementeller Algorithmus möglich. Die Änderung der Kontrollvariable hängt von der Wahl des Pixels ab:

$\textstyle \Delta_O$		$\textstyle = d_{i+1} - d_i = F(x_i+2, y_i-\frac{1}{2}) - d_i = 2x_i+3$
$\textstyle \Delta_{SO}$		$\textstyle = d_{i+1} - d_i = F(x_i+2, y_i-\frac{3}{2}) - d_i = 2x_i-2y_i+5$.

Der Anfangswert der Kontrollvariable beträgt $\textstyle \frac{5}{4} - r$. Für die ganzzahlige Rasterung lässt sich der Bruch vermeiden, indem von d $\textstyle \frac{1}{4}$ abgezogen wird. Dadurch ändert sich der Anfangswert in 1 − r und der Vergleich d_i < 0 in $\textstyle d_i &amp;amp;lt; -\frac{1}{4}$, welcher sich durch Rundung in d_i < 0 umwandeln lässt.

Der resultierende Algorithmus ist Horns Methode sehr ähnlich.

Im Gegensatz zum Midpoint-Algorithmus für Linien (siehe Rasterung von Linien) sind Δ_O und Δ_SO nicht konstant, sondern hängen von der aktuellen Position ab. Es ist daher möglich, Differenzen „zweiter Ordnung“ zu betrachten, bei der Δ_O und Δ_SO selbst inkrementell berechnet werden. Mit diesem Algorithmus wird die Initialisierung aufwändiger; innerhalb der Schleife spart man im Falle der Wahl von SO eine Addition. Auf dieses Verfahren hat IBM, Bresenhams damaliger Arbeitgeber, in mehreren Staaten Softwarepatente eingereicht, darunter auch 1982 beim Europäischen Patentamt.^[7]

Sonstiges

Die Anzahl der arithmetischen Operationen bei Bresenhams Algorithmus lässt sich weiter verringern.^[8] Es wurden noch andere, schnellere Methoden zur Rasterung vorgestellt, die mehrere Pixel auf einmal zeichnen. Wu und Rokne stellten 1987 ein Doppelschrittverfahren vor, bei dem je Schleifendurchlauf zwei Pixel eingefärbt werden.^[9] Yao und Rokne zeigten 1995, wie auch bei der Rasterung von Kreisen ganze Pixelreihen auf einmal eingefärbt werden können.^[10]

Es gibt mehrere Methoden, gefüllte Kreise zu zeichnen. Eine triviale Methode besteht darin, beim Zeichnen eines Oktanten nicht nur ein Pixel pro Schleifendurchlauf, sondern alle Pixel einer Reihe zu zeichnen. Durch die Symmetrie wird der gesamte Kreis gefüllt.^[11] Ebenfalls möglich ist das Zeichnen einer minimalen Anzahl von Rechtecken; Nachteil ist hier, dass viele Pixel mehrmals eingefärbt werden.^[12]

Anstatt einen Kreis durch seinen Mittelpunkt und seinen Radius zu definieren, ist es auch möglich, einen Mittelpunkt und einen beliebigen auf dem Kreis liegenden Punkt anzugeben. Dabei muss aber beachtet werden, dass bestimmte Punkte des Rasters gar nicht auf einem Kreis mit ganzzahligem Radius liegen. Algorithmen, die Kreise nach diesem Schema zeichnen, müssen auf ungültige Anfangspunkte testen.^[13]

Antialiasing

Field stellte eine Methode zum Antialiasing von Kreisen mittels ungewichteter Flächenabtastung vor, bei der der Kreis für jedes Pixel mit einem Trapez angenähert wird.^[14] Der Flächenanteil des Trapezes innerhalb eines Quadrats mit einem Pixel Kantenlänge bestimmt den Farbwert. Dank inkrementeller Berechnung benötigt der Algorithmus nur Multiplikationen und Additionen.

Auch der Gupta-Sproull-Algorithmus für Linien kann auf Kreise erweitert werden.^[15] Im Gegensatz zu Linien hängt der Wert des Glättungskerns nicht nur von der Distanz zur Kurve, sondern auch vom Radius ab. Daher sind verschiedene Tabellen für verschiedene Radien notwendig. Für größere Kreise kann eine einzige Tabelle verwendet werden, bei der die Krümmung vernachlässigt wird.

Literatur

• James D. Foley u. a.: Computer Graphics: Principles and Practice in C. Addison-Wesley, Reading (Massachusetts) 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? IEEE Computer Graphics and Applications 7, 8 (August 1987): 39–44, ISSN 0272-1716

Einzelnachweise

1. ↑ Richard A. Metzger: Computer generated graphic segments in a raster display. In AFIPS Conference Proceedings Vol. 34, Spring Joint Computer Conference 1969: 161–172. AFIPS Press, Montvale 1969
2. ↑ B. K. P. Horn: Circle Generators for Display Devices. Computer Graphics and Image Processing 5, 2 (June 1976): 280–288, ISSN 0146-664X (PDF, 580 KB)
3. ↑ Jack Bresenham: A linear, incremental algorithm for digitally plotting circles. Technical Report TR02.286, IBM General Products Division, San José (Kalifornien), 27. Januar 1964
4. ↑ Jack Bresenham: A linear algorithm for incremental digital display of circular arcs. Communications of the ACM 20, 2 (1977): 100–106, ISSN 0001-0782
5. ↑ Zur Geschichte der Veröffentlichung dieses Algorithmus siehe http://tog.acm.org/resources/RTNews/html/rtnv20n1.html#art4
6. ↑ James D. Foley u. a.: Computer Graphics: Principles and Practice in C, S. 83–87
7. ↑ USA: US4371933 (US Patent Office), Japan: JP57064778, Europa: EP0049360 (Europäisches Patentamt)
8. ↑ Yevgeni P. Kuzmin: An Efficient Circle-Drawing Algorithm. Computer Graphics Forum 9, 4 (December 1990): 333–336, ISSN 0167-7055
9. ↑ X. Wu, J. G. Rokne: Double-Step Incremental Generation of Lines and Circles. Computer Vision, Graphics, and Image Processing 37, 3 (March 1987): 331–344, ISSN 0734-189X
10. ↑ Chengfu Yao, Jon G. Rokne: Hybrid Scan-Conversion of Circles. IEEE Transactions on Visualization and Computer Graphics 1, 4 (December 1995): 311–318, ISSN 1077-2626
11. ↑ M. Doros: Algorithms for Generation of Discrete Circles, Rings, and Disks. Computer Graphics and Image Processing 10 (1979): 366–371
12. ↑ N. I. Badler: Disk Generators for a Raster Display Device. Computer Graphics and Image Processing 6 (1977): 589–593
13. ↑ Marek Doros: On Some Properties of the Generation of Discrete Circular Arcs on a Square Grid. Computer Vision, Graphics, and Image Processing 28, 3 (December 1984): 377–383
14. ↑ D. Field: Algorithms for Drawing Anti-Aliased Circles and Ellipses. Computer Vision, Graphics, and Image Processing 33, 1 (January 1986): 1–15
15. ↑ James D. Foley u. a.: Computer Graphics: Principles and Practice in C, S. 969–971