source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h @ 582

#ifndef _ViewCell_H__
#define _ViewCell_H__

#include "Mesh.h"
#include "Containers.h"
#include "Ray.h"
#include "Statistics.h"
//namespace GtpVisibilityPreprocessor {

struct Triangle3;

class BspInterior;
class BspPvs;
class BspLeaf;
class VspKdTree;
class VspKdLeaf;
class KdLeaf;
class ViewCellInterior;
class MergeCandidate;
class ViewCellsManager;

/** Statistics for a view cell partition.
*/

class ViewCellsStatistics: public StatisticsBase
{
public:

        /// number of view cells
        int viewCells;

        /// size of the PVS
        int pvs;

        /// largest PVS of all view cells
        int maxPvs;

        /// smallest PVS of all view cells
        int minPvs;

        /// view cells with empty PVS
        int emptyPvs;

        /// number of leaves covering the view space
        int leaves;

        /// largest number of leaves covered by one view cell
        int maxLeaves;

        int invalid;

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

        double AvgLeaves() const {return (double)leaves / (double)viewCells;};
        double AvgPvs() const {return (double)pvs / (double)viewCells;};

        void Reset()
        {
                viewCells = 0;
                pvs = 0;
                maxPvs = 0;

                minPvs = 999999;
                emptyPvs = 0;
                leaves = 0;
                maxLeaves = 0;
                invalid = 0;
        }

        void Print(ostream &app) const;

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


/**
        View cell with an optional mesh representation
*/


class ViewCell: public MeshInstance
{
public:
        ViewCell();

        /** Constructor taking a mesh representing the shape of the viewcell.
        */
        ViewCell(Mesh *mesh);

        /** Default destructor.
        */
        virtual ~ViewCell() {}

        /** Returns Pvs.
        */
        const ObjectPvs &GetPvs() const;
        ObjectPvs &GetPvs();

        int Type() const;

        void SetParent(ViewCellInterior *parent);

        /** Adds a passing ray to the passing ray container.
        */
        void AddPassingRay(const Ray &ray, const int contributions);

        /** Returns volume of the view cell.
        */
        float GetVolume() const;

        /** Returns area of the view cell.
        */
        float GetArea() const;

        /** Sets the volume of the view cell.
        */
        void SetVolume(float volume);
        
        /** Sets the area of the view cell.
        */
        void SetArea(float area);

        /** Updates the view cell statstics for this particular view cell.
        */
        virtual void UpdateViewCellsStats(ViewCellsStatistics &vcStat);

        /** if this view cell is the root of a view cell hierarchy
        */
        bool IsRoot() const;

        /** Returns parent view cell.
        */
        ViewCellInterior *GetParent() const;

        
        /** Sets the mesh for this view cell.
        */
        void SetMesh(Mesh *mesh);

        void SetValid(const bool valid);
        bool GetValid() const;




        /// parent view cell in the view cell hierarchy
        ViewCellInterior *mParent;

        /// Rays piercing this view cell.
        RayContainer mPiercingRays;


        /** if this is a view cell correspending to a leaf in a hierarchy.
        */
        virtual bool IsLeaf() const = 0;

  static bool SmallerPvs(const ViewCell *a,
                                                 const ViewCell *b) {
        return a->GetPvs().GetSize() < b->GetPvs().GetSize();
  }


        void SetTimeStamp(const int timeStamp);
        int GetTimeStamp() const;
        static void NewMail(const int reserve = 1) {
                sMailId += sReservedMailboxes;
                sReservedMailboxes = reserve;
        }
        void Mail() { mMailbox = sMailId; }
        bool Mailed() const { return mMailbox == sMailId; }

        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }

        int IncMail() { return ++mMailbox - sMailId; }


                                                 
        // last mail id -> warning not thread safe!
        // both mailId and mailbox should be unique for each thread!!!
        static int sMailId;
        static int sReservedMailboxes;
        

protected:

        /// the potentially visible objects
        ObjectPvs mPvs;

        float mVolume;
        float mArea;

        int mTimeStamp;

        bool mValid;
};


class ViewCellInterior: public ViewCell
{
public:
        ViewCellInterior();
        ~ViewCellInterior();

        ViewCellInterior(Mesh *mesh);
        

        /** Sets pointer from parent to child and vice versa.
        */
        void SetupChildLink(ViewCell *l);
        bool IsLeaf() const;

        ViewCellContainer mChildren;

};

/**
        View cell belonging to a hierarchy.
*/
template<typename T>
class ViewCellLeaf: public ViewCell
{
public:

        ViewCellLeaf<T>(): mLeaf(NULL) {}
        ViewCellLeaf<T>(Mesh *mesh):
                ViewCell(mesh), mLeaf(NULL) {}

        void UpdateViewCellsStats(ViewCellsStatistics &vcStat)
        {
                ViewCell::UpdateViewCellsStats(vcStat);

                //if ((int)mLeaves.size() > vcStat.maxLeaves)
                //      vcStat.maxLeaves = (int)mLeaves.size();
                //vcStat.leaves += (int)mLeaves.size();
        }

        bool IsLeaf() const
        {
                return true;
        }

        /// Leaf of some hierarchy which is part of this view cell.
        T mLeaf;
};


typedef ViewCellLeaf<BspLeaf *> BspViewCell;
typedef ViewCellLeaf<KdLeaf *> KdViewCell;
typedef ViewCellLeaf<VspKdLeaf *> VspKdViewCell;



class ViewCellsTree
{
public:
        ViewCellsTree(ViewCellsManager *vcm);
        ~ViewCellsTree();

