[column width=377px margin_left=120px margin_top=80px]
Bidirectional Path Tracer
Both the path tracing and light tracing method can be used to solve the global illumination problem. Some paths are however more easily traced with one method, than the other. Path tracing have problems with paths that include caustics. A path, containing caustics, must first hit a diffuse material, then go through a series of specular bounces and finally hit a light source. This has a low probability but a high contribution, which creates a lot of noise in the image. In general we can say that path tracing performs poorly when it can’t use direct lighting. Light tracing is very good at tracing paths containing caustics, but for most other paths it creates a very noisy image. Luckily it turns out that both method can be combined into one method, that uses the best from path tracing and light tracing. This method is called bidirectional path tracing.
Figure 1: The different ways to combine the eye path and the light path. The eye path starts at the eye in X0 and moves through X1 and X2. The light path starts at the light source in Y0 and moves through Y1 and Y2. To create a complete path, a shadow ray is used to connect X2 and Y2. More paths can be generated by connecting all the different combinations of points on the sub paths.
The first unbiased version of the bidirectional path tracing algorithm was presented in . In  they independently created bidirectional path tracing and in  they improved it with multiple importance sampling.
In bidirectional path tracing we start from both ends of the path (Figure 1). We create a sub path, starting from the eye: x0, x1, x2, …, xs and another sub path, starting at a light source: y0, y1, y2, …, yt. The length of each sub path can be determined by either setting a max path length or by using a method such as Russian roulette, that randomly stops the path after some criteria. When we have both sub paths, we can combine them by creating an edge between both ends of each subpath, to create a single path going from the eye to the light source: x0, x1, x2, …, xs, yt, …, y2, y1, y0. To make sure it is a legal path we have to do a visibility check using a shadow ray, between the points xs and yt. A good optimization strategy is to connect all the points on the eye path with all the vertices on the light path. This way we can create multiple paths by reusing all the points we have traced in the scene. The only cost is that we have to do a visibility check between the end points, using a shadow ray.
[column width=377px margin_left=46px margin_top=80px]
In Figure 2 we can see a simple scene rendered with a path tracer. The light source is pointing up into the ceiling of the box, which means that most of the scene can’t benefit from direct lighting. In Figure 3 we have used bidirectional path tracing to render the same scene, using the same rendering time. We can see how this scene benefits from using bidirectional path tracing.
Figure 2: The scene rendered with a path tracer.
Figure 3: The scene rendered with a bidirectional path tracer.
 Lafortune, E. P. and Willems, Y. D. (1993). Bi-directional Path Tracing. In Santo, H. P., editor, Proceedings of Third International Conference on Computational Graphics and Visualization Techniques (Compugraphics ’93), pages 145– 153, Alvor, Portugal.
 Veach, E. and Guibas, L. (1994). Bidirectional Estimators for Light Transport. In Fifth Eurographics Workshop on Rendering, pages 147–162, Darmstadt, Germany.
 Veach, E. and Guibas, L. J. (1995). Optimally combining sampling techniques for monte carlo rendering. In SIGGRAPH ’95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, pages 419–428, New York, NY, USA. ACM.