Changeset 1357 for GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp

Timestamp:

09/13/06 17:15:26 (18 years ago)

Author:

mattausch

Message:

implemented the global version of the bounding volume construction

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp (modified) (33 diffs)

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

@@ -24 +24 @@
 #define USE_FIXEDPOINT_T 0
 
-static float debugVol = 0;
-
-int BvhNode::sMailId = 10000;//2147483647;
+int BvhNode::sMailId = 10000; //2147483647;
 int BvhNode::sReservedMailboxes = 1;
 
@@ -32 +30 @@
 
 
+/// sorting operator
 inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
 {
@@ -171 +170 @@
 {
         ReadEnvironment();
-        mSubdivisionCandidates = new vector<SortableEntry>;
+        mSubdivisionCandidates = new SortableEntryContainer;
 }
 
@@ -228 +227 @@
                 "BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
         
-
+        Environment::GetSingleton()->GetBoolValue("BvHierarchy.useGlobalSort", mUseGlobalSorting);
+
+
+        ///////////////////
         //-- debug output
-
         Debug << "******* Bvh hierarchy options ******** " << endl;
     Debug << "max depth: " << mTermMaxDepth << endl;
@@ -245 +246 @@
         Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
         Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
-        
         Debug << "split borders: " << mSplitBorder << endl;
         Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
+        Debug << "use global sort: " << mUseGlobalSorting << endl;
         Debug << endl;
 }
 
 
-void AssociateObjectsWithLeaf(BvhLeaf *leaf)
+static void AssociateObjectsWithLeaf(BvhLeaf *leaf)
 {
         ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
@@ -274 +275 @@
         
 
-        //-- the front and back traversal data is filled with the new values
+        ///////////////////////////////////////////////////////////////////
+        //-- fill  front and back traversal data with the new values
 
         frontData.mDepth = backData.mDepth = tData.mDepth + 1;
@@ -328 +330 @@
         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
+        
+        // assign the objects in sorted order
+        if (mUseGlobalSorting)
+        {
+                AssignSortedObjects(sc, frontData, backData);
+        }
+        
         // return the new interior node
         return node;
@@ -388 +388 @@
                 tBackData.mNode->SetSubdivisionCandidate(backCandidate);
 
-                Debug << "leaf: " << tFrontData.mNode << " setting f candidate: " << tFrontData.mNode->GetSubdivisionCandidate() << " type: " << tFrontData.mNode->GetSubdivisionCandidate()->Type() << endl;
-                Debug << "leaf: " << tBackData.mNode << " setting b candidate: " << tBackData.mNode->GetSubdivisionCandidate() << " type: " << tBackData.mNode->GetSubdivisionCandidate()->Type() << endl;
+                Debug << "leaf: " << tFrontData.mNode << " setting f candidate: " 
+                          << tFrontData.mNode->GetSubdivisionCandidate() << " type: " 
+                          << tFrontData.mNode->GetSubdivisionCandidate()->Type() << endl;
+
+                Debug << "leaf: " << tBackData.mNode << " setting b candidate: " 
+                          << tBackData.mNode->GetSubdivisionCandidate() << " type: " 
+                          << tBackData.mNode->GetSubdivisionCandidate()->Type() << endl;
                 
                 tQueue.Push(frontCandidate);
@@ -443 +448 @@
         const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
         const float oldProp = EvalViewCellsVolume(leaf->mObjects);
-        //const float oldProp2 = splitCandidate.mParentData.mProbability; Debug << "here8 " << (oldProp - oldProp2) / viewSpaceVol << "  " << oldProp  / viewSpaceVol << " " << oldProp2  / viewSpaceVol << endl;
 
         const float oldRenderCost = oldProp * (float)leaf->mObjects.size() / viewSpaceVol;
@@ -568 +572 @@
                                                                                         ObjectContainer &objectsBack)
 {
-        SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
-        
-        vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+        PrepareLocalSubdivisionCandidates(tData, axis);
+        
+        SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
 
         int i = 0;
@@ -603 +607 @@
                                                    ObjectContainer &objectsBack)
 {
-        SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
+        PrepareLocalSubdivisionCandidates(tData, axis);
   
         // go through the lists, count the number of objects left and right
@@ -624 +628 @@
         float maxBorder = minBox;
 
-        vector<SortableEntry>::const_iterator currentPos =
+        SortableEntryContainer::const_iterator currentPos =
                 mSubdivisionCandidates->begin();
 
-        vector<SortableEntry>::reverse_iterator rcit = 
+        SortableEntryContainer::reverse_iterator rcit = 
                 mSubdivisionCandidates->rbegin(), rcit_end = mSubdivisionCandidates->rend();
                 
@@ -645 +649 @@
         vector<float>::const_iterator bit = bordersRight.begin();
 
-        vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+        SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
         for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit) 
         {
@@ -750 +754 @@
                                                                                    ObjectContainer &objectsBack)
 {
+        ////////////////////////////////////////////////////////////////
+        // go through the lists, count the number of objects left and right
+        // and evaluate the cost funcion
+
         // prepare the heuristics by setting mailboxes and counters.
         const float totalVol = PrepareHeuristics(tData, axis);
-
-        // go through the lists, count the number of objects left and right
-        // and evaluate the cost funcion
-
+        
         // local helper variables
         float volLeft = 0;
         float volRight = totalVol;
-
         int nObjectsLeft = 0;
-
         const int nTotalObjects = (int)tData.mNode->mObjects.size();
         const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
 
-        vector<SortableEntry>::const_iterator currentPos =
-                mSubdivisionCandidates->begin();
+        SortableEntryContainer::const_iterator backObjectsStart = mSubdivisionCandidates->begin();
 
         /////////////////////////////////
-        // the parameters for the current optimum
+        //-- the parameters for the current optimum
 
         float volBack = volLeft;
@@ -782 +784 @@
         const bool printStats =
                 PrepareOutput(axis, mBvhStats.Leaves(), sumStats, vollStats, volrStats);
-        
 #endif
 
-        /////////////////////////////
-        // the sweep heuristics
-        
+        ///////////////////////////////////////////////////
+        //-- the sweep heuristics
         //-- traverse through events and find best split plane
 
-        vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+        SortableEntryContainer::const_iterator cit, cit_end = cit_end = mSubdivisionCandidates->end();
 
         for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
@@ -802 +802 @@
 
                 ++ nObjectsLeft;
-                
                 const int nObjectsRight = nTotalObjects - nObjectsLeft;
 
@@ -811 +810 @@
 #ifdef _DEBUG
                 if (printStats)
+                {
                         PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
                                                         sumStats, vollStats, volrStats);
+                }
 #endif
 
