Changeset 1323

Timestamp:

09/05/06 09:51:56 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BvHierarchy.cpp (modified) (8 diffs)
• BvHierarchy.h (modified) (1 diff)
• HierarchyManager.cpp (modified) (8 diffs)
• HierarchyManager.h (modified) (1 diff)

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

@@ -580 +580 @@
 
         const float oldProp = EvalViewCellsVolume(tData.mNode->mObjects);
-        //const float oldProp2 = tData.mProbability; Debug << "here65 " << oldProp - oldProp2 << endl;
+        //const float oldProp2 = tData.mProbability;
 
         const float oldRenderCost = oldProp * (float)tData.mNode->mObjects.size();
@@ -591 +591 @@
 
 
-float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
-                                                                                   const int axis,
-                                                                                   ObjectContainer &objectsFront,
-                                                                                   ObjectContainer &objectsBack)
-{
-        // prepare the heuristics by setting mailboxes and counters.
-        const float totalVol = PrepareHeuristics(tData, axis);
-
+float BvHierarchy::EvalSah(const BvhTraversalData &tData,
+                                                   const int axis,
+                                                   ObjectContainer &objectsFront,
+                                                   ObjectContainer &objectsBack)
+{
+        SortSubdivisionCandidates(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();
+        // and evaluate the following cost funcion:
+        // C = ct_div_ci  + (ol + or)/queries
+        int objectsLeft = 0, objectsRight = (int)tData.mNode->mObjects.size();
+  
+        AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
+
+        float minBox = box.Min(axis);
+        float maxBox = box.Max(axis);
+        float boxArea = box.SurfaceArea();
+
+        float minSum = 1e20f;
+  
+        vector<float> bordersRight;
+        bordersRight.resize(mSubdivisionCandidates->size());
+
+        float minBorder = maxBox;
+        float maxBorder = minBox;
 
         vector<SortableEntry>::const_iterator currentPos =
                 mSubdivisionCandidates->begin();
 
-        /////////////////////////////////
-        // the parameters for the current optimum
-
-        float volBack = volLeft;
-        float volFront = volRight;
-        float newRenderCost = nTotalObjects * totalVol;
-
-#ifdef _DEBUG
-        const int leaves = mBvhStats.Leaves();
-        const bool printStats = ((axis == 0) && (leaves > 0) && (leaves < 90));
-        
-        ofstream sumStats;
-        ofstream vollStats;
-        ofstream volrStats;
-
-        if (printStats)
+        vector<SortableEntry>::reverse_iterator rcit = 
+                mSubdivisionCandidates->rbegin(), rcit_end = mSubdivisionCandidates->rend();
+                
+        vector<float>::reverse_iterator rbit = bordersRight.rbegin();
+        
+        for (; rcit != rcit_end; ++ rcit, ++ rbit) 
+        {
+                Intersectable *obj = (*rcit).mObject;
+                const AxisAlignedBox3 box = obj->GetBox();
+
+                if (box.Min() < minBorder)
+                        minBorder = box.Min(axis);
+                
+                (*rbit) = minBorder;
+        }
+
+        vector<float>::const_iterator bit = bordersRight.begin();
+
+        vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+        for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit) 
+        {
+                Intersectable *obj = (*cit).mObject;
+
+                ++ objectsLeft;
+                -- objectsRight;
+
+                AxisAlignedBox3 lbox = box;
+                AxisAlignedBox3 rbox = box;
+        
+                const AxisAlignedBox3 obox = obj->GetBox();
+
+                if (obox.Max(axis) > maxBorder)
+                        maxBorder = obox.Max(axis);
+
+        lbox.SetMax(axis, maxBorder);
+                rbox.SetMin(axis, *bit);
+        
+                const float sum = objectsLeft * lbox.SurfaceArea() + objectsRight * rbox.SurfaceArea();
+      
+            // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
+            // cout<<"cost= "<<sum<<endl;
+      
+                if (sum < minSum) 
+                {
+                        minSum = sum;   
+                        // objects belongs to left side now
+                        for (; currentPos != (cit + 1); ++ currentPos);
+                }
+        }
+
+        //-- assign object to front and back volume
+
+        // belongs to back bv
+        for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
+                objectsBack.push_back((*cit).mObject);
+        
+        // belongs to front bv
+        for (cit = currentPos; cit != cit_end; ++ cit)
+                objectsFront.push_back((*cit).mObject);
+
+        float oldCost = (float)tData.mNode->mObjects.size();
+        float newCost = minSum / boxArea;
+        float ratio = newCost / oldCost;
+  
+#if 0
+  cout<<"===================="<<endl;
+  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
+      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
+#endif
+  return ratio;
+}
+
+
+static bool PrepareOutput(const int axis,
+                                                  const int leaves,
+                                                  ofstream &sumStats, 
+                                                  ofstream &vollStats, 
+                                                  ofstream &volrStats)
+{
+        if ((axis == 0) && (leaves > 0) && (leaves < 90))
         {
                 char str[64];   
@@ -639 +709 @@
                 volrStats.open(str);
         }
+
+        return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
+}
+
+
+static void PrintHeuristics(const int objectsRight,
+                                                        const float sum,
+                                                        const float volLeft,
+                                                        const float volRight,
+                                                        const float viewSpaceVol,
+                                                        ofstream &sumStats, 
+                                                        ofstream &vollStats, 
+                                                        ofstream &volrStats)
+{
+        sumStats
+                << "#Position\n" << objectsRight << endl
+                << "#Sum\n" << sum / viewSpaceVol << endl
+                << "#Vol\n" << (volLeft +  volRight) / viewSpaceVol << endl;
+
+        vollStats
+                << "#Position\n" << objectsRight << endl
+                << "#Vol\n" << volLeft / viewSpaceVol << endl;
+
+        volrStats
+                << "#Position\n" << objectsRight << endl
+                << "#Vol\n" << volRight / viewSpaceVol << endl;
+}
+
+
+float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
+                                                                                   const int axis,
+                                                                                   ObjectContainer &objectsFront,
+                                                                                   ObjectContainer &objectsBack)
+{
+        // 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();
+
+        /////////////////////////////////
+        // the parameters for the current optimum
+
+        float volBack = volLeft;
+        float volFront = volRight;
+        float newRenderCost = nTotalObjects * totalVol;
+
+#ifdef _DEBUG
+        ofstream sumStats;
+        ofstream vollStats;
+        ofstream volrStats;
+
+        const bool printStats =
+                PrepareOutput(axis, mBvhStats.Leaves(), sumStats, vollStats, volrStats);
+        
 #endif
 
@@ -666 +803 @@
 
 #ifdef _DEBUG
-                
                 if (printStats)
-                {
-                        sumStats
-                                << "#Position\n" << nObjectsRight << endl
-                                << "#Sum\n" << sum / viewSpaceVol << endl
-                                << "#Vol\n" << (volLeft +  volRight) / viewSpaceVol << endl;
-
-                        vollStats
-                                << "#Position\n" << nObjectsRight << endl
-                                << "#Vol\n" << volLeft / viewSpaceVol << endl;
-
-                        volrStats
-                                << "#Position\n" << nObjectsRight << endl
-                                << "#Vol\n" << volRight / viewSpaceVol << endl;
-                }
+                        PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
+                                                        sumStats, vollStats, volrStats);
 #endif
 
