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

#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"
#include "ViewCell.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 HierarchySubdivisionStats::Print(ostream &app) const
{
        app << "#Pass\n" << 0 << endl
                << "#Splits\n" << mNumSplits << endl 
                << "#TotalRenderCost\n" << mTotalRenderCost << endl
                << "#TotalEntriesInPvs\n" << mEntriesInPvs << endl
                << "#Memory\n" << mMemoryCost << endl
                << "#StepsView\n" << mViewSpaceSplits << endl
                << "#StepsObject\n" << mObjectSpaceSplits << endl
                << "#VspOspRatio\n" << VspOspRatio() << endl
                << "#FullMem\n" << mFullMemory << endl
                << "#RenderCostDecrease\n" << mRenderCostDecrease << endl
                << "#Priority\n" << mPriority << endl
                << "#FpsPerMb\n" << FpsPerMb() << endl
                << endl;
}


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

        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
        
        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Construction.maxStepsOfSameType", mMaxStepsOfSameType);

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

        Environment::GetSingleton()->GetBoolValue(
                "Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);

        Environment::GetSingleton()->GetBoolValue(
                "Hierarchy.Construction.considerMemory", mConsiderMemory);

        Environment::GetSingleton()->GetFloatValue(
                "Hierarchy.Termination.maxMemory", mTermMaxMemory);

        Environment::GetSingleton()->GetIntValue(
                "Hierarchy.Construction.maxRepairs", mMaxRepairs);

        // compare to bytes
        mTermMaxMemory *= (1024.0f * 1024.0f);

        Debug << "******** Hierarchy Manager Options ***********" << endl;
        Debug << "max leaves: " << mTermMaxLeaves << endl;
        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
        Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
        Debug << "repair queue: " << mRepairQueue << endl;
        Debug << "number of multilevels: " << mNumMultiLevels << endl;
        Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
        Debug << "minimal number of steps from same type: " << mMinStepsOfSameType << endl;
        Debug << "maximal allowed memory: " << mTermMaxMemory << endl;
        Debug << "consider memory: " << mConsiderMemory << endl;
        Debug << "min steps of same kind: " << mMinStepsOfSameType << endl;
        Debug << "max steps of same kind: " << mMaxStepsOfSameType << endl;
        Debug << "max repairs: " << mMaxRepairs << endl;

        switch (mConstructionType)
        {
        case 0:
                Debug << "construction type: sequential" << endl;
                break;
        case 1:
                Debug << "construction type: interleaved" << endl;
                break;
        case 2:
                Debug << "construction type: gradient" << endl;
                break;
        case 3:
                Debug << "construction type: multilevel" << endl;
                break;
        default:
                Debug << "construction type " << mConstructionType << " unknown" << endl;
                break;
        }

        //Debug << "min render cost " << mMinRenderCostDecrease << 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(SplitQueue &splitQueue)
{
        SubdivisionCandidate *splitCandidate = splitQueue.Top();
        splitQueue.Pop();

        // split was not reevaluated before => do it now
        if (splitCandidate->IsDirty())
                splitCandidate->EvalCandidate();

        return splitCandidate;
}


void HierarchyManager::EvalSubdivisionStats()
{
        // question: should I also add the mem usage of the hierarchies?
        const float objectSpaceMem = GetObjectSpaceMemUsage();
        const float viewSpaceMem = mVspTree->GetMemUsage();
                
        HierarchySubdivisionStats stats;

        stats.mNumSplits = mHierarchyStats.Leaves();
        stats.mTotalRenderCost = mHierarchyStats.mTotalCost;
        stats.mEntriesInPvs = mHierarchyStats.mPvsEntries;
        stats.mMemoryCost = mHierarchyStats.mMemory  / float(1024 * 1024);
        stats.mFullMemory = mHierarchyStats.mMemory  / float(1024 * 1024)
                                                + objectSpaceMem + viewSpaceMem;
        stats.mViewSpaceSplits = mVspTree->mVspStats.Leaves();
        stats.mObjectSpaceSplits = GetObjectSpaceSubdivisionLeaves();
        stats.mRenderCostDecrease = mHierarchyStats.mRenderCostDecrease;
        stats.mPriority = mPriority;

        stats.Print(mSubdivisionStats);
}


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


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

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

        return terminationCriteriaMet;
}


void HierarchyManager::Construct(const VssRayContainer &sampleRays,
                                                                 const ObjectContainer &objects,
                                                                 AxisAlignedBox3 *forcedViewSpace)
{
        mTimeStamp = 1;

        switch (mConstructionType)
        {
        case MULTILEVEL:
                ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
                break;
        case INTERLEAVED:
        case SEQUENTIAL:
                ConstructInterleaved(sampleRays, objects, forcedViewSpace);
                break;
        case GRADIENT:
                ConstructInterleavedWithGradient(sampleRays, objects, forcedViewSpace);
                break;
        default:
                break;
        }

        // hack: should be different parameter name
        if (mUseMultiLevelConstruction)
        {
                cout << "starting optimizing multilevel ... " << endl;
                // try to optimize on the above hierarchy
                OptimizeMultiLevel(sampleRays, objects, forcedViewSpace);
                
                cout << "finished" << endl;
        }
}


