Efficient Divide-And-Conquer Ray Tracing using Ray Sampling
Kosuke Nabata∗
Wakayama University

Yoshinori Dobashi
Kei Iwasaki†
Wakayama University/UEI Research
Hokkaido University/JST CREST
Tomoyuki Nishita
UEI Research/Hiroshima Shudo University

Abstractrays in the subproblem. This results in a waste of computationaltime on ray traversal, which is inefficient especially for a large number of rays. Recent demands on high resolution images require alarge number of rays for ray tracing. Moreover, anti-aliasing methods that are used to improve the image quality usually require multi
sampling and super sampling, resulting in the generation of a large
number of rays.

Divide-and-conquer ray tracing (DACRT) methods solve intersection problems between large numbers of rays and primitives byrecursively subdividing the problem size until it can be easily
solved. Previous DACRT methods subdivide the intersection problem based on the distribution of primitives only, and do not exploit
the distribution of rays, which results in a decrease of the rendering performance especially for high resolution images with antialiasing. We propose an efficient DACRT method that exploits the
distribution of rays by sampling the rays to construct an acceleration data structure. To accelerate ray traversals, we have derived a
new cost metric which is used to avoid inefficient subdivision of theintersection problem where the number of rays is not sufficiently
reduced. Our method accelerates the tracing of many types of rays
(primary rays, less coherent secondary rays, random rays for pathtracing) by a factor of up to 2 using ray sampling.

To address this problem, our method exploits the distribution ofrays by tracing a small subset of rays, that is, a sample of the rays.
The main contribution of our method is that it derives a new cost
metric that can be used to detect and avoid the inefficient subdivision of problems where the number of rays has not been sufficiently
reduced. Our cost metric can be represented by a simple formulaand easily estimated. Before partitioning the set of primitives andconstructing a hierarchical acceleration data structure for the primitives, a small subset of rays is traced and information about the rays
obtained (e.g. the ratios of rays intersecting each bounding volumeof the partitioning candidates of the set of primitives).

CR Categories: I.3.7 [Computer Graphics]: Three-Dimensional
Graphics and Realism—Raytracing

To partition the primitives efficiently, the distribution of rays as wellas the distribution of primitives is utilized, whereas the previous
methods calculate the partitioning by assuming a uniform distribution of rays. In addition, the distribution of rays is utilized to determine the traversal order. Our experimental results demonstratethat the tracing of many types of rays such as primary rays, lesscoherent secondary rays (e.g. rays for specular reflection, ambient
occlusion, area light source, depth of field), and random rays, canbe accelerated up to a factor of 2 using our ray sampling method.

Keywords: ray tracing, divide-and-conquer algorithm, ray sampling

1

Introduction

Recent advances in ray tracing have led to the achievement of interactive performance for both static and dynamic scenes, by using acceleration data structures such as grids [Wald et al. 2006; Kalojanov
et al. 2011], kd-trees [Shevtsov et al. 2007; Zhou et al. 2008], andbounding volume hierarchies (BVHs) [Wald 2007]. These methods
construct and store acceleration data structures before ray tracing.

The contributions of our method are as follows.
• A concept of ray sampling is introduced. Our ray sampling
method during acceleration structure construction and traversal improves the performance of tracing coherent rays, lesscoherent secondary rays, and incoherent rays.

In recent years, alternative approaches that do not store auxiliary
data structures have been proposed [Mora 2011; Keller and Wachter
2011; Afra 2012]. These approaches, called divide-and-conquer ray
tracing (DACRT), calculate the intersection tests between a set ofrays and a set of primitives based on the divide-and-conquer algorithm. DACRT solves an intersection problem between a set of rays
and a set of primitives by subdividing the problem into subproblems whose problem sizes (i.e. the numbers of rays and primitives)
are smaller. DACRT subdivides the intersection problem by partitioning the set of primitives, and simultaneously traversing the setof rays.

• A new cost estimator is derived to avoid the inefficient subdivision of intersection problems in which the number of rays is
not sufficiently reduced at the cost of intersection tests. The
cost estimator is simple and therefore our method can easily
be incorporated into the original DACRT method.
The performance gain of our method increases as the number ofrays increases, which is beneficial for high resolution images andanti-aliasing using super sampling and multi sampling.

2

Previous DACRT methods subdivide the problem based on the distribution of primitives only, which may not reduce the number ofPrevious Work

