Project

I decided to ignore the KD traversal code for now and instead work on the surface area heuristic for building the tree. I implemented the heuristic as described in:

Heuristic Ray Shooting Algorithms", Vlastimil Havran (http://www.cgg.cvut.cz/~havran/phdthesis.html)

It works by computing the "cost" of various candidate axis positions and then picking the position with the least cost. The cost model is based on the fact that given that a ray R intersects a space V, then the probability that it also intersects Vsub, a subspace of V, is given by the surface are of V divided by the surface area of Vsub.

After implementing this I wrote a function to print out the tree for debugging purposes. I used a test case with 12 fairly spaced spheres. The output was satisfactory.

Debug output of KDTree(12 spheres):

       |       |       |Empty
       |       |(6) (12)
       |       |       |       |Empty
       |       |       |(6) (12)
       |       |       |       |(6) (12)
       |(6) (11) (12)
       |       |(11)
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12)
       |       |       |       |(8)
       |       |       |(8) (9)
       |       |       |       |(9)
       |       |(2) (3) (5) (8) (9)
       |       |       |       |(5)
       |       |       |(2) (3) (5)
       |       |       |       |(2) (3)
       |(1) (2) (3) (4) (5) (7) (8) (9) (10)
       |       |       |Empty
       |       |(1) (4) (7) (10)
       |       |       |       |(4) (7) (10)
       |       |       |(1) (4) (7) (10)
       |       |       |       |(1)