Automatic creation of object hierarchies for radiosity clustering

Using object clusters for hierarchical radiosity greatly improves the effic iency and thus usability of radiosity computations. By eliminating the quad ratic star ting phase very large scenes containing about 100k polygons cart be handled efficiently. Although the main algorithm extends rather easily to using abject clusters, the creation of 'good' abject hierarchies is a di fficult 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 an 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 will present a new approach of building hierarchies of obj ect clusters. Our hybrid structuring algorithm provides accuracy and speed by combining a highly optimized bounding volume hierarchy together with uni form spatial subdivisions for nodes with regular object densities. The algo rithm works without user intervention and is well suited for a wide variety of scenes. First results of using these hierarchies in a radiosity cluster ing environment are very promising and will be presented here. The combination of very deep hierarchies (we use a binary tree) together wi th an efficient ray acceleration structure shifts the computational effort away from form factor and visibility calculation towards accurately propaga ting the energy through the hierarchy. We will show how an efficient single pass gathering can be used to minimize traversal costs.