+ All Categories
Home > Documents > B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen...

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen...

Date post: 06-Apr-2016
Category:
Upload: simon-dittmar
View: 216 times
Download: 2 times
Share this document with a friend
33
B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F A E
Transcript
Page 1: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 1

Rasterungsalgorithmen Teil II

Füllen und Antialiasing

A

D

E

F

A

E

Page 2: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 2

Mündliche PrüfungenFür Informatik-, Sport- und Technikstudenten (nicht CV) 9.-13. Februar22.-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).

Page 3: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 3

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

Page 4: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 4

Füllen von Pixelmengen• Gegeben:

– gerasterte Polygone als Rand-„Pixelmenge“– „Startpunkt“, der festlegt, wo innen ist

• Gesucht: alle Pixel innerhalb des Randes

Page 5: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 5

Füllen: Begriffe

4-Nachbarschaft (von-Neumann-Nachbarschaft)

8-Nachbarschaft

Nachbarschaften

Page 6: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 6

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

Page 7: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 7

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);}

Page 8: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 8

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

Füllen: Rekursiver Algorithmus

Page 9: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 9

Füllen von PolygonenFü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

Page 10: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 10

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);

Page 11: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 11

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 zum Primitiv

gehört nicht zum Primitiv

Füllen von Polygonen

Page 12: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 12

Füllen von PolygonenIterativer 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.

Page 13: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 13

A

B

C

D

E

F

a b c dScanlinie

1 2 3 4 5 6 7 98 10 11 12 13 14

1234567

98

1011

Füllen: Iterativer Algorithmus

Page 14: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 14

Ü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.

Füllen: Iterativer Algorithmus

Page 15: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 15

Füllen: Iterativer Algorithmus• Voraussetzungen:

– Aufbau einer Kantentabelle (edge table, ET) für alle Kanten

– Pro Kante wird notiert:• 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

dx/dy

AB 1 7 3 -5/2BC 1 7 5 6/4FA 3 2 9 0CD 5 13 11 0EF 7 7 9 -5/2DE 7 7 11 6/4

A

B

C

D

E

F

2 7 13 x

11 9 7 5 3 1

y

← (2-7)/(3-1)←(13-7)/(5-1)← 0/6← 0/6← (2-7)/(9-7)← (13-7)/11-7)

Page 16: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 16

• 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

Füllen: Iterativer Algorithmus

Page 17: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 17

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 sinda) Überführe aus der ET diejenigen Einträge in die AET,

für die ymin=y ist und sortiere die AET nach xb) Fülle die Pixel in der Scanlinie y durch Nutzung von

Koordinatenpaaren der AETc) Entferne aus der AET alle die Einträge mit ymax=yd) 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

Füllen: Iterativer Algorithmus

Page 18: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 18

Kanteymin xstart ymax dx/dyAB 1 7 3 -5/2BC 1 7 5 3/2FA 3 2 9 0CD 5 13 11 0EF 7 7 9 -5/2DE 7 7 11 3/2

A

B

C

D

E

F

Kanteymin xstart ymax dx/dyAB 1 7 3 -5/2BC 1 7 5 3/2

Beide Male ist 1 der ymin-Wert einer Kante, daher zeichnen

Kanteymin xstart ymax dx/dyAB 1 9/2 3 -5/2BC 1 17/2 5 3/2

Kanteymin xstart ymax dx/dyFA 3 2 9 0CD 5 13 11 0EF 7 7 9 -5/2DE 7 7 11 3/2

A

C

D

E

F

Füllen zwischen den beiden Einträgen- (9/2, 2) aufrunden (5,2)- (17/2, 2) abrunden (8,2)

Kanteymin xstart ymax dx/dyAB 1 4/2 3 -5/2BC 1 20/2 5 3/2

2 7 13 x

11 9 7 5 3 1

Kantentabelle Aktive Kantentabelle (Zeile 1)

Kantentabelle

Aktive Kantentabelle (Zeile 3)

Aktive Kantentabelle (Zeile 2)

11 9 7 5 3 1

2 7 13 x

Füllen: Iterativer Algorithmus

Page 19: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 19

A

C

D

E

F

A

C

D

E

F

Kanteymin xstart ymax dx/dy

FA 3 2 9 0CD 5 13 11 0EF 7 7 9 -5/2DE 7 7 11 3/2

Kanteymin xstart ymax dx/dyFA 3 2 9 0AB 1 4/2 3 -5/2BC 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

Kanteymin xstart ymax dx/dy

CD 5 13 11 0EF 7 7 9 -5/2DE 7 7 11 3/2

