Pixelgraphiken und
Rasterungsalgorithmen
P
E
M
NE
M1
SE
M2
P
E
B. Preim AG Visualisierung Rasterungsalgorithmen
1
Was ist ein Pixel?
• „picture element“ - unteilbare Einheit eines Rasterbildes
• Gitterförmig angeordnet in Zeilen und Spalten
• Alle Pixel sind gleich große quadratische Bereiche.
• Pixel bedecken ein Bild vollständig (keine Lücken) und
überlappen nicht.
B. Preim AG Visualisierung Rasterungsalgorithmen
2
Pixelgraphiken: Vor-/Nachteile
• Vorteile:
– Einfache Speicherung (einfache Anordnung der Elemente)
– Viele Verarbeitungsmöglichkeiten (Bildverarbeitung)
• Nachteile:
– Diskretisierung einer geometrischen Beschreibung
erforderlich
– Probleme beim Vergrößern, Rotieren, allgemein
Transformieren (Aliasing)
– Hoher Speicherplatzbedarf
B. Preim AG Visualisierung Rasterungsalgorithmen
3
Motivation
• Am Monitor angezeigte Bilder sind Rasterbilder, daher ist
eine Konvertierung von Modellen/Polygonen notwendig.
• Rasterung auch für Druck notwendig
(auch Laserdrucker bauen Bilder aus Pixeln auf)
– RIPs (Raster Image Processors) sind in Laserdruckern
eingebaut.
• Rasterungsalgorithmen werden oft gebraucht, sind
daher zeitkritisch
– Keine aufwändigen Operationen (Multiplikation, Division,
Wurzelziehen, Winkelfunktionen aufwändiger als Addition)
– Möglichst Integer-Arithmetik
– Möglichst einfache Algorithmen
B. Preim AG Visualisierung Rasterungsalgorithmen
4
Rasterung von Linien: Anforderungen
Qualität
• Linien sollten
– Gerade aussehen
– Gleichmäßig hell erscheinen
– Konstante Dicke haben
• Helligkeit sollte unabhängig von Richtung sein
• Endpunkte sollten exakt dargestellt werden.
Effizienz:
• Linienalgorithmus soll schnell sein.
B. Preim AG Visualisierung Rasterungsalgorithmen
5
Linien mathematisch
• Gegeben: zwei Punkte P1(x1,y1) und P2(x2,y2)
• Gesucht: Beschreibung der Linie zwischen P1 und P2
• Variablen:
x=x2-x1
y=y2-y1
Anstieg m=y/x
Beschreibung
1. Explizit:
y = mx + n
m = y/x
n: y-Koordinate des Schnittpunkts mit der y-Achse
B. Preim AG Visualisierung Rasterungsalgorithmen
6
Linien mathematisch
2. Parametrische Beschreibung
x = x1 + t(x2-x1) = x1 + tx
y = y1 + t(y2-y1) = y1 + ty
für t=0 den Punkt (x1,y1)
für t=1 den Punkt (x2,y2)
Alle Punkte der Linie erhält man, wenn man für t alle
Werte aus [0,1] einsetzt.
3. Implizite Beschreibung
–
F(x,y) = ax + by + c = 0
– Für alle Punkte auf der Gerade ist obige Gleichung erfüllt.
B. Preim AG Visualisierung Rasterungsalgorithmen
7
Zeichnen von Linien: Naiver Algorithmus
• Gegeben: Punkte P1(x1,y1) und P2(x2,y2)
jeweils Integer-Koordinaten
• Gesucht: Alle Pixel, die auf der Linie liegen
1. Schritt: Geradengleichung y=mx+n aufstellen
2. Schritt: Iteration von x1 nach x2 im Pixelabstand,
zugehörige y-Werte berechnen, runden, zeichnen
double m = (y2-y1)/(x2-x1) ;
for (int x = x1; x <= x2; x++) {
double y = m*x + n;
setPixel( x, round(y), color);
}
B. Preim AG Visualisierung Rasterungsalgorithmen
8
Zeichnen von Linien: Naiver Algorithmus
Probleme:
double m = (y2-y1)/(x2-x1);
for (int x = x1; x <= x2; x++) {
double y = m*x + n;
setPixel( x, round(y), color);
}
–
–
–
–
–
Rechnen mit Gleitkommawerten bei y und m
Division und Multiplikation verbrauchen Zeit
Runden
Senkrechte Linien – m nicht definiert
Aussehen der Linien bei verschiedenen Anstiegen
B. Preim AG Visualisierung Rasterungsalgorithmen
9
Zeichnen von Linien: Naiver Algorithmus
?
B. Preim AG Visualisierung Rasterungsalgorithmen
10
Rasterung von Linien: Bresenham-Algorithmus
Eigenschaften:
• ausschließlich Integer-Arithmetik
• keine Division, keine komplizierten Multiplikationen
Einschränkungen:
• Pixel liegen auf Integer-Gitter
(keine echte Einschränkung)
• Anstieg der Linie: m < 1, d.h.
(0°  a  45°)
(Verallgemeinerung ist möglich)
B. Preim AG Visualisierung Rasterungsalgorithmen
11
Rasterung von Linien: Bresenham-Algorithmus
Vorbetrachtung:
• Implizite Geradengleichung F(x,y) = ax + by + c = 0
• Hilft zu entscheiden, auf welcher Seite der Geraden
ein gegebener Punkt P(x1,y1) liegt
– ist F(x1,y1)<0  P liegt oberhalb der Geraden
– ist F(x1,y1)>0  P liegt unterhalb der Geraden
– ist F(x1,y1)=0  liegt auf der Geraden
• Dabei ist:
– a = y
– b = -x
B. Preim AG Visualisierung Rasterungsalgorithmen
12
Beispiel für implizite Beschreibung
Gerade: y = ½ x + 2
Betrachten: Strecke von (0;2) bis (4;4)
a = y =2,
b = -x =-4
2x-4y+c = 0
Einsetzen von x=0 und y=2
ergibt c = 8
2x-4y+8 = 0
F (1;1) > 0
F (1;3) < 0
4
3
2
1
0
0
B. Preim AG Visualisierung Rasterungsalgorithmen
4
1
13
Rasterung von Linien: Bresenham-Algorithmus
Grundidee:
NE
P
• Annahme: Steigung der Linie
zwischen 0 und 1
• Gerade gesetztes Pixel ist P
• Entscheidung, welches der
beiden Pixel (E oder NE)
näher am Schnittpunkt der
Linie mit dem Pixelgitter liegt
• Wiederholen bis P(x) = x2
E
B. Preim AG Visualisierung Rasterungsalgorithmen
14
Rasterung von Linien: Bresenham-Algorithmus
Leichter zu bestimmen:
Liegt der Mittelpunkt zwischen E und
NE oberhalb der Linie?
Momentane Position: P(x,y)
Koordinaten von M: M(x+1,y+½)
NE
M
P
E
F(M) = F(x+1,y+½)
Wenn F(M)<0  E nächstes Pixel
Wenn F(M)>=0  NE nächstes Pixel
Wähle d=F(M)=F(x+1,y+½) als
Entscheidungsvariable
B. Preim AG Visualisierung Rasterungsalgorithmen
15
Rasterung von Linien: Bresenham-Algorithmus
• Berechnen von F(M) für ein Pixel, Zeichnen des Pixels,
Berechnen von F(M) für den nächsten x-Wert ...
• Fragestellung: Kann F(M) für den nächsten x-Wert aus
dem F(M) für das gerade berechnete Pixel bestimmt
werden?
– Möglicherweise einfachere Berechnungen
– Schrittweise Weitergehen von Pixel i zu Pixel i+1 (inkrementell)
B. Preim AG Visualisierung Rasterungsalgorithmen
16
Rasterung von Linien: Bresenham-Algorithmus
y+2
M1
NE
y+1
M
P
y
x
M2
E
x+1
x+2
Fall 1: NE als nächstes Pixel ausgewählt
• F(M) = F((x+1), (y+½))
= a(x+1) + b(y+½) + c
dann ist M1 der nächste Mittelpunkt
• F(M1) = F((x+2), (y+3/2))
= a(x+2) + b(y+3/2) + c
Differenz zwischen beiden:
F(M1) - F(M) = a + b
(I)
F(M1) = F(M) + a + b
a=y und b=-x in (I) einsetzen:
F(M1) = F(M) + y – x
d = d + y – x
NE = y - x
B. Preim AG Visualisierung Rasterungsalgorithmen
17
Rasterung von Linien: Bresenham-Algorithmus
y+2
M1
NE
y+1
M
P
y
x
M2
E
x+1
x+2
Fall 2: E ausgewählt
• F(M) = F((x+1), (y+½))
= a(x+1) + b(y+½) + c
M2 ist der nächste Mittelpunkt.
• F(M2) = F((x+2), (y+½))
= a(x+2) + b(y+½) + c
Differenz zwischen beiden:
F(M2) - F(M) = a
(II)
F(M2) = F(M) + a
• Setze a=y in (II) ein:
F(M2) = F(M) + y
d = d + y
E = y
B. Preim AG Visualisierung Rasterungsalgorithmen
18
Rasterung von Linien: Bresenham-Algorithmus
• Algorithmusskizze:
–
–
–
–
Setze erstes Pixel gleich dem Anfangspunkt der Linie
Berechne d=F(M) für dieses Pixel
Wähle E oder NE als nächstes Pixel
Zeichne das Pixel ( setPixel (x,y,color) )
– Aktualisiere d entsprechend der Wahl von E oder NE
– Erhöhe x-Wert um 1
– Wiederhole, solange der Endpunkt nicht erreicht ist
(Vergleich der x-Koordinaten)
• Offene Frage: Initialer Wert von d?
B. Preim AG Visualisierung Rasterungsalgorithmen
19
Rasterung von Linien: Bresenham-Algorithmus
• Initialer Wert von d?
– Startpunkt der Linie sei (x1,y1)
– Erster Mittelpunkt:
F((x1+1), (y1+½)) = a(x1+1) + b(y1+½) + c
= ax1 + a + by1 + ½b + c
= F(x1,y1) + a + ½b
– Startpunkt (x1,y1) liegt auf der Linie, also F(x1,y1)=0
– Initialer Wert der Entscheidungsvariable d = a + ½b
• aber: keine Integer-Werte
–
–
–
–
Entscheidend ist das Vorzeichen von d.
Multiplikation mit 2 hat keinen Einfluss auf das Vorzeichen
Initialer Wert der Entscheidungsvariable d = 2a + b
Inkremente: NE= 2y – 2x und E = 2y
B. Preim AG Visualisierung Rasterungsalgorithmen
20
Rasterung von Linien: Bresenham-Algorithmus
void midpoint-line(int x1, int y1, int x2, int y2, Color color)
{
int dx = x2 – x1; // Bestimme deltaX und deltaY
int dy = y2 – y1;
int d = 2 * dy - dx; // Initialisiere Entscheidungsvariable
int incrE = 2 * dy; // Initialisiere Inkremente
int incrNE = 2 * (dy - dx);
int x = x1;
int y = y1;
setPixel(x1, y1, color); // Setze erstes Pixel
while (x<x2) {
if (d<=0) {
d+=incrE;
x++;
// E -> nur x erhöhen
} else {
d += incrNE;
x++; y++;
// NE -> x und y erhöhen
}
setPixel(x, y, color);
}
}
B. Preim AG Visualisierung Rasterungsalgorithmen
21
• Beispiel: Linie von (0,0) nach (5,3)
Initiale Werte:
x = 5, y = 3,
E=6, NE =-4
d=2 * y - x =1
3
0
0
x=0, y=0, setPixel(0,0,color)
d=1>0  Auswahl NE
 d=d+NE=1-4=-3
 x=1, y=1
