Grundlegende Rastergrafik-Algorithmen

5. Zweidimensionale Zeichenalgorithmen und Grundlagen zur interaktiven Grafik

5.1. Grundlegende Rastergrafik-Algorithmen

Problem:
virtuelles Zeichenblatt mit stetigen Koordinaten (float x, float y)
® reales Rasterdisplay mit diskreten Koordinaten (int X, int Y)
Nicht-ganzzahligen Punkten (x, y) werden ganzzahlige Alias-Punkte (X, Y) zugeordnet.
Dabei: Ungenauigkeiten (und im Extremfall sehr unschöne Effekte).

Ziel 1: Linien sollen ihrem idealen Verlauf möglichst nahe kommen
Ziel 2: Ausgleich möglicher, verbleibender Störeffekte.

Zunächst zu Ziel 1:
Raster-Konvertierungen für Geraden(-stücke), Kreise, Ellipsen...

Zunächst: Linien mit Dicke von 1 Pixel darstellen
Þ für Gerade mit Steigung zwischen -1 und 1: setze in jeder Spalte genau 1 Pixel.
Für andere Geraden: Symmetrie ausnutzen (Koordinaten vertauschen)!
Abb.: Die gesetzten Pixel sind als Quadrate dargestellt.

(aus Rauber 1993)

Naiver Algorithmus:
aus x-Werten von x₁ bis x_n die y-Werte nach Geradengleichung y = mx+b berechnen und auf nächstgelegene Integer-Zahl runden.

Nachteile:

Floating-Point-Arithmetik (langsamer als Integer-Arithmetik)
Multiplikationen
Rundungsoperationen

möglichst einfache Operationen: wichtig auch für evtl. Hardware-Realisierung!

schrittweise Verbesserung (vgl. Übungsblatt 0, Aufg. 5):

y inkrementieren statt durch Multiplikation berechnen
Rundungsoperation durch Variable error und Vergleichsabfrage ersetzen (error liefert Abstand der idealen Geraden vom Pixel):

wenn error >= 0.5 ist, setze Pixel um 1 höher und dekrementiere error um 1. Damit optimale Nähe der gesetzen Pixel zur idealen Geraden gewährleistet.
Immer noch floating point-Operationen
Þ weitere Verbesserung: alles mit dx = x_n - x₁ multiplizieren, dann Rechnung nur noch im Integer-Bereich!
Zusätzlich wird error mit -dx/2 (bzw. -int(dx/2)) statt mit 0 initialisiert (Þ Vergleich nur noch mit 0 statt mit 0,5).

Ergebnis:
Bresenham-Algorithmus zur Linienrasterung (1965)

void Linie (int x1, int y1, int xn, int yn,
int value)
/* Anfangspunkt (x1, y1), Endpunkt (xn, yn),
Steigung zwischen 0 und 1 angenommen */
{
int error, x, y, dx, dy;
dx = xn - x1; dy = yn - y1;
error = -dx/2; y = y1;
for (x = x1; x <= xn; x++)
{
set_pixel(x, y, value);
error += dy;
if (error >= 0)
{
y++;
error -= dx;
}
}
}

In obiger Form nur für 1. Oktanden.
Verallgemeinerung: Ausnutzung der Symmetrie.

"Treibende Achse" = Achse, deren Werte mit fester Schrittweite 1 durchlaufen werden (im obigen Fall: x-Achse).
Fallunterscheidung nach dem Oktanden der Geraden:

Nachteil:
Linien unterschiedlicher Steigung erscheinen unterschiedlich hell.

Linie B ist sqrt(2)-mal länger als Linie A, hat aber dieselbe Zahl von Pixeln Þ erscheint schwächer!

Abhilfe: Intensität (Parameter value) mit der Steigung der Linie erhöhen.

Rasterung von Ellipsen

Parametermethode (auch: trigonometrische Methode):

Ellipsengleichung in Parameterform (Parameter q = Winkel im Mittelpunkt):

x = a cos q , y = b sin q.

q durchläuft die Werte von 0 bis 360° bzw. bis 2p.
a und b sind die Abschnitte auf den Hauptachsen. Hier Hauptachsen = Koordinatenachsen.