void HierarchyManager::ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
                                                                                                                const ObjectContainer &objects,
                                                                                                                AxisAlignedBox3 *forcedViewSpace)
{
        mHierarchyStats.Reset();
        mHierarchyStats.Start();
        
        mHierarchyStats.mNodes = 2;

        // create first nodes
        mVspTree->Initialise(sampleRays, forcedViewSpace);
        InitialiseObjectSpaceSubdivision(objects);

        // hack: assume that object space can be seen from view space
        mHierarchyStats.mTotalCost = mInitialRenderCost = (float)objects.size();
        // only one entry for start
        mHierarchyStats.mPvsEntries = 1;
        mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();

        EvalSubdivisionStats();
        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;

        const long startTime = GetTime();
        cout << "Constructing view space / object space tree ... \n";
        
        SplitQueue objectSpaceQueue;
        SplitQueue viewSpaceQueue;

        int vspSteps = 0, ospSteps = 0;

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

        // number of initial splits
        const int minSteps = mMinStepsOfSameType;
        const int maxSteps = mMaxStepsOfSameType;

        PrepareObjectSpaceSubdivision(objectSpaceQueue, sampleRays, objects);
        
        /////////////////////////
        // calulcate initial object space splits
        
        SubdivisionCandidateContainer dirtyList;

        // subdivide object space first
        // for first round, use sah splits. Once view space partition
        // has started, use render cost heuristics instead
        ospSteps = RunConstruction(objectSpaceQueue, 
                                                           dirtyList, 
                                                           NULL, 
                                                           minSteps, 
                                                           maxSteps);

        cout << "\n" << ospSteps << " object space partition steps taken" << endl;

        // create view space
        PrepareViewSpaceSubdivision(viewSpaceQueue, sampleRays, objects);

        dirtyList.clear();

        // view space subdivision started
        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

        if (1)
        {
                // rather also start with 100 view space splits to avoid initial bias.
                vspSteps = RunConstruction(viewSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
                cout << "\n" << vspSteps << " view space partition steps taken" << endl;
                
                /// Repair split queue
                cout << "repairing queue ... " << endl;
                RepairQueue(dirtyList, objectSpaceQueue, true);
                cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;

                dirtyList.clear();
        }
        else
        {
                // the priorities were calculated for driving sah.
                // => recalculate "real" priorities taking visibility into
                // account so we can compare to view space splits
                ResetQueue(objectSpaceQueue, false);
        }

        // This method subdivides view space / object space 
        // in order to converge to some optimal cost for this partition
        // start with object space partiton
        // then optimizate view space partition for the current osp
        // and vice versa until iteration depth is reached.

        bool lastSplitWasOsp = true;

        while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
        {
                // decide upon next split type
                const float vspPriority = viewSpaceQueue.Top() ? viewSpaceQueue.Top()->GetPriority() : -1e20f;
                const float ospPriority = objectSpaceQueue.Top() ? objectSpaceQueue.Top()->GetPriority() : -1e20f;
                
                cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;

                // should view or object space be subdivided further?
                if (ospPriority >= vspPriority)
                //if (!lastSplitWasOsp)
                {
                        lastSplitWasOsp = true;
                        cout << "osp" << endl;
                        
                        // dirtied view space candidates
                        SubdivisionCandidateContainer dirtyVspList;

                        // subdivide object space first for first round, 
                        // use sah splits. Once view space partition
                        // has started, use render cost heuristics instead
                        const int ospSteps = RunConstruction(objectSpaceQueue, 
                                                                                                 dirtyVspList, 
                                                                                                 viewSpaceQueue.Top(), 
                                                                                                 minSteps, 
                                                                                                 maxSteps);

                        cout << "\n" << ospSteps << " object space partition steps taken" << endl;
                        Debug << "\n" << ospSteps << " object space partition steps taken" << endl;

                        /// Repair split queue, i.e., affected view space candidates
                        cout << "repairing queue ... " << endl;
                        const int repaired = RepairQueue(dirtyVspList, viewSpaceQueue, true);
            
                        cout << "\nrepaired " << repaired << " candidates from " << (int)dirtyVspList.size() << " dirtied candidates" << endl;
                }
                else
                {
                        lastSplitWasOsp = false;
                        cout << "vsp" << endl;
                        
                        /////////////////
                        // subdivide view space with respect to the objects

                        // dirtied object space candidates
                        SubdivisionCandidateContainer dirtyOspList;

                        // process view space candidates
                        const int vspSteps = RunConstruction(viewSpaceQueue, 
                                                                                                 dirtyOspList, 
                                                                                                 objectSpaceQueue.Top(), 
                                                                                                 minSteps, 
                                                                                                 maxSteps);

                        cout << "\n" << vspSteps << " view space partition steps taken" << endl;
                        Debug << "\n" << vspSteps << " view space partition steps taken" << endl;

                        // view space subdivision constructed
                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

                        /// Repair split queue
                        cout << "repairing queue ... " << endl;
                        const int repaired = RepairQueue(dirtyOspList, objectSpaceQueue, true);

                        cout << "\nrepaired " << repaired << " candidates from " << (int)dirtyOspList.size() << " dirtied candidates" << endl;
                }
        }

        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        mHierarchyStats.Stop();
        mVspTree->mVspStats.Stop();

        FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
}


void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
                                                                                        const ObjectContainer &objects,
                                                                                        AxisAlignedBox3 *forcedViewSpace)
{
        mHierarchyStats.Reset();
        mHierarchyStats.Start();

        // two nodes for view space and object space
        mHierarchyStats.mNodes = 2; 
        mHierarchyStats.mPvsEntries = 1;
        mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
        mHierarchyStats.mTotalCost = (float)objects.size();

        mHierarchyStats.mRenderCostDecrease = 0;

        EvalSubdivisionStats();
        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;

        const long startTime = GetTime();
        cout << "Constructing view space / object space tree ... \n";
        
        // create only roots
        mVspTree->Initialise(sampleRays, forcedViewSpace);
        InitialiseObjectSpaceSubdivision(objects);

        // 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 view space subdivison immediately?
        if (StartViewSpaceSubdivision())
        {
                // prepare vsp tree for traversal
        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
                
                PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
        }
        
        // start object space subdivision immediately?
        if (StartObjectSpaceSubdivision())
        {
                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
                PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
        }

        // begin subdivision
        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, !mUseMultiLevelConstruction);
}


