Rasterung von Linien

Die Rasterung von Linien ist eine elementare Aufgabe der Computergrafik, bei der eine Linie auf das Punktraster einer Rastergrafik oder eines Raster-Grafikgeräts gezeichnet (gerastert) wird. Dazu werden diejenigen Punkte oder Pixel eingefärbt, die die ideale Strecke möglichst gut annähern.

Grundlegende Algorithmen rastern Linien nur einfarbig. Eine bessere Darstellung mit mehreren Farbabstufungen ergibt sich bei fortgeschrittenen Verfahren, die Antialiasing (Kantenglättung) unterstützen.

Da in der Computergrafik auch komplexere geometrische Figuren wie Polygone und beliebige Kurven häufig aus Liniensegmenten zusammengesetzt werden, bildet das Rastern von Linien gleichzeitig die Ausgangsbasis für deren Rasterung. Eine weitere Anwendung, bei der oft besonders viele Linien gezeichnet werden müssen, ist die Darstellung von Drahtgittermodellen.

Zwei gerasterte Linien. Die eingefärbten Pixel sind als Kreise dargestellt. Oben: einfarbige Rasterung; unten: Gupta-Sproull-Antialiasing, die ideale Linie wird hier als Fläche betrachtet.

Einfarbige Rasterung

Bei der einfarbigen Rasterung werden Linien mit einer einzigen Vordergrundfarbe auf einen Hintergrund gezeichnet. Sie eignet sich für Geräte mit monochromer Darstellung, zum Beispiel Laserdrucker.

Die Anfangs- und Endpunkte der zu rasternden Linie werden üblicherweise in ganzzahligen Koordinaten angegeben, das heißt, sie liegen direkt auf den Punkten des Rasters. Deshalb werden die meisten Methoden nur für derartige Anfangs- und Endpunkte formuliert. Zur Rasterung dicker Linien gibt es mehrere Möglichkeiten, die auch für andere Kurven geeignet sind, siehe dazu den Artikel Rasterung.

Einfache Methoden

Naive Methode der Rasterung mittels Rundung

Die einfachste Möglichkeit der Rasterung ist die direkte Umsetzung der Gleichung, die die Linie definiert. Wenn (x_a, y_a) der Anfangs- und (x_e, y_e) der Endpunkt der Linie ist, so erfüllen die Punkte auf der Linie die Geradengleichung y = m(x − x_a) + y_a, wobei $\textstyle m = \frac{\Delta y}{\Delta x} = \frac{y_e-y_a}{x_e-x_a}$ die Steigung ist.

Die Linie wird gezeichnet, indem in einer Schleife für jedes x von x_a bis x_e der entsprechende y-Wert gemäß dieser Formel berechnet und auf die nächstliegende Ganzzahl gerundet wird. Das Pixel (x, y) wird dann eingefärbt.

Dieses Verfahren ist unnötig langsam, da innerhalb der Schleife eine Multiplikation ausgeführt wird, die auf den meisten Computern wesentlich mehr Rechenzeit als eine Addition oder Subtraktion erfordert. Eine schnellere Methode ergibt sich durch die Betrachtung der Differenz zwischen zwei aufeinanderfolgenden Schritten:

$y_{i+1} - y_i \!$	$= (m(x_{i+1}-x_a) + y_a) - (m(x_i-x_a) + y_a) \!$
	$= m(x_{i+1}-x_i) \!$
	$= m \!$.

Demnach genügt es, mit (x_a, y_a) zu starten und bei jedem Schleifendurchlauf y um m zu erhöhen. Dieses Verfahren wird auch als Digital Differential Analyzer (DDA) bezeichnet.

Da die Rundung von y zur nächsten Ganzzahl dem Abrunden von y + 0,5 entspricht, lässt sich auch eine zusätzliche Kontrollvariable verwenden, die mit 0,5 initialisiert wird und zu der bei jedem Schleifendurchlauf m addiert wird. Jedes Mal, wenn die Kontrollvariable den Wert 1,0 erreicht oder übersteigt, wird y um 1 erhöht und von der Kontrollvariable 1,0 abgezogen. Dadurch ist keine Rundung mehr nötig. Diese Methode kann so umformuliert werden, dass sie nur schnellere Ganzzahl-Operationen verwendet und sich elegant in Assemblersprache implementieren lässt.^[1] Dennoch ist weiterhin eine langsame Division (Δy / Δx) zu Beginn nötig, die bei kurzen Linien nicht durch die schnelle Schleife aufgewogen werden kann.

Verallgemeinerung auf beliebige Richtungen

Rasterung beliebiger Linien durch Nutzung von Symmetrieeigenschaften. Der zulässige Bereich des Originalverfahrens ist farbig dargestellt, durch die drei Änderungen am Algorithmus werden auch die anderen Bereiche erschlossen.

Die soeben beschriebenen Verfahren funktionieren nur bei Liniensteigungen zwischen 0 und 1, was einem Winkel von 0° bis 45° zur Horizontalen entspricht. Bei anderen Steigungen wird die Linie nicht oder falsch gezeichnet. Es genügt jedoch, einen Algorithmus nur für Steigungen zwischen 0 und 1 zu beschreiben, da andere Linien durch die Nutzung von Symmetrien korrekt dargestellt werden können. Dies geschieht durch folgende drei Veränderungen:

