Efficient Ray Tracing Techniques

Eﬃcient Ray Tracing Techniques

Dario Seyb

August 14, 2016

Abstract

Ray Tracing is next to rasterization the most widely used technique to render computer generated images.

That is, to generate discrete 2D images from continuous 3D scenes. Until recently ray tracing was too

resource intensive to produce images in realtime, but advances in algorithms and hardware capabilities,

most notably the introduction of GPGPU (General Purpose Graphics Processing Units), made near-

realtime ray tracing feasible. In this report I will present some of the techniques which are used to achieve

this. Additionally I will provide an implementation of some of the presented techniques.

Keywords Ray Tracing, Acceleration Structures, Realtime Rendering, GPGPU

Contents

1 Introduction 1

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 A short history of ray tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Overview over the path tracing algorithm 3

3 Reducing Noise 4

3.1 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3.2 Temporal Supersampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2.1 Reprojection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2.2 Rejection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2.3 Combination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Acceleration Structures 7

4.1 Binary Space Partitioning (BSP) and KD-Trees . . . . . . . . . . . . . . . . . . . . . . . . 7

4.2 Bounding Volume Hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

5 Hierarchical data structures on the GPU 8

5.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5.2 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6 Results 9

7 References 10

1 Introduction

1.1 Motivation

Ray tracing is a technique used to synthesize photo-realistic images from a 3D scene description. This

is useful in many applications, from architectural visualization, games and movies to medical imaging.

While the rendered images are of very high quality, the time needed to produce even one frame of

animation is usually measured minutes or hours. Big animation studios like Disney or Pixa r can aﬀord

sup er computers to render their movies,

but this is no t feasible for sma ller companies or individuals.

http://www.engadget.com/2014/10/18/disney-big-hero-6/

Luckily, with the advent of ge ne ral purpose computation on consumer grade GPUs most people have a

small super computer sitting in their PCs. The new NVIDIA GTX 1080 for exa mple can do about 9

TFLOP/s,

as many as the fastest super computer in the world in 2001.

Real time ray tracing is appealing, especially in the context of creative wor k, because it allows artists

to preview changes to the scene immediately. Where you previously had to change the position or color of

a light and wait until the next day to review the diﬀerence you can now tweak scenes interactively. This

leads to a lower turn around time on changes in visuals and thus higher quality re sults. In this report I

will:

Describe a state of the art ray tracing algorithm. (Section 2)

Explain how to use the fact that the algorithm is running at interactive frame rates to improve

image quality. (Section 3)

Introduce techniques to re duce the time spent on ray-scene intersections. (Section 4)

Give an overview of how to parallelize the construction and traversal of acceleration structures

(Section 5 )

Present an implementation which incorporates the ideas described in this report. (Section 6)

1.2 A short history of ray tracing

The technique of tracing rays throug h a scene consisting of primitives and media has been known to the

computational physics community for a long time. There it is mostly used to simulate the propagation

of waves (e.g. shock waves of an earthqua ke) throug h a heterogeneous medium (e.g. the interior of the

earth) [Bul37].

It was ﬁrst described in relation to computer graphics by Arthur Appel in 1968 [App68]. At the time

the common method to visualize three dimens ional scenes was to synthesize two dimensional line and

point drawings. Appel re cognized the importance of shading and shadow casting in conveying s hape and

spatial relations. In his paper ”Some techniques for shading machine renderings of solids” he proposed a

method to r ealize this shading by casting rays originating from the viewers’ position through each pix el

on the viewing plane and ca lc ulating the ﬁrst point of intersection with the scene. To determine shading

he casts a second ray from this intersection point to the lig ht s ource. Appel’s technique was very compute

intensive for its time, but already illustra ted the power of ray tracing to generate realistic imag es using

a relatively simple alg orithm.

Figure 1: Left: Direct lighting only, Right: Full global illumination

The next major contribution to ray tr acing came from Turner Whitted of Bell La boratories in 1980.

In his landmark paper ”An Improved Illumination Model for Shaded Display” [Whi80] he described the

algorithm that would become known as Recursive, or Whitted, Ray Tracing. Previously ray tracing was