Um den Winkel f gedrehte Ellipse mit Mittelpunkt (x_c, y_c):
x = a cos f cos q - b sin f sin q + x_c = A cos q - B sin q + x_c

y = a sin f cos q + b cos f sin q + y_c = C cos q + D sin q + y_c
mit A = a cos f , B = b sin f , C = a sin f , D = b cos f
(durch Anwendung einer Rotation und Translation auf die ungedrehte Ellipse, vgl. Transformationsmatrizen (später) bzw. Lineare Algebra).

Durchlaufe äquidistante Parameterwerte
verbinde die zugehörigen Ellipsenpunkte durch Linien (Geradensegmente).
n = Anzahl gewünschter Geradensegmente Þ
Schrittweite incr = 2p /n.
Zu jedem q_i = q_i-1 + incr berechne zugehörigen Punkt (x_i, y_i),
zeichne Linie von (x_i-1, y_i-1) nach (x_i, y_i).
Dazu: Merken des vorangegangenen Punktes.

Implementation:

void ellipse(float a, float b, float phi,
float xc, float yc, int n, int value)
{
float cosphi, sinphi, theta, pi, costheta,
sintheta, A, B, C, D, x0, x1, y0, y1, incr;
int i;
pi = 4*arctan(1);
cosphi = sintab[pi/2 + phi];
sinphi = sintab[phi];
A = a*cosphi; B = b*sinphi;
C = a*sinphi; D = b*cosphi;
x0 = A + xc; y0 = C + yc;
theta = 0; incr = 2*pi/n;
for (j=1; j <= n; j++)
{
theta += incr;
costheta = sintab[pi/2 + theta];
sintheta = sintab[theta];
x1 = A*costheta - B*sintheta + xc;
y1 = C*costheta + D*sintheta + yc;
Draw_line(x0, y0, x1, y1, value);
x0 = x1; y0 = y1;
}
}

Kosinusberechnung wird auf Sinus zurückgeführt.
Sinusberechnung wird hier durch Lookup-Table ersetzt.
Wegen sin x = sin(p -x) und sin x = -sin(x-p ) braucht man nur die Werte zwischen 0 und p /2 zu speichern!
Verbesserung des Algorithmus (Halbierung der Laufzeit): Ausnutzung der Symmetrie der Ellipse.

Nachteil der Parametermethode:
Feste Unterteilung der Parameterwerte Þ Ungenauigkeit an Stellen starker Krümmung.
Abhilfe: nichtlineare Einteilung der Parameterwerte (incr abhängig von der Krümmung).

anderer Ansatz:

Polynom-Methode

Ausgangspunkt jetzt:
kartesische Achsenabschnittsform der Ellipsengleichung (Polynom 2. Grades).
Ungedrehte Ellipse:

(x/a)² + (y/b)² = 1

Vorgehen:
Auflösen nach y, x durchläuft alle in Frage kommenden Werte in Einerschritten, 2 y-Werte werden jeweils berechnet.
Nachteil: hoher Rechenaufwand (Quadratwurzeln!).

alternativer Ansatz:
Scangeraden-Methode
(auch für andere Arten von Kurven)

Prinzip: horizontale Scangerade wird über die (ideale) Ellipse geschoben, für jede y-Position werden die Schnittpunkte bestimmt und im Raster approximiert.
Rechnung geht wieder aus von der Achsenabschnittsform (s.o.)

Für gedrehte und verschobene Ellipsen: x und y entsprechend substituieren durch x cos f - y sin f + x_c
bzw. x sin f + y cos f + y_c.
Scangeraden-Gleichung: y = y_i (= konst.)
Schnittpunkt-Berechnung: Einsetzen von y = y_i in die Ellipsengleichung und Auflösen nach x (quadratische Gleichung; genaue Rechnung s. Rauber 1993, S. 31 ff.). Ergebnis: zwei x-Werte für die Schnittpunkte.
Berechnung nur nötig für solche Scangeraden, die die Ellipse schneiden:
Berechnung der oberen und unteren Ausdehnung y_t und y_b der Ellipse durch

y_t,b = ± Ö (b² cos² f + a² sin² f ).