void HierarchyManager::PrepareViewSpaceSubdivision(SplitQueue &tQueue,
                                                                                                   const VssRayContainer &sampleRays,
                                                                                                   const ObjectContainer &objects)
{
        cout << "\npreparing view space hierarchy construction ... " << endl;

        // hack: reset global cost misses
        mHierarchyStats.mGlobalCostMisses = 0;

        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
        mVspTree->PrepareConstruction(tQueue, sampleRays, *viewSpaceRays);

        /////////
        //-- new stats

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


float HierarchyManager::GetObjectSpaceMemUsage() const
{
        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
        {
                // TODO;
        }
        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
        {
                return mBvHierarchy->GetMemUsage();
        }

        return -1;
}

void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
{
        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
        {
                // TODO;
        }
        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
        {
                mBvHierarchy->Initialise(objects);
        }
}


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

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


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

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

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

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


void HierarchyManager::PrepareOspTree(SplitQueue &tQueue,
                                                                          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
        mOspTree->PrepareConstruction(tQueue, sampleRays, objects, *objectSpaceRays);

        mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
        Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
}


bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc, 
                                                                                                 SplitQueue &splitQueue,
                                                                                                 const bool repairQueue)
{
        const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
        const bool success = sc->Apply(splitQueue, terminationCriteriaMet);

        if (sc->IsDirty())
                cerr << "Error: Should never come here!" << endl;

        if (!success) // split was not taken
        {
                cout << "x";
                return false;
        }

        //cout << "priority: " << sc->GetPriority() << " rc decr: " << sc->GetRenderCostDecrease() << " | ";
        ///////////////
        //-- split was successful => update stats and queue

    // cost ratio of cost decrease / totalCost
        const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
        //cout << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
        
        if (costRatio < mTermMinGlobalCostRatio)
        {
                ++ mHierarchyStats.mGlobalCostMisses;
        }
        
        cout << sc->Type() << " ";
                
        /////////////
        // update stats

        mHierarchyStats.mNodes += 2;
        mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();

        const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
        mHierarchyStats.mPvsEntries += pvsEntriesIncr;
        //cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;

        // memory size in byte
        mHierarchyStats.mMemory += (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
        mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
        
        mPriority = sc->GetPriority();

        static float memoryCount = 0;

        if (mHierarchyStats.mMemory > memoryCount)
        {
                memoryCount += 100000;
                cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024) 
                         << " MB, steps: " << mHierarchyStats.Leaves() << endl;
        }

        // output stats
        EvalSubdivisionStats();
                
        if (repairQueue) 
        {
                // reevaluate candidates affected by the split for view space splits, 
                // this would be object space splits and other way round
                vector<SubdivisionCandidate *> dirtyList;
                sc->CollectDirtyCandidates(dirtyList, false);

                RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
        }

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


int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
{
        int maxLeaves= 0;

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

        return maxLeaves;
}


int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
{
        int maxLeaves = 0;

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

        return maxLeaves;
}

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) && 
                 (mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
}


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) && 
                 (mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
}


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

                ApplySubdivisionCandidate(sc, mTQueue, 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 after " 
                                 << mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") steps, mem=" 
                                 << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;

                        PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
                        
                        cout << "reseting queue ... ";
                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
                        cout << "finished" << endl;
                }

                if (StartViewSpaceSubdivision())
                {
                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

                        cout << "\nstarting view space subdivision at " 
                                 << GetObjectSpaceSubdivisionLeaves() << " (" 
                                 << mMinStepsOfSameType << ") , mem=" 
                                 << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;

                        PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);

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

                DEL_PTR(sc);
        }
}