only used to compute local illumination at the ﬁrst point of intersection and the only secondary rays that

were cast were shadow rays. This produced a fairly good approximation for diﬀuse surfa ces, but was

https://twitter.com/nvidia/status/728771223522410496

http://www.top500.org/

lacking in sc enes with very reﬂective objects. Whitted took the conce pt of casting secondary rays and

extended it to reﬂections and refractions. For each intersection point he proposed to not only compute

a shadow ray in the direction of each light source, but also r e cursively compute the color of incoming

reﬂected and re fracted light. This technique produced impressive looking results, but Whitted himse lf

acknow ledged tha t it did not provide a solution to global illumination since objects could not act as

light sources themselves and diﬀuse interreﬂections were not accounted for. Figure 1 shows the diﬀer ence

between direc t illumination only and global illumination. It highlights why I chose to implement a solution

which provides full global illumination. The indirect light is very important for the realistic appearance

of a scene and something that can not be solved easily with rasterization approaches.

Over the following years many diﬀerent approaches to solve this iss ue were proposed and in 1986 James

T. Kajiya published a paper titled ”The Rendering Equation” [Kaj86] in which he presents an equation

to describe the propagation of light in a scene. It is genera l enough to describe all optical phenomena we

care about in computer g raphics and this made it possible to classify rendering algorithms by how well

they approximate a solution to the rendering equation Eq. (1).

I(x, x

′

) =

