Accelerated building and ray tracing of restricted BSP trees

We present algorithms for building and ray tracing restricted BSP trees. The build algorithm uses a dynamic programming technique to compute coefficients that allow efficient calculation of the surface area heuristic. This algorithm reduces asymptotic runtime, and has significant impact on tree building time. Additionally, we make several simple observations which lead to very fast ray-tree traversal of RBSPs. Our new traversal algorithm is based on state-of-the-art kd-tree traversal algorithms, and effectively increases the speed of ray tracing RBSPs by an order of magnitude. We show that RBSP trees are not only practical to build, but that RBSP trees are nearly as fast to ray trace as kd-trees, generally accepted as the fastest ray acceleration structure.