COMPUTER GRAPHICS forum

DOI: 10.1111/cgf.12341

Volume 00 (2014), number 00 pp. 1–11

SATO: Surface Area Traversal Order for Shadow Ray Tracing
Jae-Ho Nah and Dinesh Manocha

University of North Carolina at Chapel Hill, NC, USAjhnah@msl.yonsei.ac.kr, dm@cs.unc.edu

Abstract
We present the surface area traversal order (SATO) metric to accelerate shadow ray traversal. Our formulation uses the surface
area of each child node to compute the TO. In this metric, we give a traversal priority to the child node with the larger surface
area to quickly find occluders. Our algorithm reduces the pre-processing overhead significantly, and is much faster than othermetrics. Overall, the SATO is useful for ray tracing large and complex dynamic scenes (e.g. a few million triangles) with shadows.
Keywords: ray tracing, shadows, traversal order
ACM CCS: I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism–Ray Tracing.

1. Introduction

tree updating time can become a major bottleneck in large dynamic
scenes. This has implications in terms of choice of techniques toaccelerate traversal of shadow rays. If the additional overhead ofthe data-structure pre-processing is more than the reduced traversal
time, use of such pre-processing may increase the overall rendertime.

A key problem in interactive rendering is generating images withhigh-quality shadows. In general, ray tracing provides a simple solution that generates accurate hard and soft shadows withgood scalability to large models. This involves tracing shadow
and non-shadow rays and accelerating intersection tests using
hierarchies.

1.1. Main results

When we trace a shadow ray, we do not need to exactly findthe closest hit point; we are only interested in whether a shadow
ray is occluded. This ‘any hit’ property can be exploited to use
more efficient traversal orders (TOs) or heuristics for shadow rays;
if an occluded shadow ray is first intersected with an occluder inan upper-level node, the traversal of the shadow ray can be quickly
terminated. Many prior approaches use the ‘any hit’ property: the raytermination surface area heuristic (RTSAH) TO [IH11], the shadow
ray distribution heuristic (SRDH) [FLF12] and the use of volumetricoccluders [DKH09]. These techniques work well in static scenes,
but can be slow for dynamic scenes when the hierarchy is updated
at each frame.

We present the new surface area TO (SATO) metric for shadow ray
tracing. Our formulation gives higher traversal priority to the childnode with the larger surface area. This TO can quickly find large
primitives in the upper-level nodes. Due to its simplicity, SATO
offers the following advantages. First, it does not have high preprocessing overhead. Second, it can be easily integrated with existing SAH-based tree construction or update methods, so parallelization of SATO computation is simple. Third, when SATO is
combined with the tree rotation method [KIS*12], the resulting algorithm can selectively update the TO only if a rotation occurs in abounding volume hierarchy (BVH).

Many applications use large and complex dynamic scenes withmillions of triangles. In these applications, there is a trade-off between the time spent in updating the hierarchy and the time spent intraversing the hierarchy for ray intersections. A good, tight-fitting
hierarchy can reduce the total time spent in tree traversal. Moreover,
it is relatively easy to parallelize tree traversal using single instruction, multiple data or multi-core capabilities (SIMD). As a result,c 2014 The Authors
c 2014 The Eurographics Association andComputer Graphics Forum John Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.

We combine the SATO metric with kd-trees and BVHs and compare its performance with RTSAH using the Manta interactive ray
tracer [BSP06]. The SATO’s traversal performance is competitive
with that of RTSAH in our benchmarks. However, the computation cost of SATO is significantly lower than that of RTSAH.
We highlight the performance benefits of SATO in large dynamic
scenes.

1

2

J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

Figure 1: Ray-traced images in the dense crowd simulation scenario with different numbers of agents: (left) 1 000 agents, (middle) 4 000
agents and (right) 16 000 agents. Each agent corresponds to a dynamic object in the scene, and at each frame, we update the hierarchy. Oursurface area TO (SATO) metric only requires 1.6 ms with a 4-core Core i7 CPU to calculate the TO for 16 000 agents with 10.9M triangles,
which makes it attractive for large dynamic scenes. Moreover, the SATO metric decreases the ray-tracing time by 15% in this complex dynamic
scene. In contrast, the approximate RTSAH metric requires 208 ms to calculate the TO.
The rest of the paper is organized in the following manner. We
give a brief overview of related work in Section 2. We present the
SATO in Section 3 and highlight its performance in Section 4.
2. Related WorkIn this section, we first summarize the SAH. Next, we describe
acceleration techniques for shadow ray tracing which are closely
related to our work. Finally, we give an overview of hierarchy update
methods that can be used with SATO.
2.1. Surface area heuristic
The SAH [GS87, MB90] has been widely used for high-quality tree
construction. Greedy SAH construction determines the split position
using the expected traversal cost using the following equation:CV (p) ≈ KT + KI

SA(VL )SA(VR )TL +TR ,SA(V )
SA(V )(1)

where CV (p) is the expected cost of the voxel V with the split
position p, KT is a traversal cost, KI is an intersection cost andVL and VR are voxels of the left and right child node, respectively.
SA(x) is the surface area of the voxel x, and TL and TR are thenumber of primitives in the left and right child node, respectively.
This metric assumes that the probability of a node being pierced byrays is proportional to the node’s surface area with finite randomrays.
2.2. Acceleration of shadow ray tracing
Djeu et al. [DKH09] proposed the use of volumetric occluders in a
kd-tree and the quick descent breadth-first search order. This method
accelerates shadow ray tracing on opaque watertight meshes.
For more general shadow computation, Ize and Hansen [IH11]
proposed the RTSAH TO for both BVHs and kd-trees. The RTSAH
metric calculates the expected cost of terminating traversal in boththe left and right child nodes. To specify which child node should betraversed first, a flag in each parent node is then updated using the