Many previous ray tracing methods construct and store acceleration data structures before tracing of the rays. Uniform grids [Fujimoto et al. 1986], kd-trees [Bentley 1975], and BVHs [Rubin andWhitted 1980] are widely used for acceleration data structures. For
static scenes, the acceleration data structure can be precomputed
and the computational time for this does not impact on the rendering frame rate. On the other hand, for dynamic scenes, the acceleration data structure must be built from scratch or updated for eachframe. Therefore, the construction time and the time for ray tracing
impact on the rendering frame rate, and fast construction methods∗ e-mail:s141044@center.wakayama-u.ac.jp† e-mail:iwasaki@sys.wakayama-u.ac.jp

Permission to make digital or hard copies of part or all of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor commercial advantage and that copies bear this notice and the full citation on thefirst page. Copyrights for components of this work owned by others than ACM must be
honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on
servers, or to redistribute to lists, requires prior specific permission and/or a fee.
Request permissions from permissions@acm.org.
HPG 2013, July 19 – 21, 2013, Anaheim, California.
Copyright © ACM 978-1-4503-2135-8/13/07 $15.00

129

rays

bounding volume

recursively breaks down the problem to be solved until it can besolved easily. For DACRT, the problem to be solved is the intersection tests between a set of primitives and a set of rays. Although
DACRT can deal with arbitrary primitives, triangles are usuallyused as primitives. DACRT recursively partitions the set of triangles into subsets and partitions the set of rays that intersect thebounding volume (BV) of the set of triangles, until the number oftriangles or the number of rays is sufficiently small for the intersection tests between the triangles and the rays to be easily calculated.
DACRT partitions the set of triangles by using a tree structure suchas kd-trees [Mora 2011] or BVHs [Afra 2012]. Leaf nodes of thetree structure store the triangles and each interior node of the tree
structure is associated with a bounding volume that encloses thetriangles in the descendant leaf nodes. Partitioning of the set oftriangles affects the ray tracing performance. To determine an efficient partitioning, the cost function of the node associated with thebounding volume V is defined as follows.

acve rays

paron a set of triangles

ray ﬁltering

Figure 1: An overview of DACRT. A single partitioning step (center) and ray filtering (right).
for grids [Wald et al. 2006; Lagae and Dutré 2008; Kalojanov andSlusallek 2009], kd-trees [Hunt et al. 2006; Shevtsov et al. 2007;
Zhou et al. 2008; Wu et al. 2011], and BVHs [Wald et al. 2007;
Lauterbach et al. 2009; Garanzha et al. 2011] have been proposed.

C(V → {VL , VR }) = CT + CI (pL NL + pR NR ),In recent years, a number of divide-and-conquer ray tracing(DACRT) methods have been proposed [Keller and Wachter 2011;
Mora 2011]. DACRT has several advantages compared to previous ray tracing methods. Firstly, DACRT does not need to store
acceleration data structures, and the memory footprint can be determined in advance as a linear function of the number of primitives and the number of rays. This is beneficial for rendering
hardware with limited memory. Secondly, the rendering speed of
DACRT [Mora 2011] is faster than previous ray tracing methods
for dynamic scenes, and is competitive for static scenes.

where VL and VR are the bounding volumes of the child nodes, CT
is the cost of an intersection test between a ray and a node, CI isthe cost of an intersection test between a ray and a triangle, andpL and pR are the probabilities of rays intersecting VL and VR , respectively. NL and NR are the numbers of triangles included in VL
and VR , respectively. Efficient partitioning is usually obtained byminimizing the cost function with Surface Area Heuristics (SAH).
Since pL and pR are unknown in the construction, SAH assumes
that the rays are uniformly distributed and approximates pL (pR ) by
the ratio of the surface area of VL (VR ) to that of V .

Mora’s method has been highly optimized for primary rays by using
conic packets. With conic packets, however, it is difficult to handle rays from different origins such as reflected or refracted rays,
rays from area light sources, and random rays, while our method
can accelerate tracing of those less coherent rays. Afra [Afra 2012]extended Mora’s method to handle incoherent rays efficiently by using SSE (Streaming SIMD Extensions) and AVX (Advanced Vector
Extensions) instructions. This method outperforms Mora’s method
for incoherent rays. Unfortunately, neither of these methods exploits the distribution of the rays. Our method further improves
Afra’s method by up to a factor of 2 for primary and less coherent
rays, and consistently outperforms that method for incoherent rays.