1. Es wird zwischen zwei Fällen unterschieden, je nachdem, ob Δx > Δy oder umgekehrt. Im ersten Fall wird die Schleife wie bisher über x durchlaufen und im Schleifenrumpf y berechnet, ansonsten wird sie über y durchlaufen und x berechnet.
2. Innerhalb des Schleifenrumpfs wird y bzw. x nicht um 1 erhöht, sondern es wird der Vorzeichenwert von Δy bzw. Δx addiert.
3. Falls Δx < 0 bzw. Δy < 0, so muss die Schleife rückwärts durchlaufen werden.

Bresenham-Algorithmus

Die ältesten veröffentlichten Algorithmen zum Rastern von Linien stammen aus den frühen 1960er Jahren. Sie dienten der Steuerung von Digitalplottern, bei denen sich der Stift nur in festen Abständen horizontal, vertikal oder diagonal auf einem Raster bewegen konnte. Dazu gehörte auch der 1963 von Jack Bresenham präsentierte Bresenham-Algorithmus, der nur Ganzzahl-Berechnungen verwendet.^[2] Pitteway gab eine äquivalente Herleitung dieses Algorithmus an, die gegenüber Bresenhams eher geometrischen Formulierung den Vorteil hat, dass sie auch auf andere Kurven als Linien angewendet werden kann.^[3] Der resultierende Algorithmus, manchmal „Midpoint-Algorithmus“ genannt, ist genau der gleiche wie in Bresenhams Veröffentlichung.

Wahl des nächsten Pixels beim Bresenham-Algorithmus

Die Idee des Bresenham-Algorithmus besteht darin, bei jedem Schritt zwischen den beiden Pixeln zu wählen, die rechts („östlich“) und rechts oben („nordöstlich“) vom zuletzt gezeichneten Pixel liegen. Es wird dasjenige Pixel gewählt, das näher an der idealen Linie liegt. Dazu betrachtet man in der Midpoint-Formulierung den Mittelpunkt M zwischen den Pixeln O und NO: befindet sich M über der idealen Linie, so liegt O näher, ansonsten NO.

Um die Position von M gegenüber der Linie zu bestimmen, wird eine andere Form der Geradengleichung verwendet:

$F(x,\,y) = ax + by + c = \Delta y \cdot x - \Delta x \cdot y + c = 0$.

F(x, y) ist 0 für Punkte auf der Linie, positiv für Punkte unterhalb und negativ für Punkte oberhalb der Linie. Wenn in diese Gleichung die Koordinaten von M eingesetzt werden, so erhält man den Wert

$\textstyle d_i = F(x_i+1,\,y_i+\frac{1}{2}) = \Delta y (x_i+1) - \Delta x (y_i+\frac{1}{2}) + c$.

Je nach Vorzeichen dieser Kontrollvariable d_i wird das Pixel O oder NO gewählt.

Um einen effizienten Algorithmus zu erhalten, wird die Kontrollvariable inkrementell berechnet, also schrittweise erhöht. Ihre Änderung zwischen zwei aufeinanderfolgenden Schritten hängt davon ab, ob Pixel O oder NO gewählt wurde. Für jeden dieser Fälle betrachtet man die Differenz zwischen dem Wert der Kontrollvariable beim übernächsten und beim nächsten Pixel:

$\begin{align} \textstyle \Delta_O &= \textstyle d_{i+1} - d_i = F(x_i+2,\,y_i+\frac{1}{2}) - d_i = \Delta y\\ \textstyle \Delta_{NO} &= \textstyle d_{i+1} - d_i = F(x_i+2,\,y_i+\frac{3}{2}) - d_i = \Delta y - \Delta x\\ \end{align}$

Bei jedem Schritt wird die Kontrollvariable je nach gewähltem Pixel um Δ_O oder Δ_NO erhöht. Ist $d_i \leq 0$, so liegt M oberhalb der Geraden, weshalb O gewählt wird, ansonsten NO.

Der Anfangswert der Kontrollvariable d lässt sich ebenfalls effizient berechnen, wenn $F(x_a,\,y_a) = 0$, der Startpunkt der Linie also genau auf einem Pixel liegt:

$\textstyle d_0 = F\left(x_a+1,\,y_a+\frac{1}{2}\right) =\ \underbrace{\Delta y \cdot x_a - \Delta x \cdot y_a + c}_{=F(x_a,\,y_a)=0}\,+\,\Delta y - \frac{\Delta x}{2} = \Delta y - \frac{\Delta x}{2}$

Um die Division durch 2 zu beseitigen, werden alle Werte der Kontrollvariable verdoppelt; das entscheidende Vorzeichen bleibt dabei erhalten. Damit lässt sich der Bresenham-Algorithmus für Linien mit einer Steigung zwischen 0 und 1 in nachfolgendem Pseudocode ausdrücken. Der Algorithmus benötigt nur Additionen innerhalb der Schleife; die einfachen Multiplikationen außerhalb der Schleife lassen sich ebenfalls durch eine Addition realisieren.

Veränderung der Kontrollvariable beim Bresenham-Algorithmus

d = 2×Δy – Δx ΔO = 2×Δy ΔNO = 2×(Δy − Δx) y = ya Pixel (xa, ya) einfärben Für jedes x von xa+1 bis xe Wenn d ≤ 0 d = d + ΔO ansonsten d = d + ΔNO y = y + 1 Pixel (x, y) einfärben

