source: GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp @ 1308

#include <stack>
#include <time.h>
#include <iomanip>

#include "BvHierarchy.h"
#include "ViewCell.h"
#include "Plane3.h"
#include "Mesh.h"
#include "common.h"
#include "Environment.h"
#include "Polygon3.h"
#include "Ray.h"
#include "AxisAlignedBox3.h"
#include "Exporter.h"
#include "Plane3.h"
#include "ViewCellsManager.h"
#include "Beam.h"
#include "VspTree.h"


namespace GtpVisibilityPreprocessor {


#define USE_FIXEDPOINT_T 0

static float debugVol = 0;

int BvhNode::sMailId = 10000;//2147483647;
int BvhNode::sReservedMailboxes = 1;

BvHierarchy *BvHierarchy::BvhSubdivisionCandidate::sBvHierarchy = NULL;


inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
{
        return obj1->mId < obj2->mId;
}


/***************************************************************/
/*              class BvhNode implementation                   */
/***************************************************************/

BvhNode::BvhNode(): mParent(NULL), mMailbox(0)
{
}

BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
mParent(NULL), mBoundingBox(bbox), mMailbox(0)
{
}


BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
mBoundingBox(bbox), mParent(parent), mMailbox(0)
{
}


bool BvhNode::IsRoot() const
{
        return mParent == NULL;
}


BvhInterior *BvhNode::GetParent()
{
        return mParent;
}


void BvhNode::SetParent(BvhInterior *parent)
{
        mParent = parent;
}



/******************************************************************/
/*              class BvhInterior implementation                  */
/******************************************************************/


BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox):
BvhNode(bbox), mSubdivisionCandidate(NULL)
{
}


BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
BvhNode(bbox, parent)
{
}


BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, 
                                 BvhInterior *parent, 
                                 const int numObjects):
BvhNode(bbox, parent)
{
        mObjects.reserve(numObjects);
}


bool BvhLeaf::IsLeaf() const 
{ 
        return true; 
}


BvhLeaf::~BvhLeaf() 
{ 
}


/******************************************************************/
/*              class BvhInterior implementation                  */
/******************************************************************/


BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
BvhNode(bbox), mFront(NULL), mBack(NULL)
{
}


BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
BvhNode(bbox, parent), mFront(NULL), mBack(NULL)
{
}


void BvhInterior::ReplaceChildLink(BvhNode *oldChild, BvhNode *newChild) 
{
        if (mBack == oldChild)
                mBack = newChild;
        else
                mFront = newChild;
}


bool BvhInterior::IsLeaf() const 
{ 
        return false; 
}


BvhInterior::~BvhInterior() 
{ 
        DEL_PTR(mFront); 
        DEL_PTR(mBack);
}


void BvhInterior::SetupChildLinks(BvhNode *front, BvhNode *back) 
{
    mBack = back;
    mFront = front;
}



/*******************************************************************/
/*                  class BvHierarchy implementation               */
/*******************************************************************/


BvHierarchy::BvHierarchy():
mRoot(NULL),
mTimeStamp(1)
{
        ReadEnvironment();
        mSubdivisionCandidates = new vector<SortableEntry>;
}


BvHierarchy::~BvHierarchy()
{
        // delete kd intersectables
        BvhIntersectableMap::iterator it, it_end = mBvhIntersectables.end();

        for (it = mBvhIntersectables.begin(); it != mBvhIntersectables.end(); ++ it)
        {
                DEL_PTR((*it).second);
        }

        DEL_PTR(mSubdivisionCandidates);

        mSubdivisionStats.close();
}


void BvHierarchy::ReadEnvironment()
{
        bool randomize = false;
        Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
        if (randomize)
                Randomize(); // initialise random generator for heuristics

        //-- termination criteria for autopartition
        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxDepth", mTermMaxDepth);
        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxLeaves", mTermMaxLeaves);
        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minObjects", mTermMinObjects);
        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minProbability", mTermMinProbability);
        
        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.missTolerance", mTermMissTolerance);
        
        //-- max cost ratio for early tree termination
        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.maxCostRatio", mTermMaxCostRatio);

        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minGlobalCostRatio",
                mTermMinGlobalCostRatio);
        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.globalCostMissTolerance", 
                mTermGlobalCostMissTolerance);

        //-- factors for bsp tree split plane heuristics

        // if only the driving axis is used for axis aligned split
        Environment::GetSingleton()->GetBoolValue("BvHierarchy.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
        Environment::GetSingleton()->GetFloatValue("BvHierarchy.maxStaticMemory", mMaxMemory);
        Environment::GetSingleton()->GetBoolValue("BvHierarchy.useCostHeuristics", mUseCostHeuristics);

        char subdivisionStatsLog[100];
        Environment::GetSingleton()->GetStringValue("BvHierarchy.subdivisionStats", subdivisionStatsLog);
        mSubdivisionStats.open(subdivisionStatsLog);

        Environment::GetSingleton()->GetFloatValue(
                "BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
        

        //-- debug output

        Debug << "******* Bvh hierarchy options ******** " << endl;
    Debug << "max depth: " << mTermMaxDepth << endl;
        Debug << "min probabiliy: " << mTermMinProbability<< endl;
        Debug << "min objects: " << mTermMinObjects << endl;
        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
        Debug << "miss tolerance: " << mTermMissTolerance << endl;
        Debug << "max leaves: " << mTermMaxLeaves << endl;
        Debug << "randomize: " << randomize << endl;
        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
        Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
        Debug << "max memory: " << mMaxMemory << endl;
        Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
        Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
        
        Debug << "split borders: " << mSplitBorder << endl;
        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
        Debug << endl;
}


void AssociateObjectsWithLeaf(BvhLeaf *leaf)
{
        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
        {
                (*oit)->mBvhLeaf = leaf;
        }
}


BvhInterior *BvHierarchy::SubdivideNode(const ObjectContainer &frontObjects,
                                                                                const ObjectContainer &backObjects,
                                                                                const BvhTraversalData &tData,
                                                                                BvhTraversalData &frontData,
                                                                                BvhTraversalData &backData)
{
        BvhLeaf *leaf = tData.mNode;
        
        // two new leaves
    mBvhStats.nodes += 2;

        // add the new nodes to the tree
        BvhInterior *node = new BvhInterior(tData.mBoundingBox, leaf->GetParent());
        

        //-- the front and back traversal data is filled with the new values

        frontData.mDepth = backData.mDepth = tData.mDepth + 1;

        frontData.mBoundingBox = ComputeBoundingBox(frontObjects, &tData.mBoundingBox);
        backData.mBoundingBox = ComputeBoundingBox(backObjects, &tData.mBoundingBox);
        
        /////////////
        //-- create front and back leaf

        BvhLeaf *back = 
                new BvhLeaf(backData.mBoundingBox, node, (int)backObjects.size());
        BvhLeaf *front = 
                new BvhLeaf(frontData.mBoundingBox, node, (int)frontObjects.size());

        BvhInterior *parent = leaf->GetParent();


        // replace a link from node's parent
        if (parent)
        {
                parent->ReplaceChildLink(leaf, node);
                node->SetParent(parent);
        }
        else // new root
        {
                mRoot = node;
        }

        // and setup child links
        node->SetupChildLinks(front, back);

        ++ mBvhStats.splits;


        ////////////////////////////////////

        frontData.mNode = front;
        backData.mNode = back;

        back->mObjects = backObjects;
        front->mObjects = frontObjects;

        AssociateObjectsWithLeaf(back);
        AssociateObjectsWithLeaf(front);
   
        // compute probability, i.e., volume of seen view cells
        frontData.mProbability = EvalViewCellsVolume(frontObjects);
        backData.mProbability = EvalViewCellsVolume(backObjects);

        return node;
}


BvhNode *BvHierarchy::Subdivide(SplitQueue &tQueue,
                                                                SubdivisionCandidate *splitCandidate,
                                                                const bool globalCriteriaMet)
{
        BvhSubdivisionCandidate *sc = 
                dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
        BvhTraversalData &tData = sc->mParentData;

        BvhNode *newNode = tData.mNode;

        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
        {       
                //-- continue subdivision

                BvhTraversalData tFrontData;
                BvhTraversalData tBackData;
                        
                // create new interior node and two leaf node
                newNode = SubdivideNode(sc->mFrontObjects,
                                                                sc->mBackObjects,
                                                                tData, 
                                                                tFrontData, 
                                                                tBackData);
        
                const int maxCostMisses = sc->mMaxCostMisses;

        // how often was max cost ratio missed in this branch?
                tFrontData.mMaxCostMisses = maxCostMisses;
                tBackData.mMaxCostMisses = maxCostMisses;
                
                // decrease the weighted average cost of the subdivisoin
                mTotalCost -= sc->GetRenderCostDecrease();

                // subdivision statistics
                if (1) PrintSubdivisionStats(*sc);

                //-- push the new split candidates on the queue
                
                BvhSubdivisionCandidate *frontCandidate = 
                        new BvhSubdivisionCandidate(tFrontData);
                BvhSubdivisionCandidate *backCandidate = 
                        new BvhSubdivisionCandidate(tBackData);

                EvalSubdivisionCandidate(*frontCandidate);
                EvalSubdivisionCandidate(*backCandidate);
        
                // cross reference
                tFrontData.mNode->SetSubdivisionCandidate(frontCandidate); 
                tBackData.mNode->SetSubdivisionCandidate(backCandidate);

                Debug << "leaf: " << tFrontData.mNode << " setting f candidate: " << tFrontData.mNode->GetSubdivisionCandidate() << " type: " << tFrontData.mNode->GetSubdivisionCandidate()->Type() << endl;
                Debug << "leaf: " << tBackData.mNode << " setting b candidate: " << tBackData.mNode->GetSubdivisionCandidate() << " type: " << tBackData.mNode->GetSubdivisionCandidate()->Type() << endl;
                
                tQueue.Push(frontCandidate);
                tQueue.Push(backCandidate);

                // delete old leaf node
                //DEL_PTR(tData.mNode);
        }

        //-- terminate traversal

    if (newNode->IsLeaf())
        {
                //-- store additional info
                
                EvaluateLeafStats(tData);
        
                const bool mStoreRays = true;
                if (mStoreRays)
                {
                        BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(newNode);
                        CollectRays(leaf->mObjects, leaf->mVssRays);
                }
                
                // detach subdivision candidate: this leaf is no candidate for
                // splitting anymore
                tData.mNode->SetSubdivisionCandidate(NULL); 
                // detach node so it won't get deleted
                tData.mNode = NULL;
        }
        
        return newNode;
}


void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate)
{
        // compute best object partition
        const float ratio =     SelectObjectPartition(
                                                        splitCandidate.mParentData, 
                                                        splitCandidate.mFrontObjects, 
                                                        splitCandidate.mBackObjects);
        
        BvhLeaf *leaf = splitCandidate.mParentData.mNode;

        // cost ratio violated?
        const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;

        splitCandidate.mMaxCostMisses = maxCostRatioViolated ? 
                splitCandidate.mParentData.mMaxCostMisses + 1 :
                splitCandidate.mParentData.mMaxCostMisses;

        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
        const float oldProp = EvalViewCellsVolume(leaf->mObjects);
        //const float oldProp2 = splitCandidate.mParentData.mProbability; Debug << "here8 " << (oldProp - oldProp2) / viewSpaceVol << "  " << oldProp  / viewSpaceVol << " " << oldProp2  / viewSpaceVol << endl;

        const float oldRenderCost = oldProp * (float)leaf->mObjects.size() / viewSpaceVol;

        // compute global decrease in render cost
        float newRenderCost = EvalRenderCost(splitCandidate.mParentData,
                                                                             splitCandidate.mFrontObjects,
                                                                                 splitCandidate.mBackObjects);

        newRenderCost /=  viewSpaceVol;
        const float renderCostDecr = oldRenderCost - newRenderCost;

        Debug << "\nbvh render cost decr: " << renderCostDecr << endl;
        splitCandidate.SetRenderCostDecrease(renderCostDecr);

#if 1
        const float priority = (float)-splitCandidate.mParentData.mDepth;
#else   
        // take render cost of node into account 
        // otherwise danger of being stuck in a local minimum!!
        const float factor = mRenderCostDecreaseWeight;
        const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
#endif

        // compute global decrease in render cost
        splitCandidate.SetPriority(priority);
}


inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &data) const
{
        // matt: TODO
        return ( 0
                //|| ((int)data.mNode->mObjects.size() < mTermMinObjects)
                //|| (data.mProbability <= mTermMinProbability)
                //|| (data.mDepth >= mTermMaxDepth)
                 );
}


inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
{
        // matt: TODO
        return (0
                || (mBvhStats.Leaves() >= mTermMaxLeaves)
                //|| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
                //|| mOutOfMemory 
                );
}


void BvHierarchy::EvaluateLeafStats(const BvhTraversalData &data)
{
        // the node became a leaf -> evaluate stats for leafs
        BvhLeaf *leaf = data.mNode;
        
        ++ mCreatedLeaves;

        if (data.mDepth >= mTermMaxDepth)
        {
        ++ mBvhStats.maxDepthNodes;
                //Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
        }

        if (data.mDepth < mTermMaxDepth)
        {
        ++ mBvhStats.minDepthNodes;
        }

        if (data.mProbability <= mTermMinProbability)
                ++ mBvhStats.minProbabilityNodes;
        
        // accumulate depth to compute average depth
        mBvhStats.accumDepth += data.mDepth;
 
        if ((int)(leaf->mObjects.size()) < mTermMinObjects)
             ++ mBvhStats.minObjectsNodes;
 
        if ((int)(leaf->mObjects.size()) > mBvhStats.maxObjectRefs)
                mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
}


