§ 1.3.3   Rasterung von Polygonen

	Computer-Graphik spielend lernen
		§ 1   Rastertechnik
			§ 1.3   Rasteralgorithmen
				§ 1.3.3   Rasterung von Polygonen

Rasterung von Polygonen

Werden Polygone als eine Folge von Strecken betrachtet, handelt es sich also um Vektorgraphik, dann kann die Rasterung durch vektorweise Anwendung des Bresenham-Algorithmus durchgeführt werden. Das Entscheidungskriterium bei diesem Algorithmus ist der kleinste Abstand zum gewünschten Vektor. Deshalb liegen die ausgewählten Pixel in der Regel auch links und rechts des idealen Verlaufs (vgl. Bild 1.18). Beschreiben Polygone jedoch die Begrenzung von Flächen, dann ist dieser Algorithmus natürlich untauglich, weil das angewandte Entscheidungskriterium irrelevant ist. Bei der Darstellung von Flächen muß nämlich entschieden werden, ob ein Pixel

der Begrenzung (Polygonkante) liegt. Innerhalb liegende Pixel gehören zur Polygonfläche und müssen gezeichnet werden.

Für Pixel, die auf einer Polygonkante liegen, muß eine Vereinbarung getroffen werden, damit auch gemeinsame Kanten zwischen zwei Flächen eindeutig behandelt werden können.

daß Pixel auf linken und unteren Kanten gezeichnet werden, auf rechten und oberen Kanten aber nicht! Das bedeutet, daß in diesen Fällen die oberste Rasterzeile und das rechte Pixel der entsprechenden Zeile fehlt!

In der folgenden Beschreibung zur Rasterung von polygonal begrenzten Flächen werden statt allgemeiner Polygone nur Dreiecke betrachtet. (Der beschriebene Algorithmus funktioniert aber auch mit allgemeinen Polygonen). Dreiecke sind per Definition konvex und tragen deshalb zu einer bestimmten Rasterzeile nur Segment bei (vgl. Bild 1.18), wodurch die Entscheidung auf innerhalb oder außerhalb vereinfacht wird. Darüber hinaus haben die für die Verdeckungs- und Beleuchtungsrechnung wichtigen Größen bei Dreiecken einen linearen Zusammenhang und können inkrementell berechnet werden (siehe Kapitel 6 und 7). Dies ist die Voraussetzung für optimale Algorithmen mit der Eignung zur Hardwareimplementierung.

Der Algorithmus besteht aus drei Schritten (vgl. Bild 1.18):

1. Berechne die Schnittpunkte zwischen Dreieckskanten und Rasterzeilen.
2. Sortiere die Schnittpunkte nach aufsteigendem X-Wert für jede Rasterzeile
3. Fülle die Segmente zwischen den entsprechenden Paaren von Schnittpunkten.

der betrachteten Polygonkante ist. Je nachdem, ob ganzzahlig oder reell ist und ob es sich um eine linke oder rechte Kante (ein Segment geht immer von links nach rechts) handelt, ist zu entscheiden, welches Pixel als zum Dreieck gehörender Start- bzw. Endpunkt eines Zeilensegments gewählt wird. Dabei ist die oben genannte Vereinbarung für den Fall auf zu beachten.

Am Beispiel einer linken Kante wird die Vorgehensweise erklärt (vgl. Bild 1.18).

 
Abbildung 1.18:   Rasterung eines Dreiecks.

Die Rasterung der linken Kante beginnt beim Startpunkt und . Laut Definition gehört dieser Punkt zum Dreieck. Für die nächste Zeile (Y = 2) wird der Kantenschnittpunkt

inkrementell berechnet. Man erkennt, daß das zum Dreieck gehörende Startpixel für die nächste Zeile durch die zu nächst größere ganze Zahl bestimmt ist, sofern der gebrochenrationale Teil von von Null verschieden ist. Ist ganzzahlig, so ist das Pixel auf der linken Kante definitionsgemäß ein Punkt des Dreiecks.

Offenbar ist der Betrag von 1/m gar nicht so entscheidend. Vielmehr interessiert, wann die Akkumulation des gebrochenrationalen Anteils von 1/m zum Überlauf führt! Hierzu wird keine Division benötigt. Addition und Subtraktion reichen als Operationen aus. nicht berechnet, sondern nur akkumuliert und das Ergebnis mit verglichen. Damit läßt sich für die linke Kante des Dreiecks folgender Algorithmus zur Rasterung angeben:

PROCEDURE linkeKante ( );

BEGIN X := ; Startpixel Y := ; X := - ; Y := - ; accu := 0; Initialisieren des Akkumulators FOR Y := TO DO BEGIN schreibe(X,Y); accu := accu + X; WHILE accu ;SPMgt; 0 DO Überlauf zum nächsten Pixel! Accu um Y verkleinern BEGIN X := X + 1; accu := accu - Y END; END END;

Der gleiche Algorithmus wird auch für die rechten Kanten benötigt, was hier aber nicht ausgeführt wird.

Aus Bild 1.18 ist zu entnehmen, daß natürlich auch bei flächigen Objekten die Ränder ästhetisch unbefriedigende Rasterfehler aufweisen. Eine mögliche Lösung ist die exakte Ermittlung der vom Dreieck überdeckten Pixelfläche.

Startseite
§ 1.3.2   Glätten von gerasterten Strecken
§ 1.3.4   Glätten von Polygonkanten