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 geometrische 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. Als solche 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 | Literatur |
|---|---|---|---|
| 1. | Grundbegriffe, Quadtrees, balancierte Quadtrees, Meshing | Blatt 1 | BCKO |
| 2. | Quadtree-Varianten, Implementierung von Quadtrees, Location-Codes | ||
| 3. |
Rekonstruktion aus Bildfolgen, Image Compression (Quadtree-Prädiktor, BTC, CCC, XCCC, S3TC) Isosurfaces, Adaptive Isosurfaces |
Blatt 2 | |
| 4. | Isosurfaces über zeitlich veränderliche Felder, zeitlicher Index-Baum, nicht-rekursive 1-dim. Stabbing Queries | ||
| 5. | Kd-Trees, Aufbau, Eigenschaften, Varianten, Nearest-Neighbor-Search, Curse of Dimensionality, approximate nearest neighbor search, Textursynthese | Blatt 3 | |
| 6. | Beweis zur Laufzeit der ANN-Suche in longest-side kd-Trees; Himmelfahrt | ||
| 7. |
Stackless kd-Tree Traversal. Konvexe Hülle, Eigenschaften, einfache Anwendungen, geometrische Prädikate, extremale Punkte auf konvexen Polygonen, Graham's Scan, geometrische Robustheit |
Blatt 4 | BCKO, PS, OR |
| 8. | Pfingstferien | ||
| 9. | Optimal output-sensitive convex hull algorithm in 2D, Konvexe Hülle in 3D (Komplexität, Clarkson-Shor), Anwendung auf Kollisionsdetektion | K, BCKO | |
| 10. | Voronoi-Diagramme und Delaunay-Triangulierung: Definition, Charakterisierung der Punkte, Kanten, und Knoten, Komplexität, globale Eigenschaften, Dualität, Max-Min-Winkel-Eigenschaft, Verallgemeinerungen (z.B. Power-Diagramm, Medial-Axis, etc.) | BCKO, K, PS, OR | |
| 11. | Vertretung: Konstruktion von kd-Trees auf massiv-parallelen Architekturen (Folien) | ||
| 12. | Anwendungen der Voronoi- und Delaunay-Graphen: post office problem, nearest neighbor graph, minimum spanning tree, 2-Approximation der optimalen Traveling-Salesman-Tour, largest empty circle, kompakte Wahlbezirke, Sampling, Protein-Struktur | K |