expected cost; this flag is used for shadow ray traversal. The approximate RTSAH metric for BVHs [IH11] reduces the pre-processing
cost by ignoring empty spaces in a BVH.
Feltman et al. [FLF12] presented the SRDH metric using therepresentative set of shadow rays. Like the ray distribution heuristic (RDH) [BH09], the SRDH exploits the traversal results of asmall representative set of rays for tree construction. By exploiting
the actual traversal results, the SRDH constructs a shadow-rayspecialized BVH and determines effective TO of the BVH. Thismethod increases the overall pre-processing time by computing an
additional BVH for shadow ray traversal, but this method may takefewer traversal steps than RTSAH.
Vinkler et al. [VHS12] presented a visibility-driven BVH construction algorithm. This algorithm employs an improved SAH thatuses the visibility of primitives to construct higher quality BVHs.
This method can accelerate the tracing of both shadow and nonshadow rays in highly occluded scenes.
Latuerbach et al. [LMM09] presented a selective ray-tracing algorithm for shadows. This algorithm first performs shadow mapping,after that, selectively performs ray tracing on potentially inaccurate
pixels to compute correct shadows. Because this algorithm onlyshoots rays corresponding to a small subset of the entire pixels,
shadows can be quickly computed with this algorithm.

2.3. Fast hierarchy updates
Because SAH construction has O(nlogn) time complexity [WH06],
full SAH construction during each frame of a dynamic scene canbe costly, especially for large scenes. Many techniques for fasthierarchy updates have been proposed to address this problem.
Fast tree reconstruction methods utilize cheaper split criteria orparallelization. The methods can be classified into SAH construction on CPUs [WBS07, CKL*10] and GPUs [LGS*09, WZL11,
KA13], spatial median/SAH hybrids on CPUs [Wal07] and GPUs
[ZHWG08, LGS*09, GPM11], object median/SAH hybrids on
CPUs [SSK07] and approximate agglomerative clustering (AAC)on CPUs [GHFB13].

c 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 

J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

3

BV refitting [LYTM06, WBS07] updates a BVH without topological changes. This method can quickly update a BVH, but it candegrade tree quality. In order to prevent the tree quality degradation
caused by BV refitting, Kopta et al. [KIS*12] presented a tree rotation algorithm that can be integrated into a refit procedure.
Other techniques are based on partial or lazy updates. In partial
updates, only dynamic parts of the scene are updated. These methods
either use a separate dynamic tree [SBSK03] or multi-level hierarchies [KNPY13]. The lazy tree construction method [DHW*11]
computes the subtree associated with a node only when a ray entersthat node.
Pre-processing overhead for specific cache-efficient tree layouts
can become a bottleneck for ray-tracing dynamic scenes. In orderto address this issue, Nah et al. [NPK*10, NPP*11] proposed anordered depth-first layout for kd-trees. In this method, the childnode with the larger surface area is stored next to its parent nodeusing the SAH assumption. This results in better cache efficiency
than depth-first layouts and can be easily combined with the SATO
metric.

3. Surface-Area Traversal OrderIn this section, we present the SATO metric that is used for fast
shadow ray traversal. In terms of design, we have two major goals:
to minimize the TO calculation time for dynamic scenes and toquickly find a large occluder for shadow ray tracing. To achievethese goals, we simply use the surface area of each node when
we determine the TO. Note that we assume that the acceleration
structure is a binary tree.
In order to evaluate the benefits of SATO, we introduce a submetric of SATO called PrimSATO. In PrimSATO, we calculate theaverage or maximum surface area of each primitive in each nodeand give the traversal priority to the child node with the higher valueof the primitives’ surface area. This method helps to quickly findlarger occluders in ray traversal. We also introduce a primitive number TO (PrimNumTO); this metric gives the traversal priority to thechild node with the less number of primitives. We then present threeassumptions that are used to analyse the relationship among PrimSATO, PrimNumTO and SATO using the surface area of each node.
To prevent confusion, we will refer to the latter metric as NodeSATO in the rest of the paper. After that, we describe PrimSATO,
NodeSATO and PrimNumTO. Finally, we describe the ray traversal
algorithm using SATO. Figure 2 illustrates the use of SATO.

3.1. Assumptions
Our metric is based on the following assumptions:
Assumption 1. Large primitives are usually located in the upperlevel nodes in a tree, so intersecting with a large primitive first can
result in early termination of a shadow ray.
Assumption 2. In SAH-constructed kd-trees, the child node with thelarger surface area between two child nodes has a higher probabilityof enclosing larger primitives.

Figure 2: An example of the SATO with a kd-tree (a) and a BVH(b). (c) shows the hierarchy of both the kd-tree in (a) and the BVHin (b). In this example, PrimSATO, PrimNumTO and NodeSATO
compute the same TO. To quickly find a larger occluder, a shadow
ray first visits the child node with the higher traversal priority as
determined by SATO. In the above figure, when the SATO is used,
TO is N0, N1 and T0. In contrast, when the front-to-back TO is used,
the TO is N0, N2, N4, T2, T3, N1 and T0.

