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

#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"
#include "HierarchyManager.h"


namespace GtpVisibilityPreprocessor {


#define PROBABILIY_IS_BV_VOLUME 1
#define USE_FIXEDPOINT_T 0
#define COUNT_ORIGIN_OBJECTS 0

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

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


/// sorting operator
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() 
{ 
}

void BvhLeaf::CollectObjects(ObjectContainer &objects)
{
        ObjectContainer::const_iterator oit, oit_end = objects.end();
        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                objects.push_back(*oit);
        }
}

/******************************************************************/
/*              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;
}


void BvhInterior::CollectObjects(ObjectContainer &objects)
{
        mFront->CollectObjects(objects);
        mBack->CollectObjects(objects);
}


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


BvHierarchy::BvHierarchy():
mRoot(NULL),
mTimeStamp(1)
{
        ReadEnvironment();
        mSubdivisionCandidates = new SortableEntryContainer;
        for (int i = 0; i < 3; ++ i)
                mSortedObjects[i] = NULL;
}


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);

        for (int i = 0; i < 3; ++ i)
        {
                DEL_PTR(mSortedObjects[i]);
        }
        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()->GetIntValue("BvHierarchy.Termination.minRays", mTermMinRays);
        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 subdivision heuristics

        // if only the driving axis is used for splits
        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);
        
        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);


        /////////////
        //-- 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 << "use global sort: " << mUseGlobalSorting << endl;
        Debug << endl;
}


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


static int CountRays(const ObjectContainer &objects)
{
        int nRays = 0;

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

        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                nRays += (int)(*oit)->mVssRays.size();
        }

        return nRays;
}


BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
                                                                                BvhTraversalData &frontData,
                                                                                BvhTraversalData &backData)
{
        const BvhTraversalData &tData = sc.mParentData;
        BvhLeaf *leaf = tData.mNode;
        AxisAlignedBox3 parentBox = leaf->GetBoundingBox();

        // update stats: we have two new leaves
        mBvhStats.nodes += 2;

        if (tData.mDepth > mBvhStats.maxDepth)
        {
                mBvhStats.maxDepth = tData.mDepth;
        }

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

        //////////////////
        //-- create front and back leaf

        AxisAlignedBox3 fbox = EvalBoundingBox(sc.mFrontObjects, &parentBox);
        AxisAlignedBox3 bbox = EvalBoundingBox(sc.mBackObjects, &parentBox);

        BvhLeaf *back = 
                new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
        BvhLeaf *front = 
                new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());

        BvhInterior *parent = leaf->GetParent();

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

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

        ++ mBvhStats.splits;


        ////////////////////////////////////////
        //-- fill  front and back traversal data with the new values

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

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

        back->mObjects = sc.mBackObjects;
        front->mObjects = sc.mFrontObjects;

        // if the number of rays is too low, no assumptions can be made
        // (=> switch to surface area heuristics?)
        frontData.mNumRays = CountRays(sc.mFrontObjects);
        backData.mNumRays = CountRays(sc.mBackObjects);

        AssociateObjectsWithLeaf(back);
        AssociateObjectsWithLeaf(front);
   
#if PROBABILIY_IS_BV_VOLUME
        // volume of bvh (= probability that this bvh can be seen)
        frontData.mProbability = fbox.GetVolume();
        backData.mProbability = bbox.GetVolume();
#else
        // compute probability of this node being visible, 
        // i.e., volume of the view cells that can see this node
        frontData.mProbability = EvalViewCellsVolume(sc.mFrontObjects);
        backData.mProbability = EvalViewCellsVolume(sc.mBackObjects);
#endif

    // how often was max cost ratio missed in this branch?
        frontData.mMaxCostMisses = sc.GetMaxCostMisses();
        backData.mMaxCostMisses = sc.GetMaxCostMisses();
        
        // assign the objects in sorted order
        if (mUseGlobalSorting)
        {
                AssignSortedObjects(sc, frontData, backData);
        }
        
        // return the new interior node
        return node;
}


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

        BvhNode *currentNode = tData.mNode;

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

                BvhTraversalData tFrontData;
                BvhTraversalData tBackData;
                        
                // create new interior node and two leaf node
                currentNode = SubdivideNode(
                        *sc, 
                        tFrontData, 
                        tBackData);
        
                // 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);

                tQueue.Push(frontCandidate);
                tQueue.Push(backCandidate);
        }

        /////////////////////////////////
        //-- node is a leaf => terminate traversal

        if (currentNode->IsLeaf())
        {
                //////////////////////////////////////
                //-- store additional info
                EvaluateLeafStats(tData);
        
                const bool mStoreRays = true;
                if (mStoreRays)
                {
                        BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(currentNode);
                        CollectRays(leaf->mObjects, leaf->mVssRays);
                }
                
                //////////////////////////////////////
                
                // this leaf is no candidate for splitting anymore
                // => detach subdivision candidate
                tData.mNode->SetSubdivisionCandidate(NULL); 
                // detach node so we don't delete it with the traversal data
                tData.mNode = NULL;
        }
        
        return currentNode;
}


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.SetMaxCostMisses(maxCostRatioViolated ? 
                splitCandidate.mParentData.mMaxCostMisses + 1 :
                splitCandidate.mParentData.mMaxCostMisses);

        const float oldProp = EvalViewCellsVolume(leaf->mObjects);
        const float oldRenderCost = EvalRenderCost(leaf->mObjects);
                
        // compute global decrease in render cost
        const float newRenderCost = 
                EvalRenderCost(splitCandidate.mFrontObjects) +
                EvalRenderCost(splitCandidate.mBackObjects);

        const float renderCostDecr = oldRenderCost - newRenderCost;
        
#ifdef _DEBUG
        Debug << "old render cost: " << oldRenderCost << endl;
        Debug << "new render cost: " << newRenderCost << endl;
        Debug << "render cost decrease: " << renderCostDecr << endl;
#endif

#if 1
        float priority;
        
        if (mHierarchyManager->GetViewSpaceSubdivisionType() == 
                HierarchyManager::NO_VIEWSPACE_SUBDIV)
        {
                ////////////////
                //-- surface area heuristics

        //      if (objects.empty())
        //              return 0.0f;

                const AxisAlignedBox3 box = EvalBoundingBox(leaf->mObjects);
                const float area = box.SurfaceArea();
                const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();

                priority = (float)leaf->mObjects.size() * area / viewSpaceArea;
        }
        else
        {
                // take render cost of node into account 
                // otherwise danger of being stuck in a local minimum!!
                priority = mRenderCostDecreaseWeight * renderCostDecr + 
                                   (1.0f - mRenderCostDecreaseWeight) * oldRenderCost;
        }

#else
        const float priority = (float)-splitCandidate.mParentData.mDepth;
#endif

        splitCandidate.SetRenderCostDecrease(renderCostDecr);

        // increase in pvs entries
        const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate);
        splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);

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


float BvHierarchy::EvalPriority(const BvhSubdivisionCandidate &splitCandidate) const
{
        BvhLeaf *leaf = splitCandidate.mParentData.mNode;

        const float oldRenderCost = EvalRenderCost(leaf->mObjects);

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

        const float renderCostDecr = oldRenderCost - newRenderCost;

#ifdef _DEBUG
        Debug << "old render cost: " << oldRenderCost << endl;
        Debug << "new render cost: " << newRenderCost << endl;
        Debug << "render cost decrease: " << renderCostDecr << endl;
#endif

#if 1
        // 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;
#else
        const float priority = (float)-splitCandidate.mParentData.mDepth;
#endif

        return priority;
}


int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate) const
{
        const int oldPvsSize = CountViewCells(splitCandidate.mParentData.mNode->mObjects);
        
        const int fPvsSize = CountViewCells(splitCandidate.mFrontObjects);
        const int bPvsSize = CountViewCells(splitCandidate.mBackObjects);

        return fPvsSize + bPvsSize - oldPvsSize;
}


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


inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
{
        // note: tracking for global cost termination 
        // does not make much sense for interleaved vsp / osp partition
        // as it is the responsibility of the hierarchy manager

        const bool terminationCriteriaMet =
                (0
                || (mBvhStats.Leaves() >= mTermMaxLeaves)
                //|| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
                //|| mOutOfMemory 
                );

#ifdef _DEBUG
        if (terminationCriteriaMet)
        {
                Debug << "bvh global termination criteria met:" << endl;
                Debug << "cost misses: " << mBvhStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
                Debug << "leaves: " << mBvhStats.Leaves() << " " << mTermMaxLeaves << endl;
        }
#endif
        return terminationCriteriaMet; 
}


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

        
        if (data.mProbability <= mTermMinProbability)
        {
                ++ mBvhStats.minProbabilityNodes;
        }

        ////////////////////////////////////////////
        // depth related stuff

        if (data.mDepth < mBvhStats.minDepth)
        {
                mBvhStats.minDepth = data.mDepth;
        }

        if (data.mDepth >= mTermMaxDepth)
        {
        ++ mBvhStats.maxDepthNodes;
        }

        // accumulate depth to compute average depth
        mBvhStats.accumDepth += data.mDepth;


        ////////////////////////////////////////////
        // objects related stuff

        // note: this number should always accumulate to the total number of objects
        mBvhStats.objectRefs += (int)leaf->mObjects.size();

        if ((int)leaf->mObjects.size() <= mTermMinObjects)
        {
             ++ mBvhStats.minObjectsNodes;
        }

        if (leaf->mObjects.empty())
        {
                ++ mBvhStats.emptyNodes;
        }

        if ((int)leaf->mObjects.size() > mBvhStats.maxObjectRefs)
        {
                mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
        }

        if ((int)leaf->mObjects.size() < mBvhStats.minObjectRefs)
        {
                mBvhStats.minObjectRefs = (int)leaf->mObjects.size();
        }

        ////////////////////////////////////////////
        // ray related stuff

        // note: this number should always accumulate to the total number of rays
        mBvhStats.rayRefs += data.mNumRays;
        
        if (data.mNumRays <= mTermMinRays)
        {
             ++ mBvhStats.minRaysNodes;
        }

        if (data.mNumRays > mBvhStats.maxRayRefs)
        {
                mBvhStats.maxRayRefs = data.mNumRays;
        }

        if (data.mNumRays < mBvhStats.minRayRefs)
        {
                mBvhStats.minRayRefs = data.mNumRays;
        }

#if 0
        cout << "depth: " << data.mDepth << " objects: " << (int)leaf->mObjects.size() 
                 << " rays: " << data.mNumRays << " rays / objects " 
                 << (float)data.mNumRays / (float)leaf->mObjects.size() << endl;
#endif
}


#if 0

/// compute object boundaries using spatial mid split
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 = EvalRenderCost(tData.mNode->mObjects);
        const float newRenderCost = 
                EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);

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

#else

/// compute object partition by getting balanced objects on the left and right side
float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
                                                                                        const int axis,
                                                                                        ObjectContainer &objectsFront,
                                                                                        ObjectContainer &objectsBack)
{
        PrepareLocalSubdivisionCandidates(tData, axis);
        
        SortableEntryContainer::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 oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
        const float newRenderCost = EvalRenderCost(objectsFront) + EvalRenderCost(objectsBack);

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


float BvHierarchy::EvalSah(const BvhTraversalData &tData,
                                                   const int axis,
                                                   ObjectContainer &objectsFront,
                                                   ObjectContainer &objectsBack)
{
        // go through the lists, count the number of objects left and right
        // and evaluate the following cost funcion:
        // C = ct_div_ci  + (ol + or)/queries
        PrepareLocalSubdivisionCandidates(tData, axis);

        int objectsLeft = 0, objectsRight = (int)tData.mNode->mObjects.size();
  
        AxisAlignedBox3 box = tData.mNode->GetBoundingBox();

        float minBox = box.Min(axis);
        float maxBox = box.Max(axis);
        float boxArea = box.SurfaceArea();

        float minSum = 1e20f;
  
        float minBorder = maxBox;
        float maxBorder = minBox;
        float areaLeft = 0, areaRight = 0;

        SortableEntryContainer::const_iterator currentPos =
                mSubdivisionCandidates->begin();

        
        // we keep track of both borders of the bounding boxes =>
        // store the events in descending order
        vector<float> bordersRight;
        bordersRight.resize(mSubdivisionCandidates->size());

        SortableEntryContainer::reverse_iterator rcit = 
                mSubdivisionCandidates->rbegin(), rcit_end = mSubdivisionCandidates->rend();
        
        vector<float>::reverse_iterator rbit = bordersRight.rbegin();
        
        for (; rcit != rcit_end; ++ rcit, ++ rbit) 
        {
                Intersectable *obj = (*rcit).mObject;
                const AxisAlignedBox3 box = obj->GetBox();

                if (box.Min(axis) < minBorder)
                {
                        minBorder = box.Min(axis);
                }

                (*rbit) = minBorder;
        }

        vector<float>::const_iterator bit = bordersRight.begin();
        SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();

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

                ++ objectsLeft;
                -- objectsRight;

                AxisAlignedBox3 lbox = box;
                AxisAlignedBox3 rbox = box;
        
                const AxisAlignedBox3 obox = obj->GetBox();

                // the borders of the bounding boxes have changed
                if (obox.Max(axis) > maxBorder)
                {
                        maxBorder = obox.Max(axis);
                }

                minBorder = (*bit);
        
        lbox.SetMax(axis, maxBorder);
                rbox.SetMin(axis, minBorder);
        
                const float al = lbox.SurfaceArea();
                const float ar = rbox.SurfaceArea();

                const float sum = objectsLeft * al + objectsRight * ar;
      
                /*cout << "pos=" << (*cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=(" 
                         << lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
                cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
            cout << "cost= " << sum << endl;
*/
                if (sum < minSum) 
                {
                        minSum = sum;
                        areaLeft = al;
                        areaRight = ar;
                        // objects belong 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);

        float oldCost = (float)tData.mNode->mObjects.size();
        float newCost = minSum / boxArea;
        float ratio = newCost / oldCost;
  
#ifdef _DEBUG
        cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of " 
                 << (int)tData.mNode->mObjects.size() << ")\t area=(" 
                 << areaLeft << "," << areaRight << ")" << endl;
        cout << "cost= " << minSum << endl;
#endif
  return ratio;
}