Ferner: Ausnutzung der Symmetrie:

Nachteil der Methode:
In jeder Bildschirmzeile, die die Ellipse trifft (außer der oberen und unteren Tangente), werden genau 2 Pixel gesetzt
Þ in Bereichen mit Steigung nahe 0 können "Lücken" auftreten

Abhilfe:

überprüfe x-Abstand zum zuletzt gesetzten Pixel, wenn > 1: setze die dazwischenliegenden Pixel der Scangeraden
oder: verwende vertikale Scangeraden in Bereichen mit Steigung zwischen -1 und 1:

Für letztere Vorgehensweise benötigt man die Parameterwerte mit Tangentensteigung +1 und -1:
bei q ₁ = arctan(-b / (a tan(p /4 - f ))), q ₂ = q ₁ + p ist die Steigung +1,
bei q ₃ = arctan(-b / (a tan(p /4 - f ))), q ₄ = q ₃ + p ist sie -1.
(Herleitung bei Rauber 1993.)

Vorteil der Scangeraden-Methode:
Direkt auch zum Füllen von Ellipsen geeignet (verbinde die Schnittpunkte jeweils durch horizontales Scangeraden-Stück).

weiterer Ansatz:
Differentielle Methode

Grundidee: wie bei der inkrementellen Geradendarstellung wird x um 1 erhöht und y um ein (variables) Inkrement m.
Variante: man erhöht den Parameter q um ein festes D q und berechnet die entsprechenden Änderungen D x und D y, um von (x, y) zum nächsten Punkt (x+D x, y+D y) zu gelangen.
Berechnung von D x und D y:

Parametergleichungen x = a cos q und y = b sin q ableiten nach q ,

Einsetzen der Ausgangsgleichungen in die Gleichungen für x' und y' liefert zwei Differentialgleichungen:

x' = -(a/b)*y, y' = (b/a)*x,

dies lässt sich schreiben als:

dx = -(a/b)*y*dq , dy = (b/a)*x*dq

Diskretisierung:

Dx = -(a/b)*y*Dq , Dy = (b/a)*x*Dq

Þ als Ansatz für die Implementation würde sich anbieten:
x -= (a/b)*y*Dq , y += (b/a)*x*Dq .
Jedoch: schlechte Konvergenz, Dq muss sehr klein sein, um genügende Genauigkeit zu erzielen.
Besser arbeitet man mit einer Zentrierung:

x_i+1 = x_i - (a/b)(y_i + y_i+1)/2 * Dq ,
y_i+1 = y_i + (b/a)(x_i + x_i+1)/2 * Dq

das sind 2 Gleichungen mit 2 Unbekannten (x_i+1 und y_i+1), die aufgelöst werden können.
Durch Zusammenfassen von Konstanten und Herausziehen von schleifeninvarianten Berechnungsteilen aus der Hauptschleife kommt man auf 4 Multiplikationen und 2 Additionen pro errechnetem Ellipsenpunkt.

Verbesserung der Laufzeit möglich durch Verwendung des Differentials zweiter Ordnung, um P_i+1 aus P_i und P_i-1 zu berechnen (Formeln siehe Rauber 1993). Dann pro dargestelltem Geradensegment nur 2 Multiplikationen und 2 Additionen.
Für gedrehte Ellipsen analog (Unterschied nur in der Initialisierung).

Nachteil des differentiellen Verfahrens in dieser Form: Darstellung ungenau an den steilen Stellen der Ellipse.
Abhilfe: Dq eliminieren, in jedem Schritt 1 Pixel der Ellipse berechnen (D x = 1), dabei die "treibende Achse" je nach Bereich der Ellipse wählen.

1: x treibende Achse, inkrementiere y.
2: y treibende Achse, inkrementiere x.
3: x treibende Achse, dekrementiere y.
4: y treibende Achse, dekrementiere x.

Komplexität: für jedes Pixel 1 Multiplikation, 1 Division, 4 Additionen erforderlich.

Kreise:

Spezialfälle der Ellipsen.
Für Kreise können (theoretisch) weitere Symmetrien ausgenutzt werden.
Beachte aber:
Für viele Monitore sind Höhe und Breite der Pixel ungleich
Þ Kreise müssen als "echte" Ellipsen (mit a ¹ b) konstruiert werden.

