mmp/pbrt-v2 — pull request #35 by jerrycaonvidia (2014-07-21 13:30:51+00:00)
Title: Add O(N*log(N)) kd-tree construction algorithm

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
killeroo-simple.pbrt 85.6
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))".