Algorithm Engineering für Probleme der Computergrafik

• Applicant: Professor Dr. Friedhelm Meyer auf der Heide
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 47756144

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 Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering
• Participating Person: Dr. Matthias Fischer