EUROGRAPHICS 2015 / O. Sorkine-Hornung and M. Wimmer(Guest Editors)

Volume 34 (2015), Number 2

T-SAH: Animation Optimized Bounding Volume Hierarchies
J. Bittner and D. Meister
Czech Technical University in Prague, Faculty of Electrical Engineering

1.1x vs SAH+refit1.5x vs HLBVH

5.4x vs SAH+refit1.1x vs HLBVH

1.3x vs SAH+refit2.6x vs HLBVH

1.4x vs SAH+refit
1.6x vs HLBVH

Figure 1: Average speedups of ray tracing for several tested animations when using our single T-SAH optimized BVH withrefitting compared to SAH with refitting and per frame rebuilding using HLBVH algorithm. From left to right: Fairy Forest,
Dragon Bunny, San Miguel + Running Horses, Breaking Lion.
Abstract
We propose a method for creating a bounding volume hierarchy (BVH) that is optimized for all frames of a given
animated scene. The method is based on a novel extension of surface area heuristic to temporal domain (T-SAH).
We perform iterative BVH optimization using T-SAH and create a single BVH accounting for scene geometry
distribution at different frames of the animation. Having a single optimized BVH for the whole animation makes
our method extremely easy to integrate to any application using BVHs, limiting the per-frame overhead only torefitting the bounding volumes. We evaluated the T-SAH optimized BVHs in the scope of real-time GPU ray tracing.
We demonstrate, that our method can handle even highly complex inputs with large deformations and significant
topology changes. The results show, that in a vast majority of tested scenes our method provides significantly betterrun-time performance than traditional SAH and also better performance than GPU based per-frame BVH rebuild.
Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Raytracing—I.3.5 [Computer Graphics]: Object Hierarchies—I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism—

1. Introduction
Ray tracing stands at the core of many rendering algorithms.
With the advances of computational power it is possible touse ray tracing for interactive applications, including those
involving dynamic or animated scenes. Bounding Volume
Hierarchies became a very popular data structure for ray
tracing. They exhibit a predictable memory budget, fast construction, very good ray tracing performance, and also allow
easy updates for handling dynamic scenes.
c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John
Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.

A number of efficient techniques have been proposed forbounding volume hierarchies. For example methods for construction of high quality BVHs [WBKP08, BHH13, KA13,
GHFB13] are particularly suitable for offline applications
as they provide hierarchies leading to the best possible ray
tracing performance. Other class of techniques uses very
fast BVH construction targeting at interactive and real-time
applications with dynamic and animated scenes [GPM11,
Kar12]. These methods lead to real-time or interactive performance for scenes of low to moderate complexity.

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchies

In many cases animated or deformable models exhibit
large amount of coherence and just refitting the BVH andkeeping its topology provides a very good overall performance. However, in some cases this approach breaks due totopology changes or large deformations [WBS07]. Several
methods have been proposed to handle this issue by dynamically updating the BVH at runtime [LYTM06, KIS∗ 12]. We
propose to use a novel approach based on temporal extensionof the surface area heuristic (T-SAH). We describe an algorithm that uses T-SAH to construct a single BVH optimized
for a given animation sequence. In the most of the test cases
the T-SAH based BVH provides surprisingly stable results
even for scenes involving very complex topology changes(see the accompanying paper video or snapshots in Figures 5
and 6 for the range of topology changes we aim to handle).
Apart from animated scenes the method can also handle deformable and/or articulated objects such as animated characters.
Since the BVH can be optimized for the whole animation sequence in the preprocess, there is no need to rebuild
the BVH at runtime. Our tests indicate, that for interactive
rendering of complex scenes with known animations thisleads to significantly better performance than rebuilding the
BVH at runtime. The savings are not only due to faster update time, but the measured ray tracing performance is also
higher for most tested scenes, since the preprocess allows toconstruct BVH of better quality than the methods working at
runtime.

2. Related Work
SAH Bounding volume hierarchies have a long tradition in
rendering and collision detection. Kay and Kajiya [KK86]
designed one of the first BVH construction algorithms using spatial median splits. Goldsmith and Salmon [GS87]
proposed the measure currently known as the surface area
heuristic (SAH), which predicts the efficiency of the hierarchy during the BVH construction. The vast majority of currently used methods for BVH construction use a top-down
approach based on SAH. A particularly popular method isthe fast approximate SAH evaluation using binning proposed
by Havran et al. [HHS06] and Wald et al. [Wal07].
SAH extensions Several extensions of the basic SAH havebeen proposed in the past. Hunt [Hun08] proposed corrections of SAH with respect to mailboxing. Fabianowski etal. [FFD09] proposed SAH modification for handling sceneinterior ray origins. Bittner and Havran proposed to modify
SAH by including the actual ray distribution [BH09], Feltman et al. [FLF12] extended this idea to shadow rays. Corrections of the SAH based BVH quality metrics have been
recently proposed by Aila et al. [AKL13].
Parallel BVH construction
Another class of methods target fast parallel BVH construction. Lauterbach etal. [LGS∗ 09] proposed a GPU BVH construction algorithm

