Changeset 485 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

Timestamp:

12/30/05 12:08:15 (19 years ago)

Author:

mattausch

Message:

changed castlinesegment of vspbpstree
changed rayinfo ray classification for bsp tree
implemented shuffling

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h (modified) (10 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -21 +21 @@
 class ViewCellsStatistics;
 class ViewCellsManager;
+class BspMergeCandidate;
+struct BspRay;
 
 
@@ -222 +224 @@
         BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
 
-        /** Returns view cell corresponding to unbounded space.
-        */
-        BspViewCell *GetRootCell() const;
-
         /** Returns epsilon of this tree.
         */
         float GetEpsilon() const;
 
-
+        /** Casts line segment into the tree.
+                @param origin the origin of the line segment
+                @param termination the end point of the line segment
+                @returns view cells intersecting the line segment.
+        */
     int CastLineSegment(const Vector3 &origin,
                                                 const Vector3 &termination,
                                                 ViewCellContainer &viewcells);
 
-        /** Merges leaves with similar PVS.
-        */
-        int MergeLeaves();
                 
         /** Sets pointer to view cells manager.
@@ -243 +242 @@
         void SetViewCellsManager(ViewCellsManager *vcm);
 
-        /** Helper function revalidating the view cell leaf list after merge.
-        */
-        void RepairVcLeafLists();
-
-        /** Collapses the tree with respect to the view cell partition.
-                @returns node of type leaf if the node could be collapsed, this node otherwise
+        /** Returns distance from node 1 to node 2.
+        */
+        int TreeDistance(BspNode *n1, BspNode *n2) const;
+
+        /** Merges view cells according to some cost heuristics.
+        */
+        int MergeViewCells(const VssRayContainer &rays);
+        
+        /** 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);
+
+        /** Collapses the tree with respect to the view cell partition,
+                i.e. leaves having the same view cell are collapsed.
+                @returns node of type leaf if the node could be collapsed, 
+                this node otherwise
         */
         BspNode *CollapseTree(BspNode *node);
-        
-
-        /** Returns distance from node 1 to node 2.
-        */
-        int TreeDistance(BspNode *n1, BspNode *n2);
+
+        /** Constructs bsp rays for post processing and visualization.
+        */
+        void ConstructBspRays(vector<BspRay *> &bspRays,
+                                                  const VssRayContainer &rays);
+
+        
+        /** Merge view cells of leaves l1 and l2.
+        */
+        bool MergeViewCells(BspLeaf *l1, BspLeaf *l2) const;
 
 protected:
@@ -286 +303 @@
         };
 
+        /** Shuffles the leaves, i.e., tests if exchanging
+                the leaves helps in improving the view cells.
+        */
+        bool ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const;
+
+        /** Helper function revalidating the view cell leaf list after merge.
+        */
+        void RepairVcLeafLists();
+
         /** Evaluates tree stats in the BSP tree leafs.
         */
@@ -478 +504 @@
 
 
+        /** Collects candidates for the merge in the merge queue.
+                @returns number of leaves in queue
+        */
+        int CollectMergeCandidates();
+        /** Collects candidates for the merge in the merge queue.
+                @returns number of leaves in queue
+        */
+        int CollectMergeCandidates(const VssRayContainer &rays);
+
         /** Take 3 ray endpoints, where two are minimum and one a maximum
                 point or the other way round.
@@ -484 +519 @@
 
         /** Take plane normal as plane normal and the midpoint of the ray.
-                PROBLEM: does not resemble any point where visibility is likely to change
+                PROBLEM: does not resemble any point where visibility is 
+                likely to change
         */
         Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;
 
-        /** Fit the plane between the two lines so that the plane has equal shortest 
-                distance to both lines.
+        /** Fit the plane between the two lines so that the plane 
+                has equal shortest distance to both lines.
         */
         Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
   
-        /** Merge view cells of leaves l1 and l2.
-        */
-        bool MergeViewCells(BspLeaf *l1, BspLeaf *l2);
+        void ShuffleLeaf(BspLeaf *leaf, 
+                                         BspViewCell *vc1, 
+                                         BspViewCell *vc2) const;
 
         /// Pointer to the root of the tree
@@ -513 +549 @@
         /// box around the whole view domain
         AxisAlignedBox3 mBox;
-
-        /// view cell corresponding to unbounded space
-        BspViewCell *mRootCell;
 
         /// minimal number of rays before subdivision termination
@@ -574 +607 @@
         float mMergeMaxCostRatio;
 
-        ViewCellsManager *mViewCellsManager;
-
         // if rays should be stored in leaves
         bool mStoreRays;
+        
+        /// if only driving axis should be used for split
+        bool mOnlyDrivingAxis;
+
+        ViewCellsManager *mViewCellsManager;
 
         vector<SortableEntry> *mSplitCandidates;
 
-        bool mOnlyDrivingAxis;
-
+        typedef priority_queue<BspMergeCandidate> MergeQueue;
+        MergeQueue mMergeQueue;
+        
+        bool mUseRaysForMerge;
 
 private:
@@ -646 +684 @@
 
 protected:
-        
+
+        /** Cost of a view cell.
+        */
+        float GetCost(ViewCell *vc) const;
         /** Evaluates the merge costs of the leaves.
         */
@@ -661 +702 @@
 
 
+class MergeStatistics: public StatisticsBase
+{
+public:
+        
+        int merged;
+        int siblings;
+        int candidates;
+        int nodes;
+
+        int accTreeDist;
+        int maxTreeDist;
+        
+        Real collectTime;
+        Real mergeTime;
+
+        // 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;
+        }
+
+        void Print(ostream &app) const;
+
+        friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 
+        {
+                stat.Print(s);
+                return s;
+        } 
+};
+
 #endif