Projekt | Universität Paderborn

Überblick

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.

Ziele und Vorgehen

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.