static bool PrepareOutput(const int axis,
                                                  const int leaves,
                                                  ofstream &sumStats, 
                                                  ofstream &vollStats, 
                                                  ofstream &volrStats)
{
        if ((axis == 0) && (leaves > 0) && (leaves < 90))
        {
                char str[64];   
                sprintf(str, "tmp/bvh_heur_sum-%04d.log", leaves);
                sumStats.open(str);
                sprintf(str, "tmp/bvh_heur_voll-%04d.log", leaves);
                vollStats.open(str);
                sprintf(str, "tmp/bvh_heur_volr-%04d.log", leaves);
                volrStats.open(str);
        }

        return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
}


static void PrintHeuristics(const int objectsRight,
                                                        const float sum,
                                                        const float volLeft,
                                                        const float volRight,
                                                        const float viewSpaceVol,
                                                        ofstream &sumStats, 
                                                        ofstream &vollStats, 
                                                        ofstream &volrStats)
{
        sumStats
                << "#Position\n" << objectsRight << endl
                << "#Sum\n" << sum / viewSpaceVol << endl
                << "#Vol\n" << (volLeft +  volRight) / viewSpaceVol << endl;

        vollStats
                << "#Position\n" << objectsRight << endl
                << "#Vol\n" << volLeft / viewSpaceVol << endl;

        volrStats
                << "#Position\n" << objectsRight << endl
                << "#Vol\n" << volRight / viewSpaceVol << endl;
}