Then DACRT calculates the set of rays that intersect each subdivided bounding volume. This operation is called ray filtering. Ray
filtering requires an intersection test between the bounding volume
and the rays. The filtered rays that intersect the bounding volume
are called active rays as shown in Fig. 1.

4

Our Method

Our method uses ray sampling to improve DACRT. For the hierarchical data structure, a BVH represented by a binary tree is employed, while our method can also be applied to kd-trees and BVHs
represented by n-ary trees [Dammertz et al. 2008]. Our method
employs axis aligned bounding boxes (AABBs) for the bounding
volume.

Several methods that exploit the distribution and intersection results of a representative set of rays in order to construct acceleration data structures and ray traversals have been proposed. Bittnerand Havran proposed a method to construct acceleration data structures using the distribution of the rays [Bittner and Havran 2009].
They derived the ray distribution heuristics (RDH) to determine thepartitioning positions of hierarchical data structures. This method,
however, increases the time required to construct the acceleration
data structures and does not provide measurable performance gains
in the time required for ray tracing. Feltman et al. [Feltman et al.
2012] derived the shadow ray distribution heuristic to accelerate
the tracing of shadow rays by using representative shadow ray sets.
Although this method can reduce the number of shadow ray traversals, the time to construct the acceleration data structures increases
and additional memory is required, whereas our method does notincrease the time required to construct the acceleration data structures compared to that without ray sampling. Moreover, the ray
sampling overhead is negligible and this can be overcome by performance gains obtained through ray sampling.

3(1)

Algorithm 1 shows the pseudo code of our algorithm. The algorithm takes a bounding volume V, a set of active rays R, and aset of triangles T as inputs, and calculates intersection points between R and T . Our method first determines whether the current
node is a leaf node or not, by checking the numbers of active rays
and triangles. If the current node is not a leaf node, our method
subdivides V into two bounding volumes by using the binningbased method [Wald 2007]. The binning-based method subdivides the bounding volume into K bins (equally-sized AABBs){B1 , B2 , · · · , BK }. The bin that includes the center of each triangle’s AABB is calculated. The set of triangles T in the bounding volume V can be divided into two disjoint subsets; TL,j in{B1 · · · Bj } and TR,j in {Bj+1 · · · BK } for the j-th bin Bj (1 ≤j ≤ K − 1). Let VL,j and VR,j be the bounding volumes of TL,jand TR,j , respectively.
We now describe the overview of main steps in Algorithm 1. Ouralgorithm consists of four steps, ray sampling, partitioning, determining the traversal order, and traversal of child nodes with skipping ray filtering. In the ray sampling step, our method traces asmall subset of active rays and calculates intersection tests between
the subset of active rays and VL,j and VR,j . In the intersection test,

Divide-And-Conquer Ray Tracing

DACRT performs the intersection tests between a set of rays anda set of primitives in a scene based on the divide and conquer algorithm, as illustrated in Fig. 1. The divide and conquer algorithm

130

Algorithm 1 Our Divide-And-Conquer Ray Tracing Algorithm. V
is a bounding volume, R is a set of active rays, and T is a set oftriangles in V . NaiveRT calculates intersection points between R
and T . vL and vR are arrays for VL,j , VR,j , respectively. Nr , Nt ,and Ns are the numbers of active rays R, triangles T , and sample
rays, respectively.

Algorithm 2 Intersection tests between sample ray r and VL,j andVR,j . INTERSECTP(V, r, tn , tf ) returns true if ray r intersects V ,and sets the intersection interval between r and V to [tn , tf ]. INTERSECTP is a common ray-box intersection algorithm as shownin [Pharr and Humphreys 2010].
1: procedure I NTERSECT(r, vL , vR , cL , cR , nL , nR )2:
for j = 1 to K − 1 do
3:dL,j , dR,j ← ∞4:
if I NTERSECT P(VL,j , r, tn , tf ) then5:cL,j ← cL,j + 1, dL,j ← tn
6:
end if7:
if I NTERSECT P(VR,j , r, tn , tf ) then8:cR,j ← cR,j + 1, dR,j ← tn
9:
end if10:
if dL,j < dR,j then11:nL,j ← nL,j + 1
12:
else
13:
nR,j ← nR,j + 1
14:
end if15:
end for
16: end procedure

