computergrafik.tex

\chapter{Computergrafik}

Zusammenfassung der Vorlesung "`Computergrafik"' aus dem Wintersemester 2014.\footnote{\url{http://cg.ivd.kit.edu/lehre/ws2014/cg/index.php}}

\section{Farben, Bilder und Perzeption}

\subsection{Bilder, Darstellung und Framebuffer}

\subsubsection{Gammakorrektur}
\begin{itemize}
	\item Bilder sind oft zu hell oder zu dunkel
	\item Korrekturfunktion für das menschlichem Empfinden von physikalischen Helligkeitsunterschieden
	\item Ein idealer Monitor bildet einen Pixel-Wert \(n\) auf die Intensität \(I(n)\) ab
	\item Vergleichsweise wenige Stufen sind ausreichend
\end{itemize}


\subsection{Licht, Sehen und Wahrnehmung}

\subsubsection{Perzeption vs. Messung}
\begin{itemize}
	\item Das menschliche Auge kann die spektrale Zusammensetzung von Licht nicht erfassen
	\item Das Auge (und das Gehirn) macht eingeschränkte Messungen und passt sich den äußeren Umständen an
\end{itemize}

\subsubsection{Das Auge}
\begin{itemize}
	\item Zapfen: Für photopisches Sehen (Tagsehen) und trichromatisches Farbsehen. Blau (7\%), Grün (37\%), Rot (56\%)
	\item Stäbchen: Für skotopisches, monochromatisches Sehen (Nachtsehen); lichtempfindlicher, überall auf der Retina
\end{itemize}

\subsubsection{Metamerie}
Verschieden zusammengesetzte Lichtspektren können beim Menschen die gleiche Farbwahrnehmung hervorrufen.

