A clustering algorithm for radiosity in complex environments.
We present an approach for accelerating hierarchical radiosity by clustering objects. Previous approaches constructed effective hierarchies by subdividing surfaces, but could not exploit a hierarchical grouping on existing surfaces. This limitation resulted in an excessive number of initial links in complex environments. Initial linking is potentially the most expensive portion of hierarchical radiosity algorithms, and constrains the complexity of the environments that can be simulated. The clustering algorithm presented here operates by estimating energy transfer between collections of objects while maintaining reliable error bounds on each transfer. Two methods of bounding the transfers are employed with different tradeoffs between accuracy and time. In contrast with the O(s2) time and space complexity of the initial linking in previous hierarchical radiosity algorithms, the new methods have complexities of O(slogs) and O(s) for both time and space. Using these methods we have obtained speedups of two orders of magnitude for environments of moderate complexity while maintaining comparable accuracy.
Introduction
Recent trends in realistic image synthesis have been towards a separation
of the rendering process into two or more stages[10, 2, 9]. One
of these stages solves for the global energy equilibrium throughout
the environment. This process can be very expensive and its complexity
grows rapidly with the number of objects in the environment.
These computational demands generally limit the level of detail of
environments that can be simulated. Furthermore, a solution to this
problem must be computed before anything useful can be displayed.
Radiosity algorithms attempt to solve the global illumination
problem by discretizing the environmentand solving a linear system
to approximate the transfer of energy between the elements [5]. For
complex environments,the large number of interactions is expensive
E-mail: {bes arvo | dpg}@graphics.cornell.edu
to compute, as each requires form factor and visibility calculations.
The challenge is to reduce the computational complexity of this
process. In one of the early approaches, Cohen et al. [3] reduced
the number of interactions by imposing a two-level hierarchy of
patches and elements on the environment. Although the number of
interactions was reduced, the approachwas still O(p 2 ) in the number
of elements in the environment.
Currently, the best radiosity algorithms are analogous to linear-time
algorithms for charged particle simulation [6]. These algorithms
work by clustering particles together so that the mutual effect
of well-separated collections can be approximated with a single
interaction. Hanrahan et al. [7] used a similar strategy to reduce
the number of interactions needed for a radiosity solution. A hierarchical
structure was imposed on each surface in an environment
and interactions were allowed to occur between the appropriate levels
on each. This approach works well when the number of initial
surfaces is small, as hierarchical radiosity (HR) algorithms can "sub-
divide" large surfaces into smaller ones, but cannot "group" smaller
elements into larger ones. The initial linking phase of HR must
check all pairs of initial surfaces for potential interactions; without
grouping surfaces together the algorithm is quadratic in the number
of initial surfaces. Because complexity in environments is often a
result of replacing large surfaces with many small surfaces, this inability
to group objects together is a major obstacle in conventional
HR algorithms.
Several methods have been developed to increase the efficiency
of HR algorithms for complex environments. Global visibility [13]
is effective for computing the initial links for environments in which
only a small number of "cells" see each other. Many environments,
however, also contain large collections of objects that are mutually
visible. In such cases, global visibility algorithms do not suffice.
Importance [12] is another method that reduces computation in
areas that have little or no noticeable effect on the surfaces of interest.
This approach is effective once the initial interactions have been
computed, but does nothing to reduce the time of the initial linking
phase. Importance driven hierarchical radiosity stands to gain even
more from clustering than standard hierarchical radiosity. Because
it attempts to compute the radiance very coarsely in some regions
of the environment, some means of clustering is needed if it is to do
less work than that required for the initial linking.
An approach to clustering was developedby Rushmeier et al. [11]
in which the effect of complex groups of surfaces is approximated
by simpler representations resembling BRDF's obtained through
Monte Carlo sampling. One disadvantage of this approach is that it
is not automatic; appropriate clusters must be specified and approximated
in advance. Also, no hierarchy is maintained, so the coarsest
representation used by the algorithm is that of the selected clusters.
Another clustering approach was proposed by Kok[8], which extended
progressive radiosity so that patches could transfer energy to
a-link
b-link
Patch link

Figure

1: Two collections of objects can interact at different levels:
a) conventional HR links, b) an ff-link requiring linear time and
space, and c) a fi-link requiring constant time and space.
groups of surfaces at once. Neither of these approaches analyze the
error of the approximations used for the transfers.
To illustrate why clustering is important, consider a simple configuration
consisting of two chairs, each containing 100 surfaces.
HR would check the 10,000 potential interactions between the two
chairs and would create in the neighborhood of 2,500 patch links

Figure

