Rastern von Linien

aus Wikipedia, der freien Enzyklopädie

Das Rastern von Linien ist eine elementare Aufgabe der Computergrafik. Hierbei wird eine Linie auf das Punktraster einer Rastergrafik oder eines Raster-Grafikgeräts gezeichnet (gerastert). Dazu werden diejenigen Punkte oder Pixel ausgewählt, 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 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.

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

[Bearbeiten] 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. Für die Rasterung dicker Linien gibt es mehrere Möglichkeiten, die auch für andere Kurven geeignet sind, siehe dazu den Artikel Rasterung.

[Bearbeiten] 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 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:

yi + 1 − yi	= (m(xi + 1 − x0) + y0) − (m(xi − x0) + y0)
	= m(xi + 1 − xi)
	= m.

Das bedeutet, dass es genügt, mit (x_a,y_a) zu starten und bei jedem Schleifendurchlauf y um m zu erhöhen. Derartige Verfahren zum Rastern von Linien, bei denen der y-Wert schrittweise erhöht wird, nennt man auch Digital Differential Analyzer (DDA).

Da die Rundung von y zur nächsten Ganzzahl dem Abrunden von y + 0,5 entspricht, lässt sich auch eine zusätzliche Kontrollvariable benutzen, 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, wodurch keine Rundung mehr nötig ist. 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.

[Bearbeiten] Verallgemeinerung auf beliebige Richtungen

Eine gerasterte Linie und die entsprechenden Linien, die sich durch Nutzung von Symmetrieeigenschaften rastern lassen

Die soeben beschriebenen Verfahren funktionieren nur bei Liniensteigungen zwischen 0 und 1, was einem Winkel zwischen 0° bis 45° zur Horizontalen entspricht. Bei anderen Steigungen wird die Linie möglicherweise 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 Veränderungen:

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

[Bearbeiten] Bresenham-Algorithmus

Hauptartikel: Bresenham-Algorithmus

Wahl des nächsten Pixels beim 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 1965 von Bresenham veröffentlichte klassische Algorithmus, der nur Ganzzahlen verwendet.^[2] Pitteway gab eine äquivalente Herleitung des Bresenham-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 jedoch genau der gleiche wie in Bresenhams Veröffentlichung.

Die Idee des Bresenham-Algorithmus ist es, 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 das Pixel gewählt, das näher an der idealen Linie liegt. Dazu betrachtet man in Pitteways Formulierung den Mittelpunkt M zwischen den Pixeln O und NO: befindet sich M über der idealen Linie, so liegt O näher, im anderen Fall ist es NO.

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

.

F(x,y) ist 0 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

.

Je nach Vorzeichen der Kontrollvariable d_i wird 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:

		.

Außerdem lässt sich leicht feststellen, dass der Anfangswert der Kontrollvariable Δy − Δx / 2 beträgt. Um diese Division zu beseitigen, werden alle Werte der Kontrollvariable verdoppelt, wobei das Vorzeichen beibehalten wird. 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 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 Betrag der Kontrollvariable geringer ist. Wie obige Grafik zeigt, liegt die Kontrollvariable stets so nahe wie möglich bei Null. Thompson beschrieb diese Formulierung des Algorithmus bereits 1964, auf die Wahl des korrekten Anfangswerts der Kontrollvariable ging er allerdings nicht ein.^[4]

Linien, deren Koordinaten als Gleitkommazahlen 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. Die restlichen Ganzzahl-Operationen werden einfach durch Gleitkomma-Operationen ersetzt.

[Bearbeiten] 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“ – also Pixel mit gleicher y-Koordinate – auf einmal zeichnet, wurde zum ersten Mal von Reggiori entwickelt.^[5] 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.^[6]

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 des Punkts, in dem 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 inkrementell berechnen. Dabei können sich einige Fälle ergeben, die nicht korrekt berechnet werden. Um das zu vermeiden, nutzt der Algorithmus eine Symmetrie zur Geraden der Steigung aus. Da alle Pixel einer Reihe auf einmal eingefärbt werden, sind in der innersten Schleife von Bresenhams neuem Algorithmus keine Additionen notwendig. Allerdings ist eine Division zur Initialisierung erforderlich.

Fung ersetzte die zeitaufwändige Division durch ein Suchverfahren und nahm einige weitere Optimierungen vor.^[7]

