Graphics Reference
In-Depth Information
Sample points
Center of
cluster
R
n
P
R
n
R
1
P
R
3
U
1
U
3
U
n
Center of cl
uster
R
3
Sample points
U
2
R
2
Figure 7.3
Dividing sample points into clusters
via the
k
-means algorithm.
Figure 7.4
Updating the cluster center points
for the next iteration of the
k
-means
algorithm.
Applying the
k
-means algorithm to partitioning the sphere based on a set of
point sources has a major drawback. The partitioning is done by distance from
the point sources—the intensity of the sources is not considered. Consequently,
the regions for the most important light sources are treated the same as the re-
gions for sources of lesser importance. If the point sources have roughly the same
intensity, this is not a problem. However, cinema lighting (real and virtual) is
typically done with different kinds of lights:
key lights
areusedfortheprimary
illumination of scene elements;
fill lights
are added to reduce shadows and change
the contrast. Fill lights normally have lower intensity than key lights, and there
are typically many more of them. An environment constructed using the
k
-means
algorithm is not likely to provide a good representation of key and fill lights.
7.2.3 Sampling an Environment Map
When an HDR environment map is used for scene illumination, it often contains
all the illumination sources, including the lights. Sampling via ray tracing over
the hemisphere therefore suffers from the same problems described in Chapter 2:
a large number of samples is necessary to ensure that enough randomly chosen
rays hit the light sources and other bright spots. The problem is more general
in environment maps, and also more complicated, because the bright parts of the
map are not necessarily known in advance. The church image shown in Figure 6.4
is a good example. In that environment, most of the illumination comes from the
windows. In this particular environment, the windows are fairly broad, but other
environments might have smaller concentrated sources that have little chance of
being hit by a random sample. Some way of ensuring that bright parts of a high
dynamic range environment map are properly sampled is therefore necessary.
The
k
-means algorithm provides on way of doing this. Each pixel in an envi-
ronment map can be regarded as a point source, i.e., a point sample on the sphere.
The
k
-means algorithm can be applied to cluster these samples into a collection of
fewer representative samples. For example, a typical HDR environment map has
