Clustering for glossy global illumination

Reviewer: Frederik W. Jansen

Global illumination methods calculate the interaction of light within a scene by applying either sampling-oriented Monte Carlo ray tracing techniques or finite-element radiosity algorithms. Radiosity algorithms calculate the diffuse interreflections efficiently, while Monte Carlo ray tracing algorithms perform better on specular (glossy) reflections. Two-pass algorithms combine the two techniques, using radiosity preprocessing for the diffuse reflection and a ray tracing pass for the specular reflection. However, the radiosity pass in the two-pass algorithms is not adequate for glossy environments because the contributions of the specular reflected light to the diffuse reflection are not fully accounted for. Recently, several methods have been proposed to extend the radiosity calculation with specular (glossy) reflection, either by introducing three-point interactions or by adding a directional component to the computation and representation of the energy exchange. In an earlier paper [1], the authors presented an extended radiosity algorithm in which the reflected energy at points on the surfaces in the scene is represented as a four-dimensional distribution (using two dimensions for position and two for direction), which is compactly represented by a four-dimensional wavelet function. Although the radiosity algorithm works with a discrete representation of the scene where the surfaces are subdivided into patches or elements, and energy exchange is only calculated on a patch-by-patch basis, the number of interactions is still rather high, as each patch may interact with every other patch. The number of interactions can be reduced by using hierarchical radiosity in combination with the notion of importance: surfaces are only subdivided when their interactions with other patches contribute significantly to the shading of the visible surfaces in the scene. Surfaces that have less important interactions remain coarsely subdivided. Nevertheless, for complex scenes, this still leaves too many expensive interactions. In this paper, the authors extend their technique by extending the hierarchy above the surface level: smaller surfaces are grouped into clusters, a method that has been applied to other hierarchical radiosity methods. With clustering, the scene is recursively subdivided into smaller cells, effectively organizing the surfaces into a hierarchy. Interactions are sought on a meaningful level within the hierarchy: direct interactions are only calculated between the most important patches, while for less important patches, clusters take over the active role as energy senders and receivers. Obviously, the clustering introduces some error as the energy for each cluster is assumed to arrive at and be sent from only one central point in the cluster. The authors derive an error bound that automatically decides on the level of interaction within the hierarchy. They propose methods to account for cluster visibility: in general, a cluster will not intercept all the light passing through it. They also present a transfer function for the interaction between a cluster and its patches. The authors prove that the complexity of their method is O p , where p is the number of initial surfaces. They further compare their method with a proven Monte Carlo ray tracing method and show that the visual result converges to the same solution faster. We can thus conclude that the radiosity method is completely functionally equivalent to and potentially more efficient than the Monte Carlo ray tracing method, although ray tracing is still applied for the display in order to obtain the required higher resolution of the specular reflection in the direction of the viewpoint.

Reviewer: Claudio Delrieux

Radiosity is one of the three major rendering approaches (the others are ray tracing and scan line algorithms). Radiosity provides a physically adequate solution to diffuse illumination and reflection, but it excludes specular and glossy illumination and reflection. Implementations of radiosity are quite expensive in time and memory but are viewer-independent, so they can be good in architectural and lighting design and animation. Integration of this rendering schema with ray tracing in a complete illumination model has not been satisfactory. Within this context, extending the modeling capabilities and performance of radiosity algorithms is welcome. This work extends previous research in clustering techniques to allow for nondiffuse reflectors. Scenes are subdivided into clusters of reflectors, which are represented by two directional radiance distributions (outgoing and incoming) and an importance measure. In this way, the authors show how to hierarchically subdivide the computations and refine the results to an arbitrary precision. The authors compare this work with most of the related work (especially the wavelets approach, which is currently attracting a lot of attention), and show that they obtain a better asymptotic complexity. The contribution is to a specific area in computer graphics, but the ideas are promising, and radiosity is becoming mainstream research.