Assumption 3. In BVHs, the child node with the larger surface area
between two child nodes also has a higher probability of enclosing
larger primitives.
Assumption 1 is related to PrimSATO. This assumption is basedon the character of SAH-constructed trees; the SAH tends to keep
larger primitives near the root [Smi98]. Therefore, if we visit a nodeenclosing a large primitive first, the number of traversal steps canbe reduced.
Assumptions 2 and 3 are related to NodeSATO. These assumptions are based on Assumption 1, so they imply a close relationshipbetween NodeSATO and PrimSATO.
We can explain the reasoning behind Assumption 2 based on
the following criteria. In SAH kd-trees, the child node with thelarger surface area would have a higher probability of containing asmaller number of primitives. This is possible when the left node’s
expected cost (SA(VL ) · TL in Equation (1) and the right node’s expected cost (SA(VR ) · TR ) are comparable. In many cases, the SAH
costs would be comparable in the upper-level nodes, because thesplit plane is inside the median interval (between the spatial andobject median) if there are no objects intersecting with the split
plane [MB90, Hav00]. In this case, it is often one of these twocases: It either has a more sparse primitive distribution, or a higher
average surface area of the primitives in that child node. Empty
spaces between primitives in the first case can be reduced basedon empty space maximizing techniques [Hav00, HKRS02]. Therefore, the second case will have a high probability, and the childnode with the larger surface area will have a higher probability of
enclosing large primitives. Additionally, if SAH values are comparable, a higher surface area implies less number of primitives. Thus,
NodeSATO and PrimNumTO will compute similar TOs in a SAH
kd-tree.

c 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 4J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

BVHs have different characteristics than kd-trees, and the analysis given for kd-tress above may not be applicable to BVHs. Because BVH nodes have a tighter fit to the primitives than kd-tree
nodes [LYTM06], there may be empty space that is not enclosed
by both child nodes. Thus, the SAH costs between the child nodes
may not be comparable if the split plane is determined in sucha way that it maximizes empty spaces. It means that the correlation between the node’s surface area and the number of primitives
in BVHs can be lower than that in kd-trees. However, in contrast
to kd-trees, the BV of a parent BVH node includes the BVs of
its primitives. Therefore, the child node with the larger surface
area among two child BVH nodes will also have a higher probability of enclosing larger primitives, as is the case with kd-trees(Assumption 3).

3.2. PrimSATO
The goal of PrimSATO is to quickly find a large occluder when
tracing a shadow ray, and is same as that of NodeSATO. In order to determine which child node has larger primitives, the PrimSATO calculation is performed during the tree construction. Before
the tree construction, we first calculate the surface area of eachprimitive. After that, when an inner node is created, we average
the surface area values of the primitives in the node or find the
maximum value of the primitives. We call the method using the
average value PrimSATOAVG and the method using the maximum
value PrimSATOMAX . By comparing the calculated average or maximum value of the two child nodes, we can give the traversal priority to the child node with the higher surface area value of theprimitives.
The PrimSATO procedure is straightforward and simple, but the
pre-processing cost of PrimSATO may not be negligible in large
dynamic scenes due to the cost of computing the surface areas.
Moreover, PrimSATO cannot be tightly coupled with BVH update
methods [LYTM06, WBS07, KIS*12]. The reason is that we cannot
get the primitive information enclosed by an inner node after thetree is constructed; a BVH node usually stores its bounding box andchild node pointers.
3.3. NodeSATO and PrimNumTO
NodeSATO addresses the weaknesses of PrimSATO; NodeSATO
compares only the surface areas of each child node, giving traversal
priority to the child node with the larger surface area. If there is ahigh traversal similarity between NodeSATO and PrimSATO, NodeSATO will be a more attractive metric in terms of TO calculation
time.
NodeSATO’s simplicity means that this metric can be easily integrated into all SAH-based tree construction/update methods (seeAppendix for details). If SAH is used for kd-tree construction,
NodeSATO metric requires only one additional computation (thenode comparison). Since we calculate the child nodes’ surface areas during SAH kd-tree construction, the calculated surface areas
can be reused. Parallelization of NodeSATO is also trivial if parallel tree construction/update methods [Wal07, CKL*10, KIS*12]
are used. Additionally, NodeSATO can be combined with lazy tree
construction [DHW*11], because NodeSATO requires only local

information about the node (child nodes’ surface areas) instead of a
traversal of the entire subtree.
When NodeSATO is combined with a tree rotation method[KIS*12] in dynamic scenes, we can selectively update the TOof only the rotated nodes. According to [KIS*12], a rotation is
performed only if the rotation can decrease the SAH cost of anode. Therefore, if a rotation is not performed, it indicates thatthe node’s bounding box is still near optimal and we can simply
reuse the TO calculated during the previous frame. If a rotationis performed, NodeSATO calculations are performed with up to
three inner nodes (the current node and the inner child nodes of thecurrent node) because a rotation affects a subtree with a depth oftwo.
PrimNumTO gives traversal priority to the child node with fewer
primitives. Thus, PrimNumTO computation only requires a simple
comparison between the child nodes. However, this method cannot be combined with BVH update methods [LYTM06, WBS07,
KIS*12] due to the same reasons that were described for PrimSATO
in Section 3.2
3.4. Ray traversal with the SATO metric
NodeSATO, PrimSATO and PrimNumTO have a common traversal
procedure, which is similar to RTSAH traversal [IH11]. SATO requires a 1-bit flag per node (e.g. the isLeftCheaper flag in Manta),
which can be embedded in the node structure without additional
memory overhead. When tracing shadow rays, the flag bit is usedin determining the TO. Instead of using the flag, we can rearrange
the node’s child order using SATO. However, if the acceleration
structure is not a BVH but a kd-tree, the 1-bit flag is still needed
for rearrangement, because kd-tree node rearrangement using surface area is the same as the ordered depth-first layout [NPK*10,
NPP*11]; the 1-bit flag is used to indicate whether the node has
been rearranged or not for front-to-back traversal.
4. Performance and Comparison
In this section, we first compare NodeSATO, PrimSATO and otherTO metrics using the benchmarks used in [IH11] and [FLF12]. Next,
we present experimental results for several dynamic scenes. Finally,
we analyse and describe the limitations of our metric.
4.1. SATO versus other TO metrics
We have tested our method in the Manta interactive ray tracer[BSP06] (revision 2542) on a PC with 3.4 GHz Intel Core i7 with
8 GB RAM. Ray tracing was performed using eight threads withhyperthreading; tree construction and pre-processing for each algorithm was performed using a single thread.
We use the static test scenes used in [IH11] (Figure 3) for evaluating the performance. The Mad Science scene with 80K triangles was
rendered using five samples per pixel, 14 area lights with 25 samples
per shading point and 36 ambient occlusion rays per shading point.
The Carnival scene with 446K triangles was rendered using fivesamples per pixel and 100 ambient occlusion rays. The Bedroom
scene with 361K triangles was rendered using 11 point lights. The
Shadow Overlap scene with 2056K triangles was rendered usingc 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 5J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

Figure 3: Static benchmark scenes: (top row) Mad Science, Carnival, Bedroom, Sponza, (bottom row) Ship and Shadow Overlap. The Shadow
Overlap scene was rendered at 1024×256 pixels, the Ship scene was rendered at 1024×768 pixels and the others were rendered at 1024×1024
pixels.
Table 1: TO calculation time for a BVH and a KD-tree (unit: millisecond, lower is better). A single thread was used.

BVH

Mad Science
Carnival
Bedroom
Shadow Overlap
SponzaShip

kd-tree

RTSAHApproxRTSAH

PrimSATO
AVG

PrimSATOMAX

NodeSATO

PrimNum

RTSAH

PrimSATO
AVG

PrimSATOMAX

NodeSATO

PrimNum

28.8
185.3
135.7
752.7
18.4
1.3

0.9
5.4
3.7
29.2
0.7
<0.1

2.3
19.6
12.0
154.2
1.8
<0.1

2.1
18.5
10.9
145.0
1.6
<0.1

<0.1
0.6
0.4
3.1
<0.1
<0.1

<0.1
0.2
0.1
1.0
<0.1
<0.1

10.3
39.9
53.2
173.8
9.0
0.7

5.3
25.8
33.7
106.3
2.9
0.2

5.1
23.1
32.1
103.8
2.2
0.2

0.2
1.4
0.8
2.8
0.3
<0.1

0.3
1.6
1.2
3.4
0.3
<0.1

one sphere area light with 10 samples per sample point. This sceneconsists of four objects with different complexity: Happy Buddha
with 1M triangles, Armadillo with 30K triangles, Bunny with 69K
triangles and Dragon with 871K triangles.
The two following benchmarks are difficult scenes in terms ofcomputing the optimal TO, in contrast to the scenes described above.
The Sponza scene with the arcade view is described in [FLF12]
consists of 66K triangles and two sphere area light sources. This
scene was rendered with two-level path tracing, and the number ofsamples per shading point was one. This scene has low amount ofocclusion and an equal number of shadow and non-shadow rays, so
TOs do not greatly affect the overall traversal time. The Ship scene
with 4K triangles was rendered using 1 area light with 16 samples
per sample point. In this scene, an axis-aligned occluder (a cabin) is
located near the shaded deck and non-axis-aligned occluders (thinropes and an anchor) are located near the light source. A BVH
node that includes non-axis-aligned objects has large empty spaces,

assigning TO to non-axis-aligned occluders may not be a good
choice. Thus, the front-to-back order is near optimal.
To measure the performance of NodeSATO and PrimSATO in
different traversal methods, we use three traversal methods: packetized ranged BVH traversal [WBS07] with 8×8 ray packets, singleray BVH traversal and single-ray kd-tree traversal. With this experimental setup, we compare a front-to-back TO, a random TO[FLF12], two RTSAH implementations (RTSAH and approximate
RTSAH) [IH11] and four SATO implementations (NodeSATO,
PrimSATOAVG , PrimSATOMAX and PrimNumTO). As described in[IH11], approximate RTSAH is only applicable to BVHs because
approximate RTSAH for BVHs and RTSAH for kd-trees are essentially same. For the random TO, we have used a fast random-number
generation function in Manta [BSP06], because the standard rand()function is not suitable for parallel processing. In all TOs, earlytermination is commonly performed when the first intersection isfound.

c 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 6J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

Table 2: Render time (unit: seconds, lower is better). Eight threads with hyperthreading were used. ARP is an abbreviation of average relative performance
when a front-to-back TO is the reference method (higher is better). Approximate RTSAH is only applicable to BVHs, as described in [IH11]. Bold values
indicate the highest performance.

Packetized BVH traversal
Mad Science
Carnival
Bedroom
Shadow Overlap
SponzaShip
ARPSingle-ray BVH traversal
Mad Science
Carnival
Bedroom
Shadow Overlap
SponzaShip
ARPSingle-ray kd-tree traversal
Mad Science
Carnival
Bedroom
Shadow Overlap
SponzaShip
ARP

Front to backRandomRTSAHApprox RTSAH

PrimSATOAVG

PrimSATOMAXNodeSATO

PrimNum

392.71151.19
0.48
0.18
0.76
1.31
1.00×

266.62114.00
0.28
0.18
0.75
1.40
1.24×

247.38
81.46
0.27
0.14
0.75
1.46
1.40×

240.05
97.34
0.26
0.14
0.73
1.42
1.38×

226.31
83.22
0.24
0.13
0.74
1.32
1.48×

228.87
98.54
0.26
0.14
0.74
1.31
1.39×

231.39
82.55
0.25
0.14
0.76
1.41
1.44×

257.71
77.35
0.26
0.13
0.73
1.49
1.44×

577.71163.88
2.36
0.24
0.93
2.57
1.00×

452.49
91.06
1.79
0.23
0.95
2.62
1.23×

320.57
63.35
1.50
0.22
0.94
2.66
1.50×

316.22
77.36
1.49
0.22
0.91
2.62
1.44×

326.85
63.77
1.47
0.21
0.93
2.49
1.52×

325.32
79.10
1.52
0.21
0.91
2.37
1.44×

334.72
65.96
1.47
0.21
0.94
2.62
1.48×

380.81
59.24
1.54
0.21
0.91
2.72
1.48×

402.86102.53
1.08
0.19
0.46
1.14
1.00×

295.11
59.06
0.86
0.21
0.47
1.16
1.21×

238.51
67.22
0.82
0.20
0.48
1.08
1.25×

–
–
–
–
–
–
–

276.23
61.48
0.89
0.18
0.48
1.12
1.23×

240.06
65.24
0.81
0.18
0.47
1.09
1.28×

249.61
59.01
0.89
0.18
0.46
1.14
1.26×

293.20
58.29
0.90
0.18
0.48
1.14
1.22×

NodeSATO

PrimNum

Table 3: The number of traversal steps per ray (left) and the number of intersection tests per ray (right). Lower is better.

Packetized BVH traversal
Mad Science
Carnival
Bedroom
Shadow Overlap
SponzaShipSingle-ray BVH traversal
Mad Science
Carnival
Bedroom
Shadow Overlap
SponzaShipSingle-ray kd-tree traversal
Mad Science
Carnival
Bedroom
Shadow Overlap
SponzaShip

Front to backRandom

RTSAH

120.5 / 21.0
378.8 / 24.6
100.7 / 12.6
111.4 / 2.6
276.3 / 11.2
50.3 / 27.1

90.8 / 12.0
297.2 / 17.5
65.1 / 8.5
111.9 / 2.6
273.8 / 10.9
51.0 / 28.5

83.7 / 11.0
204.6 / 14.3
64.9 / 7.3
86.2 / 2.5
273.7 / 11.1
51.2 / 30.6

82.7 / 11.0
257.1 / 13.5
64.7 / 6.8
84.2 / 2.5
267.7 / 11.1
51.8 / 29.0

82.6 / 9.7
205.5 / 15.9
64.0 / 6.4
78.6 / 2.6
270.4 / 11.1
47.6 / 27.6

82.6 / 9.7
236.5 / 18.5
65.7 / 7.1
86.5 / 2.6
267.7 / 11.2
50.0 / 24.9

84.5 / 9.8
207.4 / 15.9
64.5 / 6.6
84.1 / 2.5
278.3 / 11.3
48.4 / 31.8

92.3 / 11.9
206.7 / 9.4
64.3 / 7.0
80.6 / 2.6
265.3 / 10.8
49.2 / 32.2

57.1 / 8.5
84.4 / 13.3
74.9 / 9.4
28.6 / 1.7
61.9 / 3.2
44.3 / 25.3

45.4 / 6.0
45.9 / 6.5
57.2 / 7.5
27.3 / 1.5
63.0 / 3.1
43.5 / 27.0

36.2 / 4.0
33.9 / 5.0
50.2 / 5.8
27.7 / 1.6
64.1 / 3.2
44.7 / 28.4

35.2 / 4.3
42.2 / 5.2
51.1 / 5.4
27.5 / 1.6
62.1 / 3.1
45.6 / 26.9

40.4 / 3.7
34.3 / 5.3
50.6 / 5.2
27.4 / 1.6
63.7 / 3.2
41.1 / 26.0

40.5 / 3.7
42.6 / 6.9
51.6 / 5.6
27.7 / 1.7
62.3 / 3.2
43.5 / 23.2

41.1 / 3.7
34.3 / 5.6
50.7 / 5.3
27.0 / 1.6
64.2 / 3.2
41.6 / 30.5

47.3 / 4.5
32.3 / 4.0
52.5 / 5.7
27.3 / 1.5
61.8 / 3.1
43.2 / 30.0

44.3 /
52.6 /
41.1 /
33.4 /
37.5 /
33.2 /

37.9 /
37.3 /
32.5 /
32.9 /
36.9 /
32.7 /

30.4 /
37.1 /
31.2 /
32.7 /
38.4 /
31.0 /

–
–
–
–
–
–

33.7 /
34.6 /
36.0 /
31.7 /
38.2 /
31.7 /

33.5 /
36.1 /
30.2 /
31.5 /
37.6 /
31.5 /

33.0 /
32.7 /
35.8 /
32.4 /
38.1 /
32.6 /

34.6 /
32.6 /
35.8 /
32.4 /
38.2 /
34.0 /

8.9
9.8
8.3
2.3
3.0
6.8

5.4
5.3
6.1
1.9
2.8
7.2

4.2
5.3
6.5
2.3
3.0
6.4

Approx RTSAH PrimSATOAVG PrimSATOMAX

5.3
4.8
6.3
2.0
3.0
6.8

3.8
5.3
6.0
2.0
3.0
6.5

4.5
4.4
6.7
2.0
2.9
7.4

5.5
4.0
6.8
2.0
3.0
6.9


c 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 

J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

7

Figure 5: Comparison of TO similarity between NodeSATO andother metrics. This result supports Assumptions 2 and 3 in Section 3.

Figure 4: The average surface area of primitives in one leaf node
per tree depth. The above figure indicates the result of the BVHs, andthe below figure indicates the result of the kd-trees. These results
support Assumption 1 in Section 3.

We first measure the TO calculation time of each method(Table 1). This task was performed as a pre-process in static scenes,
and a single thread was used. For the RTSAH and approximate
RTSAH calculation, we have used a separate function implemented
in Manta [BSP06]. For NodeSATO, PrimSATO and PrimNumTO
calculations, we have implemented the TO calculation code in theexisting tree construction function. According to the results in Table 1, PrimSATO is faster than RTSAH but slower than approximate
RTSAH. NodeSATO and PrimNumTO are the fastest method in kdtrees and BVHs, respectively. The reason is that NodeSATO requires
an additional surface area calculation per node in BVH construction,
but does not require that computation in kd-tree construction.
In contrast to the embedded NodeSATO/PrimSATO calculation
codes in the tree build function, the RTSAH calculation code has
been implemented as a separate function. Thus, in this RTSAH implementation, node data should be fetched again for the separate
function. However, even if we consider the implementation difference, the experimental result shows that the NodeSATO and PrimNumTO calculations are significantly faster than fast approximate
RTSAH calculation.
Second, we measure ray-tracing performance using render time
(Table 2). We also measure additional statistics for better analysis(Table 3). Among the metrics, PrimSATOAVG and PrimSATOMAX
demonstrate the highest speedups in BVHs and kd-trees, respectively. These different speedups can be explained by the difference
between object hierarchies and spatial hierarchies. Each primitive
is located in a single BVH node if spatial splits are not used for
the BVH construction, so PrimSATOAVG is a more reasonable choicein this case. In contrast, a primitive can be located in multiple kdtree nodes. That is, a ray can find the hit point on the outside of
the current node if a primitive intersects the current node and theother nodes. Thus, for kd-trees, PrimSATOMAX can be more efficient. Additionally, NodeSATO and PrimNumTO do not result in
the fastest performance, but exhibit performance that is comparable
to RTSAH and PrimSATO. The random TO exhibits lower speedups
than RTSAH and SATO.
The Sponza and Ship scenes demonstrate the limitations of eachmethod. Occluded shadow rays account for a small part of the total
rays in the Sponza scene, so all TO metrics do not result in a significant difference in the overall performance. In the Ship scene with
BVHs, only PrimSATO results in similar or faster performance thanfront-to-back ordering. The reason is that PrimSATO based on actual primitives’ surface areas is robust for non-axis-aligned objects.
To evaluate the performance of SATO, we perform two additional experiments. First, to verify Assumption 1 in Section 3 wemeasure the average surface area of primitives in a leaf node pertree depth (Figure 4). The results in Figure 4 explain the advantage
of PrimSATO. According to the results, the average surface area ofprimitives in a leaf node is inversely proportional to the tree depth.
In other words, higher-level nodes have a higher probability of enclosing larger primitives. Even though the kd-trees for the Sponza
and Bedroom scenes show gradual increases from specific depths,
these results can be explained by large primitives overlapped withmultiple nodes.
Second, we measure the traversal similarity between NodeSATO
and other metrics (Figure 5). To calculate the similarity, we compare
NodeSATO’s TO flag and the others’ TO flags at each traversal step.

c 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 8J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

Figure 6: Dynamic benchmark scenes: Funnel, Fairy Forest and Lion. The captured images were rendered with soft shadows.
The data in Figure 5 were collected by single-ray BVH and kd-tree
traversal. In the kd-tree traversal, NodeSATO exhibits higher similarities with PrimSATOAVG and PrimNumTO. This result supports
Assumption 2. In contrast, PrimSATOMAX does not exhibit a highsimilarity, because the surface area of a node can be smaller than thatof the primitive in the node. This situation occurs when a large primitive overlaps multiple nodes. In the BVH traversal, NodeSATO hasa higher similarity with PrimSATOAVG and PrimSATOMAX . This
result supports Assumption 3; there is a high traversal similarity
between PrimSATO and NodeSATO.

Table 4 summarizes the experimental results in the dynamic
scenes. According to the results, NodeSATO achieves 4–18% performance improvements in the total frame time (tree update+TO
calculation+rendering). Additionally, the selective NodeSATO
Table 4: Experimental results in dynamic scenes with soft and hard shadows(unit: millisecond, lower is better). Note that the BVH update time includes
keyframe animation time, BV refitting time and rotation time. Note that the
RTSAH/approximate RTSAH TO was calculated using a single thread.

BVH update TO calculation Render time
time
time
(hard/soft)

4.2. Experimental results with dynamic scenes
We use the same rendering system and hardware configuration described in Section 4.1 to evaluate our approach on dynamic scenes.
To deal with dynamic objects, we use the tree rotation algorithm
developed by Kopta et al. [KIS*12]. We have integrated NodeSATO into the tree rotation function. We also evaluate the selective
NodeSATO update scheme (described in Section 3.3 and Appendix)
and measure its performance by enabling and disabling the scheme.
PrimSATO and PrimNumTO are excluded in this experiment, because they are difficult to integrate into the BV refit/rotation procedure, as described in Section 3. For ray traversal, we use the ranged
BVH traversal algorithm [WBS07] with the 8×8 packet size. Bothtree updates (including the NodeSATO calculation) and ray tracing
were performed using eight threads with hyperthreading; the RTSAH and approximate RTSAH calculations were performed using
a single thread.
We test our method in four dynamic scenes (Figures 1(right)
and 6). The Funnel scene only consists of 18K triangles, so inthis scene, render time is much more important than tree update
and TO calculation time. The Fairy is a mid-sized game-like scene
with 174K triangles, and the Lion scene is a large scene with 1.6M
triangles. The Crowd Simulation scene [CGZM11] (Figure 1), with
10.9M triangles, is the largest scene in our test set; the tree update
and TO calculation times are significant in this scene.
We apply two different shadow settings to the test scenes: hardshadows and soft shadows. For hard shadows, one point light source
is used. For soft shadows, one spherical area light source and four
samples per light are used. The soft-shadow setting increases the
proportion of shadow rays, so the performance improvements byusing an efficient TO also increase in this case.

Funnel (18K triangles)
Front to back
0.6
0.0
Random
0.6
0.0
RTSAH
0.6
11.8
Approx RTSAH
0.6
0.9
NodeSATO
0.6<0.1
NodeSATO
0.6<0.1(selective)
Fairy forest (174K triangles)
Front to back
6.1
0.0
Random
6.1
0.0
RTSAH
6.1
95.6
Approx RTSAH
6.1
3.3
NodeSATO
6.1<0.1
NodeSATO
6.1<0.1(selective)
Lion (1.6M triangles)
Front to back
52.2
0.0
Random
52.2
0.0
RTSAH
52.2
950.9
Approx RTSAH
52.2
37.5
NodeSATO
52.2
1.2
NodeSATO
52.2
0.1(selective)
Crowd simulation (10.9M triangles)
Front to back
369.1
0.0
Random
369.1
0.0
RTSAH
369.1
5389.5
Approx RTSAH
369.1
208.5
NodeSATO
369.1
8.2
NodeSATO
369.1
1.6(selective)

Total time
(hard/soft)

13.7/33.5
13.8/34.7
12.8/27.3
13.5/31.1
13.0/31.4
12.6/28.5

14.3/34.1
14.4/35.3
25.2/39.7
15.0/32.6
13.6/32.0
13.2/29.1

57.7/167.4
49.2/152.2
51.1/155.5
49.5/149.2
48.3/149.1
47.7/149.6

63.8/173.5
55.3/158.3
152.8/257.2
58.9/158.6
54.4/155.2
53.8/155.7

58.2/158.5
110.4/210.7
58.4/163.6
110.6/215.8
54.8/122.5 1057.9/1125.6
54.1/119.6
143.8/209.3
54.3/125.5
107.7/178.9
53.4/129.3
105.7/181.6

201.7/442.5 570.8/811.6
203.2/442.4 572.3/811.5
167.7/385.9 5926.3/6144.5
166.9/384.7 740.5/958.3
172.1/379.7 549.4/757.0
169.8/375.3 540.5/746.0


c 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 

J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

update scheme is effective in reducing the TO calculation time.
This is possible because the rotation percentage in the Funnel, Fairy
Forest, Lion and Crowd Simulation scenes is only 4.8%, 8.4%,
7.4% and 6.4%, respectively. The render time with and without the
selective NodeSATO update scheme is similar even though the selective update scheme partially reuses the TO calculated during theprevious frame. Due to the parallelization and the selective update
schemes, NodeSATO could achieve very low TO calculation times
in a large scene (1.6 ms in the Crowd Simulation scene).
In contrast, RTSAH increases the total frame time in all scenes
due to the additional TO calculation time; fast approximate RTSAH
also increases the total frame time in the Lion scene with hardshadows and the Crowd Simulation scene. This overhead can belowered by parallelization of RTSAH calculation and code in-lining,as NodeSATO does. However, NodeSATO is still faster than theparallelized RTSAH and approximate RTSAH methods in termsof TO calculation time. Additionally, random TO does not yieldnoticeable performance improvements except for the Fairy Forest
scene.
Because of tree update overheads and simple shadow settings
in the dynamic scenes, the relative performance improvements of
NodeSATO in dynamic scenes are lower than those in the static
scenes. However, in cases where we apply both faster tree update
methods and complex shadows, we expect that NodeSATO will
exhibit similar performance improvements on static and dynamic
scenes, because NodeSATO has negligible TO calculation overhead.
Also, we expect that performance gap between NodeSATO andapproximate RTSAH will increase in more complex dynamic scenes
because of the TO calculation overhead.

4.3. Analysis and limitations
4.3.1. Comparison to SRDH
NodeSATO and PrimSATO would not be faster than SRDH [FLF12]
in static scenes. This is because our metric only determines theTO, but SRDH affects both tree construction and TO. However,the SRDH increases tree construction time by up to 20 s for
pre-rendering using representative ray sets. In contrast, NodeSATO,
with its selective update scheme, only requires less than 2 ms todetermine the TO. Therefore, we believe that NodeSATO is better
suited for dynamic scenes than SRDH.

4.3.2. Limitations
Our SATO metric does not guarantee performance improvements inall situations. First, NodeSATO, PrimSATO and PrimNumTO only
accelerate occluded shadow rays, just as RTSAH [IH11] does. Thus,
if most shadow rays are not occluded or the fraction of shadow rays
is relatively low, performance improvements from using our metricwould decrease.
Second, NodeSATO and PrimNumTO assume that the tree isconstructed or updated by the SAH. If the tree is constructed by either spatial median or object median, NodeSATO and PrimNumTO
might not work well. Additionally, if BV refitting is used for BVH
updates, NodeSATO’s efficiency can be degraded due to large BVs.

9

Thus, additional tree update approaches based on the SAH, such as
the tree rotation algorithm [KIS*12] or treelet restructuring [KA13],
should be used if BV refitting significantly degrades the tree quality.
Third, the SATO metric’s efficiency is influenced by the scenecharacteristics. For example, if there are a large object that consists of many highly tessellated triangles and a small object thatconsists of a few large triangles, NodeSATO will pick the former object for giving traversal priority and cannot accelerate theshadow ray traversal. In this case, PrimSATO and PrimNumTO
will be more effective. However, if variability in scene primitive
size is very small, all our metrics (NodeSATO, PrimSATO and
PrimNumTO) may not find an optimal traversal route, because
they are designed to quickly find large occluders in the upper-levelnodes.

5. Conclusions and Future Work
We have presented the SATO metric to accelerate shadow ray tracing. To determine the TO between two child nodes, the SATO compares each node’s surface area (NodeSATO), the surface areas of theprimitives in the node (PrimSATO) or the number of primitives in
the node (PrimNumTO); NodeSATO and PrimSATO assign higher
traversal priority to a node with larger surface area, and PrimNumTO
gives traversal priority to a node with fewer primitives. Each metrichas its own strength. NodeSATO can be easily implemented in existing SAH-based tree construction or update methods. Additionally,
NodeSATO has negligible calculation overheads, so it is very usefulin dynamic scenes. PrimSATO is competitive with other metrics
when compared on the basis of traversal performance, particularly
with scenes including non-axis-aligned triangles. PrimNumTO has
the fastest TO calculation time with BVH construction.
In terms of future work, we would like to combine the SATO
with other methods and measure the effects of the combination.
First, if static and dynamic scenes are handled separately [SBSK03,KNPY13], the SRDH can be used for high-quality static tree/subtree
construction, as well as TO determination, while the SATO canbe used for dynamically updating trees or subtrees. Additionally,
we are interested in combining the SATO with lazy tree construction [DHW*11] and AAC BVH construction [GHFB13]. Because
the AAC algorithm lifts large occluders to higher levels of theBVH [GHFB13], this could be a synergistic combination. Also, thecombination of SATO and an ordered depth-first layout [NPK*10,
NPP*11] could provide both lower traversal steps and cache-missrates in kd-tree traversal. Finally, an extension of the tree quality
metric [AKL13] to the special case of shadow rays can be a future
research topic, as described in [AKL13].

Acknowledgements
We would like to thank Junho Park for the fruitful discussions, thereviewers for their valuable comments and the following people forhelping us with our experimental setup: Thiago Ize (the static scenes
used in the RTSAH paper); Priyadarshi Sharma, Sujeong Kim andSean Curtis (the dynamic scenes).
This research was supported by Basic Science Research Program
through the National Research Foundation of Korea (NRF) fundedc 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 10J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing

by the Ministry of Education (NRF-2012R1A6A3A03040332) andin part by ARO Contracts W911NF-10-1-0506, W911NF-12-10430, W911NF-13-C-0037 and NSF awards 0917040 and 1320644.
The Mad Science scene is by Dan Konieczka and Giorgio
Luciano; the Carnival by Dan Konieczka, the Bedroom was modelled by David Vacek and designed by David Tousek; all threescenes are available from the 3dRender.com Lighting Challenges.
The Happy Buddha, Bunny, Dragon and Armadillo are courtesyof the Stanford Computer Graphics Laboratory. The Sponza, Shipand Fairy Forest scenes are courtesy of Marko Dabrovic, Arauna
realtime ray tracing and the Utah 3D Animation Repository, respectively. The Funnel and Lion scenes are courtesy of the UNC
Dynamic Scene Benchmarks.

Appendix: Pseudo-Code of the NodeSATO Metric
1) NodeSATO calculation in tree construction[BH09] BITTNER J., HAVRAN V.: Rdh: Ray distribution heuristics forconstruction of spatial data structures. In SCCG ’09: Proceedingsof the 25th Spring Conference on Computer Graphics (2009), pp.
51–58.
[BSP06] BIGLER J., STEPHENS A., PARKER S. G.: Design for parallelinteractive ray tracing systems. In Proceedings of IEEE Symposium on Interactive Ray Tracing 2006 (2006), pp. 187–196.
[CGZM11] CURTIS S., GUY S. J., ZAFAR B., MANOCHA D.: Virtualtawaf: A case study in simulating the behavior of dense, heterogeneous crowds. In Proceedings of the 1st IEEE Workshop
on Modeling, Simulation and Visual Analysis of Large Crowds(2011).
[CKL*10] CHOI B., KOMURAVELLI R., LU V., SUNG H., BOCCHINO R.
L., ADVE S. V., HART J. C.: Parallel SAH k-D tree construction.
In Proceedings of the Confernce on High Performance Graphics
2010 (2010).

