Rasterung von Polygonen

Die Rasterung von Polygonen und aneinandergereihten Liniensegmenten (Polygonzügen) ist eine Aufgabe der Computergrafik. Das Rastern von Polygonzügen basiert auf der Rasterung von Linien, erfordert jedoch bei dicker Strichbreite zusätzlichen Aufwand. Dem Rastern von gefüllten Polygonen kommt in der 3D-Computergrafik eine große Rolle zu, da 3D-Szenen gerendert werden können, indem man die auf die Bildebene projizierten Polygone farbig füllt.

Verbinden von Liniensegmenten

Verschiedene Arten der Rasterung von Polygonecken: a) stumpfe Enden, b) abgerundete Enden, c) Mitering, d) Mitering mit abgeschnittenen Spitzen.

Beim Rastern dicker Liniensegmente muss entschieden werden, wie sie miteinander verbunden werden. Dicke Linien als Rechtecke zu betrachten, liefert unschöne Ergebnisse. Besser ist es, Linien mit runden Enden zu zeichnen. Eine andere Möglichkeit ist Mitering („Gehrung“), bei der die Linienenden schräg gezeichnet werden, sodass sie aneinander angrenzen. Bei sehr spitzen Winkeln ragen die Linienenden zu sehr über die eigentliche Polygonecke heraus, weshalb sie besser abgeschnitten werden.

Artefakte

Zwei verschiedene Arten der Rasterung eines Rechtecks

Bei der Rasterung von Polygonen muss entschieden werden, wie deren Koordinaten interpretiert werden. Wenn beispielsweise ein Rechteck mit den Endpunktkoordinaten (1, 1) und (5, 4) gerastert wird, so werden im Normalfall 5×4 Pixel eingefärbt, obwohl das Rechteck nur 4×3 Einheiten groß ist. Dieser unerwünschte Effekt ist eine Konsequenz der endlichen Bildauflösung. Wenn nebeneinanderliegende Polygone gezeichnet werden, so führt das dazu, dass einige Pixel mehrfach eingefärbt werden. Eine Möglichkeit, dieses Problem zumindest bei ganzzahligen Koordinaten zu umgehen, besteht darin, sie bei der Rasterung um einen halben Pixelabstand nach links und nach unten zu verschieben, sodass in Wirklichkeit das Rechteck mit den Koordinaten (0,5, 0,5) und (4,5, 3,5) gerastert wird (siehe Bild). Dadurch wird vermieden, dass bei nebeneinanderliegenden Polygonen Kanten doppelt eingefärbt werden, was bei bestimmten Rasteroperationen wie XOR unerwünschte Resultate hervorrufen würde. Eine alternative Methode, die Gleitkommazahlen vermeidet, ist, das jeweils letzte Pixel einer Zeile oder einer Spalte nicht zu rastern. Dabei wird in Kauf genommen, dass das Polygon etwas verschoben erscheint.

Auch sehr spitzwinklige Polygonecken können dazu führen, dass Pixel jeweils von mehreren Segmenten eingefärbt werden. Ein weiteres Beispiel für Artefakte sind Slivers, Polygonteile, die so dünn sind, dass sie keine Pixel einschließen und bei denen einige Rasteralgorithmen nur einzelne oder gar keine Pixel zeichnen.

Wenn ein gerasterter Winkel durch eine weitere Linie halbiert werden soll, etwa um Pfeile darzustellen, so ist es im Allgemeinen nicht möglich, ein exakt symmetrisches Resultat zu erreichen.^[1]

Aneinanderliegende Dreiecke

Wahl der Farbe eines Pixels, das genau auf einer von zwei Dreiecken geteilten Kante liegt. Hier ist Punkt a dem Referenzpunkt näher, also werden derartige Pixel hellblau eingefärbt.

Polygone mit mehr als drei Ecken als Teil von Polygonnetzen werden vor der Rasterung oft in Dreiecke umgewandelt. Dabei teilen sich sehr viele Dreiecke ihre Kanten. Wenn diese aneinanderliegenden Dreiecke unterschiedlich gefärbt sind und jede Kante als einfarbige Linie gerastert wird, so hängt das Erscheinungsbild von der Reihenfolge ab, in der die Dreiecke gerastert werden.

Um dieses Problem zu umgehen, färbt man ein Pixel dann und nur dann ein, wenn es innerhalb des zu zeichnenden Dreiecks liegt. Dazu können baryzentrische Koordinaten verwendet werden. Bezogen auf ein Dreieck kann jeder Punkt der Ebene durch die Koordinaten ${\displaystyle (\alpha ,\beta ,\gamma )}$ beschrieben werden. Ein Punkt oder Pixel befindet sich genau dann strikt innerhalb dieses Dreiecks, wenn sich jede dieser Koordinaten im Intervall ${\displaystyle ]0,1[}$ befindet. Diese Methode ist auch für nicht-ganzzahlige Eckpunktkoordinaten gültig.

Einen Sonderfall stellen Pixel dar, die sich genau auf einer Kante befinden und somit nicht trivial einem der beiden anliegenden Dreiecke zugewiesen werden können. Für diese Fälle wählt man einen außerhalb des Bildes liegenden Referenzpunkt und wählt die Farbe desjenigen Dreiecks, dessen nicht auf der Kante befindlicher Eckpunkt näher an diesem Punkt liegt. Diese Methode funktioniert immer dann, wenn der Referenzpunkt nicht auf der durch die Kante verlaufenden Geraden liegt.

Füllung

Am einfachsten werden gefüllte Dreiecke und damit Polygone gerastert, indem für jedes Pixel des Bildes der oben beschriebene Test angewendet wird: Pixel werden nur dann eingefärbt, wenn sie innerhalb eines Dreiecks liegen. Eine etwas effizientere Methode testet nur diejenigen Pixel innerhalb eines Rechtecks, welches das zu rasternde Dreieck einschließt. Neben diesen einfachen Methoden sind jedoch schnellere Verfahren entwickelt worden, die im Folgenden beschrieben werden.

Kantenlisten-Algorithmen

Grundprinzip

Mit dem Kantenlisten-Algorithmus gerastertes Polygon

Kantenlisten-Algorithmen bestimmen für jede Kante des Polygons die Schnittpunkte mit den Bildzeilen. Diese können direkt berechnet werden, oder es können Algorithmen zur Rasterung von Linien verwendet werden. Horizontale Kanten werden ignoriert. Die so ermittelten Schnittpunkte werden in einer Liste abgelegt.

Um wie weiter oben beschrieben zu vermeiden, dass zu viele Pixel an den Kanten eingefärbt werden, werden in Wirklichkeit die Schnittpunkte mit genau zwischen zwei Bildzeilen verlaufenden Geraden berechnet. Für das rechts im Bild dargestellte Beispielpolygon werden somit folgende Schnittpunkte in der Liste abgelegt:

Diese Schnittpunkte werden nun nach y-Koordinaten absteigend sortiert. Unter Werten mit gleichen y-Koordinaten wird aufsteigend nach x-Koordinaten sortiert. Nach der Sortierung sieht die Liste folgendermaßen aus:

(1; 6,5) (1,5; 6,5) (1; 5,5) (2,5; 5,5) (7,5; 5,5) (8; 5,5) (1; 4,5) (3,5; 4,5) (6,5; 4,5) (8; 4,5) (1; 3,5) (4,5; 3,5) (5,5; 3,5) (8; 3,5) (1; 2,5) (8; 2,5) (1; 1,5) (8; 1,5)

In dieser Liste gibt es immer eine gerade Anzahl von Werten mit gleicher y-Koordinate. Das Polygon wird gezeichnet, indem nacheinander Punktpaare aus der Liste betrachtet werden. Sie sind stets von der Form (x₁; y) (x₂; y); beide Punkte haben also die gleiche y-Koordinate. Es werden nun alle Pixel der entsprechenden Bildzeile gezeichnet, deren x-Koordinate sich im Intervall ${\displaystyle [x_{1}-0{,}5;x_{2}-0{,}5]}$ befindet.

Das erste Punktpaar ist (1; 6,5) (1,5; 6,5). Das einzige Pixel, das die eben genannte Bedingung erfüllt, ist hier (1; 6). Anschließend wird das nächste Punktpaar, (1; 5,5) (2,5; 5,5), betrachtet. Hier gibt es zwei Pixel, die eingefärbt werden, nämlich (1; 5) und (2; 5). Das Polygon ist fertig gerastert, wenn alle Punktpaare der sortierten Liste abgearbeitet wurden.

Aktive Kantenliste

