PowerPoint Presentation
15. Monte Carlo Sampling
Dr. Hamish Carr
COMP 5812M: Foundations of Modelling & Rendering
COMP3811: Computer Graphics 2013-2014
Random Generators
Random numbers are fair and unpredictable
Computer provides pseudo-random number
Functions in
random() returns 0 .. RAND_MAX
divide by RAND_MAX to get [0,1]
then scale & translate
COMP 5812M: Foundations of Modelling & Rendering
COMP3811: Computer Graphics 2013-2014
Example
// generates a random value
GLfloat RandomRange(GLfloat min, GLfloat max)
{ // RandomRange()
// compute range for scaling
GLfloat range = max – min;
// generate pseudorandom number in [0,RAND_MAX]
GLfloat randomNumber = (GLfloat) random();
// convert to [0,1]
randomNumber /= (GLfloat) RAND_MAX;
// scale
randomNumber *= range;
// translate
randomNumber + min;
// return result
return randomNumber;
} // RandomRange()
COMP 5812M: Foundations of Modelling & Rendering
Expected Value
Given a “random variable” X
What value do we expect?
Multiply probability of value by value
Then sum over all values
Also known as the mean or the average
COMP 5812M: Foundations of Modelling & Rendering
Variance
How tightly the value clusters
Take the difference from the mean
Square it & add them together
It’s square root is the standard deviation
COMP 5812M: Foundations of Modelling & Rendering
Sampled Integration
Instead of regular intervals for integration
Use random samples
The variance of the estimate is better
I.e. it converges faster
Regular Intervals
Uniform Sampling
COMP 5812M: Foundations of Modelling & Rendering
Importance Sampling
Large values dominate the variance
i.e. they are more important
So choose them more frequently
And weight samples for right result
Uniform Sampling
Importance Sampling
COMP 5812M: Foundations of Modelling & Rendering
Moving to 3D
This is easy for functions
But gets harder for higher dimensions
So let’s look at another aspect of this:
Monte Carlo Sampling
COMP 5812M: Foundations of Modelling & Rendering
COMP3811: Computer Graphics 2013-2014
Random (x,y) points
Generate random x, random y
COMP 5812M: Foundations of Modelling & Rendering
COMP3811: Computer Graphics 2013-2014
Directional Bias
Directions not equally likely
Diagonals more likely
COMP 5812M: Foundations of Modelling & Rendering
COMP3811: Computer Graphics 2013-2014
Circular Distribution
All directions equally probable
Could use random angle theta
Breaks down in 3D (texture distortion)
COMP 5812M: Foundations of Modelling & Rendering
COMP3811: Computer Graphics 2013-2014
Monte Carlo Method
Generate points in a square
Discard points outside the circle
COMP 5812M: Foundations of Modelling & Rendering
Monte Carlo Code
Vector2D 2DMonteCarloVector()
{ // 2DMonteCarloVector()
// loop until we get a valid one
while (true)
{ // while loop
// randomise x and y
Vector2D aVector;
aVector.x = RandomRange(-1.0, 1.0);
aVector.y = RandomRange(-1.0, 1.0);
// compute length & compare
float length = aVector.Length();
// return if it’s good
if (length <= 1.0)
return aPoint;
} // while loop
// this should never be called - but it makes the compiler happy
return Vector2D(0.0, 0.0);
} // 2DMonteCarloVector()
COMP 5812M: Foundations of Modelling & Rendering
Avoid taking the square root
Discard points inside as well
avoids degenerate cases
Normalize vectors to unit
Perfect for raytracing
Unless you want a vector not a direction
COMP3811: Computer Graphics 2013-2014
Refinements
COMP 5812M: Foundations of Modelling & Rendering
3D Monte Carlo Code
Vector3D 3DMonteCarloDirection()
{ // 3DMonteCarloDirection()
// loop until we get a valid one
while (true)
{ // while loop
// randomise x, y, z
Vector3D aVector;
aVector.x = RandomRange(-1.0, 1.0);
aVector.y = RandomRange(-1.0, 1.0);
aVector.z = RandomRange(-1.0, 1.0);
// compute length & compare
float length = aVector.Length();
// if the length is bad, do another loop
if ((length > 1.0) || (length < 0.1))
// otherwise, return the normalised version
return aVector.UnitNormal();
} // while loop
// this should never be called - but it makes the compiler happy
return Vector3D(0.0, 0.0, 0.0);
} // 3DMonteCarloDirection()
COMP 5812M: Foundations of Modelling & Rendering
Downsides
We’re wasting samples
On the region outside the circle
We want an efficient solution
That doesn’t waste random numbers
We re-parameterise the computation
COMP 5812M: Foundations of Modelling & Rendering
Weighting Factor
This turns out to be equal-area mapping
An idea long understood in cartography
Weight the sample by it’s local distortion
Known as the Jacobian
Related to the slope
COMP 5812M: Foundations of Modelling & Rendering
Random Hemisphere
We weight the probability by this area
It turns out to be a sine function
And there's a short cut
COMP 5812M: Foundations of Modelling & Rendering
Importance Sampling
Large values have more influence on variance
So we sample them more frequently
Increases contribution to the integral
So we counterweight their contribution
Net result: same mean, smaller variance
f(x) is a function on [a,b]
X is a random variable with distribution g
gives the expected value
COMP 5812M: Foundations of Modelling & Rendering
In practice
Reflection involves estimating this integral:
We know , but not L
However, if is small, the contribution is too
Better, it's proportional to:
The cosine weighted BRDF
COMP 5812M: Foundations of Modelling & Rendering
Mixed Probabilities
In practice, we need impulse or diffuse
We divide our reflections between the two
e.g. 60% chance of an impulse
40% chance of diffuse
COMP 5812M: Foundations of Modelling & Rendering
Summary
Monte Carlo sampling uses random numbers
Cheaper and faster than uniform sampling
Especially if we weight by importance
And this means more complex maths
Soluble for simple spherical distribution
Other cases: generate a random vector
Then test BRDF to see if it's extinguished
COMP 5812M: Foundations of Modelling & Rendering