@@ -705 +829 @@
         for (cit = currentPos; cit != cit_end; ++ cit)
                 objectsFront.push_back((*cit).mObject);
-
-        tData.mNode->mObjects.end();
 
         const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
@@ -775 +897 @@
 float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData, const int axis)
 {       
-        //-- sort so we can use a sweep from right to left
+        BvhLeaf *leaf = tData.mNode;
+        float vol = 0;
+
+        // sort so we can use a sweep from right to left
         SortSubdivisionCandidates(tData, axis);
-
-        float vol = 0;
-        BvhLeaf *leaf = tData.mNode;
 
         // collect and mark the view cells as belonging to front pvs
         ViewCellContainer viewCells;
         CollectViewCells(tData.mNode->mObjects, viewCells, true);
-
-    ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-
+                        
+        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
         for (vit = viewCells.begin(); vit != vit_end; ++ vit)
         {
@@ -792 +913 @@
         }
 
+        // mail the objects on the left side
+        Intersectable::NewMail();
         // mail view cells on the left side
         ViewCell::NewMail();
-        // mail the objects on the left side
-        Intersectable::NewMail();
-
+        
         return vol;
 }
@@ -808 +929 @@
         // collect all view cells associated with this objects 
         // (also multiple times, if they are pierced by several rays)
-
         ViewCellContainer viewCells;
-        
         const bool useMailboxing = false;
+
         CollectViewCells(obj, viewCells, useMailboxing);
-
 
         /// classify view cells and compute volume contri accordingly

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

@@ -553 +553 @@
                 ObjectContainer &objectsBack);
 
+        float EvalSah(
+                const BvhTraversalData &tData,
+                const int axis,
+                ObjectContainer &objectsFront,
+                ObjectContainer &objectsBack);
+
         /** Computes priority of the traversal data and stores it in tData.
         */

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

@@ -46 +46 @@
                 mOspTree = new OspTree();
                 mOspTree->mVspTree = mVspTree;
-                //mOspTree->mHierarchyManager = this;
+                
                 Debug << "creating osp tree" << endl;
                 break;
@@ -52 +52 @@
         mBvHierarchy = new BvHierarchy();
                 mBvHierarchy->mVspTree = mVspTree;
-                //mBvHierarchy->mHierarchyManager = this;
+                
                 Debug << "creating bv hierachy" << endl;
                 break;
@@ -74 +74 @@
         mOspTree->mVspTree = mVspTree;
 
-        //mOspTree->mHierarchyManager = this;
         Debug << "creating osp tree" << endl;
 
@@ -216 +215 @@
         cout << "Constructing view space / object space tree ... \n";
         
+        // use objects for evaluating vsp tree construction in the first levels
+        // of the subdivision
+        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
+        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
+
+        // start with view space subdivison: prepare vsp tree for traversal
+        PrepareViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
+
+        // start object space subdivision immediately?
+        if (StartObjectSpaceSubdivision())
+        {
+                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
+                PrepareObjectSpaceSubdivision(sampleRays, objects);
+        }
+
         // process object space candidates
         RunConstruction(sampleRays, objects, forcedViewSpace);
@@ -328 +342 @@
         const bool ospDepthReached = 
                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth);
-        const bool stillNotOsp = (mObjectSpaceSubdivisionType == NO_OBJ_SUBDIV);
     
-        return stillNotOsp && (mTQueue.Empty() || ((mConstructionType == 1) && ospDepthReached));
+        return !ObjectSpaceSubdivisionConstructed() && 
+                   (mTQueue.Empty() || ((mConstructionType == INTERLEAVED) && ospDepthReached));
 }
 
@@ -340 +354 @@
         mHierarchyStats.nodes = 0;
         mGlobalCostMisses = 0;
-
-        // use objects for evaluating vsp tree construction in the first levels
-        // of the subdivision
-        const int savedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
-        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
-
-        // start with view space subdivison: prepare vsp tree for traversal
-        PrepareViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
-
-        // start object space subdivision immediately?
-        if (StartObjectSpaceSubdivision())
-        {cout << "here1155 ";
-                mObjectSpaceSubdivisionType = savedObjectSpaceSubdivisionType;
-                PrepareObjectSpaceSubdivision(sampleRays, objects);
-        }
 
         int i = 0;
@@ -389 +388 @@
                 if (StartObjectSpaceSubdivision())
                 {
-                        mObjectSpaceSubdivisionType = savedObjectSpaceSubdivisionType;
+                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
 
                         cout << "starting object space subdivision at maximal view space subdivison depth " << mVspTree->mVspStats.maxDepth << " (" << mMinDepthForObjectSpaceSubdivion << ") " << endl;
@@ -401 +400 @@
                 DEL_PTR(mCurrentCandidate);
         }
-        
-        mObjectSpaceSubdivisionType = savedObjectSpaceSubdivisionType;
+
+        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
 }
 

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

@@ -265 +265 @@
 protected:
 
+        enum {SEQUENTIAL, INTERLEAVED};
         int mObjectSpaceSubdivisionType;
+        /// the original osp type
+        int mSavedObjectSpaceSubdivisionType;
+
         int mConstructionType;