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

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.