Project

I have finished implementing the kd-tree. My issue was not actually with the traversal code but instead I was running some methods from an object before the object was allocated. Quite an oversight. Now thats out of the way, I have been able to test my kd-tree.

Here we have three different algorithms plotted. The naive algorithm performs horrendously. Next we have a kd-tree that is built without a heuristic. The plane position is always chosen by taking the midpoint according to some axis. Lastly, a kd-tree with the surface area heuristic is plotted. Both the kd-trees are logarithmic in time, which is great to see. As expected the running time is better for SAH.

In exchange for the better performance with SAH, we suffer horrendous time complexity for build time. It is exponential in time.

This results are encouraging and gives me plenty to discuss.

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.

Project

I started to implement my kd-tree. Right now it is pretty basic. To start, at the root node a bounding box is found for the first primitive and is then extended to every other primitive in the scene. This will be the bounding box for the root node. Next the inner nodes determined by an algorithm to find the optimal split position. As of now only the spatial-median according to a specified axis is chosen. I plan to implement the surface area heuristic algorithm to determine the optimal split position. Below is the pseudo-code for building the kdtree.

void buildKDTree(Node* node)
{
    if (stopcriterionmet()) return;
   

    double splitPosition = findOptimalSplitPosition(node->bbMin, node->bbMax); //splits in half at the moment
   
    Node *leftNode = new Node();
    Node *rightNode = new Node();
   
    int nSceneObjects = node->getNumberSceneObjects();
   
    for (int i = 0; i < nSceneObjects; i++)
    {   
        SceneObject *sceneObject = node->getSceneObject(i);
       
        if (node->intersectsLeftNode(sceneObject, splitPosition)) leftNode->addSceneObject(sceneObject);
        if (node->intersectsRightNode(sceneObject, splitPosition)) rightNode->addSceneObject(sceneObject);
    }
    buildKDTree(leftNode);
    buildKDTree(rightNode);
}


For next week, I need write the tree traversal code and the code for the surface area heuristic.

Project

I have now implemented triangle primitive. To test for intersections, I find the plane the triangle lies in and then see if the point the ray intersects with the plane is in triangle. It is not the fastest, but it will do for now. A faster method involves using barycentric coordinates.

I am currently contemplating implementing a class to read Wavefront 3D obj files but it might be too much work and I think I should focus more on the kd-tree part of this project.

Rewrote Ray Tracer

To begin, I decided to take my original ray tracer I wrote in csc305 and rewrite. I modularized the code by splitting it into classes. In total, I have the following classes: Scene, SceneObject, Camera, Lights, Color and Vector. Hopefully this will make implementing a kd-tree easier.

Below is an image produced by my ray tracer.



So far, I have only implemented spheres and planes. I wish to later include triangles.

Ray Tracing with Kd-trees

For my undergrad technical project I will be implementing a kd-tree data structure for ray tracers. It is currently the most popular way and effective way of accelerating ray tracing. It is a binary space partitioning tree for k-dimensional space. I will use it for organizing primitives in 3d space. If implemented correctly it should greatly reduce the number of intersection tests required by the ray tracer.




Each node in tree creates an axis-aligned splitting plane, which creates two subspaces which are the left and right children. This process is replicated for each child until we determine when it is appropriate to stop.