SPP 1307 - Algorithm Engineering für Probleme der Computergrafik (Teilprojekt)

Wir besch?ftigen uns in diesem Projekt mit der Entwicklung, Analyse, Implementierung und experimentellen Evaluierung von Renderingalgorithmen zur Visualisierung von 3D-Szenen. Solche Computergrafik-Algorithmen h?ngen sehr stark von den F?higkeiten der Grafikkarte und Charakteristika der 3D-Szene ab. Wir zielen auf Methoden zur Analyse von Hardware und Szenen-Charakteristika ab, die die dynamische Auswahl guter Algorithmenvarianten w?hrend eines Walkthrough durch die Szene unterstützen. Schwerpunkt unserer Forschung in ist die Entwicklung von positionsbasierten Datenstrukturen, die es erlauben, zu gegebener Besucherposition und -sichtrichtung einen in dieser Situation effizienten Renderingalgorithmus auszuw?hlen. Zum Beispiel soll entschieden werden, ob es sich lohnt Occlusion-Culling (Identifikation von verdeckten Teilen der Szene) durchzuführen. Tendenziell lohnt sich Occlusion Culling, wenn ein sehr gro?er Teil der Szene zur Grafikkarte geschickt werden muss. Was ?sehr gro?er Teil" bedeutet, h?ngt in besonderem Ma?e von Charakteristika der Hardware und der Szene ab. Dieses Culling Problem ist also für unsere Untersuchungen besonders geeignet. In der ersten F?rderphase haben wir zwei erste solche Strukturen entwickelt, eine experimentell, die andere theoretisch analysiert. In der zweiten Phase m?chten wir diese samplingbasierten Verfahren und ihre Analysen in verschiedenen Richtungen erweitern. Wesentliche Herausforderungen sind hier z.B. - die Anpassung an das Verhalten der Besucher der Szenen bis hin zu online-Adaptierungen der Datenstruktur an die Bewegungsmuster der Besucher. - die Nutzung von Zellstrukturen sehr gro?er Szenen. Diese zus?tzlichen positionsabh?ngigen Informationen wollen wir nutzen, um sehr gro?e Szenen in Echtzeit zu rendern. Die positionsabh?ngigen Datenstrukturen liefert jedoch nur Teilinformation zur Beantwortung der Frage, ob Culling sinnvoll ist. Eine weitere notwendige Information betrifft Eigenschaften der zugrunde liegenden Hardware. Hier werden wir unsere Arbeiten zur Modellierung und Messung von wichtigen Hardware-Eigenschaften fortsetzen, und Messmethoden in einer Open- Source Bibliothek verfügbar machen.

DFG-Verfahren Schwerpunktprogramme

Teilprojekt zu SPP 1307: Algorithm Engineering

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.

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.