float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
                                                                                   const int axis,
                                                                                   ObjectContainer &objectsFront,
                                                                                   ObjectContainer &objectsBack)
{
        ////////////////////////////////////////////////////////////////
        // go through the lists, count the number of objects left and right
        // and evaluate the cost funcion

        // prepare the heuristics by setting mailboxes and counters.
        const float totalVol = PrepareHeuristics(tData, axis);
        
        // local helper variables
        float volLeft = 0;
        float volRight = totalVol;
        int nObjectsLeft = 0;
        const int nTotalObjects = (int)tData.mNode->mObjects.size();
        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();

        SortableEntryContainer::const_iterator backObjectsStart = 
                mSubdivisionCandidates->begin();

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

        float volBack = volLeft;
        float volFront = volRight;
        float newRenderCost = nTotalObjects * totalVol;

#ifdef _DEBUG
        ofstream sumStats;
        ofstream vollStats;
        ofstream volrStats;

        const bool printStats =
                PrepareOutput(axis, mBvhStats.Leaves(), sumStats, vollStats, volrStats);
#endif

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

        SortableEntryContainer::const_iterator cit, cit_end = 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;

#ifdef _DEBUG
                if (printStats)
                {
                        PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
                                                        sumStats, vollStats, volrStats);
                }
#endif

                if (sum < newRenderCost)
                {
                        newRenderCost = sum;

                        volBack = volLeft;
                        volFront = volRight;

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

        ////////////////////////////////////////////
        //-- assign object to front and back volume

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

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

#ifdef _DEBUG
        Debug << "\n§§§§ bvh eval const decrease §§§§" << 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;
#endif

        return ratio;
}


