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

Timestamp:

12/30/05 12:08:15 (19 years ago)

Author:

mattausch

Message:

changed castlinesegment of vspbpstree
changed rayinfo ray classification for bsp tree
implemented shuffling

File:

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

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -33 +33 @@
 int VspBspTree::sFrontAndBackId = 0;
 
-float BspMergeCandidate::sOverallCost = Limits::Small;
+float BspMergeCandidate::sOverallCost = 0;
 
 /****************************************************************/
@@ -44 +44 @@
 mCostNormalizer(Limits::Small),
 mViewCellsManager(NULL),
-mStoreRays(true),
+mStoreRays(false),
 mOnlyDrivingAxis(false)
 {
-        mRootCell = new BspViewCell();
-
         Randomize(); // initialise random generator for heuristics
 
@@ -82 +80 @@
         environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
 
+        environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
+        environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
 
         //-- debug output
@@ -137 +137 @@
 {
         DEL_PTR(mRoot);
-        DEL_PTR(mRootCell);
         DEL_PTR(mSplitCandidates);
 }
@@ -216 +215 @@
                 {
                         mBox.Include(object->GetBox()); // add to BSP tree aabb
-                        AddMeshToPolygons(mesh, polys, mRootCell);
+                        AddMeshToPolygons(mesh, polys, NULL);
                 }
         }
@@ -360 +359 @@
                  (data.mPvs <= mTermMinPvs)   ||
                  (data.mArea <= mTermMinArea) ||
-                 (mStat.nodes / 2 + 1 >= mMaxViewCells) ||
+                 (mStat.Leaves() >= mMaxViewCells) ||
                 // (data.GetAvgRayContribution() >= mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
@@ -400 +399 @@
                 BspViewCell *viewCell = new BspViewCell();
                 leaf->SetViewCell(viewCell);
-
+                
                 if (mStoreRays)
                 {
@@ -410 +409 @@
                 viewCell->mLeaves.push_back(leaf);
                 viewCell->SetArea(tData.mArea);
+                leaf->mArea = tData.mArea;
 
                 //-- update pvs
                 int conSamp = 0, sampCon = 0;
                 AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
-
+        
                 mStat.contributingSamples += conSamp;
                 mStat.sampleContributions += sampCon;
@@ -1065 +1065 @@
                         // add the termination object
                         AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
-
                         // add the source object
                         AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
@@ -1081 +1080 @@
                                 if (cf == 1)
                                         pFront += len;
-                                if (cf == -1)
+                                else if (cf == -1)
                                         pBack += len;
-                                if (cf == 0)
+                                else if (cf == 0)
                                 {
                                         // use length of rays to approximate volume
@@ -1231 +1230 @@
                 mStat.maxDepth = data.mDepth;
 
+        if (data.mPvs > mStat.maxPvs)
+                mStat.maxPvs = data.mPvs;
         if (data.mDepth < mStat.minDepth)
                 mStat.minDepth = data.mDepth;
-
         if (data.mDepth >= mTermMaxDepth)
                 ++ mStat.maxDepthNodes;
@@ -1436 +1436 @@
                 float t;
 
-                        // get classification and receive new t
+                // get classification and receive new t
                 const int cf = bRay.ComputeRayIntersection(plane, t);
 
@@ -1448 +1448 @@
                         break;
                 case 0:
-                        //-- split ray
-                        //--  look if start point behind or in front of plane
-                        if (plane.Side(bRay.ExtrapOrigin()) <= 0)
                         {
-                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
-                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
-                        }
-                        else
-                        {
-                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
-                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+                                //-- split ray
+                                //-- test if start point behind or in front of plane
+                                const int side = plane.Side(bRay.ExtrapOrigin());
+
+                                if (side <= 0)
+                                {
+                                        backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
+                                        frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+                                }
+                                else
+                                {
+                                        frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
+                                        backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+                                }
                         }
                         break;
                 default:
-                        Debug << "Should not come here 4" << endl;
+                        Debug << "Should not come here" << endl;
                         break;
                 }
@@ -1497 +1501 @@
 }
 
+
 void VspBspTree::ConstructGeometry(BspNode *n,
                                                                    BspNodeGeometry &cell) const
 {
-        PolygonContainer polys;
-        ConstructGeometry(n, polys);
-        cell.mPolys = polys;
-}
+        ConstructGeometry(n, cell.mPolys);
+}
+
 
 void VspBspTree::ConstructGeometry(BspNode *n,
@@ -1588 +1592 @@
 }
 
-void VspBspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &vcGeom) const
+
+void VspBspTree::ConstructGeometry(BspViewCell *vc, 
+                                                                   PolygonContainer &vcGeom) const
 {
         vector<BspLeaf *> leaves = vc->mLeaves;
-
         vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
 
@@ -1598 +1603 @@
 }
 
+
 int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
                                                    const bool onlyUnmailed) const
 {
         PolygonContainer cell;
-
         ConstructGeometry(n, cell);
 
@@ -1794 +1799 @@
 }
 
-BspViewCell *VspBspTree::GetRootCell() const
-{
-        return mRootCell;
-}
 
 int VspBspTree::SplitPolygons(const Plane3 &plane,
@@ -1858 +1859 @@
         BspNode *farChild = NULL;
 
+        float t;
         while (1)
         {
@@ -1865 +1867 @@
 
                         Plane3 splitPlane = in->GetPlane();
+                        
                         const int entSide = splitPlane.Side(entp);
                         const int extSide = splitPlane.Side(extp);
 
-                        if (entSide < 0)
+                        if (entSide < 0) 
                         {
                                 node = in->GetBack();
-
-                                if (extSide <= 0) // plane does not split ray => no far child
+                                // plane does not split ray => no far child
+                                if (extSide <= 0) 
                                         continue;
 
                                 farChild = in->GetFront(); // plane splits ray
-                        } else if (entSide > 0)
+                        } 
+                        else if (entSide > 0)
                         {
                                 node = in->GetFront();
@@ -1885 +1889 @@
                                 farChild = in->GetBack(); // plane splits ray
                         }
-                        else // ray and plane are coincident
-                        {
-                                // WHAT TO DO IN THIS CASE ?
-                                //break;
-                                node = in->GetFront();
-                                continue;
+                        else // ray end point on plane
+                        {       // NOTE: what to do if ray is coincident with plane?
+                                if (extSide < 0)
+                                        node = in->GetBack();
+                                else if (extSide > 0)
+                                        node = in->GetFront();
+
+                                continue; // no far child
                         }
 
                         // push data for far child
-                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
+                        tStack.push(BspRayTraversalData(farChild, extp));
 
                         // find intersection of ray segment with plane
-                        float t;
                         extp = splitPlane.FindIntersection(origin, extp, &t);
-                        maxt *= t;
-
-                } else
+                } 
+                else
                 {
                         // reached leaf => intersection with view cell
@@ -1918 +1922 @@
 
                         entp = extp;
-                        mint = maxt; // NOTE: need this?
-
-
+                        
                         BspRayTraversalData &s = tStack.top();
 
                         node = s.mNode;
                         extp = s.mExitPoint;
-                        maxt = s.mMaxT;
 
                         tStack.pop();
                 }
         }
+
         return hits;
 }
 
-int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2)
+int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const
 {
         std::deque<BspNode *> path1;
@@ -1997 +1999 @@
                 }
         }
+
+        // revalidate leaves
+        RepairVcLeafLists();
 
         return node;
@@ -2040 +2045 @@
 
 
-int VspBspTree::MergeLeaves()
-{
-        vector<BspLeaf *> leaves;
-        priority_queue<BspMergeCandidate> mergeQueue;
-
-        // collect the leaves, e.g., the "voxels" that will build the view cells
-        CollectLeaves(leaves);
-
-        int vcSize = (int)leaves.size();
-        int savedVcSize = vcSize;
-
-        BspLeaf::NewMail();
-
-        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
-
-        // find merge candidates and push them into queue
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                BspLeaf *leaf = *it;
-
-                // no leaf is part of two merge candidates
-                if (!leaf->Mailed())
-                {
-                        leaf->Mail();
-
-                        vector<BspLeaf *> neighbors;
-                        FindNeighbors(leaf, neighbors, true);
-
-                        vector<BspLeaf *>::const_iterator nit,
-                                nit_end = neighbors.end();
-
-                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
-                        {
-                                BspMergeCandidate mc = BspMergeCandidate(leaf, *nit);
-                                mergeQueue.push(mc);
-
-                                BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
-                                BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
-                        }
-                }
-        }
-
-        int merged = 0;
-        int mergedSiblings = 0;
-        int accTreeDist = 0;
-        int maxTreeDist = 0;
-        const bool mergeStats = true;
-
-
-        //-- use priority queue to merge leaf pairs
-        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
-                   (mergeQueue.top().GetMergeCost() <
-                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-        {
-                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
-                BspMergeCandidate mc = mergeQueue.top();
-                mergeQueue.pop();
-
-                // both view cells equal!
-                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-                        continue;
-
-                if (mc.Valid())
-                {
-                        ViewCell::NewMail();
-                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-                        -- vcSize;
-                        // increase absolute merge cost
-                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
-
-                        //-- stats
-                        ++ merged;
-
-                        if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-                                ++ mergedSiblings;
-
-                        if (mergeStats)
-                        {
-                                const int dist = TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-
-                                if (dist > maxTreeDist)
-                                        maxTreeDist = dist;
-
-                                accTreeDist += dist;
-                        }
-                }
-                // merge candidate not valid, because one of the leaves was already
-                // merged with another one
-                else
-                {
-                        // validate and reinsert into queue
-                        mc.SetValid();
-                        mergeQueue.push(mc);
-                        //Debug << "validate " << mc.GetMergeCost() << endl;
-                }
-        }
-
-        // collapse tree according to view cell partition
-        CollapseTree(mRoot);
-        // revalidate leaves
-        RepairVcLeafLists();
-
-        Debug << "Merged " << merged << " nodes of " << savedVcSize
-                  << " (merged " << mergedSiblings << " siblings)" << endl;
-
-        if (mergeStats)
-        {
-                Debug << "maximal tree distance: " << maxTreeDist << endl;
-                Debug << "Avg tree distance: " << (float)accTreeDist / (float)merged << endl;
-        }
-
-        //TODO: should return sample contributions
-        return merged;
-}
-
-
-bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2)
+bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) const
 {
         //-- change pointer to view cells of all leaves associated
@@ -2204 +2093 @@
         mViewCellsManager = vcm;
 }
+
+
+int VspBspTree::CollectMergeCandidates()
+{
+        vector<BspLeaf *> leaves;
+
+        // collect the leaves, e.g., the "voxels" that will build the view cells
+        CollectLeaves(leaves);
+        BspLeaf::NewMail();
+
+        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+        // find merge candidates and push them into queue
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspLeaf *leaf = *it;
+                
+                /// create leaf pvs (needed for post processing
+                leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
+
+                BspMergeCandidate::sOverallCost += 
+                        leaf->mArea * leaf->mPvs->GetSize();
+
+                // the same leaves must not be part of two merge candidates
+                leaf->Mail();
+                vector<BspLeaf *> neighbors;
+                FindNeighbors(leaf, neighbors, true);
+
+                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
+
+                // TODO: test if at least one ray goes from one leaf to the other
+                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+                {                       
+                        mMergeQueue.push(BspMergeCandidate(leaf, *nit));
+                }
+        }
+
+        return (int)leaves.size();
+}
+
+
+int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
+{
+        vector<BspRay *> bspRays;
+
+        ConstructBspRays(bspRays, rays);
+        map<BspLeaf *, vector<BspLeaf*> > neighborMap;
+
+        vector<BspIntersection>::const_iterator iit;
+
+        int leaves = 0;
+        
+        BspLeaf::NewMail();
+
+        for (int i = 0; i < (int)bspRays.size(); ++ i)
+        {  
+                BspRay *ray = bspRays[i];
+          
+                // traverse leaves stored in the rays and compare and 
+                // merge consecutive leaves (i.e., the neighbors in the tree)
+                if (ray->intersections.size() < 2)
+                        continue;
+          
+                iit = ray->intersections.begin();
+                BspLeaf *prevLeaf = (*(iit ++)).mLeaf;
+                
+                // create leaf pvs (needed for post processing)
+                if (!prevLeaf->mPvs)
+                {
+                        prevLeaf->mPvs = 
+                                new ObjectPvs(prevLeaf->GetViewCell()->GetPvs());
+
+                        BspMergeCandidate::sOverallCost += 
+                                prevLeaf->mArea * prevLeaf->mPvs->GetSize();
+                        
+                        ++ leaves;
+                }
+                
+                // traverse intersections 
+                // consecutive leaves are neighbors => 
+                // add them to queue
+                for (; iit != ray->intersections.end(); ++ iit)
+                {
+            BspLeaf *leaf = (*iit).mLeaf;
+            
+                        if (!leaf->mPvs)
+                        {
+                                leaf->mPvs = 
+                                        new ObjectPvs(leaf->GetViewCell()->GetPvs());
+                                
+                                BspMergeCandidate::sOverallCost += 
+                                        leaf->mArea * leaf->mPvs->GetSize();
+
+                                ++ leaves;
+                        }
+                
+                        vector<BspLeaf *> &neighbors = neighborMap[leaf];
+                        
+                        bool found = false;
+
+                        // both leaves inserted in queue already =>
+                        // look if double pair already exists
+                        if (leaf->Mailed() && prevLeaf->Mailed())
+                        {
+                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
+                                
+                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
+                                        if (*it == prevLeaf)
+                                                found = true; // already in queue
+                        }
+                        
+                        if (!found)
+                        {
+                                // this pair is not in map already
+                                // => insert into the neighbor map and the queue
+                                neighbors.push_back(prevLeaf);
+                                neighborMap[prevLeaf].push_back(leaf);
+
+                                leaf->Mail();
+                                prevLeaf->Mail();
+
+                                mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
+                        }
+
+                        prevLeaf = leaf;
+        }
+        }
+        Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
+        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
+        Debug << "leaves in queue: " << leaves << endl;
+        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
+
+        CLEAR_CONTAINER(bspRays);
+
+        return leaves;
+}
+
+
+void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
+                                                                  const VssRayContainer &rays)
+{
+        VssRayContainer::const_iterator it, it_end = rays.end();
+
+        for (it = rays.begin(); it != rays.end(); ++ it)
+        {
+                VssRay *vssRay = *it;
+                BspRay *ray = new BspRay(vssRay);
+
+                ViewCellContainer viewCells;
+
+                Ray hray(*vssRay);
+                float tmin = 0, tmax = 1.0;
+                // matt TODO: remove this!!
+                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
+                if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
+                        continue;
+
+                Vector3 origin = hray.Extrap(tmin);
+                Vector3 termination = hray.Extrap(tmax);
+        
+                // cast line segment to get intersections with bsp leaves
+                CastLineSegment(origin, termination, viewCells);
+
+                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+                {
+                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
+                        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
+                        //NOTE: not sorted!
+                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+                                ray->intersections.push_back(BspIntersection(0, *it));
+                }
+
+                bspRays.push_back(ray);
+        }
+}
+
+
+int VspBspTree::MergeViewCells(const VssRayContainer &rays)
+{
+        MergeStatistics mergeStats;
+        mergeStats.Start();
+        // TODO: REMOVE LATER for performance!
+        const bool showMergeStats = true;
+        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
+        long startTime = GetTime();
+
+        if (mUseRaysForMerge)
+                mergeStats.nodes = CollectMergeCandidates(rays);
+        else
+                mergeStats.nodes = CollectMergeCandidates();
+
+        mergeStats.collectTime = TimeDiff(startTime, GetTime());
+        mergeStats.candidates = (int)mMergeQueue.size();
+        startTime = GetTime();
+
+        int nViewCells = /*mergeStats.nodes*/ mStat.Leaves();
+
+        
+        //-- use priority queue to merge leaf pairs
+        while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
+                   (mMergeQueue.top().GetMergeCost() <
+                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
+        {
+                //Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
+                //        << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
+                //        << " max ratio: " << mMergeMaxCostRatio << endl;
+                BspMergeCandidate mc = mMergeQueue.top();
+                mMergeQueue.pop();
+
+                // both view cells equal!
+                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
+                        continue;
+
+                if (mc.Valid())
+                {
+                        ViewCell::NewMail();
+                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
+                        -- nViewCells;
+                        
+                        ++ mergeStats.merged;
+                        
+                        // increase absolute merge cost
+                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
+
+                        if (showMergeStats)
+                        {
+                                if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
+                                        ++ mergeStats.siblings;
+
+                                const int dist = 
+                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
+                                if (dist > mergeStats.maxTreeDist)
+                                        mergeStats.maxTreeDist = dist;
+                                mergeStats.accTreeDist += dist;
+                        }
+                }
+                // merge candidate not valid, because one of the leaves was already
+                // merged with another one => validate and reinsert into queue
+                else
+                { 
+                        mc.SetValid();
+                        mMergeQueue.push(mc);
+                }
+        }
+
+        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
+        mergeStats.Stop();
+
+        if (showMergeStats)
+                Debug << mergeStats << endl << endl;
+        
+        //TODO: should return sample contributions?
+        return mergeStats.merged;
+}
+
+
+int VspBspTree::RefineViewCells(const VssRayContainer &rays)
+{
+        int shuffled = 0;
+
+        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
+        BspLeaf::NewMail();
+
+        // Use priority queue of remaining leaf pairs 
+        // These candidates either share the same view cells or
+        // are border leaves which share a boundary.
+        // We test if they can be shuffled, i.e.,
+        // either one leaf is made part of one view cell or the other
+        // leaf is made part of the other view cell. It is tested if the
+        // remaining view cells are "better" than the old ones.
+        while (!mMergeQueue.empty())
+        {
+                BspMergeCandidate mc = mMergeQueue.top();
+                mMergeQueue.pop();
+
+                // both view cells equal or already shuffled
+                if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) ||
+                        (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
+                        continue;
+                
+                // candidate for shuffling
+                const bool wasShuffled = 
+                        ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
+                
+                //-- stats
+                if (wasShuffled)
+                        ++ shuffled;
+        }
+
+        return shuffled;
+}
+
+
+inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+        return pvs1.AddPvs(pvs2);
+}
+
+/*inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
+{
+        ObjectPvs pvs;
+        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
+        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
+                if (*it != l)
+                        pvs.AddPvs(*(*it)->mPvs);
+        return pvs.GetSize();
+}*/
+
+inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+        return pvs1.SubtractPvs(pvs2);
+}
+
+
+float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2)
+{
+        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
+        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
+        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;
+
+        return cost1 + cost2;
+}
+
+
+void VspBspTree::ShuffleLeaf(BspLeaf *leaf, 
+                                                         BspViewCell *vc1, 
+                                                         BspViewCell *vc2) const
+{
+        //Debug << "old pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
+        //        << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
+        // compute new pvs and area
+        vc1->GetPvs().SubtractPvs(*leaf->mPvs);
+        vc2->GetPvs().AddPvs(*leaf->mPvs);
+        
+        vc1->SetArea(vc1->GetArea() - leaf->mArea);
+        vc2->SetArea(vc2->GetArea() + leaf->mArea);
+
+        /// add to second view cell
+        vc2->mLeaves.push_back(leaf);
+
+        // erase leaf from old view cell
+        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
+
+        for (; *it != leaf; ++ it);
+        vc1->mLeaves.erase(it);
+
+        /*vc1->GetPvs().mEntries.clear();
+        for (; it != vc1->mLeaves.end(); ++ it)
+        {
+                if (*it == leaf)
+                        vc1->mLeaves.erase(it);
+                else
+                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
+        }*/
+
+        leaf->SetViewCell(vc2);         // finally change view cell
+        
+        //Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
+        //        << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
+
+}
+
+
+bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const
+{
+        BspViewCell *vc1 = leaf1->GetViewCell();
+        BspViewCell *vc2 = leaf2->GetViewCell();
+
+        const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
+        const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
+
+        const float oldCost = cost1 + cost2;
+        
+        float shuffledCost1 = Limits::Infinity;
+        float shuffledCost2 = Limits::Infinity;
+
+        // the view cell should not be empty after the shuffle
+        if (vc1->mLeaves.size() > 1)
+                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
+        if (vc2->mLeaves.size() > 1)
+                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
+
+        // shuffling unsuccessful
+        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
+                return false;
+        
+        if (shuffledCost1 < shuffledCost2)
+        {
+                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl;
+                ShuffleLeaf(leaf1, vc1, vc2);
+                leaf1->Mail();
+        }
+        else
+        {
+                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl;
+                ShuffleLeaf(leaf2, vc2, vc1);
+                leaf2->Mail();
+        }
+
+        return true;
+}
+
 
 /************************************************************************/