setPixel(1,1,color)
d=-3<0  Auswahl E
 d=d+E=-3+6=3
 x=2, y=1
setPixel(2,1,color)
d=3>0  Auswahl NE
 d=d+NE=3-4=-1
 x=3, y=2
setPixel(3,2,color)
d=-1<0  Auswahl E
 d=d+E=-1+6=5
 x=4, y=2
setPixel(4,2,color)
d=5>0  Auswahl NE
 d=d+NE=5-4=1
 x=5, y=3
setPixel(5,3,color)
B. Preim AG Visualisierung Rasterungsalgorithmen
5
22
Rasterung von Linien: Zusammenfassung
• Algorithmus arbeitet ausschließlich mit:
– Integer-Arithmetik
– Additionen
• Inkrementeller Algorithmus, d.h.
– Positionen der Pixel werden aus denen der vorherigen
berechnet.
– Kleine Schleifenkörper
B. Preim AG Visualisierung Rasterungsalgorithmen
23
Rasterung von Linien: Erweiterungen
• Beschränkung des Anstiegs auf 0°  m  45°
– Algorithmus kann erweitert werden auf alle möglichen
Anstiege (Vertauschen von x und y, Vorzeichen, etc.)
– Übungsaufgabe
• Lange Linien werden Pixel für Pixel gezeichnet
– Erweiterungen, die mehrere Pixel im Voraus berechnen
– Linie setzt sich aus „Mustern“ zusammen  Muster finden
und als Gesamtheit setzen.
B. Preim AG Visualisierung Rasterungsalgorithmen
24
Rasterung von Kreisen
Mathematische Beschreibung:
• Gegeben: Zentrum und Radius
• Allgemeine Kreisgleichung für einen Kreis mit dem
Zentrum im Ursprung:
(I)
F(x,y) = x2 + y2 = r2
alle Punkte (x,y), die (I) erfüllen, liegen auf dem Kreis
• Kreisgleichung, wenn Mittelpunkt nicht im Ursprung
liegt, sondern an der Position (xc,yc):
F(x,y) = (x-xc)2 + (y-yc)2 = r2
B. Preim AG Visualisierung Rasterungsalgorithmen
25
Rasterung von Kreisen: Naiver Algorithmus
• Auflösen der Kreisgleichung nach y: y   r 2  x 2
• Schleife über alle x von -r bis r
• Probleme:
- Aufwändige Berechnung
- Wurzel
- Quadrate
- Lücken in der Umgebung
von |x| = r
B. Preim AG Visualisierung Rasterungsalgorithmen
26
Rasterung von Kreisen:
Parametrischer Algorithmus
• Idee: Übergang zur Kreisgleichung in Parameterform
x = r cos 
sowie
y = r sin 
Eigenschaften:
• Keine Lücken in den Bereichen nahe |x|=r
• Schleife über  mit konstanter Schrittweite
• Probleme:
– Berechnungsaufwand für Winkelfunktionen
– Verbesserung: Diskretisierung über Lookup-Tabellen (Winkel,
Funktionswert). Besser aber immer noch ineffizient.
B. Preim AG Visualisierung Rasterungsalgorithmen
27
Rasterung von Kreisen:
Ausnutzen der Symmetrie
(-x,y)
• Verringerung der Anzahl der
Rechenoperationen durch
Nutzung der Symmetrie
(x,y)
(-y,x)
(y,x)
(-y,-x)
(y,-x)
(-x,-y)
(x,-y)
void circlePoints( int x, int y,
int color)
{
setPixel( x, y, color);
setPixel( y, x, color);
setPixel( y, -x, color);
setPixel( x, -y, color);
setPixel( -x, -y, color);
setPixel( -y, -x, color);
setPixel( -y, x, color);
setPixel( -x, y, color);
}
B. Preim AG Visualisierung Rasterungsalgorithmen
28
Rasterung von Kreisen:
Bresenham-Algorithmus
• Herangehensweise wie bei Geraden
• Ziel:
– Integer-Berechnungen
– Eliminieren aufwändiger Operationen
– Inkrementeller Algorithmus
• Basis: implizite Gleichung des Kreises
Die Funktion F(x,y) = x2 + y2 – r2
= 0 für Punkte auf der Kreislinie
< 0 für Punkte innerhalb des Kreises
> 0 für Punkte außerhalb des Kreises
B. Preim AG Visualisierung Rasterungsalgorithmen
29
Rasterung von Kreisen:
Bresenham-Algorithmus
Grundidee:
P
E
M
M1
SE
M2
• Berechnung für alle Pixel im
zweiten Oktanten
• Gerade gesetztes Pixel ist P
• Welches der beiden Pixel E
oder SE muss als nächstes
gesetzt werden?
• Kriterium: Abstand zum Kreis
• Berechne alle anderen
Oktanten über Symmetrie
B. Preim AG Visualisierung Rasterungsalgorithmen
30
Rasterung von Kreisen:
Bresenham-Algorithmus
P
E
M
M1
SE
• Liegt M innerhalb oder
außerhalb des Kreises
entspricht in diesem
Oktanten: liegt M ober- oder
unterhalb der Kreislinie
• Momentane Position: P(x,y)
• Koordinaten von M:
M(x+1,y-½)
• F(M) = F(x+1,y-½)
M2
• Wenn F(M)<0, dann geht
Kreis über M vorbei
 E nächstes Pixel
• Wenn F(M)>=0
 SE nächstes Pixel
• Wähle d=F(M)=F(x+1,y-½)
als Entscheidungsvariable
B. Preim AG Visualisierung Rasterungsalgorithmen
31
Rasterung von Kreisen:
Bresenham-Algorithmus
P
E
M
M1
SE
M2
• Fall 1: d<0  E als nächstes
Pixel ausgewählt
F(M)=F((x+1), (y-½))
=(x+1)2+(y-½)2-r2
dann ist M1 der nächste
Mittelpunkt
• F(M1)=F((x+2),(y-½))
=(x+2)2+(y-½)2-r2
• Differenz zwischen beiden:
 F(M1)-F(M) = 2x + 3
 d = d + (2x + 3)
 E = (2x + 3)
B. Preim AG Visualisierung Rasterungsalgorithmen
32
Rasterung von Kreisen:
Bresenham-Algorithmus
•
P
•
E
M
M1
•
SE
M2
=
=




Fall 2: d0  SE als nächstes
Pixel ausgewählt
F(M)=F((x+1), (y-½))
=(x+1)2+(y-½)2-r2
dann ist M2 der nächste
Mittelpunkt
F(M2)=F((x+2),(y-3/2))
=(x+2)2+(y-3/2)2-r2
Differenz zwischen beiden:
(y-3/2)2 - (y-½)2
y²-3y+9/4 – (y²-y+1/4)
-2y+2
F(M2)-F(M) = 2x +3 -2y +2
F(M2)-F(M) = 2x –2y + 5
d = d + (2x – 2y + 5)
SE = (2x – 2y + 5)
B. Preim AG Visualisierung Rasterungsalgorithmen
33
Rasterung von Kreisen:
Bresenham-Algorithmus
• Initialer Wert von d
– Erstes Pixel des Kreises (besser: des berechneten
Kreisausschnittes) ist P(0,r)
– Erster Mittelpunkt ist damit M(1,r-½)
d = F(1, r-½) = 12 + (r-½)2 - r2 = 5/4 – r
• aber: kein Integer-Wert
–
–
–
–
Neue Entscheidungsvariable h ::= d – 1/4
Anfangswert: hstart = 1 – r
Entscheidungskriterium: d < 0 wird zu h < -1/4
Da die Berechnung von h mit ganzzahligen Werten beginnt
und h nur ganzzahlig (durch E, SE) inkrementiert wird,
kann h<-1/4 durch h<0 ersetzt werden
B. Preim AG Visualisierung Rasterungsalgorithmen
34
void MidpointCircle (int radius, int color)
{
int x = 0; /* Initialisierung */
int y = radius;
int d = 1 - radius;
circlePoints (x, y, color); // Symmetrie nutzen -> 8 Punkte
while (y > x) {
if (d < 0)
{ /* Auswahl von E */
d = d + 2*x +3;
x = x + 1
} else { /* Auswahl von SE */
d = d + 2*(x-y) + 5;
x = x + 1;
y = y - 1;
}
circlePoints (x, y, color); // Symmetrie nutzen->8 Punkte
}
}
B. Preim AG Visualisierung Rasterungsalgorithmen
35
• Beispiel:
Kreis um (0,0) Radius 6
• Initialisierung:
x=0, y=6, d=1-r =-5
6
3
0
4
Rasterung von Kreisen:
Bresenham-Algorithmus
x=0, y=6, d=-5, circlePoints(0,6,c)
d=-5<0  Auswahl E
 d=d+2x+3=-2
 x=x+1=1, y = 6
