Changeset 479

Timestamp:

12/23/05 11:05:33 (18 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (5 diffs)
• src/RenderSimulator.cpp (modified) (2 diffs)
• src/ViewCell.cpp (modified) (1 diff)
• src/ViewCell.h (modified) (2 diffs)
• src/ViewCellBsp.cpp (modified) (8 diffs)
• src/ViewCellBsp.h (modified) (1 diff)
• src/ViewCellsManager.cpp (modified) (17 diffs)
• src/ViewCellsManager.h (modified) (2 diffs)
• src/VspBspTree.cpp (modified) (9 diffs)
• src/VspBspTree.h (modified) (2 diffs)
• src/VspKdTree.cpp (modified) (6 diffs)
• src/VspKdTree.h (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -177 +177 @@
 Simulation {
         objRenderCost 1.0
-        vcOverhead 7.0
-        moveSpeed 3.0
+        vcOverhead 2.0
+        # always between 0 and 1
+        moveSpeed 0.00002
 }
 
@@ -208 +209 @@
         # maximal cost for merging a view cell
         PostProcess {
-                maxCostRatio 5000000
+                maxCostRatio 1.4
                 minViewCells 100
                 maxPvsSize   50000
@@ -240 +241 @@
         
         # maximal tested rays for split cost heuristics
-        maxTests 10000
+        maxTests 500
         
         # factors for evaluating split plane costs
@@ -261 +262 @@
                 #maxAccRayLength        100
                 
-                maxViewCells            1500
+                maxViewCells            1000
                 
                 # used for pvs criterium
@@ -288 +289 @@
         
         PostProcess {
-                maxCostRatio 5000000
-                minViewCells 1000
-                maxPvsSize   50000
+                maxCostRatio 0.05
+                minViewCells 700
+                maxPvsSize   500
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

@@ -77 +77 @@
                 // probability of view cell
                 const float pInVc = mViewCellsManager->GetProbability(vc);
-                Debug << "prop: " << pInVc << endl;
                 // compute render time of PVS times probability that view point is in view cell
                 const float vcCost = pInVc * mViewCellsManager->GetRendercost(vc, mObjRenderCost);
-                Debug << "cost: " << vcCost << " rcost: "
-                          << mViewCellsManager->GetRendercost(vc, mObjRenderCost) << endl;
-
+        
                 // crossing the border of a view cell is depending on the move speed
                 // and the probability that a view cell border is crossed
                 loadPvsOverhead += GetCrossVcProbability() * mVcOverhead;
 
-                Debug << "crossvc: " << GetCrossVcProbability() * mVcOverhead << endl;
                 //-- update statistics
                 renderTime += vcCost;
@@ -105 +101 @@
 }
 
+
 float RenderSimulator::GetCrossVcProbability() const
 {
         // assume the view cells are uniformly distributed
+        //NOTE: should I take move speed relative to view space or absolute?
         const float vcNum = 
                 (float)mViewCellsManager->GetViewCells().size();
 
-        return 1.0f - (1 / mMoveSpeed * vcNum);
+        const float prop = mMoveSpeed * vcNum;
+
+        // clamp probability between 0 and 1
+        return min(1.0f, prop);
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -55 +55 @@
 }
 
+void ViewCell::UpdateViewCellsStats(ViewCellsStatistics &vcStat)
+{
+        ++ vcStat.viewCells;
+                
+        const int pvsSize = mPvs.GetSize();
+
+        vcStat.pvs += pvsSize;
+
+        if (pvsSize == 0)
+                ++ vcStat.emptyPvs;
+
+        if (pvsSize > vcStat.maxPvs)
+                vcStat.maxPvs = pvsSize;
+
+        if (pvsSize < vcStat.minPvs)
+                vcStat.minPvs = pvsSize;
+}
 
 float ViewCell::GetArea() const

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -16 +16 @@
 class VspKdLeaf;
 class KdLeaf;
-
-/**
-        View cell with an optional mesh representation
-*/
-class ViewCell: public MeshInstance
-{
-public:
-        ViewCell();
-
-        /** Constructor taking a mesh representing the shape of the viewcell.
-        */
-        ViewCell(Mesh *mesh);
-
-        /** Default destructor.
-        */
-        virtual ~ViewCell() {}
-        /** Returns Pvs.
-        */
-        const ObjectPvs &GetPvs() const;
-        ObjectPvs &GetPvs();
-
-        int Type() const;
-
-        /** Adds a passing ray to the passing ray container.
-        */
-        void AddPassingRay(const Ray &ray, const int contributions);
-
-        /** Returns volume of the view cell.
-        */
-        float GetVolume() const;
-
-        /** Returns area of the view cell.
-        */
-        float GetArea() const;
-
-        /** Sets the volume of the view cell.
-        */
-        void SetVolume(float volume);
-        
-        /** Sets the area of the view cell.
-        */
-        void SetArea(float area);
-
-        /// Ray set description of the rays passing through this node.
-        PassingRaySet mPassingRays;
-
-        /// Rays piercing this view cell.
-        RayContainer mPiercingRays;
-
-protected:
-
-        /// the potentially visible objects
-        ObjectPvs mPvs;
-
-        float mVolume;
-        float mArea;
-};
-
-/**
-        View cell belonging to a hierarchy.
-*/
-template<typename T>
-class HierarchyViewCell: public ViewCell
-{
-public:
-        HierarchyViewCell<T>(): mLeaves(0) {}
-        HierarchyViewCell<T>(Mesh *mesh):
-                ViewCell(mesh), mLeaves(0) {}
-
-        /// Leaves of the hierarchy which are part of this view cell.
-        std::vector<T> mLeaves;
-};
-
-typedef HierarchyViewCell<BspLeaf *> BspViewCell;
-typedef HierarchyViewCell<KdLeaf *> KdViewCell;
-typedef HierarchyViewCell<VspKdLeaf *> VspKdViewCell;
-
 
 /** Statistics for a view cell partition.
@@ -152 +75 @@
 };
 
+/**
+        View cell with an optional mesh representation
+*/
+class ViewCell: public MeshInstance
+{
+public:
+        ViewCell();
+
+        /** Constructor taking a mesh representing the shape of the viewcell.
+        */
+        ViewCell(Mesh *mesh);
+
+        /** Default destructor.
+        */
+        virtual ~ViewCell() {}
+        /** Returns Pvs.
+        */
+        const ObjectPvs &GetPvs() const;
+        ObjectPvs &GetPvs();
+
+        int Type() const;
+
+        /** Adds a passing ray to the passing ray container.
+        */
+        void AddPassingRay(const Ray &ray, const int contributions);
+
+        /** Returns volume of the view cell.
+        */
+        float GetVolume() const;
+
+        /** Returns area of the view cell.
+        */
+        float GetArea() const;
+
+        /** Sets the volume of the view cell.
+        */
+        void SetVolume(float volume);
+        
+        /** Sets the area of the view cell.
+        */
+        void SetArea(float area);
+        virtual void UpdateViewCellsStats(ViewCellsStatistics &vcStat);
+
+        /// Ray set description of the rays passing through this node.
+        PassingRaySet mPassingRays;
+
+        /// Rays piercing this view cell.
+        RayContainer mPiercingRays;
+
+protected:
+
+        /// the potentially visible objects
+        ObjectPvs mPvs;
+
+        float mVolume;
+        float mArea;
+};
+
+/**
+        View cell belonging to a hierarchy.
+*/
+template<typename T>
+class HierarchyViewCell: public ViewCell
+{
+public:
+        HierarchyViewCell<T>(): mLeaves(0) {}
+        HierarchyViewCell<T>(Mesh *mesh):
+                ViewCell(mesh), mLeaves(0) {}
+
+        void UpdateViewCellsStats(ViewCellsStatistics &vcStat)
+        {
+                ViewCell::UpdateViewCellsStats(vcStat);
+
+                if ((int)mLeaves.size() > vcStat.maxLeaves)
+                        vcStat.maxLeaves = (int)mLeaves.size();
+        }
+
+        /// Leaves of the hierarchy which are part of this view cell.
+        std::vector<T> mLeaves;
+};
+
+
+typedef HierarchyViewCell<BspLeaf *> BspViewCell;
+typedef HierarchyViewCell<KdLeaf *> KdViewCell;
+typedef HierarchyViewCell<VspKdLeaf *> VspKdViewCell;
+
+
 #endif

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -1178 +1178 @@
 
 Plane3 BspTree::ChooseCandidatePlane(const BoundedRayContainer &rays) const
-{       return Plane3();
-        /*const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-        
-        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
-        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
+{       
+        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+        BoundedRay *bRay = rays[candidateIdx];
+        Ray *ray = bRay->mRay;
+
+        const Vector3 minPt = ray->Extrap(bRay->mMinT);
+        const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
 
         const Vector3 pt = (maxPt + minPt) * 0.5;
-        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
-
-        return Plane3(normal, pt);*/
+
+        const Vector3 normal = ray->GetDir();
+                        
+        return Plane3(normal, pt);
 }
 
 Plane3 BspTree::ChooseCandidatePlane2(const BoundedRayContainer &rays) const
-{       return Plane3();
-        /*Vector3 pt[3];
-        
+{       
+        Vector3 pt[3];
         int idx[3];
         int cmaxT = 0;
@@ -1199 +1201 @@
         bool chooseMin = false;
 
-        for (int j = 0; j < 3; ++ j)
-        {
-                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
-                        
+        for (int j = 0; j < 3; j ++)
+        {
+                idx[j] = (int)RandomValue(0, Real((int)rays.size() * 2 - 1));
+                                
                 if (idx[j] >= (int)rays.size())
                 {
-                        idx[j] -= (int)rays.size();
-                                
+                        idx[j] -= (int)rays.size();             
                         chooseMin = (cminT < 2);
                 }
@@ -1212 +1213 @@
                         chooseMin = (cmaxT < 2);
 
-                RayInfo rayInf = rays[idx[j]];
-                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
+                BoundedRay *bRay = rays[idx[j]];
+                pt[j] = chooseMin ? bRay->mRay->Extrap(bRay->mMinT) : 
+                                                        bRay->mRay->Extrap(bRay->mMaxT);
         }       
-
-        return Plane3(pt[0], pt[1], pt[2]);*/
+                        
+        return Plane3(pt[0], pt[1], pt[2]);
 }
 
 Plane3 BspTree::ChooseCandidatePlane3(const BoundedRayContainer &rays) const
-{       return Plane3();/*
+{       
         Vector3 pt[3];
         
@@ -1230 +1232 @@
                 idx2 = (idx2 + 1) % (int)rays.size();
 
-        const RayInfo ray1 = rays[idx1];
-        const RayInfo ray2 = rays[idx2];
+        const BoundedRay *ray1 = rays[idx1];
+        const BoundedRay *ray2 = rays[idx2];
 
         // normal vector of the plane parallel to both lines
-        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
+        const Vector3 norm = 
+                Normalize(CrossProd(ray1->mRay->GetDir(), ray2->mRay->GetDir()));
+
+        const Vector3 orig1 = ray1->mRay->Extrap(ray1->mMinT);
+        const Vector3 orig2 = ray2->mRay->Extrap(ray2->mMinT);
 
         // vector from line 1 to line 2
-        const Vector3 vd = (ray2.ExtrapOrigin() - ray1.ExtrapOrigin());
+        const Vector3 vd = orig1 - orig2;
         
         // project vector on normal to get distance
@@ -1243 +1249 @@
 
         // point on plane lies halfway between the two planes
-        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
-
-        return Plane3(norm, planePt);*/
+        const Vector3 planePt = orig1 + norm * dist * 0.5;
+
+        return Plane3(norm, planePt);
 }
 
@@ -2011 +2017 @@
 }
 
-void BspTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const
-{
-        vcStat.Reset();
-
-        stack<BspNode *> nodeStack;
-        nodeStack.push(mRoot);
-
-        ViewCell::NewMail();
-
-        // exclude root cell
-        mRootCell->Mail();
-
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
-                nodeStack.pop();
-
-                if (node->IsLeaf()) 
-                {
-                        ++ vcStat.leaves;
-
-                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
-
-                        if (!viewCell->Mailed()) 
-                        {
-                                viewCell->Mail();
-                                
-                                ++ vcStat.viewCells;
-                                const int pvsSize = viewCell->GetPvs().GetSize();
-
-                vcStat.pvs += pvsSize;
-
-                                if (pvsSize < 1)
-                                        ++ vcStat.emptyPvs;
-
-                                if (pvsSize > vcStat.maxPvs)
-                                        vcStat.maxPvs = pvsSize;
-
-                                if (pvsSize < vcStat.minPvs)
-                                        vcStat.minPvs = pvsSize;
-
-                                if ((int)viewCell->mLeaves.size() > vcStat.maxLeaves)
-                                        vcStat.maxLeaves = (int)viewCell->mLeaves.size();               
-                        }
-                }
-                else 
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        nodeStack.push(interior->GetFront());
-                        nodeStack.push(interior->GetBack());
-                }
-        }
-}
 
 BspTreeStatistics &BspTree::GetStat()