Geometry Term

}| {

g(x, x

′

)[ǫ(x, x

′

)

{z }

Emission

BRDF

}| {

ρ(x, x

′

, x

′′

)

Incoming light

}| {

I(x

′

, x

′′

) dx

′′

{z }

Light reﬂected at x

′

in direction

−→

′

] (1)

It describes the light trans port between two points x and x

′

as a combination of emitted and reﬂected

light at x

′

. The geometry term describe s the amount of light that actually arrives at x (e.g. g(x, x

′

) = 0

if there is an object between the two points). To compute the reﬂected light we need to integrate over all

directions in the hemisphere S above point x

′

. The main diﬀerence between rendering algorithms is how

they approach the evaluation o f this integral. It cannot be evaluated analytically for scenes which are

even re motely interesting, but the formulation of the rendering problem as an integral equation allows us

to employ methods from calculus to devise new algorithms.

2 Overview over the path tracing algorithm

Path tracing is an algorithm which solves the integral in Eq. (1) by randomly sampling it. This pr ocess

is also called ”Monte C arlo integration”. [Vea97] The mathematical basis for Monte Carlo integration is

illustrated in Equation (2). We k now from basic statistics that the expected value of a function f is the

integral of that function times the probability distribution p from which the random samples are dr awn.

E[f(x)] =

f(x)p(x)dx ≈

i=1

f(X

), X

∼ p (2)

Since we want to compute an approximate value for

f(x)dx we are actually looking for the expected

value of

f (x)

p(x)

as shown in Equation (3).

f(x)dx =

f(x)

p(x)

p(x)dx ≈ E

[

f(x)

p(x)

] =

i=1

f(X

)

p(X

)

, X

∼ p (3)

Each sample is represented by a list of points (x

, ..., x

), x

∈ R

which form a path through space.

This is similar to Whitted Ray Tracing, except that the po ints are randomly chosen instead of being

predetermined by the reﬂection and refraction directions. The ﬁnal value of a path sample is calculated

using Equation (1), recursively evaluating it fro m x

to x

. In Figure 2 an example o f such a r andomly

generated path is shown. Note that this path contributes to the ﬁnal image since it starts at the eye and

ends on a light source.

In classical path tracing paths start at a point on the image plane . A ﬁrst intersection point in the

scene is calculated. At this point a scattering event is simulated. This is done by randomly choosing a

new dire ction with a distribution which depends on the material of the hit object. The next intersection

is calculated based on the chosen direction.

A path is terminated when it reaches a light source, the maximum path length is reached or no

intersection is found. The reason why paths start at the camera is that a path which starts at some point

on the surface of a light source is very unlikely to hit the image plane and thus likely to not contribute to

Figure 2: A light path through a scene which contributes to the ﬁnal image.

the image. More sophisticated methods like Bidirectional Path Tracing start rays at both ends and try

to connect them. They produce better results, but ar e harder to implement, espe cially on GPGPUs.

3 Reducing Noise

For classical path tracing to c onverge to a stable solution we need to sample thousands of paths for each

pixel. Since sampling a path requires intersection tests which are already the bottleneck of the pipeline

(see Se ction 4) this is not something we can aﬀord under the constr aints of real time rendering. The

lack of samples results in a high variance betwee n pixels which is expressed as noise. As des c rib e d in

[Sim+97] uniform noise is one of the more pleasant artifacts to human vision, but it still impacts the

perceived quality of rendered images . In the following I will des cribe two approaches to reduce variance

and improve ima ge quality without sampling more paths.

Reducing the variance of the sampled paths by carefully choosing the sampled distribution in

our Monte Carlo integrator.

Reusing samples from prev ious frames and thus reducing variance by having a lar ger number of

samples for each pixel.

Figure 3 shows what we can achieve with the noise reduction techniques presented in this report. It

should serve as a motivation for why noise reduction is instrumental in achieving acceptable images in

real time path tracing.

Figure 3: Left: No noise reduction, Right: Importance sampling and temp o-

ral supersampling

3.1 Importance Sampling

In his thesis Eric Veach pre sents a numbe r of ways to reduce variance in Monte Carlo algorithms. [Vea97,

pp. 45–70] I will foc us on importance sampling [Vea97, pp. 47–48], because it is easy to integrate into

existing algorithms. Other techniques such as Bidirectional Path Tracing or Metropolis Light Transport

produce better results, but are more complicated to implement correctly, especially on the GPU.

The idea of importance sampling is to concentrate our eﬀorts on parts of the integral in Equation (1)

which have a large value. That is , we would rather sample paths which contribute a lot to the image than

paths which barely do. To achieve this we choose a function p that is a s similar as possible to the function

f we want to evaluate and which can be sampled eﬃciently. A c ommon technique is to approximate or

disregard factors in f until we arrive at a function which can b e integrated analytically. The mathematical

reasoning for why a p with f(x) ∝ p (x) would be ideal is given in Eq uation (4).

V (

f(x)

p(x)

) =

f(x)∝p(x)

V (c) = 0 (4)

As such, if f is proportional to p the variance of the resulting Monte Carlo integrator is 0. It is easy

to show that this is a continuous relation, i.e. the closer f and p get to being proportional, the lower the

variance. Figure 4 illustrates this visually.

120

150

180

0 0.2 0.4 0.6 0.8 1

Figure 4: Approximating a complicated function f by a simpler function p

and sampling f based on the probability distribution of p. Note how we are

more likely to sample the f in directions where it has a large value.

In the case of path tracing f = ρ(x, x

′

, x

′′

)I(x

′

, x

′′

) where ρ is a BRDF. The factor of f that makes

it especially hard to integrate analytically or approximate is I(x

′

, x

′′

) since I is deﬁned recur sively (see

Equation (1)). If we disregard I(x

′

, x

′′

) we are left with ρ(x, x

′

, x

′′

) which is much easier to reason about.

While not all BRDFs can be solved analytically (as no ted in [MU12]) they are usually designed to be

sampled w ith a given probability distribution, which gives us the approximation p we were looking for.

The most basic example of importance sampling is using the fact that all BRDFs must account for

Lambert’s cosine law. Just by using an appropriate distribution for our outg oing directions we can reduce

the variance dramatically since we avoid sa mpling rays which a re almost parallel to the surface and thus

don’t contribute much to its illumination. The diﬀere nc e is quite subtle in Figure 5, but even at just

50 samples per pixels the right image is a lot less noisy, compared to the left image which uses uniform

sampling.

Figure 5: Left: Uniform Sampling, Right: Cosine Weighted Samp ling

To keep the expected value of the Monte Carlo integration the same we need to account for the fact

that we are no longer sampling f uniformly. This is done by adjusting the probability distribution p in

Equation (3 ).

f and p are chosen for illustration purposes only and are not sup posed to represent an actual BRDF.

There is a lot of value in ﬁnding a good approximation to a BRDF since sampling even relatively

complex approximations is very cheap compared intersection tests. Better importance sampling directly

correlates with les s variance and thus reduces the number of needed path samples per pixel dramatica lly.

3.2 Temporal Supersampling

Ray tracing research has mostly focused on the previous area for variance reduction since the common

use case is rendering still images. In real time rendering we are generating an output image 30-6 0 times

per second. Usually the changes between frames are small (i.e. we can assume temporal cohe rency).

Classical ra sterization based rendering pipelines re-render the whole image every fr ame and disregard

previous results completely. This has established itself since samples per pixel tended to be cheap and

the complexity of r eusing samples was not worth the potential quality improvements. In recent years

this no lo nger holds true. The introduction of expensive physically bas ed shading computations, even in

real time applications, made per pixel s ampling a performance issue. Previously issues like geometry and

shading aliasing could be solved by sampling the scene multiple times per pixel, but this is not feasible

any more.

The idea of temporal supersampling is to spread the cost of calculating s amples over time. If we store

a numbe r of samples from previous frames some of these samples are likely to be relevant to the current

frame due to temporal coherency. If we can ﬁgure out which sa mples are relevant and which aren’t we

can get more samples for the current frame for the cost of retrieving them from a buﬀer. This is much

cheaper than computing them from scratch. T here are three steps to temporal supersampling:

1. Reprojection: Figure out the most relevant sample pos ition in our history data and sample the

history buﬀer at that position.

2. Rejection: Reject inva lid history samples based on some rejection strategy.

3. Combination: Combine the history samples with the sa mples for the current frame.

3.2.1 Reprojection For each visible surface point p in Frame t we want to determine its clip space

position in Frame t − 1. We assume that this is where the most relevant data for this point is stor ed in

the history buﬀer. To determine this position we need to store the previous frames projection and view

matrices P

t−1

and V

t−1

for the camera and the prev ious model matr ices M

t−1

for each object O

. With

that information we can compute the previous clip space location of p as C

t−1

(p) = P ∗ V

t−1

∗ M

t−1

∗ p.

We usually store a buﬀer of oﬀsets M

(p) = C

t−1

(p)− C

(p) called ”motion vectors”. This allows temporal

sup ersampling to be implemented as a post processing step.

3.2.2 Rejection The assumption we made during reprojection breaks down in two cases: The pre vious

clip s pace position is oﬀ screen (which means p was not visible in the last fra me because it was outside

the camera frustum) or the depth stored in the history buﬀer does not match the computed depth (which

means p was occluded by some other surface). We need to detect these cases and reject the samples.

There are also other, c olor based, rejection strategies like neighborhood clamping [Kar14]. Those do not

work well with path tracing since they assume low va riance on smooth surfaces which the samples from

path tracing do n’t provide.

3.2.3 Combination Once we have identiﬁed a valid history sample we need to combine it with the new

samples from the current frame. A common approa ch to this is to use a rec ursive expo ne ntial smoothing

ﬁlter [Yan+09]

(p)) = αs