1: procedure DACRT(V, R, T )2:
if Nr is small or Nt is small then3:
return NAIVE RT(R, T )4:
end if5:
subdivide V into K bins {B1 , B2 , · · · , BK }6:
calculate TL,j , TR,j , VL,j , and VR,j for each bin Bj
7:
initialize arrays cL , cR , nL , nR ← {0}8:for each sample ray r do
⊲ ray sampling
9:
I NTERSECT(r, vL , vR , cL , cR , nL , nR )10:
end for
11:
Cmin ← ∞, jmin ← 1
12:
for j = 1 to K − 1 do ⊲ partitioning using cost function
13:
αL,j ← cL,j /Ns , αR,j ← cR,j /Ns
14:
calculate cost function C in Eq. (2)15:
if C ≤ Cmin then16:jmin ← j, Cmin ← C
17:
end if18:
end for19:
if nL,jmin ≥ nR,jmin then⊲ determine traversal order
20:(V0 , α0 , T0 ) ← (VL,jmin , αL,jmin , TL,jmin )21:(V1 , α1 , T1 ) ← (VR,jmin , αR,jmin , TR,jmin )
22:
else
23:
(V0 , α0 , T0 ) ← (VR,jmin , αR,jmin , TR,jmin )24:(V1 , α1 , T1 ) ← (VL,jmin , αL,jmin , TL,jmin )25:
end ifCbv
then
26:
if α0 > 1 − nchild
Cchild27:
DACRT(V0 , R, T0 )⊲ skip ray filtering
28:
else
29:
R0 ← R ∩ V0 , DACRT(V0 , R0 , T0 )⊲ ray filtering
30:
end ifCbv
31:
if α1 > 1 − nchildthenCchild32:
DACRT(V1 , R, T1 )⊲ skip ray filtering
33:
else
34:
R1 ← R ∩ V1 , DACRT(V1 , R1 , T1 )⊲ ray filtering
35:
end if
36: end procedure

In the ray sampling step, our method calculates intersection tests
between each sample ray and all pairs of VL,j and VR,j as shownin Algorithm 2. In the intersection test, our method calculates numbers of sample rays, cL,j and cR,j , that intersect VL,j and VR,j ,respectively. In addition, for each pair VL,j and VR,j , the bounding
volume closer to each sample ray is determined in Algorithm 2. To
determine the closer bounding volume, our method compares theentry distances (tn in Algorithm 2) to VL,j and VR,j for each sample ray. Our method calculates the numbers of sample rays, nL,jand nR,j in Algorithm 2, closer to VL,j and VR,j , respectively.

4.2

Partitioning using Cost function

The SAH cost function approximates the probability of a node being hit by a ray as the ratio of the surface area of the child node tothat of the parent node. This approximation works well when therays are uniformly distributed in the scene, while it may not provide a good estimation when the ray distribution is concentrated.
Since previous methods construct acceleration data structures before ray tracing, the probability of a node being hit by a ray cannot
be estimated.

our method stores informations about rays and bounding volumes,
which are used in the latter steps. In the second step, our method
estimates the cost function for K −1 partitioning candidates and thepartitioning that provides the minimum cost is selected. In the third
step, our method determines the traversal order of two child nodes
based on the informations obtained in the ray sampling step. In the
fourth step, we first determine whether the ray filtering reduces thecomputational cost or not, by using a simple criterion. Then our
method recursively traverses the child nodes.

On the other hand, since DACRT constructs a BVH and traces rays
simultaneously, the probability can be estimated by using the numbers of sample rays, cL,j and cR,j , that intersect VL,j and VR,j .
Our method calculates the ratio, αL,j (αR,j ), of sample rays intersecting VL,j (VR,j ). We refer to this ratio as the intersection ratio.
The probabilities pL and pR in Eq (1) are estimated by using theintersection ratios αL,j and αR,j . Then the cost function C is calculated by:
C(V → {VL,j , VR,j }) = CT + CI (αL,j NL,j + αR,j NR,j ), (2)4.1

Ray samplingwhere NL,j and NR,j are the numbers of triangles in VL,j and VR,j ,respectively. By using this cost function, our method can consider
the actual distribution of rays to construct the BVH.

Active rays are sampled to calculate the cost function, the distribution of active rays in the bounding volume, and the traversal orderof child nodes. The sampled rays are referred to as sample rays.
In the current implementation, the number of sample rays is fixed(100) and is irrespective of the number of active rays. The sample
rays are selected randomly when the number of active rays is morethan 1000. Otherwise our method avoids ray sampling since theoverhead of ray sampling cannot be amortized.

