I recently decided to try adding a Metropolis sampler (no BPT, just the sampler) to Cycles to get some experience with the Cycles code layout, but it turned out working so well that I decided to post it here. Due to some problems, it's not releasable yet, but these problems (more below) should be not too hard to fix.
The code is based on the SmallLuxGPU metropolis sampler, after I first tried the PBRT code, but that one didn't seem to work nearly as well.
Basically, it works by bypassing the RNG functions: When they are called and metropolis sampling is selected, they just return a value from a sample array that is stored in the RNG pointer. This allows the sampler to make only minimal changes to the kernel, it even uses the standard kernel_path_integrate. The sampler itself is in the CPUDevice thread.
My current test scene is a simple pool with a modifier-displaced water surface, an absorption volume in the water (works great, by the way), a glass pane on one sine of the water and a Sun-HDR-combination lighting the scene.
The upper image is the 2.69 release, while the lower one is with the metropolis patch. Both were rendered in equal time, but the patched version is a debug build.
From the Metropolis image, the biggest problem is obvious: Tiles. The current system requires one sampler per tile, so the seams are easily visible. Also, if one tile has large bright surfaces, the noise outside of those is worse than in other tiles. The solution for this would be one sampler per thread, all working on the whole image (which would require atomics for the buffer writes).
Another problem are passes, since they're currently written directly from the kernel. However, in Metropolis sampling, they need to be weighted, but this weight is only available after the kernel is done with the ray. A solution for this would be to return the values to be written to the buffer from the kernel, so that the Device is responsible for storing them. The depth, normal, ObjectID and Alpha passes could be done in a single-pass regular pathtrace.
Also, there currently is a bug that causes standard pathtracing to crash, I still have to find the source of this one.
However, this seems like a promising feature that might be worth the work fixing the problems above.
PS: A one-hour-render of the pool looks like this:
The patch is here: