Changeset 1345

Timestamp:

09/12/06 19:30:31 (18 years ago)

Author:

mattausch

Message:

started with global objects sorting for bvh split heuristics

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BvHierarchy.cpp (modified) (16 diffs)
• BvHierarchy.h (modified) (8 diffs)

GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp

@@ -262 +262 @@
 
 
-BvhInterior *BvHierarchy::SubdivideNode(const ObjectContainer &frontObjects,
-                                                                                const ObjectContainer &backObjects,
-                                                                                const BvhTraversalData &tData,
+BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
                                                                                 BvhTraversalData &frontData,
                                                                                 BvhTraversalData &backData)
 {
+        const BvhTraversalData &tData = sc.mParentData;
         BvhLeaf *leaf = tData.mNode;
-        
-        // two new leaves
-    mBvhStats.nodes += 2;
+    mBvhStats.nodes += 2; // we have two new leaves
 
         // add the new nodes to the tree
@@ -281 +278 @@
         frontData.mDepth = backData.mDepth = tData.mDepth + 1;
 
-        frontData.mBoundingBox = ComputeBoundingBox(frontObjects, &tData.mBoundingBox);
-        backData.mBoundingBox = ComputeBoundingBox(backObjects, &tData.mBoundingBox);
-        
-        /////////////
+        frontData.mBoundingBox = ComputeBoundingBox(sc.mFrontObjects, &tData.mBoundingBox);
+        backData.mBoundingBox = ComputeBoundingBox(sc.mBackObjects, &tData.mBoundingBox);
+        
+
+        ////////////////////////////////
         //-- create front and back leaf
 
         BvhLeaf *back = 
-                new BvhLeaf(backData.mBoundingBox, node, (int)backObjects.size());
+                new BvhLeaf(backData.mBoundingBox, node, (int)sc.mBackObjects.size());
         BvhLeaf *front = 
-                new BvhLeaf(frontData.mBoundingBox, node, (int)frontObjects.size());
+                new BvhLeaf(frontData.mBoundingBox, node, (int)sc.mFrontObjects.size());
 
         BvhInterior *parent = leaf->GetParent();
-
 
         // replace a link from node's parent
@@ -301 +298 @@
                 node->SetParent(parent);
         }
-        else // new root
+        else // no parent => this node is the root
         {
                 mRoot = node;
@@ -311 +308 @@
         ++ mBvhStats.splits;
 
-
         ////////////////////////////////////
+        //-- fill traversal data
 
         frontData.mNode = front;
         backData.mNode = back;
 
-        back->mObjects = backObjects;
-        front->mObjects = frontObjects;
+        back->mObjects = sc.mBackObjects;
+        front->mObjects = sc.mFrontObjects;
 
         AssociateObjectsWithLeaf(back);
         AssociateObjectsWithLeaf(front);
    
-        // compute probability, i.e., volume of seen view cells
-        frontData.mProbability = EvalViewCellsVolume(frontObjects);
-        backData.mProbability = EvalViewCellsVolume(backObjects);
-
+        // compute probability of this node being visible, 
+        // i.e., volume of the view cells that can see this node
+        frontData.mProbability = EvalViewCellsVolume(sc.mFrontObjects);
+        backData.mProbability = EvalViewCellsVolume(sc.mBackObjects);
+
+    // how often was max cost ratio missed in this branch?
+        frontData.mMaxCostMisses = sc.mMaxCostMisses;
+        backData.mMaxCostMisses = sc.mMaxCostMisses;
+                
+        // assign positions of the iterators
+#if 0
+        frontData.mObjectsStart = sc.mFrontObjectsStart;
+        frontData.mObjectsEnd = sc.mFrontObjectsEnd;
+        
+        backData.mObjectsStart = sc.mBackObjectsStart;
+        backData.mObjectsEnd = sc.mBackObjectsEnd;
+#endif
+        // return the new interior node
         return node;
 }
@@ -339 +350 @@
         BvhTraversalData &tData = sc->mParentData;
 
