Automatic creation of object hierarchies for radiosity clustering

Using object clusters for hierarchical radiosity greatly improves the efficiency and thus usability of radiosity computations. By eliminating the quadratic starting phase very large scenes containing about 100 K polygons can be handled efficiently. Although the main algorithm extends rather easily to using object clusters, the creation of “good” object hierarchies is a difficult task both in terms of construction time and in the way how surfaces or objects are grouped to clusters. The quality of an object hierarchy for clustering depends on its ability to accurately simulate the hierarchy of the energy flow in a given scene. Additionally it should support visibility computations by providing efficient ray acceleration techniques. In this paper we present a new approach of building hierarchies of object clusters. Our hybrid structuring algorithm provides accuracy and speed by combining a highly optimized bounding volume hierarchy together with uniform spatial subdivisions for nodes with regular object densities. The algorithm works without user intervention and is well suited for a wide variety of scenes. First results of using these hierarchies in a radiosity clustering environment are very promising and will be presented here. The combination of very deep hierarchies (we use a binary tree) together with an efficient ray acceleration structure shifts the computational effort away from form factor and visibility calculation towards accurately propagating the energy through the hierarchy. We show how an efficient single pass gathering can be used to minimize traversal costs