(p) + (1 − α)(f

t−1

(p) + M

(p))) (5)

Where f

is the value of the frame/history buﬀer in frame t and s

the new sample value. The

smoothing factor α pre sents a trade oﬀ between responsiveness (high α) and var iance reduction (low α).

It can either b e set statically or be determined dynamically by s ome he uristic. A rejected history sample

corres ponds to α = 1.

4 Acceleration Structures

After employing the noise reduction techniques presented in the previous section we are able to render

simple scenes in real time to an acceptable level of quality. Unfortunately more complex scenes quickly

become too expensive to render. This is becaus e intersection tests are by far the most expensive part

of any ray tracing algorithm [Whi80, p. 7]. While this is true even for simple scenes, it becomes a

major performance issue in lar ge scenes. Ideally we would like the performance of a ray tracer to be

independent from scene complexity, but this is not possible when using a classical polygon based scene

representation. Rasterization renderers usually per form a culling operation to exclude objects which are

not in view of the camera from which is being render ed. Unfortunately that is not helpful for path tracing

since secondary rays can require intersection tests with oﬀ-screen objects. The naive implementation of

a ray cast performs an intersection test with eve ry primitive in the s cene. Hence it scales linearly with

the number of primitives. Acceleration structures which partition either objects or space a llow us to do

