On building fast KD-trees for ray tracing, and on doing that in O(N log N)

Though a large variety of efficiency structures for ray tracing exist, kd-trees today seem to slowly become the method of choice. In particular, kd-trees built with cost estimation functions such as a surface area heuristic (SAH) seem to be important for reaching high performance. Unfortunately, most algorithms for building such trees have a time complexity of O(N log2 N), or even O(N2). In this paper, we analyze the state of the art in building good kdtrees for ray tracing, and eventually propose an algorithmthat builds SAH kd-trees in O(N logN), the theoretical lower bound.