find the best split plane[DHW*11] DJEU P., HUNT W., WANG R., ELHASSAN I., STOLL G.,
MARK W. R.: Razor: An architecture for dynamic multiresolution
ray tracing. ACM Transactions on Graphics 30, 5 (2011), 115:1–
115:26.

if (the split can minimize the SAH cost)make an inner node
compare each child node’s SA[DKH09] DJEU P., KEELY S., HUNT W.: Accelerating shadow rays
using volumetric occluders and modified kd-tree traversal. In
Proceedings of the Conference on High Performance Graphics
2009 (2009), pp. 69–76.

set isLeftCheaper of the node
else
make a leaf node2) Selective NodeSATO calculation with a tree rotation
if (a rotation can decrease the SAH cost)do the rotation[FLF12] FELTMAN N., LEE M., FATAHALIAN K.: SRDH: Specializing BVH construction and traversal order using representative shadow ray sets. In Proceedings of Conference on High Performance Graphics 2012 (2012), pp. 49–
55.

compare the SAs of the rotated inner nodes
set isLeftCheaper of the nodes
else
skip the TO calculation and keep the isLeftCheaper flag

[GHFB13] GU Y., HE Y., FATAHALIAN K., BLELLOCH G.: Efficient
BVH construction via approximate agglomerative clustering. In
Proceedings of the Conference on High Performance Graphics
2013 (2013), pp. 81–88.
[GPM11] GARANZHA K., PANTALEONI J., MCALLISTER D.: Simpler
and faster HLBVH with work queues. In Proceedings of theConference on High Performance Graphics 2011 (2011), pp.
59–64.