void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
                                                                                                        const int axis)                                                                                 
{
        //-- insert object queries
        ObjectContainer *objects = 
                mUseGlobalSorting ? tData.mSortedObjects[axis] : &tData.mNode->mObjects;

        CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, !mUseGlobalSorting, axis);
}


void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects, 
                                                                                                  SortableEntryContainer **subdivisionCandidates, 
                                                                                                  const bool sort,
                                                                                                  const int axis)
{
        (*subdivisionCandidates)->clear();

        // compute requested size and look if subdivision candidate has to be recomputed
        const int requestedSize = (int)objects.size() * 2;
        
        // creates a sorted split candidates array
        if ((*subdivisionCandidates)->capacity() > 500000 &&
                requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
        {
        delete (*subdivisionCandidates);
                (*subdivisionCandidates) = new SortableEntryContainer;
        }

        (*subdivisionCandidates)->reserve(requestedSize);

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

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

                (*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
        }

        if (sort)
        {       // no presorted candidate list
                stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
        }
}


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


float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData, const int axis)
{       
        BvhLeaf *leaf = tData.mNode;
        float vol = 0;

    // sort so we can use a sweep from right to left
        PrepareLocalSubdivisionCandidates(tData, axis);
        
        // 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();
        }

        // we will mail view cells switching to the back side
        ViewCell::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];

        int sAxis = 0;
        int bestAxis = -1;

        if (mOnlyDrivingAxis)
        {
                const AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
                sAxis = box.Size().DrivingAxis();
        }
        
        ////////////////////////////////////
        //-- evaluate split cost for all three axis
        
        for (int axis = 0; axis < 3; ++ axis)
        {
                if (!mOnlyDrivingAxis || (axis == sAxis))
                {
                        if (mUseCostHeuristics)
                        {
                                //////////////////////////////////
                //-- split objects using heuristics
                                
                                if (mHierarchyManager->GetViewSpaceSubdivisionType() == 
                                        HierarchyManager::KD_BASED_VIEWSPACE_SUBDIV)
                                {
                                        ///////////
                                        //-- heuristics using objects weighted by view cells volume
                                        nCostRatio[axis] =
                                                EvalLocalCostHeuristics(
                                                                                                tData,
                                                                                                axis,
                                                                                                nFrontObjects[axis],
                                                                                                nBackObjects[axis]);
                                }
                                else
                                {
                                        //////////////////
                                        //-- view cells not constructed yet     => use surface area heuristic                   
                                        nCostRatio[axis] =
                                                EvalSah(
                                                                tData,
                                                                axis,
                                                                nFrontObjects[axis],
                                                                nBackObjects[axis]);
                                }
                        }
                        else
                        {
                                //-- split objects using some simple criteria
                                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];
}


int BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays) const
{
        int nRays = 0;
        VssRayContainer::const_iterator rit, rit_end = rays.end();

        VssRay::NewMail();

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

                if (ray->mTerminationObject)
                {
                        ray->mTerminationObject->mVssRays.push_back(ray);
                        if (!ray->Mailed())
                        {
                                ray->Mail();
                                ++ nRays;
                        }
                }

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

                        if (!ray->Mailed())
                        {
                                ray->Mail();
                                ++ nRays;
                        }
                }
        }

        return nRays;
}


