A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> For hardware accelerated rendering, photon mapping is especially useful for simulating caustic lighting effects on non-Lambertian surfaces. However, an efficient hardware algorithm for the computation of the k nearest neighbours to a sample point is required.Existing algorithms are often based on recursive spatial subdivision techniques, such askd-trees. However, hardware implementation of a tree-based algorithm would have a high latency, or would require a large cache to avoid this latency on average.We present a neighbourhood-preserving hashing algorithm that is low-latency and has sub-linear access time. This algorithm is more amenable to fine-scale parallelism than tree-based recursive spatial subdivision, and maps well onto coherent block-oriented pipelined memory access. These properties make the algorithm suitable for implementation using future programmable fragment shaders with only one stage of dependent texturing. <s> BIB001 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> We present a method for interactive global illumination computation which is embedded in the framework of Quasi-Monte Carlo photon tracing and density estimation techniques. The method exploits temporal coherence of illumination by tracing photons selectively to the scene regions that require illumination update. Such regions are identified with a high probability by a small number of the pilot photons. Based on the pilot photons which require updating, the remaining photons with similar paths in the scene can be found immediately. This becomes possible due to the periodicity property inherent to the multi-dimensional Halton sequence, which is used to generate photons. If invalid photons cannot all be updated during a single frame, frames are progressively refined in subsequent cycles. The order in which the photons are updated is decided by inexpensive energy- and perception-based criteria whose goal is to minimize the perceivability of outdated illumination. The method buckets all photons on-the-fly in mesh elements and does not require any data structures in the temporal domain, which makes it suitable for interactive rendering of complex scenes. Since mesh-based reconstruction of lighting patterns with high spatial frequencies is inefficient, we use a hybrid approach in which direct illumination and resulting shadows are rendered using graphics hardware. <s> BIB002 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> This paper introduces a novel method for simulating photon mapping for real-time applications. First we introduce a new method for selectively redistributing photons. Then we describe a method for selectively updating the indirect illumination. The indirect illumination is calculated using a new GPU acceleratedfinal gathering method and the illumination is then stored in light maps. Caustic photons are traced on the CPU and then drawn using points in the framebuffer, and finally filtered using the GPU. Both diffuse and non-diffuse surfaces can be handled by calculating the direct illumination on the GPU and the photon tracing on the CPU. We achieve real-time frame rates for dynamic scenes. <s> BIB003 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> With the advancements in realtime ray tracing and new global illumination algorithms we are now able to render the most important illumination effects at interactive rates. One of the major remaining issues is the fast and efficient simulation of caustic illumination, such as e.g. the illumination from a car headlight. The photon mapping algorithm is a simple and robust approach that generates high-quality results and is the preferred algorithm for computing caustic illumination. However, photon mapping has a number of properties that make it rather slow on today's processors. Photon mapping has also been notoriously difficult to parallelize efficiently. ::: ::: In this paper, we present a detailed analysis of the performance issues of photon mapping together with significant performance improvements for all aspects of the photon mapping technique. The solution forms a complete framework for realtime photon mapping that efficiently combines realtime ray tracing, optimized and improved photon mapping algorithms, and efficient parallelization across commodity PCs. The presented system achieves realtime photon mapping performance of up to 22 frames per second on non-trivial scenes, while still allowing for interactively updating all aspects of the scene, including lighting, material properties, and geometry. <s> BIB004 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> We present a modified photon mapping algorithm capable of running entirely on GPUs. Our implementation uses breadth-first photon tracing to distribute photons using the GPU. The photons are stored in a grid-based photon map that is constructed directly on the graphics hardware using one of two methods: the first method is a multipass technique that uses fragment programs to directly sort the photons into a compact grid. The second method uses a single rendering pass combining a vertex program and the stencil buffer to route photons to their respective grid cells, producing an approximate photon map. We also present an efficient method for locating the nearest photons in the grid, which makes it possible to compute an estimate of the radiance at any surface location in the scene. Finally, we describe a breadth-first stochastic ray tracer that uses the photon map to simulate full global illumination directly on the graphics hardware. Our implementation demonstrates that current graphics hardware is capable of fully simulating global illumination with progressive, interactive feedback to the user. <s> BIB005 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> This paper describes a new scheme for computing out-of-core global illumination in complex indoor scenes using a photon-mapping approach. Our method makes use of a cells-and-portals representation of the environment for preserving memory coherence and storing rays or photons. We have successfully applied our method to various buildings, composed of up to one billion triangles. As shown in the results, our method requires only a few hundred megabytes of memory for tracing more than 1.6 billion photons in large buildings. <s> BIB006 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <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> BIB007 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> We present a novel photon mapping framework that uses single instruction, multiple data (SIMD) parallelism to accelerate the final gathering phase of photon mapping. By using SIMD instructions, four coherent tasks can be computed in parallel using almost the same memory traffic as it would cost to process one task alone. This approach has been very successful for real-time ray tracing, but until now it has been unclear how to effectively apply the same approach to final gathering. Our solution is to use sample-point density estimation instead of k-nearest neighbor density estimation, a technique drawn from reverse photon mapping. Sample-point estimation removes the overheads that make SIMD instructions impractical, while retaining the same benefits and image quality as traditional photon mapping. Additionally, an important question arises whether it is better to use forward or reverse photon mapping. In an interactive context, classical asymptotic algorithmic analysis is not enough to compare the two algorithms. We provide a novel asymptotic bandwidth analysis, which addresses more issues found in practice. The analysis motivates the use of forward photon mapping when using SIMD parallelism as well as partial reordering for improved scalability. The resulting framework can achieve interactive rates for photon mapping at low resolutions, including the time it takes to trace photons and build the photon map. <s> BIB008 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> Photon mapping attracts much attention as an excellent image generation technique that can simulate various lighting effects such as indirect illumination and caustics obtained only by the global illumination model. Although photon mapping can generate high-quality images, it requires more expensive calculations and a large memory capacity. In this paper, we present a new parallel photon mapping algorithm to solve the problems regarding the computing time and memory requirement. The proposed algorithm can effectively parallelize photon map construction and photon search by distributing partial photon maps among processing elements of a parallel computer. As a photon map is partitioned, only a part of the photon map is assigned to each processing element. Therefore, each processing element does not require a large memory space even if the entire photon map is quite huge. We implement the proposed algorithm using MPI and evaluate it through experiments on a parallel computer. The experimental results indicate that our algorithm can significantly reduce the rendering time of photon mapping as the number of processing elements increases, and can also save the memory space. <s> BIB009 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> We present a photon mapping technique capable of computing high quality global illumination at interactive frame rates. By extending the concept of photon differentials to efficiently handle diffuse reflections, we generate footprints at all photon hit points. These enable illumination reconstruction by density estimation with variable kernel bandwidths without having to locate the k nearest photon hits first. Adapting an efficient BVH construction process for ray tracing acceleration, we build photon maps that enable the fast retrieval of all hits relevant to a shading point. We present a heuristic that automatically tunes the BVH build's termination criterion to the scene and illumination conditions. As all stages of the algorithm are highly parallelizable, we demonstrate an implementation using NVidia's CUDA manycore architecture running at interactive rates on a single GPU. Both light source and camera may be freely moved with global illumination fully recalculated in each frame. <s> BIB010 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> This paper presents a GPU-based method for interactive global illumination that integrates complex effects such as multi-bounce indirect lighting, glossy reflections, caustics, and arbitrary specular paths. Our method builds upon scattered data sampling and interpolation on the GPU. We start with raytraced shading points and partition them into coherent shading clusters using adaptive seeding followed by k-means. At each cluster center we apply final gather to evaluate its incident irradiance using GPU-based photon mapping. We approximate the entire photon tree as a compact illumination cut, thus reducing the final gather cost for each ray. The sampled irradiance values are then interpolated at all shading points to produce rendering. Our method exploits the spatial coherence of illumination to reduce sampling cost. We sample sparsely and the distribution of sample points conforms with the underlying illumination changes. Therefore our method is both fast and preserves high rendering quality. Although the same property has been exploited by previous caching and adaptive sampling methods, these methods typically require sequential computation of sample points, making them ill-suited for the GPU. In contrast, we select sample points adaptively in a single pass, enabling parallel computation. As a result, our algorithm runs entirely on the GPU, achieving interactive rates for scenes with complex illumination effects. <s> BIB011 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> The NVIDIA® OptiX™ ray tracing engine is a programmable system designed for NVIDIA GPUs and other highly parallel architectures. The OptiX engine builds on the key observation that most ray tracing algorithms can be implemented using a small set of programmable operations. Consequently, the core of OptiX is a domain-specific just-in-time compiler that generates custom ray tracing kernels by combining user-supplied programs for ray generation, material shading, object intersection, and scene traversal. This enables the implementation of a highly diverse set of ray tracing-based algorithms and applications, including interactive rendering, offline rendering, collision detection systems, artificial intelligence queries, and scientific simulations such as sound propagation. OptiX achieves high performance through a compact object model and application of several ray tracing-specific compiler optimizations. For ease of use it exposes a single-ray programming model with full support for recursion and a dynamic dispatch mechanism similar to virtual function calls. <s> BIB012 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> Image space photon mapping has the advantage of simple implementation on GPU without pre-computation of complex acceleration structures. However, existing approaches use only a single image for tracing caustic photons, so they are limited to computing only a part of the global illumination effects for very simple scenes. In this paper we fully extend the image space approach by using multiple environment maps for photon mapping computation to achieve interactive global illumination of dynamic complex scenes. The two key problems due to the introduction of multiple images are 1) selecting the images to ensure adequate scene coverage; and 2) reliably computing raygeometry intersections with multiple images. We present effective solutions to these problems and show that, with multiple environment maps, the image-space photon mapping approach can achieve interactive global illumination of dynamic complex scenes. The advantages of the method are demonstrated by comparison with other existing interactive global illumination methods. <s> BIB013 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> Wide-SIMD hardware is power and area efficient, but it is challenging to efficiently map ray tracing algorithms to such hardware especially when the rays are incoherent. The two most commonly used schemes are either packet tracing, or relying on a separate traversal stack for each SIMD lane. Both work great for coherent rays, but suffer when rays are incoherent: The former experiences a dramatic loss of SIMD utilization once rays diverge; the latter requires a large local storage, and generates multiple incoherent streams of memory accesses that present challenges for the memory system. In this paper, we introduce a single-ray tracing scheme for incoherent rays that uses just one traversal stack on 16-wide SIMD hardware. It uses a bounding-volume hierarchy with a branching factor of four as the acceleration structure, exploits four-wide SIMD in each box and primitive intersection test, and uses 16-wide SIMD by always performing four such node or primitive tests in parallel. We then extend this scheme to a hybrid tracing scheme that automatically adapts to varying ray coherence by starting out with a 16-wide packet scheme and switching to the new single-ray scheme as soon as rays diverge. We show that on the Intel Many Integrated Core architecture this hybrid scheme consistently, and over a wide range of scenes and ray distributions, outperforms both packet and single-ray tracing. <s> BIB014 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> This article introduces a novel locally adaptive progressive photon mapping technique which optimally balances noise and bias in rendered images to minimize the overall error. It is the result of an analysis of the radiance estimation in progressive photon mapping. As a first step, we establish a connection to the field of recursive estimation and regression in statistics and derive the optimal estimation parameters for the asymptotic convergence of existing approaches. Next, we show how to reformulate photon mapping as a spatial regression in the measurement equation of light transport. This reformulation allows us to derive a novel data-driven bandwidth selection technique for estimating a pixel's measurement. The proposed technique possesses attractive convergence properties with finite numbers of samples, which is important for progressive rendering, and it also provides better results for quasi-converged images. Our results show the practical benefits of using our adaptive method. <s> BIB015 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> We describe the design space for real-time photon density estimation, the key step of rendering global illumination (GI) via photon mapping. We then detail and analyze efficient GPU implementations of four best-of-breed algorithms. All produce reasonable results on NVIDIA GeForce 670 at 1920 × 1080 for complex scenes with multiple-bounce diffuse effects, caustics, and glossy reflection in real-time. Across the designs we conclude that tiled, deferred photon gathering in a compute shader gives the best combination of performance and quality. <s> BIB016 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> This paper introduces an efficient and simple algorithm for constructing Multiple Reference (MR) octrees on a GPU in application to Photon Mapping and Irradiance Caching techniques. Although MR-octrees are hierarchical structures, we successfully ignore their hierarchical nature and present an approach with plain construction, compact data layout and stack-less traversal. Our algorithm uses only 2 parallel primitives (parallel append and parallel sort) and can be expressed in several lines of pseudo-code. <s> BIB017 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> At present, stochastic progressive photon mapping SPPM is one of the most comprehensive methods for a consistent global illumination computation. Even though the number of photons is unlimited due to their progressive nature, the scene size is still bound by the available main memory. In this paper, we present the first consistent out-of-core SPPM algorithm. In order to cope with large scenes, we automatically subdivide the geometry and parallelly trace photons and eye rays in a portal-based system, distributed across multiple machines in a commodity cluster. Moreover, modifications of the original SPPM method are introduced that keep both the utilization of tracer machines high and the network traffic low. Therefore, compared to a portal-based single machine setup, our distributed approach achieves a significant speedup. We compare a GPU-based with a CPU-based implementation and demonstrate our system in multiple large test scenes of up to 90 million triangles. <s> BIB018 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> Abstract High demand 3-D scenes on embedded systems draw the developers’ attention to use the whole resources of current low-power processors and add dedicated hardware as a graphic accelerator unit to deal with real-time realistic scene rendering. Photon mapping, as one of the most powerful techniques to render highly realistic 3-D images by high amounts of floating-point operations, is very time-consuming. To use the advantages of multiprocessor systems to make 3-D scenes, parallel photon-mapping rendering on a homogeneous multiprocessor SoC (MPSoC) platform along with a mesh NoC by an adaptive wormhole routing method to communicate packets among cores is proposed in this paper. To make efficient use of the MPSoC platform to carry out photon-mapping rendering, many methods concerning the increase of load balancing, the efficient use of memory, and the decrease of communication cost to achieve a scalable application are explored in this paper. The resulting MPSoC platform is verified and evaluated by cycle-accurate simulations for different sizes of the mesh NoC. As expected, the proposed methods can obtain excellent load balancing and achieve a maximum of 44.3 times faster on an 8-by-8 MPSoC platform than on a single-core MPSoC platform. <s> BIB019 </s> A survey of photon mapping state-of-the-art research and future challenges <s> Parallel photon mapping <s> Photon mapping is a global illumination algorithm which is composed of two steps: photon tracing and photon searching. During photon searching step, each shading point needs to search the photon-tree to find k-neighbouring photons for reflected radiance estimation. As the number of shading points and the size of photon-tree are dramatically large, the photon searching step is time consuming. We propose a parallel photon searching algorithm by using radiance estimation approach for coherent shading points on the Intel® Many Integrated Core (MIC) Architecture. In order to efficiently use single instruction multiple data (SIMD) units, shading points are clustered by similarity first (every cluster contains 16 shading-points), and an initial neighbouring scope is searched from the photon-tree for each cluster. Then we use 16-wide SIMD units by performing k-NN searching from the initial neighbouring scope for those 16 shading-points in a cluster in parallel. We use the method to simulate some global illumination scenes on Intel® Xeon® processors and Intel® Xeon® Phi™ coprocessors. The comparison results with existing photon mapping techniques indicate that our method gives significant improvement in speed with the same accuracy. <s> BIB020
Photon mapping is improved on result optimization but at the same time, the efficiency of the algorithm is very important. Some algorithms can improve the rendering efficiency, e.g., the method proposed by BIB015 . However, the most direct way is parallel acceleration by using graphics hardware. Early works on parallel photon mapping are based on the optimized data structures which are adapted to the GPU. BIB001 used spatial hashing to replace the nearest-neighbour queries required in KD-tree in the density estimation pass, which fits better to parallel GPUs. In BIB005 , the photons were directly stored in a grid-based photon map which was constructed and used on graphics hardware. They all presented efficient methods for locating the nearest photons in the new data structures. Hardware implementation of a tree-based algorithm is difficult because it would require a large cache to avoid a high latency on average. To use an efficient KD-tree algorithm,  presented an efficient KD-tree building method, which is used both for tracing rays and for density estimation. This is the first real-time KD-tree algorithm on GPU. They divided the contribution process to exploit the fine-grained parallelism of GPUs. Some researchers focused on the existing improved algorithms, and used a parallel compute unified device architecture (CUDA) implementation to accelerate the rendering. BIB010 presented an interactive photon mapping method, which improves the photon differentials method BIB007 on GPU and extends the original algorithm to global photon mapping. proposed the first GPU implementation of progressive photon mapping based on a new data structure. They avoided using irregular spatial data structures, which do not fit well to the balanced workload required for GPUs, in the storage of photons. In their method, the costly ray tracing-based photon shooting is not accelerated. For adaptive progressive photon mapping, BIB015 suggested that their method can be parallelized easily. NVIDIA OptiX BIB012 ) is a GPU-based ray tracing rendering engine, and with the parallel ray tracing there is an example implementation of progressive photon mapping. BIB016 introduced an efficient GPU density estimation method, which uses an explored ray tracing method and the novel shading method focusing on density estimation. The researchers proposed a method for sampling and photon gathering with vector processors. BIB017 introduced an algorithm for constructing multiple reference octrees on a GPU in photon mapping techniques. They successfully ignored octrees' hierarchical property and presented parallel append and parallel sort primitives. In 2010, Intel issued the Xeon Phi coprocessor which is based on a many integrated core architecture (MIC) with the KNC instructions. A hybrid parallel ray tracing algorithm BIB014 has been achieved based on this hardware. Various hardware architectures are worthy of attention for hardware implementation. BIB020 presented the first photon mapping method on the MIC. They decomposed the collection step according to the spatial coherence, and applied the vector calculation unit to accelerate. However, BIB008 firstly applied the SIMD packet techniques for photon mapping. Their solution is to use samplepoint density estimation instead of k-NN density estimation, which contains the overheads that make SIMD instructions impractical. BIB011 applied the coherence of raytraced shading points and interpolation to reduce the final gather cost, and this is a GPU-based method. Some studies focus on interactive frames rendering. In BIB002 , photons were divided into groups and re-emitted selectively based on dynamic objects collision. BIB003 proposed a new method for selectively redistributing photons and different elements in global illumination being calculated individually to demonstrate interactive frame rates. There are also some distributed parallel methods. BIB004 achieved a real-time distributed photon mapping for caustic rendering. BIB009 presented a parallel algorithm based on photon map partitioning. The photon map was assigned to each processing element to reduce memory requirement, and the algorithm worked by using MPI. Following BIB006 , BIB018 presented a distributed out-ofcore stochastic progressive photon mapping method. The method was implemented to trace photons and eye rays in parallel programs in a portal-based system by automatically subdividing the scene geometry. BIB019 proposed another parallel photon-mapping rendering on a homogeneous multiprocessor SoC (MPSoC) platform which considers load balancing, less memory usage, and effective communication. There are several references on real-time image space photon mapping, such as McGuire and Luebke (2009) and BIB013 . Image space photon mapping instead scatters the photon distribution to the image space pixels they contribute to. These methods do not support area light sources or participating media, and they cannot simulate the full global illumination result.