Changeset 600 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

Timestamp:

02/06/06 19:09:53 (18 years ago)

Author:

mattausch

Message:

 

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp (modified) (25 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -86 +86 @@
         //-- max cost ratio for early tree termination
         environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
-
+mTermMinPolygons = 25;
         //-- factors for bsp tree split plane heuristics
         environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
@@ -116 +116 @@
 
 
+        mSubdivisionStats.open("subdivisionStats.log");
 
 
@@ -387 +388 @@
 
 // return memory usage in MB
-float VspBspTree::GetMemUsage(/*const VspBspTraversalStack &tstack*/) const
+float VspBspTree::GetMemUsage(/*const VspBspTraversalQueue &tstack*/) const
 {
         return
@@ -402 +403 @@
 void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
 {
-        VspBspTraversalStack tStack;
+        VspBspTraversalQueue tQueue;
 
         mRoot = new BspLeaf();
@@ -426 +427 @@
                 tData.mIsKdNode = false;
 
-        tStack.push(tData);
-
+        tQueue.push(tData);
+
+        mTotalCost = tData.GetCost() / mBox.GetVolume();
+
+        Debug << "total cost: " << mTotalCost << endl;
+        mSplits = 0;
+        
         mBspStats.Start();
         cout << "Contructing vsp bsp tree ... \n";
@@ -440 +446 @@
         int nleaves = 500;
 
-        while (!tStack.empty())
-        {
-                tData = tStack.top();
-            tStack.pop();               
+        while (!tQueue.empty())
+        {
+                tData = tQueue.top();
+            tQueue.pop();               
 
                 if (0 && !mOutOfMemory)
@@ -457 +463 @@
 
                 // subdivide leaf node
-                BspNode *r = Subdivide(tStack, tData);
+                BspNode *r = Subdivide(tQueue, tData);
 
                 if (r == mRoot)
@@ -489 +495 @@
                  (data.mProbability <= mTermMinProbability) ||
                  (mBspStats.Leaves() >= mMaxViewCells) ||
+#if 0
+                 (((int)data.mPolygons->size() <= mTermMinPolygons) && !data.mPolygons->empty())||
+#endif
                  (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
@@ -494 +503 @@
 
 
-BspNode *VspBspTree::Subdivide(VspBspTraversalStack &tStack,
+BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
                                                            VspBspTraversalData &tData)
 {
@@ -512 +521 @@
                 if (!newNode->IsLeaf()) //-- continue subdivision
                 {
+                        if (1)
+                        {
+                                float costDecr = 
+                                        (tFrontData.GetCost() + tBackData.GetCost() - tData.GetCost()) / mBox.GetVolume();
+                                mTotalCost += costDecr;
+
+                                mSubdivisionStats 
+                                                << "#Nodes\n" << ++ mSplits << endl
+                                                << "#RenderCostDecrease\n" << -costDecr << endl 
+                                                << "#TotalRenderCost\n" << mTotalCost << endl;
+                        }
+
                         // push the children on the stack
-                        tStack.push(tFrontData);
-                        tStack.push(tBackData);
+                        tQueue.push(tFrontData);
+                        tQueue.push(tBackData);
 
                         // delete old leaf node
@@ -1341 +1362 @@
                         float oldCost, newCost;
 
+                        // only render cost
                         if (1)
                         {
@@ -1346 +1368 @@
                                 newCost = newRenderCost;
                         }
-                        else
+                        else // also considering standard deviation
                         {
                                 // standard deviation is difference of back and front pvs
@@ -1361 +1383 @@
 
                         cost += mPvsFactor * newCost / oldCost;
-                }
-                else
-                {
-                        //-- compute weighted sum of expected render cost and standard deviation
-                        
-                        //-- first compute expected render cost         
-                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
-                const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
-                        
-                        const float renderCostFront = penaltyFront * pFront;
-                        const float renderCostBack = penaltyBack * pBack;
-
-                        const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
-                        const float newRenderCost = renderCostFront + renderCostBack;
-
-
-                        //-- compute standard deviation
-                        const float expectedCost = 0.5f * (renderCostBack + renderCostFront);
-
-                        const float devFront = fabs(renderCostFront - expectedCost);
-                        
-                        const float devBack = fabs(renderCostBack - expectedCost);
-
-                        const float newDev = 0.5f * (devFront + devBack);
-                        const float oldDev = oldRenderCost * oldRenderCost;
-
-                        const float newCost = newRenderCost * mRenderCostWeight + newDev * (1.0f - mRenderCostWeight);
-                        const float oldCost = oldRenderCost * mRenderCostWeight + oldDev * (1.0f - mRenderCostWeight);
-
-                        cost += mPvsFactor * newCost / oldCost;
-
-                        // also try to equalize render differences between front and back pvs
-                        //const float oldCost = pOverall + Limits::Small;
-                        //float newCost = (float)abs(pvsFront - pvsBack);
-                        
                 }
         }
@@ -1404 +1390 @@
                   << " frontpvs: " << pvsFront << " pFront: " << pFront
                   << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
+        Debug << "cost: " << cost << endl;
 #endif
 
+        
         // normalize cost by sum of linear factors
         if(0)
@@ -1638 +1626 @@
         int hits = 0;
 
-        stack<BspRayTraversalData> tStack;
+        stack<BspRayTraversalData> tQueue;
 
         float maxt, mint;
@@ -1646 +1634 @@
 
         Intersectable::NewMail();
-
+        ViewCell::NewMail();
         Vector3 entp = ray.Extrap(mint);
         Vector3 extp = ray.Extrap(maxt);
@@ -1690 +1678 @@
 
                         // push data for far child
-                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
+                        tQueue.push(BspRayTraversalData(farChild, extp, maxt));
 
                         // find intersection of ray segment with plane
@@ -1709 +1697 @@
 
                         //-- fetch the next far child from the stack
-                        if (tStack.empty())
+                        if (tQueue.empty())
                                 break;
 
@@ -1718 +1706 @@
                                 break;
 
-                        BspRayTraversalData &s = tStack.top();
+                        BspRayTraversalData &s = tQueue.top();
 
                         node = s.mNode;
@@ -1724 +1712 @@
                         maxt = s.mMaxT;
 
-                        tStack.pop();
+                        tQueue.pop();
                 }
         }
@@ -2204 +2192 @@
         return (int)neighbors.size();
 }
+
+
+
+int VspBspTree::FindApproximateNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
+                                                                                 const bool onlyUnmailed) const
+{
+        stack<bspNodePair> nodeStack;
+        
+        BspNodeGeometry nodeGeom;
+        ConstructGeometry(n, nodeGeom);
+        
+        // split planes from the root to this node
+        // needed to verify that we found neighbor leaf
+        // TODO: really needed?
+        vector<Plane3> halfSpaces;
+        ExtractHalfSpaces(n, halfSpaces);
+
+
+        BspNodeGeometry *rgeom = new BspNodeGeometry();
+        ConstructGeometry(mRoot, *rgeom);
+
+        nodeStack.push(bspNodePair(mRoot, rgeom));
+
+        while (!nodeStack.empty())
+        {
+                BspNode *node = nodeStack.top().first;
+                BspNodeGeometry *geom = nodeStack.top().second;
+        
+                nodeStack.pop();
+
+                if (node->IsLeaf())
+                {
+                        // test if this leaf is in valid view space
+                        if (node->TreeValid() &&
+                                (node != n) && 
+                                (!onlyUnmailed || !node->Mailed()))
+                        {
+                                bool isAdjacent = true;
+
+                                // neighbor was found
+                                if (isAdjacent)
+                                {       
+                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
+                                }
+                        }
+                }
+                else
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+                        const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
+                                                                                                   interior->GetPlane(),
+                                                                                                   mEpsilon);
+                        
+                        BspNode *front = interior->GetFront();
+                        BspNode *back = interior->GetBack();
+            
+                        BspNodeGeometry *fGeom = new BspNodeGeometry();
+                        BspNodeGeometry *bGeom = new BspNodeGeometry();
+
+                        geom->SplitGeometry(*fGeom,
+                                                                *bGeom,
+                                                                interior->GetPlane(),
+                                                                mBox,
+                                                                mEpsilon);
+                
+                        if (cf == Polygon3::FRONT_SIDE)
+                        {
+                                nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
+                                DEL_PTR(bGeom);
+                        }
+                        else
+                        {
+                                if (cf == Polygon3::BACK_SIDE)
+                                {
+                                        nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
+                                        DEL_PTR(fGeom);
+                                }
+                                else
+                                {       // random decision
+                                        nodeStack.push(bspNodePair(front, fGeom));
+                                        nodeStack.push(bspNodePair(back, bGeom));
+                                }
+                        }
+                }
+        
+                DEL_PTR(geom);
+        }
+
+        return (int)neighbors.size();
+}
+
 
 
@@ -2378 +2458 @@
 {
         int hits = 0;
-        stack<BspRayTraversalData> tStack;
+        stack<BspRayTraversalData> tQueue;
 
         float mint = 0.0f, maxt = 1.0f;
 
         Intersectable::NewMail();
+        ViewCell::NewMail();
 
         Vector3 entp = origin;
@@ -2431 +2512 @@
 
                         // push data for far child
-                        tStack.push(BspRayTraversalData(farChild, extp));
+                        tQueue.push(BspRayTraversalData(farChild, extp));
 
                         // find intersection of ray segment with plane
@@ -2450 +2531 @@
 
                         //-- fetch the next far child from the stack
-                        if (tStack.empty())
+                        if (tQueue.empty())
                                 break;
 
                         entp = extp;
                         
-                        BspRayTraversalData &s = tStack.top();
+                        BspRayTraversalData &s = tQueue.top();
 
                         node = s.mNode;
                         extp = s.mExitPoint;
 
-                        tStack.pop();
+                        tQueue.pop();
                 }
         }
@@ -2711 +2792 @@
                 vector<BspLeaf *> neighbors;
                 FindNeighbors(leaf, neighbors, true);
-
+                //FindApproximateNeighbors(leaf, neighbors, true);
                 vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();