Efficient BVH Construction via Approximate Agglomerative Clustering
Yan GuYong He

Kayvon Fatahalian

Guy Blelloch

Carnegie Mellon University

Abstract
We introduce Approximate Agglomerative Clustering (AAC), an
efficient, easily parallelizable algorithm for generating high-quality
bounding volume hierarchies using agglomerative clustering. The
main idea of AAC is to compute an approximation to the true
greedy agglomerative clustering solution by restricting the set ofcandidates inspected when identifying neighboring geometry in thescene. The result is a simple algorithm that often produces higher
quality hierarchies (in terms of subsequent ray tracing cost) than afull sweep SAH build yet executes in less time than the widely used
top-down, approximate SAH build algorithm based on binning.

Algorithm 1 BVH construction using O(N 3 ) agglom. clustering
Input: scene primitives P = {P1 , P2 , · · · , PN }.
Output: a scene BVH (returns root node)
Clusters C = P ;// initialize with singleton clusters
while Size(C) > 1 do
Best = ∞;for all Ci ∈ C do
for all Cj ∈ C do
if Ci 6= Cj and d(Ci , Cj ) < Best thenBest = d(Ci , Cj );Lef t = Ci ; Right = Cj ;end ifend forend forCluster C 0 = new Cluster(Lef t, Right);
C = C − {Lef t} − {Right} + {C 0 };end while
return C;

CR Categories: I.3.7 [Computer Graphics]: Three-Dimensional
Graphics and Realism—Raytracing;
Keywords: Ray tracing, bounding-volume hierarchy, agglomerative clustering
Links:1DL

PDF

Introduction

In recent years there has been considerable interest in the designof efficient, parallel algorithms for constructing bounding volume
hierarchies (BVH) for ray tracing. The current best practice technique [Wald 2007] for constructing a high-quality hierarchy in parallel with reasonable cost on a multi-core CPU uses a divide-andconquer algorithm (top-down) that establishes geometry groupings
according to an approximate surface area heuristic [Goldsmith andSalmon 1987]. While higher quality structures can be generated using agglomerative (bottom-up) construction schemes [Walter et al.
2008], these methods, even with recent optimizations, have notbeen demonstrated to be performance competitive with best practice divisive implementations.
In this paper we introduce a new algorithm that efficiently constructs BVHs in a bottom-up manner using agglomerative clustering. The resulting hierarchies are often of higher quality than those
produced by a top-down, full sweep SAH build, and they can beconstructed in parallel in less time than a fast approximate SAH
build that employs the widely used optimization of “binning” [Wald2007]. Unlike previous work on bottom-up BVH construction, ouralgorithm realizes high performance by generating a structure thatis a close approximation to (but does not necessarily match) the
scene geometry’s greedy agglomerative clustering solution.

2

Background

The pursuit of practical, real-time ray tracing systems for manycore CPUs and GPUs has inspired many efforts to reduce the timerequired to build high-quality ray-tracing acceleration structures.
(A high-quality structure reduces the cost of performing ray-sceneintersection queries.) Promising techniques have been documented
extensively, and we refer the reader to [Wald 2007; Wald et al.
2007] and [Karras 2012] for excellent summaries of the design
space and key challenges of modern approaches.
In this paper, we focus on the specific problem of performing afull (“from scratch”) construction of a bounding volume hierarchy
from scene geometry. At present, the preferred approach to constructing a BVH on many-core CPU architectures is to build thehierarchy top-down, using primitive binning as a cheap approximation to evaluating the full surface area heuristic. Parallel implementations of this approach on modern architectures are described indetail in [Wald 2007; Wald 2012]. GPU-based implementations of
BVH construction discard use of the surface area heuristic in favorof maximizing parallelism during construction of the upper levelsof the hierarchy [Lauterbach et al. 2009; Karras 2012]. These implementations achieve high performance, but produce lower quality
BVHs, making them less desirable for use in ray tracing.
Our efforts are inspired by previous work by [Walter et al. 2008]
which explores the use of agglomerative clustering (as opposed to
top-down divisive methods) to build high-quality BVHs. Agglomerative clustering is a greedy algorithm that is initialized with eachscene primitive as a singleton geometry cluster, then repeatedly
combines the two nearest clusters in the scene into one. This process continues until a single cluster, representing all primitives inthe scene, remains. Agglomerative clustering is a popular techniquein many fields as it can produce high-quality hierarchies and also
generalizes to arbitrary cluster distance functions, but its use has
been limited in computer graphics due to its high cost. Solutions
have O(N 2 ) complexity [Olson 1995], but for clarity we provide
a naive, O(N 3 ) algorithm for constructing a BVH using agglom-erative clustering in Algorithm 1. In the pseudocode d(Ci , Cj ) is
the cluster distance function. In this paper we follow [Walter et al.
2008] and define d(Ci , Cj ) as the surface area of the bounding box
enclosing primitives from both clusters.
An expensive operation in an agglomerative BVH build is finding
the nearest neighbor (e.g., closest cluster) to a given cluster. Walter
et al.’s key idea was to accelerate this search by storing remaining
clusters in a K-D tree constructed using a low-cost, top-down partitioning strategy such as coordinate bisection. Thus their approach
uses a low-quality, but cheap-to-compute, hierarchical acceleration
structure to accelerate construction of a high-quality one. Walter
et al. used this idea to design two agglomerative BVH build algorithms (heap-based clustering and locally-ordered clustering) thatwere empirically shown to scale to large scenes and, for randomrays, reduced tracing cost 15-30% when compared to a top-downbinned SAH build. Although this work established agglomerative
clustering as a viable strategy for BVH construction, the resulting
build times remained slow compared to top-down methods. The
algorithm required complicated insertion and deletion of clusters
from a K-D tree (or a periodic K-D tree rebuild) and its parallelization requires speculative execution. Although Walter et al. reported
performance within a factor of two of a top-down build for unoptimized single-core implementations in Java, our experiences reimplementing and optimizing these techniques in C++ yield singlecore performance that is (even after non-trivial effort) about fourto seven times slower than a binned SAH build (see Table 2). The
primary contribution of this paper is a new algorithm, based on agglomerative clustering, that yields similar quality BVHs to Walter etal.’s solutions, but is simpler to implement, and offers performancecomparable to, and often better than, a top-down binned BVH build.
Furthermore, it parallelizes well on a modern many-core CPU.

