Importance sampling and example

December 27, 2013 Leave a comment

1. Importance sampling idea

We have random variable $X_{1}$ , it has pdf (probability density function) p(x),

we have known
$E\left ( f\left ( X_{1} \right ) \right )= \int f\left ( x \right )p\left ( x \right )dx$

And according Monte Carlo estimator, if we want evaluate function f(x) by samples from p(x), we got
$E\left ( f\left ( X_{1} \right ) \right ) \approx \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right )$ where $x_{i}$ is sample from $X_{1}$

Let’s say we want( or can only) to sample from another distribution function q(x), but we still want to get the value $E\left ( f\left ( X_{1} \right ) \right )$ by Monte Carlo method, what we should do?

For clear, we use another random variable $X_{2}$ , its pdf q(x)

A little trick
$E\left ( f\left ( X_{1} \right ) \right )= \int f\left ( x \right )p\left ( x \right )dx=\int f\left ( x \right )\frac{p\left ( x \right )}{q\left ( x \right )}q\left ( x \right )dx$

it just looks like we want evaluate function $f\left ( x \right )\frac{p\left ( x \right )}{q\left ( x \right )}$ by samples from q(x), using the new random variable $X_{2}$ , we have

$\int f\left ( x \right )\frac{p\left ( x \right )}{q\left ( x \right )}q\left ( x \right )dx = E\left ( f\left ( X_{2} \right )\frac{p\left ( X_{2} \right )}{q\left ( X_{2} \right )} \right )$

According Monte Carlo like above, we should have
$E\left ( f\left ( X_{2} \right )\frac{p\left ( X_{2} \right )}{q\left ( X_{2} \right )} \right ) \approx \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right )\frac{p\left ( x_{i} \right )}{q\left ( x_{i} \right )}$

so we have
$E\left ( f\left ( X_{1} \right ) \right ) \approx \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right )\frac{p\left ( x_{i} \right )}{q\left ( x_{i} \right )}$

where $x_{i}$ is sample from $X_{2}$

this is what importantce sampling does, it uses samples from another distribution funtion, but still evaluate the old function for old random variable.

2. why Importance sampling can do better

let’s caculate variance on

$\sigma ^2 \left ( \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right ) \right ) = \frac{1}{n^2} \sigma ^2 \left ( \sum_{1}^{n}f\left ( x_{i} \right ) \right ) = \frac{1}{n} \sigma ^2 \left ( f\left ( x \right ) \right )$

$\sigma ^2 \left ( \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right )\frac{p\left ( x_{i} \right )}{q\left ( x \right )} \right ) = \frac{1}{n} \sigma ^2 \left ( f\left ( x \right ) \frac{p\left ( x \right )}{q\left ( x \right )} \right )$

so it we select q(x) smartly, we can get a much smaller $\sigma^2$

Filed under Tech Log

A straight forward way to understand VSM

January 22, 2012 Leave a comment

Why I want to re-understand VSM

In the original VSM paper，William and Andrew derived the MAGIC result from probability theory:

$Pshadow = \frac{\sigma ^{2} }{\sigma ^{2}+d^{2}}$

Note: $\sigma ^{2}= interp(z^{2})-interp(z)^{2}$

Note:

means the shadow map depth or shadow caster depth in shadow map
means the interpolated( filtered) value in shadow map
means the interpolated(filtered) value in shadow map
D means the shadow receiver’s depth)

The derivation looks very beautiful, but not so easy to understand , especially the idea to treat z as a random variable, so here I’ll try to explain it by middle school math, then we can kill the uncomfortable MAGIC feeling.

Analysis

Firstly, let’s back to the problem why VSM had been invented : Soft Shadow.
In the real word，soft shadow are generated with a physic explanation（eg area light），
but visually, Soft shadow just means a smooth transition between shadowed area and unshadowed area.
so there are many methods to fake it in computer graphics, VSM is just one of them ( note: even with beautiful math, VSM is not a physic correct algorithm at all).

In the above graph, we have 2 neighborhood texels in shadow map corresponding to 2 light rays, their shadow depth value are Z1 and Z2,.
According shadow map algorithm, we can know pixel A is in shadow and pixel B is lit, what we care about is the area between A and B,

If applying regular shadow test, a sudden shadow density changing must happen at somewhere between A and B. Even we can use bilinear filter to fetch shadow, the smooth input value doesn’t generate a smooth output value because shadow testing result is a binary value. That is why we said shadow map is not filterable.

Let’s see what will happen if we apply the MAGIC shadow testing formula from VSM.