@@ -2070 +2022 @@
         return mStat;
 }
+
 
 float BspTree::AccumulatedRayLength(BoundedRayContainer &rays) const
@@ -2085 +2038 @@
         return len;
 }
+
 
 int BspTree::SplitRays(const Plane3 &plane,

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -457 +457 @@
         BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
 
-        /** Traverses tree and counts all view cells as well as their PVS size.
-        */
-        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const;
-
         /** Returns view cell corresponding to unbounded space.
         */

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -72 +72 @@
 }
 
+void ViewCellsManager::EvaluateViewCellsStats()
+{
+        mViewCellsStats.Reset();
+
+        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
+
+        for (it = mViewCells.begin(); it != it_end; ++ it)
+                (*it)->UpdateViewCellsStats(mViewCellsStats);
+}
+
 void ViewCellsManager::AddViewCell(ViewCell *viewCell)
 {
@@ -378 +388 @@
         }
 
-        mBspTree->EvaluateViewCellsStats(mViewCellsStats);
+        EvaluateViewCellsStats();
 
         // destroy rays created only for construction
@@ -396 +406 @@
         // compute view cell area as subsititute for probability
 #if 0
-        return GetArea(viewCell) / mBspTree->GetBoundingBox().SurfaceArea();
+        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
 #else
         return GetArea(viewCell) / GetAccVcArea();
