Wo sollte man ein neues Haus plazieren, damit es möglichst weit von Störquellen entfernt ist?
Wie sollte man Punkte in einem Höhenfeld verbinden, damit ein möglichst "plausibles" 3D Terrainmodell entsteht?
Wie kann man Bilder möglichst einfach aber dennoch platzsparend speichern oder übertragen? (JPEG ist zwar
platzsparend, aber nicht besonders einfach)
Bei vielen Algorithmen, insbesondere auch in der Computer-Graphik, liegt das Geheimnis ihrer Effizienz in den jeweils verwendeten geometrischen Datenstrukturen. In dieser Vorlesung sollen verschiedene solche Datenstrukturen besprochen werden, die sich in der Praxis als sehr erfolgreich erwiesen haben. Bevorzugt werden diejenigen Datenstrukturen und Algorithmen angesprochen, die sowohl universell einsetzbar als auch relativ einfach zu implementieren sind.
Zu allen Datenstrukturen werden einige Algorithmen, vorzugsweise, aber nicht ausschließlich aus der Computer-Graphik, vorgestellt, die deren Verwendung demonstrieren.
Geplante Themen:
Die Vorlesung bewegt sich an der Schnittstelle zwischen Computational Geometry und Computer-Graphik. Daher werden keine praktischen sondern nur (einfache) theoretische Übungsaufgaben gestellt werden.
Ein Skript wird am Ende der Vorlesung ausgeteilt; allerdings werden in der Vorlesung wahrscheinlich einige aktuelle Themen behandelt, die noch nicht in das Skript eingearbeitet sind.
| Woche | Thema | Übungsblatt |
|---|---|---|
| 1. | Grundbegriffe, Quadtrees, Navigation in Quadtrees, balancierte Quadtrees | |
| 2. | Meshing mit Quadtrees für Integer-Polygonzüge, Meshing für beliebige Polygonzüge, Quadtree-Varianten, Octrees, Octree-Rekonstruktion eines Objektes aus Bildfolgen | |
| 3. | Bildkompression mittels Quadtrees, Übung | |
| 4. | S3TC-Kompression; Isosurfaces (Definition, Marching Cubes, Octree-Methode, adaptive I.) | |
| 5. |
kd-Trees (Definition, Konstruktion, Laufzeit der Konstruktion, Varianten);
Nearest-Neighbor-Suche mit kd-Trees; Curse of Dimensionality |
|
| 6. |
Approximate Nearest Neighbor Search (Algorithmus, Korrektheit, Laufzeit);
Beweis zur Anzahl der besuchten Knoten im ANN-Algorithmus; Anwendung: Textur-Synthese |
|
| 7. |
Textur-Synthese mit Bild-Pyramide. BSP-Trees (Definition, Beispiele, Konstruktion) |
|
| 8. |
BSP-Trees (Komplexität, BSPs von konvexen Polyedern);
Anwendungen von BSPs (Ray-Shooting, Point Location in geschlossenen Polyedern); Bounding-Volume-Hierarchies (Definition, Tightness) |
|
| 9. |
Bounding-Volume-Hierarchies (Aufbau mittels Insertion-Strategie,
Surface-Area-Heuristic, top-down Aufbau, k-DOPs für Ray-Tracing,
Kollisionsdetektion mittels BVHs); Range Searching (1D-Fall, der Range Tree im d-dim. Fall) Priority Search Tree); Range X-Fast-Tree, XFT-PST |
|
| 10. |
Range Searching auf dem Gitter (X-Fast-Tree im 1D, XFT-PST im 2D); Konvexe Hülle (Anwendungen, Definitionen) |
|
| 11. |
Konvexe Hülle (Eigenschaften, Konstruktion in 2D); Voronoi-Diagramme (Definition, Eigenschaften, Anwendungen) |