source: GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.h @ 1288

#ifndef _HierarchyManager_H__
#define _HierarchyManager_H__

#include <stack>

#include "Mesh.h"
#include "Containers.h"
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "gzstream.h"
#include "SubdivisionCandidate.h"



namespace GtpVisibilityPreprocessor {

class ViewCellLeaf;
class OspTree;
class VspTree;
class Plane3;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;
class Environment;
class VspInterior;
class VspLeaf;
class VspNode;
class KdNode;
class KdInterior;
class KdLeaf;
class OspTree;
class KdIntersectable;
class KdTree;
class VspTree;
class KdTreeStatistics;
class BvHierarchy;
class Exporter;

#if 0
template <typename T> class GtPriority
{
public:
        bool operator() (const T c1, const T c2) const
        {
                //return false;
                return c1->GetPriority() < c2->GetPriority();
        }
};

typedef std::priority_queue<SubdivisionCandidate *, 
                                                        std::vector<SubdivisionCandidate *>, 
                                                        GtPriority<std::vector<SubdivisionCandidate *>::value_type> > SplitQueue;
#endif



/** View space partition statistics.
*/
class HierarchyStatistics: public StatisticsBase
{
public:

        /// total number of nodes
        int nodes;
                
        /// maximal reached depth
        int maxDepth;
        
        /// accumulated depth
        int accumDepth;

        // Constructor
        HierarchyStatistics() 
        {
                Reset();
        }

        int Nodes() const {return nodes;}
        int Interior() const { return nodes / 2; }
        int Leaves() const { return (nodes / 2) + 1; }
        
        // TODO: computation wrong
        double AvgDepth() const { return accumDepth / (double)Leaves();}
        

        void Reset() 
        {
                nodes = 0;
                maxDepth = 0;
                accumDepth = 0;
        }


        void Print(ostream &app) const;

        friend ostream &operator<<(ostream &s, const HierarchyStatistics &stat) 
        {
                stat.Print(s);
                return s;
        } 
};


typedef FlexibleHeap<SubdivisionCandidate *> SplitQueue;

/** This class implements a structure holding two different hierarchies,
        one for object space partitioning and one for view space partitioning.

        The object space and the view space are subdivided using a cost heuristics.
        If an object space split or a view space split is chosen is also evaluated
        based on the heuristics. 
        
        The view space heuristics is evaluated by weighting and adding the pvss of the back and
        front node of each specific split. unlike for the standalone method vspbsp tree,
        the pvs of an object would not be the pvs of single object but that of all objects
        which are contained in the same leaf of the object subdivision. This could be done
        by storing the pointer to the object space partition parent, which would allow access to all children.
        Another possibility is to include traced kd-cells in the ray casing process.

        Accordingly, the object space heuristics is evaluated by storing a pvs of view cells with each object.
        the contribution to an object to the pvs is the number of view cells it can be seen from.

        @note
        There is a potential efficiency problem involved in a sense that once a certain type
        of split is chosen for view space / object space, the candidates for the next split of 
        object space / view space must be reevaluated.
        
*/
class HierarchyManager
{
        friend VspTree;
        friend OspTree;
        friend BvHierarchy;
        friend ViewCellsParseHandlers;

public:
        /** Constructor with the object space hierarchy type as argument.
        */
        HierarchyManager(VspTree *vspTree, const int objectSpaceHierarchyType);
        /** Hack: OspTree will copy the content from this kd tree.
                Only view space hierarchy will be constructed.
        */
        HierarchyManager(VspTree *vspTree, KdTree *kdTree);

        ~HierarchyManager();

        /** Constructs the view space and object space subdivision from a given set of rays
                and a set of objects.
                @param sampleRays the set of sample rays the construction is based on
                @param objects the set of objects
        */
        void Construct(const VssRayContainer &sampleRays,
                                   const ObjectContainer &objects,
                                   AxisAlignedBox3 *forcedViewSpace);

        /** Constructs first view cells, then object space partition.
        */
        void Construct2(const VssRayContainer &sampleRays,
                                        const ObjectContainer &objects,
                                        AxisAlignedBox3 *forcedViewSpace);

        /** Constructs only vsp tree.
        */
        void Construct3(const VssRayContainer &sampleRays,
                                        const ObjectContainer &objects,
                                        AxisAlignedBox3 *forcedViewSpace);

        enum 
        {
                NO_OBJ_SUBDIV,
                KD_BASED_OBJ_SUBDIV,
                BV_BASED_OBJ_SUBDIV
        };

        /** The type of object space subdivison
        */
        inline int GetObjectSpaceSubdivisonType() const
        {
                return mObjectSpaceSubdivisonType;
        }
        
        void SetViewCellsManager(ViewCellsManager *vcm);

        void SetViewCellsTree(ViewCellsTree *vcTree);

        void ExportObjectSpaceHierarchy(OUT_STREAM &stream);

        bool AddSampleToPvs(
                Intersectable *obj, 
                const Vector3 &hitPoint,
                ViewCell *vc,
                const float pdf, 
                float &contribution) const;

        void PrintObjectSpaceHierarchyStatistics(ofstream &stream) const;

        VspTree *GetVspTree() { return mVspTree; }

        void ExportObjectSpaceHierarchy(
                Exporter *exporter, 
                const ObjectContainer &objects) const;


protected:

        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;

        /** Prepare construction of the hierarchies, set parameters, compute
                first split candidates.
        */
        void PrepareConstruction(
                const VssRayContainer &sampleRays,
                const ObjectContainer &objects,
                AxisAlignedBox3 *forcedViewSpace,
                RayInfoContainer &viewSpaceRays,
                RayInfoContainer &objectSpaceRays);

        void RunConstruction(const bool repair);
        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc);

        bool FinishedConstruction() const;

        SubdivisionCandidate *NextSubdivisionCandidate();

        void RepairQueue();

        void CollectDirtyCandidates(vector<SubdivisionCandidate *> &dirtyList);

        void EvalSubdivisionStats(const SubdivisionCandidate &tData);

        void AddSubdivisionStats(
                const int splits,
                const float renderCostDecr,
                const float totalRenderCost);

        void CollectObjectSpaceDirtyList();
        void CollectViewSpaceDirtyList();

        bool AddSampleToPvs(Intersectable *obj, 
                                                const float pdf,
                                                float &contribution) const;

        void CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
        void CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
                
        void ExportOspTree(Exporter *exporter, const ObjectContainer &objects) const;
        void ExportBvHierarchy(Exporter *exporter, const ObjectContainer &objects) const;


        void ConstructBvHierarchy(
                const VssRayContainer &sampleRays,
                const ObjectContainer &objects);

        void ConstructOspTree(
                const VssRayContainer &sampleRays,
                const ObjectContainer &objects);

        void ParseEnvironment();


protected:

        int mObjectSpaceSubdivisonType;

        VspTree *mVspTree;
        OspTree *mOspTree;
        BvHierarchy *mBvHierarchy;

        AxisAlignedBox3 mBoundingBox;

        SplitQueue mTQueue;

        SubdivisionCandidate *mCurrentCandidate;

        //-- global criteria
        float mTermMinGlobalCostRatio;
        int mTermGlobalCostMissTolerance;
        int mGlobalCostMisses;

        /// keeps track of cost during subdivision
        float mTotalCost;

        HierarchyStatistics mHierarchyStats;

        int mMaxLeaves;
        ofstream mSubdivisionStats;
};

}

#endif