Changeset 612 for trunk/VUT/GtpVisibilityPreprocessor/src

Timestamp:

02/12/06 21:45:02 (19 years ago)

Author:

mattausch

Message:

really last checkin before svn change

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• Environment.cpp (modified) (1 diff)
• ViewCell.cpp (modified) (10 diffs)
• ViewCellsManager.cpp (modified) (5 diffs)
• VspBspTree.cpp (modified) (33 diffs)
• VspBspTree.h (modified) (4 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1856 +1856 @@
                 "1.5");
 
+        RegisterOption("VspBspTree.useCostHeuristics",
+                optBool,
+                "-vsp_bsp_use_cost_heuristics=",
+                "false");
+
         RegisterOption("VspBspTree.Termination.maxViewCells",
                 optInt,

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -18 +18 @@
 {
 public:
-        
         //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
         bool operator() (T v1, T v2) const
@@ -508 +507 @@
                    << "#TotalPvs\n" << totalPvs << endl
                    << "#PvsSizeDecrease\n0" << endl
-                   << "#Volume\n" << endl
-                   << "#Siblings\n" << mergeStats.siblings << endl;
+                   << "#Volume\n0" << endl
+                   //<< "#Siblings\n" << mergeStats.siblings << endl
+                   << endl;
 
         //-- use priority queue to merge leaf pairs
 // HACK
+
         //const float maxAvgCost = 350;
         while (!mMergeQueue.empty())//NumActiveViewCells > mMergeMinViewCells))
@@ -549 +550 @@
                                 ResetMergeQueue();
 
-                        
                         Debug << "Values after reset: "  
                                   << " erc: " << mExpectedCost 
@@ -562 +562 @@
 
 
-        
                 MergeCandidate mc = mMergeQueue.top();
                 mMergeQueue.pop();
@@ -604 +603 @@
                         mergedVc->SetMergeCost(totalRenderCost);
 
-                        if (mViewCellsManager->EqualToSpatialNode(mergedVc))
-                                ++ mergeStats.siblings;
+                        //if (mViewCellsManager->EqualToSpatialNode(mergedVc))
+                        //      ++ mergeStats.siblings;
                         mergedVc->SetCost(realExpectedCost);
 
@@ -616 +615 @@
                                         << "#Pass\n" << pass << endl
                                         << "#Merged\n" << mergeStats.merged << endl 
-                                        << "#Viewcells\n" << realNumActiveViewCells << endl 
+                                        << "#ViewCells\n" << realNumActiveViewCells << endl 
                     << "#RenderCostIncrease\n" << renderCostIncr << endl
                                         << "#TotalRenderCost\n" << totalRenderCost << endl
@@ -625 +624 @@
                                         << "#TotalPvs\n" << totalPvs << endl
                                         << "#PvsSizeDecrease\n" << -pvsDiff << endl
-                                        << "#Volume\n" << mergedVc->GetVolume() << endl;
+                                        << "#Volume\n" << mergedVc->GetVolume() << endl
+                                        << endl;
+                                
                         }
                 }
@@ -638 +639 @@
                         }
                 }
+                
         }
 
@@ -659 +661 @@
                 Debug << "creating root of view cell hierarchy for " 
                           << (int)activeViewCells.size() << " view cells" << endl;
-                /*for (int i = 0;  i < activeViewCells.size(); ++ i){
-                        Debug << "parent " << activeViewCells[i]->GetParent() << endl;
-                        Debug << "viewcell " << activeViewCells[i] << endl;
-                }*/
+                
                 ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
                 root->SetMergeCost(totalRenderCost);
@@ -668 +667 @@
                 root->SetCost(0.0f);
                 
