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

#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;
class ViewCellsParseHandlers;
class TraversalTree;
class ObjectPvs;


#define COUNT_ORIGIN_OBJECTS 1
#define USE_AVGRAYCONTRI 0

#define BOUND_RENDERCOST 0

static const float MIN_RENDERCOST = 100.0f;



/** View space / object space hierarchy statistics.
*/
class HierarchyStatistics: public StatisticsBase
{
public:
        /// total number of entries in the pvs
        int mPvsEntries;
        /// storage cost in MB
        float mMemory;
        /// total number of nodes
        int mNodes;
        /// maximal reached depth
        int mMaxDepth;
        /// accumulated depth
        int mAccumDepth;
        /// time spent for queue repair
        float mRepairTime;

        // global cost ratio violations
        int mGlobalCostMisses;
        /// total cost of subdivision
        float mTotalCost;
        /// render cost decrease of subdivision
        float mRenderCostDecrease;

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

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

        void Reset()
        {
                mGlobalCostMisses = 0;
                mTotalCost = 0;
                mRenderCostDecrease = 0;

                mNodes = 0;
                mMaxDepth = 0;
                mAccumDepth = 0;
                mRepairTime = 0;
                mMemory = 0;
                mPvsEntries = 0;
        }

        void Print(std::ostream &app) const;

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


class HierarchySubdivisionStats
{
public:
            
        int mNumSplits;
                
        float mRenderCostDecrease;

    float mTotalRenderCost;
    
        int mEntriesInPvs;
    
        float mMemoryCost;
        
        float mFullMemory;

        int mViewSpaceSplits;

        int mObjectSpaceSplits;

        float mPriority;

        float VspOspRatio() const { return (float)mViewSpaceSplits / (float)mObjectSpaceSplits; }

        float FpsPerMb() const { return 1.0f / (mTotalRenderCost * mMemoryCost); }

        HierarchySubdivisionStats() { Reset(); }

        void Reset()
        {
                mNumSplits = 0;
                mRenderCostDecrease = 0;
                mTotalRenderCost = 0;
                mEntriesInPvs = 0;
                mMemoryCost = 0;
                mFullMemory = 0;
                mViewSpaceSplits = 0;
                mObjectSpaceSplits = 0;
                mPriority = 0;
        }


        void Print(std::ostream &app) const;

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


/** 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 class VspOspViewCellsManager;

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);
        
        /** Print out statistics.
        */
        void PrintHierarchyStatistics(std::ostream &stream) const;

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

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

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

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

        /** Export object space partition bounding boxes.
        */
        void ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects);

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

        HierarchyStatistics &GetHierarchyStats() { return mHierarchyStats; };

        inline bool ConsiderMemory() const { return mConsiderMemory; }
        
        void EvaluateSubdivision(std::ofstream &splitsStats,
                                                          const int splitsStepSize,
                                                          const bool useFilter,
                                                          const bool useHisto,
                                                          const int histoMem,
                                                          const int pass);


        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);

        int CompressObjectSpace();
        void CreateUniqueObjectIds();

        float EvalCorrectedPvs(const float pvsFront, 
                                                   const float totalPvs,
                                                   const float raysPerObjects) const;


        /** Casts line segment into the view cells tree.
                @param origin the origin of the line segment
                @param termination the end point of the line segment
                @returns view cells intersecting the line segment.
        */
    int CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells,
                                                const bool useMailboxing = true);

#ifdef USE_SSE
        int CastLineSegment(RayPacket &packet);
#endif