using a 3D space-filling curve. Wald [Wal12] studied thepossibility of fast rebuilds from scratch on an Intel architecture with many cores. Pantaleoni and Luebke [PL10],
Garanzha et al. [GPM11], and Karras [Kar12] proposed
GPU based methods for efficient parallel BVH construction.
These techniques achieve impressive performance, but generally construct a BVH of lower quality than the full SAH
builders. We use the HLBVH method [GPM11] as one of
the references for our comparisons.
High quality BVH Recently more interest has been devoted to methods, which are not limited to the top-down
BVH construction. Walter et al. [WBKP08] proposed to use
bottom-up agglomerative clustering for constructing a highquality BVH. Gu et al. [GHFB13] proposed a parallel approximative agglomerative clustering for accelerating thebottom-up BVH construction. Kensler [Ken08], Bittner et
al. [BHH13], and Karras and Aila [KA13] proposed to optimize the BVH by performing topological modifications of
the existing tree. These approaches allow to decrease the expected cost of a BVH beyond the cost achieved by the traditional top down approach. Our method uses an extensionof the insertion based optimization algorithm proposed by
Bittner et al. [BHH13].
Dynamic and animated scenes Wald et al. [WBS03] suggested to decompose dynamic scenes into multiple objects
with their local transformations and use a top-level hierarchy for organizing these objects. This concept has recently
been used within the Embree ray tracer [WWB∗ 14]. Lauterbach et al. [LYTM06] proposed to rebuild subtrees if they exhibit significant SAH cost changes. Gunther et al. [GFW∗ 06]
subdivided the model into clusters of coherent movement
and used fuzzy kd-trees to describe the residual geometry
changes. Olsson [Ols07] studied 4D kd-trees focusing on optimzing their performance for rendering motion blur. Waldet al. [WBS07] proposed to use BVH refitting combinedwith packet based traversal for rendering dynamic scenes.
Ize et al. [IWP07] proposed asynchronous BVH reconstruction and refitting for increasing runtime performance. Updating BVH at runtime using rotations has been proposedby Yoon et al. [YCM07] and more recently by Kopta etal. [KIS∗ 12]. Garanzha [Gar09] precomputes coherent triangle clusters using motion prediction in order to accelerate
the BVH construction at runtime. Mora [Mor11] proposedto perform ray tracing without an explicit data structure using a divide and conquer algorithm. Ray tracing animatedscenes was surveyed by Wald et al. [WMG∗ 09]. Unlike theprevious methods, our method is the first to create a single
ordinary BVH optimized for the whole animation, requiring
no topology modifications at runtime.
The paper is further structured as follows: Section 3
presents an overview of the proposed method, Section 4
introduces the T-SAH cost model, Section 5 describes the
BVH construction using T-SAH, Section 6 presents the results and their discussion, and Section 7 concludes the paper.
c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchies

3. Algorithm Overview

4. T-SAH for Animations

Our algorithm starts by resampling the input animation sequence into a small number of representative frames. The
representative frames provide information about the geometry distribution during the animation. We construct a BVH
for the first representative frame using a standard sweep
based algorithm based on SAH. The BVH is then iteratively
optimized using the cost model given by the temporal extension of the surface area heuristic (T-SAH). T-SAH simultaneously considers costs of all representative frames, and thus
optimizing according to T-SAH will improve the overall performance of the BVH for the input animation sequence.

The SAH cost is based on expressing the probability of hitting a bounding volume with a random unoccluded ray. Oncethe ray hits a bounding volume of area S we express the probability of hitting its child bounding volume S0 as the ratio of
surface areas S0 /S. The SAH cost of the whole BVH can be
expressed as a function of time as:

The actual BVH optimization algorithm is a modificationof the method proposed by Bittner et al. [BHH13] that uses
the new T-SAH cost model. The method performs a seriesof remove and insert operations on subtrees of the BVH inorder to minimize the T-SAH cost of the BVH. Since the estimated ray tracing performance is known during the BVH
optimization procedure, the method can put more effort to
optimize difficult representative frames. An illustration of
the optimization and its impact on a scene involving significant topology changes is shown in Figure 2.

C(t) =cT
cI∑ SN (t) + S(t)∑ SN (t) jN ,S(t) N∈innerN∈leaves(1)

where SN (t) is the surface area of node N at time t, S(t) is
the surface area of the root of the BVH, jN is the number oftriangles in leaf N, and cT , cI are costs for ray traversal andray intersection computations.
We resample the animation sequence or the pose spaceof a character into a set of n representative frames at corresponding times ti for which we obtain a discrete set of n
BVH costs Ci = C(ti ), 0 ≤ i < n. Using the representativee which is a temporal exframes we define the T-SAH cost C,
tension of the SAH cost function. T-SAH cost Ce expresses
the cost of the whole animation sequence as a weighted average of the frame costs:

Ce =1∑ wiCi∑i wi i

0≤i<n

(2)

where wi is the weight of the representative frame i.
0
1
2
3

...

...

As we do not assume a priori knowledge of importance ofthe representative animation frames, we use sampling at uniform time intervals and we set the weights wi to depend on
the actual cost of the frame: wi = Cik . The exponent k is theparameter of the method influencing the relative contributionof the cost for the given frame to the T-SAH cost function.
The T-SAH cost function is then given as:

fk =CFigure 2: Illustration of the BVH optimization using T-SAH.
During the optimization we keep an array of bounding boxes
for each BVH node, which correspond to bounding volumes for different representative frames. The optimization
regroups nodes at all tree levels to yield clusters as compact
as possible considering all frames. The bottom row shows visualization of a BVH constructed for the Dragon Bunny animation using SAH (left) and T-SAH (right) (a cut in the BVH
involving nodes with less than 5.000 polygons is shown).
Note how T-SAH automatically identifies groups of polygons
forming fragments of the broken Dragon that appear in thelater stages of the animation.

c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.

1
∑ Cik+1∑i Cik i

0≤i<n

(3)

