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)

Project

Progress has been rough. The traversal code for the KD-tree was trickier than I expected. First of all there I had   to implement the algorithm from "An Efficient and Robust Ray–Box Intersection Algorithm" to quickly do box intersections. After that I realized that there are many different ways a ray can intersect with the nodes and each case must be hardcoded. Shown below is a helpful graphic I found. This helped me visualize some of the cases. They are all not present below.

After I thought I had every case covered, I attempted to render an  image using my kd-tree.

Clearly, not all cases work as intended. The final image is supposed to be three spheres. As of now, I am in process of debugging them.