FAST AND SIMPLE
AGGLOMERATIVE LBVH CONSTRUCTION
Ciprian Apetrei
Computer Graphics & Visual Computing (CGVC) 2014
Introduction
Hierarchies
What are they for?
Introduction
Hierarchies
What are they for?
Fast Construction or Better Quality?
Introduction
Hierarchies
What are they for?
Fast Construction or Better Quality?
When do we prefer speed?
View-frustum culling
Collision detection
Particle simulation
Voxel-based global illumination
Background
Previous GPU methods constructed the hierarchy in 4 steps:
Morton code calculation
Sorting the primitives
Hierarchy generation
Bottom-ul traversal to fit bounding-boxes
Binary radix tree
The binary representations of each key are in lexicographical order.
The keys are partitioned according to their first differing bit.
Because the keys are ordered, each node covers a linear range of keys.
A radix tree with n keys has n-1 internal
nodes.
Binary radix tree
The binary representations of each key are in lexicographical order.
The keys are partitioned according to their first differing bit.
Because the keys are ordered, each node covers a linear range of keys.
A radix tree with n keys has n-1 internal nodes.
The parent of a node splits the hierarchy immediately before the first key of its
right child and after the last key of its left child.
The binary representations of each key are in lexicographical order.
The keys are partitioned according to their first differing bit.
Because the keys are ordered, each node covers a linear range of keys.
A radix tree with n keys has n-1 internal nodes.
The parent of a node splits the hierarchy immediately before the first key of its
right child and after the last key of its left child.
Binary radix tree
0 0 1 0
0 1 0 1
1 0 0 0
1 1 0 0 0
1 0 0 0
0 1 1
1 1 0 1
1 1 1 1
0 1 2 3 4 5 6 7
Algorithm Overview
Define a numbering scheme for the nodes
Establish a connection with the keys
Gain some knowledge about the parent
Algorithm Overview
Define a numbering scheme for the nodes
Establish a connection with the keys
Gain some knowledge about the parent
Each internal node i splits the hierarchy between keys i and i + 1
i
i
i+1
Algorithm Overview
We can find the parent of a node by
knowing the range of keys covered by it.
The parent splits the hierarchy either
immediately before the first key or after the last key.
Last key of the left child First key of the right child i
i
i+1
Algorithm Overview
To determine the parent we have to
analyze the split point of the two nodes.
The one that splits the hierarchy
between two more similar subtrees is the direct parent.
i
The metric distance between two keys indicates the dissimilarity between the left child and the right child of node i.
i i+1
Algorithm Overview
Algorithm steps:
Start from each leaf node.
Algorithm Overview
Algorithm steps:
Start from each leaf node.
Choose the parent between the two internal nodes that split the hierarchy at the ends of the range of keys covered by the current
node.
Pass the range of keys to the parent.
Algorithm Overview
Algorithm steps:
Start from each leaf node.
Choose the parent between the two internal nodes that split the hierarchy at the ends of the range of keys covered by the current
node.
Pass the range of keys to the parent.
Calculate the bounding box of the node.
Advance towards the root.
Only process a node if it has both its children set.
Binary Radix Tree Construction
2
0 1 3 4 5 6
0 1 2 3 4 5 6 7
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0
0 1 0
0 1 0 1
1 0 0 0
1 1 0 0 0
1 0 0 0
0 1 1
1 1 0 1
1 1 1 1
0 1 2 3 4 5 6 7
Binary Radix Tree Construction
2 0
1
4
3
5
6
0 1 2 3
4
5 6
7
0 1 2 3 4 5 6 7
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7
0 0 1 0
0 1 0 1
1 0 0 0
1 1 0 0 0
1 0 0 0
0 1 1
1 1 0 1
1 1 1 1
0 1 2 3 4 5 6 7
Binary Radix Tree Construction
2 0
1 4
3
5
6
0 1 2 3
4
5 6
7 0 3
5
0 1 2 3 4 5 6 7
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7
0 0 1 0
0 1 0 1
1 0 0 0
1 1 0 0 0
1 0 0 0
0 1 1
1 1 0 1
1 1 1 1
0 1 2 3 4 5 6 7
Binary Radix Tree Construction
2 0
1 4
3
5
6
1 3 6
7
3 7
0
0 2 5
5
0 4
0 1 2 3 4 5 6 7
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7
0 0 1 0
0 1 0 1
1 0 0 0
1 1 0 0 0
1 0 0 0
0 1 1
1 1 0 1
1 1 1 1
0 1 2 3 4 5 6 7
Binary Radix Tree Construction
2 0
1 4
3
5
6
1 3 6
7
3 7
0 7
0 2 5
5
0 4
0 1 2 3 4 5 6 7
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7
0 0 1 0
0 1 0 1
1 0 0 0
1 1 0 0 0
1 0 0 0
0 1 1
1 1 0 1
1 1 1 1
0 1 2 3 4 5 6 7
Pseudocode
Pseudocode for choosing the parent:
1: def ChooseParent(Left, Right, currentNode)
2: If ( Left = 0 or ( Right != n and δ(Right) < δ(Left-1) ) ) 3: then
4: parent à Right
5: InternalNodesparent.childA à currentNode 6: RangeOfKeysparent.left à Left
7: else
8: parent à Left - 1
9: InternalNodesparent.childB à currentNode 10: RangeOfKeysparent.right à Right
Outline
General aspects about our algorithm:
Bottom-up construction
Finds the parent at each step
O(n) time complexity
Simple to implement
Can be used for constructing different types of trees
Allows an user-defined distance metric for choosing the parent.
Results
We used the bottom-up reduction algorithm presented by Karras[2012] for
implementation.
Compare against Karras binary radix tree construction and bounding-box calculation.
Evaluate performance on GeForce GT 745M
CUDA, 30-bit Morton Codes
Used Thrust library radix sort
Results
Scene Sort Previous Bottom-
up Radix tree
Squared Distance
Stanford Bunny (69K tris)
14.9
1.78 4.53 5.56 0.85 4.74 Armadillo
(345K tris)
32.1
5.01 10.0 12.03 2.4 11.9
Skeleton Hand (654k tris)
77.8
14.1 28.3 32.5 6.54 31.8 Stanford Dragon
(871K tris)
102 19.6 37.1 42.9 8.61 42.2
Happy Buddha (1087K tris)
125
23.2 46.8 53.4 10.7 52.7 Turbine Blade
(1765K tris)
210
37.3 73.9 85.9 17.3 85.3
Thank You
