Changeset 1020 for GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp

Timestamp:

06/18/06 03:47:06 (18 years ago)

Author:

mattausch

Message:

worked on view-object space partition
fixed some loading bugs
fixeds some exporting bugs using line segments
enabling other methods for view space sampling in ViewCellsManager? OBJECT_DIRECTION_BASED_DISTRIBUTION)
added class interface for a sampling strategy

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp (modified) (44 diffs)

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

@@ -21 +21 @@
 
 #define USE_FIXEDPOINT_T 0
-
-
+#define COUNT_ORIGIN_OBJECTS 1
+
+        
 //-- static members
-
 
 int VspBspTree::sFrontId = 0;
 int VspBspTree::sBackId = 0;
 int VspBspTree::sFrontAndBackId = 0;
+
+
 
 typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
@@ -113 +115 @@
 
         Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
+        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
         Environment::GetSingleton()->GetBoolValue("VspBspTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable);
 
@@ -161 +164 @@
         Debug << "maxband: " << mMaxBand << endl;
         Debug << "use driving axis for max cost: " << mUseDrivingAxisIfMaxCostViolated << endl;
+        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
 
         Debug << "Split plane strategy: ";
@@ -189 +193 @@
 
 
-        mSplitCandidates = new vector<SortableEntry>;
+        mLocalSplitCandidates = new vector<SortableEntry>;
 
         Debug << endl;
@@ -236 +240 @@
 {
         DEL_PTR(mRoot);
-        DEL_PTR(mSplitCandidates);
+        DEL_PTR(mLocalSplitCandidates);
 }
 
@@ -497 +501 @@
         const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
 
+        /// first traversal data
         VspBspTraversalData tData(mRoot,
                                                           new PolygonContainer(polys),
@@ -520 +525 @@
         mTotalPvsSize = tData.mPvs;
         
-        // first stats
-        mSubdivisionStats 
-                        << "#ViewCells\n1" <<  endl
-                        << "#RenderCostDecrease\n0" << endl 
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-
-
+        // first subdivison statistics
+        AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize);
+    
         mBspStats.Start();
         cout << "Constructing vsp bsp tree ... \n";
@@ -586 +584 @@
 
         Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
-        cout << "finished\n";
+        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
 
         mBspStats.Stop();
@@ -624 +622 @@
         mTotalPvsSize = tData.mPvs;
         
-        mSubdivisionStats 
-                        << "#ViewCells\n1\n" <<  endl
-                        << "#RenderCostDecrease\n0\n" << endl 
-                        << "#SplitCandidateCost\n0\n" << endl
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-        
-        
-        mBspStats.Start();
+        // first subdivison statistics
+        AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize);
+   
+    mBspStats.Start();
         cout << "Constructing vsp bsp tree ... \n";
 
@@ -654 +645 @@
 
                 // cost ratio of cost decrease / totalCost
-                float costRatio = splitCandidate.GetCost() / mTotalCost;
+                float costRatio = splitCandidate.GetPriority() / mTotalCost;
 
                 //Debug << "cost ratio: " << costRatio << endl;
@@ -716 +707 @@
 
 
+void VspBspTree::AddSubdivisionStats(const int viewCells,
+                                                                         const float renderCostDecr,
+                                                                         const float splitCandidateCost,
+                                                                         const float totalRenderCost,
+                                                                         const float avgRenderCost)
+{
+        mSubdivisionStats 
+                        << "#ViewCells\n" << viewCells << endl
+                        << "#RenderCostDecrease\n" << renderCostDecr << endl 
+                        << "#SplitCandidateCost\n" << splitCandidateCost << endl
+                        << "#TotalRenderCost\n" << totalRenderCost << endl
+                        << "#AvgRenderCost\n" << avgRenderCost << endl;
+}
+
+
 bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const
 {
@@ -726 +732 @@
 
 
-
 BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
                                                            VspBspTraversalData &tData)
@@ -785 +790 @@
                         if (1)
                         {
-                                float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
-                                float cBack = (float)tBackData.mPvs * tBackData.mProbability;
-                                float cData = (float)tData.mPvs * tData.mProbability;;
-
-                float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
+                                const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+                                const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+                                const float cData = (float)tData.mPvs * tData.mProbability;;
+
+                const float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
 
                                 mTotalCost += costDecr;
                                 mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
 
-                                mSubdivisionStats 
-                                                << "#ViewCells\n" << mBspStats.Leaves() << endl
-                                                << "#RenderCostDecrease\n" << -costDecr << endl 
-                                                << "#TotalRenderCost\n" << mTotalCost << endl
-                                                << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
+                                AddSubdivisionStats(mBspStats.Leaves(),
+                                                                    -costDecr,
+                                                                        0,
+                                                                        mTotalCost,
+                                                                        (float)mTotalPvsSize / (float)mBspStats.Leaves());
                         }
 