protected:

        void PrintTimings(const bool osp);

        /** Returns true if the global termination criteria were met.
        */
        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;

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


        /** Create bounding box and root.
        */
        void InitialiseObjectSpaceSubdivision(const ObjectContainer &objects);

        /** Returns memory usage of object space hierarchy.
        */
        float GetObjectSpaceMemUsage() const;


        //////////////////////////////
        // the main loop

        /** This is for interleaved construction / sequential construction.
        */
        void RunConstruction(const bool repairQueue,
                                                 const VssRayContainer &sampleRays,
                                                 const ObjectContainer &objects,
                                                 AxisAlignedBox3 *forcedViewSpace);
        
        /** This is for interleaved construction using some objects 
                and some view space splits.
        */
        int RunConstruction(SplitQueue &splitQueue,
                                                SubdivisionCandidateContainer &chosenCandidates,
                                                //const float minRenderCostDecr,
                                                SubdivisionCandidate *oldCandidate,
                                                const int minSteps,
                                                const int maxSteps);

        /** Default subdivision method.
        */
        void RunConstruction(const bool repairQueue);
        
        
        ////////////////////////////////////////////////

        /** Evaluates the subdivision candidate and executes the split.
        */
        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc, 
                                                                   SplitQueue &splitQueue,
                                                                   //const bool repairQueue,
                                                                   std::vector<SubdivisionCandidate *> &dirtyList
                                                                   );

        /** Tests if hierarchy construction is finished.
        */
        bool FinishedConstruction() const;

        /** Returns next subdivision candidate from the split queue.
        */
        SubdivisionCandidate *NextSubdivisionCandidate(SplitQueue &splitQueue);

        /** Repairs the dirty entries of the subdivision candidate queue. The
                list of entries is given in the dirty list.

                @returns number of repaired candidates
        */
        int RepairQueue(const SubdivisionCandidateContainer &dirtyList, 
                                        SplitQueue &splitQueue,
                                        const bool recomputeSplitPlaneOnRepair);

        /** Collect subdivision candidates which were affected by the splits from the
                chosenCandidates list.
        */ 
        void CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates, 
                                                                SubdivisionCandidateContainer &dirtyList);

        /** Print subdivision stats for log.
        */
        void PrintSubdivisionStats();

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

        /** Collect affected view space candidates.
        */
        void CollectViewSpaceDirtyList(SubdivisionCandidate *sc,
                                                                   SubdivisionCandidateContainer &dirtyList);

        /** Collect affected object space candidates.
        */
        void CollectObjectSpaceDirtyList(SubdivisionCandidate *sc,
                                                                         SubdivisionCandidateContainer &dirtyList);
                
        /** Export object space partition tree.
        */
        void ExportOspTree(Exporter *exporter, 
                                           const ObjectContainer &objects) const;

        /** Parse the environment variables.
        */
        void ParseEnvironment();

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


        ////////////////////////////
        // Helper function for preparation of subdivision

        /** Prepare bv hierarchy for subdivision
        */
        void PrepareBvHierarchy(SplitQueue &tQueue,
                                                        const VssRayContainer &sampleRays,
                                                        const ObjectContainer &objects);

        /** Prepare object space kd tree for subdivision.
        */
        void PrepareOspTree(SplitQueue &tQueue,
                                                const VssRayContainer &sampleRays,
                                                const ObjectContainer &objects);

        /** Prepare view space subdivision and add candidate to queue.
        */
        void PrepareViewSpaceSubdivision(SplitQueue &tQueue,
                                                                         const VssRayContainer &sampleRays,
                                                                         const ObjectContainer &objects);

        /** Was object space subdivision already constructed?
        */
        bool ObjectSpaceSubdivisionConstructed() const;
        
        /** Was view space subdivision already constructed?
        */
        bool ViewSpaceSubdivisionConstructed() const;

        /** Reset the split queue, i.e., reevaluate the split candidates.
        */
    void ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane);

        /** After the suddivision has ended, do some final tasks.
        */
        void FinishObjectSpaceSubdivision(const ObjectContainer &objects, 
                                                                          const bool removeRayRefs = true) const;

        /** Returns depth of object space subdivision.
        */
        int GetObjectSpaceSubdivisionDepth() const;

        /** Returns number of leaves in object space subdivision.
        */
        int GetObjectSpaceSubdivisionLeaves() const;
        int GetObjectSpaceSubdivisionNodes() const;

        /** Construct object space partition interleaved with view space partition.
                Each time the best object or view space candidate is selected
                for the next split.
        */
        void ConstructInterleaved(const VssRayContainer &sampleRays,
                                                          const ObjectContainer &objects,
                                                          AxisAlignedBox3 *forcedViewSpace);

        /** Construct object space partition interleaved with view space partition.
                The method chooses a number candidates of each type for subdivision.
                The number is determined by the "gradient", i.e., the render cost decrease.
                Once this render cost decrease is lower than the render cost decrease
                for the splits of previous type, the method will stop current subdivision and
                evaluate if view space or object space would be the beneficial for the 
                next number of split.
        */
        void ConstructInterleavedWithGradient(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);

        /** Based on a given subdivision, we try to optimize using an
                multiple iteration over view and object space.
        */
        void OptimizeMultiLevel(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(SplitQueue &tQueue,
                                                                         const VssRayContainer &rays, 
                                                                         const ObjectContainer &objects);

        void ResetViewSpaceSubdivision(SplitQueue &tQueue,
                                                                   const VssRayContainer &rays, 
                                                                   const ObjectContainer &objects,
                                                                   AxisAlignedBox3 *forcedViewSpace);

        void CreateTraversalTree();

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

        void ExportStats(std::ofstream &stats, 
                                         SplitQueue &tQueue, 
                                         const ObjectContainer &objects);

        void CollectBestSet(const int maxSplits,
                                                const float maxMemoryCost,
                                                ViewCellContainer &viewCells,
                                                vector<BvhNode *> &bvhNodes);

        int ExtractStatistics(const int maxSplits,
                                                  const float maxMemoryCost,
                                                  float &renderCost,
                                                  float &memory,
                                                  int &pvsEntries,
                                                  int &viewSpaceSplits,
                                                  int &objectSpaceSplits,
                                                  const bool useFilter,
                                                  const bool useHisto,
                                                  const int histoMem,
                                                  const int pass,
                                                  bool &histoUsed);

        void ComputePvs(const ObjectPvs &pvs, float &triangles, int &pvsEntries);
        void GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const;
        void PullUpPvsIncrementally(ViewCell *viewCell) const;
        void GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const;
        void GetPvsEfficiently(ViewCell *vc, ObjectPvs &pvs) const;

        float EvalFullMem() const;

        ViewCellsManager *GetViewCellsManager();

protected:

        /** construction types
                sequential: construct first view space, then object space
                interleaved: construct view space and object space fully interleaved
                gradient: construct view space / object space until a threshold is reached
                multilevel: iterate until subdivisions converge to the optimum.
        */
        enum {SEQUENTIAL, INTERLEAVED, GRADIENT, MULTILEVEL};

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

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

        /// view space hierarchy
        VspTree *mVspTree;
        /// object space partition kd tree
        OspTree *mOspTree;

        float mInitialRenderCost;
        
        //float mMaxAvgRayContri;
        //float mMinAvgRayContri;

        float mMaxAvgRaysPerObject;
        float mMinAvgRaysPerObject;

        // quick hack:
public:
        /// bounding volume hierarchy
        BvHierarchy *mBvHierarchy;
        
        bool mUseTraversalTree;

        float mMinRenderCost;

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;
        /// Maximal allowed memory consumption.
        float mTermMaxMemory;


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

        /// number of minimal steps of the same type
        int mMinStepsOfSameType;
        int mMaxStepsOfSameType;

        /// statistics about the hierarchy
        HierarchyStatistics mHierarchyStats;

        int mMinDepthForObjectSpaceSubdivion;
        int mMinDepthForViewSpaceSubdivion;
        
        //int mMinRenderCostDecrease;

        std::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;

        /** if split plane should be recomputed for the repair.
                Otherwise only the priority is recomputed, the
                split plane itself stays the same
        */
        bool mRecomputeSplitPlaneOnRepair;

        /** If memory should be considered during choosing
                of the next split type during gradient method.
        */
        bool mConsiderMemory;

        TraversalTree *mTraversalTree;

        int mMaxRepairs;

        int mTimeStamp;
        friend VspTree;
        friend OspTree;
        friend BvHierarchy;

        float mPriority;

        friend ViewCellsParseHandlers;

        ViewCellContainer mOldViewCells;
};

}

#endif