[Bearbeiten] 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.^[8] Dazu ist es nötig, aus den verschiedenen möglichen „Pixelmustern“, die sich ergeben können, auszuwählen. Bresenhams Algorithmus kann als Spezialfall dieser Methode angesehen werden, bei dem nur Schritte von jeweils einem Pixel gemacht werden und bei dem nur zwischen zwei „Mustern“ (Pixel rechts oder rechts oben) ausgewä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, so lässt sich darauf 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 lassen sich dadurch vereinfachen, dass bei einer Steigung Muster 4 und bei Muster 1 nicht auftreten kann. Auch beim Doppelschrittverfahren lässt sich, ähnlich wie beim Bresenham-Algorithmus, die Kontrollvariable für die Tests inkrementell berechnen. Im Endeffekt kommt der Algorithmus nur mit Tests, Additionen und einer einfachen Multiplikation, die sich mit einer 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.^[9][10] 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.^[11]

[Bearbeiten] 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. Sowohl der Bresenham-Algorithmus als auch andere Verfahren lassen sich so umändern.^[12]

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 zwischen zwei Pixeln verläuft und zwischen diesen beliebig gewählt werden kann. Der oben aufgeführte Bresenham-Algorithmus etwa wählt in solchen Fällen (d = 0) immer das Pixel mit kleinerer y-Koordinate aus. Beim Zeichnen von rechts nach links wird durch die Nutzung der Symmetrie aber das Pixel mit größerer y-Koordinate ausgewählt. Wenn die Linie von rechts nach links oder bidirektional gezeichnet wird, kann sich daher das Erscheinungsbild gegenüber dem normalen Algorithmus ändern.

Wenn das gleiche Verhalten wie beim von links nach rechts zeichnenden Algorithmus garantiert werden soll, so muss gesondert auf die uneindeutigen Fälle getestet werden.

[Bearbeiten] Sonstige Techniken

Periodizität

Es lässt sich beweisen, dass, wenn bei einer Linie der größte gemeinsame Teiler von Δx und Δy a beträgt, die Folge der Werte der Kontrollvariable beim Bresenham-Algorithmus sich a Mal wiederholt.^[12] 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, wozu allerdings der ggT berechnet werden muss. Dieses Verfahren 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 alle Pixelreihen, außer möglicherweise der ersten und der letzten, maximal zwei verschiedene Längen annehmen können, die voneinander um ein Pixel abweichen.^[13] 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.^[14] 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.

Am bekanntesten dürfte Brons’ Algorithmus sein, der die gerasterte Linie als eine Zeichenkette aus Nullen und Einsen betrachtet, wobei 0 für einen Horizontal- und 1 für einen Diagonalschritt steht.^[15] 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.

[Bearbeiten] Eigenschaften und Vergleich

Obwohl im Lauf der Zeit eine Vielzahl von Algorithmen entdeckt wurden, die in algorithmischer Hinsicht schneller als der Bresenham-Algorithmus sind, ist deren praktischer Geschwindigkeitsvorteil weit weniger groß. 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. Ein Algorithmus, der eine schnelle innere Schleife hat, aber viel Zeit zur Initialisierung benötigt, kann 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.^[7] 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.^[16] 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 Bildschirmen und damit im Durchschnitt längeren Linien, etwa Laserdruckern. 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.

[Bearbeiten] 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 -mal länger als die waagrechte, dennoch werden in beiden Fällen sechs Pixel eingefärbt. Dies führt dazu, dass beide Linien auf dem Ausgabegerät unterschiedlich hell erscheinen. Dieses Problem lässt sich durch Antialiasing lösen.

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. Das kann dazu führen, dass solche Linien unterschiedlich gezeichnet werden, 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, so ergibt sich eine Linie mit anderer Steigung und damit möglicherweise auch anderem Erscheinungsbild nach der Rasterung. Um dies zu vermeiden, sind zusätzliche Tests nach dem Clipping nötig. Der Bresenham-Algorithmus kann auch mit dem Clipping kombiniert werden.^[17]

[Bearbeiten] Antialiasing

Das größte Problem bei einfarbig gerasterten Linien ist, dass sie im Allgemeinen „treppenartig“ aussehen (Treppeneffekt). 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.