void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
{
        const float costDecr = 
                sc.GetRenderCostDecrease();// / mHierarchyManager->GetViewSpaceBox().GetVolume();       

        mSubdivisionStats 
                        << "#Leaves\n" << mBvhStats.Leaves() << endl
                        << "#RenderCostDecrease\n" << costDecr << endl 
                        << "#TotalRenderCost\n" << mTotalCost << 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 ObjectContainer &objects) const
{       
        if (0 && 
                (mHierarchyManager->GetViewSpaceSubdivisionType() == 
                HierarchyManager::NO_VIEWSPACE_SUBDIV))
        {
                ////////////////
                //-- surface area heuristics

                if (objects.empty())
                        return 0.0f;

                const AxisAlignedBox3 box = EvalBoundingBox(objects);
                const float area = box.SurfaceArea();
                const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();

                return (float)objects.size() * area / viewSpaceArea;
        }
        else
        {       ///////////////
                //-- render cost heuristics

                const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();

                // probability that view point lies in a view cell which sees this node
                const float p = EvalViewCellsVolume(objects) / viewSpaceVol;    

                return (float)objects.size() * p;
        }
}


AxisAlignedBox3 BvHierarchy::EvalBoundingBox(const ObjectContainer &objects,
                                                                                         const AxisAlignedBox3 *parentBox) const
{
        // if there are no objects in this box, box size is set to parent box size. 
        // Question: Invalidate box instead?
        if (parentBox && objects.empty())
                return *parentBox;

        AxisAlignedBox3 box;
        box.Initialize();

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

        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                Intersectable *obj = *oit;
                // grow bounding box to include all objects
                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
{
        // no view cells yet
        if (0 && mHierarchyManager->GetViewSpaceSubdivisionType() == 
                HierarchyManager::NO_VIEWSPACE_SUBDIV)
                return;

        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;
        
                mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);

                // matt: probably slow to allocate memory for view cells every time
                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();

                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
                {
                        //VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
                        ViewCell *vc = *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;
                        }
                }
        }
}


int BvHierarchy::CountViewCells(Intersectable *obj) const
{
        int result = 0;
        
        VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();

        for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
        {
                VssRay *ray = (*rit);
                ViewCellContainer tmpViewCells;
        
                mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
                
                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
                {
                        ViewCell *vc = *vit;

                        // store view cells
                        if (!vc->Mailed())
                        {
                                vc->Mail();
                                ++ result;
                        }
                }
        }

        return result;
}


int BvHierarchy::CountViewCells(const ObjectContainer &objects) const
{
        // no view cells yet
        if (0 && mHierarchyManager->GetViewSpaceSubdivisionType() == 
                HierarchyManager::NO_VIEWSPACE_SUBDIV)
                return 1;

        int nViewCells = 0;

        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)
        {
                nViewCells += CountViewCells(*oit);
        }

        return nViewCells;
}


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

        if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
        
        // split candidates handling 
        // these view cells  are thrown into dirty list
        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();

        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
        {
        VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
                VspLeaf *leaf = vc->mLeaves[0];
        
                SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
                
                // is this leaf still a split candidate?
                if (candidate && (!onlyUnmailed || !candidate->Mailed()))
                {
                        candidate->Mail();
                        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::Initialise(const ObjectContainer &objects)
{
        ///////
        //-- create new root

        AxisAlignedBox3 box = EvalBoundingBox(objects);
        BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
        bvhleaf->mObjects = objects;
        mRoot = bvhleaf;

        // compute bounding box from objects
        mBoundingBox = mRoot->GetBoundingBox();

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


/*
Mesh *BvHierarchy::MergeLeafToMesh()
void BvHierarchy::MergeLeavesToMeshes()
{
        vector<BvhLeaf *> leaves;
        CollectLeaves(leaves);

        vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();

        for (lit = leaves.begin(); lit != lit_end; ++ lit)
        {
                Mesh *mesh = MergeLeafToMesh(*lit);
        }
}*/


SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
                                                                                                           const ObjectContainer &objects)
{
        ///////////////////////////////////////
        //-- we assume that we have objects sorted by their id => 
        //-- we don't have to sort them here and an binary search 
        //-- for identifying if a object is in a leaf.
        
        mBvhStats.Reset();
        mBvhStats.Start();
        mBvhStats.nodes = 1;
                
        // store pointer to this tree
        BvhSubdivisionCandidate::sBvHierarchy = this;
        
        // root and bounding box was already constructed
        BvhLeaf *bvhLeaf = dynamic_cast<BvhLeaf *>(mRoot);

        // multiply termination criterium for comparison,
        // so it can be set between zero and one and
        // no division is necessary during traversal

#if PROBABILIY_IS_BV_VOLUME
        mTermMinProbability *= mBoundingBox.GetVolume();
        // probability that bounding volume is seen
        const float prop = GetBoundingBox().GetVolume();
#else
        mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
        // probability that volume is "seen" from the view cells
        const float prop = EvalViewCellsVolume(objects);
#endif

        // only rays intersecting objects in node are interesting
        const int nRays = AssociateObjectsWithRays(sampleRays);
        //Debug << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;

        // create bvh traversal data
        BvhTraversalData oData(bvhLeaf, 0, prop, nRays);

        // create sorted object lists for the first data
        if (mUseGlobalSorting)
        {
                AssignInitialSortedObjectList(oData);
        }
        

        ///////////////////
        //-- add first candidate for object space partition     

        BvhSubdivisionCandidate *oSubdivisionCandidate = 
                new BvhSubdivisionCandidate(oData);

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

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

        PrintSubdivisionStats(*oSubdivisionCandidate);

        return oSubdivisionCandidate;
}


void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData)
{
        // we sort the objects as a preprocess so they don't have
        // to be sorted for each split
        for (int i = 0; i < 3; ++ i)
        {
                // create new objects
                if (!mSortedObjects[i])
                {
                        mSortedObjects[i] = new SortableEntryContainer();
                        CreateLocalSubdivisionCandidates(tData.mNode->mObjects, &mSortedObjects[i], true, i);
                }

                // copy list into traversal data list
                tData.mSortedObjects[i] = new ObjectContainer();
                tData.mSortedObjects[i]->reserve((int)mSortedObjects[i]->size());

                SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end();

                for (oit = mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
                {
                        tData.mSortedObjects[i]->push_back((*oit).mObject);
                }
        }
}


void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
                                                                          BvhTraversalData &frontData,
                                                                          BvhTraversalData &backData)
{
        Intersectable::NewMail();

        // we sorted the objects as a preprocess so they don't have
        // to be sorted for each split
        ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();

        for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
        {
                (*fit)->Mail();
        }

        for (int i = 0; i < 3; ++ i)
        {
                frontData.mSortedObjects[i] = new ObjectContainer();
                backData.mSortedObjects[i] = new ObjectContainer();

                frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
                backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());

                ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mSortedObjects[i]->end();

                for (oit = sc.mParentData.mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
                {
                        if ((*oit)->Mailed())
                        {
                                frontData.mSortedObjects[i]->push_back(*oit);
                        }
                        else
                        {
                                backData.mSortedObjects[i]->push_back(*oit);
                        }
                }
        }
}


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

        // reset root
        DEL_PTR(mRoot);
        
        BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
        bvhleaf->mObjects = objects;
        mRoot = bvhleaf;
        
#if PROBABILIY_IS_BV_VOLUME
        mTermMinProbability *= mBoundingBox.GetVolume();
        // probability that bounding volume is seen
        const float prop = GetBoundingBox().GetVolume();
#else
        mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
        // probability that volume is "seen" from the view cells
        const float prop = EvalViewCellsVolume(objects);
#endif

        const int nRays = CountRays(objects);
        BvhLeaf *bvhLeaf = dynamic_cast<BvhLeaf *>(mRoot);

        // create bvh traversal data
        BvhTraversalData oData(bvhLeaf, 0, prop, nRays);

        AssignInitialSortedObjectList(oData);
        

        ///////////////////
        //-- add first candidate for object space partition     

        BvhSubdivisionCandidate *oSubdivisionCandidate = 
                new BvhSubdivisionCandidate(oData);

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

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

        PrintSubdivisionStats(*oSubdivisionCandidate);

        return oSubdivisionCandidate;
}


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_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_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n" 
                <<      maxDepthNodes * 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_PMINOBJECTSLEAVES  ( Percentage of leaves with mininum objects )\n"
                << minObjectsNodes * 100 / (double)Leaves() << endl;

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

        app << "#N_MINOBJECTREFS  ( Min number of object refs / leaf )\n" << minObjectRefs << "\n";

        app << "#N_EMPTYLEAFS ( Empty leafs )\n" << emptyNodes << "\n";
        
        app << "#N_PAVGOBJECTSLEAVES  ( average object refs / leaf)\n" << AvgObjectRefs() << endl;


        ////////////////////////////////////////////////////////
        
        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with mininum rays )\n"
                << minRaysNodes * 100 / (double)Leaves() << endl;

        app << "#N_MAXRAYREFS  ( Max number of ray refs / leaf )\n" << maxRayRefs << "\n";

        app << "#N_MINRAYREFS  ( Min number of ray refs / leaf )\n" << minRayRefs << "\n";
        
        app << "#N_PAVGRAYLEAVES  ( average ray refs / leaf )\n" << AvgRayRefs() << endl;
        
        app << "#N_PAVGRAYCONTRIBLEAVES  ( Average ray contribution)\n" <<
                rayRefs / (double)objectRefs << endl;

        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n"<<
                maxRayContriNodes * 100 / (double)Leaves() << endl;

        app << "#N_PGLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;

        app << "========== END OF BvHierarchy statistics ==========\n";
}


// TODO: return memory usage in MB
float BvHierarchy::GetMemUsage() const
{
        return (float)
                 (sizeof(BvHierarchy)
                  + mBvhStats.Leaves() * sizeof(BvhLeaf) 
                  + mBvhStats.Interior() * sizeof(BvhInterior)
                  ) / (1024.0f * 1024.0f);
}


}