Technische Universität Ilmenau

Effiziente geometrische Algorithmen und Datenstrukturen - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Effiziente geometrische Algorithmen und Datenstrukturen im Studiengang Master Informatik 2013
Fachnummer101672
Prüfungsnummer2200600
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2252 (Graphische Datenverarbeitung)
Fachverantwortliche(r)Prof. Dr. Beat Brüderlin
TurnusSommersemester
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)34
Selbststudium (h)116
VerpflichtungWahlpflicht
Abschlussschriftliche Prüfungsleistung, 120 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Vorkenntnisse

Computergrafik I (Grundlagen)

Lernergebnisse

Die Studenten erlangen einen Überblick über verschiedene Ansätze zur Verarbeitung von Geometrie/Topologiedaten sowie Kenntnisse und Fähigkeiten für die Implementierung effizienter Algorithmen und Datenstrukturen zur Erfassung und Verarbeitung von 2D- und 3D-Daten.

 

Inhalt

Algorithmen: Einführung, algorithm. Komplexität, effiziente Verarbeitung von 3d-Punktedaten, räumliche (mehrdimensionale) Suchstrukturen: Grid, Voxel, Octree, K-d-Bäume, Grid-file, hierachische AABB, OBB, k-DOP, R*
Punktsuche, Bereichsuche, körperhafte Objekte als hochdimensionale Punkte, Hüllkörperhierarchie mit Überlappung, Nachbarschaftssuche, Anwendungsbsp. Ray Tracing, Kollisionserkennung (Physiksimulation, Boolean)
Effiziente geometrische Datenstrukturen & Algorithmen: Konvexe Hüllen. Definition und Konstruktion. Methode mit Stützgeraden. Erweiterung auf höhere Dimensionen.
Konvexe Hüllen. Fächermethode nach Graham + Divide & Conquer
Schneiden von Liniensegmenten mit dem Plane Sweep Verfahren.
Voronoi-Zellen, Delaunay Triangulierung, Skelette.
Output-Sensitivität, Temporale Kohärenz, Stochastische Algorithmen.

Medienformen

Folien (PDF), Beispiele in verschiedensten Formaten (HTML/JavaScript etc.)

Literatur

Beat Brüderlin, Andreas Meier:
Computergrafik und Geometrisches Modellieren.
Teubner, Wiesbaden, Germany, 2001.

Christoph M. Hoffmann:
Geometric and Solid Modeling. An Introduction.
Morgan Kaufmann, San Mateo, CA, USA, 1989.

Rolf Klein:
Algorithmische Geometrie.
Addison-Wesley, Bonn, Germany, 1997.

Martti Mäntylä:
An Introduction to Solid Modeling.
Computer Science Press, College Park, MD, USA, 1988.

David F. Rogers, J. Alan Adams:
Mathematical Elements for Computer Graphics.
2nd edition, WCB/McGraw-Hill, New York, NY, USA, 1990.

Dieter Roller:
CAD. Effiziente Anpassungs- und Variantenkonstruktion.
Springer, Berlin, Germany, 1995.

Lehrevaluation

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.