Grafische Datenverarbeitung

7 2D-Graphik: Rasterkonvertierung

Die Szenenbeschreibung enthält kontinuierliche geometrische Objekte, wie Strecken, Kurven, Polygone etc.
Bei der Rastergraphik stehen aber nur endlich viele Bildpunkte (Pixel) als Darstellungselemente zur Verfügung.
Ziel der Rasterkonvertierung ist es also ein geometrisches Objekt O durch Bildpunkte zu approximieren, so dass diese bei hinreichend feiner Auflösung wie O aussehen.

Algorithmen zur Rasterkonvertierung

Strecken (naiver Algorithmus)
Voraussetzung:
Zugehörige Gerade in expliziter Darstellung:
y = m * x + b
Betrag der Steigung m liegt zwischen 0 und 1.
Vorgehensweise:
Fortschreiten auf dem Raster in x-Richtung
Rundung des zugehörigen y-Werts auf den nächsten Rasterpunkt mit gleichem x-Wert.
Nachteil
Gleitkommaarithmetik
Rundungsfunktion ist rechenaufwendig

Strecken (Mittelpunkts-Algorithmus)
Voraussetzungen:
Strecke s[p1,p2] uzugehörige Gerade in impliziter Darstellung:
a*x + b*y+c=0
mit
????
Steigung der Geraden liegt zwischen 0 und 1
Vorgehensweise
Fortschreiten auf dem Raster in x-Richtung Berechnung der Testgröße zur Auswahl des Rasterpunkts:
d(x) = a * x + b *(y+0.5) + c
Wenn d £ 0, wird der Punkt (x,y) gesetzt, sonst der Punkt (x,y+1)
Nachteil
Gleitkommaarithmetik
Multiplikationen

Strecken (Bresenham-Algorithmus)
Voraussetzungen:
wie bei Mittelpunkts-Algorithmus
Die Endpunkte der Strecke (p1x,p1y) und (p2x,p2y) sind Rasterpunkte.

Inkrementelle Fehlerberechnung
Testgröße für den nächsten Rasterpunkt, wenn (x,y) gesetzt wurde:
d(x+1) = a *(x+1) + b * (y+0.5) + c
Testgröße für den nächsten Rasterpunkt, wenn (x,y+1) gesetzt wurde:
d(x+1) = a *(x+1) + b * (y+1+0.5) + c

Inkrementelle Fehlerberechnung
Differenz zwischen altem und neuem Fehlerwert im Fall (x,y):
 d(x+1) – d(x) = a = dy
im Fall (x,y+1):
d(x+1) – d(x) = a + b = dy - dx
d.h. der neue „Fehler“ kann durch Addieren einer Konstanten aus dem alten Wert berechnet werden.
Initialisierung
Falls der erste Punkt (p1x,p1y) ein Rasterpunkt ist (d(p1x) = 0):

Ganzzahlige Arithmetik
Um ganzzahlig rechnen zu können, wird d(x) mit 2 multipliziert.
Der Vergleich des Testwerts gegen 0 bleibt damit korrekt.
Initialisierung: d := d(px+1) = 2 * dy – dx
Inkrement im ersten Fall: dE := 2 * dy
Inkrement im zweiten Fall: dNE := 2 * (dy – dx) =

Polygone
Die Raster-Konvertierung von Polygonen wird oft auch als Füllen bezeichnet.
Gesucht sind alle Rasterpunkte, die im Inneren eines Polygons oder auf einer seiner Kanten liegen.
Problem: Da nur Rasterpunkte im Inneren des Polygons gezeichnet werden, können sich bei spitzen Polygonen Lücken ergeben.

Polygone (Scanline-Algorithmus)
Vorgehensweise
Das Bild wird zeilenweise abgearbeitet.
Für jede Zeile:
1. Bestimme die von ihr geschnittenen Polygonkanten
2. Bestimme die Intervalle auf der Zeile, die durch Schnittpunkte begrenzt werden
3. Gib die Rasterpunkte in den Intervallen aus, die im Inneren des Polygons liegen

Bemerkungen
Horizontale Kanten werden ignoriert
Werden die Zeilen nach aufsteigenden y-Koordinaten bearbeitet, werden an den Polygoneckpunkten die Kanten berücksichtigt, die dort einen y-minimalen Endpunkt haben, diejenigen mit y-maximalem Endpunkt nicht.

Datenstrukturen
Repräsentation einer Kante
Maximale y-Koordinate
Zu Beginn x-Koordinate des unteren Endpunktes, später aktuelle x-Koordinate
Steigung der Kante für die inkrementelle Berechnung der Intervallgrenze: x = 1/m * y + b

X-Datenstruktur (engl. active edge table, AET)
Die X-Datenstruktur enthält die von der aktuellen Zeile geschnittenen Kanten, die sogenannten aktiven Kanten.
Die Kanten sind dabei nach aufsteigenden x-Koordinaten des Schnittpunkts mit der aktuellen Zeile sortiert.
Wichtige Operationen auf der X-Datenstruktur sind das Einfügen und Entfernen einer Kante.
Für kleine Kantenzahlen genügt die Implementierung durch eine lineare Liste.

Ablauf
Setze y auf die kleinste y-Koordinate, für die es einen Eintrag in der Y-Datenstruktur gibt (nicht leeres Fach).
Initialisiere die X-Datenstruktur als leere Liste.
Wiederhole bis die X- und Y-Datenstruktur leer sind:
Füge die Kanten aus der Y-Datenstruktur, die im Fach y enthalten sind, in die X-Datenstruktur ein.
Fülle die Bildpunkte der aktuellen Zeile y, wobei Paare von x-Koordinaten aus der X-Datenstruktur als linker und rechter Rand benutzt werden.
Entferne alle Kanten aus der X-Datenstruktur für die y = ymax gilt.
Erhöhe y um 1
Für jede nicht vertikale Kante, berechne die x-Koordinate zur neuen Zeile y

Bemerkungen
Die Intervallgrenzen können ähnlich wie bei der Raster-Konvertierung von Strecken inkrementell bestimmt werden.
Der Algorithmus muss aber so modifiziert werden, dass nur Intervallgrenzen im Inneren des Polygons erzeugt werden).

Scanline Algorithmus Beispiel:

Datenstruktur : für Y (edge table, ET)

Ymax= gibt die Gränze an die erreicht wird, wenn zu Xunten der 1/m wert dazu addiert wird.
Xunten= gibt den Anfangswert an, bei der X-Datenstruktur wird der immer überschrieben durch die Addition
1/m=gibt die Steigung an. Formel: 1/m=dX/dY= (2-4)/(7-1)=-1/3
Datenstruktur : für X : gibt die Gränzen an.(engl. active edge table, AET)
Für jede Zeile werden die Grenzen für Polygone ausgerechnet die Gefüllt werden sollen.
bei Unserem Beispiel: Zeile: Y=3

Ymax= gibt die Gränze an die erreicht wird, wenn zu Xunten der 1/m wert dazu addiert wird.
Xk= gibt den Xpunkt an der stelle y=3 an: Formel: x=1/m*y+b = -1/3*(3-1)+4=-2/3+12/3=10/3
y=an dieser stelle ist Zeile=y-anfangswert=1also abstand der Faktorisierung.
1/m=gibt die Steigung an. Formel: 1/m=dX/dY= (2-4)/(7-1)=-1/3

??

???

OpenGL- 2D Antialiasing
Antialiasing
Zur Erzeugung runder Punkte, glatter Strecken und glatter Polygonkanten muss das Antialiasing eingeschaltet werden.
Dies erfolgt durch die Aufrufe:
glEnable(GL_POINT_SMOOTH);
glEnable(GL_LINE_SMOOTH);
glEnable(GL_POLYGON_SMOOTH);
Zusätzlich kann mit dem Befehl glHint die Qualität der Ausführung implementierungsabhängig gesteuert werden.

Steuerung von Berechnungen
Qualitätshinweise
void glHint(GLenum target, GLenum mode)
Beschreibung
Definiert die Qualität durchzuführender Berechnungen.
Sofern die OpenGL-Implementierung diese Fähigkeit unterstützt – was sie nicht muss -, kann angegeben werden, ob bestimmte Berechnungen schnellstmöglich (GL_FASTEST), schönstmöglich (GL_NICEST) oder ohne Präferenz (GL_DONT_CARE) durchgeführt werden sollen.
Bemerkung
Für das Antialiasing kann der Parameter target die Werte, GL_POINT_SMOOTH_HINT, GL_LINE_SMOOTH_HINT und GL_POLYGON_SMOOTH_HINT annehmen.

Ist das Antialiasing aktiviert, dann wird von OpenGL ein Überdeckungsgrad berechnet, der angibt, wie viel Prozent eines Bildpunktes (Pixels) ein graphisches Objekt einnimmt. Dieser Überdeckungsgrad wird mit dem Alpha-Wert der Farbe des Objekts multipliziert.
Farben in OpenGL besitzen vier Komponenten: Rot, Grün, Blau und Alpha-Wert (siehe auch Beschreibung des Befehls glColor).
Der Alpha-Wert einer Farbe ist ein Transparenzwert  und wird beim Überblenden zwischen zwei Farben benutzt.

Damit der Überdeckungsgrad eines Bildpunkts mit dem schon existierenden Farbwert verrechnet wird, muss das Überblenden von Farben aktiviert sein. Die Gewichtung muss dabei auf a für die Quelle und 1-a für das Ziel gesetzt sein:
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA,  GL_ONE_MINUS_SRC_ALPHA);
Beispiel:
Sei Rs der neue Rot-Wert (Quelle) und Rd der bereits vorhandene Rot-Wert (Ziel) sowie As der Alpha-Wert der Quelle,
dann gilt für den überblendeten Rot-Wert:
Rs * As + Rd (1 – As)