Changeset 1357

Timestamp:

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

Author:

mattausch

Message:

implemented the global version of the bounding volume construction

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BvHierarchy.cpp (modified) (33 diffs)
• BvHierarchy.h (modified) (13 diffs)
• VspTree.h (modified) (1 diff)

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
 {

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

@@ -35 +35 @@
 class VspTree;
 class ViewCellsContainer;
-//class BvhSubdivisionCandidate;
 
 
@@ -149 +148 @@
         /** The bounding box specifies the node extent.
         */
+        inline 
         AxisAlignedBox3 GetBoundingBox() const
         { return mBoundingBox; }
 
 
+        inline 
         void SetBoundingBox(const AxisAlignedBox3 &boundingBox) 
         { mBoundingBox = boundingBox; }
@@ -298 +299 @@
                 mMaxCostMisses(0), 
                 mAxis(0)
-                //mObjectsStart(0),
-                //mObjectsEnd(0)
-                {}
+                {
+                        mSortedObjects[0] = mSortedObjects[1] = mSortedObjects[2] = NULL;
+                }
                 
                 BvhTraversalData(BvhLeaf *node, 
@@ -312 +313 @@
                 mMaxCostMisses(0),
                 mAxis(0)
-                //mObjectsStart(0)
-                //mObjectsEnd(0)
-                {}
-
-                /// deletes contents and sets them to NULL
+                {
+                        mSortedObjects[0] = mSortedObjects[1] = mSortedObjects[2] = NULL;
+                }
+
+                /** Deletes contents and sets them to NULL.
+                */
                 void Clear()
                 {
                         DEL_PTR(mNode);
+                        /*DEL_PTR(mSortedObjects[0]);
+                        DEL_PTR(mSortedObjects[1]);
+                        DEL_PTR(mSortedObjects[2]);*/
                 }
 
@@ -334 +339 @@
                 /// current axis
                 int mAxis;
-                /// start of objects
-                SortableEntryContainer::const_iterator mObjectsStart;
-                /// end of objects
-                SortableEntryContainer::const_iterator mObjectsEnd;
+                /// the sorted objects for the three dimensions
+                ObjectContainer *mSortedObjects[3];             
     };
 
-        /** Candidate for a view space split.
+
+        /** Candidate for a object space split.
         */
         class BvhSubdivisionCandidate: public SubdivisionCandidate
@@ -618 +622 @@
 
         
-        /** Sorts split candidates for cost heuristics using axis aligned splits.
+        /** Prepare split candidates for cost heuristics using axis aligned splits.
                 @param node the current node
                 @param axis the current split axis
         */
-        static void SortSubdivisionCandidates(
-                const ObjectContainer &objects,
-                vector<SortableEntry> **subdivisionCandidates,
+        void PrepareLocalSubdivisionCandidates(
+                const BvhTraversalData &tData,
                 const int axis);
 
-        /** Computes best cost for axis aligned planes.
+        static void CreateLocalSubdivisionCandidates(
+                const ObjectContainer &objects, 
+                SortableEntryContainer **subdivisionCandidates,
+                const bool sort,
+                const int axis);
+
+        /** Computes object partition with the best cost according to the heurisics.
+                @param tData the traversal data
+                @param axis the split axis
+                @param objectsFront the objects in the front child bv
+                @param objectsBack the objects in the back child bv
+                @param backObjectsStart the iterator marking the position where the back objects begin
+
+                @returns relative cost (relative to parent cost)
         */
         float EvalLocalCostHeuristics(
@@ -633 +649 @@
                 const int axis,
                 ObjectContainer &objectsFront,
-                ObjectContainer &objectsFBack);
+                ObjectContainer &objectsBack);
 
         /** Evaluates the contribution to the front and back volume
@@ -708 +724 @@
         float EvalViewCellsVolume(const ObjectContainer &objects) const;
 
+        void CreateInitialSortedObjectList(BvhTraversalData &tData);
+
+        void AssignSortedObjects(
+                const BvhSubdivisionCandidate &sc,
+                BvhTraversalData &frontData,
+                BvhTraversalData &backData);
+
 
 protected:
@@ -735 +758 @@
 
 
-        //-- local termination
+        ////////////////////////////////
+        //-- local termination criteria
 
         /// maximal possible depth
@@ -751 +775 @@
 
 
-        //-- global criteria
+        ////////////////////////////////////
+        //-- global termination criteria
 
         float mTermMinGlobalCostRatio;
@@ -765 +790 @@
 
 
+        ////////////////////////////////////////
         //-- split heuristics based parameters
         
@@ -772 +798 @@
         /// if only driving axis should be used for split
         bool mOnlyDrivingAxis;
-        
         /// current time stamp (used for keeping split history)
         int mTimeStamp;
         // if rays should be stored in leaves
         bool mStoreRays;
-
-        /// epsilon for geometric comparisons
-        float mEpsilon;
-
-        /// subdivision stats output file
+        // subdivision stats output file
         ofstream  mSubdivisionStats;
         /// keeps track of cost during subdivision
@@ -789 +810 @@
         /// number of currenly generated view cells
         int mCreatedLeaves;
-
         /// represents min and max band for sweep
         float mSplitBorder;
-
         /// weight between render cost decrease and node render cost
         float mRenderCostDecreaseWeight;
-
         /// stores the kd node intersectables used for pvs
         BvhIntersectableMap mBvhIntersectables;
 
+        bool mUseGlobalSorting;
 };
 

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

@@ -256 +256 @@
 
 protected:
-
+        /// bounding box for this interior node: should we really store this?
         AxisAlignedBox3 mBoundingBox;