Rasterung von Kreisen

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

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

Für jedes ${\displaystyle \varphi }$ zwischen 0 und ${\displaystyle 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 (${\displaystyle x^{2}+y^{2}=r^{2}}$) nach ${\displaystyle y}$ aufzulösen:

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

Hier wird für jedes ${\displaystyle x}$ zwischen ${\displaystyle 0}$ und ${\displaystyle r}$ ${\displaystyle y}$ berechnet. Diese Methode ist wegen der Wurzel ebenfalls ineffizient und lässt zudem für ${\displaystyle x}$ nahe ${\displaystyle 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:

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

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 ${\displaystyle (x_{i},\,y_{i})}$ zwischen den beiden Pixeln, die sich außerhalb ${\displaystyle (x_{i},\,y_{i}+1)}$ und innerhalb ${\displaystyle (x_{i}-1,\,y_{i}+1)}$ des Kreises befinden, gewählt. Wenn ${\displaystyle R_{I}}$ der Abstand des inneren und ${\displaystyle 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 ${\displaystyle (r-R_{I})>(R_{A}-r)}$.

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

${\displaystyle 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 ${\displaystyle r>1{,}25}$ gültig ist, ergibt sich:

${\displaystyle 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.

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 ${\displaystyle (x_{i},\,y_{i})}$ das aktuelle Pixel ist, dann wird die Position des direkt darüberliegenden Pixels ${\displaystyle (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 ${\displaystyle (x_{i}-1,\,y_{i}+1)}$ gewählt. Auf letzteren Fall lässt sich unter Einführung der Kontrollvariable ${\displaystyle d}$ folgendermaßen testen:

${\displaystyle \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 ${\displaystyle d_{i+1}-d_{i}}$ bei beiden möglichen Fällen. Bei jedem Schritt wird ${\displaystyle d}$ um ${\displaystyle 2y_{i}+1}$ erhöht; wenn das linke Pixel gewählt wird, subtrahiert man ${\displaystyle 2x_{i}-2}$. Der Anfangswert der Kontrollvariable beträgt ${\displaystyle \textstyle -r+{\frac {1}{4}}}$, kann aber für Kreise mit ganzzahligen Mittelpunkten und Radien auf ${\displaystyle -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

Optimierung für den Schritt ${\displaystyle d>0}$:
Wenn man die Zeile ${\displaystyle x=x-1}$ mit der darüberliegenden vertauscht, kann man die Operation ${\displaystyle +2}$ einsparen.
Wenn zuvor also ${\displaystyle x}$ um 1 erniedrigt wurde, ist das ${\displaystyle +2}$ automatisch schon enthalten.
Von ${\displaystyle x}$ wird in beiden Versionen 1 abgezogen. Trotz Vertauschung der Zeilen bleibt also das Endergebnis für ${\displaystyle x}$ gleich.
Für ${\displaystyle d}$ ändert sich jetzt aber etwas: Statt mit dem einfachen ${\displaystyle x}$ wird in dieser Zeile mit dem um 1 reduzierten ${\displaystyle x}$ gearbeitet, mit ${\displaystyle (x-1)}$. Von ${\displaystyle d}$ wird jetzt ${\displaystyle 2*(x-1)=(2x-2)}$ abgezogen:

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

Klammern entfernen, entspricht:

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

Man kann also sehen, dass für ${\displaystyle 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:

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

Wahl des nächsten Pixels beim Midpoint-Algorithmus

Iterationsweise Fortschreiten des Midpoint-Algorithmus (${\displaystyle r=23\mathrm {px} }$). Nur der grüne Achtelkreis wird tatsächlich berechnet; er wird einfach durch Spiegelung auf die anderen Achtelkreise kopiert.

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:

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

${\displaystyle 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:

${\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}}$.

Bei ${\displaystyle 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:

${\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}$.

Der Anfangswert der Kontrollvariable beträgt ${\displaystyle \textstyle {\frac {5}{4}}-r}$. Für die ganzzahlige Rasterung lässt sich der Bruch vermeiden, indem von d ${\displaystyle \textstyle {\frac {1}{4}}}$ abgezogen wird. Dadurch ändert sich der Anfangswert in ${\displaystyle 1-r}$ und der Vergleich ${\displaystyle d_{i}<0}$ in ${\displaystyle \textstyle d_{i}<-{\frac {1}{4}}}$, welcher sich durch Rundung in ${\displaystyle 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 ${\displaystyle \Delta _{O}}$ und ${\displaystyle \Delta _{SO}}$ nicht konstant, sondern hängen von der aktuellen Position ab. Es ist daher möglich, Differenzen „zweiter Ordnung“ zu betrachten, bei der ${\displaystyle \Delta _{O}}$ und ${\displaystyle \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.[7][8][9]

Eine mögliche Implementierung des Midpoint-Algorithmus vom Bresenham in der Programmiersprache C# zeigt das folgende Beispiel:[10]

public void DrawCircle(Color[,] image, int centerX, int centerY, int radius, Color color)
{
	int d = (5 - radius * 4) / 4; // Kontrollvariable
	int x = 0;
	int y = radius;
	do
	{
		// Prüft, ob das Pixel innerhalb der Grenzen des Bilds liegt und setzt gegebenenfalls ein Pixel in jedem Oktanten
		if (centerX + x >= 0 && centerX + x <= image.Width - 1 && centerY + y >= 0 && centerY + y <= image.Height - 1) image[centerX + x, centerY + y] = color; // 7. Oktant
		if (centerX + x >= 0 && centerX + x <= image.Width - 1 && centerY - y >= 0 && centerY - y <= image.Height - 1) image[centerX + x, centerY - y] = color; // 2. Oktant
		if (centerX - x >= 0 && centerX - x <= image.Width - 1 && centerY + y >= 0 && centerY + y <= image.Height - 1) image[centerX - x, centerY + y] = color; // 6. Oktant
		if (centerX - x >= 0 && centerX - x <= image.Width - 1 && centerY - y >= 0 && centerY - y <= image.Height - 1) image[centerX - x, centerY - y] = color; // 3. Oktant
		if (centerX + y >= 0 && centerX + y <= image.Width - 1 && centerY + x >= 0 && centerY + x <= image.Height - 1) image[centerX + y, centerY + x] = color; // 8. Oktant
		if (centerX + y >= 0 && centerX + y <= image.Width - 1 && centerY - x >= 0 && centerY - x <= image.Height - 1) image[centerX + y, centerY - x] = color; // 1. Oktant
		if (centerX - y >= 0 && centerX - y <= image.Width - 1 && centerY + x >= 0 && centerY + x <= image.Height - 1) image[centerX - y, centerY + x] = color; // 4. Oktant
		if (centerX - y >= 0 && centerX - y <= image.Width - 1 && centerY - x >= 0 && centerY - x <= image.Height - 1) image[centerX - y, centerY - x] = color; // 5. Oktant
		if (d < 0)
		{
			// Pixel O wählen
			d += 2 * x + 1;
		}
		else
		{
			// Pixel SO wählen
			d += 2 * (x - y) + 1;
			y--;
		}
		x++;
	}
	while (x <= y);
}

Die Algorithmik ist weitestgehend schon erklärt, jedoch gibt es noch weitere Optimierungen.

Die neue vorgestellte Methode[11] 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):

1. Der Vergleich x >= y (gilt als Subtraktion: x - y >= 0 )
2. y++
3. t1 + y
4. t1 - x
5. x--

Operationen: 5

t1 = r / 16
x = r
y = 0
Wiederhole solange x >= y
    Pixel (x, y) sowie symmetrische Pixel einfärben
    y = y + 1
    t1 = t1 + y
    t2 = t1 - x
    Wenn t2 >= 0
        t1 = t2
        x = x - 1

Im Folgenden eine einfache Beispielimplemntierung in "C". Einfach als "main.c" zu speichern und zu kompilieren. Zur Kontrolle werden die Koordinaten der gesetzten Pixel ausgegeben.

#include <stdio.h>

void
plot( int x, int y )
{
    printf( "x=%3d, y=%3d\n", x, y );
}

void
circle( int mx, int my, int r )
{
    int t1 = r / 16;
    int t2 = 0;
    int x  = r;
    int y  = 0;
    while ( x >= y )
    {
        plot( mx + x, my + y );
        plot( mx + x, my - y );
        plot( mx - x, my + y );
        plot( mx - x, my - y );
        plot( mx + y, my + x );
        plot( mx + y, my - x );
        plot( mx - y, my + x );
        plot( mx - y, my - x );
        y  = y + 1;
        t1 = t1 + y;
        t2 = t1 - x;
        if ( t2 >= 0 )
        {
            t1 = t2;
            x  = x - 1;
        }
    }
}

int
main()
{
    circle( 20, 30, 10 );
    return 0;
}

Die Anzahl der arithmetischen Operationen bei Bresenhams Algorithmus lässt sich weiter verringern.[12] 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.[13] Yao und Rokne zeigten 1995, wie auch bei der Rasterung von Kreisen ganze Pixelreihen auf einmal eingefärbt werden können.[14]

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.[15] Ebenfalls möglich ist das Zeichnen einer minimalen Anzahl von Rechtecken; Nachteil ist hier, dass viele Pixel mehrmals eingefärbt werden.[16]

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.[17]