Note that for the special case of k = 0, all the frames
f0 correare weighted equally and the T-SAH cost function C
sponds to the average cost of the sampled animation frames:
f0 = 1 C
C
i
n∑
i

0≤i<n

(4)

If the exponent k becomes larger (e.g. k ≥ 2) significantly
more weight is given to the frames with high values of thecost function. Thus when minimizing the T-SAH cost function these frames will have higher importance and the algorithm should aim to optimize the BVH by reducing the cost

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchiesof these frames with higher priority. In other words whenminimizing the T-SAH cost function using higher exponents
k we should eliminate peaks of the sampled cost function
f0 will increase. Thiseven at the price that the average cost C
is useful for example in the scenario when we have a stricttime budget for rendering a frame and we want that the BVH
provides performance fulfilling this budget for the whole animation sequence.
The above described definition expresses the T-SAH costof the whole BVH. When evaluating a cost of a subtree using Eq. 2 we use the global weights wi corresponding to thewhole tree as they give a better overview of the importanceof different representative frames for the animation.

correspond to surface area increase at different representative frames above the node that is currently visited by
the searching algorithm. The actual costs are then evaluatedfrom the cost vectors using the T-SAH model (Eq. 2).
To accelerate the search procedure we use an approximation to T-SAH cost model, that only updates weights wi after
a batch of reinsertion operations has been performed. We
used a batch size equal to 2% of the number of nodes inf0
the BVH. Note that when optimizing the average cost C
the weights are constant and need not be re-evaluated in thewhole optimization process.

5.2. Selecting Nodes for Update
5. Building BVH using T-SAH
We decided to use T-SAH with the insertion based BVH optimization method proposed by Bittner et al. [BHH13]. Thismethod works by optimizing an already existing BVH, andso it can take into account all the components of the T-SAH
cost model including the calculation of weights wi based on
the costs of the representative frames. This section describes
the BVH construction algorithm focusing on the modifications required for supporting the T-SAH cost model.

One choice to apply the above described optimization is toselect nodes to be updated in random order. However, using
some prioritization scheme can accelerate the optimization
process [BHH13]. As a priority for updating a given node
fk . This conwe use its contribution ∆kN to the cost function C
tribution corresponds to a weighted sum of surface areas of
the node over all representative frames, where the weights
correspond to frame weights wi :∆kN = ∑ wi SN (ti ) = ∑ Cik SN (ti )5.1. Insertion Based Optimization
The elementary step of the insertion based optimization
method is removing a node from the BVH and reinserting
it back at a position reducing the global tree cost. Here we
do not reproduce the basics of the method and we refer theinterested reader to the work of Bittner et al. [BHH13]. The
removal of a node and its insertion back into the BVH requires only simple local operations on the tree once the optimal insertion position is found.
The crucial part of the algorithm is searching for the optimal position to re-insert the node into the BVH while accounting for the T-SAH cost model. Similarly to the standard version of the insertion based optimization the algorithm uses branch-and-bound search. This search tracks thecost increase caused by expanding bounding volumes ofnodes above the currently examined insertion position (induced cost). The other component of the total cost increaseis given by inserting a new node connecting the re-inserted
subtree and the node which was identified as the best insertion point (direct cost). In the algorithm by Bittner et
al. [BHH13] the induced cost corresponds to the surface area
increase of nodes on the path to the root and the direct costto the surface area of the union of bounding boxes of theinserted node and the box of the node at the insertion point.
The modification for T-SAH involves computing vectorsof costs instead of scalar variables, where the components ofthese vectors correspond to different representative frames.
For example the components of the vector of induced costsiif0 this priority simplifies to a sum of surface areas of
For C
the node bounding box over all representative frames.
We use an independent chain Metropolis-Hastings sampling in order to quickly select nodes for updates. We want
the target distribution of selected nodes to be proportional to∆kN . We pick up a node Xi+1 using a uniform proposal distribution. This node is either accepted or rejected based on
the ratio of the cost contributions of the node and the previously accepted node ∆ki+1 /∆ki . This process introduces acorrelation, i.e. some nodes would be drawn a number oftimes in a sequence. In our application updating the samenode in a sequence does not make sense as the deterministic search would always find the same optimal position forthis node in the BVH. We therefore continue the sampling
until we accept a different node, which is then updated. The
actual distribution of selected nodes does not strictly follow
fk , but nevertheless it is able to significantly accelerate the∆CNconvergence of the BVH cost (about 1.5 to 4x compared torandom sampling). We also observed that for complex animations, the described stochastic method converges fasterthan the deterministing batch sorting proposed for optimizing a single BVH [BHH13], as the later one primarily focuses only on small percentage of nodes with high costs. On
the contrary for simpler animations the batch sorting based
selection provided the best convergence rate (see Figure 3).
c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchies
batchdsort
randomM-H

74
72

avg. BVH cost [-]avg.dBVHdcostd[-]

76

70
68
66
64
0

0.5

1

1.5 2 2.5
timed[s]

3

3.5

4

1600
1400
1200
1000
800
600
400
200
0

6.1. BVH Optimizationbatch sortrandomM-H

0

50

100 150
time [s]200250

Figure 3: Convergence rates of BVH optimization for different node selection methods (left: BART robots, right: BART
museum). Note that on a very complex animation sequence
like BART Museum batch sorting was not very succesful andthe cost was reduced only after switching to random sampling after couple of initial optimization passes (at t=20s).

5.3. Terminating the Optimization
We terminate the BVH optimization if there was no reduction of the BVH cost in the given number of update batches.
We observed, that terminating after three batches when thecost was not reduced was a good overall setting for the tested
scenes.

5.4. Adaptive Leaf Size
For obtaining an optimized BVH with the highest possible
quality it is important to initially construct a deep BVH witha single triangle per leaf. This allows the T-SAH based optimization algorithm to identify fine grained groups of triangles which exhibit coherent movement or deformations.
Having such a deep BVH is however not desirable for the actual rendering. An optimal leaf size depends on the constantsof the ray tracer implementation, the type of animation, andray distribution.
To finalize the BVH we compact the tree by collapsing
the subtrees into larger leaf nodes as proposed by Bittner et
al. [BHH13]. In the case of animated scenes this does not
only account for particular constants of the ray tracer (ratioof cT /cI ), but it also efficiently handles some potential deformations of the model. The algorithm evaluates the cost of
the subtree CNk and compresses it when the cost of the subtree becoming a leaf is smaller.

6. Results
We evaluated the proposed method on nine animated scenes.
Eight scenes represent standard benchmarks for animatedray tracing, one scene is a composition of a static model ofa moderate complexity (7.8M triangles), and an animation
representing several horses running through the scene. The
overview of tested animated scenes is given in Table 1.
c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.

First, we compared the costs and the build times of BVHs
constructed offline using different methods. For the comparison we used BVH constructed for every frame using the full sweep SAH (SAH-rebuild), the best-over-time
BVH [WBS07] with refitting (SAH∗ ), BVH constructed forthe first frame with refitting (SAH0 ), and the proposed Tf0 , C
f2 ,SAH with refitting using three different settings (C∗f4 ). For SAH-rebuild and SAH we also employed the inC
sertion based optimization [BHH13]. For SAH0 this optimization was not used as we observed that for some complex animations, like Museum or Dragon-Bunny, optimizing
the BVH for the first frame slightly increased the average
BVH cost for the whole animation. The measurements were
performed within a single threaded C++ implementation on
a PC with Intel Xeon E5-1620, 3.6GHz, with 32GB RAM.
The results are summarized in Table 1. For T-SAH we used
5 uniformly sampled representative frames. The evaluation
was performed using 50 interpolated animation frames for
all tests.
The table shows that the BVH construction time for TSAH varies between 1.9s for the smallest reported scene(BART robots) and 328s for the largest one (San Miguel +Horses). The actual T-SAH optimization time corresponds
to the difference between the build times of the particular T-SAH method and SAH0 , as we always applied the TSAH based optimization on the BVH constructed for the first
frame. Comparing to SAH0 we can observe, that for simpler
animations the reduction of the average BVH cost is not very
dramatic (in order of 10-20%), which indicates that even asingle SAH optimized BVH is quite good to handle theseanimations. However for scenes with extreme deformations
such as Dragon Bunny, Breaking Lion, or BART museum
our method reduces the cost by more than an order of magnitude. We can see that in these cases the SAH∗ corresponding to the best over time BVH also provides much better results than SAH0 , but the BVH cost is still significantly larger
than for T-SAH methods. As expected the SAH-rebuild reference method provides the best results in all tests, but in thesimpler animations the SAH∗ and T-SAH methods are very
close to this reference solution. We can also observe, that inscenes with simple geometric changes different exponentsof the T-SAH cost model lead to very similar results. However in scenes with pronounced peaks of the cost function
such as Dragon-Bunny or Museum, the T-SAH with higher
exponents provides lower maximum BVH costs at the expense of a higher average BVH cost. In other words the costfunction gets more smoothed for the whole animation sequence (see Figure 4-left). This is important for time criticalapplications, like for example ray traced augmented reality
with animated objects, in which we want to ray trace the preprocessed animation at stable real-time rates. Figure 4-rightshows the progress of the optimization for different settingsof the T-SAH cost model.

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchies

BART Robots
BART Museum
Cloth Ball# triangles
71.5k# triangles
75.8k# triangles
92.2k# key frames
300# key frames
300# key frames
94
test
time [s]costmax. cost test
time [s]costmax. cost test
time [s]costmax. cost
SAH-rebuild 24.7
56
57
SAH-rebuild 39.7
40148
SAH-rebuild 22.9
73
91
SAH∗
18.5
57
58
SAH∗
18.6
364
1376 SAH∗
20.8
97
156
SAH0
0.4
69
71
SAH0
0.4
1558
2335 SAH0
0.4
97
156
f0
f0
f0
T-SAH C
1.9
57
57
T-SAH C
123
119
365
T-SAH C
9.0
90
139
f2
f2
f2
T-SAH C
1.9
57
57
T-SAH C
155
136
282
T-SAH C
9.7
90
129
f4
f4
f4
T-SAH C
2.0
57
57
T-SAH C
161
149
266
T-SAH C
0.6
98
147

BART Kitchen
24 Cell
Fairy Forest# triangles
110.5k# triangles
122.8k# triangles
174.1k# key frames
300# key frames
128# key frames
21
testtime [s]costmax. cost test
time [s]costmax. cost test
time [s]costmax. cost
SAH-rebuild 41.6
26
26
SAH-rebuild 49.2
111
120
SAH-rebuild 68.5
76
77
SAH∗
32.6
26
26
SAH∗
28.6
161
181
SAH∗
22.7
76
77
SAH0
0.7
37
38
SAH0
0.5
195
250
SAH0
1.0
87
92
f0
f0
f0
T-SAH C
3.6
26
26
T-SAH C
13.1
131
142
T-SAH C
7.5
76
77
f2
f2
f2
T-SAH C
3.7
26
26
T-SAH C
13.5
131
142
T-SAH C
6.2
76
77
f4
f4
f4
T-SAH C
3.7
26
26
T-SAH C
13.5
131
141
T-SAH C5.3
76
77

Dragon Bunny
Breaking Lion
Horses# triangles
252.5k# triangles
1604.0k# triangles
8048.9k# key frames
15# key frames
34# key frames
31
testtime [s]costmax. cost test
time [s]costmax. cost test
time [s]costmax. cost
SAH-rebuild 112
57
134
SAH-rebuild 912
555
644
SAH-rebuild 6603
130
131
SAH∗
25.8
474
1441 SAH∗
460
747
907
SAH∗
2906
159
182
SAH0
1.4
1542
2865 SAH0
12.2
1530
3801 SAH0
89
214
281
f0
f0
f0
T-SAH C
13.2
137
365
T-SAH C
116
571
658
T-SAH C
328
133
133
f2
f2
f2
T-SAH C
34.0
102
220
T-SAH C
116
567
647
T-SAH C
319
133
133
f4
f4
f4
T-SAH C
28.7
103
190
T-SAH C
120
566
640
T-SAH C
319
133
133

Table 1: Summary results for the high quality BVH construction algorithms. The table shows the BVH optimization time, andthe average and maximum BVH costs for the given animation sequence. For computing the BVH cost, we used cT = 3, cI = 2.

We also evaluated the dependence of the method on thenumber of representative frames. When increasing the number of representative frames from 5 to 10 the BVH optimization time almost doubled, the maximum BVH cost wasslightly reduced, but the resulting average BVH costs stayedpractically the same for most tested scenes. The most notabledifferences we observed for the Museum and Breaking Lion
scenes where the average BVH cost was reduced by 1% andthe maximum BVH cost by about 2%. This indicates that a
relatively small number of representative frames is sufficientto optimize even for complex animation sequences.
6.2. Performance Comparisons
We evaluated the performance of the optimized BVH for
ray tracing using CUDA ray tracing framework by Ailaet al. [AL09]. We extended the framework by implementing new kernels for interpolating triangle vertices, refittingbounding volumes, recomputing Woop matrices, and implementing the HLBVH algorithm. The actual ray tracing kernel was used without modifications. All computations thus
run on the GPU, the CPU is used only to execute CUDA
kernels. For all tests we used NVIDIA GeForce GTX TITAN Black GPU with 6GB RAM.
We used five reference methods for comparisons. The first
one uses precomputed high quality BVH (SAH-rebuild), thesecond one uses best over time BVH with refitting (SAH∗ ),the third one uses BVH build for the first frame with refitting (SAH0 ). The forth reference method uses the fast GPU
build using the HLBVH algorithm [GPM11] limited to spatial median splits with 30-bit Morton codes (HLBVH-med).
c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchies
f2
C

400
350
300
250
200
150
100
50
0

f4
C

avg. BVH cost [-]BVH cost [-]

f0
C

0

10

20

30

40

1400
1200
1000
800
600
400
200
0
0

50

5

10

avg. BVH cost [-]BVH cost [-]

450
400
350
300
250
200
150
100
50
0
0

50

100

150

15

20

25

30

35

time [s]frame [-]

200

250

300

frame [-]

1400
1200
1000
800
600
400
200
0
0

20

40

60

80

100 120 140 160 180

time [s]f0 , Cf2 , Cf4 . (left) Costs of the
Figure 4: Plots showing the costs for the BVH optimized using T-SAH with different exponents Cf0 ) in the progress of the BVH optimization.
optimized BVH for different frames of the animation. (right) Average BVH cost (CThe upper figures correspond to the Dragon Bunny scene, the lower to the Museum scene.

The fifth reference uses HLBVH including the surface area
heuristic (HLBVH-SAH) with 30-bit Morton codes (15-bits
SAH, 15-bits spatial median). Both HLBVH algorithms use
maximum 8 triangles per leaf as a termination criterion. For
all tests the we used 1024x768 resolution, 1 primary ray per
pixel, 8 ambient occlusion rays, and 2 shadow rays. We measured the time needed to update the BVH for the given frame(using either refit or rebuild), the ray tracing speed expressedin MRays/s, and the total frame time.
The results are summarized in Table 2. We can observe
f0 provides the best tothat in the majority of cases T-SAH C
tal frame times for the tested animations. In the case of relatively simple animations (BART Robots, BART Kitchen,
Fairy Forest) the results of SAH0 , SAH∗ , and T-SAH andvery close and the timing differences are also influenced by
the actual match of the BVH topology and the view point.
For scenes which involve complex animations with deformations or topological changes, the SAH0 method fails completely (BART Museum, Dragon Bunny, Breaking Lion),f0 with refit successfully compensates forwhereas T-SAH C
the dynamic changes of the scene. The HLBVH methods
provide a stable performance as the BVH is always constructed from scratch. However, with increasing size of thescene the overhead of BVH rebuild becomes more andmore important and the method provides significantly lower
frame times than T-SAH. Interestingly for most tests the TSAH provides not only lower BVH update times, but also
c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.

higher ray tracing speed even comparing to the HLBVHSAH method. This is due to the fact, that the method uses
a more complex BVH optimization than the approximate
SAH algorithm used in HLBVH. A notable exception is the
BART Museum scene, in which both HLBVH methods provide smaller total times. This scene exhibits extreme topological changes and although T-SAH provides more than
10x better performance than SAH0 , it is not able to compensate for all these changes. Nevertheless when splitting
the animation into three parts and constructing a BVH using
T-SAH for each of these parts, we can observe that the overall frame time for T-SAH gets very close to rebuilding the
BVH from scratch at each frame (see Table 2 - BART Museum*). The influence of using multiple BVHs is also shownin Figure 5. While more elaborate techniques for splitting theanimation sequence could be used such as adaptive splitting
and/or finding the minimal number of BVHs fulfilling the
given performance limit, we leave these extensions as topics
for future work. Note that the differences in refit times are
due to the adaptive leaf size discussed in Section 5.4, which
for the case of using the T-SAH cost model usually lead toslightly deeper tree.
The frame times and the ray tracing speed for two selectedanimated scenes are shown in Figure 6. We can observe, thatfor the Dragon Bunny scene T-SAH is able to eliminate thelarge total time increase of the SAH method caused by the
explosion of the geometry of the dragon. In the Breaking
Lion scene we can observe that T-SAH successfully com-

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchies

pensates the part of the animation, in which the lion is broken into a large number of disconnected pieces. This scene
has a higher polygon count and therefore we can observe a
constant overhead of both HLBVH methods in total time,
which is caused by a longer time needed to rebuild the BVH
in each frame.
SAH-rebuild
f0
T-SAH C

SAH0

SAH∗

HLBVH-med

HLBVH-SAH

total time [ms]

2000
1500
1000
500
0
0

10

20

30

40

50

60

70

80

90

total time [ms]

2000
1500
1000
500
0
0

10

20

30

40

50

60

70

80

90

frame [-]

which cannot be predicted. However we believe, that TSAH could still be used to optimize parts of such scenes
for which the movement is well predictable. We also expect that by feeding T-SAH optimization algorithm with aset of expected positions of dynamic objects would cause an
automatic separation of dynamic and static content. Thoseobjects which are expected to behave in a similar way would
get clustered together in appropriate levels of the BVH. TSAH could also be used in combination with the decomposition to local subtrees proposed by Wald et al. [WBS03] tohandle dynamic scenes with unpredictable object movement.
Optimization time We implemented the BVH optimization using a simple single threaded application that takes significantly more time than fast GPU builders. However, thisphase is only done once in preprocessing and at runtime thefinal BVH can be used just as an ordinary BVH, on which
only refit is applied.
Using T-SAH with other algorithms We expect thatbottom up clustering could easily handle T-SAH as the TSAH could serve as a basis for evaluating the distance between clusters. We believe that T-SAH could be successfully exploited also in combination with a GPU based BVH
optimization using rotations [KIS∗ 12], or with bottom-up
BVH construction algorithms [GHFB13]. Using these methods might lead to lower optimization times for applications
where this is required.
7. Conclusion and Future Work

Figure 5: Plots of the total frame time for BART Museum
scene. (top) Single BVH optimized using T-SAH. (bottom)
Using 3 BVHs optimized for frames 0-32, 33-65 and 66-99
using T-SAH.
6.3. Discussion and Limitations
Maximizing ray tracing performance
In terms of ray
tracing performance an optimal solution for a known animation sequence would precompute a high quality BVH for
every frame that is rendered as we did using SAH-rebuild
method. However this method has important practical drawbacks compared to T-SAH. First, for scenes with large number of key frames the SAH-rebuild becomes very memory
intensive. Second, the implementation has to maintain large
number of BVHs, which requires more implementation effort and complicates the usage with existing frameworks.
The first issue can actually be handled by using T-SAH optimized BVH with a range of key frames (as we suggest for
the Museum scene). Given the same memory budget T-SAH
optimized BVHs should provide better ray tracing performance than the same number of SAH optimized ones.
Dynamic scenes In fully dynamic scenes new objects canappear, or existing objects can undergo some movement,

We proposed an extension of the surface area heuristic totemporal domain (T-SAH). We exploit T-SAH to construct asingle bounding volume hierarchy optimized for all framesof an animated sequence. The algorithm uses a small setof representative frames and performs an iterative optimization of the BVH in order to minimize the T-SAH cost. Our
method uses an extension of a recently proposed insertion
based BVH optimization algorithm. We have shown that thealgorithm is able to handle a broad class of animated scenes
including those involving complex deformations and topology changes. We evaluated the performance of T-SAH optimized BVH for ray tracing. The results show that T-SAH
performs significantly better than SAH and in a vast majorityof cases it outperforms even the fast per frame rebuilds using
the HLBVH algorithm. The proposed method requires practically no modifications to existing rendering packages andthus it can be used as an optional optimization step for handling animated scenes in the context of real-time ray tracingor collision detection.
We believe that our extension of SAH to animations gives
a new insight on how hierarchical object partitioning can organize the scene by exploring locality in both spatial andtemporal domains. In the future we want to look at adaptively subdividing the input animation sequence in order toprovide a minimal set of BVHs within a given memory budget, which yield the optimal rendering performance. We also
c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchies
update trace
total update trace
total update trace
total update trace
total update trace
total
time
speed
time timespeed[ms] time
speed
time time
speed
time time
speed
time
[ms] [MRays/s] [ms] [ms] [MRays/s] [ms] [ms] [MRays/s] [ms] [ms] [MRays/s] [ms] [ms] [MRays/s] [ms]BART Robots
BART Museum
BART Museum*
Cloth Ball
BART Kitchen
SAH-rebuild
0.0
179.8
64.8 0.0
184.9
70.9
0.0
184.9
70.9
0.0
87.5
49.1 0.0
241.6
48.6
SAH∗
7.4
183.1
70.7 2.3
19.5
674.5 2.4
56.0
234.1 3.0
78.8
57.0 5.2
241.1
53.3
SAH0
3.8
190.1
66.3 2.3
6.3
2082.4 2.1
6.7
1958.0 2.5
81.2
55.5 3.4
235.5
54.5
f0
T-SAH C
7.1
190.7
68.2 2.7
62.7
212.0 2.1
118.3
110.8 3.0
82.2
55.0 5.3
239.1
53.8
HLBVH-med 18.1
117.0 119.7 10.3
161.3
91.7 10.3
161.3
91.7 12.1
79.6
66.7 17.4
172.3
87.8
HLBVH-SAH 49.3
129.4 139.0 22.6
177.9
96.5 22.6
177.9
96.5 31.2
80.3
84.6 46.2
189.2 107.7
24 Cell
Fairy Forest
Dragon Bunny
Breaking Lion
Horses
SAH-rebuild
0.0
67.3
50.4 0.0
169.9
68.2
0.0
38.8
46.7
0.0
32.6
58.2 0.0
80.5
143.7
SAH∗
4.0
57.5
62.6 4.5
162.4
75.9
3.3
17.6
105.7 9.9
26.7
82.9 36.3
75.3
190.3
SAH0
2.8
54.2
66.0 3.7
142.4
85.1
3.5
5.8
315.8 8.8
22.0
97.2 30.4
67.8
201.9
f0
T-SAH C
4.3
65.3
56.0 5.3
163.0
76.5
3.4
32.8
58.4
9.3
33.0
68.8 35.7
89.9
164.6
HLBVH-med 15.5
58.9
74.1 16.3
123.4
110.8 14.7
37.7
62.6 41.7
28.4
110.7 162.5
45.6
417.5
HLBVH-SAH 38.9
59.8
95.6 34.8
127.3
126.1 29.3
38.4
76.5 67.2
29.1
134.5 224.6
57.8
425.6

Table 2: Performance comparison of tested methods. The reported numbers represent the average values for the whole animation sequence. The times were measured using CPU side timers and thus they include the CUDA kernel execution and setup
times. For SAH∗ , SAH0 , and T-SAH method a single BVH is used for the whole animation, SAH-rebuild, HLBVH-med, and
HLBVH-SAH perform BVH rebuild in each frame. Note that for BART Museum* we used three BVHs optimized for different
parts of the animation. The results with the best trace speed and total time for a given scene are highlighted in bold (note that
this does not include the SAH-rebuild reference method).

want to study the possibility of taking into account the expected ray distribution by creating BVHs optimized not only
for the scene geometry changes, but also for the expectedcamera positions. Finally, we want to exploit T-SAH in thecontext of other applications such as collision detection or
run time BVH optimization using temporal prediction of object movement.
Acknowledgements
This research was supported by the Czech Science Foundation under research program P202/12/2413 (Opalis) and theGrant Agency of the Czech Technical University in Prague,
grant No. SGS13/214/OHK3/3T/13.
References[FLF12] F ELTMAN N., L EE M., FATAHALIAN K.: SRDH: Specializing BVH Construction and Traversal Order Using Representative Shadow Ray Sets. In Proceedings of HPG (2012),
pp. 49–55. 2[Gar09] G ARANZHA K.: The use of precomputed triangle clusters for accelerated ray tracing in dynamic scenes. Comput.
Graph. Forum 28, 4 (2009), 1199–1206. 2[GFW∗ 06] G UNTHER J., F RIEDRICH H., WALD I., S EIDEL H.P., S LUSALLEK P.: Ray tracing animated scenes using motion
decomposition. Computer Graphics Forum 25, 3 (2006), 517–
525. 2[GHFB13] G U Y., H E Y., FATAHALIAN K., B LELLOCH G. E.:
Efficient BVH Construction via Approximate Agglomerative
Clustering. In Proceedings of High Performance Graphics(2013), ACM, pp. 81–88. 1, 2, 7
[GPM11] G ARANZHA K., PANTALEONI J., M C A LLISTER D.:
Simpler and Faster HLBVH with Work Queues. In Proceedingsof posium on High Performance Graphics (2011), pp. 59–64. 2,
5[AKL13] A ILA T., K ARRAS T., L AINE S.: On Quality Metrics
of Bounding Volume Hierarchies. In In Proceedings of High Performance Graphics (2013), ACM, pp. 101–108. 2[GS87] G OLDSMITH J., S ALMON J.: Automatic Creation of Object Hierarchies for Ray Tracing. IEEE Computer Graphics andApplications 7, 5 (May 1987), 14–20. 2[AL09] A ILA T., L AINE S.: Understanding the Efficiency of Ray
Traversal on GPUs. In Proceedings of HPG (2009), pp. 145–149.
5[HHS06] H AVRAN V., H ERZOG R., S EIDEL H.-P.: On the Fast
Construction of Spatial Data Structures for Ray Tracing. In Proceedings of IEEE Symposium on Interactive Ray Tracing 2006
(Sept 2006), pp. 71–80. 2[BH09] B ITTNER J., H AVRAN V.: RDH: Ray Distribution
Heuristics for Construction of Spatial Data Structures. In Proceedings of SCCG (2009), ACM, pp. 61–67. 2[BHH13] B ITTNER J., H APALA M., H AVRAN V.: Fast InsertionBased Optimization of Bounding Volume Hierarchies. Computer
Graphics Forum 32, 1 (2013), 85–100. 1, 2, 3, 4, 5
[FFD09] FABIANOWSKI B., F OWLER C., D INGLIANA J.: A cost
metric for scene-interior ray origins. Eurographics, Short Papers(2009), 49–52. 2
c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.

[Hun08] H UNT W.: Corrections to the surface area metric withrespect to mail-boxing. In Interactive Ray Tracing, 2008. RT
2008. IEEE Symposium on (Aug 2008), pp. 77–80. 2[IWP07] I ZE T., WALD I., PARKER S. G.: Asynchronous BVH
Construction for Ray Tracing Dynamic Scenes on Parallel MultiCore Architectures. In Proceedings of Symposium on Parallel
Graphics and Visualization ’07 (2007), pp. 101–108. 2[KA13]K ARRAS T., A ILA T.:

Fast Parallel Construction of

J. Bittner & D. Meister / T-SAH: Animation Optimized Bounding Volume Hierarchies

total time [ms]total time [ms]f0
T-SAH C

900
800
700
600
500
400
300
200
100
0
0

10

20

30

40

50

60

70

80

60
50
40
30
20
10
0
0

10

20

30

40

50

60

70

80

HLBVH-med

90

frame [-]

HLBVH-SAH

220
200
180
160
140
120
100
80
60
40

90

0
trace speed [MRays/s]

trace speed [MRays/s]

SAH∗

SAH0

SAH-rebuild

10

20

30

40

50

60

70

80

90

10

20

30

40

50

60

70

80

90

45
40
35
30
25
20
15
10
0

frame [-]

Figure 6: Plots of the total frame times and ray tracing speed for the Dragon-Bunny scene (left) and Breaking Lion scene(right).

High-Quality Bounding Volume Hierarchies. In Proceedings ofHigh Performance Graphics (2013), ACM, pp. 89–100. 1, 2

Geometry. In Proceedings of High Performance Graphics ’10(2010), pp. 87–95. 2[Kar12] K ARRAS T.: Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees. In Proceedings of High
Performance Graphics (2012), pp. 33–37. 2[Wal07] WALD I.: On fast Construction of SAH based Bounding Volume Hierarchies. In Proceedings of the Symposium on
Interactive Ray Tracing (2007), pp. 33–40. 2[Ken08] K ENSLER A.: Tree Rotations for Improving Bounding
Volume Hierarchies. In Proceedings of the 2008 IEEE Symposium on Interactive Ray Tracing (Aug 2008), pp. 73–76. 2[Wal12] WALD I.: Fast Construction of SAH BVHs on the Intel
Many Integrated Core (MIC) Architecture. IEEE Transactions
on Visualization and Computer Graphics 18, 1 (2012), 47–57. 2[KIS∗ 12] KOPTA D., I ZE T., S PJUT J., B RUNVAND E., DAVISA., K ENSLER A.: Fast, effective bvh updates for animatedscenes. In Proceedings of Symposium on Interactive 3D Graphics
and Games (2012), pp. 197–204. 2, 7

[WBKP08] WALTER B., BALA K., K ULKARNI M., P INGALI
K.: Fast Agglomerative Clustering for Rendering. In IEEE Symposium on Interactive Ray Tracing (2008), pp. 81–86. 1, 2

[KK86] K AY T. L., K AJIYA J. T.: Ray Tracing Complex Scenes.
Computer Graphics (SIGGRAPH ’86 Proceedings) 20, 4 (1986),
269–278. 2[WBS03] WALD I., B ENTHIN C., S LUSALLEK P.: Distributed
interactive ray tracing of dynamic scenes. In Proceedings of theIEEE Symposium on Parallel and Large-Data Visualization andGraphics (2003), pp. 77–86. 2, 7

[LGS∗ 09] L AUTERBACH C., G ARLAND M., S ENGUPTA S.,
L UEBKE D., M ANOCHA D.: Fast BVH Construction on GPUs.
Comput. Graph. Forum 28, 2 (2009), 375–384. 2[WBS07] WALD I., B OULOS S., S HIRLEY P.: Ray tracing deformable scenes using dynamic bounding volume hierarchies.
ACM Trans. Graph. 26, 1 (Jan. 2007). 2, 5

[LYTM06] L AUTERBACH C., YOON S.-E., T UFT D.,
M ANOCHA D.:
RT-DEFORM: Interactive Ray Tracingof Dynamic Scenes using BVHs. In IEEE Symposium on
Interactive Ray Tracing (RT’06) (Sept 2006), pp. 39–46. 2[WMG∗ 09] WALD I., M ARK W. R., G ÜNTHER J., B OULOS S.,I ZE T., H UNT W. A., PARKER S. G., S HIRLEY P.: State of theart in ray tracing animated scenes. Comput. Graph. Forum 28, 6(2009), 1691–1722. 2[Mor11] M ORA B.: Naive ray-tracing: A divide-and-conquer approach. ACM Trans. Graph. 30, 5 (2011), 117:1–117:12. 2[WWB∗ 14] WALD I., W OOP S., B ENTHIN C., J OHNSON G. S.,
E RNST M.: Embree: A kernel framework for efficient CPU ray
tracing. ACM Transactions on Graphics 33 (2014). 2[Ols07] O LSSON J.: Ray Tracing Animations Using 4D Kd-Trees.
Master’s thesis, Lund University, 2007. 2[PL10] PANTALEONI J., L UEBKE D.: HLBVH: Hierarchical
LBVH Construction for Real-Time Ray Tracing of Dynamic[YCM07] YOON S.-E., C URTIS S., M ANOCHA D.: Ray Tracing
Dynamic Scenes using Selective Restructuring. In Proceedingsof Eurographics Symposium on Rendering (2007), pp. 73–84. 2

c 2015 The Author(s)Computer Graphics Forum c 2015 The Eurographics Association and John Wiley & Sons Ltd.