@@ -823 +824 @@
 
                         // objects belongs to left side now
-                        for (; currentPos != (cit + 1); ++ currentPos);
+                        for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
                 }
         }
 
+        ////////////////////////////////////////////
         //-- assign object to front and back volume
 
         // belongs to back bv
-        for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
+        for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
+        {
                 objectsBack.push_back((*cit).mObject);
-        
+        }
         // belongs to front bv
-        for (cit = currentPos; cit != cit_end; ++ cit)
+        for (cit = backObjectsStart; cit != cit_end; ++ cit)
+        {
                 objectsFront.push_back((*cit).mObject);
-
+        }
+
+        // render cost of the old parent
         const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
         // the relative cost ratio
@@ -853 +859 @@
 
 
-void BvHierarchy::SortSubdivisionCandidates(const ObjectContainer &objects,
-                                                                                        vector<SortableEntry> **subdivisionCandidates,
-                                                                                        const int axis)                                                                                 
+void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
+                                                                                                        const int axis)                                                                                 
+{
+        //-- insert object queries
+        ObjectContainer *objects;
+
+        if (!mUseGlobalSorting)
+                objects = &tData.mNode->mObjects;
+        else
+                objects = tData.mSortedObjects[axis];
+        
+        CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, mUseGlobalSorting, axis);
+}
+
+
+void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects, 
+                                                                                                  SortableEntryContainer **subdivisionCandidates, 
+                                                                                                  const bool sort,
+                                                                                                  const int axis)
 {
         (*subdivisionCandidates)->clear();
 
-        // compute requested size
+        // compute requested size and look if subdivision candidate has to be recomputed
         const int requestedSize = (int)objects.size() * 2;
         
@@ -866 +888 @@
                 requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
         {
-        delete *subdivisionCandidates;
-                *subdivisionCandidates = new vector<SortableEntry>;
+        delete (*subdivisionCandidates);
+                (*subdivisionCandidates) = new SortableEntryContainer;
         }
 
         (*subdivisionCandidates)->reserve(requestedSize);
 
-        //-- insert object queries
-        //-- These queries can induce a change in pvs size.
-        //-- Note that they cannot induce a change in view cell volume, as
-        //-- there is no ray associated with these events!!
-
         ObjectContainer::const_iterator oit, oit_end = objects.end();
 
         for (oit = objects.begin(); oit < oit_end; ++ oit)
         {
-                Intersectable *obj = *oit;
-                
                 Intersectable *object = *oit;
                 const AxisAlignedBox3 &box = object->GetBox();
@@ -890 +905 @@
         }
 
-        stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
+        if (sort)
+        {
+                stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
+        }
 }
 
@@ -905 +923 @@
         float vol = 0;
 
-        // sort so we can use a sweep from right to left
-        SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
-
+    // sort so we can use a sweep from right to left
+        PrepareLocalSubdivisionCandidates(tData, axis);
+        
         // collect and mark the view cells as belonging to front pvs
         ViewCellContainer viewCells;