#if 0
float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
                                                                                        const int axis,
                                                                                        ObjectContainer &objectsFront,
                                                                                        ObjectContainer &objectsBack)
{
        const float maxBox = tData.mBoundingBox.Max(axis);
        const float minBox = tData.mBoundingBox.Min(axis);

        float midPoint = (maxBox + minBox) * 0.5f;

        ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
        
        for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
        {
                Intersectable *obj = *oit;
                const AxisAlignedBox3 box = obj->GetBox();

                const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5f;

                // object mailed => belongs to back objects
                if (objMid < midPoint) 
                        objectsBack.push_back(obj);
                else
                        objectsFront.push_back(obj);
        }

        const float oldRenderCost = tData.mProbability * (float)tData.mNode->mObjects.size();
        const float newRenderCost = 
                EvalRenderCost(tData, objectsFront, objectsBack);

        const float ratio = newRenderCost / oldRenderCost;
        return ratio;
}

#else

float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
                                                                                        const int axis,
                                                                                        ObjectContainer &objectsFront,
                                                                                        ObjectContainer &objectsBack)
{
        SortSubdivisionCandidates(tData, axis);
        
        vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();

        int i = 0;
        const int border = (int)tData.mNode->mObjects.size() / 2;

    for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ i)
        {
                Intersectable *obj = (*cit).mObject;

                // object mailed => belongs to back objects
                if (i < border) 
                        objectsBack.push_back(obj);
                else
                        objectsFront.push_back(obj);
        }

        const float oldProp = EvalViewCellsVolume(tData.mNode->mObjects);
        //const float oldProp2 = tData.mProbability; Debug << "here65 " << oldProp - oldProp2 << endl;

        const float oldRenderCost = oldProp * (float)tData.mNode->mObjects.size();
        const float newRenderCost = EvalRenderCost(tData, objectsFront, objectsBack);

        const float ratio = newRenderCost / oldRenderCost;
        return ratio;
}
#endif


float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
                                                                                   const int axis,
                                                                                   ObjectContainer &objectsFront,
                                                                                   ObjectContainer &objectsBack)
{
        // prepare the heuristics by setting mailboxes and counters.
        const float totalVol = PrepareHeuristics(tData, axis);

        // go through the lists, count the number of objects left and right
        // and evaluate the cost funcion

        // local helper variables
        float volLeft = 0;
        float volRight = totalVol;

        int nObjectsLeft = 0;

        const int nTotalObjects = (int)tData.mNode->mObjects.size();
        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();

        vector<SortableEntry>::const_iterator currentPos =
                mSubdivisionCandidates->begin();

        /////////////////////////////////
        // the parameters for the current optimum

        float volBack = volLeft;
        float volFront = volRight;

        float newRenderCost = nTotalObjects * totalVol;


        /////////////////////////////
        // the sweep heuristics
        
        //-- traverse through events and find best split plane

        vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();

        for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
        {
                Intersectable *object = (*cit).mObject;
                
                // evaluate change in l and r volume
                // voll = view cells that see only left node (i.e., left pvs)
                // volr = view cells that see only right node (i.e., right pvs)
                EvalHeuristicsContribution(object, volLeft, volRight);

                ++ nObjectsLeft;
                
                const int nObjectsRight = nTotalObjects - nObjectsLeft;

                // the heuristics
            const float sum = volLeft * (float)nObjectsLeft + 
                                                  volRight * (float)nObjectsRight;

                if (sum < newRenderCost)
                {
                        newRenderCost = sum;

                        volBack = volLeft;
                        volFront = volRight;

                        // objects belongs to left side now
                        for (; currentPos != (cit + 1); ++ currentPos);
                }
        }

        //-- assign object to front and back volume

        // belongs to back bv
        for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
                objectsBack.push_back((*cit).mObject);
        
        // belongs to front bv
        for (cit = currentPos; cit != cit_end; ++ cit)
                objectsFront.push_back((*cit).mObject);

        tData.mNode->mObjects.end();

        const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
        // the relative cost ratio
        const float ratio = newRenderCost / oldRenderCost;

        Debug << "\n§§§§ eval local cost §§§§" << endl
                  << "back pvs: " << (int)objectsBack.size() << " front pvs: " << (int)objectsFront.size() << " total pvs: " << nTotalObjects << endl 
                  << "back p: " << volBack / viewSpaceVol << " front p " << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
                  << "render cost decrease: " << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;

        return ratio;
}


void BvHierarchy::SortSubdivisionCandidates(const BvhTraversalData &tData,
                                                                                        const int axis)                                                                                 
{
        mSubdivisionCandidates->clear();

        //RayInfoContainer *rays = tData.mRays;
        BvhLeaf *leaf = tData.mNode;

        // compute requested size
        const int requestedSize = (int)leaf->mObjects.size() * 2;
        
        // creates a sorted split candidates array
        if (mSubdivisionCandidates->capacity() > 500000 &&
                requestedSize < (int)(mSubdivisionCandidates->capacity() / 10) )
        {
        delete mSubdivisionCandidates;
                mSubdivisionCandidates = new vector<SortableEntry>;
        }

        mSubdivisionCandidates->reserve(requestedSize);

        //-- insert object queries
        //-- These queries can induce a change in pvs size.
        //-- Note that they cannot induce a change in view cell volume, as
        //-- there is no ray associated with these events!!

        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();

        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
        {
                Intersectable *obj = *oit;
                
                Intersectable *object = *oit;
                const AxisAlignedBox3 &box = object->GetBox();
                const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;

                mSubdivisionCandidates->push_back(SortableEntry(object, midPt));
        }

        stable_sort(mSubdivisionCandidates->begin(), mSubdivisionCandidates->end());
}


const BvhStatistics &BvHierarchy::GetStatistics() const
{
        return mBvhStats;
}


float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData, const int axis)
{       
        //-- sort so we can use a sweep from right to left
        SortSubdivisionCandidates(tData, axis);

        float vol = 0;
        BvhLeaf *leaf = tData.mNode;

        // collect and mark the view cells as belonging to front pvs
        ViewCellContainer viewCells;
        CollectViewCells(tData.mNode->mObjects, viewCells, true);

    ViewCellContainer::const_iterator vit, vit_end = viewCells.end();

        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
        {
                vol += (*vit)->GetVolume();
        }

        // mail view cells on the left side
        ViewCell::NewMail();
        // mail the objects on the left side
        Intersectable::NewMail();

        return vol;
}
///////////////////////////////////////////////////////////


void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
                                                                                         float &volLeft, 
                                                                                         float &volRight)
{
        // collect all view cells associated with this objects 
        // (also multiple times, if they are pierced by several rays)

        ViewCellContainer viewCells;
        
        const bool useMailboxing = false;
        CollectViewCells(obj, viewCells, useMailboxing);


        /// classify view cells and compute volume contri accordingly
        /// possible view cell classifications:
        /// view cell mailed => view cell can be seen from left child node
        /// view cell counter > 0 view cell can be seen from right child node
        /// combined: view cell volume belongs to both nodes
        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
        
        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
        {
                // view cells can also be seen from left child node
                ViewCell *viewCell = *vit;

                const float vol = viewCell->GetVolume();

                if (!viewCell->Mailed())
                {
                        viewCell->Mail();

                        // we now see view cell from both nodes 
                        // => add volume to left node
                        volLeft += vol;
                }

                // last reference into the right node
                if (-- viewCell->mCounter == 0)
                {
                        // view cell was previously seen from both nodes  =>
                        // remove volume from right node
                        volRight -= vol;
                }
        }
}


void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
{
        mViewCellsManager = vcm;
}


AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
{
        return mBoundingBox;
}


float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
                                                                                 ObjectContainer &frontObjects,
                                                                                 ObjectContainer &backObjects)
{
        ObjectContainer nFrontObjects[3];
        ObjectContainer nBackObjects[3];

        float nCostRatio[3];

        // create bounding box of node geometry
        AxisAlignedBox3 box = tData.mBoundingBox;
                
        int sAxis = 0;
        int bestAxis = -1;

        if (mOnlyDrivingAxis)
        {
                sAxis = box.Size().DrivingAxis();
        }
        
        // -- evaluate split cost for all three axis
        
        for (int axis = 0; axis < 3; ++ axis)
        {
                if (!mOnlyDrivingAxis || (axis == sAxis))
                {
                        if (mUseCostHeuristics)
                        {
                                //-- partition objects using heuristics
                                nCostRatio[axis] =
                                        EvalLocalCostHeuristics(
                                                                                        tData,
                                                                                        axis,
                                                                                        nFrontObjects[axis],
                                                                                        nBackObjects[axis]);
                        }
                        else
                        {
                                nCostRatio[axis] =
                                        EvalLocalObjectPartition(
                                                                                         tData,
                                                                                         axis,
                                                                                         nFrontObjects[axis],
                                                                                         nBackObjects[axis]);
                        }

                        if (bestAxis == -1)
                        {
                                bestAxis = axis;
                        }
                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
                        {
                                bestAxis = axis;
                        } 
                }
        }

        //-- assign values

        frontObjects = nFrontObjects[bestAxis];
        backObjects = nBackObjects[bestAxis];

        //Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
        return nCostRatio[bestAxis];
}


void BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays)
{

        VssRayContainer::const_iterator rit, rit_end = rays.end();

    for (rit = rays.begin(); rit != rays.end(); ++ rit)
        {
                VssRay *ray = (*rit);

                if (ray->mTerminationObject)
                {
                        ray->mTerminationObject->mVssRays.push_back(ray);
                }

                if (0 && ray->mOriginObject)
                {
                        ray->mOriginObject->mVssRays.push_back(ray);
                }
        }
}


void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
{
        const float costDecr = sc.GetRenderCostDecrease();      

        mSubdivisionStats 
                        << "#Leaves\n" << mBvhStats.Leaves()
                        << "#RenderCostDecrease\n" << costDecr << endl 
                        << "#TotalRenderCost\n" << mTotalCost << endl;
                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
}


void BvHierarchy::CollectRays(const ObjectContainer &objects,
                                                          VssRayContainer &rays) const
{
        VssRay::NewMail();
        
        ObjectContainer::const_iterator oit, oit_end = objects.end();

        // evaluate reverse pvs and view cell volume on left and right cell
        // note: should I take all leaf objects or rather the objects hit by rays?
        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                Intersectable *obj = *oit;
                
                VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();

                for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
                {
                        VssRay *ray = (*rit);

                        if (!ray->Mailed())
                        {
                                ray->Mail();
                                rays.push_back(ray);
                        }
                }
        }
}


float BvHierarchy::EvalRenderCost(const BvhTraversalData &tData,
                                                                  const ObjectContainer &objectsFront,
                                                                  const ObjectContainer &objectsBack) const
{
        BvhLeaf *leaf = tData.mNode;

        // probability that view point lies in a view cell which sees this node
        const float pFront = EvalViewCellsVolume(objectsFront);
        const float pBack = EvalViewCellsVolume(objectsBack);
                
        const int totalObjects = (int)leaf->mObjects.size();
        const int nObjectsFront = (int)objectsFront.size();
        const int nObjectsBack = (int)objectsBack.size();

        //-- pvs rendering heuristics
        const float newRenderCost = nObjectsFront * pFront + nObjectsBack * pBack;
        /*
        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
        Debug << "\nbvh render cost\n" 
                  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << endl
                  << "new rc: " << newRenderCost / viewSpaceVol << endl;*/

        return newRenderCost;
}


AxisAlignedBox3 BvHierarchy::ComputeBoundingBox(const ObjectContainer &objects,
                                                                                                const AxisAlignedBox3 *parentBox)
{
        if (parentBox && objects.empty())
                return *parentBox;

        AxisAlignedBox3 box;
        box.Initialize();

        ObjectContainer::const_iterator oit, oit_end = objects.end();

        //-- compute bounding box
        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                Intersectable *obj = *oit;

                // compute bounding box of view space
                box.Include(obj->GetBox());
        }

        return box;
}


void BvHierarchy::CollectLeaves(vector<BvhLeaf *> &leaves) const
{
        stack<BvhNode *> nodeStack;
        nodeStack.push(mRoot);

        while (!nodeStack.empty()) 
        {
                BvhNode *node = nodeStack.top();
                nodeStack.pop();

                if (node->IsLeaf()) 
                {
                        BvhLeaf *leaf = (BvhLeaf *)node;
                        leaves.push_back(leaf);
                }
                else 
                {
                        BvhInterior *interior = (BvhInterior *)node;

                        nodeStack.push(interior->GetBack());
                        nodeStack.push(interior->GetFront());
                }
        }
}


AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
{
        return node->GetBoundingBox();
}


void BvHierarchy::CollectViewCells(const ObjectContainer &objects, 
                                                                   ViewCellContainer &viewCells,
                                                                   const bool setCounter) const
{
        ViewCell::NewMail();
        ObjectContainer::const_iterator oit, oit_end = objects.end();

        // loop through all object and collect view cell pvs of this node
        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                CollectViewCells(*oit, viewCells, true, setCounter);
        }
}


void BvHierarchy::CollectViewCells(Intersectable *obj, 
                                                                   ViewCellContainer &viewCells,
                                                                   const bool useMailBoxing,
                                                                   const bool setCounter) const
{
        VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();

        for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
        {
                VssRay *ray = (*rit);
                ViewCellContainer tmpViewCells;
        
                mVspTree->GetViewCells(*ray, tmpViewCells);

                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();

                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
                {
                        VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);

                        // store view cells
                        if (!useMailBoxing || !vc->Mailed())
                        {
                                if (useMailBoxing)
                                {
                                        vc->Mail();
                                        if (setCounter)
                                        {
                                                vc->mCounter = 0;
                                        }
                                }
                                viewCells.push_back(vc);
                        }
                        
                        if (setCounter)
                        {
                                ++ vc->mCounter;
                        }
                }
        }
}


void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc, 
                                                                                 vector<SubdivisionCandidate *> &dirtyList)
{
        BvhTraversalData &tData = sc->mParentData;
        BvhLeaf *node = tData.mNode;
        
        ViewCellContainer viewCells;
        CollectViewCells(node->mObjects, viewCells);

        // split candidates handling 
        // these view cells  are thrown into dirty list
        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();

        Debug << "collecting " << (int)viewCells.size() << " dirty candidates" << endl;

        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
        {
                VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
                VspLeaf *leaf = vc->mLeaf;
                SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
                
                if (candidate) // is this leaf still a split candidate?
                {
                        dirtyList.push_back(candidate);
                }
        }
}


BvhNode *BvHierarchy::GetRoot() const
{
        return mRoot;
}


bool BvHierarchy::IsObjectInLeaf(BvhLeaf *leaf, Intersectable *object) const
{
        ObjectContainer::const_iterator oit =
                lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
                                
        // objects sorted by id
        if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
        {
                return true;
        }
        else
        {
                return false;
        }
}


BvhLeaf *BvHierarchy::GetLeaf(Intersectable *object, BvhNode *node) const
{
        // rather use the simple version
        if (!object) return NULL;
        return object->mBvhLeaf;
        
        ///////////////////////////////////////
        // start from root of tree
        
        if (node == NULL)
                node = mRoot;
        
        vector<BvhLeaf *> leaves;

        stack<BvhNode *> nodeStack;
        nodeStack.push(node);
  
        BvhLeaf *leaf = NULL;
  
        while (!nodeStack.empty())  
        {
                BvhNode *node = nodeStack.top();
                nodeStack.pop();
        
                if (node->IsLeaf()) 
                {
                        leaf = dynamic_cast<BvhLeaf *>(node);

                        if (IsObjectInLeaf(leaf, object))
                        {
                                return leaf;
                        }
                } 
                else    
                {       
                        // find point
                        BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
        
                        if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
                        {
                                nodeStack.push(interior->GetBack());
                        }
                        
                        // search both sides as we are using bounding volumes
                        if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
                        {
                                nodeStack.push(interior->GetFront());
                        }
                }
        }
  
        return leaf;
}


BvhIntersectable *BvHierarchy::GetOrCreateBvhIntersectable(BvhNode *node)
{
        // search nodes
        std::map<BvhNode *, BvhIntersectable *>::
                const_iterator it = mBvhIntersectables.find(node);

        if (it != mBvhIntersectables.end()) 
        {
                return (*it).second;
        }

        // not in map => create new entry
        BvhIntersectable *bvhObj = new BvhIntersectable(node);
        mBvhIntersectables[node] = bvhObj;

        return bvhObj;
}


bool BvHierarchy::Export(OUT_STREAM &stream)
{
        ExportNode(mRoot, stream);

        return true;
}


void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
{
        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
        {
                stream << (*oit)->GetId() << " ";
        }
}


void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
{
        if (node->IsLeaf())
        {
                BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(node);
                const AxisAlignedBox3 box = leaf->GetBoundingBox();
                stream << "<Leaf"
                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
                           << " objects=\"";
                
                //-- export objects
                ExportObjects(leaf, stream);
                
                stream << "\" />" << endl;
        }
        else
        {       
                BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
                const AxisAlignedBox3 box = interior->GetBoundingBox();

                stream << "<Interior"
                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
                           << "\">" << endl;

                ExportNode(interior->GetBack(), stream);
                ExportNode(interior->GetFront(), stream);

                stream << "</Interior>" << endl;
        }
}


float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects) const
{
        float vol = 0;

        ViewCellContainer viewCells;
        CollectViewCells(objects, viewCells);

        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();

        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
        {
                vol += (*vit)->GetVolume();
        }

        return vol;
}

void BvHierarchy::CreateRoot(const ObjectContainer &objects)
{
        //-- create new root
        AxisAlignedBox3 box = ComputeBoundingBox(objects);
        BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
        bvhleaf->mObjects = objects;

        mRoot = bvhleaf;

        // associate root with current objects
        AssociateObjectsWithLeaf(bvhleaf);
}


SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
                                                                                                           const ObjectContainer &objects)
{
        mBvhStats.Reset();
        mBvhStats.Start();
        mBvhStats.nodes = 1;

        // note matt: we assume that we have objects sorted by their id

        // store pointer to this tree
        BvhSubdivisionCandidate::sBvHierarchy = this;
        mBvhStats.nodes = 1;

        // compute bounding box from objects
        // note: we assume that root was already created
        mBoundingBox = mRoot->GetBoundingBox();
        BvhLeaf *bvhleaf = dynamic_cast<BvhLeaf *>(mRoot);

        mTermMinProbability *= mBoundingBox.GetVolume();
        mGlobalCostMisses = 0;
        
        // only rays intersecting objects in node are interesting
        AssociateObjectsWithRays(sampleRays);
        
        // probabilty is voume of all "seen" view cells
#if 1
        const float prop = EvalViewCellsVolume(objects);
#else
        const float prop = GetBoundingBox().GetVolume();
#endif

        // create bvh traversal data
        BvhTraversalData oData(bvhleaf, 0, mBoundingBox, prop);

        //-- add first candidate for object space partition     
        BvhSubdivisionCandidate *oSubdivisionCandidate = 
                new BvhSubdivisionCandidate(oData);

        EvalSubdivisionCandidate(*oSubdivisionCandidate);
        bvhleaf->SetSubdivisionCandidate(oSubdivisionCandidate);

        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
        mTotalCost = (float)objects.size() * prop / viewSpaceVol;

        PrintSubdivisionStats(*oSubdivisionCandidate);

        return oSubdivisionCandidate;
}


bool BvHierarchy::AddLeafToPvs(BvhLeaf *leaf, 
                                                           ViewCell *vc, 
                                                           const float pdf, 
                                                           float &contribution)
{
        // add kd intersecable to pvs
        BvhIntersectable *bvhObj = GetOrCreateBvhIntersectable(leaf);
        
        return vc->AddPvsSample(bvhObj, pdf, contribution);
}


void BvhStatistics::Print(ostream &app) const
{
        app << "=========== BvHierarchy statistics ===============\n";

        app << setprecision(4);

        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";

        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";

        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";

        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";

        app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits << endl;

        app << "#N_PMINDEPTHLEAVES ( Percentage of leaves at minimum depth )\n" 
                <<      minDepthNodes * 100 / (double)Leaves() << endl;

        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n" 
                <<      maxDepthNodes * 100 / (double)Leaves() << endl;

        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
                << maxCostNodes * 100 / (double)Leaves() << endl;

        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
                << minProbabilityNodes * 100 / (double)Leaves() << endl;

        app << "#N_PMINOBJECTSLEAVES  ( Percentage of leaves with mininum objects )\n"
                << minObjectsNodes * 100 / (double)Leaves() << endl;

        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;

        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;

        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;

        app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;

        app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";

        //app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
        
        app << "========== END OF VspTree statistics ==========\n";
}


}