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

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



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

class ViewCellsStatistics: public StatisticsBase
{
public:

        /// number of view cells
        int viewCells;
        /// cost of the PVS
        float pvsCost;
        /// largest PVS of all view cells
        float maxPvs;
        /// smallest PVS of all view cells
        float 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;
        /// number of invalid view cells
        int invalid;

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

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

        void Reset()
        {
                viewCells = 0;
                pvsCost = 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;
        }
};


class ViewCellsTreeStats
{
public:
        int mPass;
    
        int mNumViewCells;
                
        float mRenderCostDecrease;

    float mTotalRenderCost;
    
        float mCurrentPvsCost;
                                                        
        float mExpectedCost;
    
        float mAvgRenderCost;
        
        float mDeviation;
                        
        float mTotalPvsCost;
        
        int mEntriesInPvs;
    
        float mMemoryCost;
        
        int mPvsSizeDecr;
  
        float mVolume;


        void Reset()
        {
                mPass = 0;
                mNumViewCells = 0;
                mRenderCostDecrease = 0;
                mTotalRenderCost = 0;
                mCurrentPvsCost = 0;
                mExpectedCost = 0;
                mAvgRenderCost = 0;
                mDeviation = 0;
                mTotalPvsCost = 0;
                mEntriesInPvs = 0;
                mMemoryCost = 0;
                mPvsSizeDecr = 0;
                mVolume = 0;
        }


        void Print(ostream &app) const;

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


/**
        A view cell. View cells are regions in space. The visibility informations,
        i.e., the primitives seen by the view cell are stored in a PVs.
        A view cell can be represented in many different ways, e.g.,
        a 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);

        /** 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->mPvsCost < b->mPvsCost;
#else
                return a->GetPvs().EvalPvsCost() < b->GetPvs().EvalPvsCost();
#endif
        }

        static bool GreaterOrEqualPvs(const ViewCell *a, const ViewCell *b) 
        {
                return !SmallerPvs(a, b);
        }

        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;

        void UpdatePvsCost() {
                mPvsCost = GetPvs().EvalPvsCost();
        }

        void SetPvsCost(const float c) {
                mPvsCost = c;
        }

        float GetPvsCost() const {
                return mPvsCost;
        }

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

        int GetFilteredPvsSize() const 
        {
                return mFilteredPvsSize;
        }

        void SetFilteredPvsSize(const int s) {
                mFilteredPvsSize = s;
  }

protected:

        /// parent view cell in the view cell hierarchy
        ViewCellInterior *mParent;
        /// the potentially visible objects
        ObjectPvs mPvs;
        /// the volume of this view cell
        float mVolume;
        /// the area of this view cell
        float mArea;
        /// the cost that were paid for merging this view cells from two others.
        float mMergeCost;
        /// if the view cell is valid view space
        bool mValid;
        /// color used for consistent visualization
        RgbColor mColor;
        /// store pvs size, used for evaluation purpose when pvss are stored only in the leaves
        float mPvsCost;
        /** stores number of entries in pvs
            this variable has the same value as mPvsSize for object pvs, 
                but usually not for kd cell based pvs
        */
        int mEntriesInPvs;
        /** if the pvs size scalar (+ entries into pvs)
                is up to date and corresponding to the real pvs size
        */
        bool mPvsSizeValid;


        /// Filter cost of the pvs
        int mFilteredPvsSize;

};


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 ReplaceChildLink(ViewCell *prev, ViewCell *cur);

        void RemoveChildLink(ViewCell *l);
        bool IsLeaf() const;

        void SetCost(const float c) {
                mCost = c;
        }

        float GetCost() const {
                return mCost;
        }

        ViewCellContainer mChildren;

protected:

        /// Pverall 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 active view cell, i.e. this view cell or
                a parent view cell which is set as active view cell.
        */
        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;
        }

        /// Leaves of some hierarchy which contains this view cell.
        vector<T> mLeaves;
};


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




class ViewCellsTree
{
        friend class ViewCellsManager;
        friend class ViewCellsParseHandlers;

public:

        ViewCellsTree();

        /** 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 storage cost resulting from each merge step.
        */
        void GetStorageFunction(vector<int> &storageCost);

        /** 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 (i.e. the render cost of the stored objects)
        */
        float GetPvsCost(ViewCell *vc) const;
  
        /** Returns number of entries associated with this view cell. 

                This returns the same value as the "GetPvsSize" function for object pvs
                but most likely different values if we use object space grouping.
                E.g., using bounding volumes.
        */
        int GetPvsEntries(ViewCell *vc) const;

        /** Returns the number of physically stored entries in the view cells sub tree.
                This can vary based on the current storage method
        */
        int CountStoredPvsEntries(ViewCell *root) 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.
        */
        bool Export(OUT_STREAM &stream, const bool exportPvs = false);

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

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

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

        /** Sets pointer to view cells manager.
        */
        void SetViewCellsManager(ViewCellsManager *vcm);

        void Update();

protected:

        /** Reads the environment and sets member variables.
        */
        void ReadEnvironment();


        //////////////////////////////////////////////////////////////
        //                    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, float &pvsDiff);

        /** 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 cut 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!!
        */
        void ExportViewCell(ViewCell *viewCell, OUT_STREAM &stream, const bool exportPvs);      

        /** Exports pvs of a view cell.
        */
        void ExportPvs(ViewCell *viewCell, OUT_STREAM &stream);

        /** Counts the logical number of entries in the pvs this view cell.
                The pvs is assumed to be stored using lossless compression.
        */
        int GetEntriesInPvsForCompressedStorage(ViewCell *vc) const;

        /** Computes pvs size of this view cell.
                The pvs is assumed to be stored using lossless compression.
        */
        float GetPvsCostForCompressedStorage(ViewCell *vc) const;
        
        /** Computes pvs size of this view cell.
                The pvs is assumed to be stored in the leaves.
        */
        float GetPvsCostForLeafStorage(ViewCell *vc) const;

        /** Counts the logical number of entries in the pvs this view cell.
                The pvs is assumed to be stored using the leaves.
        */
        int GetEntriesInPvsForLeafStorage(ViewCell *vc) const;

        /** Update stats for the log.
        */
        void UpdateStats(ofstream &stats,
                                         const ViewCellsTreeStats &vcStats);

        

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

        /// if the view cell tree hold compressed pvs
        int mViewCellsStorage;
        /// pointer to the view cells manager
        ViewCellsManager *mViewCellsManager;
        /// the root of the view cells hierarchy
        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 in the range [0 .. 1].
        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;
        /// number of currently active view cells (=current cut)
        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;
        /** Returns leaf view cell initially associated with this merge candidate.
        */
        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