Hardware-Accelerated Dual-Split Trees

Proceedings of ACM on Computer Graphics and Interactive Techniques (Proceedings of HPG 2020)

Daqi LinElena VasiouCem YukselDaniel KoptaErik Brunvand
University of UtahUniversity of UtahUniversity of UtahUniversity of UtahUniversity of Utah
[Paper (Preprint)]
[Presentation Notes]


Bounding volume hierarchies (BVH) are the most widely used acceleration structures for ray tracing due to their high construction and traversal performance. However, the bounding planes shared between parent and children bounding boxes is an inherent storage redundancy that limits further improvement in performance due to the memory cost of reading these redundant planes. Dual-split trees can create identical space partitioning as BVHs, but in a compact form using less memory by eliminating the redundancies of the BVH structure representation. This reduction in memory storage and data movement translates to faster ray traversal and better energy efficiency. Yet, the performance benefits of dual-split trees are undermined by the processing required to extract the necessary information from their compact representation. This involves bit manipulations and branching instructions which are inefficient in software. We introduce hardware acceleration for dual-split trees and show that the performance advantages over BVHs are emphasized in a hardware ray tracing context that can take advantage of such acceleration. We provide details on how the operations needed for decoding dual-split tree nodes can be implemented in hardware and present experiments in a number of scenes with different sizes using path tracing. In our experiments, we have observed up to 31% reduction in render time and 38% energy saving using dual-split trees as compared to binary BVHs representing identical space partitioning.


An overview of the hardware dual-split intersection pipeline. The FPADD units are used for subtractions. Arrows represent 32-bit data type (int, float) by default. Vector data (e.g. float3) are marked with thickened lines. Data under 2 bits are represented by dashed lines. Colored round boxes represent input registers. Uncolored round boxes represent outputs. Squared boxes stand for functional units. Unit areas are not to scale.


Path tracing performance: (top) render times and (bottom) energy use.
(+ BVH with extended parallel ray-box pipelines ∗ Dual-split tree with software decoding)

Paper Talk


   author       = {Daqi Lin and Elena Vasiou and Cem Yuksel and Daniel Kopta and Erik Brunvand},
   title        = {Hardware-Accelerated Dual-Split Trees},
   journal      = {Proc. ACM Comput. Graph. Interact. Tech. (Proceedings of HPG 2020)},
   year         = {2020},
   volume       = {3},
   number       = {2},
   pages        = {20:1--20:21},
   articleno    = {20},
   numpages     = {18},
   url          = {http://doi.acm.org/10.1145/3406185},
   doi          = {10.1145/3406185},
   publisher    = {ACM Press},
   address      = {New York, NY, USA},

Dual-Split Trees