Computergrafik Past Paper PDF

Computergrafik Prof. Dr. Christian Pape Hochschule Karlsruhe Inhalt Projektionen Einführung Graphik-Pipeline Mathematische und geometrische Grundlagen OpenGL Bildrepräsentation...

Computergrafik Prof. Dr. Christian Pape Hochschule Karlsruhe Inhalt Projektionen Einführung Graphik-Pipeline Mathematische und geometrische Grundlagen OpenGL Bildrepräsentation Texturabbildungen Raytracing Schattierung von Oberflächen Transformationsmatrizen Prüfung Hochschule Karlsruhe 2 / 183 Prüfungsleistungen ▶ Computergrafik: 2 SWS Vorlesung + 2 SWS Labor ▶ Aktuelle Prüfungsordnungen: ▶ MINB (PO5): Pflichtfach, Modulprüfung mit Computer-Vision, 120 min, Labor. ▶ INFB (PO7): Pflichtfach, Modulprüfung, 90 min, Labor. (Computer-Vision ist Wahlfach). ▶ Zukünftige Prüfungsordnungen: ▶ MINB (PO6): Pflichtfach, Modulprüfung mit Computer-Vision, 120 min ▶ INFB (PO8): Wahlfach, 90 min Klausur und Labor. (Computer-Vision ist Wahlfach). Hochschule Karlsruhe 3 / 183 Labor ▶ Drei Aufgaben teilweise aufgeteilt auf mehrere Übungsblätter. 1. Darstellung einer bestehenden Asteroids-Implementierung ändern. 2. Einen rudimentären Raytracer implementieren. 3. Darstellung der Asteroids-Implementierung drei-dimensional implementieren mit Kamerabewegung. ▶ C++-20 (g++), SDL2 für Rastergrafik, SDL2 Mixer für Sound, GoogleTest (gtest) für automatisierte Tests. ▶ Buildprozess mit cmake und make. ▶ Verwendung von IDEs auf eigene Gefahr. ▶ EU07: Ubuntu. Aufgabenblätter sind aus Unix-Sicht beschrieben. ▶ Windows MinGW verwenden. ▶ Aufgaben sind nicht auf Macs getestet. ▶ Aufgaben und Quelltextrahmen befinden sich in Ilias. Hochschule Karlsruhe 4 / 183 Labor Anmeldung Labor ▶ Anmeldung zu Übungsgruppen via Ilias. ▶ Start nach der Vorlesung. ▶ Begrenzung auf 30 Personen pro Gruppe (Warteliste mit automatischem Aufrücken). ▶ Betreuung: Niklas Oesterle. ▶ Spätmöglichste Abgabetermine siehe Ilias, bei den Übungsgruppen. ▶ Lösung muss vor Abgabe in Ilias hochgeladen werden. ▶ Lösung muss Betreuer präsentiert und erläutert werden. Nur Hochladen reicht nicht. ▶ Keine Gruppenarbeit. Keine Quelltexte austauschen. Hochschule Karlsruhe 5 / 183 Vorlesung ▶ Iliasgruppe beitreten. ▶ Folien werden kurz vor der Vorlesung aktualisiert. ▶ Ein Teil der Inhalte ist als Tafelanschrieb vorhanden. ▶ Mitschreiben oder abfotografieren. Bei letzterem bitte keine Personen mit ablichten. ▶ Zusätzliche Übungsaufgaben gibt es derzeit nicht. Hochschule Karlsruhe 6 / 183 Vorlesung Literatur ▶ S. Marchner, P. Shirley. Fundamentals of Computer Graphics. O’Reilly Verlag. ▶ Insbesondere: Kapitel 1–8 (Kern des Kern) ▶ Mathematische Grundlagen, Rastergrafik, Raytracing, Transformationen, Projektionen, Graphik-Pipeline. ▶ Teile der Vorlesung weichen in der Darstellung ab. ▶ Später noch vertiefende und weiterführende Inhalte. Hochschule Karlsruhe 7 / 183 Vorlesung Literatur ▶ J. Vince. Mathematics for Computer Graphics. Springer-Verlag. ▶ Grundlagen und Vertiefung der mathematischen Grundlagen. ▶ Ggf. verwenden, um mathematische Inhalte noch auf andere Weise erläutert zu bekommen. Hochschule Karlsruhe 8 / 183 Vorlesung Literatur ▶ Open Book als HTML. ▶ https://pbrt.org/ ▶ Printversion erhältlich. ▶ Implementierungsnahe Darstellung anhand eines zugehörigen existierenden Raytracers. Hochschule Karlsruhe 9 / 183 Was ist Computergrafik? Engere Definition ▶ Modellierung und Erzeugung (rendering) von (animierten) Bildern (images). ▶ Modellierung (Modellraum, world space): Mathematische Modell, bestehend aus Punkten, Flächen, Linien,... ▶ Rendering: Bilderzeugungsverfahren wie Raytracing, Radiosity, Rasterverfahren, 3D-Druck,... ▶ Bilder“ (Bildraum, screen space): Pixelgrafiken, Vektorgrafiken, ” Druck auf Papier, 3D-Erzeugnisse wie Spritzdruck oder CNC-Fräsen. Hochschule Karlsruhe 10 / 183 Was ist Computergrafik? Einordnung und Abgrenzung ▶ Teil der Informatik (Wissenschaft der automatisierten Verarbeitung von Daten mit Hilfe von Digitalrechnern). ▶ Graphische Datenverarbeitung ist Oberbegriff ▶ Computergrafik: Vom Modellraum zum Bildraum ▶ Computervision: Vom Bildraum zum Modellraum ▶ Digital Image Processing: Verarbeitungen im Bildraum, Filter, Farbanpassungen, Dithering,... ▶ Computational Geometry (grafisch-geometrisch Algorithmen): Algorithmen und Datenstrukturen, bei denen verarbeitete Daten grafische Primitive sind. ▶... ▶ Beispiel Sonografie (Ultraschall): Aus Ultraschall 3D-Modelldaten erzeugen ist Computervision, die erzeugten Modelldaten rendern ist Computergrafik. ▶ Viele inhaltliche Überschneidungen. Hochschule Karlsruhe 11 / 183 Anwendungen Auswahl ▶ Computerspiele ▶ Filmindustrie: Spezialeffekte, animierte Filme (Cartoons) ▶ Industrie (CAD/CAM): Konstruktion von Maschinen, Autos, Spielfiguren. ▶ Visualisierung von Daten: Medizin, Data-Mining ▶ Simulationen: (Animierte) Darstellung simulierte Prozesse, Flugsimulatoren ▶ Abbildung zeigt Flugsimulator DASA (Wikipedia). Hochschule Karlsruhe 12 / 183 Inhalt Projektionen Einführung Graphik-Pipeline Mathematische und geometrische Grundlagen OpenGL Bildrepräsentation Texturabbildungen Raytracing Schattierung von Oberflächen Transformationsmatrizen Prüfung Hochschule Karlsruhe 13 / 183 Globales Koordinatensystem Euklidischer Raum ▶ Rechts-händisch ▶ Links-händisch ▶ Unten: 90◦ um x-Achse nach ▶ Unten: 180◦ um x-Achse nach hinten gedreht vorne gedreht y y (1,2) (1,2) z 0 x 0 x 0 x z z z y (1,2) y (1,2) 0 x (Lochmaske Kathodenstrahlröhre, Wikipedia) ▶ Graue z-Achse weglassen: 2-dimensionaler Fall Hochschule Karlsruhe 14 / 183 Polygon Definition Ein Polygon ist eine Fläche, die durch p2 eine Folge von k > 2 Punkten p1 ,... , pk definiert ist mit pi ∈ R. Die p1 Punkte bilden einen geschlossenen Streckenzug. p3 ▶ Wir betrachten nur planare Polygone: Dreick konvex Die Fläche liegt in einer Ebene. p1 ▶ Wir betrachten nur einfache Polygone, p2 deren Kanten sich nicht überschneiden (überschlagen). p3 p4 überschlagend einfach Hochschule Karlsruhe 15 / 183  Triangulierung Satz Jedes einfache Polygon mit k Punkten lässt sich in k − 2 Dreiecke zerlegen. Definition Ein Ohr ist ein aus drei aufeinander folgende Punkte gebildetes (inneres) Dreieck eines Polygon, welches von keiner Kante überschnitten wird. Satz Jedes einfache Polygon mit mehr als drei Punkten besitzt mindestens zwei Ohren (Zwei-Ohren-Theorem). Algorithmus Solange ein Ohr suchen und abschneiden, bis nur noch ein Dreieck vom Polygon übriggeblieben ist. Hochschule Karlsruhe 16 / 183 Sinus und Cosinus ▶ cos α im Einheitskreis ist die Länge der Projektion auf die x-Achse des Radius 1 um den Winkel α. ▶ sin α analog zur y-Achse. p' ▶ Für beliebigen Radius r > 0 hat die Projektion die Länge r · cos α. p ▶ sin α ≥ 0 für 0◦ ≤ α ≤ 180◦. α ▶ cos α ≥ 0 für −90◦ ≤ α ≤ 90◦ ▶ sin2 α + cos2 α = 1 (Trigonometrischer Phytagoras) ▶ sin(α±β) = sin α·cos β±cos α·sin β (Additionstheorem(e)) Hochschule Karlsruhe 17 / 183 Lage eines Punkts zu einer Strecke Gegeben: Strecke von a nach b, ein Punkt p Gesucht: Liegt p auf der Strecke ab, links davon oder rechts? b p a ▶ Zwei Winkel α und β finden, so dass Winkeldifferenz in diesen drei Fällen 0 (auf der Strecke), positiv (links) oder negativ (rechts) ist. ▶ Additionstheorem für sin verwenden, um Lösung zu berechnen. ▶ Anwendung: Punkt liegt in einem Dreieck. Hochschule Karlsruhe 18 / 183 Vektor Definition ▶ Ein n-dimensionaler Vektor → −v hat eine Länge und eine Richtung. x ▶ Repräsentation durch kartesische Koordinaten in Rn. 4,5 ▶ In der Computergrafik meist 2 ≤ n ≤ 4. ▶ Alternative Repräsentation durch Polarkoordinaten (für uns nicht von Bedeutung). v ▶ → −v = (x1 , x2 ,... , xn ) √ ▶ Länge |→ − v | = x1 2 +... + xn 2 (euklidische Distanz). ▶ Richtungswinkel α (meist Bogenmaß) Hochschule Karlsruhe ▶ In der Regel α ∈ [−π, π] bzw. α ∈ [−180, 180] 19 / 183 Vektorraum ▶ Vektoraddition und -subtraktion komponentenweise: → − ▶ → − a + b := (ax1 + bx1 ,... , axn + bxn ). → − ▶ → − a − b := (ax1 − bx1 ,... , axn − bxn ). ▶ Vektoraddition bildet abelsche additive Gruppe über Rn. Nullvektor → − → − − 0 ist neutrales Element, −→ −a := 0 − → a ist inverses Element. ▶ Skalarmultiplikation mit s ∈ R: s · → − a := (s · a ,... , s · a ) x1 xn ▶ Skalarmultiplikation bildet mit Vektoraddition einen Skalarkörper über R: → − → − ▶ s · (→ − a + b)=s ·→ −a +s · b ▶ (s + t) · → − a =s ·→ − a +t ·→ −a ,t ∈ R ▶ (s · t) · → − a = s · (t · → − a) → − ▶ 1· a = a → − ▶ Diese algebraische Struktur heißt Vektorraum. Hochschule Karlsruhe 20 / 183 Vektoraddition Geometrische Anschauung b b -a 0,5.b a a+b Hochschule Karlsruhe 21 / 183 Skalarprodukt Definition ▶ Gegeben seien zwei Vektoren → − a → − und b. |a|. sin
→ − → − ▶ a · b := ax1 · bx1 +... axn · bxn ∈ R a heißt Skalarprodukt. ▶ Es gelten folgende Eigenschaften:
→ − → − ▶ → −a · b = b ·→ −a |a|. cos
b → − → − → − → − → − → − → − ▶ a ·(b + c ) = ( a · c )+(b · c ) → − → − |a|. cos
. b ▶ s · (→ − a · b)=→ − a · (s · b ) → − → − ▶ → −a · b = cos α|→−a|·|b| ▶ Anwendungen: Bei orthogonalen Vektoren ist das Skalarprodukt 0, Berechnung von cos α. Hochschule Karlsruhe 22 / 183 Skalarprodukt Reflektionsvektor Gegeben: Ein Vektor →− v ein Vektor → −n mit |→−n | = 1, der senkrecht auf einer Oberfläche steht (Normalenvektor). Gesucht: Reflektionsrichtung → −r (Einfallswinkel gleich Ausfallswinkel) n