Eine andere Interpretation des Algorithmus geht von der Feststellung aus, dass die gerasterte Linie m = Δx − Δy Horizontal- und n = Δy Diagonalschritte enthält. Um diese beiden Schritttypen zu „mischen“, wird bei jedem Schritt entweder m von der Kontrollvariable abgezogen oder n addiert. Es wird der entsprechende Schritttyp ausgeführt, bei dem der resultierende Betrag der Kontrollvariable geringer ist. Dies wird auch aus obiger Grafik deutlich, bei der die Kontrollvariable stets so nahe wie möglich an der Nullachse liegt. Thompson beschrieb einen Algorithmus nach dieser Formulierung 1964, auf die Wahl des korrekten Anfangswerts der Kontrollvariable ging er allerdings nicht ein.^[4] Noch vor Bresenham hatte Fred Stockton 1963 einen Algorithmus zur Rasterung von Linien veröffentlicht, der ebenfalls nur Ganzzahl-Berechnungen verwendet, aber unnötig kompliziert ist.^[5]

Linien, deren Endpunkte mit nicht-ganzzahligen Koordinaten angegeben werden, lassen sich ebenfalls mit dem Bresenham-Algorithmus rastern. Hierzu muss der Anfangswert der Kontrollvariable gemäß ihrer ursprünglichen Definition berechnet werden; pauschale Vereinfachungen sind nicht möglich. Der restliche Algorithmus bleibt gültig.

Pixelreihen

Obwohl der Bresenham-Algorithmus recht effizient ist, zeichnet er nur ein Pixel pro Schleifendurchlauf und benötigt dazu eine Addition. Eine Methode, die alle Pixel einer „Reihe“ – das heißt, Pixel mit gleicher y-Koordinate – auf einmal zeichnet, wurde zum ersten Mal von Reggiori entwickelt.^[6] Reihen mit nur einem Pixel wurden dabei gesondert behandelt. Später stellte Bresenham einen allgemeineren Algorithmus vor, der ohne Tests für diesen Spezialfall auskam.^[7]

Bei Bresenhams Pixelreihen-Algorithmus wird nicht x schrittweise erhöht, sondern y. Für jedes y wird das Ende der aktuellen Reihe berechnet. Das geschieht durch Betrachtung der Punkte, in denen die ideale Linie eine durch den Mittelpunkt zwischen zwei vertikal benachbarten Pixeln verlaufende Horizontale schneidet. Das Ende der Pixelreihe ist der abgerundete Wert der x-Koordinate dieses Schnittpunkts:

Die Endpunkt-Koordinaten der Pixelreihen lassen sich auch inkrementell berechnen. Da hier bei bestimmten Steigungen einige Punkte falsch berechnet werden können, nutzt der Algorithmus eine Symmetrie zur Geraden der Steigung ½ aus.

In der innersten Schleife von Bresenhams neuem Algorithmus sind keine Additionen erforderlich, denn alle Pixel einer Reihe werden auf einmal eingefärbt. Allerdings ist eine Division zur Initialisierung erforderlich. Fung ersetzte sie durch ein Suchverfahren und nahm einige weitere Optimierungen vor.^[8]

N-Schritt-Verfahren

Die vier möglichen Pixelmuster beim Doppelschrittverfahren

Eine andere, erstmals von Wu und Rokne vorgestellte Möglichkeit der Rasterung besteht darin, Schritte von mehreren Pixeln entlang der x-Achse zu machen und alle dazwischen liegenden Pixel der Linie auf einmal einzufärben.^[9] Dazu wird zwischen den verschiedenen möglichen „Pixelmustern“ ausgewählt. Bresenhams Algorithmus kann als Spezialfall dieser Methode angesehen werden, bei dem nur Schritte von je einem Pixel gemacht werden und bei dem nur zwischen zwei „Mustern“ (Pixel rechts oder rechts oben) gewählt wird.

Um zwischen den beim Doppelschrittverfahren vier möglichen Mustern unterscheiden zu können, wird zunächst die letzte Pixelspalte des Musters betrachtet. Befindet sich das zu rasternde Pixel unten oder oben, lässt sich trivial auf das Muster 1 beziehungsweise 4 schließen. Befindet sich das Pixel hingegen in der Mitte, so ist ein zusätzlicher Test der mittleren Spalte nötig, um zwischen den Mustern 2 und 3 wählen zu können.

Diese Tests werden dadurch vereinfacht, dass bei einer Steigung m ≤ ½ Muster 4 und bei m ≥ ½ Muster 1 nicht auftreten kann. Ähnlich wie beim Bresenham-Algorithmus lässt sich auch beim Doppelschrittverfahren die Kontrollvariable für die Tests inkrementell berechnen. Im Endeffekt kommt der Algorithmus nur mit Additionen und einer einfachen Multiplikation, die sich mit einer schnellen Bitverschiebung realisieren lässt, aus.

Es wurden auch Algorithmen für Dreifach- und Vierfachschritte entwickelt, die nach dem gleichen Prinzip arbeiten, aber erheblich komplizierter und länger sind.^[10][11] Ein anderer Vierfachschritt-Algorithmus verwendet eine etwas abweichende Formulierung, die systematisch die Bedingungen untersucht, unter denen ein bestimmtes Muster auftritt, und die sich auf beliebig viele Schritte verallgemeinern lässt.^[12]

Bidirektionale Rasterung