3) BVH traversal using the SATO
(same as the RTSAH traversal)
if (a shadow ray intersects with an inner node)
front son = node.isLeftCheaper? 0 : 1;
do an intersection test with node.child+front son
do an intersection test with node.child+1-front son[GS87] GOLDSMITH J., SALMON J.: Automatic creation of object hierarchies for ray tracing. IEEE Computer Graphics and Applications 7, 5 (May 1987), 14–20.
[Hav00] HAVRAN, V.: Heuristic Ray Shooting Algorithms. PhD thesis, Czech Technical University in Prague, Nov. 2000.

References[HKRS02] HURLEY J., KAPUSTIN, A., RESHETOV A. SOUPIKOV A.: Fastray tracing for modern general purpose CPU. In Proceedings ofGraphicon 2002 (2002).

[AKL13] AILA T., KARRAS T., LAINE S.: On quality metrics of bounding volume hierarchies. In Proceedings of the Conference on High
Performance Graphics 2013 (2013), pp. 101–107.

[IH11] IZE, T., HANSEN C.: RTSAH traversal order for occlusion rays.
Computer Graphics Forum (Proceedings of EUROGRAPHICS
2011) 30, 2 (2011), 297–305.


c 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum 

J.-H. Nah & D. Manocha / SATO: Surface-Area Traversal Order for Shadow Ray Tracing[KA13] KARRAS T., AILA T.: Fast parallel construction of highquality bounding volume hierarchies. In Proceedings of theConference on High Performance Graphics 2013 (2013),
pp. 89–99.

