New contributions to spatial partitioning and parallel global illumination algorithms

Abstract

Diese Dissertation ist an der Schnittstelle zweier Disziplinen der Informatik angesiedelt: Computergrafik (Globale Beleuchtung) und Paralleles Rechnen (Dynamisches Partitionieren). Einerseits wird der Hierarchische Radiosity Algorithmus (HRA) - ein berühmter und effizienter Algorithmus zur globalen Beleuchtungssimulation - bzgl. seiner Parallelisierungsfähigkeit untersucht. Andererseits wird ein Werkzeug aus der Gattung der orthogonalen rekursiven Zweiteilungsverfahren zur dynamischen Partitionierung räumlich abgebildeter Aufgaben entwickelt sowie theoretisch und experimentell analysiert. Der HRA ist eine spezielle Instanz von Algorithmen, die als eine Ansammlung von räumlich abgebildeten Aufgaben formuliert werden können. Als Beweis der Praktikabilität unseres Werkzeugs wenden wir das Werkzeug auf den HRA an und beobachten ein gut skalierbares Verhalten und nützliche Werte bzgl. der Steigerung der Berechnungsgeschwindigkeit.

This thesis resides around the interface of two disciplines in computer science: computer graphics (global illumination) and parallel computing (dynamic partitioning). On the one hand the hierarchical radiosity algorithm (HRA) - a famous and efficient global illumination algorithm - is examined with respect to its capability of being parallelized. On the other hand a dynamic orthogonal recursive bisection tool for the dynamic partitioning of spatially mapped tasks is developped and analyzed theoretically and experimentally. The HRA is a special instance of algorithms that can be formulated as a collection of spatially mapped tasks. As a proof of practicability of our tool we apply the tool to the HRA and observe a well scalable behaviour and useful speedup values.