Changeset 653

Timestamp:

02/18/06 22:06:33 (18 years ago)

Author:

mattausch

Message:

implemented split queue (but not tested yet!)

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• VspBspTree.cpp (modified) (13 diffs)
• VspBspTree.h (modified) (5 diffs)

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

@@ -353 +353 @@
         }
         
-        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
+        Debug << "maximal pvs (i.e., pvs still considered as valid) : " 
+                  << mViewCellsManager->GetMaxPvsSize() << endl;
 
         //-- store rays
@@ -521 +522 @@
 
 
+
+void VspBspTree::ConstructWithSplitQueueQueue(const PolygonContainer &polys, 
+                                                                                          RayInfoContainer *rays)
+{
+        VspBspSplitQueue tQueue;
+
+        mRoot = new BspLeaf();
+
+        // constrruct root node geometry
+        BspNodeGeometry *geom = new BspNodeGeometry();
+        ConstructGeometry(mRoot, *geom);
+
+        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
+
+        VspBspTraversalData tData(mRoot,
+                                                          new PolygonContainer(polys),
+                                                          0,
+                                                          rays,
+                              ComputePvsSize(*rays),
+                                                          prop,
+                                                          geom);
+
+        VspBspSplitCandidate splitCandidate;
+
+
+        EvalSplitCandidate(tData, splitCandidate);
+
+        tQueue.push(splitCandidate);
+
+
+        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
+        mTotalPvsSize = tData.mPvs;
+        
+        mSubdivisionStats 
+                        << "#ViewCells\n1\n" <<  endl
+                        << "#RenderCostDecrease\n0\n" << endl 
+                        << "#TotalRenderCost\n" << mTotalCost << endl
+                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
+
+        Debug << "total cost: " << mTotalCost << endl;
+        
+        
+        mBspStats.Start();
+        cout << "Contructing vsp bsp tree ... \n";
+
+        long startTime = GetTime();     
+        int nLeaves = 0;
+        int nViewCells = 0;
+
+        // used for intermediate time measurements and progress
+        long interTime = GetTime();     
+
+        mOutOfMemory = false;
+
+        mCreatedViewCells = 0;
+        
+        while (!tQueue.empty())
+        {
+                splitCandidate = tQueue.top();
+            tQueue.pop();               
+
+                if (0 && !mOutOfMemory)
+                {
+                        float mem = GetMemUsage();
+
+                        if (mem > mMaxMemory)
+                        {
+                                mOutOfMemory = true;
+                                Debug << "memory limit reached: " << mem << endl;
+                        }
+                }
+
+                // subdivide leaf node
+                BspNode *r = Subdivide(tQueue, splitCandidate);
+
+                if (r == mRoot)
+                        Debug << "VSP BSP tree construction time spent at root: "
+                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+
+                if (mBspStats.Leaves() == nLeaves)
+                {
+                        nLeaves += 500;
+
+                        cout << "leaves=" << mBspStats.Leaves() << endl;
+                        Debug << "needed "
+                                  << TimeDiff(interTime, GetTime())*1e-3 
+                                  << " secs to create 500 view cells" << endl;
+                        interTime = GetTime();
+                }
+
+                if (mCreatedViewCells == nViewCells)
+                {
+                        nViewCells += 500;
+
+                        cout << "generated " << mCreatedViewCells << " viewcells" << endl;
+                }
+        }
+
+        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
+        cout << "finished\n";
+
+        mBspStats.Stop();
+}
+
+
 bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
 {
@@ -555 +661 @@
                 // create new interior node and two leaf nodes
                 // or return leaf as it is (if maxCostRatio missed)
-                newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
-
-                if (!newNode->IsLeaf()) //-- continue subdivision
-                {
+
+                int splitAxis;
+                bool splitFurther = true;
+                int maxCostMisses = tData.mMaxCostMisses;
+                
+                Plane3 splitPlane;
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+
+                if (!SelectPlane(splitPlane, leaf, tData, tFrontData, tBackData, splitAxis))
+                {
+                        ++ maxCostMisses;
+
+                        if (maxCostMisses > mTermMissTolerance)
+                        {
+                                // terminate branch because of max cost
+                                ++ mBspStats.maxCostNodes;
+                                splitFurther = false;
+                        }
+                }
+        
+                if (splitFurther) //-- continue subdivision
+                {
+                        newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
+
+                        if (splitAxis < 3)
+                                ++ mBspStats.splits[splitAxis];
+                        else
+                                ++ mBspStats.polySplits;
+
+                        tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && splitAxis < 3);
+                        // how often was max cost ratio missed in this branch?
+                        tFrontData.mMaxCostMisses = maxCostMisses;
+                        tBackData.mMaxCostMisses = maxCostMisses;
+
                         if (1)
                         {
@@ -643 +779 @@
 
 
+BspNode *VspBspTree::Subdivide(VspBspSplitQueue &tQueue,
+                                                           VspBspSplitCandidate &splitCandidate)
+{
+        VspBspTraversalData &tData = splitCandidate.mParentData;
+
+        BspNode *newNode = tData.mNode;
+
+        if (!mOutOfMemory && !TerminationCriteriaMet(tData))
+        {
+                PolygonContainer coincident;
+
+                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;
+#endif
+                //-- continue subdivision
+                // create new interior node and two leaf node
+                const Plane3 splitPlane = splitCandidate.mSplitPlane;
+                        
+                newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
+
+#if 0 // TODO
+                        if (splitAxis < 3)
+                                ++ mBspStats.splits[splitAxis];
+                        else
+                                ++ mBspStats.polySplits;
+
+                        tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && splitAxis < 3);
+                        // how often was max cost ratio missed in this branch?
+                        tFrontData.mMaxCostMisses = maxCostMisses;
+                        tBackData.mMaxCostMisses = maxCostMisses;
+#endif
+                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();
+
+                        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;
+                }
+
+                //-- push the new split candidates on the stack
+                VspBspSplitCandidate frontCandidate;
+                VspBspSplitCandidate backCandidate;
+
+                EvalSplitCandidate(tData, frontCandidate);
+                EvalSplitCandidate(tData, backCandidate);
+
+                tQueue.push(frontCandidate);
+                tQueue.push(backCandidate);
+
+                // delete old leaf node
+                DEL_PTR(tData.mNode);
+        }
+
+        //-- terminate traversal and create new view cell
+        if (newNode->IsLeaf())
+        {
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+                BspViewCell *viewCell = new BspViewCell();
+                
+                leaf->SetViewCell(viewCell);
+        
+                //-- update pvs
+                int conSamp = 0;
+                float sampCon = 0.0f;
+                AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
+
+                mBspStats.contributingSamples += conSamp;
+                mBspStats.sampleContributions +=(int) sampCon;
+
+                //-- store additional info
+                if (mStoreRays)
+                {
+                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
+                        for (it = tData.mRays->begin(); it != it_end; ++ it)
+                        {
+                                (*it).mRay->Ref();                      
+                                leaf->mVssRays.push_back((*it).mRay);
+                        }
+                }
+
+                // should I check here?
+                viewCell->mLeaf = leaf;
+
+                if (mUseAreaForPvs)
+                        viewCell->SetArea(tData.mProbability);
+                else
+                        viewCell->SetVolume(tData.mProbability);
+
+                leaf->mProbability = tData.mProbability;
+
+                EvaluateLeafStats(tData);               
+        }
+
+        //-- cleanup
+        tData.Clear();
+
+        return newNode;
+}
+
+
 void VspBspTree::EvalSplitCandidate(VspBspTraversalData &tData,
                                                                         VspBspSplitCandidate &splitData)
@@ -663 +915 @@
 
 
-BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
-                                                                   VspBspTraversalData &frontData,
-                                                                   VspBspTraversalData &backData,
-                                                                   PolygonContainer &coincident)
+BspInterior *VspBspTree::SubdivideNode(const Plane3 &splitPlane,
+                                                                           VspBspTraversalData &tData,
+                                                                           VspBspTraversalData &frontData,
+                                                                           VspBspTraversalData &backData,
+                                                                           PolygonContainer &coincident)
 {
         BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
         
-        // select subdivision plane
-        Plane3 splitPlane;
-        
-        int splitAxis;
-
-        const bool success = 
-                SelectPlane(splitPlane, leaf, tData, frontData, backData, splitAxis);
-
-
-        int maxCostMisses = tData.mMaxCostMisses;
-
-        if (!success)
-        {
-                ++ maxCostMisses;
-
-                if (maxCostMisses > mTermMissTolerance)
-                {
-                        // terminate branch because of max cost
-                        ++ mBspStats.maxCostNodes;
-            return leaf;
-                }
-        }
-
         //-- the front and back traversal data is filled with the new values
         frontData.mDepth = tData.mDepth + 1;
@@ -702 +932 @@
         backData.mRays = new RayInfoContainer();
         
-        // subdivide rays
+
+        //-- subdivide rays
         SplitRays(splitPlane,
                           *tData.mRays,
@@ -708 +939 @@
                           *backData.mRays);
 
-
-        // how often was max cost ratio missed in this branch?
-        frontData.mMaxCostMisses = maxCostMisses;
-        backData.mMaxCostMisses = maxCostMisses;
 
         // compute pvs
@@ -753 +980 @@
 
 
-        if (splitAxis < 3)
-                ++ mBspStats.splits[splitAxis];
-        else
-                ++ mBspStats.polySplits;
+        ///////////////////////////////////////
+        // subdivide further
 
         mBspStats.nodes += 2;
 
-
-
-        ///////////////////////////////////////
-        
-        //-- subdivide further
+        
         BspInterior *interior = new BspInterior(splitPlane);
 
@@ -1221 +1442 @@
         }
 