4.3

Traversal order

Previous method [Afra 2012] determines the traversal order of twochild nodes by using a single active ray. While this estimation
works well for incoherent rays, we observed that this estimation isinefficient for tracing secondary rays and random rays with a small

131

acve raysacve rays

current node

parent nodechild nodes

child nodes

tersection tests, the cost of the intersection tests between the active
rays of parent node and the bounding volume of current node iszero and nray active rays remain. The cost of intersection tests between nchild child nodes and nray active rays is nray Cchild nchild .
Therefore the total cost Cskip without ray filtering is calculated by:number of bounces, and the inefficient order traversal decreases theray tracing performance. To address this problem, our method uses
the number of sample rays closer to the bounding volume of eachchild node, which is obtained in the ray sampling step. Since thecalculation of entry distances is necessary to obtain the intersection
ratios, the additional operation to determine the efficient traversal
order is only a comparison, whose computational cost is negligible
compared to the performance loss due to inefficient order traversals.

Cskip = nray Cchild nchild .

(4)

Our method skips the ray filtering if Cint > Cskip . That is, theskipping criterion for the intersection ratio α is calculated by thefollowing equation.
α>1−

Cbv
.
nchild Cchild(5)

If the current node is a leaf node, the cost Cchild is the cost of
an intersection test between a triangle and a ray, and nchild is thenumber of triangles included in the leaf node. If the current node is
not a leaf node, the cost Cchild is equal to the cost Cbv , and nchildis 2 since in our method the BVH is represented by a binary tree. Insummary, the skipping criterion for a non-leaf node is simplified to
the following equation.

Skip ray filtering

The ray filtering calculates the intersection tests between active rays
intersecting V and the bounding volumes V0 and V1 as listed in
Algorithm. 1. Since this step calculates active rays for V0 and V1 ,we now consider the node with V0 as current node, and that with V
as parent node for the explanation. As shown in Fig. 2, when mostof the active rays of parent node intersect the bounding volume ofcurrent node during ray filtering, the problem size (i.e. the numberof rays) is not sufficiently divided and this wastes a huge amountof computational time on intersection tests between the bounding
volume of current node and the active rays of parent node. In thiscase, it is efficient to skip the ray filtering and assume that all active
rays intersect the bounding volume.

α > 0.5.

5(6)

Results

We tested several scenes on a standard PC with an Intel Core i7
2.67GHz CPU and 6GB memory. The timings listed in Figs. 4, 5,
6, and 7, are those for ray tracing and do not include ray generationand shading, and measured in a single thread. SSE is utilized for efficient ray tracing. In order to exploit SSE, the data structures of therays and the triangles are similar to Afra’s method [Afra 2012]. To
demonstrate the effectiveness of our method, we compare the computational time for ray tracing with and without ray sampling [Afra2012]. In the latter case, the partitioning is determined by using
the SAH cost function. To perform a fair comparison, our method
adaptively uses our cost function and middle partitioning similar to
Afra’s method. If the ratio of the number of active rays and thatof triangles is larger than a threshold (1.5 in our method), the set oftriangles is partitioned using the cost function described in Sec. 4.2.
Our method uses 32 bins and obtains good results.

To determine whether or not to skip ray filtering, we propose a new
cost metric that uses the intersection ratio α of the current node,
which is obtained in the ray sampling step. The cost metric is thesum of two costs, the cost of intersection tests between the bounding volume of the current node and the active rays of parent node,and the cost of intersection tests between the child nodes and theactive rays of the current node. Let nray be the number of active
rays of the parent node, Cbv the cost of an intersection test between
a bounding volume and a single ray. The cost of the intersection
tests between nray rays and the bounding volume of current node
is given by nray Cbv . The number of active rays for the current
node is estimated as αnray . Our method then calculates the costof intersection tests between the child nodes and the active rays ofthe current node. Let Cchild be the cost of the intersection test
between a child node and a single ray, and nchild be the numberof child nodes. The cost of intersection tests between nchild childnodes and αnray rays is given by αnray Cchild nchild . Thus, the total cost Cint with ray filtering can be calculated from the following
equation.
Cint = nray Cbv + αnray Cchild nchild .

current node

Figure 3: Skip ray filtering if the number of active rays is not sufficiently reduced. The computational cost Cskip for skipping ray
filtering is that of the intersection tests between nray active rays ofcurrent node and child nodes, and estimated as nray Cchild nchild .

