Algorithmen in der Computergrafik

Neue Grafikkartengenerationen erlauben die Echtzeitdarstellung von immer komplexeren 3D-Szenen. Hoch detaillierte Szenen von 3D-CAD Modellen, lassen sich jedoch auch auf den modernsten Grafikkarten nicht ohne weiteres darstellen. Dazu wurden in der Computergrafik Renderingalgorithmen entwickelt, die spezielle Eigenschaften von Szene und Hardware ausnutzen, um die darzustellende Datenmenge zu reduzieren ohne die Bildqualität zu mindern.

Multi-Algorithm-Rendering

Eine virtuelle 3-D-Szene kann aus Daten unterschiedlicher Quellen bestehen; etwa aus CAD-Daten (z.B. von komplexen Maschinen), Daten aus Laserscans (von Fabrikhallen, Kunstobjekten etc.), Daten aus Architekturprogrammen (z.B. geplante Fabrikhallen) oder auch Daten aus 3-D-Modellierungsprogrammen. Insbesondere wenn in einer virtuellen Szene Daten aus heterogenen Quellen kombiniert werden, ergeben sich sehr inhomogen strukturierte Daten. Für die Echtzeitdarstellung solcher Szenen stellt sich das Problem, dass ein einzelner Renderingalgorithmus häufig nur in der Lage ist, einen bestimmten Szenentyp schnell in guter Qualität darzustellen. Wenn er bei einer ungünstigen Szene eingesetzt wird, kann entweder die Bildqualität oder die Laufzeit beliebig schlecht werden. Für eine heterogene Szene kann es sich dabei als schwierig erweisen, einen einzelnen Algorithmus auszuwählen, der generell für die Darstellung geeignet ist. Deshalb haben wir eine Methode entwickelt, welche die einzelnen Bereiche der Szene in einem Bild mit unterschiedlichen Renderingalgorithmen gleichzeitig dargestellt. In der Vorbereitung wird dazu zunächst die komplette Szene automatisch in Bereiche mit homogenen Charakteristiken unterteilt. In einem zweiten Schritt wird gemessen, wie gut die einzelnen Algorithmen für die Bereiche funktionieren. Kriterien hierfür sind sowohl die Laufzeit als auch die Qualität des resultierenden Bildes. Da diese Werte stark von der Position des Betrachters in der Szene abhängen, werden sie anhand eines adaptiven Samplingprozesses für zahlreiche Positionen in der Szene ermittelt und in einer Datenstruktur gespeichert. Zur Laufzeit, wenn sich der Betrachter durch die Szene bewegt, kann anhand der gespeicherten Werte für die aktuelle Position ein Optimierungsproblem definiert werden, welches bei einer vorgegebenen maximalen Dauer zur Bildberechnung die Qualität des resultierenden Bildes maximiert. Das Verfahren erlaubt es, Szenen automatisch aufzubereiten und zu rendern, die aus hunderten von Millionen Dreiecken bestehen und aus zahlreichen unterschiedlichen Teilen aufgebaut sind.

PADrend

Für die Entwicklung dieser und anderer Renderingalgorithmen wird von uns eine Softwareplattform entwickelt und eingesetzt, die speziell auf die besonderen Anforderungen in diesem Bereich zugeschnitten ist: "PADrend: Platform for Algorithm Development and Rendering". Basierend auf einem modularen und plattformunabhängigen Plug-in-System lassen sich Algorithmen und Datenstrukturen sehr variabel anpassen und kombinieren. Insbesondere bei der Neuentwicklung von Algorithmen bietet die Möglichkeit, den ausgeführten Programmcode zur Laufzeit auszutauschen, große Vorteile; genauso wie die unterschiedlichen Möglichkeiten systematisch verschiedene Kenngrößen (Laufzeit des Algorithmus, Bildqualität etc.) zu ermitteln. Für die Evaluierung neuer Algorithmen bietet PADrend eine breite Palette an bereits existierenden Implementierungen für viele Algorithmen und Datenstrukturen aus der Literatur als Referenz, was einen fairen Vergleich von Algorithmen erlaubt.

zurück zur Übersicht