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

#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().CountPvs() < b->GetPvs().CountPvs();
#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;
        /// the volume of this view cell
        float mVolume;
        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
        int mPvsSize;
        /** 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;
        

};


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 (i.e. the number of stored objects
        */
        int GetPvsSize(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 for kd node based pvs.
        */
        int GetPvsEntries(ViewCell *vc) const;

        /** Returns the actual number of stored entries in the view cells sub tree.
        */
        int GetStoredPvsEntriesNum(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.
        */
#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

        int GetEntriesInPvsForCompressedStorage(ViewCell *vc) const;
        int GetPvsSizeForCompressedStorage(ViewCell *vc) const;
        int GetPvsSizeForLeafStorage(ViewCell *vc) const;
        int GetEntriesInPvsForLeafStorage(ViewCell *vc) const;

        void UpdateStats(
                ofstream &stats,
                const int pass,
                const int viewCells,
                const float renderCostDecrease,
                const float totalRenderCost,
                const int currentPvs,
                const float expectedCost,
                const float avgRenderCost,
                const float deviation,
                const int totalPvs,
                const int entriesInPvs,
                const int pvsSizeDecr,
                const float volume);

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