Dynamic Update of Radiosity Simulations
Deliverable 411

Data Structures and Algorithms for Efficient Radiosity Update

We have been evaluating possible data structures, with which efficient radiosity updates can be established for both fast, but not converged solutions, and high-quality, converged radiosity solutions. It seems that a hierarchical approach is well suited to fulfill this task, and therefore we decided to base our data structure on the Line-Space-Hierarchy (LSH).

The use of clustering and the LSH provides an algorithmic basis which permits interactive updates for complex environments. However, evaluating this approach, we identified several drawbacks. The most important drawback this approach suffers from is definitely its enormous memory consumption when storing shafts for the entire scene. We therefore decided to attack this drawback within the ARCADE project, and developed a method for reducing the memory requirements of the LSH by the dynamic management of shaft storage, which has been presented at the Tenth Eurographics Workshop on Rendering in 1999 [SP99].

The basic idea of this LSH extension, which has been integrated into Fraunhofer IGD's radiosity system Genesis2, is to store shaft information only locally for those parts of the scene that are currently affected by the geometry change. When the dynamic object enters new regions, new shaft data has to be computed, but on the other hand we can get rid of outdated data behind the dynamic object, using a garbage collector approach.

Dynamic shaft management

During object movement

After Line-Space update

Dynamic shaft management (shafts held in storage are indicated by red lines): Shafts at the old position of the chair.

During object movement, new shafts for the new position of the dynamic object are added to those held in storage.

After Line-Space update, outdated shafts behind the dynamic object are removed by the garbage collector.

Simple movement prediction schemes are applied, so that we can provide shaft data to the radiosity update process in time when needed. The storage management and pre-calculation of shafts can be efficiently performed in parallel to the update process itself, in order to minimize calculation overhead, if parallel hardware is available.

Predicted bounding volumes (green), extrapolated from previous (blue) and current (red) object position.

Predicted bounding volumes of the dynamic object for the next five frames, taking into account object translation and rotation..

The approach applied for storage reduction is adjustable to the available memory size. Memory consumption can be reduced significantly (up to 95% memory savings have been obtained in test applications), which makes the LSH approach applicable to complex real-world scenes.