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.
mini|hochkant=2.0|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 mini|hochkant=1.4|Naive Methode der Rasterung mittels Rundung Die einfachste Möglichkeit der Rasterung ist die direkte Umsetzung der Gleichung, die die Linie definiert. Wenn (xa, ya) der Anfangs- und (xe, ye) der Endpunkt der Linie ist, so erfüllen die Punkte auf der Linie die Geradengleichung , wobei die Steigung ist.
Die Linie wird gezeichnet, indem in einer Schleife für jedes von bis der entsprechende -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:
| || .
Demnach genügt es, mit (xa, ya) zu starten und bei jedem Schleifendurchlauf um zu erhöhen. Dieses Verfahren wird auch als Digital Differential Analyzer (DDA) bezeichnet.
Da die Rundung von zur nächsten Ganzzahl dem Abrunden von entspricht, lässt sich auch eine zusätzliche Kontrollvariable verwenden, die mit 0,5 initialisiert wird und zu der bei jedem Schleifendurchlauf addiert wird. Jedes Mal, wenn die Kontrollvariable den Wert 1,0 erreicht oder übersteigt, wird 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.Siehe Beispielcode in http://www.crbond.com/papers/newline.pdf (250 kB) Dennoch ist weiterhin eine langsame Division () zu Beginn nötig, die bei kurzen Linien nicht durch die schnelle Schleife aufgewogen werden kann.
Verallgemeinerung auf beliebige Richtungen mini|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:
Es wird zwischen zwei Fällen unterschieden, je nachdem, ob (betragsmäßig) oder umgekehrt. Im ersten Fall wird die Schleife wie bisher über durchlaufen und im Schleifenrumpf berechnet, ansonsten wird sie über durchlaufen und berechnet. Innerhalb des Schleifenrumpfs wird bzw. nicht um 1 erhöht, sondern es wird abhängig vom Vorzeichen von bzw. der Wert +1 oder −1 addiert. Falls bzw. , so muss die Schleife rückwärts durchlaufen werden. Für m wird der Betrag der Steigung verwendet
Durch die Anwendung dieser Verallgemeinerungen kann zur besseren Übersicht die folgende Tabelle erstellt werden: Quadrant m <= 1 sonst (m > 1) Richtung 1 x++y = y1 + m * i x = x1 + i/my++ von links unten nach rechts oben 2 x--y = y1 + m * i x = x1 + i/my++ von rechts unten nach links oben 3 x--y = y1 - m * i x = x1 - i/my-- von rechts oben nach links unten 4 x++y = y1 + m * i x = x1 - i/my-- von links oben nach rechts unten
Wobei i für m <= 1 Werte zwischen 0 und und für m > 1 Werte zwischen 0 und annimmt. Linien, die parallel zur X- oder Y-Achse sind, werden von dieser Tabelle ebenfalls abgedeckt und müssen nicht gesondert betrachtet werden. Die angegebene Richtung bezieht sich auf die nebenstehende Grafik unter der Annahme, dass x nach rechts größer wird und y nach oben wächst. x1 und y1 sind dabei die Koordinaten des Startpunktes einer Linie und x2 und y2 die Koordinaten des Endpunktes.
Ferner kann nur durch die Veränderung des Vorzeichens folgender Pseudocode erstellt werden, der alle acht beschriebenen Fälle abdeckt: signX = 1; signY = 1;
if x1 > x2 signX = -1;
if y1 > y2 signY = -1;
if m <= 1 for i=0; i <= deltaX; i++ drawPixel( ceil(x1 + i * signX), ceil(y1 + i * m * signY) ); else for i=0; i<= deltaY; i++ drawPixel( ceil(x1 + i / m * signX), ceil(y1 + i * signY) ); Wobei ceil() eine Funktion zum Aufrunden ist und drawPixel eine beliebige Funktion zum Setzen eines Pixels sein kann.
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.Algorithm for computer control of a digital plotter. IBM Systems Journal 4, 1 (1965): 25–30, (). Bereits im August 1963 als Vortrag auf der ACM National Conference in Denver präsentiert. 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.Mike L. V. Pitteway: Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter. The Computer Journal 10, 3 (November 1967): 282–289, Der resultierende Algorithmus, manchmal „Midpoint-Algorithmus“ genannt, ist genau der gleiche wie in Bresenhams Veröffentlichung.
mini|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 zwischen den Pixeln und : befindet sich über der idealen Linie, so liegt näher, ansonsten .
Um die Position von gegenüber der Linie zu bestimmen, wird eine andere Form der Geradengleichung verwendet:
.
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 eingesetzt werden, so erhält man den Wert
.
Je nach Vorzeichen dieser Kontrollvariable wird das Pixel oder 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 oder 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:
Bei jedem Schritt wird die Kontrollvariable je nach gewähltem Pixel um oder erhöht. Ist , so liegt oberhalb der Geraden, weshalb gewählt wird, ansonsten .
Der Anfangswert der Kontrollvariable lässt sich ebenfalls effizient berechnen, wenn , der Startpunkt der Linie also genau auf einem Pixel liegt:
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.
mini|hochkant=1.7|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 Horizontal- und Diagonalschritte enthält. Um diese beiden Schritttypen zu „mischen“, wird bei jedem Schritt entweder von der Kontrollvariable abgezogen oder 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.J. R. Thompson: Correspondence: Straight lines and graph plotters. The Computer Journal 7, 3 (August 1964): 227 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.Fred G. Stockton: Algorithm 162: XYmove plotting. Communications of the ACM 6, 4 (April 1963): 161,
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.Giovanni B. Reggiori: Digital computer transformations for irregular line drawings. Technical Report 403-22, New York University, New York, April 1972 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.Jack E. Bresenham u. a.: Run length slices for incremental lines. IBM Technical Disclosure Bulletin 22-8B (1980): 3744–3747,