Vertex merging paper and SmallVCM

(L) [2012/10/11] [ost by ingenious] [Vertex merging paper and SmallVCM] Wayback!

Disclaimer: Shameless self-promotion follows.

Hi all,

I have the pleasure to inform you that our SIGGRAPH Asia 2012 paper "Light Transport Simulation with Vertex Connection and Merging" is now publicly available at

http://www.iliyan.com/publications/VertexMerging

[IMG #1 Image]

Summary: The paper presents a multiple importance sampling combination of two of the most successful light transport simulation algorithms available today - bidirectional path tracing and (progressive) photon mapping. The so-called vertex connection and merging (VCM) algorithm aims to automatically get the best of both algorithms, which often complement each other in terms of performance under different lighting conditions.

Additional material: In addition to the paper that describes and evaluates the algorithm, we provide a supplemental document with more derivations and results. Notably, it contains a comparison against Veach and Kelemen style Metropolis light transport (done in Mitsuba). You will also find a ZIP archive with all images for easier exploration and comparison.

I have also prepared a simple web page with a cool interactive JavaScript comparison between progressive photon mapping, bidirectional path tracing and our vertex connection and merging:
[LINK http://www.iliyan.com/publications/VertexMerging/comparison/]

SmallVCM

Another big news is the release of SmallVCM - a (not too) small open source physically based renderer that implements [1] path tracing, [2] light tracing, [3] progressive photon mapping, [4] (progressive) bidirectional photon mapping, [5] bidirectional path tracing, and, of course, the superset of all these - our [6] vertex connection and merging algorithm.

The goal of this project is to provide relatively compact (but still readable [SMILEY :)] ) and practical implementations of the aforementioned algorithms in a single framework, and to help people better understand some subtleties and differences in their implementations. In particular, certain implementation details of bidirectional path tracing (BPT) often bring confusion and misunderstanding, and we've seen a lot of related discussions in this forum. Since vertex merging builds on top of bidirectional path tracing by adding even more complexity to it, we felt (and sincerely hope) that an open source implementation would be appreciated by people interested in the algorithm.

One technically interesting aspect of SmallVCM is the iterative multiple importance sampling (MIS) weight computation scheme for the bidirectional algorithms. The traditional BPT way of iterating over the vertices of each path to compute its MIS weight can severely impact vertex merging performance, as vertex merging often constructs a large number of paths with a single range query. An efficient MIS weight computation is thus even more important to the efficiency of the VCM algorithm than is it to BPT. The scheme we use is almost identical to the one independently developed by by Dietger van Antwerpen for BPT, and in addition computes weights for vertex merging. A technical report on the implementation will follow soon.

Having all this said, we are aware that the clarity of the code can still be greatly improved, and we welcome comments, suggestions and bug reports!

SmallVCM is hosted on GitHub, and has its own web site:

http://www.smallvcm.com

[IMG #2 Image]

[IMG #1]:

[IMG #2]:

(L) [2012/10/12] [ost by Dietger] [Vertex merging paper and SmallVCM] Wayback!

Thanks, very interesting stuff!
>> joedizzle wrote:In terms of PPM, does anyone have an idea how one can estimate the most appropriate kernel radius for area density approximation without manually fine tuning it?
That is indeed a good question. From my personal experience PPM convergence and quality is mostly determined by the initial radius. The progressive reduction of the kernel radius is foremost a theoretical trick to help some purists sleep at night (no offence [SMILEY :)] ).
>> ingenious wrote: Notably, it contains a comparison against Veach and Kelemen style Metropolis light transport (done in Mitsuba).
The MLT-Veach images seem to miss some light effects. In the Mirror balls and Car scenes, there are no ESDSL caustics paths, not even unconverged noisy splotches. Similar, in the Living room, the reflection of the table is almost noise free but way darker than all the others. I am not completely convinced that this MLT-Veach implementation converges the the same result as MLT-Kelemen (which are both rendered with the Mitsuba renderer if I am not mistaken?).

Dietger

(L) [2012/10/12] [ost by ingenious] [Vertex merging paper and SmallVCM] Wayback!

Let me clarify first that the SmallVCM code was not really written by me, but by my colleague Tomas Davidovic.

Regarding PPM, it actually does visually matter to reduce the radius. This allows you to start with some initial radius that results in relatively little variance, but larger bias (noticeable especially around corners). Otherwise you'd have to make it small enough to not see any bias initially, which will likely result in a noisy image. Also, if you have small-scale features in the scene, you better reduce [SMILEY :)] And in VCM the radius reduction matters even more, because it helps you gradually reduce the impact of the merging techniques, and converge to pure bidirectional path tracing in the limit, maintaining its higher convergence rate.

Regarding the MLT images, indeed there could be something fishy. We are planning to rerun the tests with the latest version of Mitsuba, and will update them. But I'm not too worried about the lack of reflected caustics. Such paths are arbitrarily difficult to sample with forward path tracing (which is required to seed MLT), plus MLT can get stuck in some regions, which can even decrease the chance of finding these paths - PT/BPT do uncorrelated sampling, which means that they actually have higher chance of discovering an SDS path in the same time. This is all speculation though, take it with a grain of salt.

(L) [2012/10/13] [ost by Dietger] [Vertex merging paper and SmallVCM] Wayback!

Let me try to clarify what I meant here. Of course you are right. The initial noise will be less, the added bias will go away and the algorithm does inherit BDPT's high asymptotic performance. But in practice nobody waits that long! If you would be willing to wait that long, you might as well have started with vanilla BDPT to begin with! After all, the whole reason we use PPM in the first place was because BDPT is too slow for some stuff.

In practice, we render only for a limited time (probably way too short for the asymptotic properties to have a significant impact). In that finite render time, PPM starts off doing things badly (bias artifacts around small objects) and then hopes to fix it later. The more PPM screws up initially, the longer it will take to fix this later. If PPM would just have started with an appropriately small but fixed radius for each pixel, it could realize a better quality/bias trade off in the same render time. Unfortunately we usually don't know this optimal radius (too big => bias, too small => noise), thats why we are stuck with this reducing radius. The reducing radius should free is from having to guess the optimal radius, at the cost of some extra bias within the same render time. Unfortunately, it turns out that the extra bias/noise of using a too big/small initial radius can still be pretty significant, even when rendering for reasonably long time. This is why the initial radius is still such an important parameter for the PPM algorithm, PPM's theoretical consistency notwithstanding.

Don't get me wrong, I really appreciate your work and I think that the proposed combination of PPM and BDPT can be very useful in practice! What I try to say is that although it is important to understand the theoretical asymptotic properties of an algorithm, we should not overrate the practical value of such theoretical properties.
>> ingenious wrote:Such paths are arbitrarily difficult to sample with forward path tracing (which is required to seed MLT), plus MLT can get stuck in some regions, which can even decrease the chance of finding these paths
True. But than again, Kelemen-MLT did manage to find them. So assuming that Veach-MLT has a reasonable probability of throwing away the first few eye vertices, it should have a decent probability of finding these caustics at least once in a while. And when MLT finds them, it will hang on! So that's why I expected at least some ugly bright splotches here and there [SMILEY :)]
More worrying, in the 'Living room' scene, PT and BDPT have no problem at all sampling the direct light on the table in the mirror, so a properly set up Veach-MLT mutation should also have no problem there. Unless the mutation selection probabilities are set up exceptionally bad, I think something is off. Anyhow, I shouldn't complain, as this is probably the only half-decent Veach-MLT implementation out there [SMILEY :)]

Dietger

Vertex merging paper and SmallVCM back

Board: Home Board index Raytracing Links & Papers