Wegen seiner Einfachheit erwähnen wir den Kreisalgorithmus von Bresenham (Analogie zum Geraden-Algorithmus):

es wird nur die Kreislinie im 2. Oktanden konstruiert (der Rest folgt aus Symmetrieoperationen)
dort gibt es bei "x++" nur die beiden Fälle "y bleibt gleich" oder "y--"
die Abstände der beiden Kandidaten-Punkte (wenn (x_i, y_i) gezeichnet ist) zum Mittelpunkt sind d_s = (x_i + 1)² + y_i² - r² und d_t = (x_i + 1)² + (y_i - 1)² - r²
d_s ist immer >0, d_t immer <0
Entscheidungsvariable für die Auswahl des nächsten Pixels: d = d_s + d_t
diese kann rekursiv berechnet werden:

für d > 0: x++; d += (4x + 6);
für d <= 0: x++; y--; d += (4(x-y)+10).

Beachte: Multiplikationen mit Zweierpotenzen lassen sich effizient als Shift-Operationen realisieren.
Damit kommt auch der Bresenham-Kreis-Algorithmus ohne "echte" Multiplikationen aus.
Pro Punkt: durchschnittl. Ö 2 Additionen, Ö 2 Shifts, 2 Inkremente und 1 Test.

Füllen von Polygonen und geschlossenen Kurven

Die Scangeraden-Methode

Voraussetzung: geschlossenes Polygon P liegt in geometrischer Beschreibung vor.

Scangerade parallel zur x-Achse wird von unten nach oben über P geschoben,
für jede Lage der Scangeraden werden die Schnittpunkte mit dem Polygon berechnet.
Für konvexe Polygone gibt es genau 2 Schnittpunkte oder keinen,
für konkave Polygone gibt es eine gerade Zahl von Schnittpunkten, die nach steigendem x geordnet werden.

(zur Paritätsregel: vgl. "even-odd Filling rule" bei PostScript!)
Es sind Sonderfälle zu beachten:

(Krömker 2001)

Nach der Regel für den y_max-Knoten einer Kante werden in diesem Beisp. für die Scangerade y=0 die Kanten a und b, für die Scangerade y=2 die Kanten c und d, für die Scangerade y=4 aber keine Kante geschnitten:

Abb. (*) (aus Rauber 1993)

Vorsicht beim Füllen von Polygonen, die sich über den Bildschirmrand erstrecken:

Wenn nur die sichtbaren Polygonkanten übergeben werden, kann z.B. für die Scangerade y = a nicht entschieden werden, ob die entspr. Bildschirmzeile innerhalb oder außerhalb des Polygons liegt.
Abhilfe: Beim Clipping (siehe später) müssen die Teile des Fensterrandes, die im Polygon liegen, als zusätzliche Kanten an den Scangeraden-Algorithmus übergeben werden.

Genaueres Vorgehen beim Einfärben:

naiver Algorithmus:
äußere Schleife: Scangerade verschieben
innere Schleife: Schnittpunkte mit allen Polygonkanten berechnen
effizienter:
äußere Schleife über die Polygonkanten e
innere Schleife: berechne für e alle Schnittpunkte mit allen Scangeraden zwischen y_min(e) und y_max(e) und lege diese sortiert in einer (globalen) Datenstruktur ab.
Danach durchlaufe die Datenstruktur und färbe die entspr. Segmente für jede Scangerade.
Vorteil: Bei Berechnung der Schnittpunkte kann ein inkrementeller Algorithmus verwendet werden (Variante des Bresenham-Algorithmus).
In der Datenstruktur brauchen für jeden Schnittpunkt nur die x-Werte separat abgespeichert zu werden, der y-Wert gilt für die gesamte Scangerade.
Dieses Beispiel bezieht sich auf obige Abb. (*):

Der Übersichtlichkeit halber sind hier noch die Labels der Punkte mit angegeben worden (a,b,c,d) - diese braucht man in der Praxis nicht. Fehler in der Abb.: ersetze das a bei der 4 durch c.

