Virtuelle 3-D Modelle von Maschinen, Gebäuden oder Werkstücken werden oft durch ihre Oberflächen in Form von Dreiecken modelliert. Je detaillierter diese Modelle sind, desto höher ist die Anzahl der benötigten Dreiecke. In einigen Anwendungen ist die Anzahl Dreiecke so hoch, dass ein einzelner Computer ein Bild der virtuellen Szene nicht mehr in Echtzeit berechnen kann. In anderen Anwendungen ist die virtuelle Szene so groß, dass sie nicht mehr im Hauptspeicher eines Rechners gespeichert werden kann. In diesem Jahr haben wir zwei Algorithmen entwickelt, um die Bildberechnungen komplexer Szenen zu beschleunigen:
Sequentielles Occlusion-Culling mit dem Hull Tree
Occlusion-Culling ist ein methodischer Ansatz, der verdeckte Objekte bestimmt und diese von den Berechnungen des Bildes ausschließt. Um die Verdeckungsberechnungen zu beschleunigen, werden Quader, die die Objekte einschließen, auf Sichtbarkeit getestet. Die Quader sind häufig zu groß und liefern deswegen ungenaue Testergebnisse. Daher haben wir eine räumliche, hierarchische Datenstruktur - den Hull Tree - entwickelt, der anstelle von Quadern sogenannte Hüllen verwendet. Diese Hüllen schließen die Objekte der Szene enger ein und liefern so exaktere Sichtbarkeitstests.
Die Datenstruktur wurde zuerst in einem sequentiellen Echtzeit-Rendering-System verwendet. Die Evaluierung zeigte, dass der Hull Tree im Vergleich zu bisherigen Verfahren nur wenig zusätzlichen Speicher benötigt. Auch die etwas aufwendigeren Hüllenberechnungen ließen sich mit nur wenigen zusätzlichen Berechnungsschritten durchführen. Der zusätzliche Speicher- und Zeitaufwand wurde durch die genaueren Sichtbarkeitstests nicht nur ausgeglichen, sondern führte insgesamt zu einer lohnenswerten Rechenzeitersparnis.
Paralleles Occlusion-Culling in heterogenen Clustern
Parallele Rendering-Verfahren beschleunigen die Bildberechnung, indem die Berechnung parallel durch mehrere Computer durchgeführt wird. Derartige parallele Rechensysteme bestehen idealerweise aus gleichstarken Rechenknoten. Aufgrund der fortschreitenden Hardwareentwicklung entstehen jedoch in letzter Zeit heterogene Systeme mit unterschiedlich leistungsstarken Rechenknoten. Unser Algorithmus arbeitet mit solchen heterogenen Clustersystemen. Die Herausforderung liegt in dem Umgang mit stark unterschiedlichen Antwortzeiten der Clusterknoten.
Komplexes 3D-Modell einer Boeing 777, dargestellt durch das parallele Occlusion-Culling-Verfahren mit einem heterogenen PC-Cluster
Die Clusterknoten haben zweierlei Aufgaben: In unserem parallelen Renderingsystem wird die Szene im Cluster verteilt gespeichert. Der Cluster fungiert damit als eine Art externer Speicher für einen Client, der die virtuelle Szene darstellt. Der Hull Tree ist auch Ausgangspunkt für das parallele Occlusion-Culling-Verfahren. Um den Hull Tree speichereffizient in einem parallelen Renderingsystem einzusetzen, arbeiten wir mit vereinfachten Objekten. Jeder Clusterknoten speichert im Hull Tree einen kleinen Teil der nicht vereinfachten originalen Objekte und für alle anderen Objekte vereinfachte Ersatzrepräsentation.
Als zweite Aufgabe unterstützen die Clusterknoten den Client, der die Szene anzeigt, bei der Berechnung des Bildes. Wenn Objekte von einem Knoten angefordert werden, prüft der Knoten, ob die angeforderten Objekte verdeckt sind und verschickt dann nur die sichtbaren Objekte.
Die Evaluierung hat gezeigt, dass durch den Einsatz dieser Technik auch PC-Cluster zur Bilderzeugung von komplexen Szenen verwendet werden können, die nur über ein relativ langsames Netzwerk verbunden sind und bei denen Clusterknoten eine schwache Rendering-Leistung aufweisen.
Genauere Objektapproximatonen durch den Hull Trees (blau) im Vergleich zu einem Standard-Octree (rot).
Gefördert durch:
Kontakt:
Dipl.-Inform. Tim Süß
E-Mail: tsuess@uni-paderborn.de
Telefon: +49 (0) 5251/60 64 28
Dr. rer. nat. Matthias Fischer
E-Mail: mafi@uni-paderborn.de
Telefon: +49 (0) 5251/60 64 66