1). However, if the chairs are well separated, then it is
unlikely that the energy transfer between them will have a significant
effect on the illumination of either. If we can guarantee this
throughout the entire solution, we can gain efficiency by coarsely approximating
the transfer of energy between them. We shall present
a new strategy for linking that would handle this configuration by
creating a single link with a cost comparable to either 1 or 200
conventional links, depending on the separation of the objects. By
reducing the total cost of the links created between two collections
of objects, we reduce the algorithmic complexity of the O(s 2 ) initial
linking step in HR.
1.1

Overview

Hierarchical algorithms for radiosity have three components: 1)
a hierarchical description of the environment, 2) a criterion for
determining the level in the hierarchy at which two objects can
interact, and 3) a means of estimating the energy transfer between
the objects.
As our criterion for interaction, we use bounds on the potential
error in the transfer of energy betweentwo objects. We first describe
hierarchical radiosity using this approach, and then present two
efficient techniques for bounding the transfers between clusters.
The first technique is a fairly accurate approach which we call ff-
linking. The second is a faster but less accurate approach which
we call fi-linking. Corresponding to these methods for determining
bounds are two ways of estimating the transfer of energy between
clusters. We also describe the method used to create the hierarchy
of clusters, which is the starting point for the cluster-based linking
strategies. Finally we give theoretical boundson the complexity and
results of our implementation demonstrating dramatic speedupsover
conventional HR in complex environments.
Hierarchical Radiosity
The value of the radiance function L on a surface at a point x due to
another surface S i can be expressed as
Z
where the kernel k(x, y) expresses the radiance at x due to a differential
area at the point y. The kernel can be written
is the angle formed by the normal of the differential area at
x and the direction given by y \Gamma x and ' 2 is the angle formed by the
normal of the differential area at y and the the direction given byx\Gammay.
Also ae is the bidirectional reflectance distribution function (BRDF).
In this paper we shall only address ideal diffuse scattering, although
much of the analysis extends to general reflectance functions.
To compute the exact radiance function across the receiver, L(x)
must be evaluated at every point on the receiver. In general, some set
of basis functions are used to represent the radiance functions and
quadrature rules are used to compute the coefficients for the basis
functions. This reduces the problem to evaluating L(x) at some fixed
number of points.
For an environment meshed to a fixed number of patches p,
there are potentially p 2 interactions. HR maintains a hierarchical
representation of each initial surface; for example, by means of a
quadtree. HR then allows surfaces interact at a level in the hierarchy
where all the interactions have an error less than some bound. This
requires bounding the error in the transfer between two patches,
which can be done by bounding the difference between the maximum
and minimum transfers[12]. The maximum transfer can be
computed by finding the maximum value of k(x, y) over all points
on the two patches and then integrating the product of this with the
radiance of the source. We will denote the maximum value of a
function f over some range A \Theta B as
f (x, y).
Using this notation the bound on the energy transfer may be written
Z
L(y)dy.
This expression allows for arbitrary distributions of radiance across
the source. The minimum can be computed similarly, with the minimum
set to zero if any two points are occluded. The maximum
and minimum values of k are computed by taking a set of jittered
samples on both the source and receiver and computing the maximum
and minimum values of the kernel between all pairs of samples
[12]. Occasionally, this approach greatly underestimates the max-
imum, such as when a small patch is very close to a large patch.
Such an underestimate usually will not prevent further subdivision,
however, and the problem diminishes as the two patches approach
the same size. Bounding the error in the transfer of energy and
only computing interactions to a given accuracy results in a linear
number of interactions [7]. The transfer of energy between the two
surfacescan then be determined using any of the various form-factor
methods.
The main deficiency of HR is that the coarsest representation is
the initial surfaces. By collecting a group of these surfaces together,
we obtain an even coarser representation. To make use of this
coarser representation, we require a bound on the transfer of energy
between two such clusters. This bound must be computed in less
Source
Receiver

Figure

2: Straightforward approach to bounding error. Each link
represents a maximum value for k.
than O(s 2 we are to gain an improvement over the brute
force method of checking all pairs of interactions. We now describe
two ways of bounding error, each with a time complexity better than
3 Bounding error on clusters
In this section we describe two strategies for computing bounds on
the energy transfer between clusters; one requiring linear time and
space, and one requiring constant time and space. The strategies
are derived by systematically introducing approximations into the
exact expression for energy transfer. The first level of approximation
results in a type of link we call an ff-link. By introducing further
approximations we produce fi-links. Although these bounds are
coarse, they often suffice for a very large fraction of the interactions.
3.1 ff-links
The transfer of energy from a cluster of patches S to a point can be
computed by summing over the n patches in the source cluster
Z
k(x, y)L(y)dy.
Since k(x, y) is a function of the position and orientation of the
receiver as well as the source and of the visibility between them,
computing the transfer of radiance between two clusters requires
evaluating L(x) at least once on each of the m receivers, resulting in
O(mn) work.
Applying the same approach used for HR to two clusters is relatively
expensive. To bound the transfer between the clusters with
this approach, we can use the maximum value of k(x, y) over pairs
of patches to bound the transfer. The maximum radiance over all
receivers due to the source cluster can be bounded by
Z
L(y)dy.
The maximum value of the kernel function must be computed for
each pair of patches, so the time complexity is O(mn). (See Figure
2.)
To improve the time complexity, we split the kernel function into
two simpler functions k r (x, y) and k s (x, y) given by
Then
Each of the new functions depends on two points, but each requires
information about the orientation of only one surface. k r
Source
Receiver

Figure

3: More efficient ff-link between two clusters.
accounts for the projected area and reflectivity of a differential area
around x and k s corresponds to the differential solid angle subtended
by a differential area around y. We now show that the above
separation of the kernel can be used to conservatively bound the
interaction between the source cluster and the receiver cluster. This
is done by bounding the energy that reaches the receiving cluster
from the source, and then determining how much of this energy
potentially reaches each receiving patch. (See Figure 3.)
We now use these pieces of the kernel to bound the radiance
function at a point x. First, k r (x, y) is replaced by the maximum
value it attains over all y in the volume B(S) containing all the
source patches. Then, for each of the sources, we replace k s (x, y)
by the maximum value it attains over all y on the source patch. We
can also assume that the visibility term is always 1. These steps
produce the following conservative upper bound:
Z
Z
dk s e x,S
Z
L(y)dy.
We can apply this idea to obtain upper bounds on the transfer between
the two clusters. The quantity k s (x, y) can be maximized over
all points in the receiving volume B(R) making k s (x, y) independent
of any particular receiver. The factor k r (x, y) can now be maximized
over each receiving patch separately. Thus, the radiance function
can be bounded as follows
dk s e B(R),S
Z
L(y)dy.
This expression can be separated into two pieces by defining
Z
L(y)dy,
which is a bound on the flux density incident upon the receiving
bounding volume. Then
dk r e R j ,B(S) L S max .
Maximizing over all of the receiving patches in R requires O(m)
work. Therefore the time complexity of computing this bound has
been reduced from O(mn) to O(m n).
The bounds needed for HR can be computed from upper and
lower bounds on the transfer. We have given upper bounds; a trivial
lower bound of zero can always be used. This lower bound is
attained when the visibility between all points in the two clusters is
zero. Now we have a bound on the error in the interaction between
two clusters, which allows us to determine when an interaction is
accurate enough. This bound on clusters determines if an ff-link is
an acceptable approximation for the interaction.
In addition to the error bound, we require an estimate for the
energy transferred to each receiving patch across the ff-link. We do
this by computing an estimate as well as the bound for the k r (x, y)
associated with each receiving patch and the k s (x, y) associated with
each source patch. Let
Now the radiance on receiving patch j can be estimated by
where
Z
L(y)dy.
Each average is bounded above by the maximum transfer and therefore
falls within the error bounds; hence it is sufficiently accurate.
In fact, it is quite likely far more accurate than the conservative
bounds indicate.
We now show that the ff-link clustering approach has time and
space complexity of O(s log s). First, assume we have s initial
patches stored in a hierarchy of clusters with each cluster containing
two smaller clusters or, at the leaves, a single patch. This structuring
results in a binary tree with a depth of log s. The total number of
clusters at level d is 2 d and each cluster at level d has s/2 d patches.
following Hanrahan et al. [7] and Greengard [6], we assume
each cluster is linked to a constant c 1 number of other clusters
resulting in c 1 2 d ff-links on level d. We can also assume that each
cluster is linked to other clusters at approximately the same level in
the tree. An ff-link between two clusters requires space and time
proportional to the size of the clusters. Summing the costs for each
of the log s levels of the hierarchy gives
log s
num links d   link cost
log s
s
Therefore, rather than the O(s 2 ) work required for a direct ap-
proach, clustering using ff-links gives a time and space complexity
of O(s log s).
3.2 fi-Links
For many transfers, the previous technique is still too expensive.
Often large numbers of interactions are insignificant and can be
treated very coarsely or ignored altogether [9]. In this section
we introduce a more efficient but cruder method for bounding the
interaction between two clusters. We do this using a very simple
bound on the kernel k(x, y) which we denote k d (x, y),
This bound requires no knowledge about the orientation of the sur-
faces. We can bound the transfer of energy between two clusters
by replacing k by the maximum value of k d over all points x in the
receiving cluster and all points y in the source cluster. (See Figure
4.) Thus,
\Upsilon
Z
L(y)dy.
Source
Receiver

Figure

4: fi-link between clusters.
This is a worst-case bound on the transfer between two clusters;
it is only achieved when all surfaces are as close as possible to
the other cluster, and each source directly faces all the receivers.
The virtue of this bound is that it requires no knowledge of the
surfaces. If the integral of the radiance over all the source patches
has beencomputed in advance,during the sweep operation described
in section 5.1, then the bound can be computed in constant time.
As with the ff-links, we can use the average value of k d over the
two clusters as an estimate of the energy transferred between them.
Again, since the average value lies within the range given by the
maximum transfer and a minimum transfer of zero, it meets the
error tolerance.
The time and space complexity of a system with fi-links is equivalent
to the complexity of the standard hierarchical radiosity method.
As with linking patches, the error term decreases rapidly with dis-
tance, so each cluster will be linked to a constant number of other
clusters. Since the number of clusters is linear in the number of
initial surfaces, and the cost of a fi-link is independent of the size of
the clusters, the complexity is O(s) where s is the number of initial
surfaces.
3.3 Strategies for linking
We have described two different approaches for linking clusters.
The more accurate clustering technique tends to be too expensive
for many clusters in a large environment. The faster clustering
technique is too coarse to eliminate many of the negligible interac-
tions. Our approach is to exploit the strengths of both strategies.
If the coarse approach does not produce an acceptable bound then
the more accurate technique is invoked. If neither are accurate
enough, then the clusters are recursively subdivided. Only when
the level of individual patches is reached does the algorithm resort
to conventional HR.
Linking Criteria
Norms provide a measure of the "size" of a function. We shall
use two different norms to quantify error in the energy transfer
between two patches or clusters. In the previous section we computed
a bound on the maximum possible difference between the
approximated radiance and the actual radiance over all points on
the receiving object. This corresponds to computing a bound on the
1-norm of the radiance function on the receiver due to the source.
More formally, if L is the exact radiance function over the receiver,
and e L is the computed radiance function then
where M is one of the previous bounds on the transfer.
The 1-norm gives a bound on the variation between the computed
radiance and the actual radiance. Another useful bound is the
energy of the difference between the computed and actual radiance
functions due to a link. This bound corresponds to the 1-norm.
More formally,
Z
R
The 1-norm can be bounded by weighting each term of the receiver
by the area of the receiver and summing instead of finding the
maximum value. We can write this bound for ff-links as
Z
L(y)dy
where A j is the area of receiver j. Coarse bounds and patch-to-
patch bounds are computed similarly. In a hierarchical solution
both norms are easily accommodated, but the norm used affects
the subdivision strategy. After performing a local pass to display a
solution, the error at each pixel is important, which implies that the
1-norm is most appropriate. However, during the global propagation
of energy throughout an environment, it may be more useful to
minimize the 1-norm of the error. Intuitively, this is because large
surfaces will often have a much more significant effect on the local
pass than the smaller ones.
Another useful norm is obtained from the importance weighting
[12]. This corresponds to a norm very similar to the 1-norm; rather
than weighting each receiver by the area, the receiver is weighted
by its importance.
5 Implementation
5.1 Clustering
Most ray tracing acceleration techniques collect nearby objects together
into groups. Some of these, such as octrees and hierarchical
bounding volumes, form a natural hierarchy. The same hierarchy
can be used to identify clusters. For simplicity, each object should
appear in only one cluster. Otherwise, some method of eliminating
copies of objects is needed to prevent an object from contributing
to a cluster twice. For these reasons we chose to use bounding volume
hierarchies [4] instead of octrees to generate our hierarchy of
clusters. We use axis-aligned rectangular bounding boxes for both
the clusters and for ray casting.
The HR algorithm can be combined with a bounding volume
hierarchy to perform clustering fairly easily. The bounds on the error
given earlier fit naturally into the brightness-weighted refinement
scheme of Hanrahan et al. [7]. This approach first links the surfaces
together, then performs several iterations of energy propagation and
refinement of the system. The error tolerance is gradually reduced
until the final error tolerance is reached. This approach is a variation
on the "multigridding" method for iteratively solving systems of
linear equations.
Very few modifications are needed to make to the bounding volume
data structures useful for clustering. For the more accurate
clustering approach, we must loop over all of the patches in the
bounding volume. Each link will contain four arrays that hold both
the maximum and average values of k s for all the source patches as
well as the maximum andaverage values of k r for all of the receiving
patches. In our implementation the maximum values are approximated
by taking a fixed number of jittered samples on the patch and
bounding volume, then finding the maximum value of the kernel at
these points. Although this method does not produce a guaranteed
bound, it tends to produce a good approximation. If two bounding
volumes overlap, the maximum values can be unbounded. In this
case we can choose a maximum based on the maximum potential
transfer of energy in the environment. We store an estimate of the
inter-cluster visibility in the link as well. Visibility is estimated using
ray casting. The following pseudocode shows the steps needed
to compute an ff-link between two clusters.
Create-ff-link(Src, Rec)
ff-link T
foreach patch i in Src
foreach patch j in Rec
if ff-Bound(T) < ffl then return TRUE
else return FALSE
Procedure ff-Bound(T) computes the bound on the maximum
amount of energy transferred across ff-link T. We have estimates of
the maximum values of k s and k r stored in the link. The integral
of the radiance function L i over patch i for constant patches is the
product of the radiance L i and the area A i of the patch. The procedure
for computing the error incurred by an ff-link between clusters is
shown in the following pseudocode:
foreach patch i in T.Src
foreach patch j in T.Rec
MaxErr Max(MaxErr, T.RecMax[j] * SrcErr)
return MaxErr
In addition to computing the error on the links, energy must be
transferred between the two clusters. During the gather step of HR,
energy is transferred across each link, including all cluster links.
The gather across an ff-link T is performed as follows.
foreach patch i in T.Src
SrcRad SrcRad * T.Vis
foreach patch j in T.Rec
For the coarse approach to clustering using fi-links, we store the
sum of the areas of all the patches in the bounding volume. We also
store the radiance of the bounding volume for use as a source, and
the irradiance striking the bounding volume for use as a receiver.
If the radiance on each patch of the receiving cluster were updated
each time a link was used in a gather, then gathering through a
single link would require linear time, resulting in worse complexity
bounds for coarse links. As in HR, after transferring energy across
the links the radiances must be swept to each object's parents and
children. For clusters, this sweep is a slightly different from the
sweep described in HR since each cluster holds the irradiance I
incident upon it, and the radiance leaving it. Irradiance is pushed
down the bounding volume hierarchy to the patches. The incident
irradiance is then weighted by the reflectance of the patch and the
resulting radiance is pushed down the patches as in HR. Pulling
radiance up from the children to the parents is the same as in HR.
Each parent receives the area-weighted average of the radiances of
its children. The following pseudocode is used when solving the
linear system to redistribute the energy gathered across the links.
HSweep is the conventional HR sweep procedure.
Sweep(C, I down )
I down /I down
if C is a leaf then
foreach patch R in C
else foreach C 0 in C
LC/L up
return L up
The fi-links between clusters are computed in a similar fashion
to the ff-links. They are easier to compute, however, as no looping
over the contents of the bounding volume is required. Also, the
maximum value for k d is the inverse of the square of the minimum
distance between the clusters, which can be computed with little
work for axis aligned bounding volumes. Each fi-link stores only
the maximum value and the best computed value of k d for the two
clusters.
Create-fi-link(Src,Rec)
fi-link T
vis / EstimateVisibility(Src,Rec)
\Upsilon
B(Rec),B(Src)
T.Avg vis
ff
B(Rec),B(Src)
if fi-Bound(T) < ffl then return TRUE
else return FALSE
The error in a fi-link between clusters is also straightforward,
following directly from the bounds on the transfer and the previous
discussion for higher accuracy links. Computing the error on a
fi-link T can be implemented as:
return T.Max * L T.Src * A T.Src
During the gather phase of the algorithm, each fi-link transfers
energy to the receiving cluster. It is stored there as irradiance until
the sweep phase when it is scaled by the BRDF.
I
The above procedures allow the clusters and patches of the environment
to be linked together. When two bounding volumes are to
be linked it is possible to first check for complete occlusion. This
can be done conservatively by checking to see if a convex object
completely obstructs the shaft between the source and the receiver.
If the two bounding volumes are not completely occluded, then the
fi-bound between the clusters is checked. When that is not sufficiently
accurate the ff-bound is checked. If this is still not accurate
enough, then the children of the larger cluster are recursively refined
against the smaller cluster. If neither of the clusters has children,
then the patches in both are refined against each other using the
patch refinement from HR. The clustering algorithm begins by
using the top-level bounding box both as source and as receiver,
which triggers the recursive refinement.
5.2 Local Pass
Once a global solution has been computed, displaying the result
usually involves smoothing the values computed for each patch so
that patch boundaries are not visible. This can be done by Gouraud-
shading the surfaces, however this is very prone to artifacts in hierarchical
systems [12]. A better approach is to use the techniques
of Lischinki et al. [9] and create a separate mesh for display pur-
poses, using the information obtained by the global solution, and
recomputing some parts of the illumination on each surface. Our
approach is based on this method as well as on the method proposed
by Reichert [10]. Given a view, we approximate the intensity100001e+06100 1000 10000 100000
Link
Cost
Initial Surfaces
s log s
Trials

Figure

5: Link cost for environments of different sizes compared
with the function s log(s).
by reconstructing the radiance function at each visible point in the
environment. This is done by taking the collection of links at all
levels of the hierarchy that directly affect this point, and for each
link recomputing the form factor from the source to the point. The
accuracy is determined by the magnitude of the error on the links,
and can result in either recomputing just the unoccluded form fac-
tor, or both the form factor and the visibility from each source to
the point. Although this method produces high quality results, it
is computationally expensive. The techniques of this paper only
address methods for efficiently computing the global pass. Further
research is required to accelerate the local pass.
6 Results
HR has a complexity bound (ignoring the visibility term) of O(s
p) where s is the number of initial surfaces and p is the number
of resulting patches. The O(s 2 ) term comes from computing the
initial links between all initial surfaces. Using clustering we do
not need to check all pairs of surfaces even if they are mutually
visible. Clustering replaces the expensive initial linking step with
an algorithm that is O(s log s) in the number of initial surfaces. This
results in an algorithm with an overall complexity of O(s log s
p). The sections that follow report results for several different
environments and refinement strategies.
6.1 Link Complexity
We first show how the cost of the links grows with the size of
the environment. As a first example, the inside of a sphere was
tessellated into triangles. Each triangle was given the same emissive
power and reflectance. This allowed us to vary s over a large range
of values without really changingthe geometry. Also, becauseevery
surface can see every other surface, it is easy to determine exactly
how many initial links would be needed without clustering. It is
also a challenging environment for clustering because every cluster
overlaps with several other clusters. We assign a cost of 1 for patch
links and fi-links. The cost for ff-links is m is the
number of patches in the receiving cluster and n is the number of
patches in the source cluster. The total link cost is the sum of the
link costs for each link computed for the environment. The model
was refined using the 1-norm criterion on the links. The graph in
figure 5 shows the link cost for five tessellations ranging from 128
patches to 32768 initial patches, as well as the function
The costs closely match the function.
For the largest tessellation a conventional HR algorithm would
need to create and store over one billion initial links before it could
(a) (b) (c) (d)

Figure

7: Solutions at different accuracies. With clustering (a-d), without clustering (e-h).100300500700900
Minutes
Iterations
a b c
d
With Clustering
Clustering

Figure

Time for solutions of increasing accuracy, both with and
without clustering.
compute a solution. With clustering the links cost only about 0.2%
of this, a reduction in both time and space of approximately 500.
6.2 Refinement Complexity
We now show howa solution refines over time both with and without
clustering. We start with an environment of 4170 initial surfaces,
illuminated by three directional lights and 8 emitting cubes, and
refine the solution from the initial linking stage through eight iterations
of successively smaller error tolerances. In this example we
used a 1-norm bound on the error for each interaction. A graph of
the times for the global solution as the accuracy increases appears
in figure 6. These solutions were computed on an HP 755 with
384 megabytes of memory to prevent swapping while computing
the solution without clustering. Images of the flat shaded patches
are shown for several different levels of accuracy in figure 7. The
long thin polygons in the model do not create ideal clusters because
of the large variation in position. Neither algorithm grows linearly
with the number of iterations, the algorithms are simply linear with
the number of resulting patches.
With clustering, HR becomes more of a progressive algorithm
since initial results can be seen relatively quickly. Without clustering
it took 583 minutes for the first solution to appear. Clustering
reduced that time to 5.35 minutes, a speed up of over one hundred
times. Both solutions refine at about the same rate once they are
linked. After eight iterations, the clustering solution resulted in
patches. Without clustering there were 114410 patches.
These numbers are very close because subdivision can only occur
by refining a patch link, and this is done the same way in both
algorithms. Bounds on the various kernels were estimated using 81
samples. Visibility was checked with 81 rays.
Clustering amortizes the cost of initial linking over many refinements
and except for simple environments, the amortization
continues well beyond the required levels of accuracy. This amortization
has some cost associated with it, but it is compensated for
by reduced link maintenance; that is, there is no need to maintain
the O(s 2 ) initial links through all the early iterations where high
accuracy is unnecessary
6.3 Importance
We also tested our algorithm using importance weighted refinement.
We used the same environment shown in figure 7, with a view of the
group of chairs near the stairs. The upper image shown in figure 8
was created with the view-dependent local pass described earlier in
the paper. The global solution used for the local pass is shown below
the image. The global pass with clustering took about 3 minutes
for the initial solution and 53 minutes for the entire global solution,
creating 27318 patches. Without clustering, the initial linking took
728 minutes and the entire global pass took 790 minutes. (Estimates
of form factor and visibility error were computed with more samples
to make the local pass more effective, causing the initial linking to
take longer than it did in the previous example.)

Figure

8: Image resulting from local pass (above) and solution used
for the local pass (below)
7 Conclusions and Future Work
Clustering is an effective technique for accelerating HR. By using
two different error bounds on the energy transfer between collections
of surfaces, two types of links between cluster were described.
Using both of these approaches in an HR algorithm reduces the
asymptotic complexity from O(s 2 +p) to O(s log s +p) in addition to
making HR a more progressive algorithm. In environments of moderate
complexity we obtained speedups of two orders of magnitude.
The approach presented here enables HR to work effectively even
when there are many mutually visible initial surfaces.
The hierarchy of clusters presented in this paper were fairly
straightforward modifications to traditional bounding volume hi-
erarchies. Our current research shows that it is beneficial to build
5D hierarchies in the spirit of [1], to bound direction of the patch
normals as well as position. This can be used to obtain tighter
bounds on the transfers since patch orientations are constrained.
In the implementation described here, two clusters with even one
pair of patches facing each other may be linked with a relatively
expensive ff-link. A 5D hierarchy seems to reduce this problem.
Although a lower bound of zero on energy transfers is always
valid, tighter lower bounds between two clusters would improve
overall performance of the algorithm. Unlike upper bounds, this
requires computing guaranteed bounds on visibility, a potentially
expensive operation. Currently, our implementation uses a sampling
approach to determine the upper bound on the transfer between
two patchs as well as the transfer between patches and clusters.
Although we have not noticed any serious problems as a result
of this approximation, analytic bounds on these transfers would
produce guaranteed bounds. Guaranteed bounds on transfers make
it possible to examine the global error in the solution. As mentioned
in [12] bounds on transfers between surfaces do not immediately
provide a bound on the total error in the solution.

Acknowledgments

We would like to thank Dani Lischinski for discussionson complexity
and for helpful comments on the paper. Also thanks go to Greg
Spencer for his software for handling high dynamic range images.
This work was supported by the NSF grant "Interactive Computer
Graphics Input and Display Techniques" (CCR-8617880), and by
the NSF/DARPA Science and Technology Center for Computer
Graphics and Scientific Visualization (ASC-8920219). The authors
gratefully acknowledge the generous equipment grant from
Hewlett-Packard Corporation.



--R

Fast ray tracing by ray classification.
A progressivemulti-pass method for global illumination
An efficient radiosity approach for realistic image synthesis.
Automatic creation of object hierarchies for ray tracing.
Modeling the interaction of light between diffuse surfaces.
The Rapid Evaluation of Potential Fields in Particle Systems.
A rapid hierarchical radiosity algorithm.
Grouping of patches in progressive radiosity.
Combining hierarchical radiosity and discontinuity meshing.

Geometric simplification for indirect illumination calculations.
An importance-driven radiosity algorithm
Global visibility for illumination computations.
--TR
Automatic creation of object hierarchies for ray tracing
Fast ray tracing by ray classification
A progressive multi-pass method for global illumination
A rapid hierarchical radiosity algorithm
An importance-driven radiosity algorithm
Combining hierarchical radiosity and discontinuity meshing
Global visibility algorithms for illumination computations

--CTR
Philipp Slusallek , Marc Stamminger , Wolfgang Heidrich , Jan-Christian Popp , Hans-Peter Seidel, Composite Lighting Simulations with Lighting Networks, IEEE Computer Graphics and Applications, v.18 n.2, p.22-31, March 1998
Simon Gibson , Roger J. Hubbold, A Perceptually-Driven Parallel Algorithm for Efficient Radiosity Simulation, IEEE Transactions on Visualization and Computer Graphics, v.6 n.3, p.220-235, July 2000
Ingo Wald , Carsten Benthin , Philipp Slusallek, Interactive global illumination in complex and highly occluded environments, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
Luc Renambot , Bruno Arnaldi , Thierry Priol , Xavier Pueyo, Towards efficient parallel radiosity for DSM-based parallel computers using virtual interfaces, Proceedings of the IEEE symposium on Parallel rendering, p.79-86, October 20-21, 1997, Phoenix, Arizona, United States
Fraois Sillion , George Drettakis, Feature-based control of visibility error: a multi-resolution clustering algorithm for global illumination, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.145-152, September 1995
Seth Teller , Celeste Fowler , Thomas Funkhouser , Pat Hanrahan, Partitioning and ordering large radiosity computations, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.443-450, July 1994
Bruce Walter , Sebastian Fernandez , Adam Arbree , Kavita Bala , Michael Donikian , Donald P. Greenberg, Lightcuts: a scalable approach to illumination, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
Thomas A. Funkhouser, Coarse-grained parallelism for hierarchical radiosity using group iterative methods, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.343-352, August 1996
Cline Loscos , George Drettakis , Luc Robert, Interactive Virtual Relighting of Real Scenes, IEEE Transactions on Visualization and Computer Graphics, v.6 n.4, p.289-305, October 2000
David Zareski , Bretton Wade , Philip Hubbard , Peter Shirley, Efficient parallel global illumination using density estimation, Proceedings of the IEEE symposium on Parallel rendering, p.47-54, October 30-31, 1995, Atlanta, Georgia, United States
Michael Garland , Andrew Willmott , Paul S. Heckbert, Hierarchical face clustering on polygonal surfaces, Proceedings of the 2001 symposium on Interactive 3D graphics, p.49-58, March 2001
L. Alonso , F. Cuny , S. Petit Jean , J.-C. Paul , S. Lazard , E. Wies, The virtual mesh: a geometric abstraction for efficiently computing radiosity, ACM Transactions on Graphics (TOG), v.20 n.3, p.169-201, July 2001
Tom Mertens , Jan Kautz , Philippe Bekaert , Hans-Peter Seidelz , Frank Van Reeth, Interactive rendering of translucent deformable objects, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
Ignacio Martn , Xavier Pueyo , Dani Tost, Frame-to-Frame Coherent Animation with Two-Pass Radiosity, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.70-84, January
Kirill Dmitriev , Thomas Annen , Grzegorz Krawczyk , Karol Myszkowski , Hans-Peter Seidel, A CAVE system for interactive modeling of global illumination in car interior, Proceedings of the ACM symposium on Virtual reality software and technology, November 10-12, 2004, Hong Kong
Grgory Lecot , Bruno Lvy , Laurent Alonso , Jean-Claude Paul, Master-element vector irradiance for large tessellated models, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand
Bruce Walter , Philip M. Hubbard , Peter Shirley , Donald P. Greenberg, Global illumination using local linear density estimation, ACM Transactions on Graphics (TOG), v.16 n.3, p.217-259, July 1997
Cyril Soler , F. X. Sillion, Texture-based visibility for efficient lighting simulation, ACM Transactions on Graphics (TOG), v.19 n.4, p.302-342, Oct. 2000
Xavier Granier , George Drettakis, A final reconstruction approach for a unified global illumination algorithm, ACM Transactions on Graphics (TOG), v.23 n.2, p.163-189, April 2004
Daniel Meneveaux , Kadi Bouatouch , Gilles Subrenat , Philippe Blasi, Efficient clustering and visibility calculation for global illumination, Proceedings of the 2nd international conference on Computer graphics, virtual Reality, visualisation and interaction in Africa, February 03-05, 2003, Cape Town, South Africa
Franois X. Sillion, A Unified Hierarchical Algorithm for Global Illumination with Scattering Volumes and Object Clusters, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.240-254, September 1995
Per H. Christensen , Dani Lischinski , Eric J. Stollnitz , David H. Salesin, Clustering for glossy global illumination, ACM Transactions on Graphics (TOG), v.16 n.1, p.3-33, Jan. 1997
Marco Pellegrini, Rendering equation revisited: how to avoid explicit visibility computations, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.725-733, January 17-19, 1999, Baltimore, Maryland, United States
Per H. Christensen , Eric J. Stollnitz , David H. Salesin , Tony D. DeRose, Global illumination of glossy environments using wavelets and importance, ACM Transactions on Graphics (TOG), v.15 n.1, p.37-71, Jan. 1996
Volevich , Karol Myszkowski , Andrei Khodulev , Edward A. Kopylov, Using the visual differences predictor to improve performance of progressive global illumination computation, ACM Transactions on Graphics (TOG), v.19 n.2, p.122-161, April 2000
Philipp Slusallek , Hans-Peter Seidel, Vision - An Architecture for Global Illumination Calculations, IEEE Transactions on Visualization and Computer Graphics, v.1 n.1, p.77-96, March 1995
Cyril Soler , Franois X. Sillion , Frdric Blaise , Philippe Dereffye, An efficient instantiation algorithm for simulating radiant energy transfer in plant models, ACM Transactions on Graphics (TOG), v.22 n.2, p.204-233, April
Donald P. Greenberg , Kenneth E. Torrance , Peter Shirley , James Arvo , Eric Lafortune , James A. Ferwerda , Bruce Walter , Ben Trumbore , Sumanta Pattanaik , Sing-Choong Foo, A framework for realistic image synthesis, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.477-494, August 1997
hierarchical radiosity;error bounds;clustering;global illumination