Figure 2: Inefficient case of ray filtering. The number of active
rays (orange color) reduced by ray filtering is only one in this case.
The cost for intersection tests between active rays of parent node
and V0 is nray Cbv . The cost for intersection tests between active
rays intersecting V0 and bounding volumes of nchild child nodes is
estimated as αnray Cchild nchild , where α is the intersection ratioof V0 .

4.4

acve rays

skip rayﬁlteringrayﬁltering

parent nodeacve raysacve raysacve rays

Fig. 4 shows the Sibenik scene rendered with different viewpoints
and different image resolutions. The floor is a specular surface
with one point light source (Figs. 4(a)(b)) or an area light source(Fig. 4(c)). As shown in Fig. 4, our method gives an average increase in speed of 1.85 and accelerates ray tracing by up to a factor
2 for primary, secondary, and shadow rays from point and area lightsources. To handle secondary rays, our method first traces primaryrays from the viewpoint and calculates the hit points. The reflectedrays are generated and traced from the hit points on the specular(3)

Next, we describe the cost Cskip of skipping the intersection tests
as illustrated in Fig. 3. In this case, since our method skips the in-132

our method is still faster compared to Afra’s method, which is optimized for incoherent rays. Although our method is slower thanMora’s method for primary rays, our method is at least 1.85 times
faster for incoherent rays. Therefore, we think our method outperforms Mora’s method in the total computational times in pathtracing where the computation of incoherent rays is dominant.

surfaces. For secondary rays, our method rebuilds the BVH fromscratch and does not reuse the BVH constructed for the primaryrays. We have experimented with the reuse of the BVH for the secondary rays for the Sibenik model. However, the reuse of the BVH
does not provide meaningful performance gains compared to our
method that reconstructs the BVH for the secondary rays, since thecomputational time for tracing of rays is dominant compared to thatfor constructing the BVH for the Sibenik model.

6

We measured the impacts of, first, using the cost function given
in Eq. (2), secondly, traversal order determination using sample
rays, and thirdly, skipping the ray filtering for the 40962 resolution image in Fig. 4(a). The acceleration ratios obtained byuse of the cost function, traversal order, and skipping ray filtering were 1.24×(27.3s/22.0s,42%), 1.05×(27.3s/26.0s,10%), and1.28×(27.3s/21.3s,48%), respectively, where the numbers in theparentheses are the computational times in seconds without andwith each technique, and the percentage contribution made to thetotal reduced time. As shown in this measurement, the performancegains due to skipping ray filtering and the cost function using actual
ray distributions have the most impact.

Conclusions and Future Work

We have presented an efficient DACRT algorithm using ray sampling. Our method exploits the distribution of rays to construct a
BVH and determine an efficient traversal order. We have derived a
new cost metric that can skip inefficient subdivisions by using theintersection ratio. The derived metric for non-leaf nodes of binary
BVHs is simplified and easily calculated using the intersection ratio. The ray sampling used in our method can accelerate the tracingof many types of rays by up to a factor of 2. The method is mostefficient for high resolution images with high quality anti-aliasing.
In future work, we would like to implement our method using multithreading. We also intend to apply our method to the motion blur.

Fig. 5(a) shows a case for which our method is not so efficient. In
this case, the performance gain due to ray sampling is relatively
small for moderate resolution images and the computational time
without ray sampling is slightly smaller than that with ray sampling
for the 10242 image. However, the performance loss due to ray
sampling is small (3ms) and our method becomes faster for highresolution images. Fig. 5(b) shows the results of rendering with
ambient occlusion (AO). For AO rays, our method traces a random
ray on the hemisphere of each hit point. Fig. 5(c) shows the San
Miguel scene with depth of field (DOF) rendering with path tracing
up to 3 bounces.

Acknowledgements
We would like to thank all the reviewers for their useful comments.
This research was partially supported by JSPS KAKENHI Grant
Number 24700093 and 13324688.

References
A FRA , A. T. 2012. Incoherent ray tracing without acceleration
structures. In Proc. of Eurographics Short Paper, 97–100.

