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

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



/** View space / object space hierarchy statistics.
*/
class HierarchyStatistics: public StatisticsBase
{
public:
        /// total number of entries in the pvs
        int pvsEntries;
        /// storage cost
        int memory;
        /// total number of nodes
        int nodes;
        /// maximal reached depth
        int maxDepth;
        /// accumulated depth
        int accumDepth;
        /// time spent for queue repair
        float repairTime;
        // global cost ratio violations
        int mGlobalCostMisses;

        // 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()
        {
                mGlobalCostMisses = 0;
                nodes = 0;
                maxDepth = 0;
                accumDepth = 0;
                repairTime = 0;
                memory = 0;
                pvsEntries = 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 view space partition tree and
                the object space hierarchy type as argument.
        */
        HierarchyManager(const int objectSpaceHierarchyType);
        /** Hack: OspTree will copy the content from this kd tree.
                Only view space hierarchy will be constructed.
        */
        HierarchyManager(KdTree *kdTree);

        /** Deletes space partition and view space partition.
        */
        ~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);

        enum 
        {
                NO_OBJ_SUBDIV,
                KD_BASED_OBJ_SUBDIV,
                BV_BASED_OBJ_SUBDIV
        };

        enum 
        {
                NO_VIEWSPACE_SUBDIV,
                KD_BASED_VIEWSPACE_SUBDIV
        };

        /** The type of object space subdivison
        */
        int GetObjectSpaceSubdivisionType() const;      
        /** The type of view space space subdivison
        */
        int GetViewSpaceSubdivisionType() const;
        /** Sets a pointer to the view cells manager.
        */              
        void SetViewCellsManager(ViewCellsManager *vcm);
        /** Sets a pointer to the view cells tree.
        */
        void SetViewCellsTree(ViewCellsTree *vcTree);
        /** Exports the object hierarchy to disc.
        */
        void ExportObjectSpaceHierarchy(OUT_STREAM &stream);
        /** Adds a sample to the pvs of the specified view cell.
        */
        bool AddSampleToPvs(
                Intersectable *obj, 
                const Vector3 &hitPoint,
                ViewCell *vc,
                const float pdf, 
                float &contribution) const;

        /** Print out statistics.
        */
        void PrintHierarchyStatistics(ostream &stream) const;

        /** Returns the view space partition tree.
        */
        VspTree *GetVspTree();

        /** Returns view space bounding box.
        */
        //AxisAlignedBox3 GetViewSpaceBox() const;
        /** Returns object space bounding box.
        */
        AxisAlignedBox3 GetObjectSpaceBox() const;

        /** Exports object space hierarchy for visualization.
        */
        void ExportObjectSpaceHierarchy(
                Exporter *exporter, 
                const ObjectContainer &objects,
                const AxisAlignedBox3 *bbox,
                const bool exportBounds = true) const;

        /** Returns intersectable pierced by this ray.
        */
        Intersectable *GetIntersectable(
                const VssRay &ray, 
                const bool isTermination) const;

        friend ostream &operator<<(ostream &s, const HierarchyManager &hm) 
        {
                hm.PrintHierarchyStatistics(s);
                return s;
        } 

        void ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects);


protected:

        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;

        /** Prepare construction of the hierarchies, set parameters, compute
                first split candidates.
        */
        void PrepareObjectSpaceSubdivision(
                const VssRayContainer &sampleRays,
                const ObjectContainer &objects);

        void RunConstruction(
                const bool repairQueue,
                const VssRayContainer &sampleRays,
                const ObjectContainer &objects,
                AxisAlignedBox3 *forcedViewSpace);
        
        void RunConstruction(const bool repairQueue);
                
        /** Evaluates the subdivision candidate and executes the split.
        */
        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc, const bool repairQueue);

        bool FinishedConstruction() const;

        SubdivisionCandidate *NextSubdivisionCandidate();

        /** Repairs the dirty entries of the candidate queue.
        */
        void RepairQueue();

        /** Collect the list of dirty candidates after the current subdivision candidate
                split.
        */
        void CollectDirtyCandidates(vector<SubdivisionCandidate *> &dirtyList);

        /** Evaluate subdivision stats for log.
        */
        void EvalSubdivisionStats(const float renderCostDecr);

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

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

        bool StartObjectSpaceSubdivision() const;
        bool StartViewSpaceSubdivision() const;

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

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

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

        bool ObjectSpaceSubdivisionConstructed() const;
        bool ViewSpaceSubdivisionConstructed() const;

    void ResetQueue();

        void FinishObjectSpaceSubdivision(const ObjectContainer &objects) const;

        int GetObjectSpaceSubdivisionDepth() const;

        void ConstructInterleaved(
                const VssRayContainer &sampleRays,
                const ObjectContainer &objects,
                AxisAlignedBox3 *forcedViewSpace);

        /** Use iteration to construct the object space hierarchy.
        */
        void ConstructMultiLevel(
                const VssRayContainer &sampleRays,
                const ObjectContainer &objects,
                AxisAlignedBox3 *forcedViewSpace);

        /** Reset the object space subdivision. 
                E.g., deletes hierarchy and resets stats.
                so construction can be restarted.
        */
        void ResetObjectSpaceSubdivision(
                const VssRayContainer &rays, 
                const ObjectContainer &objects);

        void HierarchyManager::ResetViewSpaceSubdivision(
                const VssRayContainer &rays, 
                const ObjectContainer &objects);


protected:

        enum {SEQUENTIAL, INTERLEAVED};
        /// type of hierarchy construction
        int mConstructionType;

        /// Type of object space partition
        int mObjectSpaceSubdivisionType;
        /// Type of view space partition
    int mViewSpaceSubdivisionType;

        /// the traversal queue
        SplitQueue mTQueue;
        
        ////////////
        //-- helper variables
        
        // the original osp type
        int mSavedObjectSpaceSubdivisionType;
        // the original vsp type
        int mSavedViewSpaceSubdivisionType;
        /// the current subdivision candidate
        SubdivisionCandidate *mCurrentCandidate;


        ///////////////////
        // Hierarchies

        /// view space hierarchy
        VspTree *mVspTree;
        /// object space partition kd tree
        OspTree *mOspTree;
        public:
        /// bounding volume hierarchy
        BvHierarchy *mBvHierarchy;
        
protected:


        //////////
        //-- global termination criteria

        /// the mininal acceptable cost ratio for a split
        float mTermMinGlobalCostRatio;
        /// the threshold for global cost miss tolerance
        int mTermGlobalCostMissTolerance;
        /// maximum number of leaves
        int mTermMaxLeaves;

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

        /// keeps track of cost during subdivision
        float mTotalCost;
        /// statistics about the hierarchy
        HierarchyStatistics mHierarchyStats;

        int mMinDepthForObjectSpaceSubdivion;
        int mMinDepthForViewSpaceSubdivion;
        
        ofstream mSubdivisionStats;

        /// if the queue should be repaired after a subdivision steps
        bool mRepairQueue;

        bool mStartWithObjectSpace;
        /** if multi level construction method should be used
                where we iterate over both hierarchies until we
                converge to the optimum.
        */
        bool mUseMultiLevelConstruction;
        /// number of iteration steps for multilevel approach   
        int mNumMultiLevels;
};

}

#endif