void HierarchyManager::RunConstruction(const bool repairQueue)
{
        // main loop
        while (!FinishedConstruction())
        {
                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);    
                
                ////////
                //-- subdivide leaf node of either type
        ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
                
                DEL_PTR(sc);
        }
}


int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
                                                                          SubdivisionCandidateContainer &dirtyCandidates,
                                                                          SubdivisionCandidate *oldCandidate,
                                                                          const int minSteps,
                                                                          const int maxSteps)
{
        if (minSteps >= maxSteps)
                cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;

        int steps = 0;
        SubdivisionCandidate::NewMail();

        // main loop
        while (!splitQueue.Empty())
        {
                const float priority = splitQueue.Top()->GetPriority();
                const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;

                // minimum slope reached
                if ((steps >= maxSteps) || ((priority < threshold) && !(steps < minSteps)))
                {
                        cout << "\nbreaking on " << priority << " smaller than " << threshold << endl;
                        break;
                }
                
                ////////
                //-- subdivide leaf node of either type

                SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue); 
                        
                const bool repairQueue = false;
                const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);

                if (success)
                {
                        sc->CollectDirtyCandidates(dirtyCandidates, true);
                        ++ steps;
                }

                DEL_PTR(sc);
        }

        return steps;
}


void HierarchyManager::ResetObjectSpaceSubdivision(SplitQueue &tQueue,
                                                                                                   const VssRayContainer &sampleRays, 
                                                                                                   const ObjectContainer &objects)
{       
        SubdivisionCandidate *firstCandidate;

        // 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;
                                
                        // rather use this: remove previous nodes and add the two new ones
                        //mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
                        mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
                        
                        // create root
                        mBvHierarchy->Initialise(objects);
        
                        mBvHierarchy->Reset(tQueue, sampleRays, objects);

                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
                        
                        //mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
                        mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);

                        mHierarchyStats.mMemory = 
                                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();

                        mHierarchyStats.mRenderCostDecrease = 0;

                        // evaluate stats before first subdivision
                        EvalSubdivisionStats();
                        cout << "finished bv hierarchy preparation" << endl;
                }
                break;

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


void HierarchyManager::ResetViewSpaceSubdivision(SplitQueue &tQueue,
                                                                                                 const VssRayContainer &sampleRays, 
                                                                                                 const ObjectContainer &objects,
                                                                                                 AxisAlignedBox3 *forcedViewSpace)
{
        ViewCellsManager *vm = mVspTree->mViewCellsManager;

        // HACK: rather not destroy vsp tree
        DEL_PTR(mVspTree);
        mVspTree = new VspTree();

        mVspTree->mHierarchyManager = this;
        mVspTree->mViewCellsManager = vm;

        mVspTree->Initialise(sampleRays, forcedViewSpace);
        
        //////////
        //-- reset stats
    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();
                //-mVspTree->mVspStats.nodes + 1;
        
        PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
        
        mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
        mHierarchyStats.mRenderCostDecrease = 0;

        mHierarchyStats.mMemory = 
                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();

        // evaluate new stats before first subdivsiion
        EvalSubdivisionStats();
}


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

        const long startTime = GetTime();
        cout << "Constructing view space / object space tree ... \n";
        
        // initialise view / object space
        mVspTree->Initialise(sampleRays, forcedViewSpace);
        InitialiseObjectSpaceSubdivision(objects);

        // use sah for evaluating osp tree construction 
        // in the first iteration of the subdivision

        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;

        PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);

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


        const int limit = mNumMultiLevels;
        int i = 0;

        // This method subdivides view space / object space 
        // in order to converge to some optimal cost for this partition
        // 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);

                // subdivide object space first
                ResetObjectSpaceSubdivision(mTQueue, 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(mTQueue, sampleRays, objects, forcedViewSpace);
                
                // view space subdivision constructed
                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
                
                // process view space candidates
                RunConstruction(false);

                cout << "iteration " << i << " of " << limit << " finished" << endl;
                mSubdivisionStats.close();

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

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


void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                     
                                                                                  const ObjectContainer &objects,
                                                                                  AxisAlignedBox3 *forcedViewSpace)
{
        const long startTime = GetTime();
        const int limit = mNumMultiLevels;

        // open up new subdivision
        mSubdivisionStats.close();

        int steps = 0;

        int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
        int maxObjectSpaceLeaves;
        
        // set the number of leaves 'evaluated' from the previous methods
        // we go for the same numbers, but we try to optimize both subdivisions
        switch (mObjectSpaceSubdivisionType)
        {
        case BV_BASED_OBJ_SUBDIV:
                maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
                break;
        case KD_BASED_OBJ_SUBDIV:
                maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
        default:
                maxObjectSpaceLeaves = 0;
                break;
        }

        // This method subdivides view space / object space 
        // in order to converge to some optimal cost for this partition
        // 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", steps);
                mSubdivisionStats.open(subdivisionStatsLog);

                // subdivide object space first
                ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
        
                // set the number of leaves 'evaluated' from the previous methods
                // we go for the same numbers, but we try to optimize both subdivisions
                mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;

                // process object space candidates
                RunConstruction(false);

                cout << "iteration " << steps << " of " << limit << " finished" << endl;
                mSubdivisionStats.close();

                if ((++ steps) >= limit)
                        break;

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

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

                ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);

                mVspTree->mMaxViewCells = maxViewSpaceLeaves;

                // process view space candidates
                RunConstruction(false);

                cout << "iteration " << steps << " of " << limit << " finished" << endl;
                mSubdivisionStats.close();

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

        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;
        }*/
        return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
}


bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
{
        return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
        //return mVspTree && mVspTree->GetRoot();
}


void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates, 
                                                                                          SubdivisionCandidateContainer &dirtyList)
{
        SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
        SubdivisionCandidate::NewMail();

        for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
        {
                (*sit)->CollectDirtyCandidates(dirtyList, true);
        }
}


int HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
                                                                  SplitQueue &splitQueue,
                                                                  const bool recomputeSplitPlaneOnRepair)
{
        // 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

        int repaired = 0;

        // collect list of "dirty" candidates
        const long startTime = GetTime();
        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";

        const float prop = (float)mMaxRepairs / (float)dirtyList.size();

        ///////////////////////////
        //-- reevaluate the dirty list

        SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
        
        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
        {
                // only repair a certain number of candidates
                if ((mMaxRepairs < (int)dirtyList.size()) && (Random(1.0f) >= prop))
                        continue;

                SubdivisionCandidate* sc = *sit;
                const float rcd = sc->GetRenderCostDecrease();
                
                // erase from queue
                splitQueue.Erase(sc);
                // reevaluate candidate
                sc->EvalCandidate(recomputeSplitPlaneOnRepair);
                 // reinsert
                splitQueue.Push(sc);
                
                ++ repaired;
                cout << ".";

#ifdef GTP_DEBUG
                Debug << "candidate " << sc << " reevaluated\n" 
                          << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
#endif  
        }

        const long endTime = GetTime();
        const Real timeDiff = TimeDiff(startTime, endTime);

        mHierarchyStats.mRepairTime += timeDiff;

        return repaired;
}


void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
{
        SubdivisionCandidateContainer mCandidateBuffer;

        // remove from queue
        while (!splitQueue.Empty())
        {
                SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
                
                // reevaluate local split plane and priority
                candidate->EvalCandidate(recomputeSplitPlane);
                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)
        {
                splitQueue.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;
        }
}


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,
                                                                                                  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(Intersectable *obj,
                                                                                                  const Vector3 &point) const
{

        if (!obj)
                return NULL;

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

Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray, 
                                                                                                  const bool isTermination) const
{
        Intersectable *obj = NULL;
        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 leaf;
                }
        default:
                break;
        }

        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" << mRepairTime * 1e-3f << " \n";

        app << "#N_NODES ( Number of nodes )\n" << mNodes << "\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" << mMaxDepth << 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)->DelRayRefs();
        }
}