@@ -520 +530 @@
         // reset view cells and stats
         mViewCells.clear();
+        mTotalAreaValid = false;
         mBspTree->CollectViewCells(mViewCells);
         mViewCellsStats.Reset();
-        mBspTree->EvaluateViewCellsStats(mViewCellsStats);
+        EvaluateViewCellsStats();
 
         return merged;
@@ -699 +710 @@
                         CLEAR_CONTAINER(vcGeom);
                 }
+                        
                         
                 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
@@ -840 +852 @@
 float KdViewCellsManager::GetProbability(ViewCell *viewCell)
 {
-        // compute view cell area as subsititute for probability
-        AxisAlignedBox3 box = mKdTree->GetBox(mKdTree->GetRoot());
+        // compute view cell area / volume as subsititute for probability
 #if 0
-        return GetArea(viewCell) / box.SurfaceArea();
-#else
+        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
+#endif
+#if 1
         return GetArea(viewCell) / GetAccVcArea();
 #endif
+#if 0
+        return GetVolume(viewCell) / GetSceneBbox().GetVolume();
+#endif
 }
 
@@ -855 +870 @@
 }
 
+
 AxisAlignedBox3 KdViewCellsManager::GetSceneBbox() const
 {
         return mKdTree->GetBox();
 }
+
 
 int KdViewCellsManager::Construct(const ObjectContainer &objects, 
@@ -872 +889 @@
         // create the view cells
         mKdTree->CreateAndCollectViewCells(mViewCells);
-        //mKdTree->EvaluateViewCellsStats(mViewCellsStats);
+        EvaluateViewCellsStats();
 
         return 0;
@@ -901 +918 @@
         const int pvsOut = min((int)objects.size(), 10);
         VssRayContainer *rays = new VssRayContainer[pvsOut];
-
-  //$$ JB
-//#if 0
 
         if (useViewCells)
@@ -927 +941 @@
                         
                         cout << "creating output for view cell " << i << " ... ";
-                        
+#if 0                   
                         // check whether we can add the current ray to the output rays
-                        /*for (int k = 0; k < raysOut; ++ k) 
+                        for (int k = 0; k < raysOut; ++ k) 
                         {
                                 Ray *ray = sampleRays[k];
@@ -942 +956 @@
                                         }
                                 }
-                        }*/
-                        
+                        }
+#endif                  
                         Intersectable::NewMail();
                         
