source: GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp @ 1614

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

#include "ViewCell.h"
#include "Plane3.h"
#include "HierarchyManager.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 "KdTree.h"
#include "IntersectableWrapper.h"
#include "VspTree.h"
#include "OspTree.h"
#include "BvHierarchy.h"


namespace GtpVisibilityPreprocessor {


#define USE_FIXEDPOINT_T 0


/*******************************************************************/
/*              class HierarchyManager implementation              */
/*******************************************************************/


HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
mOspTree(NULL), 
mBvHierarchy(NULL)
{
        switch(mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                mOspTree = new OspTree();
                mOspTree->mVspTree = mVspTree;
                mOspTree->mHierarchyManager = this;
                break;
        case BV_BASED_OBJ_SUBDIV:
        mBvHierarchy = new BvHierarchy();
                mBvHierarchy->mHierarchyManager = this;
                break;
        default:
                break;
        }

        // hierarchy manager links view space partition and object space partition
        mVspTree = new VspTree();
        mVspTree->mHierarchyManager = this;
        
        mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
        ParseEnvironment();
}


HierarchyManager::HierarchyManager(KdTree *kdTree): 
mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
mBvHierarchy(NULL)
{
        mOspTree = new OspTree(*kdTree);
        mOspTree->mVspTree = mVspTree;

        mVspTree = new VspTree();
        mVspTree->mHierarchyManager = this;

        mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
        ParseEnvironment();
}


void HierarchyManager::ParseEnvironment()
{
        Environment::GetSingleton()->GetFloatValue(
                "Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);

        Environment::GetSingleton()->GetBoolValue(
                "Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);

        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Termination.maxLeaves", mTermMaxLeaves);

        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Construction.type", mConstructionType);

        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);

        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
        
        Environment::GetSingleton()->GetBoolValue(
                "Hierarchy.Construction.repairQueue", mRepairQueue);

        Environment::GetSingleton()->GetBoolValue(
                "Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);

        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Construction.levels", mNumMultiLevels);

        Debug << "******** Hierachy Manager Parameters ***********" << endl;
        Debug << "max leaves: " << mTermMaxLeaves << endl;
        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
        Debug << "construction type: " << mConstructionType << endl;
        Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
        Debug << "repair queue: " << mRepairQueue << endl;
        Debug << "number of multilevels: " << mNumMultiLevels << endl;
        Debug << endl;
}


HierarchyManager::~HierarchyManager()
{
        DEL_PTR(mOspTree);
        DEL_PTR(mVspTree);
        DEL_PTR(mBvHierarchy);
}


int HierarchyManager::GetObjectSpaceSubdivisionType() const
{
        return mObjectSpaceSubdivisionType;
}


int HierarchyManager::GetViewSpaceSubdivisionType() const
{
        return mViewSpaceSubdivisionType;
}


void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
{
        mVspTree->SetViewCellsManager(vcm);

        if (mOspTree)
        {
                mOspTree->SetViewCellsManager(vcm);
        }
        else if (mBvHierarchy)
        {
                mBvHierarchy->SetViewCellsManager(vcm);
        }
}


void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
{
        mVspTree->SetViewCellsTree(vcTree);
}


VspTree *HierarchyManager::GetVspTree() 
{ 
        return mVspTree; 
}

/*
AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
{
        return mVspTree->mBoundingBox;
}*/


AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
{
        switch (mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                return mOspTree->mBoundingBox;
        case BV_BASED_OBJ_SUBDIV:
                return mBvHierarchy->mBoundingBox;
        default:
                // hack: empty box
                return AxisAlignedBox3();
        }
}


SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
{
        SubdivisionCandidate *splitCandidate = mTQueue.Top();
        mTQueue.Pop();

        return splitCandidate;
}


void HierarchyManager::EvalSubdivisionStats(const float renderCostDecr)
{
        //cout << "pvs entries " << mHierarchyStats.pvsEntries << endl;
        AddSubdivisionStats(mHierarchyStats.Leaves(),
                                                renderCostDecr,
                                                mTotalCost,
                                                mHierarchyStats.pvsEntries
                                                );
}


void HierarchyManager::AddSubdivisionStats(const int splits,
                                                                                   const float renderCostDecr,
                                                                                   const float totalRenderCost,
                                                                                   const int pvsEntries)
{
        mSubdivisionStats
                        << "#Splits\n" << splits << endl
                        << "#RenderCostDecrease\n" << renderCostDecr << endl 
                        << "#TotalEntriesInPvs\n" << pvsEntries << endl
                        << "#TotalRenderCost\n" << totalRenderCost << endl;
}


bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
{
        const bool terminationCriteriaMet = 
                (0
                || (mHierarchyStats.Leaves() >= mTermMaxLeaves) 
                || (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
                || (candidate->GlobalTerminationCriteriaMet())
                );

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

        return terminationCriteriaMet;
}


void HierarchyManager::Construct(const VssRayContainer &sampleRays,
                                                                 const ObjectContainer &objects,
                                                                 AxisAlignedBox3 *forcedViewSpace)
{
        if (mUseMultiLevelConstruction)
        {
                ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
        }
        else
        {
                char subdivisionStatsLog[100];
                Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", 
                subdivisionStatsLog);
                mSubdivisionStats.open(subdivisionStatsLog);

                ConstructInterleaved(sampleRays, objects, forcedViewSpace);
        }
}


void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
                                                                                        const ObjectContainer &objects,
                                                                                        AxisAlignedBox3 *forcedViewSpace)
{
        mHierarchyStats.Reset();
        mHierarchyStats.Start();
        mHierarchyStats.nodes = 2; // two nodes for view space and object space

        mTotalCost = (float)objects.size();
        EvalSubdivisionStats(0);
        Debug << "setting total cost to " << mTotalCost << endl;

        const long startTime = GetTime();
        cout << "Constructing view space / object space tree ... \n";
        
        // compute view space bounding box
        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);

        // use objects for evaluating vsp tree construction in the first levels
        // of the subdivision
        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;

        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;

        // start with view space subdivison: prepare vsp tree for traversal
        if (StartViewSpaceSubdivision())
        {
                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
                PrepareViewSpaceSubdivision(sampleRays, objects);
        }
        
        // start object space subdivision immediately?
        if (StartObjectSpaceSubdivision())
        {
                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
                PrepareObjectSpaceSubdivision(sampleRays, objects);
        }

        // process object space candidates
        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
        
        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

        mHierarchyStats.Stop();
        mVspTree->mVspStats.Stop();
        FinishObjectSpaceSubdivision(objects);
}


void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
                                                                                                   const ObjectContainer &objects)
{
        cout << "\nstarting view space hierarchy construction ... " << endl;
        // hack: reset global cost misses
        mHierarchyStats.mGlobalCostMisses = 0;
        
        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
        SubdivisionCandidate *vsc = 
                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);

        mTotalCost = mVspTree->mTotalCost;
        cout << "\nreseting cost for vsp, new total cost: " << mTotalCost << endl;

        mTQueue.Push(vsc);
}


void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
                                                                                                         const ObjectContainer &objects)
{
        mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses

        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
        {
                PrepareOspTree(sampleRays, objects);
        }
        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
        {
                PrepareBvHierarchy(sampleRays, objects);
        }
}


void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
                                                                                  const ObjectContainer &objects)
{
        const long startTime = GetTime();

        cout << "preparing bv hierarchy construction ... " << endl;
        
        // compute first candidate
        SubdivisionCandidate *sc =
                mBvHierarchy->PrepareConstruction(sampleRays, objects);

        mTotalCost = mBvHierarchy->mTotalCost;
        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;

    mTQueue.Push(sc);
        cout << "finished bv hierarchy preparation in " 
                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
}


void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
                                                                          const ObjectContainer &objects)
{
        cout << "starting osp tree construction ... " << endl;

        RayInfoContainer *objectSpaceRays = new RayInfoContainer();

        // start with one big kd cell - all objects can be seen from everywhere
        // note: only true for view space = object space

        // compute first candidate
        SubdivisionCandidate *osc =
                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);

        mTotalCost = mOspTree->mTotalCost;
        Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
        
    mTQueue.Push(osc);
}


bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc, const bool repairQueue)
{
        // test if global termination criteria were met before this split
        const bool globalTerminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);

        bool success = false;

        switch (sc->Type())
        {
        case SubdivisionCandidate::VIEW_SPACE:
                {
                        VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
                        success = !n->IsLeaf(); // local or global termination criteria failed?
                }
                break;
        case SubdivisionCandidate::OBJECT_SPACE:
                {
                        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
                        {
                                KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
                                // local or global termination criteria failed
                                success = !n->IsLeaf();
                        }
                        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
                        {
                                BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
                                // local or global termination criteria failed
                                success = !n->IsLeaf();                                 
                        }
                }
                break;
        default:
                break;
        }

        if (!success) // split was not taken
        {
                return false;
        }

        ///////////////
        //-- split was successful => 
        //-- update stats and render queue

    // cost ratio of cost decrease / totalCost
        const float costRatio = mCurrentCandidate->GetRenderCostDecrease() / mTotalCost;
        //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
        
        if (costRatio < mTermMinGlobalCostRatio)
        {
                ++ mHierarchyStats.mGlobalCostMisses;
        }
        
        mTotalCost -= mCurrentCandidate->GetRenderCostDecrease();
        
        cout << sc->Type() << " ";
                
        // update stats
        mHierarchyStats.nodes += 2;
        
        const int pvsEntries = sc->GetPvsEntriesIncr();
        mHierarchyStats.pvsEntries += pvsEntries;
        
        //cout << "pvs entries: " << pvsEntries << " " << mHierarchyStats.pvsEntries << endl;
        mHierarchyStats.memory += 0; // TODO
        
        // subdivision successful
        EvalSubdivisionStats(sc->GetRenderCostDecrease());
                
        // reevaluate candidates affected by the split for view space splits, 
        // this would be object space splits and other way round
        if (repairQueue) 
        {       
                RepairQueue();
        }

        return true;
}


