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

#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 "KdIntersectable.h"
#include "VspTree.h"
#include "OspTree.h"
#include "BvHierarchy.h"


namespace GtpVisibilityPreprocessor {


#define USE_FIXEDPOINT_T 0


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


HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree)
//:mVspTree(vspTree), mOspTree(ospTree)
{
        char subdivisionStatsLog[100];
        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", 
                subdivisionStatsLog);
        mSubdivisionStats.open(subdivisionStatsLog);
}


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

        return splitCandidate;
}


void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
                                                                                   const ObjectContainer &objects,
                                                                                   AxisAlignedBox3 *forcedViewSpace,
                                                                                   RayInfoContainer &viewSpaceRays,
                                                                                   RayInfoContainer &objectSpaceRays)
{
        SubdivisionCandidate *vsc = 
                mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, viewSpaceRays);
        mTQueue.Push(vsc);

        SubdivisionCandidate *osc = 
                mOspTree->PrepareConstruction(sampleRays, objects, forcedViewSpace, objectSpaceRays);

        mTQueue.Push(osc);
}


void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
{
        const float costDecr = tData.GetRenderCostDecrease();

        //mTotalCost -= costDecr;
        //mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;

        AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
                                                costDecr,
                                                mTotalCost
                                                );
}


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


bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
{
        // TODO matt: make virtual by creating superclasss for traveral data
        return candidate->GlobalTerminationCriteriaMet();
}


void HierarchyManager::Construct(const VssRayContainer &sampleRays,
                                                                 const ObjectContainer &objects,
                                                                 AxisAlignedBox3 *forcedViewSpace)
{
        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
        RayInfoContainer *viewSpaceRays = new RayInfoContainer();

        // prepare vsp and osp trees for traversal
        PrepareConstruction(sampleRays, objects, forcedViewSpace, *viewSpaceRays, *objectSpaceRays);

        mVspTree->mVspStats.Reset();
        mVspTree->mVspStats.Start();

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

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

        mVspTree->mVspStats.Stop();
}


bool HierarchyManager::SubdivideSubdivisionCandidate(SubdivisionCandidate *sc)
{
        const bool globalTerminationCriteriaMet = 
                        GlobalTerminationCriteriaMet(sc);

        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);

        if (vspSplit)
        {
                VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
        }
        else
        {
                KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
        }
        
        return !globalTerminationCriteriaMet;
}


void HierarchyManager::RunConstruction(const bool repair)
{
        int numNodes = 0;

        while (!FinishedConstruction())
        {
                SubdivisionCandidate *splitCandidate = NextSubdivisionCandidate();
            
                mTotalCost -= splitCandidate->GetRenderCostDecrease();

                // cost ratio of cost decrease / totalCost
                const float costRatio = splitCandidate->GetRenderCostDecrease() / mTotalCost;

                if (costRatio < mTermMinGlobalCostRatio)
                        ++ mGlobalCostMisses;
        
                /*Debug << "\n**********" << endl
                          << "total cost: " << mTotalCost << " render cost decr: " 
                          << splitCandidate->GetRenderCostDecrease() 
                          << " cost ratio: " << costRatio << endl << endl;*/

                //-- subdivide leaf node

                if (SubdivideSubdivisionCandidate(splitCandidate))
                {
                        // subdivision successful
                        EvalSubdivisionStats(*splitCandidate);
                
                        // reevaluate candidates affected by the split
                        // for view space splits, this would be object space splits
                        // and other way round
                        if (repair)
                                RepairQueue();

                        cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
                }

                DEL_PTR(splitCandidate);
        }
}


void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
                                                                  const ObjectContainer &objects,
                                                                  AxisAlignedBox3 *forcedViewSpace)
{
        // rays clipped in view space and in object space
        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
        RayInfoContainer *objectSpaceRays = new RayInfoContainer();


        /////////////////////////////////////////////////////////////
        // view space space partition
        /////////////////////////////////////////////////////////////

#if 0
        // makes no sense otherwise because only one kd cell available
        // during view space partition
        const bool savedCountMethod = mVspTree.mUseKdPvsForHeuristics;
        const bool savedStoreMethod = mVspTree.mStoreObjectPvs;
        
        mVspTree.mUseKdPvsForHeuristics = false;
        mVspTree.mStoreObjectPvs = false;
#endif

        SubdivisionCandidate *vsc = 
                mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);

        // add to queue
        mTQueue.Push(vsc);

        long startTime = GetTime();
        cout << "starting vsp contruction ... " << endl;

        mVspTree->mVspStats.Reset();
        mVspTree->mVspStats.Start();

        int i = 0;

        // all objects can be seen from everywhere
        mTotalCost = (float)dynamic_cast<VspTree::VspSubdivisionCandidate *>(vsc)->mParentData.mPvs;

        const bool repairQueue = false;

        // process view space candidates
        RunConstruction(repairQueue);

        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
        mVspTree->mVspStats.Stop();


        /////////////////////////////////////////////////////////////
        // object space partition
        /////////////////////////////////////////////////////////////


        Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
        cout << "starting osp contruction ... " << endl;

        // 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, forcedViewSpace, *objectSpaceRays);

        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
        mTotalCost = mOspTree->mTotalCost;

    mTQueue.Push(osc);

        mOspTree->mOspStats.Reset();
        mOspTree->mOspStats.Start();

        startTime = GetTime();
        
        // process object space candidates
        RunConstruction(repairQueue);
        
        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        mOspTree->mOspStats.Stop();

        float rc = mOspTree->EvalRenderCost(sampleRays);

        Debug << "here47 My render cost evalulation: " << rc << endl;

#if 0
        // reset parameters
        mVspTree->mUseKdPvsForHeuristics = savedCountMethod;
        mVspTree->mStoreObjectPvs = savedStoreMethod;
#endif
}


void HierarchyManager::Construct3(const VssRayContainer &sampleRays,
                                                                  const ObjectContainer &objects,
                                                                  AxisAlignedBox3 *forcedViewSpace)
{
        // construct only view space partition
        // object kd tree is taken for osp

        mVspTree->mVspStats.Reset();
        mVspTree->mVspStats.Start();

        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
        
        SubdivisionCandidate *sc = 
                mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);

        mTQueue.Push(sc);

        cout << "starting vsp contruction ... " << endl;

        long startTime = GetTime();

        RunConstruction(false);

        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
        mVspTree->mVspStats.Stop();
}


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


void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
{
        switch (mObjectSpaceSubdivisonType)
        {
        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()
{
        // TODO
        // 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
        vector<SubdivisionCandidate *> dirtyList;
        CollectDirtyCandidates(dirtyList);
        
        //-- reevaluate the dirty list
        vector<SubdivisionCandidate *>::const_iterator sit, sit_end = dirtyList.end();

        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
        {
                SubdivisionCandidate* sc = *sit;

                mTQueue.Erase(sc);

                // reevaluate
                sc->EvalPriority();

                // reinsert
                mTQueue.Push(sc);
        }
}


}