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.