i
i
i
i
i
i
i
i
332 14. Sampling
Again, a nice thing about this is that a set of jittered points on the unit square can
be easily transformed to a set of jittered points on the hemisphere with the desired
distribution. Note that if n is set to 1, we have a diffuse distribution, as is often
needed.
Often we must map the point on the sphere into an appropriate direction with
respect to a uvw basis. To do this, we can first convert the angles to a unit vectora:
a =(cosφ sin θ, sin φ sin θ, cos θ)
As an efficiency improvement, we can avoid taking trigonometric functions of
inverse trigonometric functions (e.g., cos (arccos θ)). For example, when n =1
(a diffuse distribution), the vector a simplifies to
a =
cos (2πξ
1
)
ξ
2
, sin (2πξ
1
)
ξ
2
,
1 − ξ
2
14.4.2 Rejection
A rejection method chooses points according to some simple distribution and re-
jects some of them that are in a more complex distribution. There are several
scenarios where rejection is used, and we show some of these by example.
Suppose we want uniform random points within the unit circle. We can first
choose uniform random points (x, y) ∈ [−1, 1]
2
and reject those outside the cir-
cle. If the function r() returns a canonical random number, then the procedure
is:
done = false
while (not done) do
x = −1+2r()
y = −1+2r()
if (x
2
+ y
2
< 1) then
done = true
If we want a random number x ∼ p and we know that p :[a, b] → R,and
that for all x, p(x) <m, then we can generate random points in the rectangle
[a, b] × [0,m] and take those where y<p(x):
done = false
while (not done) do
x = a + r()(b −a)
y = r()m
if (y<p(x)) then
done = true
i
i
i
i
i
i
i
i
14.4. Choosing Random Points 333
This same idea can be applied to take random points on the surface of a sphere.
To pick a random unit vector with uniform directional distribution, we first pick a
random point in the unit sphere and then treat that point as a direction vector by
taking the unit vector in the same direction:
done = false
while (not done) do
x = −1+2r()
y = −1+2r()
z = −1+2r()
if ((l =
x
2
+ y
2
+ z
2
) < 1) then
done = true
x = x/l
y = y/l
z = z/l
Although the rejection method is usually simple to code, it is rarely compatible
with stratification. For this reason, it tends to converge more slowly and should
thus be used mainly for debugging, or in particularly difficult circumstances.
14.4.3 Metropolis
The Metropolis method uses random mutations to produce a set of samples with
a desired density. This concept is used extensively in the Metropolis Light Trans-
port algorithm referenced in the chapter notes. Suppose we have a random point
x
0
in a domain S. Further, suppose for any point x, we have a way to generate
random y ∼ p
x
. We use the marginal notation p
x
(y) ≡ p(x → y) to denote this
density function. Now, suppose we let x
1
be a random point in S selected with
underlying density p(x
0
→ x
1
). We generate x
2
with density p(x
1
→ x
0
) and so
on. In the limit, where we generate an infinite number of samples, it can be proved
that the samples will have some underlying density determined by p regardless of
the initial point x
0
.
Now, supposewe want to choose p such that the underlying density of samples
to which we converge is proportional to a function f(x) where f is a non-negative
function with domain S. Further, suppose we can evaluate f, but we have little
or no additional knowledge about its properties (such functions are common in
graphics). Also, suppose we have the ability to make “transitions” from x
i
to
x
i+1
with underlying density function t(x
i
→ x
i+1
).Toaddflexibility, further
suppose we add the potentially non-zero probability that x
i
transitions to itself,
i
i
i
i
i
i
i
i
334 14. Sampling
i.e., x
i+1
= x
i
. We phrase this as generating a potential candidate y ∼ t(x
i
→ y)
and “accepting” this candidate (i.e., x
i+1
= y) with probability a(x
i
→ y) and re-
jecting it (i.e., x
i+1
= x
i
) with probability 1−a(x
i
→ y). Note that the sequence
x
0
,x
1
,x
2
,...will be a random set, but there will be some correlationamong sam-
ples. They will still be suitable for Monte Carlo integration or density estimation,
but analyzing the variance of those estimates is much more challenging.
Now, suppose we are given a transition function t(x → y) and a function f(x)
of which we want to mimic the distribution, can we use a(y → x) such that the
points are distributed in the shape of f? Or more precisely,
{x
0
,x
1
,x
2
,...}∼
f
#
s
f
.
It turns out this can be forced by making sure the x
i
are stationary in some strong
sense. If you visualize a huge collection of sample points x, you want the “flow”
between two points to be the same in each direction. If we assume the density of
points near x and y are proportional to f(x) and f(y), respectively, then the flow
in the two directions should be the same:
flow(x → y)=kf(x)t(x → y)a(x → y),
flow(y → x)=kf(y)t(y → x)a(y → x),
where k is some positive constant. Setting these two flows constant gives a con-
straint on a:
a(y → x)
a(x → y)
=
f(x)t(x → y)
f(y)t(y → x)
.
Thus, if either a(y → x) or a(x → y) is known, so is the other. Making them
larger improves the chance of acceptance, so the usual technique is to set the
larger of the two to 1.
Adifficulty in using the Metropolis sample generation technique is that it is
hard to estimate how many points are needed before the set of points is “good.”
Things are accelerated if the first n points are discarded, although choosing n
wisely is non-trivial.
14.4.4 Example: Choosing Random Lines in the Square
As an example of the full process of designing a sampling strategy, consider the
problem of finding random lines that intersect the unit square [0, 1]
2
.Wewant
this process to be fair; that is, we would like the lines to be uniformly distributed
within the square. Intuitively, we can see that there is some subtlety to this prob-
lem; there are “more” lines at an oblique angle than in horizontal or vertical di-
rections. This is because the cross section of the square is not uniform.
i
i
i
i
i
i
i
i
14.4. Choosing Random Points 335
Our first goal is to find a function-inversion method, if one exists, and then to
fall back on rejection or Metropolis if that fails. This is because we would like
to have stratified samples in line space. We try using normal coordinates first,
because the problem of choosing random lines in the square is just the problem
of finding uniform random points in whatever part of (r, θ) space corresponds to
lines in the square.
Consider the region where −π/2 <θ<0. What values of r correspond to
lines that hit the square? For those angles, r<cos θ are all the lines that hit
the square as shown in Figure 14.8. Similar reasoning in the other four quadrants
finds the region in (r, θ) space that must be sampled, as shown in Figure 14.9.
The equation of the boundary of that region r
max
(θ)is
Figure 14.8. The largest
distance r corresponds to a
line hitting the square for
θ ∈ [ − π/2, 0]. Because
the square has sidelength
one, r =cosθ.
r
max
(θ)=
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
0 if θ ∈ [−π, −
π
2
],
cos θ if θ ∈ [−
π
2
, 0],
√
2cos(θ −
π
4
) if θ ∈ [0,
π
2
],
sin θ if θ ∈ [
π
2
,π].
Because the region under r
max
(θ) is a simple function bounded below by r =0,
we can sample it by first choosing θ according to the density function:
p(θ)=
r
max
(θ)
#
π
−π
r
max
(θ)dθ
.
The denominator here is 4. Now, we can compute the cumulative probability
distribution function:
P (θ)=
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
0 if θ ∈ [−π, −
π
2
],
(1 + sin θ)/4 if θ ∈ [−
π
2
, 0],
(1 +
√
2
2
sin(θ −
π
4
))/2 if θ ∈ [0,
π
2
],
(3 − cos θ)/4 if θ ∈ [
π
2
,π].
Figure 14.9. The maximum radius for lines hitting the unit square [0,1]
2
as a function of θ.
i
i
i
i
i
i
i
i
336 14. Sampling
We can invert this by manipulating ξ
1
= P (θ) into the form θ = g(ξ
1
).This
yields
θ =
⎧
⎪
⎨
⎪
⎩
arcsin(4ξ
1
− 1) if ξ
1
<
1
4
,
arcsin(
√
2
2
(2ξ
1
− 1)) +
π
4
if ξ
1
∈ [
1
4
,
3
4
],
arccos(3 − 4ξ
1
) if ξ
1
>
3
4
.
Once we have θ,thenr is simply:
r = ξ
2
r
max
(θ).
As discussed earlier, there are many parameterizations of the line, and each has an
associated “fair” measure. We can generate random lines in any of these spaces
as well. For example, in slope-intercept space, the region that hits the square is
shown in Figure 14.10. By similar reasoning to the normal space, the density
function for the slope is
p(m)=
1+|m|
4
with respect to the differential measure
dμ =
dm
(1 + m
2
)
3
2
.
Figure 14.10. The region of (
m,b
) space that contains lines that intersect the unit square
[0,1]
2
.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.