Oben: Eine mit dem Bresenham-Algorithmus von links nach rechts gerasterte Linie; unten: bidirektionale Rasterung. Die hohlen Kreise geben die Pixel an, die eingefärbt werden, wenn bei d=0 das andere Pixel gewählt wird.

Um die Geschwindigkeit der Rasterung weiter zu erhöhen, liegt es nahe, die Linie bidirektional, also gleichzeitig vom Anfangs- und vom Endpunkt aus bis zum Mittelpunkt zu zeichnen. Hierbei läuft die Schleife nur über eine Hälfte der Linie; bei jedem Schritt werden die beiden beteiligten Pixel auf jeder Seite der Linie eingefärbt. Sowohl der Bresenham-Algorithmus als auch andere Verfahren lassen sich so umändern.^[13]

Dabei muss aber beachtet werden, dass die mit den normalen Methoden gerasterte Linie nicht unbedingt in sich punktsymmetrisch ist. Das liegt daran, dass es bei der Rasterung uneindeutige Situationen gibt, in denen die ideale Linie genau durch den Mittelpunkt zweier vertikal benachbarter Pixel verläuft, zwischen denen beliebig gewählt werden kann. Der oben aufgeführte Bresenham-Algorithmus zum Beispiel wählt in solchen Fällen (d = 0) immer das Pixel mit kleinerer y-Koordinate aus. Beim Zeichnen von rechts nach links hingegen wird, bedingt durch die Nutzung der Symmetrie, das Pixel mit größerer y-Koordinate ausgewählt. Wenn die Linie bidirektional oder von rechts nach links gezeichnet wird, kann sich daher das Erscheinungsbild gegenüber dem normalen Algorithmus ändern, sofern nicht separat auf die uneindeutigen Fälle getestet wird.

Sonstige Techniken

Periodizität

Es lässt sich beweisen, dass sich die Werte der Kontrollvariable beim Bresenham-Algorithmus a-mal wiederholen, wobei a der größte gemeinsame Teiler von Δx und Δy ist.^[13] Das bedeutet, dass die Werte der Kontrollvariable nur für einen Teil der Linie berechnet werden müssen und dann auf die anderen Teile angewandt werden können. Hierzu muss allerdings der ggT berechnet werden. Diese Methode lässt sich auch mit der bidirektionalen Rasterung kombinieren.

Pixelreihen erster, zweiter und dritter Ordnung

Hierarchische Pixelreihen

Die Länge der Pixelreihen in einer gerasterten Linie folgt einem bestimmten Muster. Rosenfeld bewies, dass die Länge aller Pixelreihen, außer möglicherweise der ersten und der letzten, höchstens um ein Pixel abweicht.^[14] Er stellte außerdem fest, dass die Folge der Pixelreihen selbst diese Struktur aufweist, ebenso wie die Folge dieser Folgen, und so weiter. Gerasterte Linien sind also hierarchisch aus Reihen „n-ter Ordnung“ aufgebaut, die jeweils nur bestimmte Längen annehmen können. Stephenson beschrieb praktikable Algorithmen, die eine Linie ausgehend von Reihen beliebig hoher Ordnung zeichnen können, sowie einen rekursiven Algorithmus, der von der Reihe höchstmöglicher Ordnung ausgeht.^[15] Dadurch wird sowohl der Bresenham-Algorithmus als auch der Pixelreihen-Algorithmus verallgemeinert. Der Algorithmus für Reihen „nullter Ordnung“, bei dem die Pixelreihen ignoriert werden, entspricht dem gewöhnlichen Bresenham-Algorithmus.

Strukturelle Algorithmen

Es wurden noch weitere Algorithmen zur Rasterung vorgeschlagen, die aber nicht inkrementell arbeiten, sondern sich die strukturellen Eigenschaften der gerasterten Linien direkt zunutze machen. Sie basieren auf Überlegungen aus der Bildverarbeitung oder digitalen Geometrie und erreichen in der Praxis nicht die Geschwindigkeit der herkömmlichen Methoden, da sie Zeichenketten manipulieren oder andere langsame Operationen erfordern.

Brons’ Algorithmus etwa repräsentiert die gerasterte Linie durch eine Zeichenkette aus Nullen und Einsen, wobei 0 für einen Horizontal- und 1 für einen Diagonalschritt steht.^[16] Der Algorithmus geht von einer Zeichenkette aus, die eine erste Annäherung an die Linie darstellt, fasst Folgen von Nullen und Einsen zusammen und verteilt sie gleichmäßig. Der gleiche Prozess wird auf die resultierende Folge angewandt. Das wiederholt sich so lange, bis keine Verbesserung mehr erzielt werden kann. Die so gerasterte Linie ist allerdings nicht optimal; um die gleiche Linie wie beim Bresenham-Algorithmus zu erhalten, sind zusätzliche Anpassungen nötig.

Eigenschaften und Vergleich

Obwohl zahlreiche Algorithmen entdeckt wurden, die weniger komplex als der Bresenham-Algorithmus sind, ist deren praktischer Geschwindigkeitsvorteil gering. Das liegt daran, dass die Befehle zum Einfärben von Pixeln auf heutiger Hardware verglichen mit der Ausführung des Rasteralgorithmus selbst sehr langsam sind. Einige Grafikkarten stellen jedoch etwas schnellere Funktionen zum Einfärben mehrerer Pixel auf einmal bereit, etwa die rectwrite-Funktion auf SGI-Systemen. Dies ist von Vorteil für Pixelreihen-Algorithmen, die so eine Reihe schnell auf einmal zeichnen können.