better. They gene rally reduce the time complexity of a ray cast fro m O(n) to O(log n) in the number of

primitives. In the following I will discuss various commonly used acceleration structures. The main trade

oﬀ is usually cons truction time versus ray tracing performance. Generally, s tructures which oﬀer better

ray tracing performance take longer to set up and ar e mostly suited for static scenes , while structur es

which trade in some ray tracing performance for shorter set up times are better suited for real time

applications and dynamic scenes [Kar12].

4.1 Binary Space Partitioning (BSP) and KD-Trees

The ﬁrst class of acceleration structures are space partitioning trees. They split the scene into smalle r

and smaller s ub-spaces which are wholly contained in their parent space as s hown in Figure 6. It is also

recorded which objects be long to which sub-spa ce. Once the tr ee is constructed a ray-scene intersection

algorithm can start at the root node and o nly traverse into sub trees if the ray intersects with their

parent node. Actual ray-primitive intersection tests are only nec essary once a leaf node is reached. If

the tree is well c onstructed this reduces the number of inters ection tests dramatically. BSP Trees split

space recur sively along splitting planes. In the general BSP tree the orientation of the splitting plane can

be cho sen freely. KD-trees are a subclass of BSP trees where the splitting planes are axis aligned. This

makes kd-trees substantially easier to construct since there are less degrees of freedom for the splitting

planes. The drawback is that there are situations w he re a BSP tree might be faster to traverse than a

kd-tree. Algorithms which co nstruct an optimal kd-tree ar e NP complete. In practice heuristics are used,

the most succe ssful one being the surface area heur istic [MB90].

Figure 6: A kd-tree built around three objects.

Eﬃcient trave rsal is achieved by always traversing the child node which lies closer to the ray origin

ﬁrst.

4.2 Bounding Volume Hierarchies

On a ﬁrst glance BVHs loo k very similar to BSP tree s. The diﬀerence is that BVHs group objects together

while BSP trees split spa ce recursively. Figure 7 shows such a BVH which co ntains the same objects as

the kd-tree in Figure 6. A common choice for bounding volumes are spheres and axis aligned bounding

boxes because they are cheap to construct, require little additional memory and their ray intersection

tests are fast. More complex bounding volumes like object oriented bounding boxes, discrete oriented

polytopes or c onvex hulls are attractive because while they can provide a tighter ﬁt, this is usually far

outweighed by the added complexity and storage requirements. Again, algorithms which ﬁnd optima l

BVHs are NP co mplete and heuristics have to be used.

Figure 7: A sphere based BVH built around the same three objects as in

Figure 6.

5 Hierarchical data structures on the GPU

The naive path tracing algo rithm is easily adapted to the GPU. The massively parallel architecture maps

nicely to computing many independent path samples. In my implementation I start one compute shader

thread for each pixel in the output image. The ma in issue with porting ray tracing algorithms in gener al

is that acceleration structure form trees, which don’t map nicely to the linear, po inter restricted memory

model of a GPU. Especially building such data structures on the GPU is diﬃcult, since parallelizing the

classical construction algorithms is often non-trivial if not impossible. [Kar12, p. 1]

5.1 Construction

Karras [Ka r12] presents a method which aids in the parallel construction of both bounding volume

hierarchies as well as spa c e partitioning trees. He constructs an ordered binary radix tree c ontaining a

Morton code for e ach primitive and shows how this construction can be distributed on n- 1 threads (where

n is the numb er of primitives). This maps very nicely to GPU architectures since the number of threads is

known in advance and the tree c onstruction can be achieved in one co mpute shader dispatch. One of the

possible outputs of this metho d is a kd-tree with n-1 internal nodes (one node per thread). Unfortuna tely

