src/SAHKDTree.h

Go to the documentation of this file.

#include <cassert>

#include "KDTree.h"
#include "Event.h"
#include "SplitPlane.h"


class Node;


class SAHKDTree : public KDTree
{
public:
    SAHKDTree(  float   lambda      = 0.8f,
                float   kTraversal  = 5.0f,
                float   kIntersect  = 1.0f )
        : KDTree(4, 64),
            mLambda(lambda),
            mKTraversal(kTraversal),
            mKIntersect(kIntersect)
    {
    }

    virtual ~SAHKDTree();

    virtual void buildTree( const PrimitiveList &   list,
                            const Box &             bbox );

private:
    typedef std::vector<Event> EventList;


    const float         mLambda;

    const float         mKTraversal;

    const float         mKIntersect;


    void buildTree( Node *          node,
                    const Box &     bbox,
                    EventList &     events,
                    unsigned int    depth ) const;

    virtual bool terminate( const Node *    current,
                            float           minCost,
                            unsigned int    depth ) const;

    float cost( float           probability_left,
                float           probability_right,
                unsigned int    number_left,
                unsigned int    number_right ) const
    {
        float result = mKTraversal + mKIntersect*(probability_left*number_left + probability_right*number_right);
        if (number_left == 0 || number_right == 0)
            return mLambda * result;
        else
            return result;
    }

    float SAH(  Side &              side,   // out param
                const Box &         bbox,
                const SplitPlane &  plane,
                unsigned int        number_left,
                unsigned int        number_right,
                unsigned int        number_middle ) const;

    SplitPlane findBestPlane(   float &             minCost,    // out param
                                const Node *        node,
                                const Box &         bbox,
                                const EventList &   events ) const;

    std::pair<Box, Box> classifyAndSplice(  EventList &         eLeft,  // out param
                                            EventList &         eRight, // out param
                                            Node *              node,
                                            const Box &         bbox,
                                            const EventList &   events,
                                            const SplitPlane &  plane ) const;

    void generateEvents(    EventList &     events,     // out param
                            Primitive *     primitive,
                            const Box &     bbox ) const;
};

---