First, let’s introduce a interpolating variable t, t will be changing linearly (0-1) from pixel A to pixel B.
Then with linear filtering, between A and B, we can write:
$interp(z^2)= Z_{1}^{2}\times (t-1) + Z_{2}^{2} \times t$

$interp(z)= Z_{1}\times (t-1) + Z_{2} \times t$

Then
$\sigma ^{2}= interp(z^{2})-interp(z)^2 = (Z_{2}-Z_{1})^{2} \times (t^{2}-t)$

$d^2 = (D-interp(z))^{2}$

$PShadow = \frac{\sigma^{2}}{\sigma^{2}+d^2} = \frac{1}{1+\frac{d^2}{\sigma^{2}}} = \frac{1}{1+\frac{(slop -t)^{2}}{t-t^{2}}}$

here, we define:

$slop = \frac{D-Z_1}{Z_2-Z1}$

Looks still mess, right?

Let’s see 2 special cases :

Special case 1: Perpendicular Reciever:

when receiver surface perpendicular to light direction (see reciever Rp)

For this scenario , we can easily know $D\equiv Z_2$ ( between t=0 and t=1)
So $slop = \frac{Z2-Z1}{Z2-Z1} = 1$
Then final result:

$PShadow_{perpendicular} = \frac{1}{1+\frac{(1-t)^2}{t-t^2}}=t$

So for this case, the shadow result will follow the most simple smooth transition when t change from 0 to 1 : Linear transition.

Special case 2: Reciever on interp(z):

When Shadow Reciever are on interp(z) ( see the red dash line in above picture).

According

we can know immediately:

$PShadow_{interpz}=1$

Combine the two special cases，and the property of that Pshadow is a Monotonic function decreasing function to D （see Appendix）

For the area between interp(z) (red dash line) and Reciever Rp, we have：

$t =PShadow_{perpendicular}\leq Pshadow \leq PShadow_{interpz} =1$

we can say: PShadow is Monotonic changing between t and 1 along D decreasing. it’s a smooth transition too.

For the portion below Rp, the situation is same but the PShadow < t.

Short Summary

with t increasing to 1, PShadow will increase to 1 smoothly
with D decreasing to interp(z), PShadow will increasing to 1 smoothly too.
when $D\equiv Z_2$ ( receiver surfaceperpendicular to light) , it’s a linear transition.

Conclusion

From the result, we can say ShadowMap filtering start to make sense, since a interpolated shadow depth can generate a shadow value between 0 and 1. that’s why we say VSM is filterable.

we can go one step forward, if we blur the shadow map texture, the same transition effect will expand from 2 neighborhood shadow depth texels to more adjacent texel, then it results a more smooth shadow transition, that’s why we say VSM is pre-filtable.

Appendix：Pshadow is a Monotonic decreasing funtion to D.

Check the original define:

$Pshadow = \frac{\sigma ^{2} }{\sigma ^{2}+d^{2}}$

since if t is fixed,

$\sigma ^{2}= interp(z^{2})-interp(z)^2 = (Z_{2}-Z_{1})^{2} \times (t^{2}-t)$ is a fixed value,

so if D is increasing, then d is increasing, then Pshadow is decreasing,

Then we can know Pshadow is a Monotonic decreasing function to D.

PS. the original VSM paper can be downloaded at :

VSM “Variance” http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.2569&rep=rep1&type=pdf

Filed under Tech Log

[Tech Memo] Content Performance Profiler For Artists.

September 12, 2011 Leave a comment

In game development，performance profiler is extremely helpful to optimize the game. but most Profiler is designed for programmers.

Actually artists(especially, shader/FX artists) need Profiler too. unlike programmers who always want to find the reason behind of bad performance. What artists need is a tool which can verify their idea quickly, if the performance doesn’t become good, then they go for another idea.

Obviously, Tools like pix can’t help them.

M	T	W	T	F	S	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

LEGEND FLAVOR

Importance sampling and example

A straight forward way to understand VSM

Why I want to re-understand VSM

Analysis

Special case 1: Perpendicular Reciever:

Special case 2: Reciever on interp(z):

Short Summary

Conclusion

Appendix：Pshadow is a Monotonic decreasing funtion to D.

[Tech Memo] Content Performance Profiler For Artists.

Read more of this post

[Tech Presentation] Baked Particle System

[Tech Presentation] Fast Cascade Variance Shadow Map

[Training Presentation] Power PC CPU Cache

Calendar

Years and Years

Categories

Recent Posts

LegendFlavor