Figs. 6 and 7 show the Conference and Sponza scenes, respectively. Fig. 8 shows the acceleration ratios using ray sampling withdifferent image sizes and different bounce numbers of rays. As
shown in Fig. 8(a), the acceleration ratio increases as the numberof rays increases. That is, our method is suited to high resolution
images as well as moderate resolution images with multi-sampled
anti-aliasing (MSAA). In fact, all the images are rendered in 5122
resolution with MSAA (e.g. a 40962 resolution image is rendered
as a 5122 image with 64 MSAA). Fig. 8(b) shows that our method
can accelerate the ray tracing for coherent and incoherent rays.

B ENTLEY, J. L. 1975. Multidimensional binary search trees used
for associative searching. Commun. ACM 18, 9, 509–517.
B ITTNER , J., AND H AVRAN , V. 2009. RDH: ray distribution
heuristics for construction of spatial data structures. In Proc. ofthe 25th Spring Conference on Computer Graphics, 51–58.
DAMMERTZ , H., H ANIKA , J., AND K ELLER , A. 2008. Shallow
bounding volume hierarchies for fast simd ray tracing of incoherent rays. Computer Graphics Forum 27, 4, 1225–1233.

We compared the performance of tracing coherent rays with that ofMora’s method [Mora 2011] for the Conference scene in Fig. 6(a).
Our method is 1.66 fps for 1024 × 1024 image on 2.67GHz CPU,
while Mora’s cone optimization method is 3.3 fps for 1280 × 800
image on 3GHz CPU. For the primary rays and shadow rays of one
point light source, our method is 2 times slower than Mora’s methodthat is optimized for primary rays. However, as described in Sec. 2,
Mora’s cone optimization cannot be applied to secondary rays andrandom rays, while our method can accelerate tracing of those rays.
Therefore the applicability of our method is much wider than thatof Mora’s method.

F ELTMAN , N., L EE , M., AND FATAHALIAN , K. 2012. SRDH:
Specializing BVH construction and travesal order using representative shadow ray sets. In Proc. of High Performance Graphics 2012, 49–55.
F UJIMOTO , A., TANAKA , T., AND I WATA , K. 1986. Arts: Accelerated ray tracing system. IEEE Computer Graphics and Applications 6, 4, 16–26.
G ARANZHA , K., PANTALEONI , J., AND M C A LLISTER , D. 2011.
Simpler and faster HLBVH with work queues. In Proc. of High
Performance Graphics 2011, 59–64.

For the Conference scene in Fig. 6(c), we compared the performance in terms of millions of rays per second with those reported
for previous DACRT methods [Mora 2011; Afra 2012]. The performance for path tracing of diffuse rays with 8 bounces (no Russianroulette) was 2.4 (M rays/s) using our method, 2.0 using Afra’s
method, and 1.3 using Mora’s method. Although our method
was measured on the slowest clocked Intel Core i7 CPU (ours :2.67GHz, Afra : 3.4GHz, Mora : 3GHz), it outperforms the previous DACRT methods for incoherent rays (1.20×Afra’s method and1.85×Mora’s method). For incoherent rays, the distribution of rays
tends to be uniform and SAH provides a good estimation. However

H UNT, W., M ARK , W. R., AND S TOLL , G. 2006. Fast kd-tree
construction with an adaptive error-bounded heuristic. In Proc.
of IEEE Symposium on Interactive Ray Tracing, 81–88.
K ALOJANOV, J., AND S LUSALLEK , P. 2009. A parallel algorithm
for construction of uniform grids. In Proc. of High Performance
Graphics 2009, 23–28.
K ALOJANOV, J., B ILLETER , M., AND S LUSALLEK , P. 2011.
Two-level grids for ray tracing on GPUs. Computer Graphics
Forum 30, 2, 307–314.

133

Sibenik
image size
5122
10242
20482
40962

(a) point light
415ms/295ms (1.41)
1520ms/1003ms (1.52)5992ms/3759ms (1.59)
27300ms/14700ms (1.86)(b) point light281ms/183ms (1.54)1130ms/700ms (1.61)4656ms/2647ms (1.76)
19772ms/11330ms (1.75)(c) area light374ms/255ms (1.47)
1430ms/860ms (1.66)
5730ms/3164ms(1.81)
22269ms/11491ms (1.94)

Figure 4: Computational times in milliseconds of ray tracing without and with ray sampling (our method) for different image sizes of theSibenik scene (75K triangles). The number in the parentheses is the acceleration ratio using our method.

image size
5122
10242
20482
40962