Die Vorausberechnung der Schnittpunkte von Polygonkanten und zwischen den Bildzeilen verlaufenden Geraden ist unnötig zeitaufwändig und kann erheblichen Speicherplatz erfordern. Mit einer so genannten aktiven Kantenliste lässt sich die Berechnung der Schnittpunkte inkrementell durchführen und der Speicherplatz reduzieren. Dieses Verfahren wird gelegentlich Scanline-Algorithmus genannt;^[2] allerdings werden mit Scanline-Algorithmen auch darauf aufbauende Verfahren bezeichnet, um im Rahmen der 3D-Computergrafik aus Polygonen aufgebaute Szenen Zeile für Zeile zu rastern.

Bei diesem Algorithmus werden für jede Polygonkante nicht die Schnittpunkte mit allen Geraden, sondern nur mit der Geraden mit der größten y-Koordinate, die die Kante schneidet, ermittelt. Zusätzlich zur x-Koordinate des Schnittpunkts werden folgende Daten ermittelt:

• Δx, die Differenz zwischen den x-Koordinaten der Schnittpunkte zweier vertikal benachbarter Geraden (der Kehrwert der Steigung der Kante);
• n_y, die Anzahl der Geraden, die von der Polygonkante geschnitten werden.

Die Daten werden in einer Tabelle gespeichert, deren Einträge nach der Bildzeile sortiert sind. Für das Beispielpolygon ergibt sich folgende Tabelle:

Die Grundidee des Algorithmus besteht darin, von diesen vorberechneten Daten auszugehen und mit Hilfe der Δx-Werte die Koordinaten der anderen Schnittpunkte fortlaufend zu berechnen. Dabei wird von der höchsten Bildzeile ausgegangen und schrittweise zur niedrigeren Bildzeile gewechselt. Eine aktive Kantenliste speichert die Kanten, die die zur Bildzeile gehörende Gerade schneiden, sowie für jede Kante die aktuellen x-, Δx- und n_y-Werte.

Zu Beginn ist die aktive Kantenliste leer. Ausgegangen wird von der höchsten Bildzeile. Für jede Bildzeile wird in der vorberechneten Tabelle gesucht, ob sie Kanten enthält, die noch nicht in der aktiven Kantenliste enthalten sind, und wenn ja, werden die entsprechenden Daten in die aktive Kantenliste kopiert. Nun werden die x-Werte aller in der aktiven Kantenliste befindlichen Kanten aufsteigend sortiert. Die resultierenden Punktpaare werden wie im grundlegenden Kantenlisten-Algorithmus dazu verwendet, Pixel einzufärben. Anschließend werden die n_y-Werte in der aktiven Kantenliste um 1 erniedrigt; fällt ein Wert unter 0, so wird die entsprechende Kante aus der aktiven Kantenliste entfernt. Schließlich werden zu allen x-Werten in der aktiven Kantenliste Δx addiert, und die Prozedur wird mit der nächsten, niedrigeren Bildzeile wiederholt. Die Rasterung ist fertig, sobald alle Bildzeilen abgearbeitet wurden.

Beim Beispielpolygon verändert sich die aktive Kantenliste in den ersten vier Bildzeilen wie folgt:

Edge-fill-Algorithmus

Der größte Nachteil der Kantenlisten-Algorithmen ist der Aufwand zur Sortierung und Manipulation der Listen. Der sehr einfache Edge-fill-Algorithmus^[3] kommt ohne diesen Aufwand aus. Beim Edge-fill-Algorithmus werden für jede Bildzeile, die bei ${\displaystyle x_{\mathrm {Schnittpunkt} }}$ eine Polygonkante schneidet, alle Pixel dieser Bildzeile mit einer x-Koordinate strikt größer als ${\displaystyle x_{\mathrm {Schnittpunkt} }+0,5}$ invertiert. „Invertierung“ bedeutet hier, dass eingefärbte Pixel in den Ausgangszustand zurückgesetzt werden und umgekehrt. Die Reihenfolge, in der die Polygonkanten abgearbeitet werden, ist beliebig. Wenn der Algorithmus die Kanten des Beispielpolygons gegen den Uhrzeigersinn abarbeitet, so ergeben sich folgende Schritte:

Das gerasterte Polygon unterscheidet sich von dem der Kantenlisten-Algorithmen, denn drei Pixel werden nicht eingefärbt. Der Nachteil des Algorithmus ist, dass viele Pixel mehrmals geändert werden müssen.

Fence-fill-Algorithmus

