Questions about metroplis sampling.

(L) [2014/10/02] [tby shiqiu1105] [Questions about metroplis sampling.] Wayback!

Hi all,
Lately I am trying to implement keleman styled metroplis sampling.
I just finished reading the paper and, despite the author has provided source code, I am still quite confused.
One thing I want to ask is why does it use only one markov chain for the entire image, instead of using one chain per pixels.
That way we get high quality samples AND equal amount of samples per pixel.
Has anyone tried this before?
Furthermore, I don't quite understand the mathematics behind it. I know there are implementation online which makes implementing it not as hard, just want to know how many of you actually figure out how exactly the math and statistics work before implementing it?
Thanks,

(L) [2014/10/02] [tby Dade] [Questions about metroplis sampling.] Wayback!

>> shiqiu1105 wrote:That way we get high quality samples AND equal amount of samples per pixel.

The point is exactly to not get an equal amount of samples per pixel (aka adaptive sampling): more samples where they are more useful (or better where they are supposed to be more useful).
If you are looking for an example of Kelemen's metropolis implementation, you can find one in LuxRender: [LINK https://bitbucket.org/luxrender/luxrays/src/c76a7566440e51ecc9d1c85758f73a63ce54be3f/src/slg/sampler/sampler.cpp?at=default#cl-69]
It is pretty much a stand-alone class (about 200 lines of code) that has already been used in other contexts too.

(L) [2014/10/02] [tby shiqiu1105] [Questions about metroplis sampling.] Wayback!

>> Dade wrote:shiqiu1105 wrote:That way we get high quality samples AND equal amount of samples per pixel.

The point is exactly to not get an equal amount of samples per pixel (aka adaptive sampling): more samples where they are more useful (or better where they are supposed to be more useful).
If you are looking for an example of Kelemen's metropolis implementation, you can find one in LuxRender: [LINK https://bitbucket.org/luxrender/luxrays/src/c76a7566440e51ecc9d1c85758f73a63ce54be3f/src/slg/sampler/sampler.cpp?at=default#cl-69]
It is pretty much a stand-alone class (about 200 lines of code) that has already been used in other contexts too.
Thanks for your answer [SMILEY :)]
But if we are using a single markov chain across the whole image, can we have parallelism?
Right now my renderer is using tile-based multithreading. If we maintain a state across the whole image, it seems trickier, if not impossible, to parallize it [SMILEY :(]

(L) [2014/10/02] [tby shiqiu1105] [Questions about metroplis sampling.] Wayback!

>> shiqiu1105 wrote:Dade wrote:shiqiu1105 wrote:That way we get high quality samples AND equal amount of samples per pixel.

The point is exactly to not get an equal amount of samples per pixel (aka adaptive sampling): more samples where they are more useful (or better where they are supposed to be more useful).
If you are looking for an example of Kelemen's metropolis implementation, you can find one in LuxRender: [LINK https://bitbucket.org/luxrender/luxrays/src/c76a7566440e51ecc9d1c85758f73a63ce54be3f/src/slg/sampler/sampler.cpp?at=default#cl-69]
It is pretty much a stand-alone class (about 200 lines of code) that has already been used in other contexts too.
Thanks for your answer
But if we are using a single markov chain across the whole image, can we have parallelism?
Right now my renderer is using tile-based multithreading. If we maintain a state across the whole image, it seems trickier, if not impossible, to parallize it
One solution that I am thinking is to maintain the same number of markov chain as thread count, and only need to pay attention when writing to the same pixel.
SLG is a gpu renderer, I am instereted in knowing how it parallize it~

(L) [2014/10/02] [tby Dade] [Questions about metroplis sampling.] Wayback!

>> shiqiu1105 wrote:SLG is a gpu renderer, I am instereted in knowing how it parallize it~
In C++ I have an instance of MetropolisSampler class for each thread. So, for instance, with 12 threads, it is like merging the results of 12 different renderings. The same goes for different network node renders.
In OpenCL I have an instance of MetropolisSampler for each work-item (i.e. 65k for each GPU !). This requires a lot of memory to store the MetropolisSampler states and each MetropolisSampler sampler converges to the optimal distribution quite slowly. It is sub-optimal but it works.
With tile rendering, I don't use MetropolisSampler at all, it requires to operate on the complete image plane otherwise it does't make very much sense to use it.

(L) [2014/10/02] [tby bachi] [Questions about metroplis sampling.] Wayback!

>> shiqiu1105 wrote:One thing I want to ask is why does it use only one markov chain for the entire image, instead of using one chain per pixels.
That way we get high quality samples AND equal amount of samples per pixel.
Has anyone tried this before?

This is exactly what the energy redistribution path tracing paper proposed to have better stratification. Though we do not have equal amount of samples per pixel even if we distribute the samples this way, since the point of metropolis sampling is to generate a sample set which has the same distribution compare to the target function, which is usually not flat on the image plane.
This strategy sometimes works, but sometimes doesn't. If the target function contains many isolated local modes, and bidirectional path tracing gives us a good enough initial guess, then it should work well. Otherwise longer chain could be a better choice since it "remember" the difficult-to-sample light paths and has higher probability to sample them.

(L) [2014/10/02] [tby Dietger] [Questions about metroplis sampling.] Wayback!

>> shiqiu1105 wrote:That way we get high quality samples AND equal amount of samples per pixel.
Has anyone tried this before?
You might want to look at the paper "Arbitrary Importance Functions for Metropolis Light Transport" by Hoberock. The idea is to boost the importance of dark pixels and reduce the importance of bright pixels so as to aim for an equal amount of samples per pixel (in expectation), even though the Markov chains walks the whole image. It's still only in expectation and because of the high correlation between mutations it will take a while before the distribution starts to look uniform, but it is definitely an improvement.

(L) [2014/10/02] [tby Dietger] [Questions about metroplis sampling.] Wayback!

>> shiqiu1105 wrote:...high quality samples ...
On another note, whether MLT really produces higher quality samples is debatable. Sure, the sampling density is proportional to the target function, perfect importance sampling and all that, but it comes at a price. When MLT gets stuck in a peak of the target function for too long the correlation artifacts can be massive, destroying any benefits gained from 'perfect' importance sampling. One major issue with the o-so-robust MLT algorithm is that it tends to suffer from aliasing artifacts. Basically it sucks at resolving small features. Imagine a lamp hanging from a pixel-thin wire or a faraway handrail. In PT you don't need that many samples per pixel before you get a nicely anti-aliased wire. However, in MLT your small step mutations better be really small in image space or else this wire will look aliased for a very long time.

(L) [2014/10/02] [tby shiqiu1105] [Questions about metroplis sampling.] Wayback!

>> Dietger wrote:shiqiu1105 wrote:...high quality samples ...
On another note, whether MLT really produces higher quality samples is debatable. Sure, the sampling density is proportional to the target function, perfect importance sampling and all that, but it comes at a price. When MLT gets stuck in a peak of the target function for too long the correlation artifacts can be massive, destroying any benefits gained from 'perfect' importance sampling. One major issue with the o-so-robust MLT algorithm is that it tends to suffer from aliasing artifacts. Basically it sucks at resolving small features. Imagine a lamp hanging from a pixel-thin wire or a faraway handrail. In PT you don't need that many samples per pixel before you get a nicely anti-aliased wire. However, in MLT your small step mutations better be really small in image space or else this wire will look aliased for a very long time.
What you said makes sense.. Maybe it's not a good idea to implement it right now after all..

Questions about metroplis sampling. back

Board: Home Board index Raytracing General Development