Diese Datenstruktur könnte in C etwa so realisiert werden:
struct scanline
{
struct xpixlist *list;
struct scanline *next;
int ypix;
}
struct xpixlist
{
int xpix;
struct xpixlist *next;
}

Es gibt eine noch platzsparendere Variante, die einen bucket sort-Algorithmus zur Erstellung einer Kantenliste ausnutzt (s. Foley et al. 1990).
Für beliebige Kurven als Grenzen der Füllregion muss nur die Berechnung der Schnittpunkte geändert werden.

Die Saatfüll-Methode

wird benutzt, wo umgebende Polygone bereits auf dem Bildschirm dargestellt sind (interaktive Grafik)
keine geometrische Repräsentation des Polygons nötig!
stattdessen: Pixel der Grenzlinie müssen durch spezifische Grenzfarbe erkennbar sein.

Grundidee:
Setze ein Pixel im zu füllenden Bereich
setze dessen Nachbarpixel auf die Füllfarbe (sofern diese nicht die Grenzfarbe haben)
wiederhole dies, bis kein Pixel mehr neu gefärbt werden kann.
Beachte:
Die Nachbarschaft darf keine Diagonal-Pixel enthalten, da sonst vom Bresenham-Algorithmus gerasterte Geraden "undicht" sind:

Implementierung:

naiver Ansatz: rekursiver Aufruf; ungünstig wegen Beanspruchung des Rekursionsstacks
effizienter:
"Horizontalisierung" des Füllens; 2 Schleifen: innere erzeugt "Pixelläufe" in horiz. Richtung, äußere iteriert dies nach oben und unten.
Beachte: Auch hier ist (außer bei konvexen Polygonen) ein Stack erforderlich, der das Auftreten zusätzlicher Pixelläufe verwaltet.

Beispiel:

(aus Rauber 1993)

Hier entstehen bei 1, 2, 3, 4 und 5 jeweils neue Pixelläufe.
Jeder Pixellauf wird durch sein rechtestes Pixel repräsentiert.
Der Algorithmus terminiert, wenn der Stack, der die Pixelläufe verwaltet, leer ist.

Nachteil:
Bei "engen" Polygonen kann der Saatfüll-Algorithmus vorzeitig stoppen. Abhilfe: Zweite Saat setzen.

(aus Fellner 1992)

Clipping von Polygonen

häufige Aufgabe: Abschneiden von Geradensegmenten an einem Polygon (häufig an einem Rechteck). Clipping, Clippen.
(Vgl. Clipping-Pfade in PostScript.)

einfachste Variante:
für jedes Pixel während der Bildschirm-Darstellung prüfen, ob es innerhalb des Clipping-Polygons liegt.

sinnvoll, wenn Schnittpunktberechnung zu aufwändig
oder wenn das zu clippende Objekt sehr klein ist (nur wenige Pixel zu prüfen).

Analytische Methode:
Schnittpunkte berechnen
Fallunterscheidungen schon bei einfachsten Objekten erforderlich.

Clippen eines Geradensegments s an einem rechteckigen Fenster

Grundsätzl. Vorgehensweise:
Endpunkte von s: P₁ und P₂
Parametergleichung der Geraden, auf der s liegt:
g = P₁ + t(P₂ - P₁), t beliebig
Für s selbst: t Î [0; 1].
Fenster-Eckpunkte: A = (x_min, y_min), B = (x_max, y_min),
C = (x_max, y_max), D = (x_min, y_max).
Gleichung der Geraden durch die Fenster-Eckpunkte A, B:
f = A + u(B - A). (analog für BC, CD, DA.)
Schnittpunkt aus Gleichsetzen der Geradengleichungen:
P₁ + t(P₂ - P₁) = A + u(B - A)
(entspr. 2 Gleichungen mit 2 Unbek.) Þ Lösungspaar t, u.
0 £ t £ 1 Û Schnittpunkt liegt auf dem gegebenen Segment
0 £ u £ 1 Û Schnittpunkt liegt auf der Fensterkante.
Fall A: beide Endpunkte von s liegen innerhalb des Fensters
Þ s liegt ganz innerhalb des Fensters
Fall B: ein Endpkt. liegt innerhalb, einer außerhalb
Þ (nur) ein Schnittpunkt zu bestimmen
Fall C: beide Entpkte liegen außerhalb des Fensters
Þ s kann durch das Fenster verlaufen; beide Schnittpunkte zu bestimmen.

