PARILLU - Parallel simulation of global illumination

# Introduction

PARILLU resides around the interface of two disciplines in computer science: computer graphics (global illumination) and parallel computing (dynamic partitioning).

## Global Illumination

The creation of raster images out of a given description of geometrical and optical characteristics of a 3D scene is the subject of Rendering. An increasing number of applications needs higher degrees of realism. Actually, the light at a point indirectly depends on all light globally transmitted through the scene. Formally this fact is described by a linear operator equation of the form L=Le + T L. Solving this equation is the subject of global illumination algorithms.

There are two basic approaches for solving the global illumination problem, the Finite Element approach and the Monte-Carlo approach, also known as the Radiosity approach and the Raytracing approach. Both approaches are very time consuming raising the natural question for a parallel computer implementation. There is no common agreement, which of these two approaches is generally preferable.

## Dynamic Partitioning

When implementing an algorithm on parallel processors one has to partition the algorithm into equally sized blocks such that all processors are kept busy while interprocessor-communication is kept as low as possible.

The accurate solution of many problems in science and engineering requires the resolution of unpredictable physical phenomena. Such problems may involve complicated partial differential or integral equations and originate from materials design, computational fluid dynamics, astrophysics, molecular dynamics, and - last but not least - global illumination. The most important feature of all these numerical problems is that some regions of the computational domain require deeper resolution than others, and that these regions are not known from the beginning. Hence, the partitioning of the algorithm should be adapted dynamically while the computation proceeds.

## Contributions

On the one hand the hierarchical radiosity algorithm (HRA) is examined with respect to its capability of being parallelized. On the other hand we develop a general tool for the dynamic partitioning of spatially mapped tasks, that is furthermore 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 get useful speedup values.

 Robert Garmann, February 22, 2002