6.7 Hierarchical Refinement and Clustering

All mesh-based algorithms covered so far in this chapter share a common drawback, illustrated in Figure 6.26. If patches are chosen too small, variance will be high. If they are chosen too large, however, disturbing discretization artifacts, such as too smooth illumination and blurred shadow boundaries, result. We discuss here how hierarchical refinement [30, 64, 164] and clustering [182, 174] can be incorporated in stochastic radiosity algorithms. Doing so significantly reduces these problems and considerably boosts the performance of stochastic radiosity algorithms.

Figure 6.26: The left image illustrates meshing difficulties with stochastic radiosity. On the one hand, high variance on small patches leads to disturbing noisy artifacts? some of these patches will receive no rays, so that they will be rendered black, while other small patches appear overly bright. Large patches, such as the walls and floor in this image, for instance, appear too smooth as only a single radiosity value is computed for the whole patch. Adaptive meshing, hierarchical refinement, and clustering reduce these problems (right image). (The conference room model shown is by Anat Grynberg and Greg Ward, Lawrence Berkeley Laboratory, Berkeley, California).

Hierarchical refinement and clustering have been introduced in radiosity with two goals in mind: automatic, adaptive meshing and a reduction of the number of form factors. First, it splits up large patches into smaller ones so that a more accurate radiosity solution is obtained where necessary. Collections of small patches, on the other hand, can also be grouped ...