Fundamentals of Computer Graphics, 3rd Edition

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,