@@ -1136 +1150 @@
         mVspKdTree->Construct(constructionRays, sceneBbox);
         mVspKdTree->CollectViewCells(mViewCells);
-        //mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);
+        EvaluateViewCellsStats();
 
         Debug << mVspKdTree->GetStatistics() << endl;
@@ -1331 +1345 @@
 {
 #if 0
-        return GetArea(viewCell) / mVspBspTree->GetBbox().SurfaceArea();
+        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
 #else
         return GetArea(viewCell) / GetAccVcArea();
@@ -1338 +1352 @@
 
 
-float VspBspViewCellsManager::GetArea(ViewCell *viewCell) const
-{
-        PolygonContainer geom;
-
-        // compute view cell area
-        mVspBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(viewCell), geom);
-        
-        const float area = Polygon3::GetArea(geom);
-        CLEAR_CONTAINER(geom);
-
-        return area;
-}
-
 float VspBspViewCellsManager::GetRendercost(ViewCell *viewCell, 
                                                                                         float objRendercost) const
@@ -1392 +1393 @@
         mVspBspTree->Construct(constructionRays);
         mVspBspTree->CollectViewCells(mViewCells);
-        mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);
+        EvaluateViewCellsStats();
 
         Debug << mVspBspTree->GetStatistics() << endl;