circlePoints(1,6,c)
d=-2<0  Auswahl E
 d=d+2x+3=5
 x=x+1=2, y=6
circlePoints(2,6,c)
d=5>0  Auswahl SE
 d=d+2(x-y)+5=2
 x=x+1=3, y=y-1=5
circlePoints(3,5,c)
d=5>0  Auswahl SE
 d=d+2(x-y)+5=3
 x=x+1=4, y=y-1=4
circlePoints(4,4,c)
B. Preim AG Visualisierung Rasterungsalgorithmen
36
Rasterung von Kreisen:
Bresenham-Algorithmus
Erweiterungen:
• Algorithmus relativ effizient, weil:
–
–
–
–
inkrementeller Algorithmus
Integer-Arithmeik
Nur 1/8 des Kreises muss berechnet werden
Multiplikationen mit 2 nicht so kritisch (Bitverschiebung)
• Aber:
– Immer noch Multiplikationen notwendig, um die Inkremente zu
berechnen
E = (2x + 3) und SE = (2x – 2y + 5)
– Linienalgorithmus arbeitet mit konstanten Inkrementen
• Geht das hier auch?
– Idee:
Berechnen der Inkremente E und SE auch inkrementell
– Vorgehen: Betrachten zwei Pixelschritte
B. Preim AG Visualisierung Rasterungsalgorithmen
37
Rasterung von Kreisen:
Bresenham-Algorithmus
Differenzen zweiter Ordnung
• Fall 1: im aktuellen Schritt wurde E gewählt
– Bewertungspunkt (aktuelles Pixel) wandert von (x,y) nach
(x+1,y)
– Inkremente am „alten“ Pixel (x,y) waren:
Eal t =2x + 3
SEalt=2x – 2y + 5
– Inkremente am neuen Pixel wären:
Eneu = 2(x+1) + 3
SEneu= 2(x+1) – 2y + 5
– Differenzen zwischen beiden:
Eneu- Ealt = 2
SEneu- SEalt = 2
B. Preim AG Visualisierung Rasterungsalgorithmen
38
Rasterung von Kreisen:
Bresenham-Algorithmus
Differenzen zweiter Ordnung
• Fall 2: im aktuellen Schritt wurde SE gewählt
– Bewertungspunkt (aktuelles Pixel) wandert von (x,y) nach
(x+1,y-1)
– Inkremente am „alten“ Pixel (x,y) waren
Ealt=2x +3
SEalt=2x –2y + 5
– Inkremente am „neuen“ Pixel wären:
Eneu=2(x+1) +3
SEneu=2(x+1) –2(y-1) + 5
– Differenzen zwischen beiden:
Eneu- Ealt = 2
SEneu- SEalt = 4
B. Preim AG Visualisierung Rasterungsalgorithmen
39
void MidpointCircle(int radius, int color)
{
int x = 0;
int y = radius;
int d = 1 − radius;
int deltaE = 3;
int deltaSE = −2 * radius + 5;
circlePoints(x, y, color); /* draws 8 points */
while (y > x) {
if (d < 0) { /* select E */
d += deltaE;
deltaE += 2;
deltaSE += 2;
} else { /* select SE */
d += deltaSE;
deltaE += 2;
deltaSE += 4;
y−−;
}
x++;
circlePoints(x, y, color);
}
B. Preim AG Visualisierung Rasterungsalgorithmen
}
40
Rasterung von Ellipsen: Grundlegendes
• Gleichung der Ellipse mit Mittelpunkt im Ursprung
F(x,y) = b2x2 + a2y2 – a2b2 = 0
• Betrachten nur „achsenparallele“ Ellipsen
• Algorithmus für ersten Quadranten reicht aus
(Symmetrie)
• Ziel: inkrementeller Mittelpunkt-Algorithmus
b
-a
a
-b
B. Preim AG Visualisierung Rasterungsalgorithmen
41
Rasterung von Ellipsen:
Inkrementeller Algorithmus
• Schwierigkeit: 2 Gebiete mit
– 1. Gebiet: Auswahl zwischen E und SE
– 2. Gebiet: Auswahl zwischen SE und S
• Grenze: Punkt, an dem die Ellipse den Anstieg –1 hat
• ohne Herleitung:
– Übergang, der erste Mittelpunkt, für den gilt: a2(y-½)b2(x-1)
B. Preim AG Visualisierung Rasterungsalgorithmen
42
Rasterung von Ellipsen:
Inkrementeller Algorithmus
• Gebiet 1: Mittelpunkt liegt zwischen E und SE
(I )dalt  F x 1, y  12   b2 ( x 1)2  a2  y  12   a2b2
2
– Wahl von E als nächstes Pixel
(II )dneu  F x  2, y  12   b2 ( x  2)2  a2  y  12   a2b2
2
( II )  ( I ) E  dneu  dalt  b2 (2x  3)
– Wahl von SE als nächstes Pixel
(III)dneu  F x  2, y 
3
2
  b (x  2)