11engine for hardware accelerated ray tracing. ACM Transactions
on Graphics 30, 6 (2011), 160:1–160:10.
[SBSK03]SZÉCSI L., BENEDEK B., SZIRMAY-KALOS L.: Accelerating
animation through verification of shooting walks. In SCCG ’03:
Proceedings of the 19th Spring Conference on Computer Graphics (2003), ACM, pp. 231–238.

[KIS*12] KOPTA D., IZE T., SPJUT J., BRUNVAND E., DAVISA., KENSLER A.: Fast, effective BVH updates for animatedscenes. In Proceedings of the ACM SIGGRAPH Symposiumon Interactive 3D Graphics and Games (2012), pp. 197–
204.

[Smi98]SMITS B.: Efficiency issues for ray tracing. Journal ofGraphics Tools 3, 2 (Feb. 1998), 1–14.

[KNPY13]KANG Y.-S., NAH J.-H., PARK W.-C., YANG S.-B.: gkDtree:
A group-based parallel update kd-tree for interactive ray tracing.
Journal of Systems Architecture 59, 3 (2013), 166–175.

[SSK07]SHEVTSOV M., SOUPIKOV A., KAPUSTIN A.: Highly parallel
fast KD-tree construction for interactive ray tracing of dynamic
scenes. Computer Graphics Forum 26, 3 (2007), 395–404.

