Hierarchical Data Structures for Lighting Simulation

Current work and first results [added 08/10/1998]

Ongoing work concerns the development of new clustering algorithms. The basic goals of clustering algorithms for Radiosity are:

In addition, cluster hierarchies for lighting often play the role of a ray-tracing acceleration structure.

For light transfer representation, we have various data structure choices. Notably we can use:

Clusters affording a good representation for light transfer will preserve the nature of the object group shapes; will not group objects which are far from each other or which would cause clusters with large empty spaces; avoid overlapping as much as possible.

We are investigating the different possibilities in the choice of clustering algorithms:

We are investigating a new approach which will combine the advantages of the above two methods and will provide a mixture of automatic and user-tuned construction policies. A set of different scene types will be selected, and statistics will be used to determine when a bottom-up or top-down strategy results in higher quality clusters. This will be used to determine a set of criteria allowing the choice of an appropriate clustering algorithm.