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.