chap-introductionGI.tex

%!TEX root = foo-thesis.tex

\chapter{Introduction to Global Illumination}
\label{chap:introductionGI}

This chapter starts by providing a brief overview of lighting techniques in computer graphics and locate and distinguish global illumination in this vast research field.
Subsequently, the foundation for the remainder of this work is laid by introducing the conceptual and theoretical foundations of global illumination in general and many-light methods in particular, combined with an overview of the related work on those topics.


\section{A High-Level Overview of Lighting in Computer Graphics}

Before examining the different lighting effects simulated in computer graphics, it is worth pointing out that in real-world physics, most of the distinctions made later in this section do not exist. Many effects and phenomena in lighting can be reduced to a basic set of interactions of photons, which are emitted by light sources and then reflected, refracted, or absorbed by matter.

In practice, simulating individual photons and atoms is obviously infeasible and unnecessary for most computer graphics applications. Instead, computer graphics researchers have examined the different real-world light phenomena and approximated them separately, using different approaches and approximations for each of them to stay within their respective performance budget.

In the following a brief and non-comprehensive overview of these lighting effects is provided and the term \textit{global illumination} is defined more precisely. The most top-level categorization of lighting effects divides them into the interaction of light with scene surfaces, and the transport of light through empty space in the scene.

\subsubsection{Light-Surface Interaction}

To determine how much and in what direction incoming light is reflected from surfaces, \textit{bi-directional reflectance distribution functions} (BRDFs) are used. While the recent shift to physically-based BRDFs has brought more unified models to real-time computer graphics, several materials such as transparent (e.\,g., glass) or highly translucent ones (e.\,g., skin) are still handled separately.


\subsubsection{Light Transport}

In order for light to interact with surfaces, it needs to be ``transported'' there from light sources. The simplest case, light that hits only one surface before reaching the camera, is called \textbf{direct light}. To determine surfaces that are directly lit by a certain light source, shadow maps are commonly used in real-time computer graphics. Direct light usually has a single point as origin in the case of point lights, or consists of entirely parallel light rays in the case of directional lights. This structuredness makes it relatively easy to compute, in terms of both complexity and performance.

\textbf{Indirect light} on the other hand has bounced off of at least two surfaces before reaching the camera. Since each point that is directly lit now reflects light into arbitrary directions, this process is much less structured and thus harder to compute. To manage this complexity, indirect light has been separated into small-scale and large-scale indirect light. An intermediate step for medium-scale indirect lighting has also been proposed \citep{reed:2012:mediumAO}.

The computation of \textbf{small-scale indirect light} has been made popular with \textit{screen-space ambient occlusion} (SSAO, \cite{Mittring:2007:Cryengine2}). While this should be more accurately described as small-scale indirect \textit{occlusion}, since it only darkens occluded areas, \textit{screen-space directional occlusion} (SSDO, \cite{Ritschel:2009:SSDO}) actually performs a form of indirect lighting, albeit a limited one. \citet{jimenez:2016:AO} has finally put this technique onto a physically based foundation.

Small-scale indirect lighting techniques such as SSAO are important for accentuating small geometric details in objects and providing a sort of contact shadow as a visual cue for the proximity of objects to each other.

In contrast, \textbf{large scale indirect lighting} provides more realistic lighting for entire scenes. While it has been computed in real-time for static scenes for a while, large-scale indirect lighting for fully dynamic scenes has yet to reach widespread use in real-time applications. More on this issue follows in the next section. The term \textbf{global illumination} (GI) has been used for varying sets of lighting effects throughout the literature. In this thesis, it is used to describe the lastly mentioned aspect, i.\,e., large-scale indirect lighting.



\section{Introduction to Global Illumination}

This section introduces global illumination by outlining its advantages and describing its theoretical foundations. Thereafter it gives a brief overview of techniques used previously to simulate (non-dynamic) global illumination before detailing the more recent related work in this field, and structures the process of computing global illumination by identifying individual building blocks. For a comprehensive introduction to global illumination, see \citet{Ritschel:2012:GISTAR}.