@@ -1532 +1533 @@
         // reset view cells and stats
         mViewCells.clear();
+        mTotalAreaValid = false;
         mVspBspTree->CollectViewCells(mViewCells);
         mViewCellsStats.Reset();
-        mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);
+        EvaluateViewCellsStats();
 
         return merged;
@@ -1696 +1698 @@
                         CLEAR_CONTAINER(vcGeom);
                 }
+                        
                         
                 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -207 +207 @@
 
 protected:
+        /** Evaluates view cells statistics and stores it in
+                mViewCellsStatistics.
+        */
+        void EvaluateViewCellsStats();
                 
         /// the view cell corresponding to unbounded space
@@ -438 +442 @@
         float GetProbability(ViewCell *viewCell);
         float GetRendercost(ViewCell *viewCell, float objRendercost) const;
-        float GetArea(ViewCell *viewCell) const;
-
+        
         AxisAlignedBox3 GetSceneBbox() const;
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -800 +800 @@
 
         // vector from line 1 to line 2
-        const Vector3 vd = (ray2.ExtrapOrigin() - ray1.ExtrapOrigin());
+        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
         
         // project vector on normal to get distance
@@ -1306 +1306 @@
 }
 
-void VspBspTree::EvaluateViewCellsStats(ViewCellsStatistics &stat) const
-{
-        stat.Reset();
-
-        stack<BspNode *> nodeStack;
-        nodeStack.push(mRoot);
-
-        ViewCell::NewMail();
-
-        // exclude root cell
-        mRootCell->Mail();
-
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
-                nodeStack.pop();
-
-                if (node->IsLeaf()) 
-                {
-                        ++ stat.leaves;
-
-                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
-
-                        if (!viewCell->Mailed()) 
-                        {
-                                viewCell->Mail();
-                                
-                                ++ stat.viewCells;
-                                const int pvsSize = viewCell->GetPvs().GetSize();
-
-                stat.pvs += pvsSize;
-
-                                if (pvsSize < 1)
-                                        ++ stat.emptyPvs;
-
-                                if (pvsSize > stat.maxPvs)
-                                        stat.maxPvs = pvsSize;
-
-                                if (pvsSize < stat.minPvs)
-                                        stat.minPvs = pvsSize;
-
-                                if ((int)viewCell->mLeaves.size() > stat.maxLeaves)
-                                        stat.maxLeaves = (int)viewCell->mLeaves.size();         
-                        }
-                }
-                else 
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        nodeStack.push(interior->GetFront());
-                        nodeStack.push(interior->GetBack());
-                }
-        }
-}
 
 BspTreeStatistics &VspBspTree::GetStat()
