src/KDTree.cpp

Go to the documentation of this file.

#include "KDTree.h"
#include "Node.h"
#include "Primitive.h"


KDTree::~KDTree()
{
    delete mRootNode;
}


bool KDTree::intersect(Ray & ray) const
{
    // intersect the ray with the bounding box of the kdtree
    std::pair<float, float> tmm = mBoundingBox.intersect(ray);

    // check if intersection is valid
    if (tmm.first >= INFINITY - EPSILON)
        return false;

//    LOG("bb.min: " << mBoundingBox.minVertex() << " , bb.max: " << mBoundingBox.maxVertex());
//    LOG(tmm.first << " " << tmm.second);

    // start traversal from the root node
    return intersect(mRootNode, ray, tmm.first, tmm.second);
}


bool KDTree::intersect( const Node *    node,
                        Ray &           ray,
                        float           min,
                        float           max ) const
{
    // don't do anything for null nodes
    if (!node)
        return false;

    // if leaf node, then look for intersection with primitives
    if (node->isLeafNode())
    {
        return node->leafIntersect(ray, min, max);
    }

    // get near and far child
    Node * near = NULL;
    Node * far  = NULL;
    node->nearFar(ray, near, far);

    // compute distance to the split plane
    float dist = node->distanceToSplitPlane(ray);

    // the whole interval is on near side
    if (dist <= 0 || dist > max)
    {
        return intersect(near, ray, min, max);
    }
    // whole interval is on far side
    else if (dist <= min)
    {
        return intersect(far, ray, min, max);
    }
    // the interval intersects the plane
    else
    {
        // first test near side
        if (intersect(near, ray, min, dist))
            return true;

        // then test the far side
        return intersect(far, ray, dist, max);
    }
}


void KDTree::buildTree( const PrimitiveList &   list,
                        const Box &             bbox )
{
    // delete root node
    delete mRootNode;

    LOG("Started building kd-tree");

    // create empty root node
    mRootNode = new Node(list);

    // reset the bounding box
    mBoundingBox    = bbox;
}


bool KDTree::terminate( const Node *    current,
                        float           /*dummy*/,
                        unsigned int    depth ) const
{
    return (current->primitives_count() <= mMinPrimitives || depth >= mMaxDepth);
}

---