-        // cost ratio miss
-        if (mUsePolygonSplitIfAvailable && !data.mPolygons->empty())
-        {
-                frontData.mIsKdNode = backData.mIsKdNode = false;
-                if (lowestCost > mTermMaxCostRatio)
-                        return false;
-
-                return true;
-        }
-
         //-- evaluate axis aligned splits
         int axis;
@@ -1236 +1447 @@
         float pFront, pBack;
 
-        candidateCost = SelectAxisAlignedPlane(plane, 
-                                                                                   data, 
-                                                                                   axis,
-                                                                                   &fGeom, 
-                                                                                   &bGeom, 
-                                                                                   pFront, 
-                                                                                   pBack,
-                                                                                   data.mIsKdNode);      
+        candidateCost = 99999999.0f;
+
+        // option: axis aligned split only if no polygon available
+        if (!mUsePolygonSplitIfAvailable || data.mPolygons->empty())
+        {
+                candidateCost = SelectAxisAlignedPlane(plane, 
+                                                                                           data, 
+                                                                                           axis,
+                                                                                           &fGeom, 
+                                                                                           &bGeom, 
+                                                                                           pFront, 
+                                                                                           pBack,
+                                                                                           data.mIsKdNode);      
+        }
 
         splitAxis = 3;
@@ -1252 +1469 @@
                 lowestCost = candidateCost;
                 splitAxis = axis;