@@ -1365 +1311 @@
         return mStat;
 }
+
 
 float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
@@ -1377 +1324 @@
         return len;
 }
+
 
 int VspBspTree::SplitRays(const Plane3 &plane,
@@ -1426 +1374 @@
         return splits;
 }
+
 
 void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
@@ -1889 +1838 @@
 }
 
+
+BspNode *VspBspTree::CollapseTree(BspNode *node)
+{
+    if (node->IsLeaf())
+                return node;
+
+        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+        BspNode *front = CollapseTree(interior->GetFront());
+        BspNode *back = CollapseTree(interior->GetBack());
+
+        if (front->IsLeaf() && back->IsLeaf())
+        {
+                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
+                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
+
+                //-- collapse tree
+                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
+                {
+                        BspViewCell *vc = frontLeaf->GetViewCell();
+
+                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
+                        
+                        // replace a link from node's parent
+                        if (leaf->GetParent())
+                                leaf->GetParent()->ReplaceChildLink(node, leaf);
+
+                        delete interior;
+
+                        return leaf;
+                }
+        }
+
+        return node;
+}
+
+
+void VspBspTree::RepairVcLeafLists()
+{
+        // list not valid anymore => clear
+        stack<BspNode *> nodeStack;
+        nodeStack.push(mRoot);
+
+        ViewCell::NewMail();
+
+        while (!nodeStack.empty())
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                if (node->IsLeaf())
+                {
+                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+                        BspViewCell *viewCell = leaf->GetViewCell();
+
+                        if (!viewCell->Mailed())
+                        {
+                                viewCell->mLeaves.clear();
+                                viewCell->Mail();
+                        }
+
+                        viewCell->mLeaves.push_back(leaf);
+                }
+                else
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+}
+
+
 int VspBspTree::MergeLeaves()
 {
@@ -1933 +1957 @@
         int merged = 0;
 
-        Debug << "here234: " << mMergeMaxCostRatio << endl;
+        Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
+        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
 
         // use priority queue to merge leaves
-        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) )//&&
-                   //(mergeQueue.top().GetMergeCost() < 
-                    //mMergeMaxCostRatio / BspMergeCandidate::sOverallCost))
-        {
-                Debug << "mergecost: " << mergeQueue.top().GetMergeCost() << " " << mMergeMaxCostRatio << endl;
+        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();
@@ -1970 +1995 @@
 
         // collapse tree according to view cell partition
-        //CollapseTree(mRoot);
-
+        CollapseTree(mRoot);
         // revalidate leaves
-        //ValidateViewCellLeaves();
+        RepairVcLeafLists();
 
         //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl;
@@ -1996 +2020 @@
 
         // set new size of view cell
-        vc->SetArea(fVc->GetVolume() + bVc->GetVolume());
+        vc->SetArea(fVc->GetArea() + bVc->GetArea());
 
         vector<BspLeaf *> fLeaves = fVc->mLeaves;

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -225 +225 @@
         BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
 
-        /** Traverses tree and counts all view cells as well as their PVS size.
-        */
-        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const;
-
-
         /** Returns view cell corresponding to unbounded space.
         */
@@ -246 +241 @@
         */
         int MergeLeaves();
-
-
                 
         /** Sets pointer to view cells manager.
         */
         void SetViewCellsManager(ViewCellsManager *vcm);
+
+        /** Helper function revalidating the view cell leaf list after merge.
+        */
+        void RepairVcLeafLists();
+
+        /** Collapses the tree with respect to the view cell partition.
+                @returns node of type leaf if the node could be collapsed, this node otherwise
+        */
+        BspNode *CollapseTree(BspNode *node);
+        
 
 protected:

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -2022 +2022 @@
         leaf->SetViewCell(vc);
 
-        vc->SetArea(GetBBox(leaf).GetVolume());
+        vc->SetVolume(GetBBox(leaf).GetVolume());
+        vc->SetArea(GetBBox(leaf).SurfaceArea());
+
         vc->mLeaves.push_back(leaf);
 
@@ -2036 +2038 @@
         }
 }
-
-
-void VspKdTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const
-{
-        vcStat.Reset();
-
-        stack<VspKdNode *> nodeStack;
-        nodeStack.push(mRoot);
-
-        ViewCell::NewMail();
-
-        while (!nodeStack.empty())
-        {
-                VspKdNode *node = nodeStack.top();
-                nodeStack.pop();
-
-                if (node->IsLeaf())
-                {
-                        ++ vcStat.leaves;
-
-                        VspKdViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
-
-                        if (!viewCell->Mailed())
-                        {
-                                viewCell->Mail();
-
-                                ++ vcStat.viewCells;
-                                const int pvsSize = viewCell->GetPvs().GetSize();
-
-                vcStat.pvs += pvsSize;
-
-                                if (pvsSize < 1)
-                                        ++ vcStat.emptyPvs;
-
-                                if (pvsSize > vcStat.maxPvs)
-                                        vcStat.maxPvs = pvsSize;
-
-                                if (pvsSize < vcStat.minPvs)
-                                        vcStat.minPvs = pvsSize;
-
-                                if ((int)viewCell->mLeaves.size() > vcStat.maxLeaves)
-                                        vcStat.maxLeaves = (int)viewCell->mLeaves.size();
-                        }
-                }
-                else
-                {
-                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
-
-                        nodeStack.push(interior->GetFront());
-                        nodeStack.push(interior->GetBack());
-                }
-        }
-}
-
 
 
@@ -2106 +2054 @@
 
         // set new size of view cell
-        vc->SetArea(fVc->GetVolume() + bVc->GetVolume());
+        vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
 
         vector<VspKdLeaf *> fLeaves = fVc->mLeaves;
@@ -2222 +2170 @@
         }
 
-        // collapse tree according to view cell partition
+        // collapse siblings belonging to the same view cell
         CollapseTree(mRoot);
-
         // revalidate leaves
-        ValidateViewCellLeaves();
+        RepairVcLeafLists();
 
         //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl;
@@ -2235 +2182 @@
 
 
-void VspKdTree::ValidateViewCellLeaves()
+void VspKdTree::RepairVcLeafLists()
 {
         // list not valid anymore => clear
@@ -2271 +2218 @@
         }
 }
+
 
 VspKdNode *VspKdTree::CollapseTree(VspKdNode *node)

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -597 +597 @@
         void CollectViewCells(ViewCellContainer &viewCells) const;
 
-        /** Traverses tree and counts all view cells as well as their PVS size.
-        */
-        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const;
-
         /** Refines view cells in a post processing step.
         */
@@ -715 +711 @@
         /** Helper function revalidating the view cell leaf list after merge.
         */
-        void ValidateViewCellLeaves();
+        void RepairVcLeafLists();
 
 protected: