Startseite > Fachgruppen > Algorithmen und Komplexität > Projekte > Algorithm Engineering für Probleme der Computergrafik

Algorithm Engineering für Probleme der Computergrafik

Das Projekt beschäftigt sich mit Algorithm Engineering Problemen aus der Computergrafik. Behandelt werden Fragestellungen zur Modellierung von Grafikhardware und virtuellen 3D-Szenen sowie die Entwicklung, Analyse, Implementierung und experimentelle Evaluierung von Renderingalgorithmen.

Projektbeschreibung

Gerade in der Computergrafik stellt der Anspruch des Algorithm Engineering - Entwicklung geeigneter Modelle für Hardware und realistische Eingaben, um die theoretische Algorithmenentwicklung und -analyse enger mit der Implementierung und experimentellen Evaluierung zu verknüpfen - eine besondere Herausforderung dar:

  • Da Computergrafik-Algorithmen sehr stark von der Grafikkarte unterstützt werden, ist es notwendig, ihre Eigenschaften in die Hardwaremodellierung einzubeziehen.
  • Je nach Anwendungsgebiet weisen “typische” 3D-Szenen sehr unterschiedliche Charakteristika auf, z.B. Dichte, Überdeckungs- und Füllgrad.
  • Als Folge sind Laufzeitanalysen alleine in Termen der Szenengröße nicht aussagekräftig; vielmehr muss Laufzeit als Term in mehreren geeigneten Parametern, die die Hardware und Szenencharakteristika beschreiben, ausgedrückt werden.

Ziel

Ziel des Projekts ist die Entwicklung, Analyse, Implementierung und experimentelle Evaluierung von Renderingalgorithmen zur Visualisierung von 3D-Szenen. Dabei wollen wir im oben beschriebenen Sinn theoretische und experimentelle Entwicklung und Analyse verbinden und zielen auf so detaillierte Analysemethoden ab, dass die gewonnenen Laufzeitvorhersagen verläßliche Effizienzvergleiche zwischen verschiedenen Algorithmen erlauben. Wir werden uns insbesondere mit Verfahren zum Occlusion-Culling (Berechnung von verdeckten Szenenteilen) befassen. Die Wirksamkeit solcher Verfahren hängt in besonderem Maße von Charakteristika der Hardware und der Szene ab, sie sind also für unsere Untersuchungen besonders geeignet. Ein Fernziel sehen wir in der Entwicklung von Algorithmen, die adaptiv in dem Sinne sind, dass sie sich selbstständig an die Charakteristika der zur Verfügung stehenden Hardware und der Eingabeszenen anpassen.

Personen

  • Claudius Jähn
  • Friedhelm Meyer auf der Heide (Projektleiter)
  • Martin Ziegler
  • Matthias Fischer (Projektleiter)
  • Ralf Petring