Die Ausführungsgeschwindigkeit der verschiedenen Algorithmen hängt von der Länge der zu rasternden Linie ab. Algorithmen, deren innere Schleife schnell ist, die aber viel Zeit zur Initialisierung benötigen, können nur bei langen Linien einen Geschwindigkeitsvorteil verbuchen. Es wurde daher vorgeschlagen, in Abhängigkeit von der Länge der Linie den jeweils effizientesten Algorithmus zu wählen.^[8] Eine statistische Analyse der Linienlängen in verschiedenen Anwendungen wie der Darstellung von Drahtgittermodellen, Kurvensegmenten und Schriftzeichen kam zu dem Ergebnis, dass knapp drei Viertel aller gerasterten Linien weniger als zehn Pixel lang waren.^[17] Demnach lohnt es sich, für den Spezialfall der kurzen Linien zu optimieren. Algorithmen, die eher bei der Rasterung langer Linien vorteilhaft sind, eignen sich besser für Ausgabegeräte mit höherer Auflösung als Bildschirme und damit im Durchschnitt längeren Linien, etwa Laserdrucker. Bei manchen Algorithmen hängt die Geschwindigkeit außerdem von der Steigung der Linie ab – Pixelreihen-Algorithmen zum Beispiel sind weniger effizient bei diagonalen Linien, da hier nur ein Pixel pro Reihe gezeichnet werden kann.

Ein anderer Faktor bei der Wahl eines Algorithmus ist die Programmlänge. Hersteller von Grafikprozessoren, die die Rasterung direkt auf Hardwareniveau implementieren und daher Platz sparen müssen, bevorzugen kurze Algorithmen wie den Bresenham-Algorithmus. Bei Softwareimplementierungen ist dieser Faktor weniger kritisch.

Probleme

Unterschiedliche Helligkeiten je nach Steigung

Alle Algorithmen zur einfarbigen Rasterung können in bestimmten Situationen Probleme verursachen:

Unterschiedliche Helligkeit

Beim Rastern von Linien gleicher Länge, aber unterschiedlicher Steigung wird nicht unbedingt die gleiche Anzahl von Pixeln eingefärbt. Im nebenstehenden Beispiel ist die diagonale Linie länger als die waagrechte, dennoch werden in beiden Fällen die gleiche Anzahl von Pixeln eingefärbt. Dies führt dazu, dass beide Linien auf dem Ausgabegerät unterschiedlich hell erscheinen. Bei monochromen Geräten kann dieses Problem nicht umgangen werden.

Linienstile

Die Nutzung der Symmetrie zum Rastern von Linien mit beliebigem Anfangs- und Endpunkt kann unerwünschte Effekte verursachen, falls bestimmte Linienstile verwendet werden. Wenn gestrichelte oder gepunktete Linien gezeichnet werden sollen, so fängt das jeweilige Muster beim Anfangspunkt der Linie an. Solche Linien werden anders gezeichnet, wenn Anfangs- und Endpunkt vertauscht werden. Sofern die Striche eines Linienstils durch eine bestimmte Anzahl einzufärbender Pixel definiert sind, variiert außerdem die tatsächliche Strichlänge je nach Steigung.

Clipping

Das Clipping ist eine Operation, die die Rasterung auf einen bestimmten, meist rechteckigen Bereich einschränkt. Dies geschieht, indem vor der Rasterung die Anfangs- und Endpunkte der zu rasternden Linie zu den Kanten des rechteckigen Bereichs hin verschoben werden, sofern sie herausragen. Im Allgemeinen führt das dazu, dass die Koordinaten dieser Punkte nicht mehr ganzzahlig sind. Wenn diese Koordinaten dennoch gerundet werden, ergibt sich eine Linie mit anderer Steigung und damit möglicherweise auch anderem Erscheinungsbild. Um dies zu vermeiden, sind zusätzliche Tests nach dem Clipping nötig. Der Bresenham-Algorithmus kann auch mit einem Clipping-Algorithmus kombiniert werden.^[18]

Antialiasing

Das größte Problem bei einfarbig gerasterten Linien ist ihr im Allgemeinen „treppenartiges“ Aussehen, auch Treppeneffekt genannt. Auf Grafikgeräten, die zur Darstellung mehrerer Helligkeitsstufen fähig sind, kann diesem Effekt durch Antialiasing entgegengewirkt werden. Hierbei wird die zu rasternde Linie üblicherweise nicht mehr als eindimensionale Strecke, sondern als zweidimensionale Form, im einfachsten Fall als Rechteck mit gewünschter Dicke, betrachtet. Für die Rasterung müssen die Farbwerte der Pixel, die in der Nähe des Rechtecks liegen, ermittelt werden.

Methode von Gupta und Sproull

Illustration des kegelförmigen Glättungskerns. Die Intensität des Pixels ist proportional zum Volumen V.

Beim Antialiasing lässt sich der Farbwert eines Pixels ermitteln, indem ein so genannter Glättungskern oder Rekonstruktionsfilter über das Pixel gelegt wird. Gupta und Sproull schlugen als Glättungskern einen Kegel mit einem Radius von einem Pixel vor.^[19] Der Farbwert des Pixels ist proportional zum Volumen des Kegelteils, der die zu rasternde Linie (hier also das zu rasternde Rechteck) überlappt. Dieses Volumen wiederum hängt von der Distanz D zwischen der Mittellinie des Rechtecks und dem Pixel ab.

