A survey of photon mapping state-of-the-art research and future challenges <s> Introduction <s> The creation of photorealistic images of three-dimensional models is central to computer graphics. Photon mapping, an extension of ray tracing, makes it possible to efficiently simulate global illumination in complex scenes. Photon mapping can simulate caustics (focused light, like shimmering waves at the bottom of a swimming pool), diffuse inter-reflections (e.g., the bleeding of colored light from a red wall onto a white floor, giving the floor a reddish tint), and participating media (such as clouds or smoke). This book is a practical guide to photon mapping; it provides both the theory and the practical insight necessary to implement photon mapping and simulate all types of direct and indirect illumination efficiently. <s> BIB001 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Introduction <s> We describe a novel data structure for representing light transport called ray map. The ray map extends the concept of photon maps: it stores not only photon impacts but the whole photon paths. We demonstrate the utility of ray maps for global illumination by eliminating boundary bias and reducing topological bias of density estimation in global illumination. Thanks to the elimination of boundary bias we could use ray maps for fast direct visualization with the image quality being close to that obtained by the expensive final gathering step. We describe in detail our implementation of the ray map using a lazily constructed kD-tree. We also present several optimizations bringing the ray map query performance close to the performance of the photon map. <s> BIB002 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Introduction <s> A number of popular global illumination algorithms uses density estimation to approximate indirect illumination. The density estimate is performed on finite points -- particles -- generated by a stochastic sampling of the scene. In the course of the sampling, particles, representing light, are stochastically emitted from the light sources and reflected around the scene. The sampling induces noise, which in turn is handled by the density estimate during the illumination reconstruction. Unfortunately, this noise reduction imposes a systematic error (bias), which is seen as a blurring of prominent illumination features. This is often not desirable as these may lose clarity or vanish altogether. We present an accurate method for reconstruction of indirect illumination with photon mapping. Instead of reconstructing illumination using classic density estimation on finite points, we use the correlation of light footprints, created by using Ray Differentials during the light pass. This procedure gives a high illumination accuracy, improving the trade-off between bias and variance considerable as compared to traditional particle tracing algorithms. In this way we preserve structures in indirect illumination. <s> BIB003 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Introduction <s> This paper introduces a simple and robust progressive global illumination algorithm based on photon mapping. Progressive photon mapping is a multi-pass algorithm where the first pass is ray tracing followed by any number of photon tracing passes. Each photon tracing pass results in an increasingly accurate global illumination solution that can be visualized in order to provide progressive feedback. Progressive photon mapping uses a new radiance estimate that converges to the correct radiance value as more photons are used. It is not necessary to store the full photon map, and unlike standard photon mapping it possible to compute a global illumination solution with any desired accuracy using a limited amount of memory. Compared with existing Monte Carlo ray tracing methods progressive photon mapping provides an efficient and robust alternative in the presence of complex light transport such as caustics and in particular reflections of caustics. <s> BIB004 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Introduction <s> The photon mapping method is one of the most popular algorithms employed in computer graphics today. However, obtaining good results is dependent on several variables including kernel shape and bandwidth, as well as the properties of the initial photon distribution. While the photon density estimation problem has been the target of extensive research, most algorithms focus on new methods of optimising the kernel to minimise noise and bias. In this paper we break from convention and propose a new approach that directly redistributes the underlying photons. We show that by relaxing the initial distribution into one with a blue noise spectral signature we can dramatically reduce background noise, particularly in areas of uniform illumination. In addition, we propose an efficient heuristic to detect and preserve features and discontinuities. We then go on to demonstrate how reconfiguration also permits the use of very low bandwidth kernels, greatly improving render times whilst reducing bias. <s> BIB005 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Introduction <s> We present a new sampling space for light transport paths that makes it possible to describe Monte Carlo path integration and photon density estimation in the same framework. A key contribution of our paper is the introduction of vertex perturbations, which extends the space of paths with loosely coupled connections. The new framework enables the computation of path probabilities in the same space under the same measure, which allows us to use multiple importance sampling to combine Monte Carlo path integration and photon density estimation. The resulting algorithm, unified path sampling, can robustly render complex combinations and glossy surfaces and caustics that are problematic for existing light transport simulation methods. <s> BIB006 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Introduction <s> Developing robust light transport simulation algorithms that are capable of dealing with arbitrary input scenes remains an elusive challenge. Although efficient global illumination algorithms exist, an acceptable approximation error in a reasonable amount of time is usually only achieved for specific types of input scenes. To address this problem, we present a reformulation of photon mapping as a bidirectional path sampling technique for Monte Carlo light transport simulation. The benefit of our new formulation is twofold. First, it makes it possible, for the first time, to explain in a formal manner the relative efficiency of photon mapping and bidirectional path tracing, which have so far been considered conceptually incompatible solutions to the light transport problem. Second, it allows for a seamless integration of the two methods into a more robust combined rendering algorithm via multiple importance sampling. A progressive version of this algorithm is consistent and efficiently handles a wide variety of lighting conditions, ranging from direct illumination, diffuse and glossy inter-reflections, to specular-diffuse-specular light transport. Our analysis shows that this algorithm inherits the high asymptotic performance from bidirectional path tracing for most light path types, while benefiting from the efficiency of photon mapping for specular-diffuse-specular lighting effects. <s> BIB007
The photon mapping (PM) algorithm is an effective method for implementing global illumination, which is one of the most important parts of photo-realistic rendering. Since  proposed the photon mapping algorithm, many studies have attempted to obtain the accurate rendering result and to improve the rendering efficiency. Photon mapping is a two-pass algorithm. The ‡ Corresponding author first pass is the photon tracing pass to generate the photon maps, and the second pass is the photon collection pass, in which the illumination is reconstructed via the photon maps (Fig. 1) . Although the approach has advantages in many practical ways, it still faces significant challenges such as visual noise and bias problems (Fig. 2) . In this paper, we analyze improved photon mapping algorithms and produce a classified summary. Improved radiance estimation methods use more accurate radiance estimation methods. Changing the accumulation mode of photon energy BIB001 BIB002 and improving the search bandwidth BIB003 can reduce the bias and noise in the photon mapping algorithm. Photon relaxation methods eliminate random distribution noise in the photon map. Through photon relaxation methods BIB005 , photons can be distributed uniformly in a local area. The noise in the distribution can be eliminated, but the illumination features may be smoothed. Progressive photon mapping methods increase the number of photons emitted. The billions of emissions lead to the increase of memory usage, so researchers proposed a progressive photon mapping method BIB004 in which it was unnecessary to store the full photon map. The method can effectively decrease noise with little memory being used, and it can also be combined naturally with the method of bidirectional path tracing BIB006 BIB007 . Photon tracing methods improve the photons' emission path. Improved photon tracing methods can optimize photon distribution through the transmitting step, speed up rendering, and achieve accurate results. Parallel methods accelerate the rendering processes by using graphics hardware. Global illumination algorithms are time-consuming in the process of photo-realistic image rendering. To take full advantage of the hardware's computing ability to accelerate, different methods use different strategies. The analysis of the optimized methods based on three challenges, namely smoothness, features, and space-savings, is presented in Fig. 3 . Fig. 3a shows the ideal solution which has good performance on the three challenges. Fig. 3b is the analysis of radiance estimation methods without considering storage completely. Fig. 3c is the analysis of photon relaxation methods which can generate smooth results with a small photon map, but it is difficult to keep the features. Fig. 3d shows that the progressive photon mapping methods can change the storage mode of photons and generate smooth results through a massive number of iterations. It is close to the ideal model. However, the progressive photon mapping methods are time-consuming as too many iterations are needed. Fig. 3e shows that the photon tracing methods can optimize the distribution focusing on the emission technique in order to improve the quality of rendering results. What is more, general We also analyze the parallel algorithms, which can accelerate rendering by using hardware acceleration units in general.