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

Timestamp:

01/17/06 23:28:10 (18 years ago)

Author:

mattausch

Message:

 

File:

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

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -36 +36 @@
 
 float BspMergeCandidate::sOverallCost = 0;
+bool BspMergeCandidate::sUseArea = false;
 
 /********************************************************************/
@@ -43 +44 @@
 VspBspTree::VspBspTree():
 mRoot(NULL),
-mPvsUseArea(true),
+mUseAreaForPvs(false),
 mCostNormalizer(Limits::Small),
 mViewCellsManager(NULL),
 mOutOfBoundsCell(NULL),
-mShowInvalidSpace(false),
 mStoreRays(false)
 {
@@ -59 +59 @@
         environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
         environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
-        environment->GetFloatValue("VspBspTree.Termination.minArea", mTermMinArea);
+        environment->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
         environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
         environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
@@ -89 +89 @@
         environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
 
-        environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
 
         //-- termination criteria for axis aligned split
@@ -100 +99 @@
         environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
 
+        
+        mStats.open("bspStats.log");
+
         //-- debug output
         Debug << "******* VSP BSP options ******** " << endl;
     Debug << "max depth: " << mTermMaxDepth << endl;
         Debug << "min PVS: " << mTermMinPvs << endl;
-        Debug << "min area: " << mTermMinArea << endl;
+        Debug << "min probabiliy: " << mTermMinProbability << endl;
         Debug << "min rays: " << mTermMinRays << endl;
         Debug << "max ray contri: " << mTermMaxRayContribution << endl;
@@ -158 +160 @@
                 mOutOfBoundsCell = new BspViewCell();
                 mOutOfBoundsCell->SetId(-1);
-        }
+                mOutOfBoundsCell->SetValid(false);
+        }
+
         return mOutOfBoundsCell;
 }
@@ -311 +315 @@
                 }
         }
-
-        mMaxPvs = (int)(mMaxPvsRatio * (float)numObj);
-        
-        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mMaxPvs << endl;
+        
+        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -334 +336 @@
         }
 
-        mTermMinArea *= mBox.SurfaceArea(); // normalize
+        if (mUseAreaForPvs)
+                mTermMinProbability *= mBox.SurfaceArea(); // normalize
+        else 
+                mTermMinProbability *= mBox.GetVolume();
+
         mStat.polys = (int)polys.size();
 
@@ -372 +378 @@
         ConstructGeometry(mRoot, *geom);
 
+        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
+
         VspBspTraversalData tData(mRoot,
                                                           new PolygonContainer(polys),
@@ -377 +385 @@
                                                           rays,
                               ComputePvsSize(*rays),
-                                                          geom->GetArea(),
+                                                          prop,
                                                           geom);
 
@@ -386 +394 @@
 
         long startTime = GetTime();     
+        // used for intermediate time measurements
         long interTime = GetTime();     
+
         mOutOfMemory = false;
 