Die drei möglichen Pixel, die bei einer Liniendicke von einem Pixel eingefärbt werden

Der Gupta-Sproull-Algorithmus basiert auf dem Bresenham-Algorithmus, berechnet aber zusätzlich D für jedes der Pixel, deren Glättungskern die Linie überlappt. Bei einer Linienstärke von einem Pixel sind dies maximal drei Pixel pro Spalte. Aus Effizienzgründen werden die Distanzen nicht exakt berechnet, sondern nur 24 mögliche Distanzen betrachtet. Die Intensitätswerte, die diesen Distanzen entsprechen, wurden im Voraus berechnet und in einer Tabelle (Lookup-Tabelle) gespeichert, sodass sie schnell abgerufen werden können.

Die Linienenden müssen gesondert behandelt werden, da hier mehr als drei Pixel, insgesamt bis zu sechs, beteiligt sind. Die Intensitäten dieser Pixel hängen von der Steigung der Linie ab. Sie werden für einige Steigungen im Voraus berechnet und auch hier wieder in einer Tabelle gespeichert. Es sind auch andere Formen für die Linienenden denkbar, zum Beispiel abgerundete Endpunkte; die Intensitäten der beteiligten Pixel ändern sich dementsprechend.

Der Gupta-Sproull-Algorithmus eignet sich für Linien mit beliebiger Linienstärke, wobei sich allerdings auch die Lookup-Tabelle ändert. Bei einer Linienstärke größer als einem Pixel muss beachtet werden, dass möglicherweise die Glättungskerne von mehr als drei Pixeln die Linie überlappen.

Ein Problem des Gupta-Sproull-Algorithmus ist, dass gerasterte Linien oftmals an verschiedenen Stellen unterschiedlich hell zu sein scheinen. Dieses „seilartige“ Aussehen ist vor allem auf die Unzulänglichkeit des Kegels als Glättungskern zurückzuführen.^[20]

Methode von Wu

Berechnung der Intensitäten beim Wu-Antialiasing

Wu wählte einen anderen Ansatz für das Antialiasing, der nicht auf der Nutzung eines bestimmten Glättungskerns, sondern auf einem Fehlermaß basiert.^[21] Die Methode ist in der Grundform nur auf ideale, unendlich dünne Linien anwendbar.

Beim Bresenham-Algorithmus wird versucht, eine Annäherung an die ideale Linie zu erreichen, indem der „Fehler“, also der Abstand zwischen der idealen Linie und zwei möglichen Pixeln minimiert wird. Wu schlug ein anderes Fehlermaß vor, das auf beliebige Kurven anwendbar ist. Der Fehler im Sinne dieses Fehlermaßes lässt sich vollständig beseitigen, sofern beliebige Farbwerte zugelassen werden. Dazu müssen die beiden Pixel, die direkt über und unter der idealen Linie liegen, Farbwerte proportional zur vertikalen Distanz zur idealen Linie annehmen.

Für Linien gab Wu einen besonders schnellen Algorithmus an. Dank trickreicher Ganzzahl-Operationen benötigt er nur eine Kontrollvariable, die schrittweise verändert wird und sowohl die Position der zwei beteiligten Spaltenpixel als auch deren Intensität bestimmt.

Sonstige Techniken

Verschiedene Antialiasing-Methoden am Beispiel eines CAD-Drahtgittermodells. Von links nach rechts: Kein Antialiasing (Bresenham), Gupta-Sproull, ungewichtete Flächenabtastung und Wu.

Eine andere Möglichkeit des Antialiasing ist die ungewichtete Flächenabtastung (unweighted area sampling). Hierbei entspricht der Farbwert eines Pixels dem Flächenanteil der Linie innerhalb eines Quadrats von einem Pixel Kantenlänge um das betreffende Pixel, der Glättungskern ist in diesem Fall also ein Würfel. Für diese Methode sind schnelle Algorithmen entwickelt worden.^[22] Nachteilig an der ungewichteten Flächenabtastung ist das verschwommene Erscheinungsbild der Linien.

Wie auch bei der einfarbigen Rasterung kann die Struktur der Pixelreihen dazu genutzt werden, die Geschwindigkeit der Rasterung zu erhöhen.^[23]

Neben den speziell für Linien optimierten Antialiasing-Verfahren können auch allgemeine Verfahren genutzt werden, etwa Whitteds Methode, bei der eine hochaufgelöste Rastergrafik als „Pinsel“ entlang der Linie bewegt wird.^[24]

Besondere Optimierungen

Die Rasterung von Linien lässt sich durch Näherungsverfahren, Nutzung von oder direkte Implementierung in Hardware sowie Parallelisierung noch effizienter gestalten. Dies ist erforderlich, wenn eine sehr große Zahl von Linien in Echtzeit gerastert werden muss.

Näherungsverfahren

Boyer und Bourdin stellten ein Näherungsverfahren vor, das immer die direkt unter der idealen Linie liegenden Pixel einfärbt.^[25] Eine derartig gerasterte Line verfügt über einige besondere Eigenschaften, die ausgenutzt werden können. So etwa sind in diesem Fall nicht nur die Bresenham-Kontrollvariable, sondern auch die Linienabschnitte periodisch. Zusammen mit weiteren Optimierungen ergibt sich ein Algorithmus, der insbesondere bei längeren Linien erheblich schneller als die präzisen Verfahren ist. Eine Qualitätsverschlechterung ist bei Linien mit sehr geringer Steigung feststellbar.

Parallelisierung

Eine einfache Methode zur Parallelisierung der einfarbigen Rasterung lässt verschiedene Algorithmen parallel laufen, die – jeweils etwas verschoben – mehrere Pixel in bestimmten Abständen zeichnen.^[26] Eine andere Möglichkeit besteht darin, die Linie in mehrere ungefähr gleich große Teile aufzuteilen, die jeweils einem Prozessor zur Rasterung zugewiesen werden.^[27] Jeder Teil wird mit Hilfe des Bresenham-Algorithmus gerendert; das Hauptproblem ist die Berechnung der korrekten Anfangswerte der Variablen. Weiterhin ist es möglich, mehrere Prozessoren die Endpunkt-Koordinaten der Reihen bei Bresenhams Pixelreihen-Algorithmus berechnen zu lassen.^[28] Auch für massiv parallel arbeitende Vektorrechner mit über 1000 Prozessoren wurden Algorithmen vorgestellt.^[29] Jedes Pixel der Rastergrafik wird dabei einem Prozessor zugewiesen, der entscheidet, ob dieses Pixel eingefärbt werden soll oder nicht.

Um die langsamen Speicherzugriffe bei der Rasterung zu beschleunigen, wurden spezielle Speicherarchitekturen entwickelt, etwa solche, bei denen der Speicher in Zellen unterteilt wird, in denen unabhängig voneinander ein Teil der Linie gezeichnet werden kann.^[30] Auch die Rasterung mit Antialiasing kann durch Hardware unterstützt werden.^[31]

Verwandte Probleme

4-verbundene Rasterung. Die zusätzlich zur 8-verbundenen Rasterung ausgewählten Quadrate sind schraffiert dargestellt.

Linien können nicht nur wie normalerweise üblich 8-verbunden, sondern auch 4-verbunden (4-connected) gerastert werden. Das bedeutet, dass keine Diagonal-, sondern nur noch Horizontal- und Vertikalschritte erlaubt sind. Wenn man sich das Punktraster in Quadrate unterteilt denkt, so werden hierbei alle Quadrate, die von der Linie überlappt werden, ausgewählt. Eine Verallgemeinerung dieser Technik auf drei Dimensionen findet bei Voxelgittern, einer Beschleunigungstechnik des Raytracing, Verwendung. Sie dient der Bestimmung der Voxel, durch die ein Strahl beim Raytracing wandert.

Bei gerasterten Linien sind die diagonalen Pixelschritte möglichst gleichmäßig verteilt. Algorithmen zum Rastern von Linien lassen sich daher auch dazu verwenden, Punkte mit ganzzahligen Koordinaten gleichmäßig in einem bestimmten Intervall zu verteilen.^[32] Mögliche Anwendungen sind die lineare Interpolation oder das Downsampling in der Signalverarbeitung. Weitere Parallelen ergeben sich zum Euklidischen Algorithmus sowie Farey-Reihen und einigen anderen mathematischen Konstrukten.^[33]

Literatur

• James D. Foley u. a.: Computer Graphics: Principles and Practice in C. Addison-Wesley, Reading (Massachusetts) 1995, ISBN 978-0-201-84840-3. (Behandelt den Bresenham-Algorithmus, Probleme bei der Rasterung sowie Gupta-Sproull-Antialiasing)

Einzelne Artikel:

Diese Liste ist eine Auswahl; ein ausführliches Literaturverzeichnis ist in Stephensons Dissertation (14.) enthalten.

