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

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

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


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);
                
        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 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};
        
        int mObjectSpaceSubdivisionType;
    int mViewSpaceSubdivisionType;

        /// the original osp type
        int mSavedObjectSpaceSubdivisionType;
        int mSavedViewSpaceSubdivisionType;

        int mConstructionType;

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

        AxisAlignedBox3 mBoundingBox;

        SplitQueue mTQueue;

        SubdivisionCandidate *mCurrentCandidate;

        ////////
        //-- global criteria
        float mTermMinGlobalCostRatio;
        int mTermGlobalCostMissTolerance;
        
        /// keeps track of cost during subdivision
        float mTotalCost;

        HierarchyStatistics mHierarchyStats;

        int mMinDepthForObjectSpaceSubdivion;
        int mMinDepthForViewSpaceSubdivion;

        int mTermMaxLeaves;
        ofstream mSubdivisionStats;

        bool mRepairQueue;

        bool mStartWithObjectSpace;

        bool mUseMultiLevelConstruction;
};

}

#endif