Algorithmen in der Computergraphik

Inhaltsverzeichnis

1 Einleitung.- 1.1 Vektorgraphiksysteme.- 1.2 Rastergraphiksysteme.- 1.3 Überblick.- 2 Grundlegende Rastergraphikalgorithmen.- 2.1 Daxstellung von Linien.- 2.1.1 Inkrementeller Algorithmus.- 2.1.2 Bresenham-Algorithmus.- 2.2 Daxstellung von Kurven zweiter Ordnung.- 2.2.1 Parametermethode.- 2.2.2 Scangerade-Methode.- 2.2.3 Differentielle Methode.- 2.3 Füllen von Polygonen und geschlossenen Kurven.- 2.3.1 Scangeraden-Methode.- 2.3.2 Saatfüllen.- 2.4 Clippen von Polygonen.- 2.4.1 Der Algorithmus von Cohen und Sutherland.- 2.4.2 Clippen bzgl. allgemeinen Polygonen.- 2.5 Halbtonverfahren.- 2.5.1 Halbton-Simulation.- 2.5.2 Dither-Verfahren.- 2.5.3 Fehlerverteilungs-Verfahren.- 2.5.4 Fehlerdiffusions-Verfahren.- 2.6 Verwendung einer Farbtabelle.- 2.6.1 Auswahl der Farbschattierungen.- 2.6.2 Besetzung der Farbtabelle.- 2.6.2.1 Uniforme Quantisierung.- 2.6.2.2 Popularitätsalgorithmus.- 2.6.2.3 Median-Schnitt-Algorithmus.- 2.6.2.4 Octree-Quantisierung.- 2.7 Behebung von Aliasing-Effekten.- 2.7.1 Aliasing-Effekte und Fourier-Analyse.- 2.7.2 Anti-Aliasing-Techniken.- 2.7.2.1 Nachfiltern mit Supersampling.- 2.7.2.2 Nachfiltern ohne Supersampling.- 2.7.3 Anti-Aliasing mit modifiziertem Grundalgorithmus.- 3 Dreidimensionale Computergraphik.- 3.1 Mathematische Grundbegriffe.- 3.2 Homogene Koordinaten.- 3.3 Rotation um eine beliebige Achse.- 3.4 Projektionen.- 3.4.1 Perspektivische Projektion.- 3.4.2 Paxallelprojektion.- 3.5 Spezifikation einer beliebigen Projektion.- 3.6 Berechnung einer beliebigen Projektion.- 3.6.1 Normalisierungs-Transformation für parallele Projektion.- 3.6.2 Normalisierungs-Transformation für perspektivische Projektion.- 3.7 Clippen bzgl. der kanonischen Sichtvolumen.- 4 Bestimmung sichtbarer Oberflächen.- 4.1 Sichtbare Oberflächen für konvexe Objekte.- 4.2 Sichtbare Kanten für eine allgemeine Szene.- 4.3 z-Puffer-Algorithmus.- 4.4 Scangeraden-Algorithmen.- 4.5 Sortierung nach dem Abstand vom Betrachter.- 4.6 Flächenunterteilungs-Algorithmus.- 4.7 Vergleich der Verfahren.- 5 Reflexions- und Beleuchtungsmodelle.- 5.1 Physikalische Grundlagen.- 5.2 Strahlungslehre.- 5.3 Das Phong-Reflexionsmodell.- 5.3.1 Diffuse Reflexion.- 5.3.2 Licht aus der Umgebung.- 5.3.3 Spiegelnde Reflexion.- 5.3.4 Vereinfachungen des Phong-Modells.- 5.3.5 Berücksichtigung von Farbe.- 5.3.6 Ungleichmäßige Abstrahlung der Lichtquelle.- 5.4 Das Reflexionsmodell von Cook und Torrance.- 6 Schattierungsverfahren.- 6.1 Gouraud-Schattierung.- 6.2 Phong-Schattierung.- 6.3 Beschleunigung der Phong-Interpolation.- 7 Gekrümmte Oberflächen.- 7.1 Bézier-Kurven.- 7.1.1 Der Casteljau-Algorithmus.- 7.1.2 Formulierung mit Bernstein-Polynomen.- 7.1.3 Zusammengesetzte Bézier-Kurven.- 7.2 B-Spline-Kurven.- 7.2.1 Der De-Boor-Algorithmus.- 7.2.2 B-Spline-Funktionen.- 7.2.3 B-Spline-Kurven.- 7.3 Polynomielle Interpolation.- 7.4 B-Spline-Interpolation.- 7.5 Wahl der Parametrisierung.- 7.6 Bezier-Oberflächen.- 7.7 B-Spline-Oberflächen.- 7.8 Interpolation mit B-Spline-Oberflächen.- 7.9 Zeichnen von Oberflächen.- 8 Ray-Tracing-Verfahren.- 8.1 Ray-Tracing-Grundalgorithmus.- 8.2 Reflexion und Transmission.- 8.2.1 Berechnung des reflektierten Strahls.- 8.2.2 Berechnung des gebrochenen Strahles.- 8.3 Berechnung der (lokalen) Intensitätswerte.- 8.4 Umgebende Volumen.- 8.4.1 Kugeln als umgebendes Volumen.- 8.4.1.1 Algebraische Lösung.- 8.4.1.2 Geometrische Lösung.- 8.4.2 Boxen als umgebende Volumen.- 8.4.3 Vergleich von Kugeln und Boxen als umgebende Volumen.- 8.4.4 Hierarchische umgebende Volumen.- 8.5 Adaptive Tiefenkontrolle.- 8.6 Unterteilung des Raumes.- 8.6.1 Nicht-uniforme Raumunterteilung.- 8.6.2 Uniforme Raumaufteilung.- 8.6.3 Mögliche Ineffizienzen und Fehler.- 8.6.4 Ein Vergleich durch Graphdarstellung.- 8.7 Unterteilung der Strahlrichtungen.- 8.8 Ray-Tracing-Verfahren und Objektmodellierung.- 8.9 Zusammenfassung und Ausblick.- 9 Radiosity-Verfahren.- 9.1 Grundlegende Theorie und Basis-Algorithmus.- 9.2 Nachträgliche Verfeinerung der Unterteilu