Changeset 580 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

Timestamp:

02/01/06 19:29:59 (18 years ago)

Author:

mattausch

Message:

implemented variance
started implementing merge history

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h (modified) (9 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -16 +16 @@
 class VspKdLeaf;
 class KdLeaf;
+class ViewCellInterior;
+class MergeCandidate;
+class ViewCellsManager;
 
 /** Statistics for a view cell partition.
@@ -78 +81 @@
 };
 
+
 /**
         View cell with an optional mesh representation
 */
+
+
 class ViewCell: public MeshInstance
 {
@@ -93 +99 @@
         */
         virtual ~ViewCell() {}
+
         /** Returns Pvs.
         */
@@ -100 +107 @@
         int Type() const;
 
+        void SetParent(ViewCellInterior *parent);
+
         /** Adds a passing ray to the passing ray container.
         */
@@ -124 +133 @@
         virtual void UpdateViewCellsStats(ViewCellsStatistics &vcStat);
 
-        /// Ray set description of the rays passing through this node.
-        PassingRaySet mPassingRays;
+        /** 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;
 
-        /** Sets the mesh for this view cell.
-        */
-        void SetMesh(Mesh *mesh);
-
-        void SetValid(const bool valid);
-        bool GetValid() const;
+
+        /** if this is a view cell correspending to a leaf in a hierarchy.
+        */
+        virtual bool IsLeaf() const = 0;
 
   static bool SmallerPvs(const ViewCell *a,
@@ -142 +168 @@
   }
 
+
+        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:
 
@@ -150 +199 @@
         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;
+
 };
 
@@ -158 +227 @@
 */
 template<typename T>
-class HierarchyViewCell: public ViewCell
+class ViewCellLeaf: public ViewCell
 {
 public:
-        HierarchyViewCell<T>(): mLeaves(0) {}
-        HierarchyViewCell<T>(Mesh *mesh):
-                ViewCell(mesh), mLeaves(0) {}
+
+        ViewCellLeaf<T>(): mLeaf(NULL) {}
+        ViewCellLeaf<T>(Mesh *mesh):
+                ViewCell(mesh), mLeaf(NULL) {}
 
         void UpdateViewCellsStats(ViewCellsStatistics &vcStat)
@@ -169 +239 @@
                 ViewCell::UpdateViewCellsStats(vcStat);
 
-                if ((int)mLeaves.size() > vcStat.maxLeaves)
-                        vcStat.maxLeaves = (int)mLeaves.size();
-                vcStat.leaves += (int)mLeaves.size();
-        }
-
-        /// Leaves of the hierarchy which are part of this view cell.
-        std::vector<T> mLeaves;
-};
-
-
-typedef HierarchyViewCell<BspLeaf *> BspViewCell;
-typedef HierarchyViewCell<KdLeaf *> KdViewCell;
-typedef HierarchyViewCell<VspKdLeaf *> VspKdViewCell;
-
+                //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);
+
+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;
+
+        /** Recalculates this merge candidate and sets valid.
+        */
+        void SetMergeCandidateValid(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.
+        */
+        int UpdateMergedViewCells(ViewCellContainer &viewCells);
+
+
+
+        ViewCellsManager *mViewCellsManager;
+        ViewCell *mRoot;
+
+        /// if merge visualization should be shown
+        bool mExportMergedViewCells;
+
+        
+                
+        ViewCellContainer mInactiveViewCells;
+        ViewCellContainer mActiveViewCells;
+
+        /// 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 mNumViewCells;
+
+        /// minimal number of view cells
+        int mMergeMinViewCells;
+        /// maximal cost ratio for the merge
+        float mMergeMaxCostRatio;
+
+        ofstream mStats;
+
+        typedef priority_queue<MergeCandidate> MergeQueue;
+
+        MergeQueue mMergeQueue;
+
+        
+
+};
+
+
+/**
+        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