Image-Based Lighting - The Magic of Computer Graphics - page 186

7.2.2 Clustering: Simplifying Environment Maps

Rendering using an environment map can produce an accurate GI rendering of a
scene. However, digital artists often find it difficult to construct environment maps
that correspond to a preconceived notion of the illumination in a scene. Artists are
more accustomed to lighting a scene with point sources; arranging the positions
and brightness of point sources is more intuitive. While a scene can be rendered
directly with such point sources, converting them to an environment map results
in smoother illumination. An environment map so constructed consists of disjoint
regions, each of which contains a single point source. The light from the point
source is spread out over the region so that the sum of the radiance values over all
the pixels matches the intensity of the source.
This process of partitioning the sphere into regions has other applications.
For example, it can be employed to simplify an environment with too many point
sources. The problem in this case is to construct regions that correspond to the
average illumination produced by a collection of point sources, that presumably
have similar intensity. The illumination in the region is an average of the sources
it contains, or perhaps is that of one representative source in the region. This
process is known as clustering . The illumination produced by a cluster region
can be regarded as that of a single point source at the center of the region. Each
pixel of a digitized environment map, such as one obtained using the light probe
method described, can be regarded as a point source. Clustering can be applied
to reduce all these pixels to a few representative point sources, or samples as they
maybecalledinthiscontext.
Clustering points on the sphere can be accomplished using the k -means algo-
rithm. In this algorithm, the number of clusters is determined at the outset. If
there are to be N cluster regions, a preliminary set of regions is created based on
N randomly chosen samples U 1

, ,...,

U N . The regions form a partition of the
sphere known as a Voronoi diagram : all points on the sphere inside the region
containing U i are closer to U i than any other of the randomly chosen points. Fig-
ure 7.3 shows part of three such regions for sample points labeled U 1 , U 2 ,and U 3 .
Note that the regions are bounded by line segments midway between neighbor-
ing sample points. Each preliminary region thus contains one of the N randomly
chosen sample points as well as any number of remaining points. The next step
is to update the regions to better match the points as a whole. The centroid (aver-
age position) of all the points contained in each region is computed ( Figure 7.4 ) ,
and the regions are reconstructed using the centroids instead of the original N
sample points. This step is repeated until the regions converge. The name “ k -
means” refers to the notion that a collection of points is represented by k averages
(means).

U 2