3

Approximate Agglomerative Clustering

The key observation underlying our new agglomerative clustering technique is that the cost of forming new clusters via locallyordered or heap-based agglomerative clustering [Walter et al. 2008]is highest at the beginning of the construction process when thenumber of clusters is large. Since these techniques are initializedwith one cluster per scene primitive (N initial clusters), each nearest neighbor search at the beginning of hierarchy construction is a
global operation incurring cost at least O(log N ). Thus, constructing the bottom-most nodes of the resulting BVH dominates overall
computation cost. This property is particularly undesirable since
combining the original singleton clusters is a highly local operationthat need not incur the high cost of a scene-wide search.
Thus, the main idea of our approach is to accelerate BVH construction using an approximate agglomerative clustering (AAC) methodthat restricts nearest neighbor search to a small subset of neighboring scene elements. We show that this approximation minimally impacts resulting BVH quality but significantly accelerates
the speed of BVH construction.
Conceptually the idea of the AAC method (illustrated in Figure 1)
is to quickly organize scene primitives into a binary tree based onrecursive coordinate bisection—i.e., at each level of the tree one
coordinate (x, y, or z) is bisected. Leaf nodes in this tree (which
we call the constraint tree) contain a small set of scene primitives(singleton clusters) whose centers fall within the corresponding region of space. BVH construction via agglomerative clustering thenproceeds bottom up, with the constraint tree controlling what primitives can be clustered. In particular each node of the constraint tree
generates a set of un-combined clusters by taking the union of justthe un-combined clusters generated by its two children and reducing the size of this union by greedily combining some of the clus-

Interior node:P primitives
CombineClusters(CL U CR, P )LR
Leaf node:
P ≤Figure 1: Illustration of the AAC algorithm’s “constraint tree”
with groups of at most δ primitives at the leaves. Each node represents a computation that combines clusters from its two children
using agglomerative clustering (see CombineClusters). The
size of a node in the figure represents the number of clusters returned by the node, which increases going up the tree. The last stepof the algorithm (top node) combines all remaining clusters into asingle cluster corresponding to the BVH root node.
ters. The number of un-combined clusters returned by each node
is controlled by the algorithm and is somewhere between 1 (everything has been combined into a single cluster) and the number ofprimitives in the subtree (nothing has been combined yet). At theroot of the constraint tree the clusters are reduced to a single cluster
using a final step of true greedy agglomerative clustering.
An important property of the method that balances efficiency andaccuracy is to increase the number of clusters generated by thenodes as we proceed up the tree, but decrease the total number
across each level. This keeps the computation required near theleaves small, but allows for more accuracy at modest costs higher
in the tree where there are fewer nodes. We control the number ofclusters generated by a node using a cluster count reduction function f , described below.

3.1

Algorithm Basics

We now go into more detail on how we efficiently implement the
AAC method. Pseudocode is given in Algorithms 2, 3 and 4.
Primitive sort. The algorithm first sorts scene primitives according to the Morton code (z-order) of their bounding box center [Gargantini 1982; Bern et al. 1999]. Generating the Morton code fromprimitive centers and subsequent radix sort are cheap to computeand easily parallelized. Our implementation constructs a Morton
code with dlog4 N e bits per dimension and uses a variable-bit radix
sort that executes in time linear in the number of primitives (seeSection 3.4.1 for details). Indeed the Morton code is a common
technique used in several high-performance (but lower tree quality)
algorithms for BVH construction [Lauterbach et al. 2009; Karras
2012]. Unlike these algorithms, the AAC algorithm does not use
the ordering directly to build a BVH. Rather it uses the implicit
structure to define constraints on cluster combining.
Constraint tree traversal (“downward phase”). Following
the sort, the AAC algorithm invokes the recursive function
BuildTree (Algorithm 3) to traverse the implicit constraint tree
structure organizing the primitives. (Note that the constraint tree
is implicit in the Morton code sort, it is never explicitly constructed.) Following [Lauterbach et al. 2009], in each traversal step,
MakePartition (line 5) bisects the current spatial extent basedon the next bit in the Morton code. This serves to partition the prim-