int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
{
        int maxDepth = 0;

        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
        {
                maxDepth = mOspTree->mOspStats.maxDepth;
        }
        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
        {
                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
        }

        return maxDepth;
}


bool HierarchyManager::StartObjectSpaceSubdivision() const
{
        // view space construction already started
        if (ObjectSpaceSubdivisionConstructed())
                return false;

        // start immediately with object space subdivision?
        if (mStartWithObjectSpace)
                return true;

        // is the queue empty again?
        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
                return true;

        // has the depth for subdivision been reached?
        return 
                ((mConstructionType == INTERLEAVED) && 
                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
}


bool HierarchyManager::StartViewSpaceSubdivision() const
{
        // view space construction already started
        if (ViewSpaceSubdivisionConstructed())
                return false;

        // start immediately with view space subdivision?
        if (!mStartWithObjectSpace)
                return true;

        // is the queue empty again?
        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
                return true;

        // has the depth for subdivision been reached?
        return 
                ((mConstructionType == INTERLEAVED) && 
                 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
}


void HierarchyManager::RunConstruction(const bool repairQueue,
                                                                           const VssRayContainer &sampleRays,
                                                                           const ObjectContainer &objects,
                                                                           AxisAlignedBox3 *forcedViewSpace)
{
        int i = 0;
        while (!FinishedConstruction())
        {
                mCurrentCandidate = NextSubdivisionCandidate();    
                        
                ///////////////////
                //-- subdivide leaf node

                ApplySubdivisionCandidate(mCurrentCandidate, repairQueue);
                                
                // we use objects for evaluating vsp tree construction until 
                // a certain depth once a certain depth existiert ...
                if (StartObjectSpaceSubdivision())
                {
                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;

                        cout << "\nstarting object space subdivision at depth " 
                                 << mVspTree->mVspStats.maxDepth << " (" 
                                 << mMinDepthForObjectSpaceSubdivion << ") " << endl;

                        PrepareObjectSpaceSubdivision(sampleRays, objects);

                        cout << "reseting queue ... ";
                        ResetQueue();
                        cout << "finished" << endl;
                }

                if (StartViewSpaceSubdivision())
                {
                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

                        cout << "\nstarting view space subdivision at depth " 
                                 << GetObjectSpaceSubdivisionDepth() << " (" 
                                 << mMinDepthForViewSpaceSubdivion << ") " << endl;

                        PrepareViewSpaceSubdivision(sampleRays, objects);

                        cout << "reseting queue ... ";
                        ResetQueue();
                        cout << "finished" << endl;
                }

                DEL_PTR(mCurrentCandidate);
        }
}



void HierarchyManager::RunConstruction(const bool repairQueue)
{
        int i = 0;
        // main loop
        while (!FinishedConstruction())
        {
                mCurrentCandidate = NextSubdivisionCandidate();    
                        
                ///////
                //-- subdivide leaf node

                ApplySubdivisionCandidate(mCurrentCandidate, repairQueue);
                DEL_PTR(mCurrentCandidate);
        }
}


void HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
                                                                                                   const ObjectContainer &objects)
{       
#if 0   
                DEL_PTR(mBvHierarchy);
                mBvHierarchy = new BvHierarchy();
                mBvHierarchy->mHierarchyManager = this;

                PrepareObjectSpaceSubdivision(sampleRays, objects);
                return;
#else
        
        // no object space subdivision yet
        if (!ObjectSpaceSubdivisionConstructed())
        {
                return PrepareObjectSpaceSubdivision(sampleRays, objects);
        }

        // object space partition constructed => reconstruct
        switch (mObjectSpaceSubdivisionType)
        {
        case BV_BASED_OBJ_SUBDIV:
                {
                        cout << "\nreseting bv hierarchy" << endl;
                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
        
                        SubdivisionCandidate *firstCandidate = 
                                mBvHierarchy->Reset(sampleRays, objects);

                        mTQueue.Push(firstCandidate);
                        mTotalCost = mBvHierarchy->mTotalCost;

                        mHierarchyStats.nodes = 2;
                        mHierarchyStats.pvsEntries = 0;
                        EvalSubdivisionStats(0);
                }
                break;

        case KD_BASED_OBJ_SUBDIV:
                // TODO
                break;
        default:
                break;
        }
#endif
}


void HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays, 
                                                                                                 const ObjectContainer &objects)
{
        ViewCellsManager *vc = mVspTree->mViewCellsManager;

        DEL_PTR(mVspTree);
        mVspTree = new VspTree();
        mVspTree->mHierarchyManager = this;
        mVspTree->mViewCellsManager = vc;

        PrepareViewSpaceSubdivision(sampleRays, objects);
        
        mHierarchyStats.nodes = 2;
        mHierarchyStats.pvsEntries = 0;
        EvalSubdivisionStats(0);

}


void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                    
                                                                                   const ObjectContainer &objects,
                                                                                   AxisAlignedBox3 *forcedViewSpace)
{
        mHierarchyStats.Reset();
        mHierarchyStats.Start();
        mHierarchyStats.nodes = 2;
        
        mTotalCost = (float)objects.size();
        Debug << "setting total cost to " << mTotalCost << endl;

        const long startTime = GetTime();
        cout << "Constructing view space / object space tree ... \n";
        
        // compute view space bounding box
        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);

        // use sah for evaluating osp tree construction 
        // in the first iteration of the subdivision
        
        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;

        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
        //mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;

        const int limit = mNumMultiLevels;
        int i = 0;

        // render cost optimization
        // start with object space partiton
        // then optimizate view space partition for the current osp
        // and vice versa until iteration depth is reached.
        while (1)
        {
                char subdivisionStatsLog[100];
                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
                mSubdivisionStats.open(subdivisionStatsLog);

                // fsubdivide object space first
                ResetObjectSpaceSubdivision(sampleRays, objects);
                // process object space candidates
                RunConstruction(false);

                // object space subdivision constructed
                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;

                cout << "iteration " << i << " of " << limit << " finished" << endl;

                mSubdivisionStats.close();
                if ((i ++) >= limit)
                        break;

                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
                mSubdivisionStats.open(subdivisionStatsLog);

                /////////////////
                // subdivide view space with respect to the objects

                ResetViewSpaceSubdivision(sampleRays, objects);
                // process view space candidates
                RunConstruction(false);
                // view space subdivision constructed
                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
        
                cout << "iteration " << i << " of " << limit << " finished" << endl;

                mSubdivisionStats.close();

                if ((i ++) >= limit)
                        break;
        }
        
        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