+        
                 // assign already computed values
                 // we can do this because we always save the
                 // computed values from the axis aligned splits         
+
                 if (fGeom && bGeom)
                 {
@@ -1269 +1488 @@
                 DEL_PTR(bGeom);
         }
-
-        frontData.mIsKdNode = backData.mIsKdNode = 
-                (data.mIsKdNode && splitAxis < 3);
+        
 
 #ifdef _DEBUG
@@ -1277 +1494 @@
 #endif
 
-        // cost ratio miss
         if (lowestCost > mTermMaxCostRatio)
         {

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

@@ -171 +171 @@
                 float mRenderCost;
 
+                VspBspSplitCandidate(): mRenderCost(0) 
+                {};
+
                 VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 
-                mSplitPlane(plane), mParentData(tData)
+                mSplitPlane(plane), mParentData(tData), mRenderCost(0)
                 {}
 
@@ -395 +398 @@
                                                                  const VspBspTraversalData &data) const;
 
+        void ConstructWithSplitQueueQueue(const PolygonContainer &polys, RayInfoContainer *rays);
+
+
         /** Returns view cell corresponding to 
                 the invalid view space. If it does not exist, it is created.
@@ -424 +430 @@
         BspNode *Subdivide(VspBspTraversalQueue &tStack, 
                                            VspBspTraversalData &tData);
+
+        BspNode *Subdivide(VspBspSplitQueue &tQueue,
+                                           VspBspSplitCandidate &splitCandidate);
 
         /** Constructs the tree from the given traversal data.
@@ -459 +468 @@
                                                          float &pBack) const;
 
-        /** Subdivide leaf.
+        /** Subdivides leaf.
                 @param leaf the leaf to be subdivided
                 
@@ -473 +482 @@
         */
 
-        BspNode *SubdivideNode(VspBspTraversalData &tData,
-                                                   VspBspTraversalData &frontData,
-                                                   VspBspTraversalData &backData,
-                                                   PolygonContainer &coincident);
+        BspInterior *SubdivideNode(const Plane3 &splitPlane,
+                                                           VspBspTraversalData &tData,
+                                                           VspBspTraversalData &frontData,
+                               VspBspTraversalData &backData,
+                                                           PolygonContainer &coincident);
 
         /** Extracts the meshes of the objects and adds them to polygons.