\subsection{Motivation}
The single overarching advantage of simulating global illumination in graphics applications is the added realism which leads to a host of benefits. An obvious one is the greater immersion achieved in movies and video games, but also architectural and e-commerce visualization applications can provide better assistance to its users through more realistic renderings. For instance, in architectural visualization, the colors of the furniture, carpets, decoration etc.\ are influencing the overall tone of the scene, e.\,g., by coloring the walls slightly, leading to a better basis for real-world design decisions.

Real-time techniques that allow camera movements in a given scene and lighting setup on the one hand enable approximating global illumination in applications that are inherently real-time, e.\,g., video games. On the other hand, even applications that do not require real-time frame rates can benefit from such techniques. For instance, while the features that are covered in this thesis are basically solved for offline rendering, the film industry can benefit from real-time global illumination techniques during production by means of faster testing of, e.\,g., different camera angles. Archviz applications can serve more use cases by implementing interactive walkthroughs.

Allowing changing geometry provides additional benefits: Games can create new experiences with changing level geometry, e.\,g., through destruction; level designers and lighting artists can expect a more natural workflow without having to resort to workarounds like fake lights; artists in filmmaking benefit from shorter iteration cycles; and visualization tools provide immediate feedback to changes in, e.\,g., interior decoration in the case of archviz.


\subsection{Theory}
\label{sec:intro:gi:theory}


% based on https://github.com/naps62/msc-thesis/tree/ee10a36eecbb691ba1a67b4c5367967023d07440/doc/common/equations
\newcommand{\dir}{\bm{\omega}} % directions are represented by greek omega character

\newcommand{\outgoingDir}{ \dir_o}
\newcommand{\incidenceDir}{\dir_i}

\newcommand{\outgoingRadiance}{  L_o(x, \outgoingDir)}
\newcommand{\emittedRadiance}{   L_e(x, \outgoingDir)}
\newcommand{\reflectedRadiance}{ L_r(x, \outgoingDir)}
\newcommand{\incidentRadiance}{  L_i(x, \incidenceDir)}

\newcommand{\brdf}{f_r} % brdf function name

\newcommand{\surfaceNormal}{\bm{n}}

This section will explain the significance of global illumination using the rendering equation \citep{Kajiya:1986:RenderingEquation}. The most basic form of the rendering equation is as follows:
%
\begin{equation}
\outgoingRadiance = \emittedRadiance + \reflectedRadiance\,,
\label{eq:renderBasic}
\end{equation}
%
where $L_o$ describes the outgoing radiance from a surface point $x$ in the direction $\outgoingDir$ as the emitted radiance $L_e$ plus the reflected radiance $L_r$. The significance of this equation comes from the fact that the outgoing radiance of a point towards the camera determines its color in a rendering.