@@ -2220 +2518 @@
 }
 
+float BspMergeCandidate::GetCost(ViewCell *vc) const
+{
+        return vc->GetPvs().GetSize() * vc->GetArea();
+}
+
 float BspMergeCandidate::GetLeaf1Cost() const
 {
         BspViewCell *vc = mLeaf1->GetViewCell();
-        return vc->GetPvs().GetSize() * vc->GetArea();
+        return GetCost(vc);
 }
 
@@ -2229 +2532 @@
 {
         BspViewCell *vc = mLeaf2->GetViewCell();
-        return vc->GetPvs().GetSize() * vc->GetVolume();
+        return GetCost(vc);
 }
 
@@ -2239 +2542 @@
 
         const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
+        const int newPvs = diff1 + vc1->GetPvs().GetSize();
 
         //-- compute ratio of old cost
@@ -2247 +2550 @@
 
         const float newCost =
-                (float)vcPvs * (vc1->GetArea() + vc2->GetArea());
+                (float)newPvs * (vc1->GetArea() + vc2->GetArea());
 
         mMergeCost = newCost - oldCost;
-
 //      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
 //              mMergeCost += 1.0;
@@ -2294 +2596 @@
         EvalMergeCost();
 }
+
+
+/************************************************************************/
+/*                  MergeStatistics implementation                      */
+/************************************************************************/
+
+
+void MergeStatistics::Print(ostream &app) const
+{
+        app << "===== Merge statistics ===============\n";
+
+        app << setprecision(4);
+
+        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
+
+        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
+
+        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
+
+        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
+
+        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
+
+        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
+        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
+
+        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
+
+        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
+
+        app << "===== END OF BspTree statistics ==========\n";
+}