Rasterungsalgorithmen Teil II
Füllen und Antialiasing
D
F
E
A
E
A
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
1
Mündliche Prüfungen
Für Informatik-, Sport- und Technikstudenten (nicht CV)
9.-13. Februar
22.-27. März
Einschreibung im ISG-Sekretariat bei Frau Janka
(29-217)
Inhaltlich:
Ein Thema (Vorlesung 1-11) kann „aussortiert“ werden
und wird nicht geprüft.
Geschichte der CG (Vorl. 1) wird nicht geprüft. Vorlesung
12 (Texturemapping, Schatten … auch nicht).
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
2
Füllen:
Zu lösendes Problem
• Polygon gegeben durch
– Geometrische Beschreibung (Ecken, Kanten)
– Pixelmenge (entsteht durch Rasterung der Kanten)
• Fragen:
– Welche Pixel bilden das Innere der Fläche und sind daher
einzufärben, wenn die Fläche gefüllt werden soll?
– Womit (welche Farbe) sind die Pixel zu füllen?
• Füllalgorithmen für:
– Polygone, deren Rand als Pixelmenge gegeben ist,
– Polygone, die durch Kanten gegeben sind
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
3
Füllen von Pixelmengen
• Gegeben:
– gerasterte Polygone als Rand-„Pixelmenge“
– „Startpunkt“, der festlegt, wo innen ist
• Gesucht: alle Pixel innerhalb des Randes
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
4
Füllen: Begriffe
Nachbarschaften
4-Nachbarschaft
(von-Neumann-Nachbarschaft)
8-Nachbarschaft
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
5
Füllen: Begriffe
• Kante: Verbindung
zweier Eckpunkte
• Scanlinie:
horizontale Linie auf
Höhe einer
Rasterzeile
• Spanne: Abschnitt
auf einer Scanlinie
zwischen zwei
Schnittpunkten mit
Polygonkanten
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
6
Füllen: Rekursiver Algorithmus
•
•
•
Bestimmung der Zugehörigkeit zum Rand erfolgt über Pixelfarbe, daher
einfarbiger Rand
Beginne mit einem Startpixel
Teste, ob das aktuelle Pixel auf dem Rand liegt (getPixel(x,y) ).
– wenn ja, dann ist nichts zu füllen
– wenn nein, dann fülle die {4er, 8er}-Nachbarschaft
void floodFill( int x, int y, int fillColor, int border)
{ // 4er-Nachbarschaft
if ((getPixel(x, y) == border) ||
(getPixel(x, y) == fillColor)) {return;}
setPixel( x, y, fillColor);
floodFill( x, y+1, fillColor, border);
floodFill( x, y-1, fillColor, border);
floodFill( x+1, y, fillColor, border);
floodFill( x-1, y, fillColor, border);
}
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
7
Füllen: Rekursiver Algorithmus
Probleme:
•
•
•
•
Rekursion → hoher Berechnungsaufwand
mehrfaches Testen von Pixeln
„spill-out“ bei Lücken in den Rändern
Rand bei Verwendung der 8-Nachbarschaft
muss auch diagonal dicht definiert sein
Vorteile:
• Es muss nichts über die Geometrie des zu
füllenden Gebietes bekannt sein!
• Keine langwierigen Berechnungen
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
8
Füllen von Polygonen
Füllalgorithmen auf Basis einer geometrischen Beschreibung
• Füllen von Polygonen, die definiert sind durch
– Liste von Eckpunkten (engl. Vertices) {V} und dazwischen liegenden
Kanten (engl. edges) {E}
– Kante von vi zu Eckpunkt vi+1 für i: 1 i < n
– Kante von vn nach v1 schließt das Polygon
Konvexe Polygone: Wenn P1 und P2 zum Polygon
gehören, gehören auch alle Punkte auf der Verbindung
zwischen P1 und P2 zum Inneren des Polygons
Konkave Polygone: ... Auch mit
Selbstüberschneidungen
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
9
Einstieg: Füllen von Rechtecken
• Füllen mit einheitlicher Farbe
• Rechteck definiert durch zwei Ecken (xmin, ymin) und
(xmax, ymax)
• Algorithmus:
for (y=ymin; y<=ymax; y++)
for (x=xmin; x<=xmax; x++)
writePixel (x, y, color);
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
10
Füllen von Polygonen
Definition:
• Pixel auf einer Kante gehören nicht zum Primitiv, wenn die
durch die Kante definierte Halbebene, die das Primitiv enthält,
unter dieser Kante oder links von ihr liegt.
• Pixel auf einer Kante gehören zum Primitiv, wenn die
Halbebene, die das Primitiv enthält, oberhalb oder rechts liegt.
gehört nicht zum Primitiv
gehört zum Primitiv
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
11
Füllen von Polygonen
Iterativer Algorithmus:
• Abtasten (Scannen) des Polygons Pixelzeile für
Pixelzeile von unten nach oben (mit Scanlinien)
• Suche alle Schnittpunkte der Scanlinien mit
Polygonkanten
• Sortiere die Schnittpunkte nach wachsenden
x-Koordinaten
• Fülle alle Pixel zwischen Schnittpunkten nach Parität:
Parität ist anfangs 0 und wechselt bei jedem
Schnittpunkt. Gezeichnet wird bei Parität 1.
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
12
Füllen: Iterativer Algorithmus
D
11
10
F
9
8
a
7
E
b
c
d
Scanlinie
6
5
C
4
3
A
2
B
1
1
2
3
4
5
6
7
8
9
10 11 12 13 14
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
13
Füllen: Iterativer Algorithmus
Überlegungen/Sonderfälle
• Wie bestimmt man für einen nicht-ganzzahligen Schnittpunkt,
welches der beiden Nachbarpixel innen liegt?
Erreicht man den Schnittpunkt, während man „innen“ ist, wird
abgerundet, während man „außen“ ist, wird aufgerundet.
• Wie verfährt man mit Eckpunkten an ganzzahligen Pixelkoordinaten?
Ein ganzzahliger Schnittpunkt wird am Beginn einer Spanne als
„innen“; am Ende einer Spanne als „außen“ betrachtet.
• Wie verfährt man mit doppelt belegten Schnittpunkten?
Der ymin-Wert einer Kante wird als zugehörig, der ymax-Wert einer
Kante als nicht zugehörig betrachtet.
• Wie verfährt man mit horizontalen Kanten?
Untere Kanten werden dargestellt, obere nicht.
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
14
Füllen: Iterativer Algorithmus
• Voraussetzungen:
– Aufbau einer Kantentabelle (edge table, ET) für alle Kanten
– Pro Kante wird notiert:
•
•
•
•
y
11
ymin= unterer y-Wert
xstart= x-Wert an dem Punkt mit ymin (kann größerer x-Wert sein!)
ymax= oberer y-Wert
t=dx/dy=horizontaler Versatz zwischen zwei Scanlines (entspricht
1/Anstieg)
Kante ymin xstart ymax
AB
1
7
3
BC
1
7
5
FA
3
2
9
CD
5
13 11
EF
7
7
9
DE
7
7
11
D
F
9
E
7
C
5
A
3
B
1
2
7
13
dx/dy
-5/2
6/4
0
0
-5/2
6/4
← (2-7)/(3-1)
←(13-7)/(5-1)
← 0/6
← 0/6
← (2-7)/(9-7)
← (13-7)/11-7)
x
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
15
Füllen: Iterativer Algorithmus
• Algorithmus iteriert über Scanlinien und baut eine
Aktivkantentabelle (active edge table, AET) auf.
• AET enthält nach wachsenden x-Werten sortierte
Schnittpunkte von Scanlinien mit Polygonkanten.
• Spannen zwischen Paaren von solchen
Schnittpunkten (Einträge in der AET) werden gefüllt.
• AET wird beim Übergang zur nächsten Scanlinie
aktualisiert.
• Algorithmus endet, wenn AET leer ist
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
16
Füllen: Iterativer Algorithmus
1. Weise y den kleinsten in der ET vorkommenden
Wert zu
2. Initialisiere die AET mit dem Anfangszustand „leer“
3. Wiederhole bis ET und AET leer sind
a) Überführe aus der ET diejenigen Einträge in die AET, für die
ymin=y ist und sortiere die AET nach x
b) Fülle die Pixel in der Scanlinie y durch Nutzung von
Koordinatenpaaren der AET
c) Entferne aus der AET alle die Einträge mit ymax=y
d) Inkrementiere y (nächste Scanlinie)
e) Aktualisiere für jede nicht vertikale Kante (dx/dy !=0) der
AET den xstart-Wert für das neue y
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
17
Füllen: Iterativer Algorithmus
Kantentabelle
11
9
F
7
E
5
3
C
A
1
B
2
7
A
1
7
13
Kante ymin
x
xstart
ymax dx/dy
AB
1
7
3
-5/2
AB
1
7
3
-5/2
BC
1
7
5
3/2
BC
1
7
5
3/2
FA
3
2
9
0
CD
5
13
11
0
EF
7
7
9
-5/2
DE
7
7
11
3/2
Beide Male ist 1 der ymin-Wert einer
Kante, daher zeichnen
Aktive Kantentabelle (Zeile 2)
Kante ymin
Kante ymin
C
2
ymax dx/dy
Kantentabelle
E
5
xstart
x
F
7
3
13
D
11
9
Kante ymin
D
Aktive Kantentabelle (Zeile 1)
xstart
ymax dx/dy
FA
3
2
9
0
CD
5
13
11
0
EF
7
7
9
-5/2
DE
7
7
11
3/2
xstart
ymax dx/dy
AB
1
9/2
3
-5/2
BC
1
17/2
5
3/2
Füllen zwischen den beiden Einträgen
- (9/2, 2) aufrunden (5,2)
- (17/2, 2) abrunden (8,2)
Aktive Kantentabelle (Zeile 3)
Kante ymin
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
xstart
ymax dx/dy
AB
1
4/2
3
-5/2
BC
1
20/2
5
3/2
18
y
Füllen: Iterativer Algorithmus
11
9
E
C
A
1
2
7
y
11
13
FA
3
2
9
0
CD
5
13
11
0
EF
7
7
9
-5/2
DE
7
7
11
3/2
x
Kante ymin
D
Aktive Kantentabelle (Zeile 3)
xstart
ymax dx/dy
xstart
ymax dx/dy
FA
3
2
9
0
AB
1
4/2
3
-5/2
BC
1
20/2
5
3/2
- ymin der Kante FA entfällt
- Füllen zwischen den beiden letzten
Einträgen, dabei ist erster Punkt als
innen, letzter als außen betrachtet
- Kante AB entfernen
- Füllen zwischen beiden Einträgen,
(23/2, 4) auf (11, 4) abrunden
Aktive Kantentabelle (Zeile 4)
F
7
E
5
3
ymax dx/dy
Kante ymin
5
9
xstart
F
7
3
Kante ymin
D
Kante ymin
C
A
1
2
7
13
xstart
ymax dx/dy
CD
5
13
11
0
FA
3
2
9
0
EF
7
7
9
-5/2
BC
1
26/2
5
3/2
DE
7
7
11
3/2
x
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
19
Füllen: Iterativer Algorithmus
y
11
9
xstart
ymax dx/dy
Kante ymin
F
7
E
5
3
Kante ymin
D
C
A
1
2
7
13
CD
5
13
11
0
EF
7
7
9
-5/2
DE
7
7
11
3/2
x
xstart
ymax dx/dy
FA
3
2
9
0
BC
1
26/2
5
3/2
CD
5
13
11
0
- ymin der Kante CD entfällt
- Füllen zwischen den ersten beiden
Einträgen, dabei wird (26/2, 5) als
außen betrachtet
- Kante BC entfernen
Aktive Kantentabelle (Zeile 6)
D
Kante ymin
xstart
ymax dx/dy
Füllen zwischen den beiden Einträgen,
dabei wird (13, 6) als außen betrachtet
F
Kante ymin
E
A
EF
7
7
9
-5/2
DE
7
7
11
3/2
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
xstart
ymax dx/dy
FA
3
2
9
0
CD
5
13
11
0
20
Füllen: Iterativer Algorithmus
Aktive Kantentabelle (Zeile 7)
y
11
9
Kante ymin
D
xstart
ymax dx/dy
Kante ymin
F
E
7
5
3
A
1
2
7
13
x
EF
7
7
9
-5/2
DE
7
7
11
3/2
xstart
ymax dx/dy
FA
3
2
9
0
EF
7
7
9
-5/2
DE
7
7
11
3/2
CD
5
13
11
0
- Füllen zwischen den ersten beiden Einträgen. (7, 7) wird als außen betrachtet.
- Füllen zwischen den letzten beiden Einträgen. (13, 7) wird als außen betrachtet.
Aktive Kantentabelle (Zeile 8)
Kante ymin
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
xstart
ymax dx/dy
FA
3
2
9
0
EF
7
9/2
9
-5/2
DE
7
17/2
11
3/2
CD
5
13
11
0
21
Füllen: Iterativer Algorithmus
Aktive Kantentabelle (Zeile 9)
y
11
Kante ymin
D
9
--
F
7
E
5
--
xstart
--
ymax dx/dy
--
--
- Füllen zwischen den ersten beiden
Einträgen, (9/2, 8) zu (4, 8) abgerundet
- Füllen zwischen den letzten beiden
Einträgen, (17/2, 8) wird zu (9, 8)
aufgerundet
xstart y
Kante y
dx/dy
min
3
A
1
2
7
13
x
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
max
FA
3
2
9
0
EF
7
4/2
9
-5/2
DE
7
20/2
11
3/2
CD
5
13
11
0
22
Füllen: Iterativer Algorithmus
y
11
9
D
F
Kante
ymin
xstart
ymax
dx/dy
--
--
--
--
--
E
7
5
3
A
1
Aktive Kantentabelle (Zeile 10)
- Füllen zwischen den ersten beiden
Einträgen, dabei wird (2, 9) nicht
gesetzt, da er ymax zweier Kanten ist.
- Füllen zwischen den letzten beiden
Einträgen, dabei wird (13, 9) als
außen betrachtet
- Entfernen von FA und EF
Kante ymin
2
7
y
11
13
x
D
9
7
E
Kante
ymin
xstart
ymax
dx/dy
--
--
--
--
--
7
23/2
11
3/2
CD
5
13
11
0
Aktive Kantentabelle (Zeile 11)
- Füllen zwischen beiden Einträgen,
dabei wird (23/2, 10) zu (12, 10)
aufgerundet und (13, 10) als außen
betrachtet
Kante ymin
A
1
2
7
13
ymax dx/dy
DE
5
3
xstart
xstart
ymax dx/dy
DE
7
26/2
11
3/2
CD
5
13
11
0
x
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
23
Füllen: Iterativer Algorithmus
y
11
Kante
D
ymin
xstart
dx/dy
Aktive Kantentabelle (Zeile 12)
- Der Pixel (13, 11) wird nicht gesetzt,
da er ymax zweier Kanten ist
- Kanten DE und CD entfernen
9
7
ymax
E
5
3
Kante
A
ymin
xstart
ymax
dx/dy
1
2
7
13
x
Sowohl ET als auch AET sind leer -- ENDE
E
A
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
24
Füllen: Zusammenfassung
Eigenschaften:
• Effizienter Algorithmus
• Beliebige Polygone (auch konkave)
• Vereinfachung für konvexe Polygone möglich (immer
nur eine Spanne)
• Performance-Gewinn durch
– Schnelles Sortieren
– Integer-Arithmetik (beim Addieren von dx/dy)
• Wird häufig angewendet, u.a. beim Shading in der
3D-Computergraphik
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
25
Füllen mit Mustern
• Muster als Bitmap (Textur = 2D Bild) gegeben, soll in
das Innere eines Polygons übertragen werden
• keine einheitliche Farbe, daher direkte Zuordnung zu
füllendes Pixel auf Texturpixel notwendig
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
26
Füllen mit Mustern: Zwei Modi
• Verankerung der linken unteren Textur-Ecke in einer Polygonecke
– Muster ist mit Polygon verbunden, bewegt sich bei
Animationen mit dem Polygon
• Verankerung der Textur auf dem Hintergrund
– Muster nicht mit Polygon verbunden, Polygon bewegt sich
„über“ der Textur
– Belegen der Polygonpixel mit dem Wert 1 und logische UNDVerknüpfung mit dem Muster
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
27
Zusammenfassung Füllen mit Mustern
• Einfache Erweiterung der Füllalgorithmen
– Keine einheitliche Farbe
– stattdessen: Lookup der Pixelfarbe in der Textur
– Verknüpfen der Texturfarbe mit der Hintergrundfarbe in
verschiedenen Modi:
• Farben verknüpfen (Interpolation, verschiedene Verfahren)
• Textur-Farbwert für weitere Berechnungen verwenden
• Verwendung beim Rendering:
– Shading in Verbindung mit Texturierung
– Texture Mapping, Bump Mapping, etc.
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
28
Antialiasing
Durch die Diskretisierung in das Pixelraster entstehen
sichtbare Artefakte (Aliasing). Diese sind besonders
offensichtlich, wenn die Pixelauflösung groß ist und
wenn die Kontraste zwischen Vordergrund- und
Hintergrund groß sind.
Ursache:
begrenzte Zahl der Pixel und ihre
feststehende Größe und Position.
Aliasing bei einer kurzen und langen Linie
Quelle: Bender/Brill (2003)
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
29
Antialiasing
Lösungsmöglichkeiten (Antialiasing):
Anstelle der binären Entscheidung Pixel gesetzt Ja/Nein,
wird eine „weichere“ Entscheidung getroffen und
Pixel werden ggf. mit Zwischenfarben gesetzt. Bei
einer schwarzen Linie auf weißem Grund werden
Grautöne verwendet.
Antialiasing bei einer kurzen und langen Linie
Quelle: Bender/Brill (2003)
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
30
Antialiasing
Kriterien für die Einfärbung der Pixel:
1. Abstand d des Pixelzentrums zum Schnittpunkt mit der
Linie (oder dem Kreis bzw. der Ellipse).
Wenn d > 1: → Setze Hintergrundfarbe,
Sonst:
→ Interpoliere linear zwischen Vordergrund- und
Hintergrundfarbe (Farbraum beachten)
2. Bestimme Flächeninhalt des Pixels, der von dem Primitiv bedeckt
wird, als Kriterium.
Wenn Pixel vollständig bedeckt → Vordergrundfarbe
Sonst: wiederum Interpolation
3. Bestimme Flächeninhalt, der bedeckt wird, aber wichte Teilflächen
nach ihrem Abstand zum Pixelmittelpunkt (gewichtete
Flächenbewertung). Entspricht einer Integration im Ortsbereich.
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
31
Antialiasing
• Aliasing ist auch in bewegten Bildern
(Computeranimationen) ein Problem. Man spricht von
zeitlichem Aliasing (im Unterschied zum
örtlichen/räumlichen Aliasing)
• Zeitliches Aliasing kann dazu führen, dass sehr
kurzzeitige Effekte nicht dargestellt werden oder
dazu, dass kleine Objekte in einzelnen Bildern
aufblitzen und in anderen verschwinden.
• Ähnlich wie beim räumlichen Antialiasing wird eine
Integration über den Zeitraum zwischen zwei
diskreten Bildern angenähert, um Effekte zu mildern.
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
32
Antialiasing
Zusammenfassung
Berücksichtigung der partiellen Belegung eines Pixels
durch ein Graphikprimitiv
• ermöglicht bessere Darstellungsqualität,
• führt zu Bildern mit „vielen“ Grauwerten bzw. Farben
• führt zu höheren Berechnungszeiten, wobei prinzipiell
inkrementelle Algorithmen erweitert werden können.
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)
33

Füllen: Iterativer Algorithmus