[LGS*09] LAUTERBACH C., GARLAND, M., SENGUPTA S., LUEBKE D.,
MANOCHA D.: Fast BVH construction on GPUs. Computer Graphics Forum 28, 2 (2009), 375–384.

[VHS12]VINKLER M., HAVRAN V., SOCHOR J.: Visibility driven BVH
build up algorithm for ray tracing. Computers & Graphics 36, 4(2012), 283–296.

[LMM09] LAUTERBACH C., MO Q., MANOCHA D., : Selective Ray
Tracing for Interactive High-Quality Shadows. Tech. Rep. TR09004, University of North Carolina at Chapel Hill, 2009.

[Wal07] WALD I.: On fast construction of SAH-based bounding
volume hierarchies. In Proceedings of IEEE Symposium on Interactive Ray Tracing 2007 (2007), pp. 33–40.

[LYTM06] LAUTERBACH C., YOON S.-E., TUFT D., MANOCHA D.:
RT-DEFORM: Interactive ray tracing of dynamic scenes using
BVHs. In Proceedings of IEEE Symposium on Interactive Ray
Tracing 2006 (2006), pp. 39–45.

[WBS07] WALD, I., BOULOS S. SHIRLEY P.: Ray tracing deformablescenes using dynamic bounding volume hierarchies. ACM Transactions on Graphics 26, 1 (2007), 6:1–6:18.