Algorithm 2 AAC(P )Input: list of all scene primitives P
Output: BVH containing primitives in P

Algorithm 4 CombineClusters(C, n)Input: list of clusters C
Output: list of at most n clusters

1: Compute Morton code for centers of P ;2: RadixSort P by Morton code;
3: C = BuildTree(P );4: return CombineClusters(C, 1);

1: for all Ci ∈ C do
2:
Ci .closest = C.FindBestMatch(Ci );3: end for

Algorithm 3 BuildTree(P )Input: subset of scene primitives P
Output: at most f (|P |) clusters containing primitives in P
1: if (|P | < δ) then2:
Initialize C with P ;3:
return CombineClusters(C, f (δ));
4: end if
5: hPL , PR i = MakePartition(P );6: C = BuildTree(PL ) ∪ BuildTree(PR );7: return CombineClusters(C, f (|P |));

itive set P into subsets PL and PR . The partition is easily computed
using binary search through P to find where the Morton code for theprimitives switches from 0 to 1 at the current bit position. As noted
previously [Gargantini 1982; Lauterbach et al. 2009], the Morton
code sort ensures that all primitives on the 0 side of the flip point in
P are on the low side of the coordinate bisection (in PL ), and primitives on the 1 side are on the high side (PR ), so no data movement isnecessary when forming these subsets. Therefore the work spent ontree traversal is T (n) = T (n−a)+T (a)+O(log(min(a, n−a))),which is linear in n for a ≥ 1. In the rare event that the algorithm
exhausts the Morton code bits during traversal without partitioning
the primitives into a sufficiently small set, we continue traversal bypartitioning P in half each step.
Bottom-up clustering (“upward phase”). Agglomerative clustering begins once the number of primitives in P drops below thethreshold δ (Algorithm 3, line 1), where δ is a parameter of thealgorithm. Like locally-ordered clustering, the AAC algorithm initializes cluster formation by creating one singleton cluster per primitive (line 2). We select δ to be small (in Section 4 we demonstratehigh-quality builds using δ = 4 and 20).
The algorithm CombineClusters is the key component of thebottom up clustering. It is used to reduce the number of clusters at
every node of the constraint tree to f (|P |), where the cluster countreduction function f is a parameter of the algorithm. At the leavesof the tree this reduces the initial set of primitives to the required
size (line 3), and at internal nodes it reduces the union of the two
sets of clusters from its children to the required size (lines 6 and
7). Since the number of clusters in C is never that large, we use
a brute force method to reduce the number of clusters as describedin Algorithm 4. The method findBestMatch implements linear
search over all clusters in C. This algorithm takes at least O(|C|2 )time. CombineClusters then greedily selects the closest pair ofmatches by find the best best-match, and combines this pair. This isrepeated until n clusters remain. We defer further details about our
optimized implementation of CombineClusters to Section 3.3.
Each invocation of Buildtree(P ) returns a list of f (|P |) clusters produced via agglomerative clustering of the contents of C.
While the recursive splitting phase of BuildTree (“downward”
phase) serves to partition scene primitives into local groups, the recombination phase that follows the return of child recursive calls(“upward” phase) serves to agglomerate the clusters resulting fromthe PL and PR primitive sets. The call to CombineClusters

4: while |C| > n do
5:Best = ∞;6:
for all Ci ∈ C do
7:
if d (Ci , Ci .closest) < Best then
8:
Best = d (Ci , Ci .closest);
9:
Lef t = Ci ; Right = Ci .closest;10:
end if
11:
end for12:c0 = new Cluster(Lef t, Right);
13:
C = C − {Lef t, Right} + {c0 };14:
c0 .closest = C.FindBestMatch(c0 );15:
for all Ci ∈ C do
16:
if Ci .closest ∈ {Lef t, Right} then17:
Ci .closest = C.FindBestMatch(Ci );18:
end if
19:
end for
20: end while
21: return C;

