Geometrische Datenstrukturen für die Computergraphik - SS 09

Geometric Data Structures for Computer Graphics


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:

  1. Quadtrees / Octrees, Texturkompression, Isosurfaces, Terrain-Visualisierung,
  2. kd-trees, BSP-Trees, Boolesche Operationen, Textursynthese,
  3. Bounding-Volumen-Hierarchien,
  4. Kinetische Datenstrukturen, Collision Detection,
  5. Konvexe Hülle,
  6. Voronoi- und Delaunay-Diagramme,
  7. etc.
Achtung: diese Liste ist nur vorläufig und kann sich im Laufe des Semesters ändern.

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.

Aktuelles


Folien

Die folgende Tabelle enthält die behandelten Themen und die dazugehörigen Übungsblätter.

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

Hier finden Sie die Folien, die während der Vorlesung zu Illustrationszwecken gezeigt wurden.

Literatur

Falls Sie sich diese Bücher anschaffen möchten, sollten Sie vielleicht überlegen, gebrauchte Exemplare zu erwerben -- oft gibt es diese zu einem Bruchteil des Neupreises. Zwei gute Internetadressen sind Abebooks und BookButler.

Scheinerwerb

Einen Schein erwirbt man durch erfolgreiche Teilnahme an den Übungen, d.h., Sie sollten wenigstens ca. 50 % der Punkte schaffen. Die Übungsblätter werden ausschließlich theoretisch sein (Bleistift und Papier).

Prüfung

Die Vorlesung wird mündlich geprüft. Wer sich prüfen lassen möchte, melde sich bitte wie üblich im Prüfungsamt und bei Frau Cronjäger (IfI, Zimmer 202) an.

Change Monitoring:

 by ChangeDetection (it's free and it's private).
 by ChangeDetect (it's free and private, too).
If you enter your email adress in one of the boxes above and then press one of the "Monitor" buttons, then either ChangeDetection or ChangeDetect will send you an email whenever I make changes to this page.
Gabriel Zachmann
Last modified: Fri Dec 18 10:59:15 MET 2009