@@ -814 +819 @@
         {
                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+                
                 BspViewCell *viewCell = new BspViewCell();
-                
                 leaf->SetViewCell(viewCell);
         
@@ -860 +865 @@
                 leaf->mProbability = tData.mProbability;
 
+                // finally evaluate stats until this leaf
                 EvaluateLeafStats(tData);               
         }
@@ -906 +912 @@
                 tBackData.mMaxCostMisses = maxCostMisses;
                         
-                
+                // statistics
                 if (1)
                 {
@@ -920 +926 @@
                         mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
 
-                        mSubdivisionStats 
-                                        << "#ViewCells\n" << mBspStats.Leaves() << endl
-                                        << "#RenderCostDecrease\n" << -costDecr << endl
-                                        << "#SplitCandidateCost\n" << splitCandidate.GetCost() << endl
-                                        << "#TotalRenderCost\n" << mTotalCost << endl
-                                        << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
+                        AddSubdivisionStats(mBspStats.Leaves(), 
+                                                                -costDecr,  
+                                                                splitCandidate.GetPriority(), 
+                                                                mTotalCost, 
+                                                                (float)mTotalPvsSize / (float)mBspStats.Leaves());
                 }
 
@@ -948 +953 @@
         {
                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+
                 BspViewCell *viewCell = new BspViewCell();
-
         leaf->SetViewCell(viewCell);
                 
@@ -974 +979 @@
                 }
 
-                // should I check here?
+                
                 viewCell->mLeaf = leaf;
 
@@ -984 +989 @@
         leaf->mProbability = tData.mProbability;
 
+                // finally evaluate stats until this leaf
                 EvaluateLeafStats(tData);               
         }
@@ -1029 +1035 @@
         
         // compute global decrease in render cost
-        splitData.mRenderCost = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
+        splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
         splitData.mParentData = tData;
         splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
@@ -1192 +1198 @@
           
                 // only count termination objects?
-                if (1 && ray->mOriginObject) 
+                if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject) 
                 {
                         if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
                                 madeContrib = true;
+
                         sc += contribution;
                 }
@@ -1214 +1221 @@
                                                                          float maxBand)
 {
-        mSplitCandidates->clear();
+        mLocalSplitCandidates->clear();
 
         int requestedSize = 2 * (int)(rays.size());
         // creates a sorted split candidates array
-        if (mSplitCandidates->capacity() > 500000 &&
-                requestedSize < (int)(mSplitCandidates->capacity() / 10) )
-        {
-        delete mSplitCandidates;
-                mSplitCandidates = new vector<SortableEntry>;
-        }
-
-        mSplitCandidates->reserve(requestedSize);
+        if (mLocalSplitCandidates->capacity() > 500000 &&
+                requestedSize < (int)(mLocalSplitCandidates->capacity() / 10) )
+        {
+        delete mLocalSplitCandidates;
+                mLocalSplitCandidates = new vector<SortableEntry>;
+        }
+
+        mLocalSplitCandidates->reserve(requestedSize);
 
         float pos;
@@ -1245 +1252 @@
                 if (0) ClipValue(pos, minBand, maxBand);
                 
-                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
+                mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
                                                                         pos, (*ri).mRay));
 
@@ -1252 +1259 @@
                 if (0) ClipValue(pos, minBand, maxBand);
 
-                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
+                mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
                                                                         pos, (*ri).mRay));
         }
 
-        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
+        stable_sort(mLocalSplitCandidates->begin(), mLocalSplitCandidates->end());
 }
 
@@ -1307 +1314 @@
                 Intersectable *tObject = (*ri).mRay->mTerminationObject;
 
-                if (oObject)
+                if (COUNT_ORIGIN_OBJECTS && oObject)
                 {
                         if (!oObject->Mailed())
@@ -1319 +1326 @@
                         }
                 }
+
                 if (tObject)
                 {
@@ -1335 +1343 @@
         Intersectable::NewMail();
 
-        vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
-
-        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
+        vector<SortableEntry>::const_iterator ci, ci_end = mLocalSplitCandidates->end();
+
+        for (ci = mLocalSplitCandidates->begin(); ci != ci_end; ++ ci)
         {
                 VssRay *ray;
@@ -1350 +1358 @@
                         case SortableEntry::ERayMin:
                                 {
-                                        if (oObject && !oObject->Mailed())
+                                        if (COUNT_ORIGIN_OBJECTS && oObject && !oObject->Mailed())
                                         {
                                                 oObject->Mail();
                                                 ++ pvsl;
                                         }
+
                                         if (tObject && !tObject->Mailed())
                                         {
@@ -1360 +1369 @@
                                                 ++ pvsl;
                                         }
+
                                         break;
                                 }
                         case SortableEntry::ERayMax:
                                 {
-                                        if (oObject)
+                                        if (COUNT_ORIGIN_OBJECTS && oObject)
                                         {
                                                 if (-- oObject->mCounter == 0)
@@ -1379 +1389 @@
                                 }
                 }
-
-                
-                
-                // Note: sufficient to compare size of bounding boxes of front and back side?
+                
+                
+                // Note: we compare size of bounding boxes of front and back side because
+                // of efficiency reasons (otherwise a new geometry would have to be computed
+                // in each step and incremential evaluation would be difficult.
+                // but then errors happen if the geometry is not an axis aligned box 
+                // (i.e., if a geometry aligned split was taken before)
+                // question: is it sufficient to make this approximation?
                 if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
                 {
@@ -1873 +1887 @@
                 // find front and back pvs for origing and termination object
                 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+
+                if (COUNT_ORIGIN_OBJECTS) 
+                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
         }
 
@@ -1910 +1926 @@
 
         // -- pvs rendering heuristics
+
+        // upper and lower bounds
         const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
         const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
 
-        // only render cost heuristics or combined with standard deviation
-        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
+        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
                         
         const float oldRenderCost = pOverall * penaltyOld;
@@ -1924 +1941 @@
         const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume();
         
-
-#if 1
+        const float weight = mRenderCostDecreaseWeight;
         // take render cost of node into account to avoid being stuck in a local minimum
         const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
         
-        //Debug << "rendercostdecr: " << 0.99f * renderCostDecrease << " old render cost: " << 0.01f * normalizedOldRenderCost << endl;
-        return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
-#else
-        return renderCostDecrease;
-#endif
+        //Debug << "rendercostdecr: " << weight * renderCostDecrease << " old render cost: " << (1.0f - weight) * normalizedOldRenderCost << endl;
+        return weight * renderCostDecrease + (1.0f - weight) * normalizedOldRenderCost;
 }
 
@@ -1944 +1957 @@
                                                                          float &pBack) const
 {
-        float cost = 0;
-
         float totalPvs = 0;
         float pvsFront = 0;
@@ -1957 +1968 @@
         pBack = 0;
 
-
-        int limit;
-        bool useRand;
-
+        int numTests; // the number of tests
+
+        // if random samples shold be taken instead of testing all the rays
+        bool useRand; 
+
+        if ((int)data.mRays->size() > mMaxTests)
+        {
+                useRand = true;
+                numTests = mMaxTests;
+        }
+        else
+        {
+                useRand = false;
+                numTests = (int)data.mRays->size();
+        }
+        
         // create unique ids for pvs heuristics
         GenerateUniqueIdsForPvs();
 
-        // choose test rays randomly if too much
-        if ((int)data.mRays->size() > mMaxTests)
-        {
-                useRand = true;
-                limit = mMaxTests;
-        }
-        else
-        {
-                useRand = false;
-                limit = (int)data.mRays->size();
-        }
-        
-        for (int i = 0; i < limit; ++ i)
+        for (int i = 0; i < numTests; ++ i)
         {
                 const int testIdx = useRand ? 
@@ -1988 +1999 @@
                 // find front and back pvs for origing and termination object
                 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+
+                if (COUNT_ORIGIN_OBJECTS) 
+                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
         }
 
@@ -2057 +2070 @@
         }
 
-        cost += mPvsFactor * newCost / (oldCost + Limits::Small);
+        const float cost = mPvsFactor * newCost / (oldCost + Limits::Small);
                 
 
@@ -2165 +2178 @@
         for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
         {
-                //if (!(*rit).mRay->IsActive()) continue;
-
                 // determine the side of this ray with respect to the plane
                 float t;
@@ -2172 +2183 @@
         
                 AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
-                AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
-        }
+
+                if (COUNT_ORIGIN_OBJECTS) 
+                        AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
+        }
+
 
         //-- pvs heuristics
-        float pOverall;
-
-        //-- compute heurstics
-        //-- we take simplified computation for mid split
-                
-        pOverall = data.mProbability;
-
+
+        float pOverall = data.mProbability;
+
+        // note: we use a simplified computation assuming that we always do a
+        // spatial mid split    
+        
         if (!mUseAreaForPvs)
-        {   // volume
+        {   
+                // volume
                 pBack = pFront = pOverall * 0.5f;
-                
 #if 0
                 // box length substitute for probability
@@ -3220 +3233 @@
                 VssRay *ray = (*rit).mRay;
 
-                if (ray->mOriginObject)
+                if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject)
                 {
                         if (!ray->mOriginObject->Mailed())
@@ -3228 +3241 @@
                         }
                 }
+
                 if (ray->mTerminationObject)
                 {
@@ -3343 +3357 @@
                         }
                         else // one of the ray end points is on the plane
-                        {       // NOTE: what to do if ray is coincident with plane?
+                        {       
+                                // NOTE: what to do if ray is coincident with plane?
                                 if (extSide < 0)
                                         node = in->GetBack();
@@ -3365 +3380 @@
                         ViewCell *viewCell;
                         
+                        // question: always contribute to leaf or to currently active view cell?
                         if (0)
                                 viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());