on line 7 of Algorithm 3 combines the clusters returned from theleft and right constraint tree nodes into a smaller number of clusters determined by the function f . Notice that clusters containing
primitives in different child primitive sets as given by the constraint
tree can be combined into the same output cluster in this step. The
recombination phase continues until reaching the root of the constraint tree, which returns f (|P |) clusters. Last, the remaining clusters are reduced to a single cluster on line 4 of Algorithm 2. The
result is a BVH containing all primitives in the scene.
Algorithm Parameters. The AAC algorithm has two parameters:
the cluster count reduction function f and the traversal stopping
threshold δ. These parameters modify the extent to which the algorithm approximates the full agglomerative clustering solution andthus affect the quality of the generated BVH and its construction
cost. The result of the function f (x) can vary between 1 and x. A
value of 1 yields a cheap to compute, but poor-quality BVH that issimilar to directly building the BVH from the results of the Mortonsort [Lauterbach et al. 2009]. Setting f (x) = x defers all cluster agglomeration to the root node of the bisection tree, causing the AAC
algorithm to degenerate into a true greedy agglomerative clustering method. To achieve performance between these two extremes,
our implementation of AAC algorithm uses functions of the formf (x) = cxα for 0 ≤ α ≤ 1 and some constant c (see Section 3.2).
Discussion. Before analyzing the overall complexity of the algorithm and describing implementation details, we highlight key differences between AAC construction and locally-ordered clustering.
Firstly, the AAC build’s output is an approximation to the results oflocally-ordered clustering (the two algorithms may generate different BVHs). While locally-ordered clustering yields the same result
as a brute-force clustering implementation run on all scene primitives (it will always cluster the two closest clusters), the primitive
partitioning performed during AAC build’s downward phase constrains what clusters can be formed. For example, it is possible
for partitioning to separate the two closest primitives in the scene.
Although these primitives will likely be grouped in some interior
node of the resulting BVH, they will not be contained in the sameleaf cluster.

Since each constraint tree node returns many un-combined clusters
as determined by the cluster count reduction function f , the AAC
algorithm has flexibility to delay combining of certain clusters until
higher levels of the constraint tree. In particular clusters containing large primitives will get pushed up the constraint tree without
combining until they get to a node which represents a spatial regionof the “appropriate size”—i.e. for which all clusters are about aslarge. This is because the greedy method combines clusters withthe smaller spatial bounds first (recall d(Ci , Cj ) is the resulting aggregate bounding box size), leaving large ones un-combined. Combining large primitives high in the constraint tree is what makes agglomerative clustering work well in comparison to top-down methods when there is large variation in the size of scene primitives, andis a reason why the AAC algorithm works almost as well as the true
greedy agglomerative clustering.
The second difference is that locally-ordered clustering uses a KD tree to accelerate finding the minimum distance cluster from apotentially large collection (this adds significant complexity to thealgorithm since the tree must support cluster insertions and deletions during the clustering process). In contrast, at both the leaf
and interior levels of the constraint tree, the AAC build never performs clustering on a large number of elements. As a result, there
is no need for a K-D tree to accelerate search. In an AAC build,presorting geometry and the constraint tree traversal process serve
to limit the number of clusters processed at any one point by thealgorithm (to a local set), not to accelerate nearest neighbor searchover a scene-wide collection.

3.2

Cost Analysis

A fully balanced constraint tree with height H and leaves containing δ primitives has 2H = N/δ leaves (where N is the total
number of primitives contained in the tree). Thus, execution of
CombineClusters for leaf nodes constitutes O(2H × δ 2 ) work.
Processing CombineClusters in all H levels requires work:H2X
2H−i · f δ · 2i!

i=0

If we assume f (x) = c · x1/2 , the amount of work done on eachlevel is about the same and the time complexity is:
!
H
 √
2
X
H−i
i
O
2
· c δ·2= O(H · 2H c2 δ) = O(N log N ) .
i=0

A smaller choice of α in f (x), allows the AAC build to run in linear
time. In particular for f (x) = c · x0.5− ,  > 0, the work per level
geometrically decreases going up the tree, and the time complexity
is:
!
!
H
H

1−2
X
X
H−i
2
i
H−2i
O
2
·c δ·2=O
2= O(N ) .
i=0

results of
BuildTree(TL)

results offill distance matrix results of
BuildTree(T)BuildTree(TR) (prior to calling
CombineClusters)

Figure 2: Careful data arrangement allows reuse of cluster distance computations from child nodes. Four steps in computing clusters for a subtree T are shown. Distance results computed during
processing of the left subtree (green) and right subtree (purple) arealready stored in the correct location in the distance matrix for T .
Thus, for the balanced case, as long as the number of clusters returned at each node is smaller than the square root of the number ofprimitives contained in the subtree, the algorithm takes linear time.
A completely imbalanced constraint tree will have depth N − δand the size of each node is O(f (N )). Therefore assuming thatf (x) = c · xα the AAC build will have O min N 2 , N 1+2αtime complexity. In practice this worst case cannot occur, at least
for fixed or floating-point representations of primitive coordinates,
since such numbers do not have the precision to represent such an
unbalanced tree.
0.5+

In this section we analyze the AAC algorithm for the case where recursive coordinate bisection yields a fully balanced constraint tree,
as well as under the worst-case assumption of a completely unbalanced tree. In practice we observe performance close to the fullybalanced case. In this analysis we also assume the execution of
CombineClusters has O(|C|2 ) cost, which we observe to be
the case in practice although it is theoretically possible to constructgeometric configurations that require O(|C|3 ) work. As discussed
earlier in Section 3.1, the cost of sorting the Morton codes andthe combined cost of MakePartition is linear in the numberof primitives.

