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

#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, 
                                                                   const int objectSpaceSubdivisionType):
mObjectSpaceSubdivisonType(objectSpaceSubdivisionType),
mVspTree(vspTree), 
mOspTree(NULL), 
mBvHierarchy(NULL)
{
        switch(mObjectSpaceSubdivisonType)
        {
        case KD_BASED_OBJ_SUBDIV:
                mOspTree = new OspTree();
                mOspTree->mVspTree = mVspTree;
                //mOspTree->mHierarchyManager = this;
                Debug << "creating osp tree" << endl;
                break;
        case BV_BASED_OBJ_SUBDIV:
        mBvHierarchy = new BvHierarchy();
                mBvHierarchy->mVspTree = mVspTree;
                //mBvHierarchy->mHierarchyManager = this;
                Debug << "creating bv hierachy" << endl;
                break;
        default:
                break;
        }

        if (mVspTree)
                mVspTree->mHierarchyManager = this;

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


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

        //mOspTree->mHierarchyManager = this;
        Debug << "creating osp tree" << endl;

        if (mVspTree)
                mVspTree->mHierarchyManager = this;

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


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


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

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


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


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

        //////////////////////////
        // matt: only for debugging purpose

        const float rc = mOspTree->EvalRenderCost(sampleRays);

        Debug << "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);
        }
}


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


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

        switch (mObjectSpaceSubdivisonType)
        {
        case NO_OBJ_SUBDIV:
                // potentially visible objects
                return vc->AddPvsSample(obj, pdf, contribution);

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


void HierarchyManager::PrintObjectSpaceHierarchyStatistics(ofstream &stream) const
{
        switch (mObjectSpaceSubdivisonType)
        {
        case KD_BASED_OBJ_SUBDIV:
                {
                        stream << mOspTree->GetStatistics();
                        break;
                }
        case BV_BASED_OBJ_SUBDIV:
                {
                        stream << mBvHierarchy->GetStatistics();
                        break;
                }
        default:
                break;
        }
}


void HierarchyManager::ExportObjectSpaceHierarchyForViz(const ObjectContainer &objects) const
{
        if (mOspTree && mOspTree->GetRoot()) 
        {       
                //-- export final object partition
                Exporter *exporter = Exporter::GetExporter("final_object_partition.wrl");
                
                if (exporter)
                {
                        cout << "exporting object space partition ... ";

                        if (1)
                        {
                                exporter->ExportGeometry(objects);
                        }
                        
#if 0           
                        // export rays
                        exporter->ExportRays(visRays, RgbColor(0, 1, 0));
#endif

                        exporter->SetWireframe();
        
                        const int colorCode = 0;
                        const int maxPvs = 0;//mOspTree.GetStatistics().maxPvs;

                        exporter->ExportOspTree(*mOspTree, 0);

                        delete exporter;

                        cout << "finished" << endl;
                }
        }
}

}