source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.h @ 1121

#ifndef _ViewCell_H__
#define _ViewCell_H__

#include "Mesh.h"
#include "Containers.h"
#include "Ray.h"
#include "Statistics.h"
#include "Material.h"
#include "gzstream.h"


namespace GtpVisibilityPreprocessor {

struct Triangle3;

class BspInterior;
class BspPvs;
class BspLeaf;
class VspLeaf;
class KdLeaf;
class ViewCellInterior;
class MergeCandidate;
class ViewCellsManager;
class ViewCellLeaf;
//class Environment;


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

class ViewCellsStatistics: public StatisticsBase
{
public:

        /// number of view cells
        int viewCells;

        /// size of the PVS
        int pvsSize;

        /// 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)pvsSize / (double)viewCells;};

        void Reset()
        {
                viewCells = 0;
                pvsSize = 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
{
        friend class ViewCellsTree;
        friend class ViewCellsManager;

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;

        /** Returns pvs.
        */
        ObjectPvs &GetPvs();

        /** Completely substitutes the pvs.
        */
        void SetPvs(const ObjectPvs &pvs);

        /** Type of view cells.
        */
        int Type() const;

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


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

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

        /** Sets parent of this view cell.
        */
        void SetParent(ViewCellInterior *parent);


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

        /** Sets this view cell to be a valid view cell according to some criteria.
        */
        void SetValid(const bool valid);
        /** Returns true if this view cell is considered to be valid according to
                some criteria.
        */
        bool GetValid() const;

        /** Returns estimated render cost of this view cell.
        */
        float GetRenderCost() const;

        /** set color for visiualizations.
        */
        void SetColor(const RgbColor &color);

        /** get color for visualuzations.
        */
    RgbColor GetColor() const;

        /** Adds a sample to the pvs.
                @param sample the sample to be added
                @param pdf a continuos measure of visibility
                @param contribution returns the contribution of this sample to the pvs
        */
        bool AddPvsSample(Intersectable *sample, const float pdf, float &contribution);
  


        /// 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) 
        {
                // HACK: take scalar value because pvs may not have been stored properly
#if 1
                return a->mPvsSize < b->mPvsSize;
#else
                return a->GetPvs().GetSize() < b->GetPvs().GetSize();
#endif
        }

        static bool SmallerRenderCost(const ViewCell *a, const ViewCell *b) 
        {
                return a->GetRenderCost() < b->GetRenderCost();
        }

        static bool LargerRenderCost(const ViewCell *a, const ViewCell *b) 
        {
                return a->GetRenderCost() > b->GetRenderCost();
        }

        /** Sets merge cost used for merging this view cell from other cells. 
                @hack The function is available for leaves also to have a common interface,
                but it should be less than zero for leaves.
                */
        void SetMergeCost(const float mergeCost);

        /** Returns merge cost needed to merge this leaf from other cells.
                @hack The function is available for leaves also to have a common interface,
                but it should be less than zero for leaves.
        */
        float GetMergeCost() const;



        ////////////////////////////////////////////
        //       mailing stuff


        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:

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

        /// the potentially visible objects
        ObjectPvs mPvs;

        float mVolume;
        float mArea;

        float mMergeCost;

        bool mValid;

        /// color used for consistent visualization
        RgbColor mColor;

        
        /// store pvs size, used for evaluation purpose when pvss are stored only in the leaves
        int mPvsSize;
        /// if the pvs size scalar is up to date and corresponding to the real pvs size
        bool mPvsSizeValid;

};


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

        ViewCellInterior(Mesh *mesh);
        

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

        ViewCellContainer mChildren;

  void SetCost(const float c) {
        mCost = c;
  }
  float GetCost() const {
        return mCost;
  }
  
protected:
  /** overall cost resulting from the merge */
  float mCost;
};


/**
        Leaf of the view cell.
*/
class ViewCellLeaf: public ViewCell
{
public:
        ViewCellLeaf()  {  mActiveViewCell = this; }
        ViewCellLeaf(Mesh *mesh):
        ViewCell(mesh) { mActiveViewCell = this; }

        bool IsLeaf() const
        {
                return true;
        }

        /** Returns if this view cell is active.
        */
        ViewCell *GetActiveViewCell() const 
        { return mActiveViewCell; }

        /** Sets this view cell to be an active view cell.
        */
        void SetActiveViewCell(ViewCell *vc)
        { mActiveViewCell = vc;}

        
        /** points to the currently active view cell. This is the
                view cell representing the current brach.
        */
        ViewCell *mActiveViewCell;
};

/** Leaf of the view cell hierarchy corresponding 
        to a leaf in a spatial hierarchy.
*/
template<typename T>
class HierarchyLeafViewCell: public ViewCellLeaf
{
public:

        HierarchyLeafViewCell<T>(): ViewCellLeaf() {  }
        HierarchyLeafViewCell<T>(Mesh *mesh):
        ViewCellLeaf(mesh) {  }
                

        bool IsLeaf() const
        {
                return true;
        }


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


typedef HierarchyLeafViewCell<VspLeaf *> VspViewCell;
typedef HierarchyLeafViewCell<BspLeaf *> BspViewCell;
typedef HierarchyLeafViewCell<KdLeaf *> KdViewCell;




class ViewCellsTree
{
        friend class ViewCellsManager;


public:
        /** View cells tree constructor taking a view cell mnanager as parameter
        */
        ViewCellsTree(ViewCellsManager *vcm);
        ~ViewCellsTree();