O

R

i=0

In practice, we choose c = δ 2 , which indicates that f (δ) = 2δ ,so that AAC algorithm halves the number of clusters on leaf nodes.

3.3

Optimizations

Although the AAC build algorithm is conceptually quite simple, anumber of important optimizations to CombineClusters wererequired to achieve the high performance reported in Section 4.2.
3.3.1

Construction Speed

Reduce redundant computation of cluster distances. The cluster
distance function d(Ci , Cj ) is an expensive function that requires
loading two cluster bounding boxes from memory, then calculating
an aggregate bounding box and its surface area. Thus, at the start of
CombineClusters we pre-compute all possible d(Ci , Cj ) forthe clusters in C and save these results in a matrix. This matrix issymmetric, so only its upper-triangle need be calculated and stored.
Moreover, each clustering step requires removal of two clusters
from the set C (line 13). Our implementation replaces one deleted
cluster with the newly formed cluster c0 , and the other deleted cluster with the last cluster in the set. Thus the precomputed matrix remains compact without much data movement, and its size decreases
by one each iteration.
A second optimization is that cluster distance values available atthe termination of CombineClusters(C,n) are values that arealso needed during clustering at the next level up the constraint tree.
These distances are retained and reused, as described further in thenext optimization.
Reducing data movement. The storage required for the distancematrix computed by CombineClusters is greater at higher levels of the constraint tree (size of the set C is larger). Careful management of this temporary storage can eliminate the need for dynamic allocation during the build and also enable reuse of distancescomputed during child processing.

As illustrated in Figure 2, suppose we have a pre-allocated a distance matrix with R rows and columns and seek to process subtree T . Processing the left subtree TL can be carried out using
a fraction of the allocation shown in green. (Specifically, the final distance matrix for clusters returned from TL is stored at thislocation.) Then TR is processed using an adjacent storage region,
producing the distance matrix shown in purple. The computation of
distances by node T can reuse these values. Only the new distances,
shown in orange, must be computed before clustering is performedby CombineClusters for node T . The final distance matrix forthe node T is given in blue.
On average, for n tree nodes, the size R of the pre-allocated matrix
for the average case should be:log(n/δ)

R=

X
i=1

f

n
2i

≤f

n
2

·

1
.
1 − 0.50.5−

Our implementation sets R = 4c · n0.5−/2 , resulting in an allocation that is sublinear in the total number of primitives n. Although
it is possible to create a scene for which construction requires more
temporary storage than this bound (requiring dynamic reallocation),
we have not encountered this situation in practice.
3.3.2

Subtree Flatting for Improved BVH Quality