Karras does no t analyse the ray tracing performance of the generated tree s. Figure 8 shows the steps

needed for this algorithm.

1010

1000

0010

0000

1011

1001

0011

0001

1110

1100

0110

0100

1111

1101

0111

0101

0100

1001

1111

Figure 8: Steps of constructing a kd-tree as described in [Kar12]

1) Assign a Morton code t o each object.

2) S ort objects and insert into binary radix tree

3) Construct kd-tree.

The sorting step can be done parallelized by using some parallel sorting technique like the one intro-

duced in [MG10].

5.2 Traversal

Once we have constructed an acceleration structure we need to ﬁnd an eﬃcient way to traverse it and

ﬁnd the closest intersection with a ray. For this report I will focus on traversing kd-trees , since ”[they are]

the best general purpos e acceleration structure for CPU raytracers” [FS05] and a kd-tre e is one of the

outputs of the algorithm described in the previous section. The classical traversal algorithm requires a

stack to store nodes which still need to be processed. Due to the high number of rays which are process ed

in parallel on the GPU, a sta ck per ray is not feasible . This is why stackless traversal algorithms are

necessary for eﬃcient GPU ray tracing. One such algorithm is introduced by Popov et al. [Pop+07]. They

not only describe a technique which can travers any kd-tree without needing a stack, but also propose an

eﬃcient memory layout, taking the peculiarities of modern GPUs into consideration. A usual limitation

of stackless traversal algorithms is the need to ”restart” a traversal when a leaf is reached, since we cannot

store which internal nodes to travers next.

Popov et al. [Pop+07] get around this by storing additional information, so called ”r opes”, in each

leaf. Ropes are pointers to the spatially adjacent nodes of a leaf. Once a leaf is reached during regular

traversal we can move to the next node by following the appropr iate rope based on the ray direction.

This reduces the time spent on ”re-traversing” the tr ee immensely. They also propos e an eﬃcient post-

processing algorithm to add ropes to any kd-tre e. Figure 9 shows the steps taken when intersecting one

ray with the acceleration structure. Note that there is no stack needed thanks to the ro pes.

Figure 9: Traversing a kd-tree with ropes as proposed by Popov et al.

[Pop+07]. The ﬁrst leaf is found as usual, afterwards we follow a rope in

the appropriate direction instead of moving back up the tree.

6 Results

To familiarize myself w ith the techniques I describe in this paper I implemented a real time path tracer

using C++ and O penGL. The source code can be found at https://github.com/daseyb/pro-se-cg. Much

of the code is based on the edge-of-spac e engine [SSG16] which was built for the game programming

module at RWTH Aachen in WS 15/1 6. The ma in features are:

Real time rendering of triangle models using path tracing.

An interactive c amera sy stem.

Shader hot reloading for fast iteration times.

A ﬂexible mater ial system supporting reﬂection, transmission and emission.

GPU based acc eleration structures as described in this report.

Note that all images presented here are created with my own renderes. Zaphod ([Sey16b]) for oﬄine

rendering and Orion ([Sey16a]) for real time re ndering. Please consult the respective project pages for

more info rmation, since unfortunately a detailed description of my implementation is out of sco pe for this

report.

7 References

References

[App68] Arthur Appel.“Some Techniques for Shading Machine Renderings of Solids”. In: Proceedings of

the April 30–May 2, 1968, Spring Joint Computer Conference. AFIPS ’68 (Spring). Atlantic

City, New Jersey: ACM, 1968, pp. 37–45. doi: 10 . 1145 / 1468075 . 1468082. url: http :

//doi.acm.org/10.1145/1468075.1468082.

[Bul37] K. E. Bullen. “Seismic Ray Theory”. In: Geophysical Journal International 4 (1937), pp. 93–

105. issn: 1365-24 6X. doi: 10.1111/j.1365-246X.1937.tb07106.x. url: http://dx.doi.

org/10.1111/j.1365-246X.1937.tb07106.x.

[FS05] Tim Foley and Jer emy Sugerman. “KD-tree Acceleration Structures for a GPU Raytracer”. In:

Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware.

