Can anyone summarize in simple terms, how PSSMLT/MLT algorithms work?

Question

I understand backwards path tracing and bidirectional path tracing (BDPT). However I'm failing to understand how Metrpolis Light Transport methods are even remotely feasible to run.

My understanding is that MLT methods start with BDPT to generate an initial set of light paths. Then it "mutates" these paths to explore the light paths nearby so that it can better converge in situations with difficult lighting. This leaves me with two questions:

1. Is that mutation process simply perturbing a given ray? That is to say, if I have a light path C -> p1 -> p2 -> L (where C is the Camera, L is the light, and pi is some intersection point), that I slightly perturb the ray p1 -> p2 and trace it so that I get some new p2_mutated, thus creating a new chain: C -> p1 -> p2_mutated -> L? Or is the mutation scheme somehow actually manipulating the intersection point directly?

2. It would seem to me that you would needd to do this broard search and mutation scheme for every single primary ray. But that would be totally computationally infeasible. Is there some kind of assumption that the search for light paths with high contributions is done for only a subset of the primary rays, and then those light paths are "applied" to subsequent primary rays allowing you to skip the searching step for some rays?

I'm having a difficult time understanding the papers but I feel like if someone could explain in plane english what is happening, I might be able to make more sense of it.

Answer 1

To give a bit of context MLT and PSSMLT fall into the broader family of Markov Chain Monte Carlo (MCMC) methods, so my answer will contain a small bit of Markov chain terminology. I assume you are familiar with it, but if you are not it might explain why you feel like you're struggling to understand papers (if so, see my ending note).

1. If I rephrase your question, you're asking if more raycasting need to be performed, or if the geometry of the path can be directly modified.

The theory doesn't put any constraint on it, but in practice it would be difficult to design a mutation strategy that guarantees that the new intersections fall on the surfaces of your scene. At least I'm not aware of any !

A simplified answer is that to mutate a path, you replace a chosen subpath of the current path and replace it by tracing paths from the remaining paths on both the emitter side and the sensor side, and connect. It is more complex in practice, because you need to ensure that paths are connectable.

The first version of Mitsuba used to have an MLT implementation using BDPT mutation to which you can refer, looking for the sampleMutation method. In this, proposal is initialised to the l first vertices of the current path, then the emitter subpath is extended by s events and the sensor subpath by t events, and a connection is made. But this is only one implementation.

2. Indeed this would be untractable.

The point of the Metropolis-Hastings algorithms is that you perform a random walk in the space of your possible states (the possible paths, here), so you don't need to cover them all. It is too complex to detail more here, but the Chapter 11 of Eric Veach thesis is what you need. The mutations you use, combined with a given acceptance law, "hard-code" the assumptions you make about what light paths will bring the highest contributions. In a sense, you're encoding how you expect the contribution function to be, to be able to sample it better (i.e. take the most significant paths).

Common assumptions includes that shorter paths bring more energy, and highly contributing paths are worth exploring by using small mutations while other may be skipped by performing larger mutations.

In the case of PSSMLT, it is assumed that close points in the primary sample space make close paths in the light path space.

The thing is, the mutations and acceptance strategies are what make the litterature of MCMC path tracers so populated (and precisely answering your question difficult) ! A good example — I think, although a bit off from original MLT — is MEPT Jakob & Marschner., 2012, because it illustrates quite visually some assumptions that may drive the design of a mutation strategy. Also it's a much quicker read than Veach's thesis :D, and it completes my answer to your first question. Essentially you want to sample paths that are reflected similarly on a reflective surface ; this is a geometrical constraint, and the paper identifies a "manifold" (quickly, a subset of the path space that matches that constraint) and try to move around on it. Each mutation step has a modification step and a reprojection step, that guarantees the new path is a valid path.