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

Timestamp:

09/15/06 17:33:22 (18 years ago)

Author:

mattausch

Message:

fixed sah for objeect partition
loader for single triangles also for x3d

File:

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

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

@@ -290 +290 @@
                                                                                 BvhTraversalData &backData)
 {
-        mBvhStats.nodes += 2; // we have two new leaves
-
         const BvhTraversalData &tData = sc.mParentData;
         BvhLeaf *leaf = tData.mNode;
         AxisAlignedBox3 parentBox = leaf->GetBoundingBox();
+
+        // update stats
+        mBvhStats.nodes += 2; // we have two new leaves
+
+        if (tData.mDepth > mBvhStats.maxDepth)
+        {
+                mBvhStats.maxDepth = tData.mDepth;
+        }
 
         // add the new nodes to the tree
@@ -471 +477 @@
                 splitCandidate.mParentData.mMaxCostMisses;
 
-        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
         const float oldProp = EvalViewCellsVolume(leaf->mObjects);
-
-        const float oldRenderCost = oldProp * (float)leaf->mObjects.size() / viewSpaceVol;
-
+        const float oldRenderCost = EvalRenderCost(leaf->mObjects);
+                
         // compute global decrease in render cost
-        float newRenderCost = EvalRenderCost(splitCandidate.mParentData,
-                                                                             splitCandidate.mFrontObjects,
-                                                                                 splitCandidate.mBackObjects);
-
-        newRenderCost /=  viewSpaceVol;
+        const float newRenderCost = 
+                EvalRenderCost(splitCandidate.mFrontObjects) +
+                EvalRenderCost(splitCandidate.mBackObjects);
+
         const float renderCostDecr = oldRenderCost - newRenderCost;
 
-        //Debug << "\nbvh render cost decr: " << renderCostDecr << endl;
+#ifdef _DEBUG
+        Debug << "old render cost: " << oldRenderCost << endl;
+        Debug << "new render cost: " << newRenderCost << endl;
+        Debug << "render cost decrease: " << renderCostDecr << endl;
+#endif
         splitCandidate.SetRenderCostDecrease(renderCostDecr);
 
-#if 0
-        const float priority = (float)-splitCandidate.mParentData.mDepth;
-#else   
+#if 1
         // take render cost of node into account 
         // otherwise danger of being stuck in a local minimum!!
         const float factor = mRenderCostDecreaseWeight;
         const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
+#else
+        const float priority = (float)-splitCandidate.mParentData.mDepth;
 #endif
 
@@ -540 +547 @@
         // depth related stuff
 
-        if (data.mDepth > mBvhStats.maxDepth)
-        {
-                mBvhStats.maxDepth = data.mDepth;
-        }
-
         if (data.mDepth < mBvhStats.minDepth)
         {
@@ -640 +642 @@
         }
 
-        const float oldProp = EvalViewCellsVolume(tData.mNode->mObjects);
-        //const float oldProp = tData.mProbability;
-
-        const float oldRenderCost = oldProb * (float)tData.mNode->mObjects.size();
+        const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
         const float newRenderCost = 
-                EvalRenderCost(tData, objectsFront, objectsBack);
+                EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
 
         const float ratio = newRenderCost / oldRenderCost;
@@ -672 +671 @@
                 // object mailed => belongs to back objects
                 if (i < border) 
+                {
                         objectsBack.push_back(obj);
+                }
                 else
+                {
                         objectsFront.push_back(obj);
-        }
-
-        const float oldProp = EvalViewCellsVolume(tData.mNode->mObjects);
-        //const float oldProp = tData.mProbability;
-
-        const float oldRenderCost = oldProp * (float)tData.mNode->mObjects.size();
-        const float newRenderCost = EvalRenderCost(tData, objectsFront, objectsBack);
+                }
+        }
+
+        const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
+        const float newRenderCost = EvalRenderCost(objectsFront) + EvalRenderCost(objectsBack);
 
         const float ratio = newRenderCost / oldRenderCost;
@@ -694 +694 @@
                                                    ObjectContainer &objectsBack)
 {
-        PrepareLocalSubdivisionCandidates(tData, axis);
-  
         // go through the lists, count the number of objects left and right
         // and evaluate the following cost funcion:
         // C = ct_div_ci  + (ol + or)/queries
+        PrepareLocalSubdivisionCandidates(tData, axis);
+
         int objectsLeft = 0, objectsRight = (int)tData.mNode->mObjects.size();
   
@@ -709 +709 @@
         float minSum = 1e20f;
   
+        float minBorder = maxBox;
+        float maxBorder = minBox;
+        float areaLeft = 0, areaRight = 0;
+
+        SortableEntryContainer::const_iterator currentPos =
+                mSubdivisionCandidates->begin();
+
+        
+        // we keep track of both borders of the bounding boxes =>
+        // store the events in descending order
         vector<float> bordersRight;
         bordersRight.resize(mSubdivisionCandidates->size());
 
-        float minBorder = maxBox;
-        float maxBorder = minBox;
-
-        SortableEntryContainer::const_iterator currentPos =
-                mSubdivisionCandidates->begin();
-
         SortableEntryContainer::reverse_iterator rcit = 
                 mSubdivisionCandidates->rbegin(), rcit_end = mSubdivisionCandidates->rend();
-                
+        
         vector<float>::reverse_iterator rbit = bordersRight.rbegin();
         
@@ -728 +732 @@
                 const AxisAlignedBox3 box = obj->GetBox();
 
-                if (box.Min() < minBorder)
+                if (box.Min(axis) < minBorder)
+                {
                         minBorder = box.Min(axis);
-                
+                }
+
                 (*rbit) = minBorder;
         }
 
         vector<float>::const_iterator bit = bordersRight.begin();
-        cout << "here42" << endl;
         SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+
         for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit) 
         {
@@ -749 +755 @@
                 const AxisAlignedBox3 obox = obj->GetBox();
 
+                // the borders of the bounding boxes have changed
                 if (obox.Max(axis) > maxBorder)
+                {
                         maxBorder = obox.Max(axis);
-
+                }
+
+                minBorder = (*bit);
+        
         lbox.SetMax(axis, maxBorder);
-                rbox.SetMin(axis, *bit);
-        
-                const float sum = objectsLeft * lbox.SurfaceArea() + objectsRight * rbox.SurfaceArea();
+                rbox.SetMin(axis, minBorder);
+        
+                const float al = lbox.SurfaceArea();
+                const float ar = rbox.SurfaceArea();
+
+                const float sum = objectsLeft * al + objectsRight * ar;
       
-                cout << "pos=" << (*cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=(" 
+                /*cout << "pos=" << (*cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=(" 
                          << lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
+                cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
             cout << "cost= " << sum << endl;
-      
+*/
                 if (sum < minSum) 
                 {
-                        minSum = sum;   
+                        minSum = sum;
+                        areaLeft = al;
+                        areaRight = ar;
                         // objects belong to left side now
                         for (; currentPos != (cit + 1); ++ currentPos);
                 }
         }
+
 
         ////////////////////////////////////////////
@@ -784 +802 @@
         float ratio = newCost / oldCost;
   
-#if 0
-  cout<<"===================="<<endl;
-  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
-      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
+#ifdef _DEBUG
+        cout << "\n\nobjects=(" << objectsBack.size() << "," << objectsFront.size() << " of " << tData.mNode->mObjects.size() << ")\t area=(" 
+                 << areaLeft << "," << areaRight << ")" << endl;
+        cout << "cost= " << minSum << endl;
 #endif
   return ratio;
@@ -855 +873 @@
         int nObjectsLeft = 0;
         const int nTotalObjects = (int)tData.mNode->mObjects.size();
-        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+        const float viewSpaceVol = mHierarchyManager->GetViewSpaceBox().GetVolume();
 
         SortableEntryContainer::const_iterator backObjectsStart = mSubdivisionCandidates->begin();
@@ -1128 +1146 @@
                                         //-- use surface area heuristic because view cells not constructed yet                          
                                         nCostRatio[axis] =
-                                                EvalLocalCostHeuristics(
-                                                                                                tData,
-                                                                                                axis,
-                                                                                                nFrontObjects[axis],
-                                                                                                nBackObjects[axis]);
+                                                EvalSah(
+                                                                tData,
+                                                                axis,
+                                                                nFrontObjects[axis],
+                                                                nBackObjects[axis]);
                                 }
                         }
@@ -1138 +1156 @@
                         {
                                 //-- split objects using some simple criteria
-
                                 nCostRatio[axis] =
                                         EvalLocalObjectPartition(
@@ -1245 +1262 @@
 
 
-float BvHierarchy::EvalRenderCost(const BvhTraversalData &tData,
-                                                                  const ObjectContainer &objectsFront,
-                                                                  const ObjectContainer &objectsBack) const
-{
-        // probability that view point lies in a view cell which sees this node
-        const float pFront = EvalViewCellsVolume(objectsFront);
-        const float pBack = EvalViewCellsVolume(objectsBack);
-                
-        //-- pvs rendering heuristics
-        const float newRenderCost = (int)objectsFront.size() * pFront + (int)objectsBack.size() * 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;
+float BvHierarchy::EvalRenderCost(const ObjectContainer &objects) const
+{
+        if (mHierarchyManager->GetViewSpaceSubdivisionType() == HierarchyManager::NO_VIEWSPACE_SUBDIV)
+        {
+                if (objects.empty())
+                        return 0.0f;
+
+                /////////////////////////////
+                //-- surface area heuristics
+
+                const AxisAlignedBox3 box = ComputeBoundingBox(objects);
+                const float area = box.SurfaceArea();
+
+                return (float)objects.size() * area;
+        }
+        else
+        {       /////////////////////////////
+                //-- render cost heuristics
+
+                const float viewSpaceVol = mHierarchyManager->GetViewSpaceBox().GetVolume();
+                // probability that view point lies in a view cell which sees this node
+                const float p = EvalViewCellsVolume(objects) / viewSpaceVol;    
+
+                return (float)objects.size() * p;
+        }
 }
 
 
 AxisAlignedBox3 BvHierarchy::ComputeBoundingBox(const ObjectContainer &objects,
-                                                                                                const AxisAlignedBox3 *parentBox)
+                                                                                                const AxisAlignedBox3 *parentBox) const
 {
         if (parentBox && objects.empty())
@@ -1325 +1349 @@
                                                                    const bool setCounter) const
 {
+        // no view cells yet
+        if (mHierarchyManager->GetViewSpaceSubdivisionType() == 
+                HierarchyManager::NO_VIEWSPACE_SUBDIV)
+                return;
+
         ViewCell::NewMail();
         ObjectContainer::const_iterator oit, oit_end = objects.end();
@@ -1348 +1377 @@
                 ViewCellContainer tmpViewCells;
         
-                mVspTree->GetViewCells(*ray, tmpViewCells);
+                mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
 
                 ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
@@ -1645 +1674 @@
         bvhleaf->SetSubdivisionCandidate(oSubdivisionCandidate);
 
-        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+        const float viewSpaceVol = mHierarchyManager->GetViewSpaceBox().GetVolume();
         mTotalCost = (float)objects.size() * prop / viewSpaceVol;