-        BvhNode *newNode = tData.mNode;
+        BvhNode *currentNode = tData.mNode;
 
         if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
         {       
+                //////////////////////////////////////////
                 //-- continue subdivision
 
@@ -349 +361 @@
                         
                 // create new interior node and two leaf node
-                newNode = SubdivideNode(sc->mFrontObjects,
-                                                                sc->mBackObjects,
-                                                                tData, 
-                                                                tFrontData, 
-                                                                tBackData);
-        
-                const int maxCostMisses = sc->mMaxCostMisses;
-
-        // how often was max cost ratio missed in this branch?
-                tFrontData.mMaxCostMisses = maxCostMisses;
-                tBackData.mMaxCostMisses = maxCostMisses;
-                
+                currentNode = SubdivideNode(
+                        *sc, 
+                        tFrontData, 
+                        tBackData);
+        
                 // decrease the weighted average cost of the subdivisoin
                 mTotalCost -= sc->GetRenderCostDecrease();
@@ -367 +372 @@
                 if (1) PrintSubdivisionStats(*sc);
 
+
+                /////////////////////////////////////////
                 //-- push the new split candidates on the queue
                 
@@ -386 +393 @@
                 tQueue.Push(frontCandidate);
                 tQueue.Push(backCandidate);
-
-                // delete old leaf node
-                //DEL_PTR(tData.mNode);
-        }
-
-        //-- terminate traversal
-
-    if (newNode->IsLeaf())
-        {
+        }
+
+        /////////////////////////////////
+        //-- node is a leaf => terminate traversal
+
+        if (currentNode->IsLeaf())
+        {
+                //////////////////////////////////////
                 //-- store additional info
-                
                 EvaluateLeafStats(tData);
         
@@ -402 +407 @@
                 if (mStoreRays)
                 {
-                        BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(newNode);
+                        BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(currentNode);
                         CollectRays(leaf->mObjects, leaf->mVssRays);
                 }
                 
-                // detach subdivision candidate: this leaf is no candidate for
-                // splitting anymore
+                //////////////////////////////////////
+                
+                // this leaf is no candidate for splitting anymore
+                // => detach subdivision candidate
                 tData.mNode->SetSubdivisionCandidate(NULL); 
-                // detach node so it won't get deleted
+                // detach node so we don't delete it with the traversal data
                 tData.mNode = NULL;
         }
         
-        return newNode;
+        return currentNode;
 }
 
