Improving Kd-tree quality at a reasonable construction cost
Alexei Soupikov, Maxim Shevtsov, Alexander Kapustin · 2008
We consider construction of high-quality kd-tree and investigate the effect of techniques based on perfect splits. The main idea of perfect splits is clipping of objects straddling the splitting planes during the construction. This effectively results in reducing the number of references in leaves while also generating new potential split positions. We derive an efficient algorithm for triangle clipping/assignment and show how to avoid problems for parallel construction using clipping. Investigating the influence of using clipping results at different kd-tree construction stages, we finally come up with on-the-fly pruning algorithm that improves rendering performance by up to 25% decreasing construction time as well.