3. 2D-Darstellungselemente Flashcards
1. Rastern von Linien 2. Antialiasing 3. Approximation von Kurven (21 cards)
Rastern von Linien
Welche Forderungen hat man an den Algorithmus? (4)
Algorithmus soll:
-> möglichst effizient sein
(kurze Laufzeit)
- > einfach zu implementieren sein
- > ein treffendes Ergebnis liefern
- > eine konstante Helligkeit, unabhängig von der Steigung berechnen
Rastern von Linien
Welche 3 Algorithmen gibt es dazu?
- Basisalgorithmus
- Inkrementeller Algorithmus
- Bresenham Algorithmus (Mittelpunktschema)
Rastern von Linien
- Basisalgorithmus
Wie funktioniert er?
Basisalgorithmus
-> hier wird die Anzahl der Schritte in x-Richtung mit der Steigung pro Schritt multipliziert
(+ y-Achsenabschnitt)
-> der Wert wird dann gerundet
________________
Gegeben:
P_0 (x0, y0), P_1 (x1, y1)
Gesucht:
Gerasterte Linie von P_0 nach P_1
Geradengleichung:
y = m * x + B
mit
m = Steigung
B = y-Achsenabschnitt
Rastern von Linien
- Basisalgorithmus
Nachteile? (2)
-> ist die Steigung größer als 1 oder -1 muss eine Fallunterscheidung stattfinden
-> jedes Mal ist eine Multiplikation und eine Addition nötig, Wert wird gerundet
=> ineffizient!
Rastern von Linien
- Inkrementeller Algorithmus
Wie wird er noch bezeichnet?
Wie funktioniert er?
Was gilt für alle Punkte auf der Geraden?
Inkrementeller Algorithmus
-> es wird für den jeweils nächsten Wert, die Steigung pro Schritt auf den alten Wert dazu addiert
(in jedem Schritt wird x um 1 und y um die erste Ableitung m = dy erhöht)
____________________
-> für alle Punkte (xi, yi) auf der Geraden gilt:
Wenn xi+1 = xi + 1,
so ist yi+1 = yi + m
Rastern von Linien
- Inkrementeller Algorithmus
Vorteil? (1)
Nachteile? (2)
Inkrementeller Algorithmus
Vorteil:
-> keine Multiplikation mehr nötig
____________________
Nachteile:
-> eine Fallunterscheidung zwischen m <= 1 und m > 1 ist nötig, da dann nicht mehr
xi+1 = xi + 1 gilt
(das nächste Pixel muss dann möglicherweise direkt über dem Vorigen gezeichnet werden)
-> immer noch mathematische Rundung
Rastern von Linien
- Bresenham Algorithmus (Mittelpunktschema)
Was ist die Idee davon?
Idee:
-> Berechnung einer Entscheidungsvariablen
d = F(M)
-> Algorithmus muss in jeder Spalte nur zwischen 2 Pixeln unterscheiden
(Ost-Pixel ‚E‘ und Nord-Ost-Pixel ‚NE‘)
Rastern von Linien
- Bresenham Algorithmus (Mittelpunktschema)
Welche 3 Ergebnismöglichkeiten gibt es für diesen Algorithmus?
Bresenham Algorithmus
3 Ergebnismöglichkeiten für den Algorithmus:
auf der Linie:
F(x,y) = 0 => E
über der Linie:
F(x,y) > 0 => NE
über der Linie:
F(x,y) < 0 => E
Rastern von Linien
- Bresenham Algorithmus (Mittelpunktschema)
Vorteile? (3)
Bresenham Algorithmus
Vorteile:
-> nur ganzzahlige Addition nötig
-> Keine Multiplikation, keine Rundung
-> sehr effizient
(optimaler Algorithmus)
Rastern von Linien
Was sind die Probleme aller Algorithmen?
Was schafft Abhilfe?
(Lösung)
Probleme aller Algorithmen:
-> Intensität der Geraden je nach Steigung unterschiedlich
(Diagonale Linien haben z.B. nur eine Intensität von I
(wenn I die Intensität pro Längeneinheit einer
√2 horizontalen Linie ist)
_________________
Abhilfe: Antialiasing
Antialiasing
Wann tritt Aliasing auf?
Welche Gründe gibt es dafür? (2)
Antialiasing
-> tritt auf, wenn das Shannon‘sche Abtasttheorem beim Übergang von analogen zu diskreten Signalen nicht eingehalten wird
(beim Übergang von kontinuierlichen Signalen (beliebiger Wert aus endlichem Intervall) zu diskreten Signalen (endliche Wertemenge))
____________________
Shannon’sche Abtasttheorem:
f_a ≥ 2 * f_max
mit
fa : Abtastfrquenz
fmax : höchste im kontinuierlichen Signal enthaltene Frequenz
_________________
Gründe:
-> Technik der Rasterschirme
-> Unterabtastung
(Strukturen im Bild sind feiner als die Auflösung des Monitors)
Antialiasing
Welche Lösungen gegen Aliasing gibt es? (3)
Erläutere.
Lösungen:
- Erhöhen der Auflösung
-> eine Doppelte Auflösung
=> besseres Ergebnis
(kleinere Treppenstufen)
Nachteile:
-> sehr teuer
-> physikalische Grenzen
___________________
- Bereichsmittelwerte ohne Gewichtung
(unweighted area sampling)
-> bestimmt durch einen Überlappungsbereich über die Intensität der Pixel
(Grauwert (Sättigung) eines Pixels wird proportional zu vom Rechteck überdeckten Fläche eingestellt => 2D Fläche, bzw. 3D Quader)
-> geringerer Kontrast zwischen benachbarten Pixeln
=> weicher Übergang
___________________
- Bereichsmittelwerte mit Gewichtung
(weighted area sampling)
Gewichtungsfunktion / Filterfunktion
=> Kegel
-> die Intensität eines Pixels hängt vom Teilvolumen des Kegelschnitts ab
Approximation von Kurven
Zielsetzung, Bedeutung, Forderung
Zielsetzung:
-> Freihandkurven
_________________
Approximation = Annäherung
_________________
Forderung:
-> glatte Kurven als Verbindung vorgegebener Punkte (Stützpunkte)
Approximation von Kurven
Welche Möglichkeiten für die Approximation von Kurven gibt es? (6)
Möglichkeiten für die Approximation von Kurven:
- > Polynome
- > Splines
- > Kubische Splines
- > Bézierkurven
- > B-Splinekurven
- > Nurbs
Approximation von Kurven - Polynome
Definiere Polynome
Nachteil?
-> durch n Punkte (Stützpunkte) lassen sich Polynome n-ten Grades legen
n = 2: Gerade,
n = 3 : Parabel, …
__________________
Nachteil:
-> Kurve oszilliert meistens zwischen den Stützpunkten
Approximation von Kurven - Splines
Definiere Splines.
Welche gibt es? (3)
Was ist jeweils deren Nachteil?
Splines
-> stückweise polynomielle Kurven
__________________
Geraden:
-> mit Polynomen 1. Grades
(2 Stützpunkte)
Nachteil:
-> es sind nur gerade Linien möglich
__________________
Parabeln:
-> mit Polynomen 2. Grades
(3 Stützpunkte)
Nachteil:
-> stoßen Splines aufeinander, ergeben sich Ecken
(C0-Stetigkeit)
__________________
kubische Splines:
-> mit Polynomen 3. Grades
-> diese liefern schöne Ergebnisse
(C2-Stetigkeit)
Nachteil:
-> Berechnungen sehr aufwändig
(deshalb nicht durchgesetzt)
Approximation von Kurven
Grad der Stetigkeit (Continuity)
Welche Stetigkeiten gibt es und was bedeuten sie?
Welche Stetigkeit ist beim Zeichnen von Kurven in der CA wünschenswert?
Zwischen zwei Kurvensegmenten gilt:
C0 :
-> bei auftreffenden Splines (selben Funktionswerte zweier Kurven) ergeben sich harte Ecken
(gleiche Funktionswerte, ungleich 1. Ableitungen)
__________________
C1 :
-> bei identischen Funktionsweiten gleicht sich die erste Ableitung, die 2. Ableitung unterscheidet sich jedoch
__________________
C2 :
-> bei identischen Funktionswerten gleicht sich sowohl die erste, als auch die zweite Ableitung
__________________
=> in der CA wurde „entschieden“, dass C1-Stetigkeit beim Zeichen von Kurven
wünschenswert sei
Approximation von Kurven - Bezierkurven
Aus was bestehen Bezierkurven?
Was sind ihre Eigenschaften? (5)
Bézierkurven
jedes Kurvensegment besteht aus vier Punkten:
-> 2 Stützpunkte für Anfang und Ende
-> 2 Kontrollpunkte für den Kurvenverlauf
________________
Eigenschaften:
- > im Anfangs- & Endpunkt ist die Kurve tangential zum Kontrollpolygon
- > C1-Stetigkeit an den Verbindungspunkten der Kurvensegmente durch Ausrichtung der Tangenten
- > Kurve liegt innerhalb der Hülle der Kontrollpunkte
- > nur globale Kontrolle des Kurvensegments
- > es kann jede beliebige Kurve dargestellt werden
Approximation von Kurven - B-Splines
Definiere B-Splines.
Was sind ihre Eigenschaften? (5)
Was sind die Ziele von B-Splines? (2)
B-Splines
B = Basis
-> Verallgemeinerung von Beziérkurven
_______________
Eigenschaften:
- > C(k-2) -Stetigkeit
- > Kurve liegt innerhalb der konvexen Hülle
- > durch Mehrfachpunkte sind „Ecken“ (Bereiche starker Krümmung) darstellbar
- > werden berechnet wie Bezierkurven, die Punkte werden mit den zugehörigen Polynomen verrechnet und miteinander aufaddiert
-> k wird vom User gesetzt,
bei Bezierkurven ist k gegeben
_______________
Ziele:
-> nicht alle Stützpunkte sollen Einfluss auf den gesamten Kurvenverlauf haben
-> der Grad der Polynome soll unabhängig von der Anzahl der Stützpunkte sein
(Lokale Kontrolle)
Approximation von Kurven - Nurbs
Definiere Nurbs.
(Was ist mit ihnen möglich?)
Was bedeutet ihr Name?
Nurbs
(non-uniform rational basis splines)
-> sind eine Erweiterung der B-Splines
-> mit ihnen sind genaue Abbildungen eines Kreises möglich
_________________
Non-uniform: Der Abstand zwischen den Werten des Kontrollvektors ist ungleichmäßig
Rational: Der Einfluss eines Kontrollpunktes wird über ein Gewicht gesteuert, welches durch den Quotienten (ratio) zweier Polynome gebildet wird
Approximation von Kurven
Nenne Vorteile von Nurbs im Vergleich zu Bezierkurven und B-Splines. (2)
Vorteile im Vergleich zu Bezierkurven / B-Splines:
-> exakte Darstellung von Kegelschnitt-Funktionen (Kreisen)
- > Invarianz der Kontrollpunkte unter Translation, Skalierung, Rotation und Zentralprojektion,
d. h. Unveränderlichkeit des Kurvenverlaufs unter diesen Operationen