2
2
 a y 
2

3 2
2
 a2b2
( III)  ( I ) E  dneu  dalt  b2 (2x  3)  a2 (2 y  2)
• Gebiet 2: Mittelpunkt liegt zwischen SE und S - analog
B. Preim AG Visualisierung Rasterungsalgorithmen
43
Rasterung von Ellipsen:
Inkrementeller Algorithmus
• Initialer Wert für d:
– (0,b) sei das erste Pixel, damit (1,b-½) der erste Mittelpunkt
F (1, b  12 )  b 2  a 2 (b  12 ) 2  a 2b 2 
 b 2  a 2b²  a ²b  a ² 14  a 2b 2  b 2  a 2 (b  14 )  d
– Beim Wechsel der Gebiete ist ein neuer Initialwert für d zu
berechnen. Er liegt zwischen S und SE bei (x+½, y-1)
F (x  12 , y  1)  b 2 (x  12 )2  a 2 (y  1)2  a 2b 2  d
– sonst Algorithmus wie beim Kreis
– Ausnutzen der vierfachen Symmetrie:
void ellipsePoints (int x, int y, int color)
{ setPixel (x, y, color); setPixel (x,-y, color);
setPixel (-x, y, color; setPixel (-x,-y, color);
}
B. Preim AG Visualisierung Rasterungsalgorithmen
44
void MidpointEllipse(int a, int b, int color)//Ellipse mit Mittelpunkt
(0;0)
{
int x = 0; int y = b;
double d = b*b-a*a*b-(a*a/4); //Initialisierung von d für 1. Oktanten
ellipsePoints( x, y, color);
//Setze 4 Punkte
while( a*a*(y-0.5) > b*b*(x-1)) {
if (d < 0) // East
d += b*b*(2*x+3);
else {
// SouthEast
d += (b*b*(2*x+3)+a*a*(-2*y+2));
y--;
}
x++
ellipsePoints( x, y, color); // Setze 4 Punkte
}
d = b*b*(x+.5)*(x+.5)+a*a*(y-1)*(y-1)-a*a*b*b; // Initialisierung von d
while (y > 0) {
if (d < 0) { //SouthEast
d += b*b*(2*x+2)+a*a*(-2*y+3);
x++;
}
else
// South
d += a*a*(-2*y+3);
y--;
ellipsePoints( x, y, color);
}
B. Preim AG Visualisierung Rasterungsalgorithmen
45
}
Rasterung von Ellipsen: Zusammenfassung
• Algorithmus kann erweitert werden:
–
–
–
–
Ellipsen nicht im Ursprung (trivial)
Ellipsen nicht achsenparallel (schwierig)
Differenzen zweiter Ordnung (trivial)
Float-Berechnungen (schwieriger)
• Eigenschaften:
– inkrementeller Algorithmus
– relativ einfache Berechnungen
B. Preim AG Visualisierung Rasterungsalgorithmen
46
Zusammenfassung Rasteralgorithmen
• werden oft benutzt, daher besondere Anforderungen:
– schnell
– einfach
– Integer-Arithmetik
• inkrementelle Algorithmen
– nach dem Mittelpunkt-Schema
– Linien, Kreise, Ellipsen
– erweiterbar für allgemeine Lagen der Primitive
• Beispiel für Herleitung von Algorithmen in der
Rastergraphik
B. Preim AG Visualisierung Rasterungsalgorithmen
47
Offene Probleme
• Rasterung allgemeiner Kurven
– CAGD-Vorlesung
• Beim Rastern wurden alle Pixel mit einer Farbe
gesetzt, das führt zu Artefakten – Aliasing.
– Antialiasing – nächste Vorlesung
• Darstellung des Inneren von Graphikprimitiven?
– Füllen – nächste Vorlesung
B. Preim AG Visualisierung Rasterungsalgorithmen
48

Rasterung von Kreisen