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.