[Bearbeiten] 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 über das Pixel gelegt wird. Gupta und Sproull schlugen als Glättungskern einen Kegel mit einem Radius von einem Pixel vor.^[18] Der Farbwert des Pixels ist proportional zum Volumen des Kegelteils, der die zu rasternde Linie (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 überlappen. Bei einer Linienstärke von einem Pixel sind dies maximal drei Pixel pro Spalte. Aus Effizienzgründen werden die Distanzen nicht exakt berechnet, sondern es werden nur 24 mögliche Distanzen betrachtet. Die Intensitätswerte, die diesen Distanzen entsprechen, wurden im Voraus berechnet und sind in einer Tabelle (Look-Up-Table) 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 Look-Up-Table ä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.

[Bearbeiten] 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.^[19] 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. Bei der einfarbigen Rasterung ist es sehr aufwändig, die Punkte auszuwählen, die den Fehler im Sinne dieses Fehlermaßes minimieren. Der Fehler lässt sich aber 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.

[Bearbeiten] Sonstige Techniken

Vier 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. Diese Methode liefert schlechtere Resultate als gewichtete Verfahren; insbesondere wirken die Linien verschwommener. Für die ungewichtete Flächenabtastung sind schnelle Algorithmen entwickelt worden.^[20]

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

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

[Bearbeiten] Besondere Optimierungen

Das Rastern von Linien lässt sich durch Näherungsverfahren, Nutzung von oder direkter Implementierung in Hardware sowie Parallelisierung noch effizienter gestalten. Dies ist erforderlich, wenn eine sehr große Zahl von Linien in Echtzeit gerastert werden müssen.

[Bearbeiten] Näherungsverfahren

Boyer und Bourdin stellten ein Näherungsverfahren vor, das immer die direkt unter der idealen Linie liegenden Pixel einfärbt.^[23] Eine derartig gerasterte Line verfügt über einige besondere Eigenschaften, die ausgenutzt werden können. So etwa ist in diesem Fall die gesamte gerasterte Linie, und nicht nur die Bresenham-Kontrollvariable, 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.

[Bearbeiten] 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.^[24] 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.^[25] Jeder Teil wird mit Hilfe des Bresenham-Algorithmus gerendert; das Hauptproblem ist, die korrekten Anfangswerte der Variablen für jeden Teil zu berechnen. Eine weitere Methode besteht darin, mehrere Prozessoren die Endpunkt-Koordinaten der Reihen bei Bresenhams Pixelreihen-Algorithmus berechnen zu lassen.^[26]

Auch für massiv parallel arbeitende Vektorrechner mit über 1000 Prozessoren wurden Algorithmen vorgestellt.^[27] Jedes Pixel der Rastergrafik wird dabei einem Prozessor zugewiesen, der entscheidet, ob dieses Pixel eingefärbt werden soll oder nicht. Eine Methode tut dies, indem der Prozessor den Schnittpunkt der idealen Linie mit einer horizontalen oder vertikalen Linie berechnet und diesen mit den Koordinaten des ihm zugewiesenen Pixels vergleicht. Eine andere Methode ermittelt, ob die Distanz des Pixels zur idealen Linie unter einem bestimmten Wert liegt; damit können auch dicke Linien gerastert werden.

Um die langsamen Speicherzugriffe bei der Rasterung zu beschleunigen, wurden spezielle Speicherarchitekturen entwickelt, etwa solche, in denen der Speicher in Zellen unterteilt wird, in denen dank Parallelisierung ein Teil der Linie auf einmal gezeichnet werden kann.^[28] Auch die Rasterung mit Antialiasing kann durch Hardware unterstützt werden.^[29]

[Bearbeiten] 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. In diesem Fall dient die 8-verbundene Rasterung der Bestimmung der Voxel, durch die ein Strahl beim Raytracing wandert.

Bei gerasterten Linien sind die vertikalen 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.^[30] Mögliche Anwendungen sind die lineare Interpolation oder das Downsampling in der Signalverarbeitung. Ähnlichkeiten gibt es auch mit der Berechnung von Schaltjahren: Da das Jahr nicht genau 365 Tage lang ist, muss der verbleibende Rest als zusätzlicher Schalttag möglichst gleichmäßig in bestimmten Jahresabständen verteilt werden. Weitere Parallelen ergeben sich zum Euklidischen Algorithmus sowie Farey-Reihen und einigen anderen mathematischen Konstrukten.^[31]

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

[Bearbeiten] 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 nimmt am Schreibwettbewerb teil. Hilf mit, ihn zu verbessern.