[MB90]MACDONALD D. J., BOOTH K. S.: Heuristics for ray tracing
using space subdivision. The Visual Computer 6, 3 (1990), 153–
166.
[NPK*10] NAH J.-H., PARK J.-S., KIM J.-W., PARK C., HAN T.-D.:
Ordered depth-first layouts for ray tracing. In Proceedings of
ACM SIGGRAPH ASIA 2010 Sketches (2010), pp. 55:1–55:2.
[NPP*11]NAH J.-H., PARK J.-S., PARK C., KIM J.-W., JUNG Y.-H.,
PARK W.-C., HAN T.-D.: T&I engine: Traversal and intersection[WH06] WALD I., HAVRAN V.: On building fast kd-trees for ray
tracing, and on doing that in O(N log N). In Proceedings of IEEE
Symposium on Interactive Ray Tracing 2006 (2006), pp. 61–69.
[WZL11] WU Z., ZHAO F., LIU X.: SAH KD-tree construction on
GPU. In HPG’11: Proceedings of the Conference on High Performance Graphics 2011 (2011), pp. 71–78.
[ZHWG08] ZHOU K., HOU Q., WANG R., GUO B.: Real-time KDtree construction on graphics hardware. ACM Transactions on
Graphics 27, 5 (2008), 1–11.


c 2014 The Authors
c 2014 The Eurographics Association and John Wiley & Sons Ltd.
Computer Graphics Forum