Diplomarbeit: Paralleles Hierarchisches Radiosity auf der CM-5
zur englischen Version English version

Robert Garmann:
Paralleles Hierarchisches Radiosity auf der CM-5,
Diplomarbeit, November 1994

Text: pdf, gzipped postscript

Zusammenfassung als pdf

Zusammenfassung

Die Diplomarbeit behandelt die Entwicklung eines parallelen Algorithmus zur realitätsnahen Bildsynthese.

Realitätsnahe Bildsynthese

Gegenstand der realitätsnahen Bildsynthese ist die Berechnung realistisch wirkender Rasterbilder aus einer dreidimensionalen Szenenbeschreibung nach Modellen, die aus der Optik abgeleitet sind. Die Methoden der realitätsnahen Bildsynthese werden in der Beleuchtungsplanung eingesetzt und finden z. B. in der Architektur- oder in der Werbebranche Anwendung.

Ein Ziel aktueller Anstrengungen ist das Lösen der allgemeinen Bildsynthesegleichung von Kajiya [2]. Das Radiosity-Verfahren ist ein bekannter Ansatz zur Simulation diffuser Reflexion. In jüngerer Zeit wurde mit dem hierarchischen Radiosity-Verfahren (HRV) von Hanrahan u. a. [1] ein Durchbruch in mehrfacher Hinsicht erzielt. Einerseits ist die Komplexität des Verfahrens dramatisch gesunken. Andererseits gewährleistet der Algorithmus durch frei einstellbare Präzisionsparameter technische Anwendbarkeit. Zudem zeichnet sich ab, daß das HRV auch auf spiegelnde Reflexion und Brechung übertragbar ist. Dadurch ist eine gute Approximation der allgemeinen Bildsynthesegleichung gegeben.

Trotz dieser Fortschritte lassen die Laufzeiten bei der Verarbeitung komplexerer Szenen auf heutigen konventionellen Rechnern zu wünschen übrig. Die Parallelisierung des HRV ist ein Ausweg.

Hierarchisches Radiosity

Beim HRV ist eine dreidimensionale Szene durch eine Menge von Polygonen gegeben. Die optischen Eigenschaften der Polygone sind durch Reflexionskoeffizienten und Emissionsdichten beschrieben. Der Algorithmus simuliert den Lichttransport zwischen den einzelnen Polygonen der Szene, indem er jeweils für Polygonpaare (Links) den Lichtaustausch unter Berücksichtigung geometrischer Gegebenheiten wie Abstand und Verdeckung berechnet. Durch wiederholte Simulation des Austauschs für alle Links der Szene wird eine approximative Lösung gefunden, die den Gleichgewichtszustand des Systems beschreibt. Eine übliche, weil praktikable Festlegung ist, daß die Helligkeit eines Polygons über seiner ganzen Fläche konstant ist. Eine realistische Beleuchtung erhält man dann durch die Unterteilung von Polygonen in mehrere Teilpolygone. Beim HRV wird die Unterteilung adaptiv an den Stellen vorgenommen, wo der Beleuchtungsfehler groß ist. Der Grad der Unterteilung kann beliebig durch Angeben des maximal tolerierbaren Beleuchtungsfehlers festgelegt werden.

Hardware

Das HRV wurde im Rahmen der Diplomarbeit auf der Connection-Machine-5 (CM-5) im SPMD-Stil (single program multiple data) unter Verwendung von message passing-Routinen realisiert. Die CM-5 ist ein skalierbarer massiv paralleler Supercomputer, dessen Prozessoren (SPARC-2) vollständig durch einen sogenannten Fat-Tree miteinander verbunden sind. Für die Diplomarbeit standen maximal 64 Prozessoren zur Verfügung. Das Programm wurde objektorientiert konzipiert. Die verwendete Programmiersprache ist C++ unter Unix.

Parallelisierung

Für die Parallelisierung des HRV wird der Algorithmus als ein Verfahren aufgefaßt, das einen großen ungerichteten Graphen manipuliert. Der Graph enthält die Daten der Szene und die Abhängigkeiten bzgl. bestimmter Aufgaben. Da der Graph adaptiv und damit nahezu unvorhersagbar manipuliert wird, ist eine starre Verteilung des Graphen auf die Prozessoren ungeeignet, um eine gute Auslastung aller Prozessoren zu erreichen. Stattdessen wird zu mehreren Zeitpunkten im Verlaufe des Verfahrens geprüft, ob die dynamische Manipulation des Graphen aktuell zu einer schlechten Auslastung geführt hat. Simulated Annealing [3] wird in diesem Fall benutzt, um den Graphen so umzuverteilen, daß die Auslastung wieder gut und der Kommunikationsaufwand nahezu minimal wird.

Die beim HRV zu erledigenden Aufgaben - wie z. B. das Unterteilen eines Polygons oder die Berechnung des Lichtaustauschs - werden zum Zwecke der Parallelisierung in unabhängig voneinander abzuarbeitende Teilaufgaben unterteilt. Ein spezieller Programmteil, der Scheduler, organisiert das Anfordern und Entgegennehmen der Informationen an bzw. von anderen Prozessoren. Die Wartezeiten werden durch die Verwendung von nach Prioritäten geordneten Warteschlangen minimiert. Der Nachrichtenaustausch erfolgt asynchron und damit sehr effizient. Der parallele Algorithmus ist auf beliebig viele Prozessoren skalierbar. Das Programm kann leicht auf andere Parallelrechner, die das message-passing-Paradigma unterstützen, übertragen werden.

Ergebnisse

Für eine Beispielszene (eine Hausetage mit 12 Räumen) erzeugte das Verfahren über 56000 Links. Auf 64 Prozessoren wurde ein Speedup von 8.4 bei einer Berechnungszeit von 296 Sekunden erreicht. Die Auslastung der Prozessoren lag bei durchschnittlich 55 Prozent.

Das HRV ist inhärent nicht-parallel. Durch einen hohen Kommunikationsaufwand und die nicht vorhersagbare dynamische Entwicklung der bearbeiteten Daten wird der durch mehrere Prozessoren gegebene Geschwindigkeitsvorteil geschmälert. Dennoch wurden signifikante Verbesserungen erzielt.

Dokumentation

Die Diplomarbeit umfaßt eine detaillierte Beschreibung des bekannten sequentiellen HR-Verfahrens sowie dessen Parallelisierung. Teilaspekte, wie z. B. das Unterteilen von Polygonen und Sichtbarkeitsberechnungen, werden vertiefend betrachtet. Das auf der CM-5 implementierte Programm wird mit all seinen Modulen eingehend erläutert. Für verschiedene Beispielszenen werden empirisch gewonnene Laufzeiten unter unterschiedlichen Aspekten analysiert und interpretiert.

Literatur

[1] P. Hanrahan, D. Salzman, L. Aupperle. A rapid hierarchical radiosity algorithm. Computer Graphics, 25(4):197-206, Jul. 1991.
[2] J. T. Kajiya. The rendering equation. Computer Graphics, 20(4):143-150, Aug. 1986.
[3] S. Kirkpatrick, C. D. Gelatt, Jr. M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671-680, May 1983.
Robert Garmann, 10.6.2007
HOME