Der Fence-fill-Algorithmus^[4] ist eine Weiterentwicklung des Edge-fill-Algorithmus, der die Zahl der nötigen Pixelinvertierungen verringert. Dabei wird ein Zaun (engl. “fence”), eine durch den Schnittpunkt zweier Polygonkanten verlaufende vertikale Gerade, genutzt.

• Für alle Schnittpunkte auf der linken Seite des Zauns werden alle Pixel vom Schnittpunkt bis links vom Zaun invertiert.
• Für alle Schnittpunkte auf der rechten Seite des Zauns werden alle Pixel vom Zaun bis links vom Schnittpunkt invertiert.

Dadurch ergeben sich folgende Schritte:

Edge-flag-Algorithmus

Eingefärbte Kontur nach dem ersten Schritt des Edge-flag-Algorithmus

Der Edge-flag-Algorithmus^[5] besteht aus zwei Schritten:

• Im ersten Schritt wird die Kontur des Polygons gezeichnet. Dazu wird für jeden Schnittpunkt einer Polygonkante mit einer Bildzeile das erste Pixel mit der Koordinate ${\displaystyle x>x_{\mathrm {Schnittpunkt} }+0,5}$ eingefärbt (siehe Bild).

 Für jede Polygonkante  linie, des Polygons
   punkt1 = linie.punkt1
   punkt2 = linie.punkt2
   wenn (punkt1.y > punkt2.y) dann tausche punkt1 mit punkt2
   Für jede Bildzeile y, des Bildes
     steigung_inv = (punkt1.x - punkt2.x) / (punkt1.y - punkt2.y)
     schnittpunkt_y = y + 0.5
     schnittpunkt_x = punkt1.x + steigung_inv * (schnittpunkt_y - punkt1.y)
     x = abrunden(schnittpunkt_x)
     wenn (x + 0,5) <= schnittpunkt_x dann x=x+ 1
     //- Randpunkt des Schnittpunktes mit der Bildzeile umkehren (einfärben oder zurücksetzen)
     Pixel (x,y) = ! Pixel (x,y);

• Im zweiten Schritt werden die Pixel innerhalb dieser Kontur eingefärbt. Dazu wird eine boolesche Variable verwendet, die angibt, ob man sich aktuell innerhalb des Polygons befindet oder nicht. Als Pseudocode lässt sich dieser Schritt folgendermaßen beschreiben:

Für jede Bildzeile y, die das Polygon schneidet
  Innerhalb = Falsch
  Für jedes x von links bis rechts
    Wenn Pixel (x, y) eingefärbt ist
      Innerhalb negieren
    Wenn Innerhalb
      Pixel (x, y) einfärben
    ansonsten
      Pixel (x, y) auf Hintergrundfarbe zurücksetzen

Als Softwareimplementierung sind der Kantenlisten-Algorithmus und der Edge-flag-Algorithmus vergleichbar schnell,^[6] implementiert in Hardware ist letzterer jedoch erheblich schneller.

Siehe auch

• Rasterung von Kreisen
• Rasterung von Linien

Literatur

• James D. Foley u. a.: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6.
• David F. Rogers: Procedural Elements for Computer Graphics. WCB/McGraw-Hill, Boston 1998, ISBN 0-07-053548-5.
• Peter Shirley u. a.: Fundamentals of Computer Graphics. AK Peters, Wellesley 2005, ISBN 1-56881-269-8.

Einzelnachweise

1. ↑ Donald E. Knuth: A note on digitized angles. In: Electronic Publishing—Origination, Dissemination, and Design. 3, 2, Mai 1990, S. 99–104, ISSN 0894-3982.
2. ↑ James D. Foley u. a.: Computer Graphics: Principles and Practice. S. 97.
3. ↑ Bryan Ackland, Neil Weste: Real time animation playback on a frame store display system. In: ACM SIGGRAPH Computer Graphics. 14, 3, Juli 1980, S. 182–188, ISSN 0097-8930.
4. ↑ Michael Dunlavey: Efficient polygon-filling algorithms for raster displays. In: ACM Transactions on Graphics. 2, 4, Oktober 1983, S. 264–273, ISSN 0730-0301.
5. ↑ Bryan Ackland, Neil Weste: The edge flag algorithm – a fill method for raster scan displays. In: IEEE Transactions on Computers. 30, 1, Januar 1981, S. 41–48, ISSN 0018-9340.
6. ↑ Turner Whitted, David Weimer: A software test-bed for the development of 3-D raster graphics systems. In: ACM SIGGRAPH Computer Graphics. 15, 3, August 1981, S. 271–277.