src/SimpleKDTree.cpp

Go to the documentation of this file.

#include "SimpleKDTree.h"
#include "Node.h"
#include "Primitive.h"


SimpleKDTree::~SimpleKDTree()
{
}


void SimpleKDTree::buildTree(   const PrimitiveList &   list,
                                const Box &             bbox )
{
    KDTree::buildTree(list, bbox);

    // create the tree recursively
    buildTree(mRootNode, 0);

    LOG("Building kd-tree done");
}


void SimpleKDTree::setBestSplit(Node * node) const
{
    if (!node)
        return;

    // set split axis
    switch (node->splitAxis())
    {
        case X_AXIS:    node->setSplitAxis(Y_AXIS);
                        break;
        case Y_AXIS:    node->setSplitAxis(Z_AXIS);
                        break;
        case Z_AXIS:
        case NO_AXIS:   node->setSplitAxis(X_AXIS);
    }

    // to find a location for the split plane we use the method of arithmetic average value.
    // Hence we compute the average value of the prmitive's location
    // and set this as the split plane
    // This is a bad heuristic. Optimize it later if you like
    float avg = 0.0;
    for (unsigned int i=0; i < node->primitives_count(); i++)
    {
        avg += (node->primitive(i)->bounds().minVertex()[node->splitAxis()]
                + node->primitive(i)->bounds().maxVertex()[node->splitAxis()]) * 0.5;
    }

    node->setSplitPlane(avg / node->primitives_count());
}


void SimpleKDTree::buildTree(   Node *          node,
                                unsigned int    depth ) const
{
    assert(node);
    assert(!node->left());
    assert(!node->right());

    float f = 0;
    if (terminate(node, f, depth))
    {
        // make leaf node
        node->setSplitAxis(NO_AXIS);
        return;
    }

    // setup node's split axis and plane
    setBestSplit(node);

    // create both children
    Node * left     = new Node();
    Node * right    = new Node();
    node->setLeftRight(left, right);
    left->setSplitAxis(node->splitAxis());
    right->setSplitAxis(node->splitAxis());

    // check based on the split plane where to put the primitives
    for (unsigned int i=0; i < node->primitives_count(); i++)
    {
        const Box & box = node->primitive(i)->bounds();

        if (box.minVertex()[node->splitAxis()] >= node->splitPlane())
        {
            // if primitive lies completly on the right side
            right->add(node->primitive(i));
        }
        else if (box.maxVertex()[node->splitAxis()] <= node->splitPlane())
        {
            // if primitive lies completly on the left side
            left->add(node->primitive(i));
        }
        else
        {
            // for the rest of cases we just put the primitive in both subtrees
            left->add(node->primitive(i));
            right->add(node->primitive(i));
        }
    }

    // clear the node's primitive list, since now the childrens do contain them
    node->clear_primitives();

    // setup subtrees
    buildTree(left, depth + 1);
    buildTree(right, depth + 1);
}

---