(a) point light
110ms/110ms (1.00)
331ms/334ms (0.99)1236ms/1130ms (1.09)
5075ms/4219ms (1.20)(b) AO
446ms/365ms (1.22)1716ms/1217ms (1.41)6948ms/4359ms (1.59)29439ms/19300ms (1.53)(c) PT and DOF
17319ms/16876ms (1.03)
27725ms/26435ms (1.05)
67253ms/59893ms (1.12)215805ms/173018ms (1.25)

Figure 5: Computational times in milliseconds for (a) inefficient cases, (b) rendering with ambient occlusion (AO), and (c) depth of field(DOF) rendering with path tracing (PT) for the San Miguel scene (7.9M triangles). The acceleration ratio using our method is listed in theparenthesis.

K ELLER , A., AND WACHTER , C. 2011. Efficient ray tracing without auxiliary acceleration data structure. In Proc. of High Performance Graphics 2011 (Poster).

S HEVTSOV, M., S OUPIKOV, A., AND K APUSTIN , E. 2007. Highly
parallel fast kd-tree construction for interactive ray tracing of dynamic scenes. Computer Graphics Forum 26, 3, 395–404.

L AGAE , A., AND D UTR É , P. 2008. Compact, fast and robust grids
for ray tracing. Computer Graphics Forum 27, 4, 1235–1244.

WALD , I., I ZE , T., K ENSLER , A., K NOLL , A., AND PARKER ,S. G. 2006. Ray tracing animated scenes using coherent gridtraversal. ACM Trans. Graph. 25, 3, 485–493.

L AUTERBACH , C., G ARLAND , M., S ENGUPTA , S., L UEBKE , D.,
AND M ANOCHA , D. 2009. Fast BVH construction on GPUs.
Computer Graphics Forum 28, 2, 375–384.

WALD , I., B OULOS , S., AND S HIRLEY, P. 2007. Ray tracing
deformable scenes using dynamic bounding volume hierarchies.
ACM Trans. Graph. 26, 1, 6:1–6:18.

M ORA , B. 2011. Naive ray-tracing: A divide-and-conquer approach. ACM Trans. Graph. 30, 5, 117:1–117:12.

WALD , I. 2007. On fast construction of SAH-based bounding
volume hierarchies. In Proc. of the 2007 IEEE Symposium on
Interactive Ray Tracing, 33–40.
W U , Z., Z HAO , F., AND L IU , X. 2011. SAH kd-tree construction
on GPU. In Proc. of High Performance Graphics, 71–78.

P HARR , M., AND H UMPHREYS , G. 2010. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann
Publishers.

Z HOU , K., H OU , Q., WANG , R., AND G UO , B. 2008. Real-time
kd-tree construction on graphics hardware. ACM Trans. Graph.
27, 5, 126:1–126:11.

RUBIN , S. M., AND W HITTED , T. 1980. A 3-dimensional representation for fast rendering of complex scenes. SIGGRAPH
Comput. Graph. 14, 3, 110–116.

134

Conference
image size
5122
10242
20482
40962

(a) point light234ms/189ms (1.24)
803ms/602ms (1.34)
3113ms/2182ms (1.43)
12784ms/8930ms (1.43)(b) point light273ms/189ms (1.44)1030ms/671ms (1.54)5992ms/2636ms (1.60)
17987ms/10618ms (1.69)(c) path tracing
1208ms/1071ms (1.13)3936ms/3279ms (1.20)
15533ms/12316ms (1.26)
65117ms/47761ms (1.36)

Figure 6: Computational times in milliseconds of ray tracing without and with ray sampling (our method) for different image sizes of theConference scene (331K triangles). The acceleration ratio using our method is listed in the parenthesis.

Sponzaimage size
5122
10242
20482
40962

(a) point light
661ms/478ms (1.38)
2298ms/1428ms (1.61)
8801ms/5056ms (1.74)
35397ms/19657ms (1.80)(b) point light599ms/448ms (1.52)2213ms/1471ms (1.50)8774ms/5363ms (1.64)
35643ms/20548ms (1.73)(c) path tracing
2853ms/2331ms (1.22)8288ms/7066ms (1.17)
31960ms/23779ms (1.34)
136327ms/98228ms (1.39)

Figure 7: Computational times in milliseconds of ray tracing without and with ray sampling (our method) for different image sizes of theSponza scene (262K triangles). The acceleration ratio using our method is listed in the parenthesis.

Figure 8: Acceleration ratios using ray sampling for (a) different image sizes and (b) different bounce numbers of rays.

135

136