Rendering Competition 07/08

SAH KDTree

As second accelleration structure we implemented a SAHKDTree that uses a surface area heuristic to find the best splitting plane for optimal traversal costs. For building our tree we implemented the widely used algorithm that is described in Wald's paper "On building fast kdtrees for ray tracing, and on doing that in O(n log n)". The fast building time is accomplished by generating planar events for split candidates and presorting them in a way that we do not have to sort them again during the tree construction and thus avoiding O(n log n) cost for sorting them which would have caused O(n (log n)²) building time.