        /** Returns number of leaves this view cell consists of.
        */
        int GetSize(ViewCell *vc) const;

        /** Collects leaves corresponding to a view cell.
        */
        void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const;

        /** Merges view cells according to some cost heuristics.
        */
        int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects);
        
        /** Refines view cells using shuffling, i.e., border leaves 
                of two view cells are exchanged if the resulting view cells
                are tested to be "better" than the old ones.
                @returns number of refined view cells
        */
        int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);

        /** Compresses the pvs of the view cells.
        */
        void CompressViewCellsPvs();

        /** Returns optimal set of view cells for a given number of view cells.
        */
        void CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells);

        /** Root of view cells tree.
        */
        ViewCell *GetRoot();

protected:


        //////////////////////////////////////////////////////////////
        //                 merge options                            //
        //////////////////////////////////////////////////////////////
        

        /** Returns cost of this leaf according to current heuristics.
        */
        float GetCostHeuristics(ViewCell *vc) const;

        /** Returns cost of leaf.
        */
        float GetRenderCost(ViewCell *vc) const;

        /** Evaluates the merge cost of this merge candidate pair.
        */
        void EvalMergeCost(MergeCandidate &mc) const;

        /** Variance of leaf.
        */
        float GetVariance(ViewCell *vc) const;

        /** Standard deviation of leaf.
        */
        float GetDeviation(ViewCell *vc) const;

        /** Tries to set this merge candidate to valid. 
                @returns false if both view cells are the same
        */
        bool ValidateMergeCandidate(MergeCandidate &mc) const;

        /** Merge view cells of leaves l1 and l2.
                @returns difference in pvs size
        */
        ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff); //const;

        /** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
                to view cell 2.
        */
        void ShuffleLeaf(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const;   
                
        /** Shuffles the leaves, i.e., tests if exchanging
                the leaves helps in improving the view cells.
        */
        bool ShuffleLeaves(ViewCell *l, ViewCell *r) const;

        /** Calculates cost for merge of view cell 1 and 2.
        */
        float EvalShuffleCost(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const;

        /** Exports a snapshot of the merged view cells to disc.
        */
        void ExportMergedViewCells(ViewCellContainer &viewCells, 
                                                           const ObjectContainer &objects,
                                                           const int numNewViewCells);

        /** merge queue must be reset after some time because expected value
                may not be valid.
        */
        void ResetMergeQueue();

        /** Updates the current top level of view cells.
                @returns number of newly merged view cells
        */
        int UpdateActiveViewCells(ViewCellContainer &viewCells);

        void ComputeCommonPvs(ViewCellInterior *interior);


        /** Returns memory usage of view cells.
        */
        float GetMemUsage() const;




        ViewCellsManager *mViewCellsManager;
        ViewCell *mRoot;

        /// if merge visualization should be shown
        bool mExportMergedViewCells;

        
                
        ViewCellContainer mMergedViewCells;
        

        /// weights between variance and render cost increase (must be between zero and one)
        float mRenderCostWeight;

        /// overall cost used to normalize cost ratio
        float mOverallCost;
        float mExpectedCost;
    float mDeviation;
        float mAvgRenderCost;

        int mUseAreaForPvs;

        int mNumActiveViewCells;

        /// minimal number of view cells
        int mMergeMinViewCells;
        /// maximal cost ratio for the merge
        float mMergeMaxCostRatio;

        ofstream mStats;

        typedef priority_queue<MergeCandidate> MergeQueue;

        MergeQueue mMergeQueue;

        float mMaxMemory;

};


/**
        Candidate for leaf merging based on priority.
*/
class MergeCandidate
{  
        friend class ViewCellsTree;

public:

        MergeCandidate(ViewCell *l, ViewCell *r);

        /** If this merge pair is still valid.
        */
        bool IsValid() const;

        
        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
        {
                return leafb.GetMergeCost() < leafa.GetMergeCost();
        }

        void SetLeftViewCell(ViewCell *l);
        void SetRightViewCell(ViewCell *l);

        ViewCell *GetLeftViewCell() const;
        ViewCell *GetRightViewCell() const;

        ViewCell *GetInitialLeftViewCell() const;
        ViewCell *GetInitialRightViewCell() const;

        /** Returns the increase of the standard deviation of this merge candidate.
        */
        float GetDeviationIncr() const;

        /** Merge cost of this candidate pair.
        */
        float GetMergeCost() const;

        /** Render cost of this candidate.
        */
        float GetRenderCost() const;
        
        static float sRenderCostWeight;

protected:

        /// render cost increase by this merge
        float mRenderCost;
        /// increase / decrease of standard deviation
        float mDeviationIncr;

        ViewCell *mLeftViewCell;
        ViewCell *mRightViewCell;

        ViewCell *mInitialLeftViewCell;
        ViewCell *mInitialRightViewCell;
};


class MergeStatistics: public StatisticsBase
{
public:
        
        int merged;
        int siblings;
        int candidates;
        int nodes;

        int accTreeDist;
        int maxTreeDist;
        
        Real collectTime;
        Real mergeTime;

        Real overallCost;

        Real expectedRenderCost;
        Real deviation;
        Real heuristics;

        // Constructor
        MergeStatistics() 
        {
                Reset();
        }
        
        double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 

        void Reset() 
        {
                nodes = 0;
                merged = 0;
                siblings = 0;
                candidates = 0;
        
                accTreeDist = 0;
                maxTreeDist = 0;

                collectTime = 0;
                mergeTime = 0;
                overallCost = 0;

                expectedRenderCost = 0;
                deviation = 0;
                heuristics = 0;

        }

        void Print(ostream &app) const;

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

#endif