@@ -561 +568 @@
                                                                                         ObjectContainer &objectsBack)
 {
-        SortSubdivisionCandidates(tData, axis);
+        SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
         
         vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
@@ -596 +603 @@
                                                    ObjectContainer &objectsBack)
 {
-        SortSubdivisionCandidates(tData, axis);
+        SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
   
         // go through the lists, count the number of objects left and right
@@ -846 +853 @@
 
 
-void BvHierarchy::SortSubdivisionCandidates(const BvhTraversalData &tData,
+void BvHierarchy::SortSubdivisionCandidates(const ObjectContainer &objects,
+                                                                                        vector<SortableEntry> **subdivisionCandidates,
                                                                                         const int axis)                                                                                 
 {
-        mSubdivisionCandidates->clear();
-
-        //RayInfoContainer *rays = tData.mRays;
-        BvhLeaf *leaf = tData.mNode;
+        (*subdivisionCandidates)->clear();
 
         // compute requested size
-        const int requestedSize = (int)leaf->mObjects.size() * 2;
+        const int requestedSize = (int)objects.size() * 2;
         
         // creates a sorted split candidates array
-        if (mSubdivisionCandidates->capacity() > 500000 &&
-                requestedSize < (int)(mSubdivisionCandidates->capacity() / 10) )
-        {
-        delete mSubdivisionCandidates;
-                mSubdivisionCandidates = new vector<SortableEntry>;
-        }
-
-        mSubdivisionCandidates->reserve(requestedSize);
+        if ((*subdivisionCandidates)->capacity() > 500000 &&
+                requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
+        {
+        delete *subdivisionCandidates;
+                *subdivisionCandidates = new vector<SortableEntry>;
+        }
+
+        (*subdivisionCandidates)->reserve(requestedSize);
 
         //-- insert object queries
@@ -872 +877 @@
         //-- there is no ray associated with these events!!
 
-        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
-
-        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+        for (oit = objects.begin(); oit < oit_end; ++ oit)
         {
                 Intersectable *obj = *oit;
@@ -882 +887 @@
                 const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;
 
-                mSubdivisionCandidates->push_back(SortableEntry(object, midPt));
-        }
-
-        stable_sort(mSubdivisionCandidates->begin(), mSubdivisionCandidates->end());
+                (*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
+        }
+
+        stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
 }
 
@@ -901 +906 @@
 
         // sort so we can use a sweep from right to left
-        SortSubdivisionCandidates(tData, axis);
+        SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
 
         // collect and mark the view cells as belonging to front pvs
@@ -1464 +1469 @@
         mBvhStats.nodes = 1;
 
+        for (int i = 0; i < 3; ++ i)
+        {
+                mGlobalSubdivisionCandidates[i] = new vector<SortableEntry>();
+                SortSubdivisionCandidates(objects, &mGlobalSubdivisionCandidates[i], i);
+        }
+
         // note matt: we assume that we have objects sorted by their id
 

GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h

@@ -283 +283 @@
 public:
         
+        struct SortableEntry;
+        typedef vector<SortableEntry> SortableEntryContainer;
+
         /** Additional data which is passed down the BSP tree during traversal.
         */
@@ -294 +297 @@
                 mProbability(0.0),
                 mMaxCostMisses(0), 
-                mPriority(0),
                 mAxis(0)
+                //mObjectsStart(0),
+                //mObjectsEnd(0)
                 {}
                 
@@ -307 +311 @@
                 mProbability(v),
                 mMaxCostMisses(0),
-                mPriority(0),
                 mAxis(0)
+                //mObjectsStart(0)
+                //mObjectsEnd(0)
                 {}
-
-
-                /** Returns cost of the traversal data.
-                */
-                float GetCost() const
-                {
-                        return mPriority;
-                }
 
                 /// deletes contents and sets them to NULL
@@ -337 +334 @@
                 /// current axis
                 int mAxis;
-                /// current priority
-                float mPriority;
-
-
-                friend bool operator<(const BvhTraversalData &a, const BvhTraversalData &b)
-                {
-                        return a.GetCost() < b.GetCost();
-                }
+                /// start of objects
+                SortableEntryContainer::const_iterator mObjectsStart;
+                /// end of objects
+                SortableEntryContainer::const_iterator mObjectsEnd;
     };
 
@@ -544 +537 @@
                 }
         };
- 
+
         /** Evaluate balanced object partition.
         */
@@ -586 +579 @@
         
         /** Subdivides leaf.
-                @param leaf the leaf to be subdivided
+                @param sc the subdivisionCandidate holding all necessary data for subdivision           
                 
-                @param polys the polygons to be split
-                @param frontPolys returns the polygons in front of the split plane
-                @param backPolys returns the polygons in the back of the split plane
-                
-                @param rays the polygons to be filtered
-                @param frontRays returns the polygons in front of the split plane
-                @param backRays returns the polygons in the back of the split plane
-
-                @returns the root of the subdivision
+                @param frontData returns the traversal data for the front node
+                @param backData returns the traversal data for the back node
+
+                @returns the new interior node = the of the subdivision
         */
         BvhInterior *SubdivideNode(
-                const ObjectContainer &frontObjects,
-                const ObjectContainer &backObjects,
-                const BvhTraversalData &tData,
+                const BvhSubdivisionCandidate &sc,
                 BvhTraversalData &frontData,
                 BvhTraversalData &backData);
@@ -636 +622 @@
                 @param axis the current split axis
         */
-        void SortSubdivisionCandidates(
-                const BvhTraversalData &data,
+        static void SortSubdivisionCandidates(
+                const ObjectContainer &objects,
+                vector<SortableEntry> **subdivisionCandidates,
                 const int axis);
 
@@ -724 +711 @@
 protected:
         
+        /// pre-sorted subdivision candidtes for all three directions.
+        vector<SortableEntry> *mGlobalSubdivisionCandidates[3];
+
         /// pointer to the hierarchy of view cells
         ViewCellsTree *mViewCellsTree;