@@ -437 +447 @@
                 (((int)data.mRays->size() <= mTermMinRays) ||
                  (data.mPvs <= mTermMinPvs)   ||
-                 (data.mArea <= mTermMinArea) ||
+                 (data.mProbability <= mTermMinProbability) ||
                  (mStat.Leaves() >= mMaxViewCells) ||
                  (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
@@ -475 +485 @@
         {
                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
-                BspViewCell *viewCell;
-
-                if (!CheckValid(tData))
-                {
-                        leaf->SetTreeValid(false);
-                        PropagateUpValidity(leaf);
-                        // view cell for invalid view space
-                        viewCell = GetOrCreateOutOfBoundsCell();
-                        ++ mStat.invalidLeaves;
-                }
-                else
-                {       // create new view cell for this leaf                   
-                        viewCell = new BspViewCell();
-                }
+                BspViewCell *viewCell = new BspViewCell();
                 
                 leaf->SetViewCell(viewCell);
@@ -506 +503 @@
                                 leaf->mVssRays.push_back((*it).mRay);
                 }
-
-                viewCell->mLeaves.push_back(leaf);
-                viewCell->SetArea(tData.mArea);
-                leaf->mArea = tData.mArea;
+                
+                if (!mViewCellsManager->CheckValid(viewCell))
+                {
+                        viewCell->SetValid(false);
+
+                        leaf->SetTreeValid(false);
+                        PropagateUpValidity(leaf);
+
+                        ++ mStat.invalidLeaves;
+                }
+                
+        viewCell->mLeaves.push_back(leaf);
+
+                if (mUseAreaForPvs)
+                        viewCell->SetArea(tData.mProbability);
+                else
+                        viewCell->SetVolume(tData.mProbability);
+
+                leaf->mProbability = tData.mProbability;
 
                 EvaluateLeafStats(tData);               
@@ -591 +603 @@
 
         // split front and back node geometry and compute area
-        if (mPvsUseArea)
-        {
-                // if geometry was not already computed
-                if (!frontData.mGeometry && !backData.mGeometry)
-                {
-                        frontData.mGeometry = new BspNodeGeometry();
-                        backData.mGeometry = new BspNodeGeometry();
-
-                        tData.mGeometry->SplitGeometry(*frontData.mGeometry,
-                                                                                   *backData.mGeometry,
-                                                                                   interior->GetPlane(),
-                                                                                   mBox,
-                                                                                   mEpsilon);
+        
+        // if geometry was not already computed
+        if (!frontData.mGeometry && !backData.mGeometry)
+        {
+                frontData.mGeometry = new BspNodeGeometry();
+                backData.mGeometry = new BspNodeGeometry();
+
+                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
+                                                                           *backData.mGeometry,
+                                                                           interior->GetPlane(),
+                                                                           mBox,
+                                                                           mEpsilon);
                 
-                        //frontData.mArea = frontData.mGeometry->GetArea();
-                        //backData.mArea = backData.mGeometry->GetArea();
-                        frontData.mArea = frontData.mGeometry->GetVolume();
-                        backData.mArea = backData.mGeometry->GetVolume();
-                }
-        }
-        else
-        {
-                frontData.mArea = (float)frontData.mRays->size();
-                backData.mArea = (float)backData.mRays->size();
-        }
+                if (mUseAreaForPvs)
+                {
+                        frontData.mProbability = frontData.mGeometry->GetArea();
+                        backData.mProbability = backData.mGeometry->GetArea();
+                }
+                else
+                {
+                        frontData.mProbability = frontData.mGeometry->GetVolume();
+                        backData.mProbability = backData.mGeometry->GetVolume();
+                }
+        }
+        
 
         //-- create front and back leaf
@@ -836 +848 @@
                                                                                  BspNodeGeometry **frontGeom,
                                                                                  BspNodeGeometry **backGeom,
-                                                                                 float &frontArea,
-                                                                                 float &backArea,
-                                                                                 bool useKdSplit)
+                                                                                 float &pFront,
+                                                                                 float &pBack,
+                                                                                 const bool useKdSplit)
 {
         const bool useCostHeuristics = false;
@@ -845 +857 @@
         float nPosition[3];
         float nCostRatio[3];
-        float nFrontArea[3];
-        float nBackArea[3];
+        float nProbFront[3];
+        float nProbBack[3];
 
         BspNodeGeometry *nFrontGeom[3];
@@ -856 +868 @@
         AxisAlignedBox3 box;
         box.Initialize();
+        
         //TODO: for kd split geometry already is box
-        if (1 && mPvsUseArea)
+        if (1 && mUseAreaForPvs)
         {
                 PolygonContainer::const_iterator it, it_end = tData.mGeometry->mPolys.end();
@@ -872 +885 @@
         }
 
-        int sAxis = box.Size().DrivingAxis();
+        const int sAxis = box.Size().DrivingAxis();
 
         for (axis = 0; axis < 3; ++ axis)
@@ -885 +898 @@
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
                                 Vector3 normal(0,0,0); normal[axis] = 1.0f;
-                                
+
+                                // allows faster split because we have axis aligned kd tree boxes
                                 if (useKdSplit)
                                 {
@@ -891 +905 @@
                                                                                                                                 box,
                                                                                                                                 axis,
-                                                                                                                                nPosition[axis]);
+                                                                                                                                nPosition[axis],
+                                                                                                                                nProbFront[axis], 
+                                                                                                                                nProbBack[axis]);
                                         
                                         Vector3 pos;
                                         
                                         pos = box.Max(); pos[axis] = nPosition[axis];
-                                        const AxisAlignedBox3 backBox(box.Min(), pos);
-                                        backBox.ExtractPolys(nBackGeom[axis]->mPolys);
+                                        AxisAlignedBox3 bBox(box.Min(), pos);
+                                        bBox.ExtractPolys(nBackGeom[axis]->mPolys);
                                         
                                         pos = box.Min(); pos[axis] = nPosition[axis];
