matt77hias
commented
8 years ago Building kd-trees with the naive O(N^2) build time version, the O(N log N) build time version [Wald and Havran] or the O(N (log N)^2) build time version [pbrt] must result in the same kd-trees if you (i) consider the same splitting planes at each level, (ii) use the same cost metric and (iii) use the same termination criteria. These versions only differ in construction time (which you do not mention), not in rendering time.
Since your rendering times differ, your comparison is not fair (or the variance on the timings is too high). Assuming your timings are correct and you use the same cost metric and termination criteria, you probably always consider all 3 primary axes at every split decision whereas pbrt is not guaranteed to consider all 3 axes.
Add O(N*log(N)) kd-tree construction algorithm in PBRT.
Here is the performance comparison of the new one and old one. (Since there is no construction time available in the console output, only rendering performance is compared here.) First number is this KD-Tree implementation, second is the old one. anim-killeroos-moving.pbrt 50.7 58.0 anim-moving-reflection.pbrt 9.2 9.6 bunny.pbrt 1.8 1.9 metal.pbrt 7.1+35.2 8.0+40.8 prt-teapot.pbrt 1.1 1.2 ss-envmap.pbrt 1.2+0.7+60.1 1.0+0.7+69.8
The algorithm is mentioned in the paper "On building fast kd-trees for Ray Tracing, and on doing that in O(N*log(N))".