void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects, 
                                                                                                        const bool removeRayRefs) const
{
        switch (mObjectSpaceSubdivisionType)
        {
        case KD_BASED_OBJ_SUBDIV:
                {
                        mOspTree->mOspStats.Stop();
                        break;
                }
        case BV_BASED_OBJ_SUBDIV:
                {
                        mBvHierarchy->mBvhStats.Stop();
                        if (removeRayRefs)
                                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;
}


class HierarchyNodeWrapper;


template <typename T> class myless
{
public:
        bool operator() (T v1, T v2) const
        {
                return (v1->GetMergeCost() < v2->GetMergeCost());
        }
};


typedef priority_queue<HierarchyNodeWrapper *, vector<HierarchyNodeWrapper *>, 
                                           myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;

class HierarchyNodeWrapper
{
public:
        enum {VSP_NODE, BVH_NODE, VIEW_CELL};

        virtual float GetMergeCost() const = 0;
        virtual int Type() const  = 0;
        virtual bool IsLeaf() const = 0;

        virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
};


class VspNodeWrapper: public HierarchyNodeWrapper
{
public:
        VspNodeWrapper(VspNode *node): mNode(node) {}

        int Type() const { return VSP_NODE; }

        float GetMergeCost() const { return (float) -mNode->mTimeStamp; };

        bool IsLeaf() const { return mNode->IsLeaf(); }

        void PushChildren(HierarchyNodeQueue &tQueue)
        {
                if (!mNode->IsLeaf())
                {
                        VspInterior *interior = dynamic_cast<VspInterior *>(mNode);

                        tQueue.push(new VspNodeWrapper(interior->GetFront()));
                        tQueue.push(new VspNodeWrapper(interior->GetBack()));
                }
        }

        VspNode *mNode;
};


class BvhNodeWrapper: public HierarchyNodeWrapper
{
public:
        BvhNodeWrapper(BvhNode *node): mNode(node) {}
        
        int Type()  const { return BVH_NODE; }

        float GetMergeCost() const { return (float)-mNode->GetTimeStamp(); };

        bool IsLeaf() const { return mNode->IsLeaf(); }

        void PushChildren(HierarchyNodeQueue &tQueue)
        {
                if (!mNode->IsLeaf())
                {
                        BvhInterior *interior = dynamic_cast<BvhInterior *>(mNode);

                        tQueue.push(new BvhNodeWrapper(interior->GetFront()));
                        tQueue.push(new BvhNodeWrapper(interior->GetBack()));
                }
        }

        BvhNode *mNode;
};


class ViewCellWrapper: public HierarchyNodeWrapper
{
public:

        ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
        
        int Type()  const { return VIEW_CELL; }

        float GetMergeCost() const { return mViewCell->GetMergeCost(); };

        bool IsLeaf() const { return mViewCell->IsLeaf(); }

        void PushChildren(HierarchyNodeQueue &tQueue)
        {
                if (!mViewCell->IsLeaf())
                {
                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(mViewCell);

                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();

                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
                        {
                                tQueue.push(new ViewCellWrapper(*it));
                        }
                }
        }

        ViewCell *mViewCell;
};


void HierarchyManager::CollectBestSet(const int maxSplits,
                                                                          const float maxMemoryCost,
                                                                          ViewCellContainer &viewCells,
                                                                          vector<BvhNode *> &bvhNodes)
{
        HierarchyNodeQueue tqueue;
        //tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
        tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
        tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
        
        float memCost = 0;

        while (!tqueue.empty())
        {
                HierarchyNodeWrapper *nodeWrapper = tqueue.top();
                tqueue.pop();
                //cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
                // save the view cells if it is a leaf or if enough view cells have already been traversed
                // because of the priority queue, this will be the optimal set of v
                if (nodeWrapper->IsLeaf() || 
                        ((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) ||
                        (memCost > maxMemoryCost)
                        )
                {
                        if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
                        {
                                //cout << "1";
                                ViewCellWrapper *viewCellWrapper = dynamic_cast<ViewCellWrapper *>(nodeWrapper);
                                viewCells.push_back(viewCellWrapper->mViewCell);
                        }
                        else
                        {
                                //cout << "0";
                                BvhNodeWrapper *bvhNodeWrapper = dynamic_cast<BvhNodeWrapper *>(nodeWrapper);
                                bvhNodes.push_back(bvhNodeWrapper->mNode);
                        }
                }
                else 
                {       
                        nodeWrapper->PushChildren(tqueue);
                }

                delete nodeWrapper;
        }
}


void HierarchyManager::ComputePvs(const ObjectPvs &pvs, float &rc, int &pvsEntries)
{
        BvhNode::NewMail();

        ObjectPvsIterator pit = pvs.GetIterator();

        while (pit.HasMoreEntries())
        {
                ObjectPvsEntry entry = pit.Next();

                BvhNode *activeNode;
                BvhNode *intersect = dynamic_cast<BvhNode *>(entry.mObject);

                // hack for choosing which node to account for
                if (intersect->IsLeaf())
                        activeNode = dynamic_cast<BvhLeaf *>(intersect)->GetActiveNode();
                else
                        activeNode = intersect;

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

                        ObjectContainer objects;
                        activeNode->CollectObjects(objects);

                        ++ pvsEntries;
                        rc += mBvHierarchy->EvalAbsCost(objects);
                }
        }
}


// TODO matt: implement this function for different storing methods
void HierarchyManager::GetPvsIncrementally(ViewCell *vc, ObjectPvs &pvs) const
{
        ////////////////
        //-- pvs is not stored with the interiors => reconstruct
        ViewCell *root = vc;
        
        // add pvs from leaves
        stack<ViewCell *> tstack;
        tstack.push(vc);

        while (!tstack.empty())
        {
                vc = tstack.top();
                tstack.pop();
        
                // add newly found pvs to merged pvs: break here even for interior
                if (!vc->GetPvs().Empty())
                {
                        pvs.MergeInPlace(vc->GetPvs());
                }
                else if (!vc->IsLeaf()) // interior cells: go down to leaf level
                {
                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();

                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
                        {
                                tstack.push(*it);
                        }               
                }
        }
}

int HierarchyManager::ExtractStatistics(const int maxSplits,
                                                                                const float maxMemoryCost,
                                                                                float &renderCost,
                                                                                float &memory,
                                                                                int &pvsEntries,
                                                                                int &viewSpaceSplits,
                                                                                int &objectSpaceSplits,
                                                                                const bool useFilter)
{
        ViewCellContainer viewCells;
        vector<BvhNode *> bvhNodes;

        // collect best set of view cells for this #splits
    CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
        vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
        
        // set new nodes to be active
        for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
        {
                mBvHierarchy->SetActive(*bit);
        }

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

        pvsEntries = 0;
        renderCost = 0.0f;

        ViewCell::NewMail();

        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
        {
                ViewCell *vc = *vit;

                float rc = 0;
        ObjectPvs pvs;
                
                //mVspTree->mViewCellsTree->GetPvs(vc, pvs);
                GetPvsIncrementally(vc, pvs);
                
                vc->SetPvs(pvs);

                vc->Mail();

                if (useFilter)
                {
                        ObjectPvs filteredPvs;
                        mVspTree->mViewCellsManager->ApplyFilter2(vc, false, 1.0f, filteredPvs);
                        ComputePvs(filteredPvs, rc, pvsEntries);
                }
                else
                {
                        ComputePvs(pvs, rc, pvsEntries);
                }

                rc *= vc->GetVolume();
                renderCost += rc;
        }

        renderCost /= mVspTree->mViewCellsManager->GetViewSpaceBox().GetVolume();
        memory = pvsEntries * ObjectPvs::GetEntrySize();

        viewSpaceSplits = (int)viewCells.size();
        objectSpaceSplits = (int)bvhNodes.size();
        //cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;

        // delete old "base" view cells if they are not leaves
        ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();

        for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
        {
                if (!(*oit)->Mailed() && !(*oit)->IsLeaf())
                {
                        (*oit)->GetPvs().Clear();
                }
        }

        mOldViewCells = viewCells;

        return (int)(viewCells.size() + bvhNodes.size());
}


void HierarchyManager::ExportStats(ofstream &stats, 
                                                                   SplitQueue &tQueue, 
                                                                   const ObjectContainer &objects)
{
        HierarchySubdivisionStats subStats;
        subStats.Reset();

        /////////////
        //-- initial situation

        subStats.mNumSplits = 0;
        subStats.mTotalRenderCost = (float)objects.size();
        subStats.mEntriesInPvs = 1;
        subStats.mMemoryCost = (float)ObjectPvs::GetEntrySize();
        subStats.mFullMemory = subStats.mMemoryCost;
        subStats.mViewSpaceSplits = 0;
        subStats.mObjectSpaceSplits = 0;
        subStats.mRenderCostDecrease = 0;
        subStats.Print(stats);

        cout << "exporting vsposp stats ... " << endl;

        //-- go through tree in the order of render cost decrease
        //-- which is the same order as the view cells were merged
        //-- or the reverse order of subdivision for subdivision-only 
        //-- view cell hierarchies.
        
        while (!tQueue.Empty())
        {
                SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
                bool isLeaf;
                int timeStamp;
                float rcDecr; 
                int entriesIncr; 

        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
                {
                        timeStamp = (int)-nextCandidate->GetPriority();

                        VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
                        VspNode *oldNode = (VspNode *)nextCandidate->mEvaluationHack;
                        
                        isLeaf = newNode->IsLeaf();
                        //subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
                        //entriesIncr = oldNode->mPvsEntriesIncr;
                }
                else
                {
                        timeStamp = (int)-nextCandidate->GetPriority();
                        
                        BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
                        BvhNode *oldNode = (BvhNode *)nextCandidate->mEvaluationHack;
                        
                        isLeaf = newNode->IsLeaf();
                        //subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
                        //entriesIncr = oldNode->mPvsEntriesIncr;
                }               
                                
                if (!isLeaf)
                {
                        subStats.mTotalRenderCost -= subStats.mRenderCostDecrease;
                        //subStats.mEntriesInPvs += entriesIncr;

                        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
                        {
                                ++ subStats.mViewSpaceSplits;
                                cout << "v";
                                //cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
                        }
                        else
                        {
                                ++ subStats.mObjectSpaceSplits;
                                cout << "o";
                                //"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
                        }

                        ++ subStats.mNumSplits;

                        if ((subStats.mNumSplits % 500) == 499)
                                cout << subStats.mNumSplits << " steps taken" << endl;

                        subStats.mMemoryCost = (float)subStats.mEntriesInPvs * (float)ObjectPvs::GetEntrySize();
                        subStats.mFullMemory = subStats.mMemoryCost;

                        subStats.Print(stats);
                        
                }

                DEL_PTR(nextCandidate);
        }

        stats.close();
}


void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,
                                                                                   const ObjectContainer &objects,
                                                                                   const string &filename)
{
#if 0
        VspTree *oldVspTree = mVspTree;
        ViewCellsManager *vm = mVspTree->mViewCellsManager;
        BvHierarchy *oldHierarchy = mBvHierarchy;

        mBvHierarchy = new BvHierarchy();
        mBvHierarchy->mHierarchyManager = this;
        mBvHierarchy->mViewCellsManager = vm;

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

        // create first nodes
        mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
        InitialiseObjectSpaceSubdivision(objects);

        const long startTime = GetTime();
        cout << "Constructing evaluation hierarchies ... \n";
        
        ofstream stats;
        stats.open(filename.c_str());
        SplitQueue tQueue;

        BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
        VspNode *oldVspRoot = oldVspTree->GetRoot();

        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
        
        SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
        mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);

    firstVsp->mEvaluationHack = oldVspRoot;
        firstBvh->mEvaluationHack = oldBvhRoot;

        firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
        firstBvh->SetPriority((float)-oldBvhRoot->GetTimeStamp());

        tQueue.Push(firstVsp);
        
        ExportStats(stats, tQueue, objects);

        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
        RemoveRayRefs(objects);

        // view cells needed only for evaluation
        ViewCellContainer viewCells;
        mVspTree->CollectViewCells(viewCells, false);
        
        // helper trees can be destroyed
        DEL_PTR(mVspTree);
        DEL_PTR(mBvHierarchy);

        CLEAR_CONTAINER(viewCells);

        // reset hierarchies
        mVspTree = oldVspTree;
        mBvHierarchy = oldHierarchy;

        // reinstall old bv refs
        vector<BvhLeaf *> leaves;
        mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), leaves);
        vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();

        for (bit = leaves.begin(); bit != bit_end; ++ bit)
        {
                mBvHierarchy->AssociateObjectsWithLeaf(*bit);
        }
#endif
}


void HierarchyManager::EvaluateSubdivision2(ofstream &splitsStats,
                                                                                        const int splitsStepSize,
                                                                                        const bool useFilter)
{
        vector<HierarchySubdivisionStats> subStatsContainer;

        int splits = (1 + mHierarchyStats.Leaves() / splitsStepSize) * splitsStepSize;
        cout << "splits: " << splits << endl;

        while (1)
        {
                HierarchySubdivisionStats subStats;
                subStats.mNumSplits = ExtractStatistics(splits, 
                                                                                                99999.0, 
                                                                                                subStats.mTotalRenderCost, 
                                                                                                subStats.mMemoryCost, 
                                                                                                subStats.mEntriesInPvs,
                                                                                                subStats.mViewSpaceSplits,
                                                                                                subStats.mObjectSpaceSplits,
                                                                                                useFilter);

                
                const float objectSpaceHierarchyMem = float(
                                                                                          subStats.mObjectSpaceSplits * mBvHierarchy->mMemoryConst//sizeof(ObjectContainer)
                                                                                          //+ (subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior)
                                                                                          //+sizeof(BvHierarchy)
                                                                                          ) / float(1024 * 1024);

                        
                const float viewSpaceHierarchyMem = float(
                                                                                        subStats.mViewSpaceSplits * mVspTree->mMemoryConst//sizeof(ObjectPvs)
                                                                                        //+ (subStats.mViewSpaceSplits - 1) * sizeof(VspInterior)
                                                                                        + sizeof(ObjectPvs)
                                                                                        //+ sizeof(VspTree)
                                                                                        )  / float(1024 * 1024);

                subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
                
                subStatsContainer.push_back(subStats);
                
                if (splits == 0)
                        break;

                splits -= splitsStepSize;

                cout << subStats.mNumSplits << " ";
        }

        vector<HierarchySubdivisionStats>::const_reverse_iterator hit, hit_end = subStatsContainer.rend();

        for (hit = subStatsContainer.rbegin(); hit != hit_end; ++ hit)
        {
                (*hit).Print(splitsStats);
        }

        // delete old "base" view cells: only pvss in the leaves are allowed
        ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
        for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
        {
                if (!(*oit)->IsLeaf())
                {
                        (*oit)->GetPvs().Clear();
                }
        }

        mOldViewCells.clear();

        // reset active nodes
        vector<BvhLeaf *> bvhLeaves;

        mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), bvhLeaves);

        vector<BvhLeaf *>::const_iterator bit, bit_end = bvhLeaves.end();

        for (bit = bvhLeaves.begin(); bit != bit_end; ++ bit)
        {
                (*bit)->SetActiveNode(*bit);
        }

        cout << endl;
}


void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
{
        mBvHierarchy->CollectObjects(box, objects);
}

}