@@ -939 +957 @@
         CollectViewCells(obj, viewCells, useMailboxing);
 
-        /// classify view cells and compute volume contri accordingly
-        /// possible view cell classifications:
-        /// view cell mailed => view cell can be seen from left child node
-        /// view cell counter > 0 view cell can be seen from right child node
-        /// combined: view cell volume belongs to both nodes
+        // classify view cells and compute volume contri accordingly
+        // possible view cell classifications:
+        // view cell mailed => view cell can be seen from left child node
+        // view cell counter > 0 view cell can be seen from right child node
+        // combined: view cell volume belongs to both nodes
         ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
         
@@ -956 +974 @@
                 {
                         viewCell->Mail();
-
                         // we now see view cell from both nodes 
                         // => add volume to left node
@@ -964 +981 @@
                 // last reference into the right node
                 if (-- viewCell->mCounter == 0)
-                {
+                {       
                         // view cell was previously seen from both nodes  =>
                         // remove volume from right node
@@ -1005 +1022 @@
         }
         
-        // -- evaluate split cost for all three axis
+        ////////////////////////////////////////////
+        //-- evaluate split cost for all three axis
         
         for (int axis = 0; axis < 3; ++ axis)
@@ -1042 +1060 @@
         }
 
+        /////////////////////////////////////
         //-- assign values
 
@@ -1129 +1148 @@
         //-- pvs rendering heuristics
         const float newRenderCost = nObjectsFront * pFront + nObjectsBack * pBack;
-        /*
+
+#ifdef _DEBUG
         const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
         Debug << "\nbvh render cost\n" 
                   << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << endl
                   << "new rc: " << newRenderCost / viewSpaceVol << endl;*/
+#endif
 
         return newRenderCost;
@@ -1448 +1469 @@
 }
 
+
 void BvHierarchy::CreateRoot(const ObjectContainer &objects)
 {
@@ -1454 +1476 @@
         BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
         bvhleaf->mObjects = objects;
-
         mRoot = bvhleaf;
 
@@ -1465 +1486 @@
                                                                                                            const ObjectContainer &objects)
 {
+        ///////////////////////////////////////////////////////////////
+        // note matt: we assume that we have objects sorted by their id
+
         mBvhStats.Reset();
         mBvhStats.Start();
         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
 
         // store pointer to this tree
@@ -1502 +1518 @@
         BvhTraversalData oData(bvhleaf, 0, mBoundingBox, prop);
 
+        // create sorted object lists for the first data
+        if (mUseGlobalSorting)
+        {
+                CreateInitialSortedObjectList(oData);
+        }
+        
+
+        ////////////////////////////////////////////////////
         //-- add first candidate for object space partition     
+
         BvhSubdivisionCandidate *oSubdivisionCandidate = 
                 new BvhSubdivisionCandidate(oData);
@@ -1530 +1555 @@
 
 
+void BvHierarchy::CreateInitialSortedObjectList(BvhTraversalData &tData)
+{
+        SortableEntryContainer *sortedObjects = new SortableEntryContainer();
+
+        // we sort the objects as a preprocess so they don't have
+        // to be sorted for each split
+        for (int i = 0; i < 3; ++ i)
+        {
+                CreateLocalSubdivisionCandidates(tData.mNode->mObjects, &sortedObjects, true, i);
+                        
+                tData.mSortedObjects[i] = new ObjectContainer();
+                tData.mSortedObjects[i]->reserve((int)sortedObjects->size());
+
+                SortableEntryContainer::const_iterator oit, oit_end = sortedObjects->end();
+                for (oit = sortedObjects->begin(); oit != oit_end; ++ oit)
+                {
+                        tData.mSortedObjects[i]->push_back((*oit).mObject);
+                }
+        }
+
+        delete sortedObjects;
+}
+
+
+void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
+                                                                          BvhTraversalData &frontData,
+                                                                          BvhTraversalData &backData)
+{
+        Intersectable::NewMail();
+
+        // we sorted the objects as a preprocess so they don't have
+        // to be sorted for each split
+        ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();
+
+        for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
+        {
+                (*fit)->Mail();
+        }
+
+        for (int i = 0; i < 3; ++ i)
+        {
+                frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
+                backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
+
+                ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mNode->mObjects.end();
+
+                for (oit = sc.mParentData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
+                {
+                        if ((*oit)->Mailed())
+                        {
+                                frontData.mSortedObjects[i]->push_back(*oit);
+                        }
+                        else
+                        {
+                                backData.mSortedObjects[i]->push_back(*oit);
+                        }
+                }
+        }
+}
+
+
 void BvhStatistics::Print(ostream &app) const
 {