/*#if _DEBUG
        cout << "view space: " << GetViewSpaceBox() << endl;
        cout << "object space:  " << GetObjectSpaceBox() << endl;
#endif*/

        mHierarchyStats.Stop();
        mVspTree->mVspStats.Stop();
        FinishObjectSpaceSubdivision(objects);
}


bool HierarchyManager::FinishedConstruction() const
{
        return mTQueue.Empty();
}


bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
{
        switch (mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                return mOspTree && mOspTree->GetRoot();
        case BV_BASED_OBJ_SUBDIV:
                return mBvHierarchy && mBvHierarchy->GetRoot();
        default:
                return false;
        }
}


bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
{
        return mVspTree && mVspTree->GetRoot();
}


void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
{
        switch (mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                {
                        OspTree::OspSubdivisionCandidate *sc = 
                                dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);

                        mOspTree->CollectDirtyCandidates(sc, dirtyList);
                        break;
                }
        case BV_BASED_OBJ_SUBDIV:
                {
                        BvHierarchy::BvhSubdivisionCandidate *sc = 
                                dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);

                        mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
                        break;
                }
        default:
                break;
        }
}


void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
{
        VspTree::VspSubdivisionCandidate *sc = 
                dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);

        mVspTree->CollectDirtyCandidates(sc, dirtyList);
}


void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
{
        // we have either a object space or view space split
        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
        {
                CollectViewSpaceDirtyList(dirtyList);
        }
        else // object space split
        {
                CollectObjectSpaceDirtyList(dirtyList);
        }
}


void HierarchyManager::RepairQueue()
{
        // for each update of the view space partition:
        // the candidates from object space partition which
        // have been afected by the view space split (the kd split candidates
        // which saw the view cell which was split) must be reevaluated 
        // (maybe not locally, just reinsert them into the queue)
        //
        // vice versa for the view cells
        // for each update of the object space partition
        // reevaluate split candidate for view cells which saw the split kd cell
        // 
        // the priority queue update can be solved by implementing a binary heap
        // (explicit data structure, binary tree)
        // *) inserting and removal is efficient
        // *) search is not efficient => store queue position with each
        // split candidate

        // collect list of "dirty" candidates
        const long startTime = GetTime();
   
        vector<SubdivisionCandidate *> dirtyList;
        CollectDirtyCandidates(dirtyList);
        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
        
        /////////////////////////////////
        //-- reevaluate the dirty list

        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
        
        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
        {
                SubdivisionCandidate* sc = *sit;
                const float rcd = sc->GetRenderCostDecrease();
                
                mTQueue.Erase(sc); // erase from queue
                sc->EvalPriority(); // reevaluate
                
#ifdef _DEBUG
                Debug << "candidate " << sc << " reevaluated\n" 
                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
#endif  
                mTQueue.Push(sc); // reinsert
                cout << ".";
        }

        long endTime = GetTime();
        Real timeDiff = TimeDiff(startTime, endTime);
        mHierarchyStats.repairTime += timeDiff;

        if (1) cout << "repaired in " << timeDiff * 1e-3f << " secs" << endl;
}


void HierarchyManager::ResetQueue()
{
        SubdivisionCandidateContainer mCandidateBuffer;

        // remove from queue
        while (!mTQueue.Empty())
        {
                SubdivisionCandidate *candidate = NextSubdivisionCandidate();
                candidate->EvalPriority(); // reevaluate
                cout << ".";
                mCandidateBuffer.push_back(candidate);
        }

        // put back into queue
        SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
        {
                mTQueue.Push(*sit);
        }
}


void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
{
        // the type of the view cells hierarchy
        switch (mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
                mOspTree->Export(stream);
                stream << endl << "</ObjectSpaceHierarchy>" << endl;
                break;          
        case BV_BASED_OBJ_SUBDIV:
                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
                mBvHierarchy->Export(stream);
                stream << endl << "</ObjectSpaceHierarchy>" << endl;
                break;
        }
}


bool HierarchyManager::AddSampleToPvs(Intersectable *obj, 
                                                                          const Vector3 &hitPoint,
                                                                          ViewCell *vc,
                                                                          const float pdf, 
                                                                          float &contribution) const
{
        if (!obj) return false;

        switch (mObjectSpaceSubdivisionType)
        {
        case NO_OBJ_SUBDIV:
                {
                        // potentially visible objects
                        return vc->AddPvsSample(obj, pdf, contribution);
                }
        case KD_BASED_OBJ_SUBDIV:
                {
                        // potentially visible kd cells
                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
                }
        case BV_BASED_OBJ_SUBDIV:
                {
                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
                        BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
                        
                        return vc->AddPvsSample(bvhObj, pdf, contribution);
                }
        default:
                return false;
        }
}


void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
{
        stream << mHierarchyStats << endl;
        stream << "\nview space:" << endl << endl;
        stream << mVspTree->GetStatistics() << endl;
        stream << "\nobject space:" << endl << endl;

        switch (mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                {
                        stream << mOspTree->GetStatistics() << endl;
                        break;
                }
        case BV_BASED_OBJ_SUBDIV:
                {
                        stream << mBvHierarchy->GetStatistics() << endl;
                        break;
                }
        default:
                break;
        }
}


void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
                                                                                                  const ObjectContainer &objects,
                                                                                                  const AxisAlignedBox3 *bbox,
                                                                                                  const bool exportBounds) const
{
        switch (mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                {
                        ExportOspTree(exporter, objects);
                        break;
                }
        case BV_BASED_OBJ_SUBDIV:
                {
                        exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
                        break;
                }
        default:
                break;
        }
}


void HierarchyManager::ExportOspTree(Exporter *exporter, 
                                                                         const ObjectContainer &objects) const
{
        if (0) exporter->ExportGeometry(objects);
                        
        exporter->SetWireframe();
        exporter->ExportOspTree(*mOspTree, 0);
}


Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray, 
                                                                                                  const bool isTermination) const
{

        Intersectable *obj;
        Vector3 pt;
        KdNode *node;

        ray.GetSampleData(isTermination, pt, &obj, &node);
        
        if (!obj) return NULL;

        switch (mObjectSpaceSubdivisionType)
        {
        case HierarchyManager::KD_BASED_OBJ_SUBDIV:
                {
                        KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
                        return mOspTree->GetOrCreateKdIntersectable(leaf);
                }
        case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                {
                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
                        return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
                }
        default:
                return obj;
        }
}


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

        app << setprecision(4);

        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
        
        app << "#N_RTIME  ( Repair time [s] )\n" << repairTime * 1e-3f << " \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 << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;

        app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
        
        app << "========== END OF Hierarchy statistics ==========\n";
}


static void RemoveRayRefs(const ObjectContainer &objects)
{
        ObjectContainer::const_iterator oit, oit_end = objects.end();
        for (oit = objects.begin(); oit != oit_end; ++ oit)
        {
                (*oit)->mVssRays.clear();
        }
}


void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects) const
{
        switch (mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                {
                        mOspTree->mOspStats.Stop();
                        break;
                }
        case BV_BASED_OBJ_SUBDIV:
                {
                        mBvHierarchy->mBvhStats.Stop();
                        RemoveRayRefs(objects);
                        break;
                }
        default:
                break;
        }
}


void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
{
        stream << "<BoundingBoxes>" << endl;
            
        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
        {
                KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();

                int id = 0;
                for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
                {
                        Intersectable *obj = (*kit).second;
                        const AxisAlignedBox3 box = obj->GetBox();
                
                        obj->SetId(id);

                        stream << "<BoundingBox" << " id=\"" << id << "\""
                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
                }
        }
        else
        {
                ObjectContainer::const_iterator oit, oit_end = objects.end();

                for (oit = objects.begin(); oit != oit_end; ++ oit)
                {
                        const AxisAlignedBox3 box = (*oit)->GetBox();
                
                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
                }
        }
                
        stream << "</BoundingBoxes>" << endl;
}

}