+                mStats 
+                        << "#Pass\n" << pass << endl
+                        << "#Merged\n" << mergeStats.merged << endl 
+                        << "#ViewCells\n" << realNumActiveViewCells << endl 
+            << "#RenderCostIncrease\n" << 0 << endl // TODO
+                        << "#TotalRenderCost\n" << totalRenderCost << endl
+                        << "#CurrentPvs\n" << root->GetPvs().GetSize() << endl
+            << "#ExpectedCost\n" << realExpectedCost << endl
+                        << "#AvgRenderCost\n" << realAvgRenderCost << endl
+                        << "#Deviation\n" << mDeviation << endl
+                        << "#TotalPvs\n" << totalPvs << endl
+                        << "#PvsSizeDecrease\n" << 0 << endl // TODO
+                        << "#Volume\n" << root->GetVolume() << endl
+                        << endl;
+
                 mRoot = root;
         }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -16 +16 @@
 #include "RssPreprocessor.h"
 
-#define SAMPLE_AFTER_SUBDIVISION 1
+#define SAMPLE_AFTER_SUBDIVISION 0
 
 
@@ -2502 +2502 @@
         Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
 
-        if (1) // export initial view cells
+        if (0) // export initial view cells
         {
                 cout << "exporting initial view cells (=leaves) ... ";
@@ -2580 +2580 @@
         
         //BspLeaf::NewMail();
-        if (1) // export merged view cells
+        if (0) // export merged view cells
         {
                 mColorCode = 0;
@@ -2617 +2617 @@
         }
 
-        if (1) // export merged view cells
+        if (0) // export merged view cells using pvs coding
         {
                 mColorCode = 1;
@@ -2909 +2909 @@
 
         
-        if (1) // export view cells
-        {// hack pvs
+        if (0) // export view cells
+        {       // hack pvs
                 int savedColorCode = mColorCode;
                 mColorCode = 1;

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -124 +124 @@
         mSubdivisionStats.open("subdivisionStats.log");
 
+        environment->GetBoolValue("VspBspTree.useCostHeuristics", mUseCostHeuristics);
+
 
         //-- debug output
@@ -393 +395 @@
 
 
-// return memory usage in MB
+// TODO: return memory usage in MB
 float VspBspTree::GetMemUsage(/*const VspBspTraversalQueue &tstack*/) const
 {
@@ -454 +456 @@
 
         long startTime = GetTime();     
+        int nLeaves = 0;
+        int nViewCells = 0;
 
         // used for intermediate time measurements and progress
@@ -460 +464 @@
         mOutOfMemory = false;
 
-        int nleaves = 500;
-
+        mCreatedViewCells = 0;
+        
         while (!tQueue.empty())
         {
@@ -485 +489 @@
                                   << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 
-                if (mBspStats.Leaves() >= nleaves)
-                {
-                        nleaves += 500;
-                                
+                if (mBspStats.Leaves() == nLeaves)
+                {
+                        nLeaves += 500;
+
                         cout << "leaves=" << mBspStats.Leaves() << endl;
                         Debug << "needed "
                                   << TimeDiff(interTime, GetTime())*1e-3 
-                                  << " secs to create 500 leaves" << endl;
+                                  << " secs to create 500 view cells" << endl;
                         interTime = GetTime();
+                }
+
+                if (mCreatedViewCells == nViewCells)
+                {
+                        nViewCells += 500;
+
+                        cout << "generated " << mCreatedViewCells << " viewcells" << endl;
                 }
         }
@@ -530 +541 @@
                 VspBspTraversalData tFrontData;
                 VspBspTraversalData tBackData;
+
 #if OCTREE_HACK
                 //Debug << "new axis:" << (tData.mAxis + 1) % 3 << endl;
-
                 tFrontData.mAxis = (tData.mAxis + 1) % 3;
                 tBackData.mAxis = (tData.mAxis + 1) % 3;
@@ -593 +604 @@
                                 leaf->mVssRays.push_back((*it).mRay);
                 }
+
                 // should I check here?
                 if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize()))
@@ -634 +646 @@
         int maxCostMisses = tData.mMaxCostMisses;
 
+        int splitAxis;
+
         const bool success = 
-                SelectPlane(splitPlane, leaf, tData, frontData, backData);
+                SelectPlane(splitPlane, leaf, tData, frontData, backData, splitAxis);
 
         if (!success)
@@ -648 +662 @@
                 }
         }
+
+        //! error also computed if cost ratio is missed
+        if (splitAxis < 3)
+                ++ mBspStats.splits[splitAxis];
+        else
+                ++ mBspStats.polySplits;
 
         mBspStats.nodes += 2;
@@ -792 +812 @@
         // creates a sorted split candidates array
         if (mSplitCandidates->capacity() > 500000 &&
-                requestedSize < (int)(mSplitCandidates->capacity()/10) )
+                requestedSize < (int)(mSplitCandidates->capacity()  / 10) )
         {
         delete mSplitCandidates;
@@ -801 +821 @@
 
         // insert all queries
-        for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
-        {
-                bool positive = (*ri).mRay->HasPosDir(axis);
+        for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
+        {
+                const bool positive = (*ri).mRay->HasPosDir(axis);
                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
                                                                                                   (*ri).ExtrapOrigin(axis), (*ri).mRay));
@@ -821 +841 @@
                                           float &position)
 {
-        int raysBack;
-        int raysFront;
-        int pvsBack;
-        int pvsFront;
-
         SortSplitCandidates(rays, axis);
 
@@ -832 +847 @@
         // C = ct_div_ci  + (ql*rl + qr*rr)/queries
 
-        int rl = 0, rr = (int)rays.size();
-        int pl = 0, pr = pvsSize;
+        int pvsl = 0, pvsr = pvsSize;
+
+        int pvsBack = pvsl;
+        int pvsFront = pvsr;
 
         float minBox = box.Min(axis);
@@ -839 +856 @@
         float sizeBox = maxBox - minBox;
 
-        float minBand = minBox + 0.1f*(maxBox - minBox);
-        float maxBand = minBox + 0.9f*(maxBox - minBox);
-
-        float sum = rr*sizeBox;
+        float minBand = minBox + 0.1f * (maxBox - minBox);
+        float maxBand = minBox + 0.9f * (maxBox - minBox);
+
+        float sum = (float)pvsSize * sizeBox;
         float minSum = 1e20f;
 
         Intersectable::NewMail();
 
-        // set all object as belonging to the fron pvs
-        for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
-        {
-                if ((*ri).mRay->IsActive())
-                {
-                        Intersectable *object = (*ri).mRay->mTerminationObject;
-
-                        if (object)
-                        {
-                                if (!object->Mailed())
-                                {
-                                        object->Mail();
-                                        object->mCounter = 1;
-                                }
-                                else
-                                        ++ object->mCounter;
+        RayInfoContainer::const_iterator ri, ri_end = rays.end();
+
+        // set all object as belonging to the front pvs
+        for(ri = rays.begin(); ri != ri_end; ++ ri)
+        {
+                Intersectable *oObject = (*ri).mRay->mOriginObject;
+                Intersectable *tObject = (*ri).mRay->mTerminationObject;
+
+                if (oObject)
+                {
+                        if (!oObject->Mailed())
+                        {
+                                oObject->Mail();
+                                oObject->mCounter = 1;
+                        }
+                        else
+                        {
+                                ++ oObject->mCounter;
+                        }
+                }
+                if (tObject)
+                {
+                        if (!tObject->Mailed())
+                        {
+                                tObject->Mail();
+                                tObject->mCounter = 1;
+                        }
+                        else
+                        {
+                                ++ tObject->mCounter;
                         }
                 }
@@ -869 +900 @@
         Intersectable::NewMail();
 
-        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
-                ci < mSplitCandidates->end(); ++ ci)
+        vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
+
+        for (ci = mSplitCandidates->begin(); ci < ci_end; ++ ci)
         {
                 VssRay *ray;
+                ray = (*ci).ray;
+                
+                Intersectable *oObject = ray->mOriginObject;
+                Intersectable *tObject = ray->mTerminationObject;
+                
 
                 switch ((*ci).type)
@@ -878 +915 @@
                         case SortableEntry::ERayMin:
                                 {
-                                        ++ rl;
-                                        ray = (VssRay *) (*ci).ray;
-
-                                        Intersectable *object = ray->mTerminationObject;
-
-                                        if (object && !object->Mailed())
+                                        if (oObject && !oObject->Mailed())
                                         {
-                                                object->Mail();
-                                                ++ pl;
+                                                oObject->Mail();
+                                                ++ pvsl;
+                                        }
+                                        if (tObject && !tObject->Mailed())
+                                        {
+                                                tObject->Mail();
+                                                ++ pvsl;
                                         }
                                         break;
@@ -892 +929 @@
                         case SortableEntry::ERayMax:
                                 {
-                                        -- rr;
-                                        ray = (VssRay *) (*ci).ray;
-
-                                        Intersectable *object = ray->mTerminationObject;
-
-                                        if (object)
+                                        if (oObject)
                                         {
-                                                if (-- object->mCounter == 0)
-                                                        -- pr;
+                                                if (-- oObject->mCounter == 0)
+                                                        -- pvsr;
+                                        }
+
+                                        if (tObject)
+                                        {
+                                                if (-- tObject->mCounter == 0)
+                                                        -- pvsr;
                                         }
 
@@ -910 +948 @@
                 if ((*ci).value > minBand && (*ci).value < maxBand)
                 {
-                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
+                        sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
 
                         //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
@@ -920 +958 @@
                                 position = (*ci).value;
 
-                                raysBack = rl;
-                                raysFront = rr;
-
-                                pvsBack = pl;
-                                pvsFront = pr;
-
-                        }
-                }
-        }
-
-        float oldCost = (float)pvsSize;
-        float newCost = mCtDivCi + minSum / sizeBox;
-        float ratio = newCost / oldCost;
+                                pvsBack = pvsl;
+                                pvsFront = pvsr;
+                        }
+                }
+        }
+
+        // -- compute cost
+
+        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+        const float pOverall = sizeBox;
+
+        const float pBack = position - minBox;
+        const float pFront = maxBox - position;
+        
+        const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+        
+        const float oldRenderCost = penaltyOld * pOverall;
+        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+        float ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small);
 
         //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
@@ -950 +999 @@
                                                                                  const bool useKdSplit)
 {
-        const bool useCostHeuristics = false;
-
-        //-- regular split
         float nPosition[3];
         float nCostRatio[3];
@@ -960 +1006 @@
         BspNodeGeometry *nFrontGeom[3];
         BspNodeGeometry *nBackGeom[3];
+
+        for (int i = 0; i < 3; ++ i)
+        {
+                nFrontGeom[i] = NULL;
+                nBackGeom[i] = NULL;
+        }
 
         int bestAxis = -1;
@@ -990 +1042 @@
         for (axis = 0; axis < 3; ++ axis)
         {
-                nFrontGeom[axis] = new BspNodeGeometry();
-                nBackGeom[axis] = new BspNodeGeometry();
-
                 if (!mOnlyDrivingAxis || (axis == sAxis))
                 {
-                        if (!useCostHeuristics)
-                        {
+                        if (!mUseCostHeuristics)
+                        {
+                                nFrontGeom[axis] = new BspNodeGeometry();
+                                nBackGeom[axis] = new BspNodeGeometry();
+
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
                                 Vector3 normal(0,0,0); normal[axis] = 1.0f;
@@ -1042 +1094 @@
                                 bestAxis = axis;
                         }
-
                         else if (nCostRatio[axis] < nCostRatio[bestAxis])
                         {
@@ -1061 +1112 @@
 
         // and delete other geometry
-        delete nFrontGeom[(bestAxis + 1) % 3];
-        delete nBackGeom[(bestAxis + 2) % 3];
+        DEL_PTR(nFrontGeom[(bestAxis + 1) % 3]);
+        DEL_PTR(nBackGeom[(bestAxis + 2) % 3]);
 
         //-- split plane
@@ -1076 +1127 @@
                                                          VspBspTraversalData &data,
                                                          VspBspTraversalData &frontData,
-                                                         VspBspTraversalData &backData)
+                                                         VspBspTraversalData &backData,
+                                                         int &splitAxis)
 {
         // simplest strategy: just take next polygon
@@ -1150 +1202 @@
         float pFront, pBack;
 
-        candidateCost = SelectAxisAlignedPlane(plane, data, axis,
-                                                                                   &fGeom, &bGeom, 
-                                                                                   pFront, pBack,
+        candidateCost = SelectAxisAlignedPlane(plane, 
+                                                                                   data, 
+                                                                                   axis,
+                                                                                   &fGeom, 
+                                                                                   &bGeom, 
+                                                                                   pFront, 
+                                                                                   pBack,
                                                                                    data.mIsKdNode);      
 
-        bool isAxisAlignedSplit = false;
+        splitAxis = 3;
 
         if (candidateCost < lowestCost)
@@ -1161 +1217 @@
                 bestPlane = plane;
                 lowestCost = candidateCost;
-
+                splitAxis = axis;
                 // assign already computed values
                 // we can do this because we always save the
                 // computed values from the axis aligned splits         
-                frontData.mGeometry = fGeom;
-                backData.mGeometry = bGeom;
-        
-                frontData.mProbability = pFront;
-                backData.mProbability = pBack;
-                
-                //! error also computed if cost ratio is missed
-                ++ mBspStats.splits[axis];
-                isAxisAlignedSplit = true;
+                if (fGeom && bGeom)
+                {
+                        frontData.mGeometry = fGeom;
+                        backData.mGeometry = bGeom;
+        
+                        frontData.mProbability = pFront;
+                        backData.mProbability = pBack;
+                }
         }
         else
@@ -1181 +1236 @@
         }
 
-        frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);
+        frontData.mIsKdNode = backData.mIsKdNode = 
+                (data.mIsKdNode && splitAxis < 3);
 
 #ifdef _DEBUG
@@ -1401 +1457 @@
                 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
                         
-                const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
+                const float oldRenderCost = pOverall * penaltyOld;
                 const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
 
@@ -1420 +1476 @@
                                 fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
 
-                        const float oldDeviation = penaltyOld + Limits::Small;
+                        const float oldDeviation = penaltyOld;
 
                         newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
@@ -1426 +1482 @@
                 }
 
-                cost += mPvsFactor * newCost / oldCost;
+                cost += mPvsFactor * newCost / (oldCost + Limits::Small);
                 
         }
@@ -1656 +1712 @@
         mBspStats.accumDepth += data.mDepth;
 
+        ++ mCreatedViewCells;
 #ifdef _DEBUG
         Debug << "BSP stats: "
@@ -1666 +1723 @@
 #endif
 }
+
 
 int VspBspTree::CastRay(Ray &ray)

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -127 +127 @@
                 float GetCost() const
                 {
-#if 0
+#if 1
                         return mPvs * mProbability;
 #endif
-#if 1
+#if 0
                         return (float) (-mDepth); // for regular grid
 #endif
@@ -398 +398 @@
                                          VspBspTraversalData &data,
                                          VspBspTraversalData &frontData,
-                                         VspBspTraversalData &backData);
+                                         VspBspTraversalData &backData,
+                                         int &splitAxis);
         
         /** Strategies where the effect of the split plane is tested
@@ -627 +628 @@
         /// box around the whole view domain
         AxisAlignedBox3 mBox;
+
+        bool mUseCostHeuristics;
 
         /// minimal number of rays before subdivision termination
@@ -721 +724 @@
         int mTimeStamp;
 
+        int mCreatedViewCells;
+
 private: