B-KD Trees for Hardware Accelerated Ray Tracing of Dynamic Scenes

Sven Woop, Gerd Marmitt, and Philipp Slusallek
Graphics Hardware 2006, Vienna, September 3rd - 4th, 2006
[bib] [pdf]


This paper introduces a new spatial index structure, called Bounded KD tree (B-KD tree), for realtime ray tracing
of dynamic scenes. By presenting hardware units of all time critical B-KD tree algorithms in the context of a custom
realtime ray tracing chip we show that this spatial index structure is well suited for hardware implementation.
B-KD trees are a hybrid spatial index structure that combine the advantages of KD trees and Bounding Volume
Hierarchies into a single, simple to handle spatial index structure. Similar to KD trees, B-KD trees are binary
trees where each node considers only a single spatial dimension. However, instead of a single splitting plane that
divides space into two disjoint sub-spaces, each node in B-KD trees contains two pairs of axis aligned planes
that bound the geometry of its two child nodes. As a bounding volume approach B-KD trees allow for simple and
efficient updates when changing geometry while maintaining the fast traversal operations and simple hardware
implementation known from KD trees. This enables the support for dynamic scenes with constant mesh topology
and coherent dynamic changes, like typical skinned meshes.
Our hardware architecture contains several fixed-function units that completely handle skinning, updating, and
ray tracing of dynamic scenes using B-KD trees. An FPGA prototype of this architecture already delivers realtime
performance of up to 35 frames per second even when clocked at only 66 MHz.