EGAD

Prof. Dr. sc. techn. Beat Brüderlin

Computergrafik I (Grundlagen)

2 SWS Vorlesung; 1SWS Übung

Für die Verarbeitung geometrischer Daten in 2D und 3D gibt es eine Vielzahl an Problemstellungen, z.B. die Berechnung konvexer Hüllen, Delaunay Triangulierung, Schnitte von Liniensegmenten und Dreiecken, Voronoi-Diagramme und räumliche Indexstrukturen. In dieser Veranstaltung wird das Wissen vermittelt, wie Aufgabenstellungen mit geometrischen Algorithmen und Datenstrukturen effizient, d.h. mit niedriger asymptotischer Laufzeitkomplexität, zu lösen und deren Laufzeit für den average case, best case und worst case zu bestimmen sind.

Mittels bekannter Ansätze, z. B. iterativer Ansätze, Divide und Conquer, Plane Sweep-Algorithmen, probabilistische sowie problemspezifische und output-sensitive Ansätze werden verschiedene Verfahren vorgestellt, die für die selbe Aufgabe, je nach Daten- und Hardware-Voraussetzungen, am geeignetsten sind. Dabei wird der Unterschied zwischen algorithmischer Komplexität und Problemkomplexität und der Einfluss der Hardwarearchitektur und deren Eigenschaften (SIMD, Pipeline, Zugriffe auf RAM, externer Langzeitspeicher mit Latenzen) vermittelt.

Ziel des Seminars ist eine anschauliche Vermittlung ausgewählter Sachverhalte der Vorlesung und verwandter Themen. Diese werden praktisch, beispielsweise durch direkt im Seminar durchgeführte Implementierungen oder Lösung textueller Aufgaben, untersucht. Die Verwendung bestimmter Tools und Programmiersprachen ist dabei nicht vorgeschrieben, stattdessen wird vielmehr die Eigeninitiative der Teilnehmer aktiv ermutigt. Ein sicherer Umgang mit den jeweils gewählten Tools und Programmiersprachen wird jedoch empfohlen.