doi: 10.7873/DATE.2015.0176

FastTree: A Hardware KD-Tree Construction Acceleration Engine for Real-Time Ray Tracing

Xingyu Liua, Yangdong Dengb, Yufei Nic and Zonghui Lid

Institute of Microelectronics, Tsinghua University, China.


The ray tracing algorithm is well-known for its ability to generate photo-realistic rendering effects. Recent years have witnessed a renewed momentum in pushing it to real-time for better user experience. Today the construction of acceleration structures, e.g., kd-tree, has become the bottleneck of ray tracing. A dedicated hardware architecture, FastTree, was proposed for kd-tree construction by adopting a fully parallel construction algorithm. FastTree was validated by an FPGA prototype and evaluated as an ASIC implementation. Experiment result shows FastTree outperforms existing hardware construction engines by a factor of nearly 4X at a similar area and power budget.

Keywords: Ray tracing, Kd-tree, Kd-tree construction, Hardware acceleration, Real-time ray tracing.

Full Text (PDF)