3

I cannot understand an algorithm which combines stratified sampling and importance sampling of Monte Carlo. It is introduced in Page 73 of a textbook "Advanced Global Illumination", 2nd edition, written by Philip Dutre, Philippe Bekaert and Kavita Bala. The text gives almost no explanation on the algorithm so I got stuck at the line $N_i=\lfloor Pn+u\rfloor-N_{sum}$. I tried my best but I think I'm at my wit's end to figure out how this line or the whole psudo-code works. I just don't have any understanding. I read the text again and again and stared at Fig 3.9 above the algorithm for a long time but could not find any clue. Could you please give me an explanation of this algorithm in a way a common human can follow? For your convenience, I copied this section as follows. I know there is another question thread but that question has not been answered and I think my post is more detailed so please do not merge mine to his.

Thanks a lot for your help.

enter image description here enter image description here

user5280911
  • 193
  • 1
  • 3
  • You can technically feed any pointset in the inverse transform mapping. As a special case this pointset may be produced by jittering the points if a regular grid, so that each sample is jittered within its cell. What they have done there is just mix up the two. I'd suggest keeping it modular. – lightxbulb Dec 27 '19 at 16:54

1 Answers1

1

It's difficult to parse, but here's my best understanding.

In this case the goal is determine number of $N_i$ out of $n$ samples to distribute to each strata with probability given by the discrete pdf in $\{p_0, ..., p_n\}$

The summation of $P$ += $p_i$ is computing the CDF for $i$.

I believe "sample the ith term $N_i$ times" means to take a jittered sample within that strata using new random variables.

Let's take a small example where we have the pdf with 4 elements. $$ PDF = \{0.2, 0.1, 0.6, 0.1\} $$

And it's corresponding cdf, each element corresponds to $P$ in the ith iteration in the pseudo code. $$ CDF = \{0.2, 0.3, 0.9, 1.0\} $$

Now given $\left \lfloor{P*n + u}\right \rfloor$ we can illustrate for a few example cases.

With $u = 0$ $$ \left \lfloor{P*n + u}\right \rfloor = \{0, 1, 3, 4\} $$ $$ N_i = {0, 1, 2, 1} $$

With $u = 0.5$ $$ \left \lfloor{P*n + u}\right \rfloor = \{1, 1, 4, 4\} $$ $$ N_i = {1, 0, 3, 0} $$

With $u = 0.99$ $$ \left \lfloor{P*n + u}\right \rfloor = \{1, 2, 4, 4\} $$ $$ N_i = {1, 1, 2, 0} $$

Notice how for example $N_3$ corresponds to a higher number of samples. When we now sample the 3rd element $N_3$ times we are weighting that strata in proportion to its pdf.

Also, I don't see any reason that the sample count has to be the same $n$ as the # of discrete elements in the pdf.

Calvin
  • 506
  • 2
  • 7