        /** Returns number of leaves this view cell consists of.
        */
        int GetNumInitialViewCells(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);
        
        /** Assign colors to the viewcells so that they can be renderered interactively without
            color flickering.  
        */
        void AssignRandomColors();

        /** Updates view cell stats for this particular view cell.
        */
        void UpdateViewCellsStats(ViewCell *vc, ViewCellsStatistics &vcStat);

        /** Get costs resulting from each merge step. 
        */
        void GetCostFunction(vector<float> &costFunction);
  
        /** 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() const;

        /** Returns pvs of view cell.
                @note pvs is returned per reference if tree is not compressed,
                per copy else.
        */
        void GetPvs(ViewCell *vc, ObjectPvs &pvs) const;

        /** Returns pvs size of view cell.
        */
        //int GetPvsSize(ViewCell *vc) const;
        int GetPvsSize(ViewCell *vc, const bool countKdPvs = false) const;

        /** Returns actual number of object in this pvs and the children.
        */
        int GetNumPvsEntries(ViewCell *vc) const;

        /** Returns memory cost of this view cell.
        */
        float GetMemoryCost(ViewCell *vc) const;

        /** Sets method of storage for view cells.
        */
        void SetViewCellsStorage(int type);

        /** pvs storage methods 
        */
        enum {PVS_IN_INTERIORS, COMPRESSED, PVS_IN_LEAVES};

        
        /** If view cells in this tree have compressed pvs.
        */
        int ViewCellsStorage() const;

        /** Returns active view cell that is in the path of this view cell.
        */
        ViewCell *GetActiveViewCell(ViewCellLeaf *vc) const;

        /** Sets the leaves to be the currently active view cells.
        */
    void SetActiveSetToLeaves();

        /** Propagates pvs up the tree to the root and downwards the tree.
        */
        void PropagatePvs(ViewCell *vc);

        /** Exports view cells to file.
        */
#if ZIPPED_VIEWCELLS
        bool Export(ogzstream &stream, const bool exportPvs = false);
#else
        bool Export(ofstream &stream, const bool exportPvs = false);
#endif

        /** Export statistics of this view cell tree.
        */
        void ExportStats(const string &mergeStats);

        /** Sets root of hierarchy.
        */
        void SetRoot(ViewCell *root);

        //float ComputeVolume(ViewCell *vc);

        /** Assignes unique ids to view cells.
        */
        void CreateUniqueViewCellsIds();

        /** Resets pvs of whole tree.
        */
        void ResetPvs();

        /** Counts pvs of the view cell taking the kd cells into account.
        */
        int CountKdPvs(const ViewCellLeaf *vc) const;

protected:


        /////////////////////////////////////////////////////////////////
        //                    merge related stuff                      //
        /////////////////////////////////////////////////////////////////

        /** Computes render cost of the merged pvs.
        */
        float ComputeMergedPvsCost(const ObjectPvs &pvs1, const ObjectPvs &pvs2) const;

        /** 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, ViewCellInterior *vc1, ViewCellInterior *vc2) const;   
                
        /** Shuffles the leaves, i.e., tests if exchanging
                the leaves helps in improving the view cells.
        */
        bool ShuffleLeaves(MergeCandidate &mc) const;

        /** Calculates cost for merge of view cell 1 and 2.
        */
        float EvalShuffleCost(ViewCell *leaf, 
                                                  ViewCellInterior *vc1, 
                                                  ViewCellInterior *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);

        /** Helper function pullling pvs as high up in the tree as possible.
        */ 
        void PullUpVisibility(ViewCellInterior *interior);

        /** Compress pvs of view cell and children.
        */
        void CompressViewCellsPvs(ViewCell *root);

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

        /**     Exports single view cell.
                NOTE: should be in exporter!!
        */
#if ZIPPED_VIEWCELLS
        void ExportViewCell(ViewCell *viewCell, ogzstream &stream, const bool exportPvs);
#else
        void ExportViewCell(ViewCell *viewCell, ofstream &stream, const bool exportPvs);        
#endif

        /** Exports pvs of a view cell.
        */
#if ZIPPED_VIEWCELLS
        void ExportPvs(ViewCell *viewCell, ogzstream &stream);
#else
        void ExportPvs(ViewCell *viewCell, ofstream &stream);
#endif


        /// if the view cell tree hold compressed pvs
        int mViewCellsStorage;

        ViewCellsManager *mViewCellsManager;
        ViewCell *mRoot;

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

        
        /// intermediate container of merged view cells.
        ViewCellContainer mMergedViewCells;
        

        /// if merged view cells are refined.
        bool mRefineViewCells;

        /// 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;
        /// the area is used for pvs heuristics
        int mUseAreaForPvs;

        int mNumActiveViewCells;

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

        typedef priority_queue<MergeCandidate> MergeQueue;

        MergeQueue mMergeQueue;

        float mMaxMemory;

        int mMaxMergesPerPass;
        float mAvgCostMaxDeviation;
};


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

        /** Returns leaf view cell initially associated with this merge candidate.
        */
        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