-                                        const AxisAlignedBox3 frontBox(pos, box.Max());
-                                        frontBox.ExtractPolys(nFrontGeom[axis]->mPolys);
-
+                                        AxisAlignedBox3 fBox(pos, box.Max());
+                                        fBox.ExtractPolys(nFrontGeom[axis]->mPolys);
                                 }
                                 else
@@ -908 +923 @@
                                         nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), 
                                                                                                           tData, *nFrontGeom[axis], *nBackGeom[axis],
-                                                                                                          nFrontArea[axis], nBackArea[axis]);
+                                                                                                          nProbFront[axis], nProbBack[axis]);
                                 }
                         }
@@ -936 +951 @@
         //-- assign values
         axis = bestAxis;
-        frontArea = nFrontArea[bestAxis];
-        backArea = nBackArea[bestAxis];
+        pFront = nProbFront[bestAxis];
+        pBack = nProbBack[bestAxis];
 
         // assign best split nodes geometry 
@@ -958 +973 @@
                                                                                    const AxisAlignedBox3 &box,
                                                                                    const int axis,
-                                                                                   const float &position) const
-{
+                                                                                   const float &position,                                                                                 
+                                                                                   float &pFront,
+                                                                                   float &pBack) const
+{
+        int pvsTotal = 0;
         int pvsFront = 0;
         int pvsBack = 0;
-        int pvsTotal = 0;
-
+        
         // create unique ids for pvs heuristics
         GenerateUniqueIdsForPvs();
@@ -984 +1001 @@
         }
 
