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

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^{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

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

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:

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-Algorithmus

Wahl des nächsten Pixels beim Midpoint-Algorithmus

Iterationsweise Fortschreiten des Midpoint-Algorithmus (

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:

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.^[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);
}

Methode von Jesko

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):

Der Vergleich x >= y (gilt als Subtraktion: x - y >= 0 )
y++
t1 + y
t1 - x
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 Beispielimplementierung 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;
}

Sonstiges

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]

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.^[18] 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.^[19] 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.

Siehe auch

Literatur

James D. Foley u. 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), S. 39–44, ISSN 0272-1716

Einzelnachweise

↑ Richard A. Metzger: Computer generated graphic segments in a raster display. In: AFIPS Conference Proceedings. Vol. 34, Spring Joint Computer Conference 1969. S. 161–172. AFIPS Press, Montvale 1969
↑ B. K. P. Horn: Circle Generators for Display Devices. In: Computer Graphics and Image Processing, 5, 2, June 1976, S. 280–288, ISSN 0146-664X, csail.mit.edu (PDF; 580 kB)
↑ Jack Bresenham: A linear, incremental algorithm for digitally plotting circles. Technical Report TR02.286, IBM General Products Division, San José CA, 27. Januar 1964
↑ Jack Bresenham: A linear algorithm for incremental digital display of circular arcs. In: Communications of the ACM, 20, 2, 1977, S. 100–106, ISSN 0001-0782
↑ Zur Geschichte der Veröffentlichung dieses Algorithmus siehe tog.acm.org (Memento des Originals vom 23. Dezember 2007 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/tog.acm.org
↑ James D. Foley u. a.: Computer Graphics: Principles and Practice in C. S. 83–87
↑ Patent US4371933.‌
↑ Patent JP57064778.‌
↑ Patent EP0049360.‌
↑ Rosetta Code: Bitmap/Midpoint circle algorithm
↑ Zur Geschichte der Veröffentlichung dieses Algorithmus siehe https://schwarzers.com/algorithms
↑ Yevgeni P. Kuzmin: An Efficient Circle-Drawing Algorithm. Computer Graphics Forum 9, 4 (December 1990): 333–336, ISSN 0167-7055
↑ X. Wu, J. G. Rokne: Double-Step Incremental Generation of Lines and Circles. In: Computer Vision, Graphics, and Image Processing, 37, 3, March 1987, S. 331–344, ISSN 0734-189X
↑ Chengfu Yao, Jon G. Rokne: Hybrid Scan-Conversion of Circles. In: IEEE Transactions on Visualization and Computer Graphics, 1, 4, December 1995, S. 311–318, ISSN 1077-2626
↑ M. Doros: Algorithms for Generation of Discrete Circles, Rings, and Disks. In: Computer Graphics and Image Processing, 10, 1979, S. 366–371
↑ N. I. Badler: Disk Generators for a Raster Display Device. In: Computer Graphics and Image Processing, 6, 1977, S. 589–593
↑ 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, S. 377–383
↑ D. Field: Algorithms for Drawing Anti-Aliased Circles and Ellipses. In: Computer Vision, Graphics, and Image Processing, 33, 1, January 1986, S. 1–15
↑ James D. Foley u. a.: Computer Graphics: Principles and Practice in C. S. 969–971

[1] Richard A. Metzger: Computer generated graphic segments in a raster display. In: AFIPS Conference Proceedings. Vol. 34, Spring Joint Computer Conference 1969. S. 161–172. AFIPS Press, Montvale 1969

[2] B. K. P. Horn: Circle Generators for Display Devices. In: Computer Graphics and Image Processing, 5, 2, June 1976, S. 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, 27. Januar 1964

[4] Jack Bresenham: A linear algorithm for incremental digital display of circular arcs. In: Communications of the ACM, 20, 2, 1977, S. 100–106, ISSN 0001-0782

[5] Zur Geschichte der Veröffentlichung dieses Algorithmus siehe tog.acm.org (Memento des Originals vom 23. Dezember 2007 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/tog.acm.org

[6] James D. Foley u. a.: Computer Graphics: Principles and Practice in C. S. 83–87

[7] Patent US4371933.‌

[8] Patent JP57064778.‌

[9] Patent EP0049360.‌

[10] Rosetta Code: Bitmap/Midpoint circle algorithm

[11] Zur Geschichte der Veröffentlichung dieses Algorithmus siehe https://schwarzers.com/algorithms

[12] Yevgeni P. Kuzmin: An Efficient Circle-Drawing Algorithm. Computer Graphics Forum 9, 4 (December 1990): 333–336, ISSN 0167-7055

[13] X. Wu, J. G. Rokne: Double-Step Incremental Generation of Lines and Circles. In: Computer Vision, Graphics, and Image Processing, 37, 3, March 1987, S. 331–344, ISSN 0734-189X

[14] Chengfu Yao, Jon G. Rokne: Hybrid Scan-Conversion of Circles. In: IEEE Transactions on Visualization and Computer Graphics, 1, 4, December 1995, S. 311–318, ISSN 1077-2626

[15] M. Doros: Algorithms for Generation of Discrete Circles, Rings, and Disks. In: Computer Graphics and Image Processing, 10, 1979, S. 366–371

[16] N. I. Badler: Disk Generators for a Raster Display Device. In: Computer Graphics and Image Processing, 6, 1977, S. 589–593

[17] 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, S. 377–383

[18] D. Field: Algorithms for Drawing Anti-Aliased Circles and Ellipses. In: Computer Vision, Graphics, and Image Processing, 33, 1, January 1986, S. 1–15

[19] James D. Foley u. a.: Computer Graphics: Principles and Practice in C. S. 969–971

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]