v r ▶ Behauptung: → − r =→−v − 2(→− v ·→− n)·→ − n ▶ Anwendungen: Raytracing, Stoßgesetze Hochschule Karlsruhe 23 / 183 Kreuzprodukt (Vektorprodukt) Definition → − ▶ Gegeben → −a , b ∈ R3 → − ax b ▶ → −a × b := (a2 · b3 − a3 · b2 , a3 · b1 − a1 · b3 , a1 · b2 − a2 · b1 ) ∈ R3 heißt → − Kreuzprodukt von → −a und b. b ax b α ▶ Es gelten folgende Eigenschaften: a → − − → − ▶ → −a ×( b + → c ) = (→ −a × b )+(→ − a ×→ − c) → − → − → − → − ▶ a × b = −( b × a ) (Antikommutativ) ▶ − →a ×→ −a =0 → − → − ▶ |→ −a × b | = |→ −a | · | b | sin α. ▶ Drei-Finger-Regel für rechte → − Hand von →−a × b [Abbildung Wikipedia] ▶ Anwendungen: Schnittpunkt Halbstrahl mit Dreieck, Physik Hochschule Karlsruhe 24 / 183 Lineare Interpolation von Punkten → − Gegeben: Zwei Punkte → − a und b in Rn → − Gesucht: Alle Punkte p(α) auf der Geraden, die durch → −a und b gebildet werden, α ∈ R. → − ▶ In der Informatik: p = lerp(→ − a , b , α) (linear interpolation), z.B. std::lerp. → − ▶ Zusätzliche Eigenschaften: lerp(→ −a , b , 0) = → −a und → − → − → − lerp( a , b , 1) = b → − Für 0 ≤ α ≤ 1 liegen die Punkte auf der Strecke zwischen → −a und b. → − → − ▶ Lösung: lerp(→ −a , b , α) = α→ − a + (1 − α) b ▶ Anwendungen: α-Blending, γ-Korrektur, Gerade in Parameterdarstellung (Physik: Berechnung von Schwerpunkten). ▶ α-Blending: Pinsel mit Farbe a auf farbigen Untergrund b malen. Dann soll die Untergrundfarbe zu 50 % (α = 0.5) durchscheinen. (Aquarell) ▶ Umkehrung: p gegeben, α gesucht. Numerisch stabiles, robustes Verfahren? Hochschule Karlsruhe 25 / 183 Lineare Interpolation von Punkten Alpha-Blending ▶ GIMP Pinseleigenschaften ▶ Deckkraft = α-Wert (in Prozent) Hochschule Karlsruhe 26 / 183 Schnitt Halbstrahl mit Dreieck Gegeben: Ein Dreieck im R3 mit Punkten a, b und c und Gerade → − g (t) = → − o + t · d (für t ≥ 0). Gesucht: Schnittpunkt s von g (t) mit Dreieck. b s d c a o ▶ Ebenengleichung aufstellen. Beispielsweise Hessesche Normalform: → − n ·→ − v = d. ▶ g (t) einsetzen und nach t auflösen: t = ⃗n⃗a−⃗ ⃗ n⃗o ⃗nd ▶ Liegt s im Dreieck? (bereits gelöst) ▶ Anwendung: Raytracing Hochschule Karlsruhe 27 / 183  Strahlensätze Erste Strahlensatz Prämisse: Ein Scheitelpunkt s, zwei Halbstrahlen, die von s ausgehen und zwei parallele Strecken, welche die Halbstrahlen in den Punkten a, b und c, d schneiden (siehe Abbildung). Dann gilt: sa sc = sb sd (( 4,5 3 v α Hochschule Karlsruhe 28 / 183 Schnitt mit Strecken Achsenparallele Strecke → − Gegeben: Gerade in Parameterdarstellung g (t) = → − o + t d und Koordinate x (jede Dimension möglich). Gesucht: Lösung t für Schnittpunkt g (t) für Koordinate x. x d g(t) o ▶ Behauptung: t = x−odx x ▶ Lösung mit Strahlensatz ▶ Anwendung: Schnitt mit achsen-orientierten Rechteck (axis aligned bounding box, AABB) Hochschule Karlsruhe 29 / 183 Matrizenrechnung ▶ Eine n × m-Matrix A ∈ M n×m ist eine rechteckige Anordnung von Elementen einer Menge M in n-Zeilen und m-Spalten:   a11 a12... a1m  a21 a22... a2m  A=...  = (aij ), i = 1,... , n; j = 1,... m  .. .......  an1 an2... anm ▶ Computergrafik meist quadratische Matrizen (n = m) und n = 2, 3, 4 ▶ Addition elementweise: A + B := (aij + bij ). m X ▶ Multiplikation: A · B := cij = aik · bkj (Zeile i mal Spalte j) k=1 ▶ Es gelten (bei passenden Matrizen) Assoziativ- und Distributivgesetze. Aber nicht kommutativ. ▶ Multiplikation n × m-Matrix A mit Vektor v = (x1 ,... , xm ): Pm Pm A · v := ( i=1 a1i · xi ,... , i=1 ani xi ) ▶ Anwendungen: Transformationen von Punkten und Objekten. Hochschule Karlsruhe 30 / 183 Matrizenrechnung Drehmatrix Gegeben: Punkt p ∈ R2 , Winkel α. Gesucht: Drehung von p um den Winkel α um den Ursprung herum. p' p α ▶ Drehung mit Drehmatrix Rα repräsentieren. ▶ Drehung ist Multiplikation p ′ = Rα · p. Hochschule Karlsruhe 31 / 183 Lineare Gleichungssystem (LGS) Cramersche Regel Gegeben: m Lineare Gleichungen a1i · x1 +... + ami · xn = bi mit n Unbekannten xi für i = 1,... , m. (Wertemenge R) Gesucht: Eine Belegung von x, welches die Gleichungen erfüllt. (Lösung des LGS) ▶ In Matrixform A · x = b ▶ mit x = (x1 ,... , xn ), b = (b1 ,... , bm ), A = ((ai j)), i = 1,... , m; j = 1,... , n ▶ Cramersche Regel für quadratische LGS (n = m): det(Ai ) xi = det(A) wobei Ai aus A entsteht, indem die i-te Spalte durch b ersetzt wird. ▶ Beispiel: x + y = 1 x − y = 2 ▶ Anwendungen: Lösungen von Schnittpunkt zweier Geraden Hochschule Karlsruhe 32 / 183 Lineare Interpolation Barycentrische Koordinaten → −− Gegeben: Drei paarweise, verschiedene Punkte → − a, b→ c in Rn , → − Punkt p in der durch die Punkte definierten Ebene. → − Gesucht: u, v , w ∈ R mit → − p =u·→ −a +v · b +w ·→ − c (Baryzentrische Koordinaten) b c p a ▶ Zusätzliche Eigenschaften (analog lerp mit p = αa + βb): u+v +w =1 0 ≤ u, v , w ≤ 1, wenn → −p im Dreick liegt. ▶ Folgerung: w = 1 − u − v ▶ Anwendungen: Interpolation von Normalenvektoren, Schwerpunkt einer Fläche an einem Punkt. Hochschule Karlsruhe 33 / 183 Lineare Interpolation Barycentrische Koordinaten ▶ Anwendungsbeispiel: Farbauswahl GIMP. ▶ Lineare Interpolation zwischen ausgewählter Farbe (hier Rot), Schwarz und Weiß durch Verschiebung eines Punkts. Hochschule Karlsruhe 34 / 183 Schnitt Halbstrahl mit Dreieck Verbesserung mit Barycentrische Koordinaten Gegeben: Ein Dreieck im R3 mit Punkten a, b und c und Gerade → − g (t) = → − o + t · d (für t ≥ 0). Gesucht: Schnittpunkt s von g (t) mit Dreieck. ▶ Wie bisher: Sehstrahl und Ebene auf Parallelität prüfen. ▶ Dann: u und v berechnen, t erst zum Schluss ▶ LGS aufstellen zur Lösung von t, u und v via → − → − → − o +t · d =u·→ − a + v · b + (1 − u − v ) · → − c ▶ Mit Cramerschen-Regel lösen. ▶ Für v1 , v2 , v3 ∈ R3 gilt: det(v1 |v2 |v3 ) = v1 · (v2 × v3 ) (Beweis durch Nachrechnen) ▶ Möller, Tomas und Trumbore, Ben: Fast, Minimum Storage Ray-Triangle Intersection. Journal of Graphics Tools. 2: 21–28. Hochschule Karlsruhe 35 / 183 Inhalt Projektionen Einführung Graphik-Pipeline Mathematische und geometrische Grundlagen OpenGL Bildrepräsentation Texturabbildungen Raytracing Schattierung von Oberflächen Transformationsmatrizen Prüfung Hochschule Karlsruhe 36 / 183 Raster vs Vektorgraphik ▶ Rastergraphik ▶ Vektorgraphik Hochschule Karlsruhe 37 / 183 Rastergraphik ▶ Rastergraphik: Bild wird durch eine Matrix von farbigen Pixel (pixel elements) repräsentiert. ▶ Anzahl Zeilen und Spalten der Matrix nennt man Auflösung. ▶ Pixel können quadratisch sein. ▶ Ausgabegeräte: ▶ Bildschirm: Röhrenmonitor, LED, Plasma (selbstleuchtend), LCD (lichtdurchlässig),... ▶ Hardcopy: Tintenstrahldrucker, 3D-Drucker,... ▶ Eingabegeräte: Digitalkamera, Flachbettscanner,... ▶ Farbbildschirmen: Farbe ist in Rot, Grün und PLATO V Terminal Blau-Anteil aufgeteilt (additive with plasma display Farbmischung). 1981 (Wikipedia) Hochschule Karlsruhe 38 / 183 Beispiel LC-Display ▶ LCD (liquid crystal displays) ▶ Unpolarisierte weiße Hintergrundbeleuchtung ▶ Flüssigkristalle zwischen zwei Dioden und gerillten Polarisationsfiltern ▶ Spannung zwischen Dioden ordnet Kristalle unterschiedlich an ▶ Oben: Kristalle polarisieren Licht vertikal. ▶ Unten: Horizontale Polarisieren bleibt erhalten. ▶ Pixel besteht aus drei LC mit Farbfilter für Rot, Grün und Blau. Hochschule Karlsruhe 39 / 183 Beispiel Tintenstrahldrucker ▶ Druckkopf besteht aus einer Matrix einzelner Düsen. ▶ Düse wird durch Druck gepresst: ein Farbklecks wird abgesondert (z.B. Piezokristall) ▶ Muster von Farbkleckse bestimmen Helligkeit. ▶ Pixel besteht aus drei additiv gemischten Farben: Cyan, Yellow, Magenta. ▶ Druckauflösung wird mit Pixeldichte beschrieben: DPI (dots per inch), PPI (pixel per inch). Abbildung Wikipedia Hochschule Karlsruhe 40 / 183 Portable Anymap ▶ Binär- und textbasierte (ASCII), unkomprimierte Dateiformate für RGB-Bitmaps ▶ Teil von Netpbm: Sammlung 350 Kommandozeilen-orientierter Programme inklusive Konverter für ca. 100 Dateiformate. ▶ https://netpbm.sourceforge.net Portable Bitmap PBM Monochrom 1 Bit Portable Graymap PGM Graustufen 8/16 Bit Portable Pixmap PPM RGB-Farben 24/48 Bit ▶ jeweils Text- und Binärversion. ▶ Portable Anymap: Erweiterung, die alle drei Formate in einem erweiterten Format inklusive Alphakanal vereint. Hochschule Karlsruhe 41 / 183 Portable Pixmap ▶ Pro Datei ein Bild, max. 70 Zeichen pro Zeile ▶ Pro Farbeanteil ein Wert (ITU-R Recommendation BT.709) ▶ Pixel: Drei mit Leerzeichen getrennte Farbwerte ▶ Folge von mit Leerzeichen getrennte Pixel ▶ Linkshändisches Koordinatensystem P3 # magic number: PPM Textformat 7 7 # 7 x 7 Raster 15 # max. Wert pro RGB-Farbanteil [0, 65536] 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 Hochschule Karlsruhe 42 / 183 Portable Pixmap #include int main(void) { std::cout b und n > f.  2 r −l 0 0 − rr −l +l  2 t+b  (r;t;f)  0  t−b 0 − t−b  2 n+f  y  0 0 n−f − n−f (l;b;n) 0 0 0 1 x z Hochschule Karlsruhe 95 / 183 Projektionen Kamera-Transformation Gegeben: Punkte des R3 Modelraums. Eine Kamera mit Augenpunkt e, einer Blickrichtung ⃗g und einen Vektor ⃗t (zeigt nach oben“) ” Gesucht: Verschiebung und Drehung der Punkt, so dass vom globalen Nullpunkt Richtung negativer z-Achse alle Punkte liegen. ▶ ⃗t, ⃗g und e bilden ein (nicht notwendigerweise orthogonales) lokales Koordinatensystem. −⃗g ⃗t × w ⃗ u t ⃗ := w , ⃗u := ⃗ × ⃗u , ⃗v := w |⃗g | ⃗ |t × w⃗| w e g v    ux uy uz 0 1 0 0 −ex  vx  vy vz 0   0 1 0 · −ey    wx wy wz 0  0 0 1 −ez  0 0 0 1 0 0 0 1 Hochschule Karlsruhe 96 / 183 Projektionen Zentralprojektion Gegeben: Punkte des R3 Modelraums. Eine Kamera mit Augenpunkt e, einer Blickrichtung ⃗g und einen Vektor ⃗t (zeigt nach oben“) und ” Abstand d zu einer Projektionsfläche. Gesucht: Perspektivische Projektion aller Punkte von e auf die Fläche entlang Blickrichtung.   d 0 0 0  0 d 0 0     0 0 1 0  0 0 1 0 ▶ Strahlensatz anwenden: Es muss durch pz g geteilt werden. ▶ Mit linearen Transformationsmatrizen e nicht möglich. ▶ Lösung: w -Komponente auf pz setzten, beim Zeichnen durch w teilen. Hochschule Karlsruhe 97 / 183 Projektionen Zentralprojektion ▶ Tiefeninformation geht verloren, wird aber später benötigt. ▶ z-Koordinaten nicht linear auf eine monotone Funktion abbilden. ▶ pz 7→ (n + f ) · pz − f · n ▶ Hat die Eigenschaft: pz = n und pz = t jeweils auf n und t abgebildet werden.   d 0 0 0  0 d 0 0     0 0 n+f −fn  0 0 1 0 Hochschule Karlsruhe 98 / 183 Projektionen Sichtfeld ▶ Sichtfeld (field of view): Bildwinkel Θ eines optischen Geräts oder Sensors, innerhalb dessen Aufzeichnungen stattfinden können. ▶ Beim Menschen Gesichtsfeld (visual field): Optische Wahrnehmung des Auges ohne dieses zu bewegen. Ca. 107° horizontal (links und rechts), 60°-70° vertikal nach oben, 70°-80° nach unten. ▶ Beim Sichtfeld werden Augenbewegungen mit zugelassen. ▶ Alternative Angabe der Zentralprojektion mit Sichtfeld möglich. ▶ Annahme: l = −r , b = −t (Bildmitte v wird anvisiert), nx gegeben. Pixel quadratisch. ▶ d = −n ist normalerweise gegebener w Abstand. e ▶ Vertikaler FoV: tan Θ2 = |n| t d (r,t,n) ▶ Alternativen: Horizontaler oder u diagonaler FoV. Hochschule Karlsruhe 99 / 183 Inhalt Projektionen Einführung Graphik-Pipeline Mathematische und geometrische Grundlagen OpenGL Bildrepräsentation Texturabbildungen Raytracing Schattierung von Oberflächen Transformationsmatrizen Prüfung Hochschule Karlsruhe 100 / 183 Graphik-Pipeline ▶ Vertex-Processing: Grafische Primitive, die durch Punkte definiert sind, werden Command Stream Vertex Processing verarbeitet, z.B. mit Transformed Geometry Transformationsmatrizen. Rasterung ▶ Rasterung: Primitive werden in einzelne Fragments Fragmente zerlegt. Für jedes Pixel ein Fragment Processing Fragment. Blending ▶ Fragment-Processing: Fragmente werden Framebu
er geprüft, z.B. Einfärbung. ▶ Blending: Farben werden kombiniert, z.B. Fragment-Farbe mit Hintergrund kombiniert. Hochschule Karlsruhe 101 / 183 Graphik-Pipeline ▶ Koordinaten des 3D-Modell (Punkte) können mit den bisherigen Projektionen einschließlich Viewport-Transformation den Bildkoordinaten zugeordnet werden (links). ▶ Jeder Koordinaten können Farb- oder andere Materialeigenschaften wie Oberflächennormalen zugeordnet sein. ▶ Es fehlt die Rasterung der Objekte (Fläche) und Einfärbung der sichtbaren Pixel (rechts). Hochschule Karlsruhe 102 / 183 Rasterung von Strecken Midpoint-Algorithmus Gegeben: Eine Strecke in der x/y-Ebene mit Punkten x = (x0 , y0 ), y = (x1 , y1 ) ∈ R2 in Bildkoordinaten. Pixel sind quadratisch. Gesucht: Alle Pixel, die von der Strecke überdeckt werden, so dass ein lückenloser Verlauf entsteht. ▶ Annahme x0 ≤ x1 (Ansonsten Punkte vertauschen). ▶ Steigung m der Strecke ist m = yx1 −y 0 1 −x0 ▶ Implizite Repräsentation der Strecke: f (x, y ) = (y0 − y1 ) · x + (x1 − x0 ) · y + x0 · y1 − x1 · y0 = 0 ▶ Wir betrachten m ∈ [0, 1) ▶ Ziel: dünnste Strecke zeichnen, so dass keine Lücken entstehen. Hochschule Karlsruhe 103 / 183 Rasterung von Strecken Midpoint-Algorithmus ▶ Pixel (x, y ) sei zuletzt gezeichnetes Pixel (Mitte des Pixels). ▶ (x + 1, y ) oder (x + 1, y + 1) auswählen (gelbe Pixel)? ▶ Mittleren Punkt auf der horizontalen Strecken dazwischen betrachten: (x + 1, y + 0, 5) ▶ Liegt der Punkt unterhalb der Strecke: oberes Pixel. Ansonsten unteres Pixel. ▶ Start: x0 und y0 zur nächsten ganzen Zahl runden. 1 y = y0 2 f o r x = x0 t o x1 do 3 draw ( x , y) 4 if ( f (x + 1 , y + 0. 5 ) < 0) then 5 y = y + 1 Hochschule Karlsruhe 104 / 183 Rasterung von Strecken Midpoint-Algorithmus Verbesserung 1 y = y0 2 f o r x = x0 t o x1 do 3 draw ( x , y) 4 if ( f (x + 1 , y + 0. 5 ) < 0) then 5 y = y + 1 ▶ Berechnungen vom vorherigen Pixel wiederverwenden. ▶ f (x + 1, y ) = (y0 − y1 ) · (x + 1) + (x0 − x1 ) · y + y1 · y0 − x1 · y0 = f (x, y ) + (y0 − y1 ) ▶ f (x + 1, y + 1) = f (x, y ) + (y0 − y1 ) + (x0 − x1 ) 1 y = y0 2 d = f ( x0 + 1 , y0 + 0. 5 ) 3 f o r x = x0 t o x1 do 4 draw ( x , y ) 5 if d < 0 6 y = y + 1 7 d = d + ( x1 − x0 ) + ( y0 − y1 ) 8 else 9 d = d + ( y0 − y1 ) Hochschule Karlsruhe 105 / 183 Rasterung von Strecken Midpoint-Algorithmus ▶ Farbe zwischen Anfangs- und Endpunkt der Strecke kann linear interpoliert werden. ▶ Pitteway, M. L. V., 1967: Algorithm for drawing ellipses or hyperbolae with a digital plotter. The Computer Journal. ▶ Van Aken, Jerry; Novak, Mark, 1985: Curve-Drawing Algorithms for Raster Displays. Association for Computing Machinery. ▶ Bresenham, J. E., 1965. Algorithm for Computer Control of a Digital Plotter. IBM Systems Journal, 4(1). Hochschule Karlsruhe 106 / 183 Rasterung von Dreiecken Gegeben: Dreick mit drei Eckpunkten p0 = (x0 , y0 ), p1 = (x1 , y1 ) und p2 = (x2 , y2 ) in der Bildebene. Gesucht: Rasterung des Dreiecks, so dass keine Lücken entstehen. ▶ Den Eckpunkten seien Farbwerte c0 , c1 , c2 zugeordnet. ▶ Interpolation der Farbwerte für ein gerastertes Pixel mit Baryzentrischen Koordinaten. ▶ Oder: Bestimmung der sichtbaren Farbe in Eckpunkt mit z.B. Lambertschen Shading mit Normalen der Eckpunkte und dann Interpolation mit Baryzentrischen Koordinaten (Gouraud Shading). ▶ Problem: Dreicke, die Eckpunkte teilen, müssen ohne Lücke dazwischen gerastert werden. ▶ Einfachste Lösung: Jedes Pixel, das im Dreick liegt, wird gezeichnet. Hochschule Karlsruhe 107 / 183 Rasterung von Dreiecken 1 f o r a l l x do 2 f o r a l l y do 3 compute ( u , v , w) f o r ( x , y ) 4 i f ( u ∈ [0, 1] and v ∈ [0, 1] and w ∈ [0, 1] ) t h e n 5 c = u · c0 v · c1 + w · c2 6 drawpixel (x , y ) with c o l o r c ▶ Wie Pixel (x, y ) auswählen? ▶ Brute-Force: Bounding-Box des Dreiecks berechnen und über alle Pixel der Box iterieren. ▶ xmax = ⌈min{x0 , x1 , x2 }⌉ ▶ xmin = ⌊min{x0 , x1 , x2 }⌋ ▶ ymax = ⌈min{y0 , y1 , y2 }⌉ ▶ ymin = ⌊min{y0 , y1 , y2 }⌋ Hochschule Karlsruhe 108 / 183 Rasterung von Dreiecken Verbesserung ▶ Seien f01 , f 12, f20 jeweils die implizite Repräsentation der Strecken p0 p1 , p1 p2 und p2 p0. ▶ Dann gilt u = ff12(x(x,y ) f20 (x,y ) f01 (x,y ) ,y ) , v = f (x ,y ) , w = f (x ,y ) 12 0 0 20 1 1 01 2 2 1 f o r y = ymin t o ymax do 2 f o r x = xmin t o xmax do 3 u = f12 ( x , y ) / f12 ( x0 , y0 ) 4 v = f20 ( x , y ) / f20 ( x1 , y1 ) 5 w = f01 ( x , y ) / f01 ( x2 , y2 ) 6 i f ( u > 0 and v > 0 and w > 0 ) t h e n 7 c = u · c0 + v · c1 + w · c2 8 drawpixel (x , y ) with c o l o r c ▶ Algorithmus kann wie zuvor auch inkrementell verbessert werden. ▶ Degenerierte Dreiecke (Strecke) führt zu Division durch 0. Hochschule Karlsruhe 109 / 183 Tiefenpuffer (z-Buffer) ▶ Gerastertes Pixel wird nur in Framebuffer (Bildspeicher) geschrieben, wenn zugehöriger Punkt dem Betrachter näher ist. ▶ Lösung: Zweiten Speicher, der Tiefeninformation eines Pixel (z-Koordinate des zugehörigen Punkts) speichert. Tiefenpuffer. ▶ Wertebereich z-Koordinate ist [−1, 1]. ▶ Pixel wird nur gesetzt, wenn z-Koordinate größer als bisherige ist (größer, da wir in negativer z-Richtung blicken!) ▶ In der Praxis werden nicht negative ganze Abb. Fundamentals of Computer Graphics Zahlen statt Gleitkommazahlen verwendet (Zahlenwerte negieren, ggf. um Eins verschieben, Exponent konstant setzten und Mantisse als ganze Zahl verwenden). Hochschule Karlsruhe 110 / 183 Clipping ▶ Nur Dreiecke, die im Sichtbereich sind, sollen gezeichnet werden. ▶ Clipping: Abschneiden von Objektteilen an (rechteckigen) Bildausschnitten. ▶ Clipping in nicht-homogenen Weltkoordinaten (R3 ) gegenüber den sechs Ebenen des Quaders. Also vor Kamera-Transformation. ▶ Oder nach kanonischer Form (OpenGL). Blickrichtung y x nicht sichtbar z Hochschule Karlsruhe 111 / 183 Clipping Schnitt Strecke mit Ebene Gegeben: Strecke von a nach b. Ebenengleichung ⃗n · ⃗p + D = 0. (D = −d in ⃗n · ⃗p = d) Gesucht: Punkte auf Strecke, der in der Ebene liegt (falls vorhanden). 1. Prüfe, ob a und b sich auf verschiedenen Seiten der Ebene befinden (mit impliziter Form wie bei Midpoint-Algorithmus): sgn(⃗n · a + D) ̸= sgn(⃗n · b + D) 2. Parameterdarstellung: p(t) = a + t · (b − a) in Ebenengleichung einsetzen und nach t auflösen: ⃗n · a + D t= ⃗n · (a − b) ▶ Das gleiche für den die Strecke vom außen liegenden Punkt zum anderen Dreieckspunkt. Hochschule Karlsruhe 112 / 183 Clipping Dreieck zerteilen ▶ Dreieck zerteilen, die innere mit den restlichen Ebenen clippen. ▶ Das Dreieck zerfällt immer in drei Dreiecke. ▶ Farben und Normalen in den Eckpunkten? b y c x z a Hochschule Karlsruhe 113 / 183 Inhalt Projektionen Einführung Graphik-Pipeline Mathematische und geometrische Grundlagen OpenGL Bildrepräsentation Texturabbildungen Raytracing Schattierung von Oberflächen Transformationsmatrizen Prüfung Hochschule Karlsruhe 114 / 183 OpenGL Geschichte OpenGL (Open Graphics Library) ist eine plattform-unabhängige, performante 2D/3D-Grafik-API-Spezifikation. 1980 Iris GL (Intergrated Raster Imaging System Graphics Librar), Silikon Graphics. Für Iris-Workstation (MC68000, MIPS). 1992 OpenGL 1.0 (Mark Segal, Kurz Akeley). Formalisierung von Iris GL. Plattformunabhängig. Standardisierung durch Architectural Review Board (ARB). 2004 OpenGL 2.0. Einführung von Shader-Sprachen (GLSL). 2008 OpenGL 3.0. Teile der API als veraltet markiert und (3.1) entfernt. Kernfunktionalitäten (3.2), OpenCL (3.3). 2017 OpenGL 4.0 – 4.6. Binäre Shader-Programme. 64-Bit Gleitkommazahlen, Texturkompression, teilweise DX11-Emulation. ▶ Aktuelle Hardware unterstützt mindestens Kernfunktionen von OpenGL 3.3. Hochschule Karlsruhe 115 / 183 OpenGL Resourcen ▶ Khronos-Group heute verantwortlich für Standardisierung. ▶ https://registry.khronos.org/OpenGL/specs/gl/glspec46. core.pdf ▶ Direkte Seite für OpenGL: https://www.opengl.org/. ▶ Alternativen: Direct-3D (Microsoft), Vulcan (low-level, von AMD zur Khronos-Group), Metal (low-level, Apple), OpenGL ES (embedded / mobile) Teilmenge von OpenGL. ▶ OpenGL ist praktisch Standard bei plattform-unabhänigen Grafik-Programmen. ▶ Online-Tutorials (auf OpenGL 3.x+ achten): https:www.learnopengl.com, www.opengl-tutorial.org, ogldev.org (Videos). Hochschule Karlsruhe 116 / 183 OpenGL Resourcen ▶ OpenGL ist nur eine Spezfikation, nah an C, keine Implementierung. ▶ Zugriff auf plattformabhängige API-Einsprungadressen mit GLEW (lädt auch Treiber, DLL, je nach Betriebssystem). ▶ OpenGL-Header-Dateien Open-Source. Kann üblicherweise über Paketmanager installiert werden. ▶ OpenGL benötigt Zugriff auf Hardware, insbesondere Framebuffer (Context). ▶ OpenGL besitzt keine Funktionen, um Fenster, UI oder ähnliches zu bauen. ▶ SDL2 / GLFW /SFML bieten Funktionen, um Context für OpenGL zu erzeugen. Hochschule Karlsruhe 117 / 183 OpenGL Erstes Programm 1. Fenster mit SDL2 erzeugen. SDL_WINDOW_OPENGL wichtig. 2. OpenGL-Context mit SDL2 für das Fenster erzeugen. 3. GLEW initialisieren. 4. OpenGL-API-Befehle nutzen. 1 SDL Window * window = n u l l p t r ; 2 i f ( S D L I n i t ( SDL INIT VIDEO ) < 0 ) { 3 s t d : : c o u t