Rasterung von Kreisen
# Rasterung 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\pi$ 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^{2}+y^{2}=r^{2}$) 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

Eine frühe Methode zum Rastern von Kreisen wurde 1969 von Metzger vorgestellt. 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^{2}>(x_{i}-1)^{2}+(2y_{i}+2)^{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

Ein Algorithmus, der nur Additionen und Subtraktionen verwendet, wurde 1976 von Horn vorgestellt. 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:
Optimierung für den Schritt $d>0$: Wenn man die Zeile $x=x-1$ mit der darüberliegenden vertauscht, kann man die Operation $+2$ einsparen. Wenn zuvor also $x$ um 1 erniedrigt wurde, ist das $+2$ automatisch schon enthalten. Von $x$ wird in beiden Versionen 1 abgezogen. Trotz Vertauschung der Zeilen bleibt also das Endergebnis für $x$ gleich. Für $d$ ändert sich jetzt aber etwas: Statt mit dem einfachen $x$ wird in dieser Zeile mit dem um 1 reduzierten $x$ gearbeitet, mit $(x-1)$. Von $d$ wird jetzt $2*(x-1)=(2x-2)$ abgezogen:
$d=d-(2x-2)$
Klammern entfernen, entspricht:
$d=d-2x+2$
Man kann also sehen, dass für $d$ der gleiche Wert, wie in der unoptimierten Version errechnet wird. Damit ist gezeigt, dass das Endergebnis sich algorithmisch nicht von der unoptimierten Version unterscheidet.
Optimiert sieht das dann so aus:

### Midpoint-Algorithmus

1964 und 1977 stellte Bresenham einen weiteren Algorithmus vor (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.
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^{2}+y^{2}-r^{2}$.
$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}=d_{i+1}-d_{i}=F(x_{i}+2,y_{i}-{\frac {1}{2}})-d_{i}=2x_{i}+3$
    $\textstyle \Delta _{SO}=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}<-{\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 $\Delta _{O}$ und $\Delta _{SO}$ nicht konstant, sondern hängen von der aktuellen Position ab. Es ist daher möglich, Differenzen „zweiter Ordnung“ zu betrachten, bei der $\Delta _{O}$ und $\Delta _{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.
Eine mögliche Implementierung des Midpoint-Algorithmus vom Bresenham in der Programmiersprache C# zeigt das folgende Beispiel:

### Methode von Jesko

Die Algorithmik ist weitestgehend schon erklärt, jedoch gibt es noch weitere Optimierungen.
Die neue vorgestellte Methode kommt mit nur 5 Rechenoperationen pro Schritt (für 8 Pixel) aus und ist damit gerade für niedrigperformante Systeme bestens geeignet. In der "Wenn" Operation wird nur das Vorzeichen geprüft (positiv? Ja oder Nein) und es gibt eine Variablenzuweisung, was auch nicht als Rechenoperation gilt. Die Initialisierung in der ersten Zeile (Geschiebe um 4 Bits nach rechts) ist nur der Schönheit geschuldet und nicht wirklich nötig.
Also bleibt (zählbare Operationen in der Hauptschleife):
* Der Vergleich x >= y (gilt als Subtraktion: x - y >= 0 )
* y++
* t1 + y
* t1 - x
* x--
Operationen: 5
Im Folgenden eine einfache Beispielimplementierung in C. Einfach als "main.c" zu speichern und zu kompilieren. Zur Kontrolle werden die Koordinaten der gesetzten Pixel ausgegeben.

### Sonstiges

Die Anzahl der arithmetischen Operationen bei Bresenhams Algorithmus lässt sich weiter verringern. 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. Yao und Rokne zeigten 1995, wie auch bei der Rasterung von Kreisen ganze Pixelreihen auf einmal eingefärbt werden können.
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. Ebenfalls möglich ist das Zeichnen einer minimalen Anzahl von Rechtecken; Nachteil ist hier, dass viele Pixel mehrmals eingefärbt werden.
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.

## 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. 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. 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.