Ziel: Zahl der Schnittpunktberechnungen vermindern!

Beispiel: Wenn beide Endpunkte von s links des Fensters liegen, kann s nicht durch das Fenster verlaufen.
Ebenso: wenn beide rechts, beide oberhalb, beide unterhalb.
Systematisierung:

Algorithmus von Cohen und Sutherland
Kennzeichnung der 9 Bereiche in Bezug auf das Fenster durch 4 Bits. Bit 0 gesetzt für Bereiche links des Fensters, 1 für rechts, 2 für unten, 3 für oben: ("outcodes")

Þ Bitmuster von horizontal oder vertikal benachbarten Bereichen unterscheiden sich in genau 1 Bitposition.
Ordne den Endpunkten von s ihre Bitcodes c1 und c2 zu.
c1 | c2 = 0 (bitweises Oder) Û c1 und c2 sind beide 0000 Û s liegt ganz im Fenster.
c1 & c2 ¹ 0 (bitweises Und) Û c1 und c2 haben in mindestens einer Stelle gemeinsame Bits Û s liegt auf einer Seite des Fensters, kann nicht durch das Fenster gehen!
in allen übrigen Fällen: Teile s mittels einer der Fenstergeraden in zwei Teile (hier Schnittpunktberechnung erforderlich!), wiederhole das Verfahren für beide Teile (einer muss ganz außen liegen!). Mit welcher Fenstergerade schneiden: entscheide mittels des Bitcodes z.B. von c1 (wenn c1 ¹ 0, sonst c2).
Wenn Bit 3 gesetzt: entspr. Punkt liegt ganz oberhalb des Fensters; wähle die obere Begrenzungsgerade. Analog für die anderen Bits.

(aus Rauber 1993)

3 Beispielfälle für die Anwendung des Algorithmus

Programmskizze:

void CS_clip (float x1, float y1, float x2,
float y2, float xmin, float xmax,
float ymin, float ymax,
int value)
{
int c1, c2; float xs, ys;
c1 = code(x1, y1); c2 = code(x2, y2);
if (c1 | c2 == 0x0)
Draw_Line(x1, y1, x2, y2, value);
else
if (c1 & c2 != 0x0)
return;
else
{
intersect(xs, ys, x1, y1, x2, y2,
xmin, xmax, ymin, ymax);
if (is_outside(x1, y1))
CS_clip(xs, ys, x2, y2, xmin, xmax,
ymin, ymax, value);
else
CS_clip(x1, y1, xs, ys, xmin, xmax,
ymin, ymax, value);
}
}

intersect berechnet in den Rückgabeparametern xs und ys einen Schnittpunkt zwischen dem Geradensegment und einer der Fenstergeraden, die anhand der 4-Bit-Zahl der Endpunkte des Geradensegments ausgewählt wird.
is_outside berechnet, ob der Punkt (x1, y1) bzgl. derselben Fenstergeraden außerhalb des Fensters liegt.
(nach Rauber 1993)

Clipping bzgl. beliebiger (auch konkaver) Polygone:
wichtig z.B. bei Systemen, die das Überlappen mehrerer Fenster auf einem Bildschirm erlauben!

Vorgehensweise:
Bestimme alle n Schnittpunkte des Geradensegments s mit dem Clipping-Polygon P.
Ordne diese nach aufsteigenden Parameterwerten.
Entscheide, welche von den n+1 Segmenten von s zwischen den Schnittpunkten im Inneren von P liegen ("sichtbar sind"):
Liegt der Endpunkt P₁ von s innerhalb von P?
Teststrahl von P₁ aus, zähle Anzahl der Schnittpunkte mit P, Paritätsprüfung (ungerade Þ innerhalb).
Wenn P₁ innerhalb von P: das bei P₁ beginnende und danach jedes zweite Parameterintervall liegen in P.
Sonst genau die hierzu komplementären.

(aus Rauber 1993).

Letzte Änderungen: 4. November 2001.