The reflected radiance can be defined as
%
\begin{equation}
\reflectedRadiance = \int\limits_{\Omega} \brdf(x, \incidenceDir, \outgoingDir)\incidentRadiance (\incidenceDir \cdot \surfaceNormal) d \omega_i\,,
\label{eq:render}
\end{equation}
%
where $\Omega$ is the hemisphere located at point $x$ and oriented towards the surface normal $\surfaceNormal$ at point $x$, $\brdf$ is the BRDF of the surface and $L_i$ the incident radiance. While this is the most common representation of the rendering equation, \citet{Kajiya:1986:RenderingEquation} defined the reflected radiance using an integral over all surface points, not over all directions:
%
  \begin{equation}
    \reflectedRadiance = \int\limits_{S} \brdf(x, \incidenceDir, \outgoingDir) \incidentRadiance (\incidenceDir \cdot \surfaceNormal) V(x, x') d x'\,,
  \label{eq:renderWithVisibility}
  \end{equation}
%
where $\incidenceDir$ is redefined as the normalized difference vector between $x$ and $x'$ and $S$ is the (infinite) set of all surface points. Since not all surface points are visible from $x$, a visibility term $V$ has been added that is $1$ if $x$ and $x'$ are mutually visible, $0$ otherwise.

This equation illustrates a major difficulty when simulating global illumination, namely the integral that needs to be solved for the infinite set of surface points. To approximate this integral, often clusters of points are selected to form surface patches. Even then, the performance requirements are generally too high for real-time computer graphics. As a result, this integral is either solved in a preprocessing step for static parts of the scene, or solved only for the set of points that are considered light sources, discarding a large portion of the light energy in the scene and heavily biasing the rendered output. In fact, area lights are often ignored or approximated because they again would require solving this integral for an infinite number of points.

Another difficulty made explicit by \Cref{eq:renderWithVisibility} is the visibility term. Even with an algorithm that transfers light between points or surface patches at a sufficient resolution and sufficient speed, the visibility term requires the addition of another algorithm that tests for each pair of surface elements whether any other surface element is located between them. To perform such visibility tests efficiently, acceleration structures are needed that allow to quickly traverse the scene's geometry. However, these data structures are often difficult to update with dynamic geometry and do not map well to GPUs. This often makes visibility testing one of the most computationally intensive parts of global illumination algorithms.




\subsection{The Path to Real-Time Dynamic Global Illumination}

In interactive 3D graphics applications, global illumination has been ignored for a long time. To avoid completely unlit areas, an ambient term has been used that uniformly adds light to all surfaces.

For large-scale indirect lighting, light maps have seen widespread use since they have been introduced in the video game Quake \citep{Abrash:1997:BlackBook}. This technique is inherently static since the texturing of scene surfaces is an offline preprocessing step, and it is inherently large-scale since large texels are used to avoid excessive memory requirements.

Games have employed variations of \emph{precomputed radiance transfer} (PRT, \cite{sloan:2002:PRT}) to accommodate for changing lighting conditions. For instance, \citet{stefanov:2012:PRTinFarCry3} uses probes instead of the scene geometry to store the PRT results to be able to light dynamic objects. However, even though dynamic objects receive indirect lighting, they are unable to affect indirect lighting of other objects, a commonly made compromise.

Besides not fully supporting dynamic objects, the long precomputation times of conventional global illumination methods are a common hindrance in the workflow of artists. Global illumination techniques that support dynamic objects and require no expensive precomputation have yet to reach widespread use in real-time applications due to the high performance requirements.


\subsection{Components of Real-Time Dynamic Global Illumination}
\label{sec:intro:gi:components}

In order to better understand the next section discussing the current research around real-time dynamic global illumination, we have identified three stages that most real-time global illumination methods consist of:

\begin{description}
    \item[Direct lighting or light injection.] Since light sources can be very (if not infinitely) small and can be difficult to process for some techniques, the first step of the light propagation, sometimes called ``light injection'', can be separated and used to compute areas that are directly lit by the scene lights. These areas are then used as starting points for the global illumination algorithm. Other techniques use this approach purely as an optimization, since the first light bounce can be easier to compute than subsequent bounces.
    \item[Light propagation.] Starting from the light source or directly lit surfaces, this step sends out the light and records where it hits scene geometry. This might be done repeatedly to simulate multiple light bounces.
    \item[Final gathering.] Several techniques perform one last step that, instead of propagating light from lit surfaces into all directions, gathers light from lit surfaces into areas that are visible to the camera. This is a common optimization that guarantees that the calculations are relevant to the currently rendered frame, whereas the light propagation step is often more unguided and oblivious to the current viewport.
\end{description}%
%
Note that not all techniques implement all of these steps. For instance, performing direct lighting and a final gathering step while omitting the light propagation step is sufficient for simulating one indirect bounce. Brute-force ray tracing can be done by simulating only the light propagation step, and light propagation volumes (\Cref{sec:intro:gi:previousWork:lpv}) omit the final gathering step.

\vspace{\baselineskip}
\noindent
There are two more essential design decisions to be made:

\begin{description}
    \item[Visibility testing.] To prevent light from incorrectly shining through objects or walls, the visibility term in \Cref{eq:renderWithVisibility} needs to be solved. Since brute-force ray casting is prohibitively slow, it requires special acceleration structures or alternative approximations, like replacing ray casts with (a moderate amount of) shadow maps. As mentioned previously, this component uses a substantial if not most of the computation time for many of the global illumination approaches presented in the next section.
    \item[Choice of receiving elements.]
    The final gathering step collects light into areas that are visible to the camera. These areas can be represented by several forms of \textit{receiving elements}. Besides directly using pixels in screen space, other choices are texels in texture space, surfels or voxels in world or view space, or other virtual objects placed in the scene, e.\,g., in the form of spherical harmonics, which are then interpolated for shading individual pixels. Technically, the light propagation step also necessarily stores its results in some form of receiving elements, which might differ from the ones that are used during final gathering. In this thesis however, the term describes those data structures that are used to perform the actual per-pixel shading.
\end{description}%
%
As with most lighting concepts, real-time global illumination is often separated into diffuse and specular components, since the diffuse component is both easier to simulate with plausible results due to its low-frequency nature, and more important for the visual quality compared to the specular component. For the same reasons, only the diffuse component is covered in this thesis.

\vspace{0.3cm}

\section{Previous Work on Real-Time Dynamic Global Illumination}
\label{sec:intro:gi:previousWork}

This section presents previous work on global illumination while focusing on methods that work in real-time and support dynamic scenes, excluding many-light methods which are covered separately in the next section. A more comprehensive study of interactive global illumination methods is provided by \citet{Ritschel:2012:GISTAR}.

\subsection{Point-Based Approaches}

Based on the work of \citet{Bunnell:2005:AO}, point-based global illumination has been used for offline rendering in the film industry \citep{christensen2008point}.
Despite its name, the geometry representation used to approximate the scene geometry consists of disk-shaped surface elements (\emph{surfels}).
These surfels are then organized into the leaves of a tree structure, while the higher-level nodes are aggregate representations of all nodes they contain.
This tree is then used to compute visibility and propagate light between the surfels.

While \citet{Bunnell:2005:AO} propose a rough approximation for computing visibility, \citet{christensen2008point} employs ray tracing or spherical harmonics based on the distance between surfels to compute fairly accurate approximations of global illumination.
\citet{Ritschel:2009:microrendering} achieve interactive frame rates by utilizing the GPU to perform the final gathering step, which renders the scene into a \emph{micro-buffer} for each receiving element (in their case, screen-space pixels).
Due to the large amounts of surfels required and because the tree structure can be expensive to update when geometry moves, this technique is best suited for static or very small dynamic scenes.



\subsection{Light Propagation Volumes}
\label{sec:intro:gi:previousWork:lpv}

Initially proposed by \citet{Kaplanyan:2010:LPV} and extended by \citet{Kaplanyan:2010:LPV2}, this technique reduces the scene's geometry to two voxel grids, called \emph{light propagation volume} and \emph{geometry volume} respectively. Thereafter, light is injected from primary light sources into the light propagation volume, and the scene geometry is inserted into the geometry volume. With this, the light is iteratively propagated from each illuminated voxel to its neighboring voxels until the geometry volume indicates that the path is occluded. However, since inaccuracies of the propagation process accumulate over the iterations, this approach is inaccurate when dealing with long distances between sending an receiving surfaces.


\subsection{Voxel Cone Tracing}

Similar to light propagation volumes, the scene is first reduced to voxels and light from primary sources is injected. However, instead of propagating the light through the grid, the light is collected starting at receiving elements, usually pixels in screen space, by tracing cones through the grid.
While the original proposal \citep{Crassin:2012:OctreeVCT} uses a sparse voxel octree to represent the scene, \citet{Panteleev:2015:VXGI} introduces clip-maps that use several levels of equally-sized voxel grids to represent the scene with varying resolution depending on the distance to the camera.
Both approaches can compute specular reflections for moderately glossy surfaces. While the voxel octree is expensive to update with dynamic objects, the clip-maps are faster in this regard, but still need relatively large amounts of VRAM for higher quality levels. Lower quality levels result in noticeable voxelization artifacts.


\subsection{Ray Tracing}

Several attempts have been made to adapt ray tracing to be usable in real-time contexts.
\citet{Thiedemann:2011:VGI} trace rays through a voxel grid, but have to limit the ray's maximum distance for performance reasons and, similar to voxel cone tracing, suffer from high memory requirements.
\citet{Tokuyoshi:2012:pathtracingrasterization} trace rays using rasterization, but at the cost of a severe performance impact since they render the whole scene multiple times.
\citet{Chen:2016:Compactvoxels} use one bit per voxel to indicate whether it is opaque or not, and look up lighting information directly in an RSM during the final gather phase. They too achieve merely interactive frame rates.


\subsection{Radiance Caching}

Partly orthogonal to the previous sections, radiance caches are a different form of receiving elements that are placed in world or screen space and capture the incoming radiance. During actual shading, the nearest caches are interpolated. The major advantage is the reduction of the number of receiving elements for which incoming light needs to be gathered.
The original proposal cached irradiance values \citep{Ward:1988:IrradianceCaching}. The resulting loss of detail during interpolation and inability to compute specular reflections was overcome by radiance caching \citep{Krivanek:2005:RadianceCaching} at a performance loss. \citet{Scherzer:2012:PreconvolvedRadianceCaching} achieved real-time frame rates for static geometry and another improvement in efficiency was proposed by \citet{Rehfeld:2014:ClusteredPreconvolvedRadianceCaching}.
Radiance caching is orthogonal to the other techniques in so far as visibility still needs to be solved by other means, and using it introduces new problems such as temporal stability of the cache placement.


\subsection{Screen-Space Approaches}

Screen-space approaches inherently suffer from the lack of information about objects that are outside of the view frustum or occluded. The latter is alleviated by deep G-buffers \citep{Mara:2014:DeepGBuffers, Mara:2016:DeepGBuffers2}, but working only within the frustum, even this approach is limited to small to medium-scale indirect illumination.



\section{Introduction to Many-Light Methods}

This section will introduce many-light methods by first explaining the idea behind the technique and the effects that can be simulated, and then identifying the different components of a many-light rendering system.

\subsection{Overview}

Many-light methods as another means to compute global illumination originate in instant radiosity \citep{Keller:1997:InstantRadiosity}. In the original paper, photons are traced through the scene, similar to photon mapping \citep{Jensen:1996:PhotonMapping}. With each bounce, however, instead of storing the photon in a photon map, instant radiosity creates a new \emph{virtual point light} (VPL). These point lights illuminate the scene and thereby simulate light reflections (\Cref{fig:intro:many_lights_visualization}). While the concrete method of creating VPLs often differs, many-light methods share the idea of approximating various lighting effects through large numbers of VPLs.

\begin{figure}[htb]
\centering
  \begin{tabular}{@{}cc@{}}
    \includegraphics[width=.48\textwidth]{graphics/many_lights_laine_1} &
    \includegraphics[width=.48\textwidth]{graphics/many_lights_laine_2}\\
  \end{tabular}
  \caption{Illustration of the many-light concept. Left: VPLs are created on surfaces that are directly lit by a light source. Right: When shading a surface point (orange), all VPLs that are visible for that point are used to indirectly light it. Figures reprinted from \citet{laine2007incremental}.}
  \label{fig:intro:many_lights_visualization}
\end{figure}

\noindent
The use of many-light methods is intriguing since they are a natural and intuitive model of real-world light interactions. In addition the concept is highly scalable: Many-light methods have been used for real-time applications with up to a few thousand lights to offline rendering with millions of lights. Given a sufficient number of lights, the concept is capable of accurately simulating advanced effects like subsurface scattering and participating media. \citet{Dachsbacher:2014:ManyLightsSTAR} gives an overview of the higher-end spectrum of many-light methods.

When applied to real-time applications, the available performance budget enforces the use of a limited number of lights. With a few thousand lights at most, many effects are not possible to reasonably approximate anymore. However, the low-frequency nature of diffuse reflections enables several approximations and optimizations that make a convincing global illumination effect feasible to create. Using more or less conventional point light sources has another advantage, at least in the context of real-time applications: Many techniques from classical real-time rendering are applicable, such as point light rendering including conventional shadow maps for visibility testing. This allows for simple implementations of the basic concepts, even though more advanced techniques are necessary to achieve high performance and quality levels.



\subsection{Components of Many-Light Methods}
This section will take the components of global illumination identified in \Cref{sec:intro:gi:components} and explain how they translate to many-light methods. Two new components are added that are unique to many-light methods, namely VPL placement and mitigating singularities.

\begin{description}
    \item[Direct lighting or light injection.] In theory, many-light methods do not need a light injection step since they are usually iterative processes that start with the scene lights and from there on, create new lights wherever the current light set illuminates the scene. In practice, the first bounce is often handled separately for performance reasons, and because the VPLs have different characteristics than most scene lights.
    \item[Light propagation.] As just mentioned, many-light methods can simulate an arbitrary number of light bounces by repeating the propagation step with an expanding set of VPLs. However, many techniques (and this thesis) simulate just the first bounce, since that alone provides a large quality enhancement over simulating no global illumination at all, and subsequent bounces are more complex in terms of implementation and computation.
    \item[VPL placement.] Since the budget of VPLs is limited, it is desirable to get the maximum effect out of each VPL. Thus, much research has gone into placing VPLs where they contribute the most to the output image, while at the same time not introducing any bias. Both the light injection and light propagation step create VPLs and can take considerable amounts of computation time through complex sampling methods. Some techniques also do not distinguish between light injection and light propagation and have a unified process for placing VPLs.
    \item[Final gathering.] Most many-light methods perform final gathering per screen-space pixel. There are two main approaches commonly referred to as splatting and gathering. Both are too slow to use every light to shade every pixel, therefore optimizations and approximations are used. More on this in the next section.
    \item[Visibility testing.] Many-light methods provide no means of visibility computation; these need to be solved separately. The advantage of many-light methods is that each receiving element only needs to test the (bounded) number of VPLs for visibility, not an arbitrarily high number of scene elements. In contrast to other global illumination methods, this makes it possible (although not performant) to use shadow maps for visibility testing.
    \item[Choice of receiving elements.] As mentioned before, screen-space pixels are most commonly used, albeit often downscaled or combined with interleaved sampling (\Cref{sec:intro:relatedWorkManyLight:finalGathering}). The other options listed in \Cref{sec:intro:gi:components} are technically possible as well, but haven't been combined with many-light methods yet.
    \item[Mitigating singularities.] Since the entire energy of the indirect light bounces is concentrated into a few infinitely small light sources, the areas near these light sources receive too much light. This effect is distinctly visible as bright spots around the VPL's location (\Cref{fig:introGI:clamping}), making it necessary for many-light methods to alleviate this artifact.
\end{description}

\vspace{-5pt}

\begin{figure}[htb]
    \centering
    \begin{subfigure}[b]{0.32\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{graphics/clamping1-dachsbacher}%
        \caption{}
    \end{subfigure}%
    \hfill
    \begin{subfigure}[b]{0.32\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{graphics/clamping2-dachsbacher}%
        \caption{}
    \end{subfigure}%
    \hfill
    \begin{subfigure}[b]{0.32\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{graphics/clamping3-dachsbacher}%
        \caption{}
    \end{subfigure}%
    \caption{A rendering generated using a many-light method. (a) Naive approaches produce singularities near the VPL's location. (b) Clamping the light attenuation term makes the problem less apparent, but causes bias in the form of darkening in the corners and on the statue. (c) An unbiased rendering for comparison. Figure reprinted from \citet{Dachsbacher:2014:ManyLightsSTAR}.}
    \label{fig:introGI:clamping}%
\end{figure}%

\vspace{-10pt}

\section{Previous Work on Real-Time Many-Light Methods}
\label{sec:intro:relatedWorkManyLight}

This section will present several many-light methods while concentrating on those that are applicable to real-time rendering. It is structured roughly according to the different design decisions to be taken when applying many-light methods: VPL sampling, computing visibility, final gathering, and mitigating singularities. The light transport step is not covered separately as it is often either omitted, simulating only one bounce, or it is an integral part of the VPL sampling algorithm. The choice of receiving elements is not covered as well, as most papers in this area simply use screen-space pixels. \citet{Dachsbacher:2014:ManyLightsSTAR} provide another overview of many-light methods, including those unsuitable for real-time rendering.


\subsection{Virtual Point Light Sampling}
\label{sec:intro:relatedWorkManyLight:vplSampling}

While \citet{Keller:1997:InstantRadiosity} proposes an approach similar to photon mapping to create VPLs, real-time applications are in need of something more performant. A commonly used technique are \emph{reflective shadow maps} (RSMs, \cite{Dachsbacher:2005:RSM}), which use rasterization to create first-order VPLs. While in this paper, each pixel of the RSM is considered a VPL and during gathering, a random subset of all VPLs is sampled, beginning with \citet{dachsbacher2006splatting} most papers sample the RSM to create a fixed set of VPLs which is used during shading.

\citet{georgiev2010simple, ritschel2011ismsViewAdaptive} sample the RSM to create a set of VPLs with (estimated) high contributions to the final image. \citet{dong2009real, prutkin2012reflective} cluster several samples to form \emph{virtual area lights}. They observe that far fewer virtual area lights than VPLs are necessary to achieve the same quality at a minor performance expense.

Most of these approaches suffer from poor temporal stability. To improve on that, \citet{laine2007incremental} update only a portion of the VPLs per frame but introduce latency to the indirect light, additionally dynamic objects can receive but not bounce light. \citet{barak2013temporally} provide temporally stable results with dynamic scene geometry, but not with moving light sources. \citet{hedman2016sequential} achieve near-optimal temporal stability even with moving light sources while maintaining high per-image accuracy at real-time frame rates. They use one classic shadow map per VPL though, which must be updated lazily to stay within real-time limits.


\subsection{Final Gathering}
\label{sec:intro:relatedWorkManyLight:finalGathering}

Splatting techniques have been used to add a light's contribution to the rendered image \citep{dachsbacher2006splatting, Nichols:2009:splatting}, but do not utilize modern GPUs efficiently. Instead, gathering approaches are commonly used today, employing interleaved sampling \citep{Keller:2001:InterleavedSampling} to reduce the number of lights processed per pixel, in combination with an edge-aware blur similar to \citet{laine2007incremental}. \citet{segovia2006non} improve the cache efficiency of interleaved sampling.


\subsection{Visibility Computation}
\label{sec:intro:relatedWorkManyLight:visibility}

There are several approaches to calculate visibility between VPLs and the scene parts visible to the camera. Classic shadow maps are a fairly exact solution, but cannot be updated every frame for the several hundreds or even thousands of VPLs.

A popular approach are \emph{imperfect shadow maps} \citep[ISMs,][]{ritschel2008ism}, which use a precomputed set of points as scene representation to quickly render large amounts of small and inaccurate shadow maps. \citet{ritschel2011ismsViewAdaptive} extend the approach to fully dynamic scenes among other improvements. \citet{barak2013temporally} use tessellation to compute the point set, eliminating the need to keep a separate point set updated, making it inherently dynamic, and providing better performance for larger point sets.

Ray tracing has been proposed to compute visibility as well \citep[e.\,g.,][]{segovia2006bidirectional}, but suffers from the usual drawbacks of ray tracing in a real-time context. A voxel-based scene representation has also been used to perform visibility queries for many-light techniques \citep{sun2015manylightsSVO}.


\subsection{Mitigating Singularities}
\label{sec:intro:relatedWorkManyLight:singularities}

In naive implementations of many-light techniques, bright spots will appear near the VPL’s positions due to the light’s attenuation term approaching infinity. A common approach is to clamp the term (\Cref{fig:introGI:clamping}). This introduces bias, which can be compensated, e.\,g., in screen space \citep{novak2011screen}. Singularities can also be avoided through more advanced light representations \citep{tokuyoshi2015vsgl}.


\cleardoublepage