\subsubsection{Farbtemperatur und Schwarzkörperstrahlung}
Die Farbtemperatur ist definiert als die Temperatur eines Schwarzen Körpers, des sogenannten Planckschen Strahlers, die zu einer bestimmten Farbe des Lichts gehört, das von dieser Strahlungsquelle ausgeht. Konkret ist es die Temperatur, deren Lichtwirkung bei gleicher Helligkeit und unter festgelegten Beobachtungsbedingungen der zu beschreibenden Farbe am ähnlichsten ist.\footnote{\url{http://de.wikipedia.org/wiki/Farbtemperatur}}

\subsubsection{Farbmischungen}
\begin{itemize}
	\item \textbf{Additiv}
	\begin{itemize}
		\item RGB: \(C=rR+gG+bB\)
		\item Farbkombination durch Addition der Spektren
		\item Biologisch und technisch motiviert
		\item Anwendung: Monitore, Beamer
	\end{itemize}
	\item \textbf{Subtraktiv}
	\begin{itemize}
		\item CMY(K): Jede Primärfarbe absorbiert einen Teil des Spektrums; Key ist beim Druck meist Schwarz
		\item Dualer Farbraum zu RGB
		\item Farbkombination durch Multiplikation der Spektren
		\item Anwendung: Film, Farbstifte, Farbdrucker
	\end{itemize}
	\item \textbf{HSV}
	\begin{itemize}
		\item Farbton (Hue), Sättigung (Saturation) und Helligkeit (Value)
		\item Darstellung als Zylinder oder hexagonaler Kegel
		\item Anwendung: Benutzerschnittstellen, da intuitiv
		\item Weder additiv noch subtraktiv
	\end{itemize}
	\item \textbf{XYZ}
	\begin{itemize}
		\item Beschreibung aller wahrnehmbaren Farben
		\item Eentspricht der menschlichen Farbwahrnehmung des Auges
		\item Farbraum mit rein positiven Color Matching Funktionen
		\item Lineare Abbildung \[XYZ \Leftrightarrow RGB\]
	\end{itemize}
	\item \textbf{XYY}
	\begin{itemize}
		\item Darstellung aller sichtbaren Farben
		\item Normalisierung auf der \(X+Y+Z=1\)-Ebene mit anschließender Projektion auf die \(XY\)-Ebene
		\item Farben auf der Strecke zwischen zwei Punkten können durch additives Mischen der Farben an den Endpunkten erreicht werden
	\end{itemize}
\end{itemize}

\subsubsection{Farbraum}
Die Menge der Farben, die mit einem bestimmten Modell beschrieben werden können.

\subsubsection{Gamut}
Die Menge aller Farben, die ein Gerät darstellen kann (z.B. Scanner, Drucker, Monitor, etc).

\subsubsection{Graßmannsche Gesetze}
Jeder Farbeindruck kann mit drei Grundgrößen beschrieben werden.


\subsection{CIE Color Matching Functions}
\begin{itemize}
	\item Wahrnehmungsexperimente: Referenzfarbe vorgegeben, soll durch drei Grundfarben reproduziert werden
	\item Problem: Nicht alle Farben konnten reproduziert werden
	\item Lösung: Primärfarben als negativer Vergleichwert
\end{itemize}


\subsection{Weber-Fechner-Gesetz}
Die subjektiv empfundene Stärke von Sinneseindrücken ist proportional zum Logorithmus der Intensität des physikalisch Reizes (1:2 wird empfunden wie 100:200).


\subsection{Ray Tracing}
\begin{itemize}
	\item Idee: Geometrische Überlegungen über Lichtstrahlen
	\item Verfolge die Lichtstrahlen, die die Öffnung der Lochkamera passieren, finde Pixel, die das Objekt beeinflussen und bestimme Pixelfarbe
\end{itemize}


\subsection{Nyquist-Shannon-Abtasttheorem}
Ein kontinuierliches, bandbegrenztes Signal mit einer maximalen Frequenz \(f_{max}\) muss mit einer Frequenz größer \(2f_{max}\) abgetastet werden, damit aus dem diskreten Signal das Ursprungssignal exakt rekonstruiert werden kann.



\section{Ray Tracing}

\subsection{Grundbegriffe}

\subsubsection{Virtuelle Kamera}
Definiert durch:
\begin{itemize}
	\item Position und Blickrichtung
	\item Orientierung der vertikalen Achse
	\item Bildebene vor der Kamera
\end{itemize}

\subsubsection{Rasterisierung}
\begin{itemize}
	\item Idee: Transformation von Geometrie (3D auf 2D-Bildebene)
	\item Für alle Objekte: Finde Pixel, die das Objekt bedeckt und bestimme Pixelfarbe
\end{itemize}

\subsubsection{Bildsynthese}
\begin{itemize}
	\item Erzeuge ein Rasterbild aus einer Szenenbeschreibung (Objekte), bestimme also, welche Objekte die Farbe jedes Pixels beeinflussen
	\item \textbf{Objektbasiert (Object-Order Rendering)}
	\begin{enumerate}
		\item Betrachte ein Objekt/Fläche nach der anderen
		\item Finde heraus, welche Pixel das Objekt bedecken
		\item Bestimme die Pixelfarbe
	\end{enumerate}
	\item \textbf{Bildbasiert (Image-Order Rendering)}
	\begin{enumerate}
		\item Betrachte einen Pixel nach dem anderen
		\item Finde heraus, welches Objekt an dieser Stelle sichtbar ist
		\item Bestimme die Pixelfarbe
	\end{enumerate}
\end{itemize}

\subsubsection{Strahlentypen}
\begin{itemize}
	\item Sichtstrahl: Halbgerade von der Kamera durch den Pixel
\end{itemize}


\subsection{Prinzip}
\begin{itemize}
	\item Betrachte einen Pixel nach dem anderen (ray generation)
	\item Finde das Objekt, das die Kamera durch diesen Pixel sieht (ray intersection)
	\item Berechne Farbe und Schattierung (shading)
	\item Rekursive Fortsetzung der Strahlenverfolgung
\end{itemize}

\subsubsection{Prinzipielles Vorgehen im Detail}
\begin{enumerate}
	\item \textbf{ray generation}
	\begin{itemize}
		\item Erzeugung von Sichtstrahlen (vom Betrachter zur Bildebene) durch jeden Pixel der Bildebene
		\item Die Bildebene ist festgelegt durch den Abstand zur Kamera und die Größe der Ebene
		\item Typischerweise ist das Sichtfeld orthogonal zum mittleren Sichtstrahl und symmetrisch 
	\end{itemize}
	\item \textbf{ray intersection}
	\begin{itemize}
		\item Finde Objekt, das den Sichtstrahl schneidet und dessen Schnittpunkt der Kamera am nächsten ist
		\item Schnittpunktberechnung beispielsweise über Baryzentrische Koordinaten
	\end{itemize}
	\item \textbf{shading}
\end{enumerate}


\subsection{Materialeigenschaften}

\subsubsection{Schattierung/Beleuchtungsberechnung}
\begin{itemize}
	\item Essentiell für dreidimensionalen Eindruck
	\item Interaktion von Lichtquellen und Oberflächen
	\item \textbf{Extrema}
	\begin{itemize}
		\item Spekulare Reflexion: Einfallswinkel gleich Ausfallswinkel
		\item Diffuse (lambertsche) Reflexion: Gleiche Reflexion in alle Richtungen
	\end{itemize}
\end{itemize}

\subsubsection{Licht-Material-Interaktion}
Was passiert, wenn Licht auf eine Oberfläche trifft?
\begin{itemize}
	\item Ein Teil wird reflektiert
	\item Ein Teil dringt ins Material ein
	\item Das Verhältnis ist abhängig vom Einfallswinkel (\textit{Fresnel-Effekt}) und den Brechungsindizes beider Materialien
\end{itemize}

\subsubsection{Reflexion}
\begin{itemize}
	\item Diffus: Licht erhellt das Objekt gleichmäßig
	\item Glänzend (imperfekt spiegelnd): Licht wirft einen Kegel in Richtung Ausfallswinkel
	\item Spekular: Perfekte Spiegelung (Einfallswinkel = Ausfallswinkel)
\end{itemize}

\subsubsection{BRDFs}
Bidirektionale Reflektanz-Verteilungsfunktion (Bidirectional Reflectance Distribution Function)
\begin{itemize}
	\item Radiometrisches Konzept, um die Reflexion an einem Oberflächenpunkt zu beschreiben
	\item \textbf{Entwicklung von BRDFs}
	\begin{itemize}
		\item Messung von realen Materialproben mit einem Goniorereflektometer
		\item Phänomenologisch-motivierte Modelle: Wenige, intuitiv verständliche Parameter; nur in beschränktem Maße realistisch
		\item Physikalisch-motivierte Modelle: Exakte Resultate; Einstellung der Parameter allerdings schwierig
	\end{itemize}
\end{itemize}


\subsubsection{Phong-Bleuchtungsmodell}
Phänomologisches Modell, das die Reflexion mit drei Komponenten modelliert:
\begin{itemize}
	\item Ambient: Indirekte Beleuchtung, Licht von anderen Oberflächen
	\item Diffus: Nach dem Lambertschen Gesetz
	\item Spekular: Imperfekte Spiegelung
	\begin{itemize}
		\item Durch gerichtete Reflexion entstehen Glanzlichter
		\item Findet nur in Richtung des Ausfallswinkels statt (Geometrisch: Spiegelung des Lichtvektors an der Normalen)
		\item Größe des Fokus abhängig vom Phong-Exponenten und damit vom Material (großer Exponent \(\rightarrow\) kleiner Kegel)
	\end{itemize}
\end{itemize}

\subsubsection{Formel zur Berechnung}
\[I = k_a\cdot I_L + k_d\cdot I_L \cdot (N \cdot L) + k_s\cdot I_L \cdot (R_L \cdot V)^n\]

\subsubsection{Stereo-Rendering}
\textbf{Idee:} Für jedes Auge ein anderes Bild durch die Einführung einer zweiten Kamera.

\subsubsection{Schattierung von Dreiecksnetzen}
\begin{itemize}
	\item Stückweise lineare Approximation einer (gekrümmten) Oberfläche durch Dreiecke
	\item Flat Shading: Verwendung der Dreiecksnormale zur Beleuchtungsberechnung (Interpolation der Normalen der Eckpunkte)
	\item Scharfe Kanten brauchen mehrere Normalen
	\item Typischerweise werden drei Eckpunkte, drei Normalen sowie zusätzliche Attribute (beispielsweise Farben) gespeichert
	\item Phong Shading: Beleuchtungsberechnung mit interpolierten Normalen
\end{itemize}

\subsubsection{Licht und Schatten}
\begin{itemize}
	\item Objekte können Schatten werfen
	\item Schattenstrahl: Senden eines Strahls von der Oberfläche zur Lichtquelle hin, um zu gucken, ob ein anderes Objekt geschnitten wird
	\item Problem: Endliche Genauigkeit der Gleitkommadarstellung, dadurch treten Artefakte auf und die Strahl schneidet eventuell die Oberfläche von der er startet nochmal
	\item \textbf{Lösungen}
	\begin{itemize}
		\item Teste explizit, ob das geschnittene Objekt bereits geschnitten wurde
		\item Starte etwas weiter weg von der Oberfläche
	\end{itemize}
\end{itemize}

\subsubsection{Arten von Lichtquellen}
\begin{itemize}
	\item Punktlichtquellen: Definiert durch Position und Intensität. Bei realen Lichtquellen: Abfall der Intensität mit dem Abstandsquadrat
	\item Paralleles Licht: Definiert durch Richtung und Flussdichte, z.B. Sonnenlicht
	\item \textbf{Andere Lichtquellentypen}
	\begin{itemize}
		\item Strahler (Spot-Lights): Lichtkegel mit Abstrahlcharakteristik \(cos^n \Theta\)
		\item Flächenlichtquellen
		\item Punktlichtquellen mit Richtungscharakteristik
	\end{itemize}
\end{itemize}

\subsubsection{Primär- und Sekundärstrahlen}
\begin{itemize}
	\item Ray Tracing basiert auf den Gesetzen der geometrischen Optik
	\item Grundidee: Strahlenverfolgung vom Auge aus
	\item Rekursion um Spiegelung und Lichtbrechung darzustellen \(\rightarrow\) Sekundärstrahlen: Reflexionsstrahlen und Transmissionsstrahlen
	\item Steigende Genauigkeit mit steigender Rekursionstiefe
\end{itemize}

\subsubsection{Snellsches Brechungsgesetz}
\begin{itemize}
	\item Beschreiben der Richtungsänderung einer Welle (Licht) beim Übergang von einem Medium in ein anderes mit unterschiedlicher Brechungszahl
	\item Licht bewegt sich in unterschiedlichen Medien unterschiedlich schnell: \(\eta = \frac{c_{Vakuum}}{c_{Medium}}\)
	\item Die Brechzahl \(\eta\) ist wellenlängenabhängig \(\rightarrow\) Aufspaltung in unterschiedliche Wellenlängen (Dispersion)
	\item \textbf{Brechungsgesetz}
	\begin{itemize}
		\item \(\eta_i sin(\Theta_i) = \eta_t sin(\Theta_t)\)
		\item Übergang ins optisch dichtere Medium (\(\eta_t > \eta_i\)): Brechung zum Lot hin
		\item Übergang ins optisch dünnere Medium (\(\eta_t < \eta_i\)): Brechung vom Lot weg
	\end{itemize}
	\item Fresnel-Effekt: Verteilung der Strahlendichte
	\item Totalreflexion: Wird beim Übergang ein bestimmter Grenzwinkel überschritten wird der Strahl komplett reflektiert
\end{itemize}

\subsubsection{Aliasing}
\begin{itemize}
	\item Aliasing-Effekte entstehen durch (falsche) Abtastung von Signalen
	\item \textbf{Lösungsansätze}
	\begin{itemize}
		\item Filterung des Signals vor der Abtastung zur Entfernung von hohen Frequenzen: Im allgemeinen Fall nicht möglich
		\item Höhere Abtastrate des Signals und anschließend mitteln (Überabtastung, Supersampling)
	\end{itemize}
	\item Abtasttheorem von Nyquist und Shannon: Ein kontinuierliches, bandbegrenztes Signal mit einer maximalen Frequenz \(f_{max}\) muss mit einer Frequenz größer als \(2f_{max}\) abgetastet werden, damit aus dem diskreten Signal das Ursprungssignal exakt rekonstruiert werden kann.
\end{itemize}

\subsubsection{Supersampling-Strategien}
\begin{itemize}
	\item \textbf{Uniformes Supersampling}
	\begin{itemize}
		\item Statt Abtastung eines Punktes innerhalb eines Pixels wird \(k^2\)-mal im selben Intervall abgetastet
		\item Abstand zwischen den Samples muss immer gleich sein
	\end{itemize}
	\item \textbf{Adaptives Supersampling}
	\begin{itemize}
		\item Heute kaum noch verwendet
		\item Ist die Farbdifferenz benachbarter Samples zu groß, dann werden die Pixel mehrfach unterteilt
		\item Einfarbige Pixel benötigen im Schnitt nur ein Sample, Kanten werden trotzdem geglättet
	\end{itemize}
	\item \textbf{Stochastisches Supersampling}
	\begin{itemize}
		\item Uniformes Supersampling oft nicht ausreichend für um hohe Frequenzen aufzulösen
		\item Unterteilt Pixel in ein Gitter und wählt zufällig einen Punkt pro Zelle (Stratified Sampling)
		\item Reduziert Aliasing, führt aber zu mehr Rauschen, was allerdings von der menschlichen Wahrnehmung als weniger störend empfunden wird
	\end{itemize}
\end{itemize}


\subsection{Distributed Ray Tracing}

\subsubsection{Probleme des Whitted-Style Ray Tracing}
\begin{itemize}
	\item Bilder sehen zu makellos aus
	\item Perfekte Spiegelung und Transmission
	\item Harte Schattenkanten
	\item Unendlich Schärfentiefe
\end{itemize}

\subsubsection{Weiche Schatten}
\begin{itemize}
	\item Reale Lichtquellen besitzen endliche Ausdehnung
	\item Schatten beginnen am Objekt mit harten Kanten, die mit wachsendem Abstand weicher werden
\end{itemize}

\subsubsection{Bewegungsunschärfe}
\begin{itemize}
	\item Verteilung der Strahlen in der Zeit: Objekte bewegen sich in einem Zeitintervall
	\item Erzeuge verschiedene Strahlen pro Pixel und mittle die Farbwerte
	\item Vgl. Blichtungszeit bei realen Kameras
\end{itemize}

\subsubsection{Tiefenunschärfe}
\begin{itemize}
	\item "`Modell der dünnen Linse"'
	\item Verteilung der Strahlen in der Breite
	\item Wähle einen Punkt auf der Bildebene und der Linse und berechne dadurch den Punkt auf der Fokusebene
\end{itemize}

\subsection{Imperfekte Spiegelung und Transmission: Distributed Ray Tracing}
\begin{itemize}
	\item Mehrere Strahlen für Spiegelung und Transmission
	\item An jedem Schnittpunkt werden viele Sekundärstrahlen weiterverfolgt
	\item (Quasi-)zufällige Richtung
	\item Gewichtung nach der BRDF
	\item Durch Rekursion wird ein verzweigter "`Strahlenbaum"' aufgebaut
\end{itemize}



\section{Transformationen und homogene Koordinaten}
\begin{itemize}
	\item Eine Transformation bildet einen Punkt \(x\) auf einen Punkt \(x'\) ab
	\item Transformationen werden mit Abbildungsmatrizen beschrieben: \(T(x) = Ax\)
	\item Beispiele: Platzierung von Objekten, Animation, Deformation, Echtzeitschatten, usw.
\end{itemize}

\subsubsection{Grundlegende Transformationen}
\begin{itemize}
	\item Identität, Translation (Verschiebung), Rotation, isotrope Skalierung
	\item Können beliebig kombiniert werden
	\item Sind umkehrbar/invertierbar
\end{itemize}

\subsubsection{Transformationsgruppen}
\begin{itemize}
	\item Euklidische Transformationen: Erhalten Abstände, Inhaltsgrößen und Winkel (Translation, Identität, Rotation)
	\item Ähnlichkeitsabbildungen: Erhalten lediglich die Winkel (isotrope Skalierung, sowie alle euklidischen Transformationen)
	\item Lineare Abbildungen: Identität, Rotation, isotrope Skalierung, Skalierung, Spiegelung, Scherung
	\item Affine Abbildung: Parallele Linien werden erhalten (alle bisher genannten Abbildungen)
	\item Projektive Abbildungen: Geraden werden auf Geraden abgebildet (auch alle bisher genannten Abbildungen)
\end{itemize}


\subsection{2D Transformationen}
\begin{itemize}
	\item Beschreibung mittels Vektor-Matrix-Multiplikation
	\item Skalierung: Ändert Längen
	\item Scherung: Verschiebung parallel zu einer Achse (Flächeninhalt bleibt erhalten)
	\item Spiegelung: Spiegelungen sind negative Skalierungen
	\item Rotationen um den Winkel \(\phi\)
\end{itemize}

\subsubsection{Zusammengesetzte 2D Transformationen}
\begin{itemize}
	\item Hintereinanderausführen von Tranformationen
	\item Transformationen werden von rechts angewendet
	\item Im Allgemeinen nicht kommutativ: Reihenfolge ist entscheidend
\end{itemize}


\subsection{3D Transformationen}

\subsubsection{Rotation}
\begin{itemize}
	\item \(R_x\) dreht die \(y\)-Achse in Richtung \(z\)-Achse
	\item \(R_y\) dreht die \(z\)-Achse in Richtung \(x\)-Achse
	\item \(R_z\) dreht die \(x\)-Achse in Richtung \(y\)-Achse
\end{itemize}


\subsection{Affine Abbildungen}
\begin{itemize}
	\item Kombination aus linearer Abbildung und Translation
	\item \textbf{Eigenschaften}
	\begin{itemize}
		\item Linien werden auf Linien abgebildet, parallele Linien bleiben parallel
		\item Teilverhältnistreu
		\item Nicht winkelerhaltend
	\end{itemize}
	\item Beispiele: Rotation, Translation, Skalierung, Scherung
\end{itemize}


\subsection{Homogene Koordinaten}
\begin{itemize}
	\item Ergänzen den euklischen/affinen Raum um Fernpunkte
	\item Parallele Geraden schneiden sich
	\item Anwendung: Beschreiben von affinen Punkte und Richtungen, beschreiben von Translationen durch Matrizen
\end{itemize}

\subsubsection{Homogene Koordinaten bei affinen Abbildungen}
\begin{itemize}
	\item Ziel: Beschreibung von affinen Punkten und Richtungen, sowie affinen Abbildungen mit Matrizen
	\item Vorteil: Zusammengesetzte affine Transformation
	\item Hinzufügen einer \(1\) als dritte Koordinate (im 2D)
\end{itemize}


\subsection{Koordinatensysteme in der Computergrafik}
\begin{enumerate}
	\item Objektkoordinaten: Objekte in einer Szene werden zur Modellierung in ihrem eigenen Koordinatensystem angegeben
	\item Weltkoordinaten: Die Platzierung von Objekten erfolgt dann durch Translation, Rotation, Skalierung, etc.
	\item Kamerakoordinaten: Anschließend erfolgt die Transformation in das Kamerakoordinatensystem
\end{enumerate}


\subsection{Hierarchisches Modellieren}
\begin{itemize}
	\item Modellieren komplexer Szenen wird einfacher, wenn Kopien von Instanzen erstellt werden und Objekte zu Gruppen zusammengefasst werden
	\item Beispiel: Modell eines Autos mit Karosserie, Rädern, Reifen, Felgen und Schrauben
	\item Durch das Gruppieren von Objekten entsteht ein \textit{Szenengraph}
	\item Szenengraphen erlauben effiziente Operationen in komplexen Szenen
\end{itemize}


\subsection{Transformation von Normalen}
\begin{itemize}
	\item Lineare und affine Transformationen sind im Allgemeinen nicht winkeltreu \(\rightarrow\) Normalen können nicht einfach mittransformiert werden
	\item Verwendung von homogenen Koordinaten: Transformation der Tangentenebene zur Normalen, nicht den Normalenvektor selbst
\end{itemize}


\subsection{Transformationen und Schnitttests}
\begin{itemize}
	\item Schwierigkeit: Berechnung von Schnittpunkten bei zusammengesetzten Transformationen
	\item Idee: Schnittpunktberechnung in Modellkoordinaten
\end{itemize}



\section{Texturen}
\begin{itemize}
	\item Idee: Realistischeres Aussehen einer Oberfläche kann man durch "`Feinstrukturierung"' pro Pixel erreichen
	\item Geometrie wird mit Bildern kombiniert
	\item Texture Mapping: Wie wird einem Punkt auf der Oberfläche eine Stelle in der Textur zugeordnet?
\end{itemize}


\subsection{Mapping von Texturen}
\begin{itemize}
	\item 1D Textur: Parameter entlang einer der drei Achsen
	\item \textbf{2D Textur}
	\begin{itemize}
		\item Planare Projektion eines Bildes in der \(X-Y\)-Ebene
		\item Standardkörper mit natürlicher Parametrisierung (z.B. Punkte auf einer Kugel lassen sich mittels Polarkoordinaten ausdrücken)
		\item Sphärische Koordinaten oder zyklindrische Parametrisierung: Darstellung der Objektkoordinaten in Polarkoordinaten
		\item Würfel Parametrisierung: Würfeltextur wird dort ausgelesen, wo ein Strahl vom Objektmittelpunkt einen umgebenden Würfel schneidet
		\item Flächenparameter: Beschreibung beispielsweise mit Hilfe von Bézier-/Splinepatches
	\end{itemize}
	\item Zweiphasen-Mapping: Texturierung beliebiger Objekte mit Standardkörpern als Zwischenschritte
\end{itemize}

\subsubsection{Texturkoordinaten für Dreiecksnetze}
\begin{itemize}
	\item Parametrisierung für jeden Vertex wird in der Texturkoordinaten gespeichert
	\item Interpolation mit baryzentrischen Koordinaten
\end{itemize}

\subsubsection{Texture Wrapping}
\begin{itemize}
	\item Repeat/Wrapping: Fortsetzen einer Textur über \(\lbrack 0,1 \rbrack^2\) hinaus
	\item Adressierung wird für jede Dimension separat gewählt
\end{itemize}

\subsubsection{Texture Mapping und Aliasing}
\begin{itemize}
	\item Aliasingeffekte können durch Unterabtastung auftreten
	\item Entscheident: Verhältnis der Abtastfrequenz am Bildschirm zur Auflösung der projizierten Textur
\end{itemize}

\subsection{Texture Filterung}
\begin{itemize}
	\item \textbf{Vergrößerung (Magnification)}
	\begin{itemize}
		\item Abbildung weniger Texel auf viele Pixel
		\item Nearest Neighbor: Verwende Farbe des nächstliegenden Texels
		\item Bilineare Interpolation zur Glättung des Signals
	\end{itemize}
	\item \textbf{Textur-Filter}
	\begin{itemize}
		\item Die menschliche Wahrnehmung nimmt Unstetigkeiten nur bis zur zweiten Ableitung wahr \(\rightarrow\) Verwendung von Interpolation höherer Ordnung
		\item Bikubische Interpolation (benötigt Zugriff auf 4x4 Texel
	\end{itemize}
	\item \textbf{Verkleinerung (Minification)}
	\begin{itemize}
		\item Abbildung mehrerer Texel auf einen Pixel
		\item Wird nur ein Texel ausgelesen, obwohl der Pixel im Texturraum mehrere Texel bedeckt entstehen Aliasing-Artefakte durch Unterabtastung
		\item Möglichkeiten
		\begin{itemize}
			\item Vorfilterung des Signals (hohe Frequenzen vor der Abtastung entfernen)
			\item Überabtastung/Supersamling (in der Regel zu teuer)
		\end{itemize}
	\end{itemize}
	\item \textbf{Mip-Mapping}
	\begin{itemize}
		\item Einfache Vorfilterung von Texturen (Auflösungspyramide)
		\item Rekursive Speicherung von Texturen mit \(\frac{1}{4}\) Größe
		\item Meist Mittelung über je 2x2 Texel
		\item Insgesamt nur 33\% mehr Speicherbedarf
		\item Wahl der Mip-Map Stufe \(n\): \(Texelgroesse(n) \leq Groesse~Pixelfootprint~auf~Textur < Texelgroesse(n+1)\)
	\end{itemize}
	\item \textbf{Anisotrope Texturfilterung}
	\begin{itemize}
		\item Map-Mapping resultiert oft in sehr verschwaschenen Details
		\item Der Abdruck eines Pixels im Texturraum ist oft eher länglich
		\item RIPmaps (Rectangular MipMaps, in der Praxis selten): Rechteckige Vorfilterung entlang jeder Achse
		\item Vierfacher Speicherbedarf
	\end{itemize}
\end{itemize}

\subsubsection{Bestimmung des Footprints}
\begin{enumerate}
	\item Schicke einen Primärstrahl durch die Ecken eines Pixels
	\item Bestimme die vier Texturkoordinaten
	\item Differenzen der Texturkoordinaten liefern die Größe des Footprints
	\item Textur-Lookup an der berechneten Stelle mit der entsprechenden Filterung
\end{enumerate}

\subsubsection{Multitexturing}
\begin{itemize}
	\item Komplexe optische Effekte durch Kombination mehrerer Texturen
	\item Texturen enthalten oft auch andere Informationen, nicht nur Farbe
\end{itemize}


\subsection{Texturierungstechniken}
\begin{itemize}
	\item \textbf{Diffuse Textur}
	\begin{itemize}
		\item Kontrolle der Eigenfarbe eines Materials
		\item Bsp. Phong-Beleuchtungsmodell: \(k_d\) entstammt der Textur
	\end{itemize}
	\item \textbf{Bump oder Normal Mapping}
	\begin{itemize}
		\item Variation der Normalen einer Oberfläche durch Verwendung einer \textit{Bump Map} oder \textit{Displacement Map}
		\item Die Fläche bleibt geometrisch flach, nur die Normalen verändern sich
		\item Berechnung meist im Tangentenraum
	\end{itemize}
	\item \textbf{Gloss Map/Gloss-Textur}
	\begin{itemize}
		\item Kontrolle der Stärke und Streuung der spekularen Reflexion
		\item Bsp. Phong-Beleuchtungsmodell: \(k_s\) und \(n\) aus der Textur
	\end{itemize}
	\item \textbf{Displacement Mapping}
	\begin{itemize}
		\item Verschiebung der Oberfläche und Änderung der Normalen
		\item Keine reine Änderung der Beleuchtungsberechnung
		\item Bsp. Geometrie-Tesselierung und Verschiebung mit GPU-Unterstützung
	\end{itemize}
	\item \textbf{Inverse Displacement Mapping}
	\begin{itemize}
		\item Besonders schnelle Approximation, beispielsweise geeignet um Bodendetails darzustellen (Silhouetten meist problematisch)
		\item Geometrie wird nicht wirklich erzeugt, Schnittpunktberechnung wird im Texturraum durchgeführt
	\end{itemize}
	\item \textbf{Ambient Occlusion}
	\begin{itemize}
		\item Kontrolle des ambienten Anteils des Beleuchtungsmodells
		\item \(k_a\) entstammt der Textur, meistens wird auch der diffuse Term modifiziert
	\end{itemize}
	\item \textbf{Textur-Atlas}
	\begin{itemize}
		\item Spezielle Bijektive Parametrisierung: Jedem Oberflächenpunkt entspricht eine Stelle in der Textur
		\item Erstellung aufwendig per Hand oder automatisch
		\item Anwendungen
		\begin{itemize}
			\item Speichern einer Funktion/Daten auf der Oberfläche
			\item Erstellen der Textur direkt aus dem Objekt
			\item Berechnung von Normal-Maps aus fein aufgelösten Dreiecksnetzen
		\end{itemize}
	\end{itemize}
\end{itemize}


\subsection{Transparenz und Alpha-Test}
\begin{itemize}
	\item Rasterbilder werden oft mit 32 Bit/Pixel gespeichert (zusätzlicher 8 Bit Alpha-Kanal)
	\item (Semi-)Transparenz: Verwende Alpha-Kanal um die Transparenz der Oberfläche an einem Punkt zu bestimmen
	\item Alpha-Test: Verwerfe Objekt-/Schnittpunkt, wenn \(\alpha < threshold\)
\end{itemize}


\subsection{3D-Texturen für Oberflächen}
\begin{itemize}
	\item Probleme von 2D-Texturen: Tapeteneffekt, Verzerrung bei großer Flächenkrümmung
	\item \textbf{Solid-Texturen}
	\begin{itemize}
		\item "`Herausschneiden einer Skulptur"', z.B. aus einem Holz- oder Mamorblock
		\item Vorteil: Parametrisierung fällt weg
		\item Nachteil: Großer Speicherbedarf der Textur
		\item Erstellung sehr aufwendig
	\end{itemize}
	\item Solid-Textures: Prozedurales Erzeugen von 3D-Texturen
\end{itemize}


\subsection{Reflection/Environment-Mapping}
\begin{itemize}
	\item Darstellung reflektierender Objekte mit Spiegelung
	\item Approximation der Reflexion ohne Ray Tracing
	\item Idee: Speichern eines Bilds der Umgebung in einer Textur
	\item Entspricht anschaulich einer Textur auf einer virtuellen Kugel um ein Objekt/die Szene
	\item \textbf{Parametrisierungen}
	\begin{itemize}
		\item Latidute/Longtitude-Maps: Parametrisierung über Winkel, allerdings vergleichweise teuer in der Berechnung und ungleichmäßige Abtastung an den Polen
		\item Sphere-Mapping
		\begin{itemize}
			\item Speicherung ebenfalls in 2D-Textur
			\item Aufnahme soll mit einem Fotoapperat möglich sein
			\item Idealisierte Annahme: Bei der Aufnahme sollen alle Primärstrahlen parallel sein (kleine Spiegelkugel wird mit einem Teleobjekt fotografiert)
			\item Probleme
			\begin{itemize}
				\item Abtastrate maximal für Richtung entgegen der Aufnahmerichtung
				\item Singularität in Aufnahmerichtung (am Rand)
				\item Ungleiche Abtastung
			\end{itemize}
		\end{itemize}
		\item Kubische Environment Maps
		\begin{itemize}
			\item Abbilden der Umgebung auf einen Würfel
			\item Texturfilterung wie bei Mip-Mapping möglich
		\end{itemize}
	\end{itemize}
	\item \textbf{Aufnahme von Environment-Maps}
	\begin{itemize}
		\item In der Praxis: Meist mit spiegelnden Chromkugeln
		\item Mehrere Aufnahmen zum nachträglichen Entfernen des Fotoapparats (HDR-Fotografie)
		\item Umrechnung in andere Parametrisierungen möglich
	\end{itemize}
	\item \textbf{Vorfilterung}
	\begin{itemize}
		\item Statt mehrfachem Abtasten wird die Textur vorgefiltert
		\item Größe und Form des richtigen Winkelbereichs abhängig von Material und parametrisierung
	\end{itemize}
\end{itemize}



\section{Räumliche Datenstrukturen}

\subsubsection{Optimierung des Ray Tracings}
\begin{itemize}
	\item Der wesentliche Rechenanteil des Ray Tracings entsteht durch das Finden von Schnittpunkten (ca. 90\%, skaliert schlecht)
	\item \textbf{Optimierungsansätze}
	\begin{itemize}
		\item Schnellerer Schnittalgorithmen? Wenig Spielraum zur Optimierung
		\item Weniger Strahlen: Verlust von Details; Unschärfen
		\item Weniger Schnittberechnungen: Vermeidung von Berechnung bei weit entfernten Objekten
		\item Schnittpunkte mit "`dicken"' Strahlen (nicht Teil der Vorlesung)
		\item Einführung von Datenstrukturen zur Raumunterteilung
	\end{itemize}
\end{itemize}


\subsection{Raumunterteilung}

\subsubsection{Idee/Ziel}
\begin{itemize}
	\item Finde potentiell geschnittene Objekte schneller
	\item Teste keine Objekte, die nicht in Frage kommen
\end{itemize}


\subsection{Hüllkörper}
\begin{itemize}
	\item Reduziert Schnitttest: Prüfe, ob ein Schnitt mit einer Umgebungsgeometrie ("`Hüllkörper"') existiert \(\rightarrow\) schneller Ausschluss des Schnitttests
	\item Hüllkörper möglichst enganliegend
	\item Lohnen nur, wenn die Geometrie entsprechend detailliert ist
\end{itemize}

\subsubsection{Axis Aligned Bounding Box}
\begin{itemize}
	\item Sechs orthogonale Ebenen, die das Objekt umschließen
	\item Bestimme nahsten Schnittpunkt \textit{innerhalb} der Box
	\item \textbf{Optimierungen}
	\begin{itemize}
		\item Mehrere Strahlen parallel
		\item Hierarchien von Bounding Boxes
	\end{itemize}
\end{itemize}

\subsection{Bounding-Volume-Hierarchie}
\begin{itemize}
	\item Idee: Hierarchie von einschließenden Hüllkörpern, automatisches Zusammenfassen von Objekten und Gruppen von Objekten
	\item Vorteile: Adaptivität der Raumunterteilung; schnellere Suche, da Objektgruppen ausgeschlossen werden können
	\item \textbf{Aufbau der Hierarchie}
	\begin{enumerate}
		\item Bestimme die gemeinsame Bounding Box aller Objekte
		\item Teile die Objekte in zwei Gruppen auf
		\item Verfahre so rekursiv weiter
	\end{enumerate}
	\item Schnittberechnung: Überprüfe auf Schnitt mit der Wurzel und steige rekursiv ab. Prüfe anschließend die weiter entfernten Knoten
	\item Problem: Bei überlappenden Hüllkörpern können mehrere Schnittpunkte hintereinander entstehen
	\item \textbf{Fazit}
	\begin{itemize}
		\item Vorteile
		\begin{itemize}
			\item Konstruktion und Traversierung ist einfach
			\item Resultiert in einem Binärbaum: Fixe, geringe Verzweigung
			\item Komplixität: Im Mittel \(\mathcal{O}(log~n)\) Schnitttests statt \(\mathcal{O}(n)\)
		\end{itemize}
		\item Herausforderungen
		\begin{itemize}
			\item Finden einer guten Unterteilung ist schwierig
			\item Ungeschickte Unterteilung kann zu schlechter Aufteilung führen
		\end{itemize}
	\end{itemize}
	\item Performance: Beschleunigung 2200x (Aufbau nicht berücksichtigt)
\end{itemize}


\subsection{Regulär Gitter}
\begin{itemize}
	\item \textbf{Vorgehen}
	\begin{enumerate}
		\item Unterteilung des Raums in Zellen gleicher Forum und Größe
		\item Eintrag der Objekte in Zellen, die von ihnen geschnitten werden
		\item Traversierung der vom Strahl getroffenen Zellen
		\item Schnittberechnung mit den enthaltenen Objekten
	\end{enumerate}
	\item Vermeidung mehrfacher Schnitttests: Markiere Objekt als getestet
	\item Mailboxing: Cache Schnitttests, die außerhalb der Zelle sind
	\item \textbf{Fazit}
	\begin{itemize}
		\item Vorteile
		\begin{itemize}
			\item Einfach zu konstruieren
			\item Einfach zu traversieren
		\end{itemize}
		\item Nachteile
		\begin{itemize}
			\item In der Regel nur wenige Zellen belegt
			\item Unter Umständen viel Geometrie in wenigen Zellen konzentriert
		\end{itemize}
	\end{itemize}
	\item Performance: Beschleunigung 2200x (Aufbau nicht berücksichtigt)
\end{itemize}


\subsection{Adaptive Gitter}
\begin{itemize}
	\item Idee: Rekursive Unterteilung einer Zelle bis
	\begin{itemize}
		\item sie nur noch eine vorgegebene Anzahl Primitive enthält, oder
		\item eine maximale Zahl an Unterteilungen durchgeführt wurde
	\end{itemize}
	\item \textbf{Oktalbaum (Octrees)}
	\begin{itemize}
		\item Aufbau
		\begin{enumerate}
			\item Beginne mit der Bounding Box für die ganze Szene
			\item Rekursive 1-zu-8 Unterteilung
		\end{enumerate}
		\item Adaptive Unterteilung erlaubt große Schritte im leeren Raum
		\item Feine Unterteilung dort (und nur dort) wo Geometrie ist
		\item Traversierung relativ teuer: Viele Auf- und Abbewegung in der Hierarchie
	\end{itemize}
	\item \textbf{Verschachtelte Gitter}
	\begin{itemize}
		\item Kombination aus regulären Gittern und Octrees
		\begin{itemize}
			\item Nutze effiziente Traversierung von regulären Gittern
			\item Nutze Adaptivität einer hierarchischen Repräsentation
		\end{itemize}
		\item Aufbau
		\begin{enumerate}
			\item Grobes Gitter für Bounding Box der Szene
			\item Bounding Box von Objekt/Primitiv/Gruppen mit dicht gepackten Objekten werden durch neues Gitter ersetzt
		\end{enumerate}
		\item Problem: Was sind gute Gruppen?
	\end{itemize}
\end{itemize}


\subsection{Baumstrukturen}

\subsubsection{BSP-Baum (Binary Space Partitioning Tree)}
\begin{itemize}
	\item Idee: Erweiterung von Binärbäumen auf \(k\) Dimensionen
	\item Verwende Ebenen um den Raum rekursiv zu unterteilen \(\rightarrow\) ergibt Binärbaumstruktur
	\item Die Unterteilungsebenen können beliebig orientiert sein
	\item \textbf{Konstruktion}
	\begin{enumerate}
		\item Initialisiere Wurzelknoten: Enthält alle Objekte der Szene
		\item Unterteile bis maximale Elementzahl pro Knoten oder maximale Rekursionstiefe erreicht ist
		\item Teile die Primitive in einen rechten und einen linken Kindknoten auf
	\end{enumerate}
	\item \textbf{Vergleich mit BHV}
	\begin{itemize}
		\item Echte Raumunterteilung: Knoten überlappen sich nicht
		\item Gute Anpassung an Geometrie möglich
		\item Blattknoten speichern die Primitive, Knoten speichern die Split-Ebenen
	\end{itemize}
\end{itemize}

\subsubsection{kD-Baum}
\begin{itemize}
	\item Split-Ebenen senkrecht zu den Achsen
	\item Primitive, die eine Split-Ebene schneiden werden meist in beide Kindknoten eingefügt
\end{itemize}


\subsection{Konstruktion "`guter"' kD-Bäume und BHV}

\subsubsection{Bestimmunf der optimalen Schnittebene}
\begin{itemize}
	\item Räumliches Mittel: Teile Knoten in der Mitte entlang der Achse mit der größten Ausdehnung oder in regelmäßiger Reihenfolge (Aufwand in \(\mathcal{O}(n~log~n)\))
	\item Objektmittel: So dass beide Kindknoten gleich viele Elemente enthalten (Aufbau in \(\mathcal{O}(n~log^2~n)\))
	\item Kostenfunktion: Im Mittel sollen zufällige Strahlen, die den betrachteten Knoten schneiden den gleichen Aufwand verursachen. Daraus resultiert ein balancierter Baum (Aufwand in \(\mathcal{O}(n~log^2~n\))
\end{itemize}

\subsubsection{Surface Area Heuristic (Kostenfunktion)}
\begin{itemize}
	\item Idee: Stelle eine Kostenfunktion auf und minimiere
	\item Unterteilung nur dann, wenn die Kosten dadurch geringer werden, als den Schnitt mit allen Objekten des Knotens zu berechnen
	\item Einsetzbar für BSP-Bäume, kD-Bäume und BHVs
	\item Kostenoptimierte Unterteilung: Isolation von komplexen Szenenteilen mit großen dünnbesetzten/leeren Bereichen
	\item \textbf{Unterteilung/Bestimmung der Unterteilung}
	\begin{itemize}
		\item Aufwendig, da der Suchraum groß sein kann
		\item Daher meist approximierte Konstruktion
		\item Gut konstruierte Bäume bzw. BHVs können um ein Vielfaches schneller sein als schlecht optimierte
	\end{itemize}
\end{itemize}

\subsubsection{Richtungsunterteilung}
\begin{itemize}
	\item Idee: Unterteile Objekte nach der Richtung, in der sie liegen
	\item Optional: Jeweils nach Entfernung
	\item Beschleunigen beispielsweise Schattentests bei Punktlichtquellen
	\item Werden sehr selten eingesetzt
\end{itemize}

\subsubsection{Modernes Ray Tracing: SIMD-Optimierung}
\begin{itemize}
	\item Kohärente Strahlenpakete: Gruppen von Strahlen mit ähnlichem Ursprung und Richtung
	\item Können oft sehr schnell verarbeitet werden
\end{itemize}



\section{Rasterisierung, Clipping und Projektionstransformation}
Interaktive/Echtzeitgrafik basiert meist auf Rasterisierung
\begin{itemize}
	\item Repräsentation von Oberflächen meist durch Dreiecke
	\item Abbilden der Dreiecke auf 2D Bildschirmkoordinaten
	\item Rasterisierung der Dreicke
	\item Interpolation von Farben, Texturkoordinaten, Tiefenwert, etc
	\item Verdeckungsberechnung, Tiefentest
\end{itemize}


\subsection{Tiefenpuffer}
\begin{itemize}
	\item Idee: Speichere für jeden Pixel die Distanz zur nahsten Fläche
	\item Entfernung/Tiefenwert wird pro Vertex berechnet und interpoliert
	\item Zusätzlich zum Framebuffer gibt es einen Z-Buffer
	\item \textbf{Nachteile}
	\begin{itemize}
		\item Speicherbedarf (heutzutage nicht mehr)
		\item Begrenzte Genauigkeit
		\item Transparente Flächen können nicht behandelt werden
		\item Viel unnötiger Aufwand in Szenen mit hoher Tiefenkomplexität
	\end{itemize}
	\item \textbf{Vorteile}
	\begin{itemize}
		\item Dreiecke können in beliebiger Reihenfolge verarbeitet werden (wichtig für Grafikhardware)
		\item Z-Buffering ist Standard in allen Rasterisierern
		\item Für die meisten Probleme existieren heute spezielle Lösungen oder Render-Techniken
	\end{itemize}
\end{itemize}


\subsection{Clipping}
\begin{itemize}
	\item Abschneiden von Linien/Polygon-Teilen, die außerhalb des Bildschirms liegen
	\item Wichtig für die Effiziens, die Rasterisierung und beispielsweise auch für Constructive Solid Geometry
	\item Ansätze: On-the-fly während der Rasterisierung oder besser analytisch
\end{itemize}

\subsubsection{Clipping von Polygonen}
\begin{itemize}
	\item Naives Clipping: Brute-Force (Teste nur Pixel am Bildschirm) oder Scanline (zeichne nur Scanlines innerhalb des Bildes)
	\item \textbf{Sutherland-Hodgeman Polygon Clipping}
	\begin{itemize}
		\item Clipping gegen eine Kante nach der anderen
		\item Effizient: Nach jeder Kante erhält man ein geschlossenes Polygon; erlaubt Pipelining
	\end{itemize}
\end{itemize}


\subsection{Projektion}
Wir betrachten zwei Arten Projektionen:
\begin{itemize}
	\item Orthographische Kamera: Parallele Sichtstrahlen, senkrecht zur Bildebene
	\item Perspektifische Kamera: Sichtstrahlen ausgehend von einem Projektionszentrum
	\item Zusätzliches Koordinatensystem: Clip Kordinaten
	\item z-Wert zur Sichtbarkeitsbestimmung verwenden
	\item Gesucht: Projektionstranformation, die das Sichtvolumen auf den Einheitswürfel abbildet \(\rightarrow\) einheitliche Behandlung unterschiedlicher Projektionen
	\item \textbf{Optionen}
	\begin{enumerate}
		\item Clipping gegen das Frustum in Welt- oder Kamerakoordinaten, vor der Projekttransformation
		\item Clipping in homogenen Clip-Koordinaten, nach der Projekttransformation, aber vor dem Dehomogenisieren
		\begin{enumerate}
			\item Projektionstransformation
			\item Clipping in homogene Koordinaten
			\item Perspektivische Divison \(\rightarrow\) ergibt Normalized Device Coords. (Einheitswürfel)
			\item Projektion auf Bildschirmkoordinaten und Viewport Transformation
		\end{enumerate}
	\end{enumerate}
\end{itemize}

\subsubsection{Perspektivisch-korrekte Attribut-Interpolation}
\begin{itemize}
	\item Lineare Interpolation im Bildraum (bisher) führt zu Verzerrungen
	\item Lösung: Affine Interpolation (erhält die Längenverhältnisse)
\end{itemize}


\subsection{Rasterisierung vs. Raytracing}
\begin{itemize}
	\item \textbf{Rasterierung}
	\begin{itemize}
		\item Sehr effizient, Hardware-Umsetzung ist einfach
		\item Nur für Primärstrahlen: Globale Effekte (Schatten, Spiegelungen, etc) nur über spezielle Techniken
		\item Handhabung komplexer Szenen durch räumliche Datenstrukturen
		\item Spezielle Techniken, z.B. zur Einschränkung der Schattenberechnung auf sichtbare Flächen
		\item Echtzeit-Rendering
	\end{itemize}
	\item \textbf{Raytracing}
	\begin{itemize}
		\item Konzeptionell einfaches Verfahren
		\item Sekundärstrahlen, komplexe Beleuchtungseffekte sind einfach
		\item Handhabung komplexer Szenen durch räumliche Datenstrukturen
		\item Offline Rendering, bedingt interaktives Rendering
	\end{itemize}
\end{itemize}



\section{OpenGL und Grafik-Hardware}

\subsubsection{Verarbeitung in der Grafik-Pipeline}
\begin{itemize}
	\item Applikation
	\item Geometrieverarbeitung: Vertices \(\rightarrow\) Primitive
	\item Rasterisierung: Primitive \(\rightarrow\) Fragmente
	\item Pro-Fragment-Operationen: Fragmente \(\rightarrow\) Pixel
	\item Framebuffer
\end{itemize}


\subsection{OpenGL}
\begin{itemize}
	\item Plattform-, hardware und programmiersprachenunabhängige Programmierschnittstelle für Grafik-Hardware
	\item Fenstersystemneutral
	\item OpenGL implementiert die Grafik-Pipeline
	\item Zustandsmaschine: Die Verarbeitung in der Grafik-Pipeline wird konfiguriert; ein Zustand bleibt erhalten bis er explizit geändert wird
	\item Client-Server Konzept
	\item Shading Language GLSL für Programmierung der Geometrie- und Fragmentverareitung
	\item Heute sind große Teile der Grafik-Pipeline frei programmierbar
\end{itemize}


\subsection{Klassisches OpenGL}

\subsubsection{Struktur einer GLUT Anwendung}
\begin{enumerate}
	\item Initialisiere, konfiguriere und öffne Fenster mit Render-Kontext
	\item Initialisiere OpenGL States (es gibt einen Default-Zustand)
	\item Registriere Callback-Funktionen: Zeichnen, Benutzereingabe, Mauseingabe, Animation, etc
	\item Warte in Ereignisschleife
\end{enumerate}

\subsubsection{Bestandteile eines Framebuffers}
\begin{itemize}
	\item Color Buffer: Enthält die Pixeldaten mit den Farbwerten
	\item Z-Buffer: Enthält die Tiefenwerte
	\item Double Buffer: Front Buffer enthält das gerade dargestellte Bild, im Back Puffer wird unsichtbar das nächste Bild erzeugt
\end{itemize}

\subsubsection{Primitive und Vertex-Attribute}
\begin{itemize}
	\item Vertizes werden wie angegeben verbunden mit \textit{glBegin(primType); ...; glEnd();}
	\item Zusätzliche Attribute: \textit{glColor*();}, \textit{glNormal*();} oder \textit{glTexCoord*();}
	\item Globale Zustände müssen vor \textit{glBegin} gesetzt werden
\end{itemize}

\subsubsection{Vertizes in der Grafik-Pipeline}
\begin{enumerate}
	\item Primitive werden aus dem Strom von Vertices zusammengesetzt
	\item Zusammensetzen der Primitiven (Primitive Assembly)
	\item Clipping und Rasterisierung (ohne eigenes Zutun)
\end{enumerate}

\subsubsection{Transformations-Pipeline}
\begin{enumerate}
	\item Object: Vertex \(\rightarrow\) ModelView Matrix
	\item Eye: ModelView Matrix \(\rightarrow\) Projektionsmatrix
	\item Clip: Projektionsmatrix \(\rightarrow\) Perspective Division
	\item Normalized Device: Perspective Division \(\rightarrow\) ViewPort Transform
	\item Window: Viewport Transorm \(\rightarrow\)
\end{enumerate}

\subsubsection{Zusammengesetzte Transformationen}
\begin{itemize}
	\item Globale Sicht (wie wird das Objekt transformiert: Platzieren/Bewegen des Objekts relativ zum Ursprung der Weltkoordinaten; Reihenfolge im Code rückwärts
	\item Lokale Sicht (wie sieht das Koordinatensystem aus, in dem das Objekt liegt?): Bewege das lokale Koordinatensystem der Objekt; Reihenfolge im Code vorwärts
\end{itemize}

\subsubsection{Hierarchische Modellierung}
Verwende Push/Pop auf ModelView-Matrix-Stack.

\subsubsection{Backface Culling}
\begin{itemize}
	\item Bei Dreiecken und Polygonen wird zwischen Voder- und Rückseite unterschieden
	\item Flächen, auf deren Rückseite man blickt, kann man verwerfen lassen
\end{itemize}

\subsubsection{Beleuchtung und Schattierung}
\begin{itemize}
	\item Einschalten der Beleuchtungsberechnung: \(glEnable(GL\_LIGHTNING)\)
	\item Beleuchtungsberechnung in Kamerakoordinaten. OpenGL unterstützt nativ lediglich Gouraud Shading
	\item Gouraud Shading: Berechnung pro Vertex; Machsche Effekte, verpasste Glanzlichter
	\item Phong Shading: Berechnung der Beleuchtung pro Pixel/Fragment; Interpolation der Normale
	\item \textbf{Blinn-Phong-Modell}
	\begin{itemize}
		\item Abwandlung des spekularen Teils des Phong Modells
		\item Ersetzt den Reflexionsvektor \(R_L\) durch den \textit{Halfway-Vektor} \(H\) und einen neuen Exponenten: \(I_S = k_S \cdot I_L \cdot (N \cdot H)^n\)
		\item Beleuchtungsberechnung erfolgt pro Vektor
		\item Vertextfarbe setzt sich zusammen aus: Materialemission, globales ambientes Licht, abgeschwächte ambiente, diffuse und spekulare Beiträge aller Lichtquellen
		\item Nach der Beleuchtungsberechnung werden die Werte auf \(\lbrack 0;1\rbrack\) begrenzt
	\end{itemize}
\end{itemize}

\subsubsection{Z-Fighting}
\begin{itemize}
	\item Polygone, die sich in der selben Ebene überlagern bereiten Probleme
	\item Entstehung beispielsweise: Rundungsfehler bei der Tiefe bei projizierten Flächen
	\item Lösung: Tiefenwerte werden leicht um einen konstanten Offset und einen neigungsabhängigenOffset verschoben
\end{itemize}

\subsubsection{Rasterisierung und Antialiasing}
\begin{itemize}
	\item Verwendung von (starrem) Supersampling: Fixes Abtastschema mit anschließender Mittelung der "`Subpixels"'
	\item \textbf{Coverage Sample Antialiasing}
	\begin{itemize}
		\item Verwendet einige Samples (z.B. 4) wie bisher
		\item Weitere Samples (z.B. 12) nur zur Berechnung der Sichtbarkeit
		\item Zuordnung schattierte Samples und Sichtbarkeits-Samples
		\item Idee: Schattierungsberechnung ist teurer als Sichtbarkeit
	\end{itemize}
	\item In OpenGL: Festgelegt bei der Erzeugung des Framebuffers (z.B. mit \(GLUT\_MULTISAMPLE\))
\end{itemize}


\subsection{Modernes OpenGL}
\begin{itemize}
	\item Die OpenGL-API hat sich mit der Hardware weiterentwickelt (extrem hohe Rechenleistung von GPUs)
	\item Wesentliche Änderungen mit dem Ziel eine schlankere API zu schaffen: Keine Fixed-Function-Pipeline und keine Hilfsfunktionen mehr
	\item Core Profil: Entrümpelt, alle alte Funktionalität muss selbst programmiert werden
	\item Kompatibilitätsprofil für die alte Funktionalität
\end{itemize}

\subsubsection{OpenGL Pipeline}
\begin{enumerate}
	\item \textbf{Geometrieverarbeitung: Vertex Shader}
	\begin{itemize}
		\item Programmierung mit der C-ähnlichen OpenGL Shading Language
		\item Transformation einzelner Vertizes und Verarbeitung deren Attribute
		\item Keine Vertexerzeugung/Vertexlöschung/Informationen über andere Vertizes
		\item Berechnung von Attributen, die für Fragmente interpoliert werden sollen: Z.B. Beleuchtung per Vertex (Gouraud Shading) oder Normalen für Phong Shading
	\end{itemize}
	\item \textbf{Geometrieverarbeitung: Assembly und Tessellation}
	\begin{itemize}
		\item Primitive Assembly: Setzt aus den Vertices die angeforderten Primitive zusammen und ist nicht programmierbar
		\item Tessellation
		\begin{enumerate}
			\item Tessellation Control Shader: Bestimmt die Unterteilung
			\item Tessellation: Führt die Unterteilung durch (nicht programmierbar)
			\item Tessellation Evaluation Shader: Arbeitet auf der resultierenden Geometrie
		\end{enumerate}
	\end{itemize}
	\item \textbf{Geometrieverarbeitung: Geometry Shader, Clipping, Rasterization}
	\begin{itemize}
		\item Geometry Shader: Bearbeitet Primitive; kann Primitive vervielfachen, entfernen, umwandlen; programmierbar; optional
		\item Clipping: Verwirft unsichtbare Punktprimitive; verändert Dreiecke durch Schnitt mit Sichtvolumen; nicht programmierbar
		\item Anschließend: Perspektivische Division (nicht programmierbar) und Rasterisierung zur Generation von Fragmenten für den Ausgabepuffer
	\end{itemize}
	\item \textbf{Fragmentverarbeitung}
	\begin{itemize}
		\item Wird für jedes Fragment ausgeführt
		\item Berechnet Farbe, Transparenz und optional Tiefe pro Fragment (z.B. Phong Shading)
		\item Eingabe-Attribute werden innerhalb des Primitivs interpoliert
		\item Tiefentest und Blending
	\end{itemize}
\end{enumerate}

\subsubsection{Möglichkeiten mit programmierbarer Grafik-Hardware}
\begin{itemize}
	\item Beliebige Beleuchtungsberechnung und Materialen programmierbar: Direkte, prozudurale Texturierung; komplexe Datenstrukturen
	\item Komplexe Geometrieberechnung und Animation
\end{itemize}

\subsubsection{Texturen in OpenGL}
\begin{itemize}
	\item Rasterbilder mit frei wählbarer Größe, Komponentenzahl, Layout, Datentyp
	\item Texturen sind OpenGL-Objekte
	\item Müssen zur Verwendung an Textureinheiten gebunden werden
	\item Automatische Erzeugung von MipMaps
	\item Texture Wrapping: Forsetzen von quadratischen Texturen
\end{itemize}

\subsubsection{Index Buffers und Shared Vertex Repräsentation}
\begin{itemize}
	\item Indexed Face Set: Verwende Array mit Vertizes und weiteren Attributen
	\item Vorteil: Weniger Daten (ein Vertex ist Eckpunkt mehrerer Dreiecke)
	\item Vertex Cache: GPUs speichern Ergebnisse der letzten verarbeiteten Vertizes, funktioniert nur mit indizierten Vertizes
\end{itemize}

\subsubsection{Shadow Mapping}
\begin{itemize}
	\item Idee: Eine Textur speichert, wie weit die nahsten Oberflächen von der Lichtquelle entfernt sind
	\item Wir betrachten hier nur Spotlight, gedankliches Ersetzen der Lichtquelle durch eine Kamera
	\item Die gespeicherte Entfernung entspricht der tatsächlichen Entfernung
	\item Für jede Lichtquelle kann eine Shadow Map erzeugt werden, die später während dem Rendering als Schattentest verwendet wird
	\item Funktioniert eingeschränkt auch mit klassischem OpeGL
\end{itemize}

\subsubsection{Fragmentverarbeitung}
\begin{itemize}
	\item Durch Rasterisierung werden Fragmente erzeugt
	\item Vor dem Schreiben in den Framebuffer müssen die Fragmente Tests und Framebuffer-Operationen durchlaufen
	\begin{enumerate}
		\item Scissor Test
		\begin{itemize}
			\item Entfernt Fragmente außerhalb eines Rechtecks
			\item Wird verwendet, um kleinere Bereiche des Fensters zu aktualisieren
			\item Vergleichbar mit einer rechteckigen Stencil-Maske
		\end{itemize}
		\item Stencil Test
		\begin{itemize}
			\item "`Stanzmaske"', die oft verwendet wird, um Zustände für jeden Pixel zu speichern
			\item Es kann entschieden werden, ob ein Fragment gezeichnet wird
			\item Typische Anwendungen: Maskierung von Anwendungen, projektive Schatten, Stencil Routing
		\end{itemize}
		\item Tiefentest (Depth Buffer Test)
		\item Blending: Farbkombination von erzeugten Fragmenten und Pixel; jede Komponente wird separat berechnen
		\item Dithering: Historisch, nur für Hardware ohne TrueColor Darstellung
	\end{enumerate}
\end{itemize}

\subsubsection{Alpha-Test}
\begin{itemize}
	\item Idee: Verwerfe Fragmente aufgrund ihres Alpha-Wertes (Definition einer Schranke)
	\item Im Core-Profil von modernem OpenGL nicht mehr vorhanden
	\item Muss händisch implementiert werden, ist dann aber flexibler als ein konfigurierbarer Alpha-Test
\end{itemize}

\subsubsection{Blending}
\begin{itemize}
	\item Anwendungsbeispiel: Zeichnen eines semitransparenten Objekts über ein opakes
	\item \textit{glBlendFunc(GL\_SRC\_ALPHA, GL\_MINUS\_SRC\_ALPHA)}
	\item \textit{glBlendEquaction(GL\_FUNC\_ADD)}
\end{itemize}

\subsubsection{Semitransparente Objekte}
\begin{itemize}
	\item Darstellung semitransparenter Objekte erfordert Tiefensortierung, weil Blending im Allgemeinen nicht kommutativ ist
	\item Semitransparenz ohne Blending: Setze Pixel beim Rasterisieren entsprechend eines Binärmusters mit Anteil der Einsen entsprechend der Opazität. Wichtig: Unterschiedliche Muster, sonst kein Transparenzeffekt
\end{itemize}

\subsubsection{Accumulation Buffer}
\begin{itemize}
	\item Zwischenspeichern zur Kombination mehrerer Rendering-Schritte mit anschließender Durchschnittsbildung
	\item Zeichne mehrerer Bilder zu verschiedenen Zeitpunkten
	\item Anwendungen: Beispielsweise Bewegungsunschärfe, Tiefenunschärfe, weiche Schatten, Antialiasing
\end{itemize}

\subsubsection{Stereo/Double Buffering}
\begin{itemize}
	\item Erzeuge je ein Bild für jedes Auge
	\item Quad Buffer benötigt (2x Front und 2x Back Buffer)
\end{itemize}



\section{Prozedurale Modelle}
\begin{itemize}
	\item Kompakte Beschreibung statt Speicherung
	\item Erzeugung von großen Szenen oder viel Inhalt
	\item Modellieren von natürlichen Phänomenen
\end{itemize}


\subsection{Rauschen, Turbulenzen und prozedurale Texturen}
\begin{itemize}
	\item \textbf{Zufallszahlen}
	\begin{itemize}
		\item Weißes Rauschen: Energie in allen Frequenzbereichen verteilt
		\item Rotes Rauschen: Energie vor allem in niedrigen Frequenzen \(\rightarrow\) Kohärenz
	\end{itemize}
	\item Natürliche Objekte zeigen stochastische Veriationen bei räumlicher Kohärenz \(\rightarrow\) zufällige Strukturen können aus Rauschtexturen berechnet werden
	\item \textbf{Anorderungen an Rausch-/Noise-Funktionen}
	\begin{itemize}
		\item Reproduzierbar
		\item Keine (sichtbare) Periodizität
		\item Begrenzter Wertebereich und definierte Frequenzverteilung
		\item Räumliche Korrelation
	\end{itemize}
\end{itemize}

\subsubsection{Noise-Funktionen nach Ken Perlin (1985)}
\begin{itemize}
	\item \textit{Die} Grundlage für stochastische Modellierung/prozedurale Texturen
	\item Erzeugen Bilder aus Pseudozufallszahlen
	\item \textbf{Klassen von Noise-Funktionen}
	\begin{itemize}
		\item Lattice Value Noise: Werte aus einem Gitter
		\item Lattice Gradient Noise (nicht Teil der Vorlesung)
	\end{itemize}
\end{itemize}

\subsubsection{Lattice Value Noise}
\begin{itemize}
	\item Pseudozufallszahlen aus einem Gitter
	\item Räumliche Korrelation und Bandbegrenzung durch Interpolation
	\item Unterschiedlicher Abstand liefert ein anderes Frequenzspektrum
	\item \textbf{Elegantes Vorgehen zur Erzeugung}
	\begin{enumerate}
		\item Erzeuge einmalig ein 1D-Array mit Zufallszahlen
		\item Verwende Hash-Funktion um darauf zuzugreifen
	\end{enumerate}
\end{itemize}

\subsubsection{Rauschen}
\begin{itemize}
	\item Ausswertung der Noisefunktion an Position \(x\) mit Frequenz \(f\) und Offset \(o\): \(n(fx+o)\)
	\item Die Fequenz bestimmt die Größe der Strukturen
\end{itemize}

\subsubsection{Turbulenz}
\begin{itemize}
	\item Spektrale Synthese: Kombination unterschiedlicher Frequenzbereiche
	\item (Gewichtete) Summe von \(k\) Oktaven: \(turbulence(x) = \sum_k (\frac{1}{2})^k \cdot n \cdot (2^k\cdot x)\)
	\item Turbulenz mit Strukturen: Color Mapping durch eine Sinus-Funktion
	\item Können kombiniert werden
	\item \textbf{Beispiel: Feueranimation}
	\begin{itemize}
		\item 4D-Turbulenztextur mit mehreren Oktaven
		\item Zeitliche Variationen: Räumliche Kohärenz wird zu zeitlicher Kohärenz
	\end{itemize}
	\item \textbf{Weitere Anwendungen}
	\begin{itemize}
		\item Bump/Displacement Mapping: Noise-/Turbulenzfunktion als Höhenfeld
		\item Prozedurale Landschaften: Höhenfelder und Texturen generiert aus Noise-Funktion
	\end{itemize}
\end{itemize}

\subsubsection{Prozedurale Texturen}
\begin{itemize}
	\item \textbf{Algorithmische Beschreibung von Texturen}
	\begin{itemize}
		\item Kompakte Repräsentation
		\item Auflösungsunabhängig
		\item Für beliebig große Flächen
		\item Parametrisierbar (z.B. mehrere Sorten Holz)
	\end{itemize}
	\item \textbf{Implizite Methode}
	\begin{itemize}
		\item Aufruf des Shaders für jeden Pixel/Schnittpunkt
		\item Benötigt eventuell Zugriff auf benachbarte Pixel
		\item Filterung st nicht trivial (bei Turbulenzen schon)
	\end{itemize}
	\item \textbf{Explizite Methode}
	\begin{itemize}
		\item Generiere 2D/3D-Textur vor der Verwendung
		\item Verwende Texture-Mapping
		\item Vorteil: Texture-Filtering ist einfach
	\end{itemize}
\end{itemize}


\subsection{Textursynthese}
\begin{itemize}
	\item Oft kleine Textur (Exemplar) vorgegeben (z.B. extrahiert aus einer Fotografie)
	\item Kachelung führt zu sichtbaren Wiederholungen
	\item Ziel: Berechnen einer großen Textur, die genauso "`aussieht"'
	\item Verfahren in der Vorlesung langsam: Keine Auswertung zur Laufzeit
\end{itemize}

\subsubsection{Pixelbasierte Textursynthese}
\begin{itemize}
	\item Ausgabetextur wird Pixel für Pixel erzeugt
	\item Betrachte Nachbarschaft des nächsten zu erzeugenden Pixels (Nachbarschaft i.d.R. klein, aber groß genug um die Struktur aufzufassen) und suche ähnliche Nachbarschaften in der Eingabetextur
	\item Kopiere den Pixel einer der ähnlichsten Nachbarschaften mit stochastischer Variation
	\item Durch die Suche nach Nachbarschaften sehr langsam
	\item Berücksichtigung der Perspektive ist möglich
\end{itemize}


\subsection{Hypertextures}
\begin{itemize}
	\item Ziel: Erzeugung von komplexen 3D Texturen (beispielsweise Feuer oder Wolken)
	\item Beschreibung der Hypertexture-Objekte durch eine Dichtefunktion \(D\) im \(\mathbb{R}^3\)
	\item \textbf{Dichtefunktion}
	\begin{itemize}
		\item Innen: \(D(X) = 1\); außen: \(D(x) = 0\); Übergangsbereich: \(0 < D(x) < 1\)
		\item Beispiel: Dichtefunktion ohne Transparenz:  \(D(x) = sphere \bigg(x\cdot \Big( 1+\sum_i \frac{1}{2^i} \cdot n(2^i f x) \Big) \bigg),~sphere(x)=\begin{cases} 1 & |x| < 1 \\ 0 & sonst \end{cases}\)
	\end{itemize}
	\item Ray Marching (opake Objekte): Gehe in kleinen Schritten den Strahl entlang und prüfe, ob \(D(X) = 1 \); viele verschiedenen Optimierung (Anpassen der Schrittweite, binäre Suche, etc.)
	\item Ray Marching (semitransparente Objekte): Akkumuliere Opazität entlang des Strahls
\end{itemize}


\subsection{Distanzfelder}
\begin{itemize}
	\item Implizite Darstellung von soliden Objekten
	\item Eine Distanzfunktion liefert zu jedem Punkt \(x\) die kürzeste Entfernung zur Oberfläche \(f(x) = 0\)
	\item Beispiel: Kugel mit \(f(x) = |x-m|-r\)
	\item Wird \(f(x)\) diskret gespeichert (beispielsweise in einer 3D-Textur), dann spricht man von einem Distanzfeld
	\item \textbf{Schnittpunktberechnung}
	\begin{itemize}
		\item Shere Tracing: Finden des Schnittpunkts durch Ray Marching unter Ausnutzung der Distanzfunktion (man kann immer eine Strecke \(f(x)\) zurücklegen, ohne einen Schnittpunkt zu verpassen)
		\item Mehrere Schritte für Strahlen, die Objekte knapp verpasst haben
	\end{itemize}
	\item \textbf{Verknüpfung von Distanzfunktionen: Constructive Solid Geometry (CSG)}
	\begin{itemize}
		\item Verwende Boolsche Algebra, um komplexe Objekte zu erzeugen
		\item Verknüpfung von Operationen um neue Objekte zu erhalten
		\item CSG ist auch mit anderen Repräsentationen möglich (z.B. Dreiecksnetze), aber u.U. deutlich aufwendiger
	\end{itemize}
\end{itemize}


\subsection{L-Systeme}
\begin{itemize}
	\item Theoretisch Modell für biologische Entwicklung und Morphogenese
	\item Idee: Definiere ein komoplexes Objekt durch sukzessives Ersetzen von Teilen eines einfachen Objekts
	\item Fraktale: Geometrisches Muster/Gebilde mit hohem Grad an Selbstähnlichkeit
	\item Selbstähnlichkeit in der Natur ist nicht exakt und dritt nur auf wenigen diskreten Skalen auf
	\item \textbf{Ersetzungssysteme}
	\begin{itemize}
		\item L-Systeme arbeiten nach Chomskys formalen Grammatiken
		\item Defintion über Alphabet, Terminalsysmbol, Startwort, Produktionsregeln und Interpretationsvorschrift
		\item Verzweigungen: Erweiterung um einen Stack, der den aktuellen Zustand halten kann (dabei wird keine Linie gezeichnet)
	\end{itemize}
	\item Rein algorithmische Erzeugung bestimmter Pflanzenteile (z.B. Knospenanordnung) ist manchmal unflexibel und erfordert viel Übung: Daher oft um parametrisierte, stachastische Ersetzungsregeln order Spezialsymbole, die direkte Geometrie erzeugen (z.B. Blätter), erweitert
\end{itemize}


\subsection{Fazit}
\begin{itemize}
	\item Prozedurale Modellierung ist ein mächtiges Werkzeug...
	\item ...machnal aber schwer zu kontrollieren
	\item Zunehmend wichtiger in Spielen, Filmen, etc.
	\item Durch kompakte Beschreibung eine ideale Form der "`Datenkompression"'
\end{itemize}



\section{Kurven und Flächen}
\begin{itemize}
	\item Definition einer glatten, parametrischen Kurve \(P(u)\) durch Platzieren einer "`Kontrollpunkte"'
	\item Interpolation: Kurve geht durch alle vorgegebenen Punkte: Kann instabil sein und Überschwinger erzeugen
	\item Approximation: Die Kurve geht nicht durch alle Punkte (oder auch durch gar keinen): Erlaubt Kurfen mit "`angenehmeren"' Eigenschaften
\end{itemize}

\subsubsection{Beispiel Bézierkurven}
\begin{itemize}
	\item Definiert durch vier Kontrollpunkte \(b_i\)
	\item Die Kurve geht durch \(b_0\) und \(b_3\) und approximiert \(b_1\) und \(b_2\)
	\item Die Kurve liegt innerhalb der konvexen Hülle ihrer Kontrollpunkte
	\item Mathematische Beschreibung mit einem kubischen Polynom \(P(u) = (1-u)^3b_0 + 3u(1-u)^2b_1 + 3u^2(1-u)b_2 + u^3b_3\)
\end{itemize}


\subsection{Polynomkurven}
\begin{itemize}
	\item \(d\)-dimensionale Polynomkurve mit \(P(u) = \sum_{i=0}^n a_iui,~a_i \in \mathbb{R}^d\)
	\item Bernstein-Polynome \(B_i^3\) als Gewichtungsfunktion
	\item Anschaulich: Jedes \(B_i^3\) legt den Einfluss von \(b_i\) auf die Kurve an der Stelle \(u\) fest
\end{itemize}


\subsection{Bézierkurven}
\begin{itemize}
	\item Allgemeine Definition: \(F(u) = \sum_{i=0}^n B_i^n(u) \cdot b_i,~b_i \in \mathbb{R}^d\)
	\item \textbf{Eigenschaften}
	\begin{itemize}
		\item Bernstein-Polynome vom Grad 1 resultieren in lineare Interpolation
		\item \(F(u)\) liegt ind er konvexen Hülle des Kontrollpolynoms
		\item Variationsreduzierung: "`Eine Bézierkurve \(F\) wackelt nicht stärker als ihr Kontrollpolygon \(B\)"'
	\end{itemize}
\end{itemize}

\subsubsection{Algorithmus von de Casteljau}
\begin{itemize}
	\item Effiziente Auswertung und Unterteilung von Bézierkurven
	\item Berechnung von \(F(u) = \sum_i\ B_i^n(u)b_i\) durch fortgesetzte lineare Interpolation, ohne die Bernstein-Polynome zu berechnen
\end{itemize}


\subsection{Béziersplines}
\begin{itemize}
	\item Modellieren von komplexeren Formen mit Bézierkurven
	\begin{enumerate}
		\item Verwende eine Bézierkurve von hohem Grad
		\item Füge mehrere Bézierkurven niedrigen Grades stückweise aneinander
	\end{enumerate}
	\item Béziersplines: Stückweise polynomielle Kurve, deren einzelne Abschnitte durch Bézierkurven beschrieben sind
	\item \textbf{Stetigkeit}
	\begin{itemize}
		\item \(C^0\)-stetig: Stetig, keine Sprungstelle
		\item \(C^1\)-stetig: Zusätzlich gleicher Tangentenvektor
		\item \(C^2\)-stetig: Zusätzlich gleicher Schmiegekreis
	\end{itemize}
\end{itemize}


\subsection{Tensorproduktflächen}
\begin{itemize}
	\item Erweiterung einer zweidimensionalen Kurve durch eine weitere zweidimensionale Kurve zu einer Fläche (Tensorprodukt-Bézier-Fläche)
	\item \(S(u,v) = \sum_{i=0}^n \sum_{j=0}^m B_i^n(u) \cdot B_j^m(v) \cdot b_{i,j}\)
	\item Die Kontrollpunkte \(b_{i,j}\) bilden das Kontrollnetz
	\item \textbf{Eigenschaften}
	\begin{itemize}
		\item Konvexe Hülle-Eigenschaft
		\item Interpolation der vier Ecken des Kontrollnetztes
		\item Die Fläche ist tangential zu den Exkpunkten
		\item Die Rundkurven der Flche sind Bézierkurven
		\item Variationsreduzierung gilt nicht
	\end{itemize}
\end{itemize}


\section{Appendix A: Baryzentrische Koordinaten}
Baryzentrische Koordinaten dienen in der linearen Algebra und in der Geometrie dazu, die Lage von Punkten in Bezug auf eine gegebene Strecke, ein gegebenes Dreieck, ein gegebenes Tetraeder oder allgemeiner ein gegebenes Simplex zu beschreiben. Der Punkt wird dargestellt durch die Koeffizienten einer Affinkombination (also einer Linearkombination von Punkten, bei der die Summe der Koeffizienten 1 ist).\footnote{\url{http://de.wikipedia.org/wiki/Baryzentrische_Koordinaten}}

\subsubsection{Geometrische Interpretation}
\[\lambda_1 = \frac{A_{\triangle}(Q,P_2,P_3)}{A_{\triangle} (P_1,P_2,P_3)}, \lambda_2 = \frac{A_{\triangle}(Q,P_1,P_3)}{A_{\triangle} (P_1,P_2,P_3)}, \lambda_3 = \frac{A_{\triangle}(Q,P_1,P_2)}{A_{\triangle} (P_1,P_2,P_3)}\]

\subsection{Anwendungen}

\subsubsection{Liegt ein Punkt innerhalb eines Dreiecks?}
Der Punkt \(Q = \lambda_1 P_1 + \lambda_2 P_2 + \lambda_3 P_3\) liegt innerhalb des Dreiecks \(\triangle(P_1,P_2,P_3)\), wenn \(\lambda_1,\lambda_2,\lambda_3\) positiv sind.

\subsubsection{Lineare Interpolation von Farbwerten}
\begin{itemize}
	\item \textbf{Gegeben:} Eine Farbe \(c_1,c_2,c_3\) als RGB-Triple zu jedem Eckpunkt.
	\item \textbf{Gesucht:} Die interpolierte Farbe \(c_Q\) an einem Punkt \(Q\) auf dem Dreieck
	\item \textbf{Lösung:} Berechne \(\lambda_1,\lambda_2,\lambda_3\), dann ist \(c_Q=\lambda_1 c_1+\lambda_2 c_2 + \lambda_3 C_3\)
\end{itemize}

\subsubsection{Berechnung des Schnittpunkts eines Dreiecks und einer Geraden}
\begin{enumerate}
	\item \(r(t) = e+t\cdot d\), \(|d|=1\)
	\item Gleichsetzen
	\begin{itemize}
		\item \(r(t) = Q(\lambda_2,\lambda_3)\)
		\item \(e+t\cdot d = P_1+\lambda_2(P_2-P_1)+\lambda_3(P_3-P_1)\)
		\item Schnittpunkt, wenn \(\lambda_2+\lambda_3<1 \wedge \lambda_2 > 0 \wedge \lambda_3 >0\)
	\end{itemize}
	\item 3 Gleichungen mit 3 Unbekannten: \(e_x+t\cdot d_x=P_{1,x}+\lambda_2(P_{2,x}-P_{1,x})+\lambda_3(P_{3,x}-P_{1,x},...\)
	\item Lösung mittels Cramerscher Regel
	\begin{itemize}
		\item Baryzentrische Koordinaten müssen noch auf Positivität getestet werden
		\item Direkte Umsetzung im Programmcode
		\item Effizient, ohne Umweg über Ebenengleichung
	\end{itemize}
\end{enumerate}



\section{Appendix B: Transformationen}

\subsection{2D Transformationen}

\subsubsection{Skalierung}
\[scale(s_x,s_y) = \begin{pmatrix} s_x & 0 \\ 0 & s_y \end{pmatrix}\]

\subsubsection{Scherung horizontal}
\[shear_x(s) = \begin{pmatrix} 1 & s \\ 0 & 1 \end{pmatrix}\]

\subsubsection{Scherung vertikal}
\[shear_y(s) = \begin{pmatrix} 1 & 0 \\ s & 1 \end{pmatrix}\]

\subsubsection{Spiegelung}
\[\begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}~bzw.~\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\]

\subsubsection{Rotation}
\[rotate(\phi) = \begin{pmatrix} cos\phi & -sin\phi \\ sin\phi & cos\phi \end{pmatrix}\]


\subsection{3D Transformationen}

\subsubsection{Rotation}
\[R_x(\phi) = \begin{pmatrix} 1 & 0 & 0 \\ 0 & cos\phi & -sin\phi \\ 0 & sin\phi & cos\phi \end{pmatrix}\]
\[R_y(\phi) = \begin{pmatrix} cos\phi & 0 & sin\phi \\ 0 & 1 & 0 \\ -sin\phi & 0 & cos\phi \end{pmatrix}\]
\[R_z(\phi) = \begin{pmatrix} cos\phi & -sin\phi & 0 \\ sin\phi & cos\phi & 0 \\ 0 & 0 & 1 \end{pmatrix}\]



\section{Appendix C: OpenGL Shading Language (GLSL)}
\begin{itemize}
	\item Separate Verarbeitung pro Vertex, Primitiv oder Fragment
	\item Shader sind OpenGL-Objekte und stehen über OpenGL-Aufrufe zur Verfügung
	\item C-ähnlich
	\item Funktionen und Überladen von Funktionen ist möglich
	\item Rekursion ist nicht vorgesehen, da es keinen Stack auf GPUs gibt
\end{itemize}

\subsubsection{Datentypen}
\begin{itemize}
	\item Basis-Datentypen: float, double, bool, int, half
	\item Vektoren mit 2,3 oder 4 Komponenten: \(vec\{x,y,z\}\)
	\item Matrizen 2x2, 3x3 oder 4x4: [d]mat2
	\item Sampler: Speichern von Textureinheiten \(sampler\lbrack 1,2,3\rbrack D\)
\end{itemize}

\subsubsection{Definition des Verwendungszweck von Variablen}
\begin{itemize}
	\item \(const\): Konstante, zur Compile-Zeit festgelegt
	\item \(uniform\): read-only, globale Variablen, die pro Aufruf konstant bleiben und von der Applikation gesetzt werden
	\item \(in\): Eingabeattribut des aktuellen Shaders
	\item \(out\): Ausgabeattribut des aktuellen Shaders
	\item \(attribute\): Vertexattribute, read-only, nur im Vertex-Shader
	\item \(varying\): Weitergegebene/interpolierte Werte
\end{itemize}

\subsubsection{Transformationspipeline}
\begin{itemize}
	\item Objektkoordinaten \(\rightarrow\) Kamerakoordinaten: \(gl\_ModelViewMatrix\)
	\item Objektkoordinaten \(\rightarrow\) Clip Koordinaten: \(gl\_ModelViewProjectionMatrix\)
\end{itemize}

\subsubsection{Build-In Funktionen}
\begin{itemize}
	\item \(degrees\), \(radians\)
	\item \(\lbrack a \rbrack sin \lbrack h \rbrack\), \(\lbrack a \rbrack cos \lbrack h \rbrack\), \(\lbrack a \rbrack tan \lbrack h \rbrack\)
	\item \(abs\), \(sign\), \(floor\)
	\item \(length\), \(distance\), \(dot\), \(normalize\), \(reflect\)
\end{itemize}


\subsection{Beispiele}

\subsubsection{Minimalbeispiel}
\begin{minipage}{\textwidth}
Vertex-Shader
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=GLSL]
uniform mat4 matrixMVP;
in vec4 in_position;

void main() {
	gl_Position = matrixMVP * in_position;
}
\end{lstlisting}
\end{minipage}
\\\\
\begin{minipage}{\textwidth}
Fragment-Shader
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=GLSL]
out vec4 out_color;

void main() {
	out_color = vec4(1.0, 1.0, 1.0, 0.0);
}
\end{lstlisting}
\end{minipage}

\subsubsection{Texturierung im Fragment Shader}
\begin{minipage}{\textwidth}
Fragment-Shader
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=GLSL]
uniform sampler2D tex;
in vec2 texCoord;

void main() {
	vec3 ogl = texture(tex, texCoord).rgb;
	out_frag_color = vec4(kd * ogl.rgb, 1.0);
}
\end{lstlisting}
\end{minipage}

\subsubsection{Diffuse Beleuchtung}
\begin{minipage}{\textwidth}
Vertex-Shader
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=GLSL]
uniform mat4 matrixMVP, matrixMV, matrixNrml;
uniform vec3 lightSourcePos;
in  vec4 in_position;
in  vec3 in_normal;
out vec4 color;

void main() {
	gl_Position = matrixMVP * in_position;

	// Beleuchtungsberechnung in Kamerakoordinaten
	vec3 P = vec3(matrixMV * in_position);
	vec3 N = normalize(vec3(matrixNrml * vec4(in_normal, 0.0)));
	vec3 L = normalize(lightSourcePos - P);
	color  = vec4(max(0.0, dot(L, N)));
}
\end{lstlisting}
\end{minipage}
\\\\
\begin{minipage}{\textwidth}
Fragment-Shader
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=GLSL]
in  vec4 color;
out vec4 out_color;

void main() {
	out_color = color;
}
\end{lstlisting}
\end{minipage}

\subsubsection{Per-Pixel Beleuchtung}
\begin{minipage}{\textwidth}
Vertex-Shader
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=GLSL]
uniform mat4 matrixMVP, matrixMV, matrixNrml;
uniform vec3 lightSourcePos;
in  vec4 in_position;
in  vec3 in_normal;
out vec3 L, N;

void main() {
	gl_Position = matrixMVP * in_position;

	// Beleuchtungsberechnung in Kamerakoordinaten
	vec3 P = vec3(matrixMV * in_position);
	     N = vec3(matrixNrml * vec4(in_position));
	     L = lightSourcePos - P;
}
\end{lstlisting}
\end{minipage}
\\\\
\begin{minipage}{\textwidth}
Fragment-Shader
\begin{lstlisting}[frame=single,numbers=left,mathescape,language=GLSL]
in  vec3 L, N;
out vec4 out_color;

void main() {
	float kd = max(0.0, dot(normalize(L) * normalize(N)));
	out_color = vec4(kd);
}
\end{lstlisting}
\end{minipage}

\subsubsection{Phong Shading}
Alle Richtungsvektoren müssen normiert werden.
\begin{itemize}
	\item \textbf{Vertex Shader}
	\begin{itemize}
		\item Position in Clip-Koordinaten und Weltkoordinaten
		\item Normale in Weltkoordinaten
		\item Weitergeben der Texturkoordinate
	\end{itemize}
	\item \textbf{Fragment Shader}
	\begin{itemize}
		\item Berechnung von \(k_d\) (der Farbe) aus der Textur
		\item Berechnung der Beleuchtung für alle Lichtquellen und Summieren der Ergebnisse
		\item Formel: \(\Big( k_d max(0,L\cdot N) + k_s max(0,R\cdot L)^n \Big) \frac{I_l}{\|x-x_l\|^2}\)
	\end{itemize}
\end{itemize}