- Füllen zwischen beiden Einträgen, (23/2, 4) auf (11, 4) abrunden

Kanteymin xstart ymax dx/dyFA 3 2 9 0BC 1 26/2 5 3/2

Füllen: Iterativer Algorithmus

2 7 13 x

11 9 7 5 3 1

yAktive Kantentabelle (Zeile 3)

Aktive Kantentabelle (Zeile 4)

2 7 13 x

11 9 7 5 3 1

y

Page 20: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 20

A

D

E

F

A

C

D

E

F

Kanteymin xstart ymax dx/dy

CD 5 13 11 0EF 7 7 9 -5/2DE 7 7 11 3/2

- 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

Kanteymin xstart ymax dx/dyFA 3 2 9 0BC 1 26/2 5 3/2CD 5 13 11 0

Kanteymin xstart ymax dx/dy

EF 7 7 9 -5/2DE 7 7 11 3/2

Füllen zwischen den beiden Einträgen, dabei wird (13, 6) als außen betrachtet

Kanteymin xstart ymax dx/dyFA 3 2 9 0CD 5 13 11 0

Füllen: Iterativer Algorithmus

2 7 13 x

11 9 7 5 3 1

y

Aktive Kantentabelle (Zeile 6)

Page 21: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 21

A

D

E

F

Kanteyminxstart ymax dx/dy

EF 7 7 9 -5/2DE 7 7 11 3/2

Kanteyminxstart ymax dx/dy

FA 3 2 9 0EF 7 7 9 -5/2DE 7 7 11 3/2CD 5 13 11 0

- Füllen zwischen den ersten beiden Ein- trägen. (7, 7) wird als außen betrachtet.- Füllen zwischen den letzten beiden Ein- trägen. (13, 7) wird als außen betrachtet.

Kanteyminxstart ymax dx/dy

FA 3 2 9 0EF 7 9/2 9 -5/2DE 7 17/2 11 3/2CD 5 13 11 0

2 7 13 x

11 9 7 5 3 1

y

Füllen: Iterativer AlgorithmusAktive Kantentabelle (Zeile 7)

Aktive Kantentabelle (Zeile 8)

Page 22: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 22

Füllen: Iterativer Algorithmus

A

D

E

F

Kanteyminxstart ymax dx/dy

-- -- -- -- --

Kanteyminxstart ymax dx/dy

FA 3 2 9 0EF 7 4/2 9 -5/2DE 7 20/2 11 3/2CD 5 13 11 0

- 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

2 7 13 x

11 9 7 5 3 1

yAktive Kantentabelle (Zeile 9)

Page 23: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 23

A

D

E

A

D

E

F

Kante ymin xstart ymax dx/dy-- -- -- -- --

Kanteymin xstart ymax dx/dyDE 7 23/2 11 3/2CD 5 13 11 0

- 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 xstart ymax dx/dy-- -- -- -- --

Kanteymin xstart ymax dx/dyDE 7 26/2 11 3/2CD 5 13 11 0

- Füllen zwischen beiden Einträgen, dabei wird (23/2, 10) zu (12, 10) aufgerundet und (13, 10) als außen betrachtet

Füllen: Iterativer Algorithmus

2 7 13 x

11 9 7 5 3 1

y

11 9 7 5 3 1

y

2 7 13 x

Aktive Kantentabelle (Zeile 10)

Aktive Kantentabelle (Zeile 11)

Page 24: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 24

A

D

E

Kante ymin xstart ymax dx/dy

Kante ymin xstart ymax dx/dy

- Der Pixel (13, 11) wird nicht gesetzt, da er ymax zweier Kanten ist- Kanten DE und CD entfernen

Sowohl ET als auch AET sind leer -- ENDE

A

E

Füllen: Iterativer Algorithmus

2 7 13 x

11 9 7 5 3 1

y Aktive Kantentabelle (Zeile 12)

Page 25: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 25

Füllen: ZusammenfassungEigenschaften:• 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

Page 26: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 26

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

Page 27: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 27

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 UND-Verknüpfung mit dem Muster

Page 28: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 28

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.

Page 29: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 29

AntialiasingDurch 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)

Page 30: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 30

AntialiasingLö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 LinieQuelle: Bender/Brill (2003)

Page 31: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 31

AntialiasingKriterien 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 → VordergrundfarbeSonst: 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.

Page 32: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 32

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.

Page 33: B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II)1 Rasterungsalgorithmen Teil II Füllen und Antialiasing A D E F.

B. Preim AG Visualisierung Rasterungsalgorithmen (Teil II) 33

AntialiasingZusammenfassungBerü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.


Recommended