-        //-- only one of these options should be one
-        //-- pvs + probability heuristics
-        float pBack, pFront, pOverall;
-
-        if (1)
-        {
+        //-- pvs heuristics
+        float pOverall;
+
+        // -- simplified computation for mid split
+        
+        
+        pOverall = data.mProbability;
+
+        if (!mUseAreaForPvs)
+        {   // volume
+                pBack = pFront = pOverall * 0.5f;
                 // box length substitute for probability
+#if 0
                 const float minBox = box.Min(axis);
                 const float maxBox = box.Max(axis);
@@ -997 +1020 @@
                 pFront = maxBox - position;
                 pOverall = maxBox - minBox;
+#endif
         }
         else //-- area substitute for probability
         {
-                pOverall = box.SurfaceArea();
-
-                const bool useMidSplit = true;
-                //const bool useMidSplit = false;       
-                                        
-                //-- simplified computation for mid split
                 const int axis2 = (axis + 1) % 3;
                 const int axis3 = (axis + 2) % 3;
@@ -1019 +1037 @@
         //Debug << pFront << " " << pBack << " " << pOverall << endl;
 
-        // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position);
         const float newCost = pvsBack * pBack + pvsFront * pFront;
-        //  float oldCost = leaf->mRays.size();
         const float oldCost = (float)pvsSize * pOverall;
 
@@ -1094 +1110 @@
         int axis;
         BspNodeGeometry *fGeom, *bGeom;
-        float fArea, bArea;
+        float pFront, pBack;
 
         candidateCost = SelectAxisAlignedPlane(plane, data, axis,
                                                                                    &fGeom, &bGeom, 
-                                                                                   fArea, bArea,
+                                                                                   pFront, pBack,
                                                                                    onlyAxisAligned);     
 
@@ -1109 +1125 @@
                 // we can do this because we always save the
                 // computed values from the axis aligned splits
+                
                 frontData.mGeometry = fGeom;
                 backData.mGeometry = bGeom;
-                frontData.mArea = fArea;
-                backData.mArea = bArea;
-
+        
+                frontData.mProbability = pFront;
+                backData.mProbability = pBack;
+                
                 //! error also computed if cost ratio is missed
                 ++ mStat.splits[axis];
@@ -1220 +1238 @@
                                                                  BspNodeGeometry &geomFront,
                                                                  BspNodeGeometry &geomBack,
-                                                                 float &areaFront,
-                                                                 float &areaBack) const
+                                                                 float &pFront,
+                                                                 float &pBack) const
 {
         float cost = 0;
@@ -1233 +1251 @@
         // probability that view point lies in back / front node
         float pOverall = 0;
-        float pFront = 0;
-        float pBack = 0;
+        pFront = 0;
+        pBack = 0;
 
         int raysFront = 0;
@@ -1290 +1308 @@
 
         const float raysSize = (float)data.mRays->size() + Limits::Small;
+
         if (mSplitPlaneStrategy & PVS)
         {
@@ -1295 +1314 @@
                 GenerateUniqueIdsForPvs();
 
-                if (mPvsUseArea) // use front and back cell areas to approximate volume
-                {
-                        // construct child geometry with regard to the candidate split plane
-                        data.mGeometry->SplitGeometry(geomFront,
-                                                                                  geomBack,
-                                                                                  candidatePlane,
-                                                                                  mBox,
-                                                                                  mEpsilon);
-
-                        
+                // construct child geometry with regard to the candidate split plane
+                data.mGeometry->SplitGeometry(geomFront,
+                                                                          geomBack,
+                                                                          candidatePlane,
+                                                                          mBox,
+                                                                          mEpsilon);
+
+                pOverall = data.mProbability;
+
+                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
+                {
                         pFront = geomFront.GetVolume();
-                        pBack = geomBack.GetVolume();
-                        //areaFront = geomFront.GetArea();
-                        //areaBack = geomBack.GetArea();
-
-                        pOverall = data.mArea;
-
-                }
-                else // use number of rays to approximate volume
-                {
-                        pOverall = (float)data.mRays->size();
-                        pFront = (float)raysFront;
-                        pBack = (float)raysBack;
+                        pBack = pOverall - geomFront.GetVolume();
+                }
+                else
+                {
+                        pFront = geomFront.GetArea();
+                        pBack = geomBack.GetArea();
                 }
         }
@@ -1471 +1485 @@
                 ++ mStat.maxRayContribNodes;
 
-        if (data.mArea <= mTermMinArea)
-                ++ mStat.minAreaNodes;
+        if (data.mProbability <= mTermMinProbability)
+                ++ mStat.minProbabilityNodes;
         
         // accumulate depth to compute average depth
@@ -1586 +1600 @@
 
 
-void VspBspTree::CollectViewCells(ViewCellContainer &viewCells) const
+void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
 {
         ViewCell::NewMail();
-        CollectViewCells(mRoot, viewCells, true);
+        CollectViewCells(mRoot, onlyValid, viewCells);
 }
 
@@ -1602 +1616 @@
         nodeStack.push(mRoot);
         
+        const bool addToUnbounded = false;
+
         while (!nodeStack.empty()) 
         {
@@ -1611 +1627 @@
                         BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
 
-                        if (node->TreeValid())
+                        if (!addToUnbounded && node->TreeValid())
                         {
                                 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
                         
-                                if (viewCell->GetPvs().GetSize() > mMaxPvs)
+                                if (!mViewCellsManager->CheckValid(viewCell))
                                 {
-                                        while (!viewCell->mLeaves.empty())
+                                        vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
+                                        for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
                                         {
-                                                BspLeaf *l = viewCell->mLeaves.back();
+                                                BspLeaf *l = *it;
+                                                
                                                 l->SetTreeValid(false);
+                                                PropagateUpValidity(l);
+                                                
+                                                if (addToUnbounded)
+                                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
+
                                                 ++ mStat.invalidLeaves;
-                                                PropagateUpValidity(l);
-
-                                                l->SetViewCell(GetOrCreateOutOfBoundsCell());
-                                                viewCell->mLeaves.pop_back();
                                         }
 
-                                        mOutOfBoundsCell->GetPvs().AddPvs(viewCell->GetPvs());
-
-                                        DEL_PTR(viewCell);
+                                        // add to unbounded view cell or set to invalid
+                                        if (addToUnbounded)
+                                        {
+                                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
+                                                DEL_PTR(viewCell);
+                                        }
+                                        else
+                                        {
+                                                viewCell->SetValid(false);
+                                        }
                                 }
                         }
@@ -1644 +1670 @@
 }
 
-void VspBspTree::CollectViewCells(BspNode *root, 
+
+void VspBspTree::CollectViewCells(BspNode *root,
+                                                                  bool onlyValid,
                                                                   ViewCellContainer &viewCells,
                                                                   bool onlyUnmailed) const
@@ -1662 +1690 @@
                 if (node->IsLeaf())
                 {
-                        if (!mShowInvalidSpace && node->TreeValid())
+                        if (!onlyValid ||node->TreeValid())
                         {
                                 ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
@@ -2357 +2385 @@
                 {
                 case -1:
-                        CollectViewCells(node, beam.mViewCells, true);
+                        CollectViewCells(node, true, beam.mViewCells, true);
                         break;
                 case 0:
@@ -2427 +2455 @@
 
         // set new size of view cell
-        vc->SetArea(fVc->GetArea() + bVc->GetArea());
-
+        if (mUseAreaForPvs)
+                vc->SetArea(fVc->GetArea() + bVc->GetArea());
+        else
+                vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
+        
         vector<BspLeaf *> fLeaves = fVc->mLeaves;
         vector<BspLeaf *> bLeaves = bVc->mLeaves;
@@ -2480 +2511 @@
 
                 BspMergeCandidate::sOverallCost += 
-                        leaf->mArea * leaf->mPvs->GetSize();
+                        leaf->mProbability * leaf->mPvs->GetSize();
 
                 // the same leaves must not be part of two merge candidates
@@ -2510 +2541 @@
         vector<BspRay *> bspRays;
 
+        ViewCell::NewMail();
         long startTime = GetTime();
         ConstructBspRays(bspRays, rays);
@@ -2525 +2557 @@
         {  
                 BspRay *ray = bspRays[i];
-          
+        
                 // traverse leaves stored in the rays and compare and 
                 // merge consecutive leaves (i.e., the neighbors in the tree)
@@ -2541 +2573 @@
 
                         BspMergeCandidate::sOverallCost += 
-                                leaf->mArea * leaf->mPvs->GetSize();
+                                leaf->mProbability * leaf->mPvs->GetSize();
                         
                         ++ numLeaves;
@@ -2566 +2598 @@
                                 
                                 BspMergeCandidate::sOverallCost += 
-                                        leaf->mArea * leaf->mPvs->GetSize();
+                                        leaf->mProbability * leaf->mPvs->GetSize();
 
                                 ++ numLeaves;
@@ -2585 +2617 @@
                                                 found = true; // already in queue
                         }
-                        
+                
                         if (!found)
                         {
@@ -2595 +2627 @@
                                 leaf->Mail();
                                 prevLeaf->Mail();
-
+                
                                 mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
                         }
@@ -2611 +2643 @@
         {
                 vector<BspLeaf *> leaves;
-                CollectLeaves(leaves, true, mMaxPvs);
+                CollectLeaves(leaves, true);
                 Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
                 CollectMergeCandidates(leaves);
@@ -2652 +2684 @@
                         //NOTE: not sorted!
                         for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+                        {
                                 ray->intersections.push_back(BspIntersection(0, *it));
+                        }
                 }
 
@@ -2660 +2694 @@
 
 
-int VspBspTree::MergeViewCells(const VssRayContainer &rays)
-{
-        BspMergeCandidate::sMaxPvsSize = mMaxPvs;
+int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
+{
+        BspMergeCandidate::sMaxPvsSize = mViewCellsManager->GetMaxPvsSize();
+        BspMergeCandidate::sUseArea = mUseAreaForPvs;
 
         MergeStatistics mergeStats;
@@ -2685 +2720 @@
 
         int nViewCells = mStat.Leaves() - mStat.invalidLeaves;
+        int pass = 0;
+        const int nextPass = 200;
 
         //-- use priority queue to merge leaf pairs
@@ -2704 +2741 @@
                 {
                         ViewCell::NewMail();
-        
+                        const float mergeCost = mc.GetMergeCost();
+
                         MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
                         -- nViewCells;
                         
-                        ++ mergeStats.merged;
                         
                         // increase absolute merge cost
                         BspMergeCandidate::sOverallCost += mc.GetMergeCost();
+
+                        
 
                         if (showMergeStats)
@@ -2723 +2762 @@
                                         mergeStats.maxTreeDist = dist;
                                 mergeStats.accTreeDist += dist;
+
+
+                                if ((mergeStats.merged % nextPass == 0) || (nViewCells == mMergeMinViewCells))
+                                {
+                                        mStats 
+                                                << "#Pass\n" << pass ++ << endl
+                                                << "#Merged\n" << mergeStats.merged << endl 
+                                                << "#Viewcells\n" << nViewCells << endl 
+                                                << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl 
+                                                << "#CurrentCost\n" << mergeCost << endl
+                                                << "#RelCost\n" << mc.GetMergeCost() / BspMergeCandidate::sOverallCost << endl
+                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl;
+
+                                        ViewCellContainer viewCells;    
+                                        CollectViewCells(mRoot, false, viewCells);
+                        
+                                        char s[64];
+                                        sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
+                                        Exporter *exporter = Exporter::GetExporter(s);
+                                
+                                        if (exporter)
+                                        {
+                                                Debug << "vc size " << viewCells.size() << endl;
+                                                ViewCellContainer::const_iterator it, it_end = viewCells.end();
+                
+                                                for (it = viewCells.begin(); it != it_end; ++ it)
+                                                {
+                                                        exporter->ExportGeometry(objects);
+                                                        mViewCellsManager->ExportVcGeometry(exporter, *it);
+                                                }
+                                        
+                                                delete exporter;
+                                        }
+                                }
                         }
+
                 }
                 // merge candidate not valid, because one of the leaves was already
@@ -2740 +2814 @@
                 Debug << mergeStats << endl << endl;
         
+
         //TODO: should return sample contributions?
         return mergeStats.merged;
@@ -2836 +2911 @@
 
 
-float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2)
+float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2, bool useArea)
 {
         //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
@@ -2842 +2917 @@
         const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
 
-        const float area1 = vc1->GetArea() - leaf->mArea;
-        const float area2 = vc2->GetArea() + leaf->mArea;
-
-        const float cost1 = pvs1 * area1;
-        const float cost2 = pvs2 * area2;
+        float p1, p2;
+
+    if (useArea)
+        {
+                p1 = vc1->GetArea() - leaf->mProbability;
+                p2 = vc2->GetArea() + leaf->mProbability;
+        }
+        else
+        {
+                p1 = vc1->GetVolume() - leaf->mProbability;
+                p2 = vc2->GetVolume() + leaf->mProbability;
+        }
+
+        const float cost1 = pvs1 * p1;
+        const float cost2 = pvs2 * p2;
 
         return cost1 + cost2;
@@ -2860 +2945 @@
         vc2->GetPvs().AddPvs(*leaf->mPvs);
         
-        vc1->SetArea(vc1->GetArea() - leaf->mArea);
-        vc2->SetArea(vc2->GetArea() + leaf->mArea);
+        if (mUseAreaForPvs)
+        {
+                vc1->SetArea(vc1->GetArea() - leaf->mProbability);
+                vc2->SetArea(vc2->GetArea() + leaf->mProbability);
+        }
+        else
+        {
+                vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);
+                vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);
+        }
 
         /// add to second view cell
@@ -2890 +2983 @@
         BspViewCell *vc2 = leaf2->GetViewCell();
 
-        const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
-        const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
+        float cost1; 
+        float cost2; 
+
+        if (mUseAreaForPvs)
+        {
+                cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
+                cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
+        }
+        else
+        {
+                cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();
+                cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();
+        }
 
         const float oldCost = cost1 + cost2;
@@ -2900 +3004 @@
         // the view cell should not be empty after the shuffle
         if (vc1->mLeaves.size() > 1)
-                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
+                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2, mUseAreaForPvs);
         if (vc2->mLeaves.size() > 1)
-                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
+                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1, mUseAreaForPvs);
 
         // shuffling unsuccessful
@@ -2921 +3025 @@
         return true;
 }
+
 
 bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
@@ -2952 +3057 @@
 
 
-bool VspBspTree::CheckValid(const VspBspTraversalData &data) const
-{
-        return data.mPvs <= mMaxPvs;
-}
-
-
 void VspBspTree::PropagateUpValidity(BspNode *node)
 {
@@ -3019 +3118 @@
 }
 
+
 float BspMergeCandidate::GetCost(ViewCell *vc) const
 {
-        return vc->GetPvs().GetSize() * vc->GetArea();
-}
+        if (sUseArea)
+                return vc->GetPvs().GetSize() * vc->GetArea();
+
+        return vc->GetPvs().GetSize() * vc->GetVolume();
+}
+
 
 float BspMergeCandidate::GetLeaf1Cost() const
@@ -3030 +3134 @@
 }
 
+
 float BspMergeCandidate::GetLeaf2Cost() const
 {
@@ -3035 +3140 @@
         return GetCost(vc);
 }
+
 
 void BspMergeCandidate::EvalMergeCost()
@@ -3050 +3156 @@
         const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
 
-        const float newCost =
-                (float)newPvs * (vc1->GetArea() + vc2->GetArea());
+    const float newCost = sUseArea ? 
+                (float)newPvs * (vc1->GetArea() + vc2->GetArea()) :
+                (float)newPvs * (vc1->GetVolume() + vc2->GetVolume());
+
 
         if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large