i
i
i
i
i
i
i
i
14
Sampling
Many applications in graphics require “fair” sampling of unusual spaces, such as
the space of all possible lines. For example, we might need to generate random
edges within a pixel, or random sample points on a pixel that vary in density
according to some density function. This chapter provides the machinery for such
probability operations. These techniques will also prove useful for numerically
evaluating complicated integrals using Monte Carlo integration, also covered in
this chapter.
14.1 Integration
Although the words “integral” and “measure” often seem intimidating, they relate
to some of the most intuitive concepts found in mathematics, and they should not
be feared. For our very non-rigorous purposes, a measure is just a function that
maps subsets to R
+
in a manner consistent with our intuitive notions of length,
area, and volume. For example,on the 2D real plane R
2
, we have the area measure
A which assigns a value to a set of points in the plane. Note that A is just a
function that takes pieces of the plane and returns area. This means the domain of
A is all possible subsets of R
2
, which we denote as the power set P(R
2
). Thus,
we can characterize A in arrow notation:
A : P(R
2
) → R
+
.
317
i
i
i
i
i
i
i
i
318 14. Sampling
An example of applying the area measure shows that the area of the square with
side length one is one:
A([a, a +1]× [b, b +1])=1,
where (a, b) is just the lower left-hand corner of the square. Note that a single
point such as (3, 7) is a valid subset of R
2
and has zero area: A((3, 7)) = 0.The
same is true of the set of points S on the x-axis, S =(x, y) such that (x, y) ∈ R
2
and y =0, i.e., A(S)=0. Such sets are called zero measure sets.
To be considered a measure, a functionhas to obey certain area-like properties.
For example, we have a function μ : P(S) → R
+
.Forμ to be a measure, the
following conditions must be true:
1. The measure of the empty set is zero: μ(∅ )=0,
2. The measure of two distinct sets together is the sum of their measure alone.
This rule with possible intersections is
μ(A ∪ B)=μ(A)+μ(B) − μ(A ∩ B),
where ∪ is the set union operator and ∩ is the set intersection operator.
When we actually compute measures, we usually use integration. We can think
of integration as really just notation:
A(S) ≡
x∈S
dA(x).
You can informally read the right-hand side as “take all points x in the region S,
and sum their associated differential areas.” The integral is often written other
ways including
S
dA,
x
∈S
dx,
x
∈S
dA
x
,
x
dx.
All of the above formulas represent “the area of region S.” We will stick with the
first one we used, because it is so verbose it avoids ambiguity. To evaluate such
integrals analytically, we usually need to lay down some coordinate system and
use our bag of calculus tricks to solve the equations. But have no fear if those
skills have faded, as we usually have to numerically approximate integrals, and
that requires only a few simple techniques which are covered later in this chapter.
Given a measure on a set S, we can always create a new measure by weighting
with a non-negative function w : S → R
+
. This is best expressed in integral
i
i
i
i
i
i
i
i
14.1. Integration 319
notation. For example, we can start with the example of the simple area measure
on [0, 1]
2
:
x
∈[0,1]
2
dA(x),
and we can use a “radially weighted” measure by inserting a weighting function
of radius squared:
x
∈[0,1]
2
x
2
dA(x).
To evaluate this analytically, we can expand using a Cartesian coordinate system
with dA ≡ dx dy:
x
∈[0,1]
2
x
2
dA(x)=
1
x=0
1
y=0
(x
2
+ y
2
) dx dy.
The key thing here is that if you think of the x
2
term as married to the dA term,
and that these together form a new measure, we can call that measure ν.This
would allow us to write ν(S) instead of the whole integral. If this strikes you
as just a bunch of notation and bookkeeping, you are right. But it does allow us
to write down equations that are either compact or expanded depending on our
preference.
14.1.1 Measures and Averages
Measures really start paying off when taking averages of a function. You can
only take an average with respect to a particular measure, and you would like to
select a measure that is “natural” for the application or domain. Once a measure
is chosen, the average of a function f over a region S with respect to measure μ is
average(f) ≡
#
x∈S
f(x) dμ(x)
#
x∈S
dμ(x)
.
For example, the average of the function f(x, y)=x
2
over [0, 2]
2
with respect to
theareameasureis
average(f) ≡
#
2
x=0
#
2
y=0
x
2
dx dy
#
2
x=0
#
2
y=0
dx dy
=
4
3
.
This machinery helps solve seemingly hard problems where choosing the measure
is the tricky part. Such problems often arise in integral geometry,afield that
studies measures on geometric entities, such as lines and planes. For example,
i
i
i
i
i
i
i
i
320 14. Sampling
one might want to know the average length of a line through [0, 1]
2
. That is, by
definition,
average(length) =
#
lines L through [0, 1]
2
length(L)dμ(L)
#
lines L through [0, 1]
2
dμ(L)
.
All that is left, once we know that, is choosing the appropriate μ for the applica-
tion. This is dealt with for lines in the next section.
14.1.2 Example: Measures on the Lines in the 2D Plane
What measure μ is “natural”?
If you parameterize the lines as y = mx + b, you might think of a given line
as a point (m, b) in “slope-intercept” space. An easy measure to use would be
dm db, but this would not be a “good” measure in that not all equal size “bundles”
of lines would have the same measure. More precisely, the measure would not be
Figure 14.1. These
two bundles of lines should
have the same measure.
They have different inter-
section lengths with the
y
-axis so using
db
would be
a poor choice for a differen-
tial measure.
invariant with respect to change of coordinate system. For example, if you took
all lines through the square [0, 1]
2
, the measure of lines through it would not be
the same as the measure through a unit square rotated forty-five degrees. What
we would really like is a “fair” measure that does not change with rotation or
translation of a set of lines. This idea is illustrated in Figures 14.1 and 14.2.
To develop a natural measure on the lines, we should first start thinking of
them as points in a dual space. This is a simple concept: the line y = mx + b
can be specified as the point (m, b) in a slope-intercept space. This concept is
illustrated in Figure 14.3. It is more straightforward to develop a measure in
(φ, b) space. In that space b is the y-intercept, while φ is the angle the line makes
with the x-axis, as shown in Figure 14.4. Here, the differential measure dφ db
almost works, but it would not be fair due to the effect shown in Figure 14.1. To
Figure 14.2. These
two bundles of lines should
have the same measure.
Since they have different
values for change in slope,
using
dm
would be a poor
choice for a differential
measure.
account for the larger span b that a constant width bundle of lines makes, we must
add a cosine factor:
dμ =cosφdφdb.
It can be shown that this measure, up to a constant, is the only one that is invariant
with respect to rotation and translation.
This measure can be converted into an appropriate measure for other param-
eterizations of the line. For example, the appropriate measure for (m, b) space
is
dμ =
dm db
(1 + m
2
)
3
2
.
i
i
i
i
i
i
i
i
14.1. Integration 321
For the space of lines parameterized in (u, v) space,
ux + vy +1=0,
the appropriate measure is
dμ =
du dv
(u
2
+ v
2
)
3
2
.
For lines parameterized in terms of (a, b),thex-intercept and y-intercept, the
measure is
Figure 14.3. The set of
points on the line
y=mx +
b
in (
x, y
) space can also
be represented by a sin-
gle point in (
m, b
) space so
the top line and the bottom
point represent the same
geometric entity: a 2D line.
dμ =
ab da db
(a
2
+ b
2
)
3
2
.
Note that any of those spaces are equally valid ways to specify lines, and which is
best depends upon the circumstances. However, one might wonder whether there
exists a coordinate system where the measure of a set of lines is just an area in the
dual space. In fact, there is such a coordinate system, and it is delightfully simple;
it is the normal coordinates which specify a line in terms of the normal distance
from the origin to the line, and the angle the normal of the line makes with respect
to the x-axis (Figure 14.5). The implicit equation for such lines is
x cos θ + y sin θ − p =0.
And, indeed, the measure in that space is
x
y
φ
Figure 14.4. In angle-
intercept space we param-
eterize the line by angle
φ ∈ [−π/2,π/2) rather
than slope.
dμ = dp dθ.
We shall use these measures to choose fair random lines in a later section.
Figure 14.5. The normal
coordinates of a line use
the normal distance to the
origin and an angle to spec-
ify a line.
14.1.3 Example: Measure of Lines in 3D
In 3D there are many ways to parameterize lines. Perhaps, the simplest way is
to use their intersection with a particular plane along with some specification of
their orientation. For example, we could chart the intersection with the xy plane
along with the spherical coordinates of its orientation. Thus, each line would be
specified as a (x, y, θ, φ) quadruple. This shows that lines in 3D are 4D entities,
i.e., they can be described as points in a 4D space.
The differential measure of a line should not vary with (x, y), but bundles of
lines with equal cross section should have equal measure. Thus, a fair differential
measure is
dμ = dx dy sin θdθdφ.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.