HWWS ’05. Los Angeles, California: ACM, 2005, pp. 15–22. isbn: 1-59593-086-8. doi: 10.

1145/1071866.1071869. url: http://doi.acm.org/10.1145/1071866.1071869.

[Kaj86] James T. Kajiya. “The Rendering Equation”. In: SIGGRAPH Comput. Graph. 20.4 (Aug.

1986), pp. 143–150. issn: 0097-8930. doi: 10.1145/15886.15902. url: http://doi.acm.

org/10.1145/15886.15902.

[Kar14] Brian Karis.“High Quality Temporal Sup e rsampling”. In: (2014). url: https://de45xmedrsdbp.

cloudfront.net/Resources/files/TemporalAA_small-59732822.pdf.

[Kar12] Tero Karras. “Maximizing Parallelism in the Construction of BVHs, Octrees, and K-d Trees”.

In: Proceedings of the Fourth ACM SIGGRAPH / Eurographics Conference on High-Performance

Graphics. EGGH-HPG’12. Paris, France: Eurographics Associatio n, 2012, pp. 33–37. isbn:

978-3-905674-41-5. doi: 10.2312/EGGH/HPG12/033- 037. url: http://dx.doi.org/10.

2312/EGGH/HPG12/033-037.

[MB90] J. David MacDonald and Kellogg S. Booth. “Heuristics for ray tracing using space subdivi-

sion”. In: The Visual Computer 6.3 (199 0), pp. 153–166. issn: 1432-2315. doi: "10.1007/

BF01911006. url: http://dx.doi.org/10.1007/BF01911006.

[MG10] Duane G. Merrill and Andrew S. Grimshaw. “Revisiting Sorting for GPGPU Stream Archi-

tectures”. In: Proceedings of the 19th International Conference on Parallel Architectures and

Compilation Techniques. PACT ’10 . Vienna, Austria: ACM, 2010, pp. 545–546. isbn: 978-

1-4503-0178-7. doi: 10 . 1145 / 1854273. 1854344. url: http : / / doi . acm . org / 10 . 1145/

1854273.1854344.

[MU12] Rosana Montes and Carlos Ure˜na. “An Overview of BRDF Models”. In: (20 12).

[Pop+07] Stefan Popov et al. “Stackless KD-Tree Traversal for High Performance GPU Ray Tracing”.

In: Computer Graphics Forum. Vol. 26 . 3. Wiley Online Library. 2007, pp. 415 –424.

[Sey16a] Dario Seyb. Orion Raytracer Code. 2016. url: http://github.com/daseyb/pro- se- cg

(visited o n 08/10/2016).

[Sey16b] Dario Seyb. Zaphod Raytracer Code. 2016. url: http://github.com/daseyb/zaphod.

[SSG16] Da rio Seyb, Kaspar Scharf, and David Gilbert. Edge of Space. 2016. url: https: / / www.

graphics.rwth-aachen.de:9000/dseyb/edge-of-space (visited on 06/03/2016).

[Sim+97] Enrico Simonotto et al. “Visual Perception of Stochastic Resonance”. In: Phys. Rev. Lett. 78

(6 1997 ), pp. 1186–1189. doi: 10.1103/PhysRevLett.78.1186. url: http://link.aps.org/

doi/10.1103/PhysRevLett.78.1186.

[Vea97] Eric Veach.“Robust monte carlo methods for lig ht transport simulation”. PhD thesis. Stanford

University, 1997.

[Whi80] Turner Whitted. “An Improved Illumina tion Model for Shaded Display”. In: Commun. ACM

23.6 (June 1980 ), pp. 343–349. issn: 0001-0782. doi: 10.1145/358876.358882. url: http:

//doi.acm.org/10.1145/358876.358882.

[Yan+09] Lei Yang et al. “Amortized Supersampling”. In: ACM SIGGRAPH Asia 2009 Papers. SIG-

GRAPH Asia ’09. Yokohama, Japan: ACM, 2009, 135:1–135:12. isbn: 978- 1-60558-858-2. doi:

10.1145/1661412.1618481. url: http://doi.acm.org/10.1145/1661412.1618481.