8

Why is it that it's so common to use monte carlo randomized sample locations, instead of uniform sampling?

I'm assuming that taking randomized samples gives some benefit but I don't know what they could be.

Is anyone able to explain the advantage of randomized sample locations over uniform sample locations?

Alan Wolfe
  • 7,711
  • 3
  • 29
  • 72
  • Usually to avoid getting uniform patterns everywhere, if you are using equally spaced uniform samples then you will get moire pattern effects as some pixels hit and miss features at a regular interval. Ideally some kind of importance sampling should be used to bias sampling directions. – PaulHK Aug 19 '16 at 09:33
  • I recently read that both stratified sampling and low discrepency sequences (like halton, sobol, etc) are a middle ground between random sampling (which creates noise) and uniform sampling (which creates aliasing). – Alan Wolfe Sep 06 '16 at 21:04

2 Answers2

7

Sample locations with a uniform pattern will create aliasing in the output, whenever there are geometric features of size comparable to or smaller than the sampling grid. That's the reason why "jaggies" exist: because images are made of a uniform square pixel grid, and when you render (for example) an angled line without antialiasing, it crosses rows/columns of pixels at regular intervals, creating a regular pattern of stairstep artifacts in the resulting image.

Supersampling at a finer uniform grid will improve things, but the image will still have similar artifacts—just less badly. You can see this with MSAA, as in this comparison image from an NVIDIA presentation on temporal antialiasing:

comparison of no AA, uniform-grid MSAA, and temporal AA

The 8x MSAA image (which is not quite a grid but still has a repeating pattern) still plainly has jaggies in it, although they're antialiased jaggies. Compare to the TXAA result, which both has a higher effective sample count (due to temporal reuse) and uses a Gaussian rather than box filter for accumulating the samples.

On the other hand, random sampling produces noise instead of aliasing. There is no pattern to the sample locations, so no pattern to the resulting errors. Both aliasing and noise are errors due to not having enough samples to form a clean image, but arguably noise is the less visually-objectionable artifact.

On the other other hand, perfectly random sampling (in the sense of i.i.d. random variables) tends to exhibit a certain level of clumping. Purely by chance, some areas in the domain will have denser-than-average clumps of samples, and other areas will be lacking in samples; those areas will be, respectively, over-represented and under-represented in the resulting estimate.

The convergence rate of the Monte Carlo process can often by improved by using things like stratified sampling, low-discrepancy sequences, or blue noise. These are all strategies to generate "de-clumped" samples that are spaced out a bit more evenly than i.i.d. samples, but without creating any regular patterns that might lead to aliasing.

Nathan Reed
  • 24,302
  • 2
  • 63
  • 103
6

Monte Carlo methods rely on the law of large numbers, which states that the average of a random event repeated a large number of times converges toward the expected value (if you flip a coin a gazillion times, on average you will obtain each side half the time). Monte Carlo integration uses that law to evaluate an integral by averaging a large number of random samples.

Using a uniform distribution would break the algorithm because the law it is based upon wouldn't apply anymore.

Julien Guertault
  • 4,340
  • 2
  • 21
  • 47
  • Yes but mostly it can be summed as this for a unknown problem, ramdom is the best strategy. since contribution is unknown... – joojaa Aug 19 '16 at 13:10
  • @joojaa: oh, I realize you and I have read the question differently. Yes, Monte Carlo is a strategy that works when the analytical solution is unknown (although a math person would probably have a much more precise way of putting it). – Julien Guertault Aug 19 '16 at 14:34
  • Said differently: even if the solution is unknown, Monte Carlo is proven to converge toward it. – Julien Guertault Aug 19 '16 at 14:35