After each cluster merge, the AAC algorithm performs a check todetermine whether to maintain the BVH subtree corresponding tothis cluster, or to flatten the subtree into a list of primitives. The
optimization of electing not to build a subtree structure is a natural and standard optimization in top-down SAH builds, but an agglomerative build must detect and “undo” the subtree it has alreadyconstructed when a flat list of primitives will reduce expected ray
tracing cost. To detect this condition, we employ a cost metric issimilar to the SAH cost metric, however since the flattening checkproceeds bottom-up the true cost of the subtrees is known. (No linear approximation of subtree cost is required.) The cost C(T ) of
BVH subtree T is:(
Ct · |T |C(T ) = min S(Tl )r)(Cb + C(Tl )) + S(T(Cb + C(Tr ))
S(T )
S(T )
where |T | is the number of primitives in T , Tl and Tr are the left
and right subtrees of T , S(T ) is the surface area of the boundingbox of T , and Cb and Ct are estimated ray-box and ray-triangle intersection costs. Nodes are flattened if the above metric indicatescost is minimized by doing so. This process is similar in spirit to thesubtree flattening performed after a top-down SAH build by [Bittner et al. 2013]. We observe that tree flattening modestly improves
BVH quality (reduces intersection and traversal computations during ray tracing) by 3-4%.

3.4

Parallelism

The AAC algorithm is amenable to parallel implementation ona multi-core CPU. As with SAH-based top-down builds, the algorithm’s divide-and-conquer structure creates many independent
subtasks corresponding to subtrees. These subtasks can be processed by different cores in parallel.
The lack of parallelism at the top of the constraint tree is less problematic for an AAC build than a traditional top-down SAH build,since the work performed in the upper nodes of the tree is substantially less. For example, for the 7.9 M triangle San Miguel scene(see Table 2), the topmost clustering step must only process 1,724
clusters. As a result, we do not attempt any intra-node parallelization of the algorithm and still observe good speedup on 32 cores(see Section 4.2). We note that multi-core parallelization of theclustering process within each node would incur similar complexities as those encountered in [Walter et al. 2008]. However, thebrute-force implementation of CombineClusters is amenable
to vector parallelization (we have not attempted this optimization).
During top-down bisection, our implementation creates approximately eight times as many parallel subtasks as cores. Subtrees
associated with each task are evaluated in serial on a core, using all
the storage and redundant-computation elimination optimizations
described in Section 3.3. Note these optimizations induce a serial
ordering on the processing of subtrees, so they cannot be employed
for subtrees executed in parallel.
3.4.1

Radix Sort

Our AAC implementation employs a parallel radix sort that sorts
log n
bits per pass, where n is the number of keys being sorted.
2
Since the number of bits we use for the Morton code is O(log n),
the number of passes is a constant, and the total work of the sort
is linear in N . The sort is based on the integer sort found in the
Problem Based Benchmark Suite [Shun√ et al. 2012]. The√ algorithm
partitions the array of size
√ n into n blocks of size n. Withineach block we maintain n buckets and count the number of entriesof each possible value of the log2 n bits being sorted. The blocks canbe processed in parallel since the buckets are maintained √separately.
√
The result of the counting phase can be viewed as an n × narray of counts with the buckets across the rows and processors
down the columns. By flattening this array in column-major order,
then performing a parallel plus-scan on the result, we get the offset
location for the appropriate bucket for each processor. A final passover the data array can be used to permute the data to its sorted
location. This is again parallel over the blocks.

4

Evaluation

We evaluated AAC BVH construction by comparing its performance and output BVH quality against that of three alternate
BVH build implementations (1) a top-down full-sweep SAH build(SAH), (2) a top-down “binned” SAH build (SAH-BIN) that evaluates SAH-cost at the boundaries of 16 bins along the longest axis,and (3) locally-ordered clustering (Local-Ord) as described in [Walter et al. 2008]. Since implementation and machine differences canmake it difficult to compare performance (and even tree-quality)
measurements against those reported in previous publications, wedeveloped our own implementations of each algorithm. Our implementations have undergone substantial optimization (with one
exception: our implementations of the algorithms do not use SIMD
intrinsics). Still, Table 2 indicates that SAH is over two times fasterthan that published in [Wald 2007], SAH-BIN is within a factorof 1.7 (adding SIMD execution would likely more than make up
this difference), and Local-Ord is at least two times faster than theimplementation in [Walter et al. 2008]. Our experiments include
two configurations of AAC construction: AAC-HQ is configured
conservatively to build a high-quality BVH (δ = 20,  = 0.1).
AAC-Fast is configured for high performance (δ = 4,  = 0.2).
We executed all five build algorithms on the six scenes shown above
Table 2. (Half-Life is a scene containing geometry exported from
Half-Life 2: Episode 2.) Renderings used 16 diffuse bounce rays
per pixel and four-to-five point light sources depending on scene.
All experiments were run on a 40-core machine with four 10-coreIntel E7-8870 Xeon processors (1066 MHz bus). Parallel implementations were compiled with CilkPlus, which is included in g++.

Avg. Ray-Scene Intersection Cost
(Relative to SAH-BIN)

Ray-Scene Intersection Cost (Relative to SAH-BIN)
1.0

Ray-triangle
tests

0.8
0.6

Ray-box
tests

0.4
0.2
1 2 3 4 5Sponza

1 2 3 4 5
Fairy

1 2 3 4 5
Conference

1: SAH-BIN
2: SAH (full sweep)
3: Local-Ord

1 2 3 4 5
Buddha

1 2 3 4 5
Half-Life1 2 3 4 5
San Miguel

4: AAC-HQ (δ = 20, ε = 0.1)
5: AAC-Fast (δ = 4, ε = 0.2)

Figure 3: Cost of ray-scene intersection (measured as the sum of BVH node traversals and triangle intersection tests). Values are averaged
over all rays (primary, shadow, and gather) and normalized to the cost of traversal through the BVH constructed using SAH-BIN. In all
scenes but Buddha, both the AAC-HQ and AAC-Fast configurations yield as good (or better) trees than a full sweep SAH build. The benefitsof bottom-up agglomerative construction diminish when all scene triangles are similarly sized, as is the case in a model like Buddha.
Local-Ord

AAC-HQ

AAC-Fast.89 / .91
.97 / .94
.86 / .82
.98 / .95
.81 / .87
.88 / .89

.86 / .84
.97 / .88
.76 / .68
1.08 / 1.03
.86 / .86
.82 / .75

.86 / .82
.95 / .84
.79 / .67
1.09 / 1.03
.80 / .83
.83 / .78

.90 / .90
.94 / .88
.78 / .67
1.07 / 1.04
.82 / .87
.90 / .84

Table 1: Normalized ray-scene intersection costs for diffuse bounce(left value) and shadow (right value) rays. Costs are normalized tothat of SAH-BIN. In general, the relative improvement of the agglomerative techniques is higher for shadow rays since large occluders are lifted to higher levels of the BVH. Primary ray results
are similar to diffuse bounce rays and are not shown.

4.1

BVH Quality

Figure 3 compares the cost of tracing rays through the BVHs produced by each algorithm, normalized to that of SAH-BIN. The sumof node traversal steps (bottom part of bar) and intersection tests(top of bar in lighter color) is used as a simple proxy for tracing
cost. (We find tracing wall clock times, despite their dependence
on the ray tracer used, track these counts well.) Values in the figure are the result of averaging counts over primary, shadow, anddiffuse bounce rays. More detailed individual statistics for shadow
and diffuse bounce rays are given in Table 1.
Figure 3 shows that the approximate agglomerative clustering performed by the AAC build algorithm does not significantly impact
the quality of the resulting BVH. AAC-HQ produces BVHs thathave essentially the same quality as those produced by Local-Ord(in the worst case of San Miguel, AAC-HQ and Local-Ord costs
differ by only 3%). Tracing cost ranges from 15% to 30% less thanthat of the SAH-BIN built BVH, and it remains lower than the full
SAH build for all scenes but Buddha. More surprisingly, AAC-Fastalso produces BVHs that are as good or better than the full sweep
build in these cases.
We also observed that BVHs produced by the agglomerative methods realize the greater benefit for shadow rays than radiance rays,
particularly when scenes contain primitives with large spatial extent(Table 1). This is because the agglomerative approaches are more

Multi-core Speedup (San Miguel)40

Linear Speedup
AAC-HQ
AAC-Fast

32

SpeedupSponzaFairy
Conference
BuddhaHalf-Life
San-Miguel

SAH

24
16
8
0

1 4

8

16

24

32

Number of Cores

40

40 HT

Figure 4: AAC-HQ BVH construction achieves near linear scalingout to 16 cores and 35× speedup when executed using 80 threads on
40 cores with Hyper-Threading (40 HT). AAC-Fast achieves 27×
speedup in the 40 HT configuration.
likely to place large primitives higher in the tree. Thus large primitives, which are likely to be frequent occluders, are encounteredquickly during traversal, leading to early ray termination.
All three agglomerative techniques (not only the AAC configurations) generate a lower quality BVH than the top-down SAH
method for Buddha. The benefit of bottom-up methods is greatest
when variability in scene triangle size is large, a condition that is
not present in Buddha. We observe similar results (BVH quality of
agglomerative clustering equal to or slightly worse than SAH) for
scenes consisting of single high-resolution scanned models (e.g.,
the Stanford Dragon) or single hairball models. One technique for
improving top-down SAH build quality in scenes with large variation in triangle size is to pre-split large triangles [Ernst and Greiner
2007]. Agglomerative methods handle this case well without introducing many new triangles into the scene.

4.2

BVH Construction Performance

Table 2 reports BVH build times for each of the five methods. Timings include all aspects of BVH construction, including Morton

Sponza

Fairy

67 K
174 K
283 K
1.1 M
1.2 M
7.9 M

BuddhaSAH SAH-BIN Local-Ord
1 core exec. time (ms)Num TriSponzaFairy
Conference
BuddhaHalf-LifeSan Miguel

Conference

115
364
560
3,016
3,190
27,800

48
148
228
932
1,110
8,430

Half-Life

AAC-HQ
1 core (ms)32 cores (ms)

214
1,004
1,279
5,570
5,978
43,659

52
117
225
1,101
1,080
7,350

2
5
10
43
42
298

San Miguel

AAC-Fast
1 core (ms) 32 cores (ms)(24.0×)(24.5×)(23.6×)(25.8×)(25.7×)(24.6×)

20
44
70
397
359
2,140

1
2
4
16
15
99

(21.5×)(22.4×)(19.4×)(24.0×)(22.8×)(21.6×)Table 2: Single core BVH construction times for all build algorithms (+ 32-core timings for the AAC configurations). The AAC-Fast build isover three times faster than SAH-BIN while also producing a higher-quality BVH in all scenes except Buddha.

1 core (ms)Morton CodeAgglomeration
Total

351
7,000
7,350

(5%)
(95%)

Execution Time Breakdown: San Miguel
AAC-HQ
32 cores (ms) Speedup
1 core (ms)AAC-Fast
32 cores (ms)

21
277
298

21
78
99

(7%)
(93%)

16.8×
25.1×
24.6×

351
1,789
2,140

(16%)
(84%)

(21%)
(79%)

Speedup
16.8×
23.0×
21.6×

Table 3: Execution time breakdown for 1- and 32-core executions of AAC-HQ and AAC-Fast on San Miguel. The Morton code sort constitutes
only a small fraction of total execution time in AAC-HQ (<7%), but a notable fraction in AAC-Fast (up to 21%). The sort consumes a larger
fraction of total build time in the parallel executions since it parallelizes less efficiently than the agglomeration phase of the AAC algorithm.
code sort in the AAC configurations. We find that the performanceof a single-core AAC-HQ build is similar to that of SAH-BIN andapproximately five to six times faster than Local-Ord (while producing BVHs of similar quality). AAC-Fast (which still generates
higher quality trees than both SAH-BIN and SAH in all cases but
Buddha) performs even less work, resulting in a build that is up to
4× faster than SAH-BIN.
We also find that the AAC methods scale well to high core count(Figure 4). For the San Miguel scene AAC-HQ achieves nearlylinear speedup out to 16 cores, and a 34× speedup on 40 cores(using 80 threads with Hyper-Threading enabled, see “40 HT” data
point in Figure 4) . AAC-Fast also scales well out to 16 cores, butachieves a more modest 24× speedup on average on 40 cores.
Table 3 breaks down the execution time of 1- and 32-core configurations of AAC-HQ and AAC-Fast for San Miguel. The parallel
Morton code sort occupies only 5% of total execution in the single core AAC-HQ configuration. This percentage increases to 7%
in the 32-core configuration since the agglomeration phase of thealgorithm parallelizes more efficiently. (The Morton code sort isbandwidth bound.) The Morton code sort consumes a larger fraction of AAC-Fast execution time (16% and 21% for the 1- and 32core executions) since the agglomeration phase in AAC-Fast performs less work. This is a major reason why AAC-Fast achieves alower overall parallel speedup than AAC-HQ.

5Discussion

In this paper we demonstrated that bottom-up BVH construction based on agglomerative clustering can produce high-quality
BVHs with lower construction cost than top-down SAH-based approaches. Our algorithm features abundant coarse-grained paral-

lelism, making it easy to scale on many-core CPU architectures.
While we have evaluated its utility in the context of ray tracing, we
believe it will find use in other areas of computer graphics where
high-quality object hierarchies are desired.
We have not yet investigated the possibility of a “lazy” variant of an
AAC build. While lack of support for lazy builds is a known drawback of previous bottom-up approaches, it may be possible to leverage the top-down bisection process of the AAC build to achieve“lazy” behavior. Last, while our efforts in this paper focused on theimplementation of the technique on many-core CPUs, an obvious
area of future work is to consider if additional parallelism can be
exploited to enable efficient implementation on a GPU.

6

Acknowledgments

This work is partially supported by the National Science Foundation under grant CCF-1018188, by the Intel Labs Academic Research Office under the Parallel Algorithms for Non-Numeric Computing Program, and by the NVIDIA Corporation.

References
B ERN , M., E PPSTEIN , D., AND T ENG , S.-H. 1999. Parallel construction of quadtrees and quality triangulations. International
Journal of Computational Geometry and Applications 9, 6, 517–
532.
B ITTNER , J., H APALA , M., AND H AVRAN , V. 2013. Fast
insertion-based optimization of bounding volume hierarchies.
Computer Graphics Forum 32, 1, 85–100.

E RNST, M., AND G REINER , G. 2007. Early split clipping forbounding volume hierarchies. In Proceedings of the 2007 IEEE
Symposium on Interactive Ray Tracing, IEEE Computer Society,
RT ’07, 73–78.
G ARGANTINI , I. 1982. An effective way to represent quadtrees.
Communications of the ACM 25, 12, 905–910.
G OLDSMITH , J., AND S ALMON , J. 1987. Automatic creation of
object hierarchies for ray tracing. IEEE Computer Graphics andApplications 7, 5 (May), 14–20.
K ARRAS , T. 2012. Maximizing parallelism in the construction of
BVHs, octrees, and K-D trees. In Proceedings of the Conference on High Performance Graphics, Eurographics Association,
HPG’12, 33–37.
L AUTERBACH , C., G ARL , M., S ENGUPTA , S., L UEBKE , D., AND
M ANOCHA , D. 2009. Fast BVH construction on GPUs. In In
Proc. Eurographics ’09.
O LSON , C. F. 1995. Parallel algorithms for hierarchical clustering.
Parallel Computing 21, 1313–1325.

S HUN , J., B LELLOCH , G. E., F INEMAN , J. T., G IBBONS , P. B.,
K YROLA , A., S IMHADRI , H. V., AND TANGWONGSAN , K.
2012. Brief announcement: the Problem Based Benchmark
Suite. In Proc. ACM Symp. on Parallelism in Algorithms andArchitectures.
WALD , I., M ARK , W. R., G ÜNTHER , J., B OULOS , S., I ZE , T.,
H UNT, W., PARKER , S. G., AND S HIRLEY, P. 2007. State of
the art in ray tracing animated scenes. In Computer Graphics
Forum.
WALD , I. 2007. On fast construction of SAH-based bounding
volume hierarchies. In Interactive Ray Tracing, 2007. RT ’07.
IEEE Symposium on, 33–40.
WALD , I. 2012. Fast construction of SAH BVHs on the Intel
Many Integrated Core (MIC) architecture. IEEE Transactions
on Visualization and Computer Graphics 18, 1 (Jan.), 47–57.
WALTER , B., BALA , K., K ULKARNI , M., AND P INGALI , K.
2008. Fast agglomerative clustering for rendering. In Interactive Ray Tracing, 2008. RT 2008. IEEE Symposium on, 81–86.