1. ↑ Siehe Beispielcode in http://www.crbond.com/papers/newline.pdf (250 KB)
2. ↑ Algorithm for computer control of a digital plotter. IBM Systems Journal 4, 1 (1965): 25–30, ISSN 0018-8670 (PDF, 220 KB). Bereits im August 1963 als Vortrag auf der ACM National Conference in Denver präsentiert.
3. ↑ Mike L. V. Pitteway: Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter. The Computer Journal 10, 3 (November 1967): 282–289, ISSN 0010-4620
4. ↑ J. R. Thompson: Correspondence: Straight lines and graph plotters. The Computer Journal 7, 3 (August 1964): 227
5. ↑ Fred G. Stockton: Algorithm 162: XYmove plotting. Communications of the ACM 6, 4 (April 1963): 161, ISSN 0001-0782
6. ↑ Giovanni B. Reggiori: Digital computer transformations for irregular line drawings. Technical Report 403-22, New York University, New York, April 1972
7. ↑ Jack E. Bresenham u. a.: Run length slices for incremental lines. IBM Technical Disclosure Bulletin 22-8B (1980): 3744–3747, ISSN 0018-8689
8. ↑ ^{a b} Khun Yee Fung: A Run-Length Slice Line Drawing Algorithm without Division Operations. Computer Graphics Forum 11, 3 (1992): 267–277, ISSN 0167-7055
9. ↑ Xiaolin Wu, Jon 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. ↑ Phil Graham, S. Sitharama Iyengar: Double- and triple-step incremental generation of lines. In ACM CSC ’93 Proceedings: 384–389. ACM Press, Indianapolis 1993, ISBN 0-89791-558-5
11. ↑ Paul Bao, Jon G. Rokne: Quadruple-step line generation. Computers & Graphics 13, 4 (1989): 461–469, ISSN 0097-8493
12. ↑ Graeme W. Gill: N-Step Incremental Straight-Line Algorithms. IEEE Computer Graphics and Applications 14, 3 (May 1994): 66–72, ISSN 0272-1716
13. ↑ ^{a b} Giulio Casciola: Basic concepts to accelerate line algorithms. Computers & Graphics 12, 3/4 (1988): 489–502
14. ↑ Azriel Rosenfeld: Digital Straight Line Segments. IEEE Transactions on Computers C-23, 12 (December 1974): 1264–1269, ISSN 0018-9340
15. ↑ Peter Stephenson: The Structure of the Digitised Line: with Applications to Line Drawing and Ray Tracing in Computer Graphics. PhD Thesis, James Cook University of North Queensland, Australia, 1998 (Online)
16. ↑ Reyer Brons: Linguistic Methods for the Description of a Straight Line on a Grid. Computer Graphics and Image Processing 3 (1974): 48–62, ISSN 0146-664X
17. ↑ Jim X. Chen: The Analysis and Statistics of Line Distribution. IEEE Computer Graphics and Applications 22, 6 (November/December 2002): 100–107
18. ↑ Yevgeny P. Kuzmin: Bresenham’s Line Generation Algorithm with Built-in Clipping. Computer Graphics Forum 14, 5 (1995): 275–280
19. ↑ Satish Gupta, Robert F. Sproull: Filtering edges for gray-scale displays. In ACM SIGGRAPH ’81 Proceedings: 1–5. ACM Press, Dallas 1981, ISBN 0-89791-045-1
20. ↑ A. R. Forrest: Antialiasing in practice. In R. A. Earnshaw (Hrsg.): Fundamental Algorithms for Computer Graphics (=NATO ASI Series F.17): 113–134. Springer, Berlin 1985, ISBN 3-540-13920-6
21. ↑ Xiaolin Wu: An efficient antialiasing technique. In ACM SIGGRAPH ’91 Proceedings: 143–152. ACM Press, New York 1991, ISBN 0-89791-436-8
22. ↑ Siehe etwa Vincent Boyer, Jean-Jacques Bourdin: Discrete Analysis for Antialiased Lines. Short Presentation, Eurographics 2000 (PDF, 230 KB)
23. ↑ Nicholas A. Diakopoulos, Peter D. Stephenson: Anti-Aliased Lines Using Run-Masks. Computer Graphics Forum 24, 2 (June 2005): 165–172
24. ↑ Turner Whitted: Anti-aliased line drawing using brush extrusion. In ACM SIGGRAPH ’83 Proceedings: 151–156. ACM Press, Detroit 1983, ISBN 0-89791-109-1
25. ↑ Vincent Boyer, Jean-Jacques Bourdin: Fast Lines: a Span by Span Method. Computer Graphics Forum 18, 3 (1999): 377–384 (PDF, 400 KB)
26. ↑ Robert F. Sproull: Using program transformations to derive line-drawing algorithms. ACM Transactions on Graphics 1, 4 (October 1982): 259–273, ISSN 0730-0301
27. ↑ William E. Wright: Parallelization of Bresenham’s line and circle algorithms. IEEE Computer Graphics and Applications 10, 5 (September 1990): 60–67
28. ↑ Ivo Považan, Tomáš Hrúz: Parallel Line: a Unified Solution. In WSCG ’97 Proceedings: 60–67. University of West Bohemia, Pilsen 1997, ISBN 80-7082306-2 (Online)
29. ↑ Alex T. Pang: Line-drawing algorithms for parallel machines. IEEE Computer Graphics and Applications 10, 5 (September 1990): 54–59
30. ↑ Siehe etwa Pere Marès Martí, Antonio B. Martínez Velasco: Memory architecture for parallel line drawing based on nonincremental algorithm. In: Euromicro 2000 Proceedings: Vol. 1, 266–273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8
31. ↑ Siehe etwa Robert McNamara u. a.: Prefiltered Antialiased Lines Using Half-Plane Distance Functions. In HWWS 2000 Proceedings: 77–85. ACM Press, New York 2000, ISBN 1-58113-257-3
32. ↑ Chengfu Yao, Jon G. Rokne: An integral linear interpolation approach to the design of incremental line algorithms. Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, ISSN 0377-0427
33. ↑ Mitchell A. Harris, Edward M. Reingold: Line drawing, leap years, and Euclid. ACM Computing Surveys 36, 1 (March 2004): 68–80, ISSN 0360-0300 (PDF, 270 KB)

Weblinks

• Bresenham’s algorithm (NIST Dictionary of Algorithms and Data Structures) – Hintergründe zum Bresenham-Algorithmus, mit Original-Quellcode (englisch)
• Rasterung von Linien, Kreisen, Ellipsen (Uni Magdeburg, Institut für Simulation und Graphik) – Java-Applet zum Nachvollziehen des Bresenham-Algorithmus
• Project: Line Statistics (George Mason University Computer Graphics Lab) – Untersuchung zur Verteilung von Linienlängen und -steigungen (englisch)

Dieser Artikel wurde am 4. Mai 2007 in dieser Version in die Liste der exzellenten Artikel aufgenommen.