Changeset 462 for trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

Timestamp:

12/13/05 17:28:02 (19 years ago)

Author:

mattausch

Message:

worked on vsp kd view cells

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp (modified) (64 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -25 +25 @@
 #include "Ray.h"
 #include "RayInfo.h"
+#include "ViewCell.h"
 #include "ViewCellsManager.h"
-#include "ViewCell.h"
+#include "ViewCellBsp.h"
 
 // Static variables
-int VspKdTreeLeaf::mailID = 0;
+int VspKdLeaf::sMailId = 0;
+int MergeCandidate::sMaxPvsSize = 150;
+
 
 #define USE_FIXEDPOINT_T 0
@@ -70 +73 @@
 
 /**************************************************************/
-/*                class VspKdTreeNode implementation          */
+/*                class VspKdNode implementation          */
 /**************************************************************/
 
 // Inline constructor
-VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p):
+VspKdNode::VspKdNode(VspKdInterior *p):
 mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0) 
 {}
 
-VspKdTreeNode::~VspKdTreeNode() 
+VspKdNode::~VspKdNode() 
 {};
 
-inline VspKdTreeInterior *VspKdTreeNode::GetParent() const
+inline VspKdInterior *VspKdNode::GetParent() const
 {
         return mParent;
 }
 
-inline void VspKdTreeNode::SetParent(VspKdTreeInterior *p)
+inline void VspKdNode::SetParent(VspKdInterior *p)
 {
         mParent = p;
 }
 
-bool VspKdTreeNode::IsLeaf() const 
+bool VspKdNode::IsLeaf() const 
 { 
         return mAxis == -1; 
 }
   
-int VspKdTreeNode::GetAccessTime() 
+int VspKdNode::GetAccessTime() 
 {
         return 0x7FFFFFF;
@@ -102 +105 @@
 
 /**************************************************************/
-/*                VspKdTreeInterior implementation            */
+/*                VspKdInterior implementation            */
 /**************************************************************/
 
-VspKdTreeInterior::VspKdTreeInterior(VspKdTreeInterior *p):
-VspKdTreeNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
-{
-}
-
-int VspKdTreeInterior::GetAccessTime()
+VspKdInterior::VspKdInterior(VspKdInterior *p):
+VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
+{
+}
+
+int VspKdInterior::GetAccessTime()
 {
         return mLastAccessTime;
 }
 
-void VspKdTreeInterior::SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f) 
+void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f) 
 {
         mBack = b;
@@ -123 +126 @@
 }
 
-void VspKdTreeInterior::ReplaceChildLink(VspKdTreeNode *oldChild, 
-                                                                                 VspKdTreeNode *newChild)
+void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild, 
+                                                                                 VspKdNode *newChild)
 {
         if (mBack == oldChild)
@@ -132 +135 @@
 }
 
-int VspKdTreeInterior::Type() const  
+int VspKdInterior::Type() const  
 { 
         return EInterior; 
 }
   
-VspKdTreeInterior::~VspKdTreeInterior()
+VspKdInterior::~VspKdInterior()
 {
         DEL_PTR(mBack);
@@ -143 +146 @@
 }
   
-void VspKdTreeInterior::Print(ostream &s) const 
+void VspKdInterior::Print(ostream &s) const 
 {
         switch (mAxis)
@@ -161 +164 @@
 }
         
-int VspKdTreeInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 
+int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 
 {
         return rayData.ComputeRayIntersection(mAxis, mPosition, t);
 }
 
-VspKdTreeNode *VspKdTreeInterior::GetBack() const
+VspKdNode *VspKdInterior::GetBack() const
 {
         return mBack;
 }
 
-VspKdTreeNode *VspKdTreeInterior::GetFront() const
+VspKdNode *VspKdInterior::GetFront() const
 {
         return mFront;
@@ -178 +181 @@
 
 /**************************************************************/
-/*              class VspKdTreeLeaf implementation            */
+/*              class VspKdLeaf implementation            */
 /**************************************************************/
-VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p,      const int nRays):
-VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
+
+
+VspKdLeaf::VspKdLeaf(VspKdInterior *p,  const int nRays):
+VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
 {
         mRays.reserve(nRays);
 }
 
-VspKdTreeLeaf::~VspKdTreeLeaf() 
-{}
-
-int VspKdTreeLeaf::Type() const  
+VspKdLeaf::~VspKdLeaf() 
+{
+}
+
+int VspKdLeaf::Type() const  
 { 
         return ELeaf; 
 }
 
-void VspKdTreeLeaf::Print(ostream &s) const 
+void VspKdLeaf::Print(ostream &s) const 
 {
         s << endl << "L: r = " << (int)mRays.size() << endl;
 };
 
-void VspKdTreeLeaf::AddRay(const RayInfo &data) 
+void VspKdLeaf::AddRay(const RayInfo &data) 
 {
         mValidPvs = false;
@@ -206 +212 @@
 }
 
-int VspKdTreeLeaf::GetPvsSize() const 
+int VspKdLeaf::GetPvsSize() const 
 {
         return mPvsSize;
 }
 
-void VspKdTreeLeaf::SetPvsSize(const int s) 
+void VspKdLeaf::SetPvsSize(const int s) 
 {
         mPvsSize = s;
 }
 
-void VspKdTreeLeaf::Mail()
+void VspKdLeaf::Mail()
 { 
-        mMailbox = mailID; 
-}
-
-void VspKdTreeLeaf::NewMail() 
+        mMailbox = sMailId; 
+}
+
+void VspKdLeaf::NewMail() 
 { 
-        ++ mailID; 
-}
-
-bool VspKdTreeLeaf::Mailed() const 
+        ++ sMailId; 
+}
+
+bool VspKdLeaf::Mailed() const 
 { 
-        return mMailbox == mailID; 
-}
-
-bool VspKdTreeLeaf::Mailed(const int mail) 
-{
-        return mMailbox >= mailID + mail;
-}
-
-float VspKdTreeLeaf::GetAvgRayContribution() const 
+        return mMailbox == sMailId; 
+}
+
+bool VspKdLeaf::Mailed(const int mail) const
+{
+        return mMailbox == mail;
+}
+
+int VspKdLeaf::GetMailbox() const
+{
+        return mMailbox;
+}
+
+float VspKdLeaf::GetAvgRayContribution() const 
 {
         return GetPvsSize() / ((float)mRays.size() + Limits::Small);
 }
 
-float VspKdTreeLeaf::GetSqrRayContribution() const 
+float VspKdLeaf::GetSqrRayContribution() const 
 {
         return sqr(GetAvgRayContribution());
 }
 
-RayInfoContainer &VspKdTreeLeaf::GetRays()
+RayInfoContainer &VspKdLeaf::GetRays()
 {
         return mRays;
 }
 
-void VspKdTreeLeaf::ExtractPvs(ObjectContainer &objects) const
+void VspKdLeaf::ExtractPvs(ObjectContainer &objects) const
 {
         RayInfoContainer::const_iterator it, it_end = mRays.end();
@@ -264 +275 @@
 }
 
-void VspKdTreeLeaf::GetRays(VssRayContainer &rays)
+void VspKdLeaf::GetRays(VssRayContainer &rays)
 {
         RayInfoContainer::const_iterator it, it_end = mRays.end();
@@ -272 +283 @@
 }
 
-ViewCell *VspKdTreeLeaf::GetViewCell()
+VspKdViewCell *VspKdLeaf::GetViewCell()
 {
         return mViewCell;
 }
 
-/*********************************************************/
-/*            class VspKdTree implementation             */
-/*********************************************************/
-
-
-VspKdTree::VspKdTree(): mOnlyDrivingAxis(true)
-{         
-        environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
-        environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
-        environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
-        environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
-        environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
-        environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
-
-        mTermMinSize = sqr(mTermMinSize);
-
-        environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
-        environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
-        
-        environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
-        environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
-    
-        environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
-        environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
-
-        // split type
-        char sname[128];
-        environment->GetStringValue("VspKdTree.splitType", sname);
-        string name(sname);
-                
-        Debug << "======= vsp kd tree options ========" << endl;
-        Debug << "max depth: "<< mTermMaxDepth << endl;
-        Debug << "min pvs: "<< mTermMinPvs << endl;
-        Debug << "min rays: "<< mTermMinRays << endl;
-        Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
-        Debug << "max cost ratio: "<< mTermMaxCostRatio << endl;
-        Debug << "min size: "<<mTermMinSize << endl;
-
-        if (name.compare("regular") == 0)
-        {
-                Debug << "using regular split" << endl;
-                splitType = ESplitRegular;
-        }
-        else
-        {
-                if (name.compare("heuristic") == 0)
-                {
-                        Debug << "using heuristic split" << endl;
-                        splitType = ESplitHeuristic;
-                }
-                else 
-                {
-                        cerr << "Invalid VspKdTree split type " << name << endl;
-                        exit(1);
-                }
-        }
-
-        mRoot = NULL;
-
-        mSplitCandidates = new vector<SortableEntry>;
-}
-
-
-VspKdTree::~VspKdTree()
-{
-        DEL_PTR(mRoot);
-        DEL_PTR(mSplitCandidates);
-}
-
-void VspKdStatistics::Print(ostream &app) const
-{
-        app << "===== VspKdTree statistics ===============\n";
-
-        app << "#N_RAYS ( Number of rays )\n"
-                << rays << endl;
-  
-        app << "#N_INITPVS ( Initial PVS size )\n"
-                << initialPvsSize << endl;
-  
-        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
-
-        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
-
-        app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
-  
-        for (int i=0; i<7; i++)
-                app << splits[i] <<" ";
-        app << endl;
-
-        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
-                rayRefs << "\n";
-
-        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
-                rayRefs / (double)rays << "\n";
-
-        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
-                rayRefs / (double)Leaves() << "\n";
-
-        app << "#N_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" <<
-                maxRayRefs << "\n";
-
-  //  app << setprecision(4);
-
-        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" <<
-                maxDepthNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" <<
-                minPvsNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" <<
-                minRaysNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<<
-                minSizeNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" <<
-                maxRayContribNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<<
-                addedRayRefs << endl;
-
-        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n"<<
-                removedRayRefs << endl;
-
-        //  app << setprecision(4);
-
-        app << "#N_MAXPVS ( Maximal PVS size / leaf)\n"
-                << maxPvsSize << endl;
-
-        app << "#N_CTIME  ( Construction time [s] )\n"
-                << Time() << " \n";
-
-        app << "===== END OF VspKdTree statistics ==========\n";
-}
-
-
-void
-VspKdTreeLeaf::UpdatePvsSize()
+void VspKdLeaf::SetViewCell(VspKdViewCell *viewCell)
+{
+        mViewCell = viewCell;
+}
+
+
+void VspKdLeaf::UpdatePvsSize()
 {
         if (!mValidPvs) 
@@ -449 +329 @@
 }
 
-
-void
-VspKdTree::Construct(const VssRayContainer &rays,
-                                         AxisAlignedBox3 *forcedBoundingBox)
+/*********************************************************/
+/*            class VspKdTree implementation             */
+/*********************************************************/
+
+
+
+VspKdTree::VspKdTree(): mOnlyDrivingAxis(true)
+{         
+        environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
+        environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
+        environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
+        environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
+        environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
+        environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
+
+        mTermMinSize = sqr(mTermMinSize);
+
+        environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
+        environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
+        
+        environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
+        environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
+    
+        environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
+        environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
+
+        environment->GetFloatValue("VspKdTree.maxCostRatio", mMaxCostRatio);
+        environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
+
+        MergeCandidate::sMaxPvsSize = 300; // TODO: add option
+
+        // split type
+        char sname[128];
+        environment->GetStringValue("VspKdTree.splitType", sname);
+        string name(sname);
+                
+        Debug << "======= vsp kd tree options ========" << endl;
+        Debug << "max depth: "<< mTermMaxDepth << endl;
+        Debug << "min pvs: "<< mTermMinPvs << endl;
+        Debug << "min rays: "<< mTermMinRays << endl;
+        Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
+        Debug << "max cost ratio: "<< mTermMaxCostRatio << endl;
+        Debug << "min size: "<<mTermMinSize << endl;
+
+        if (name.compare("regular") == 0)
+        {
+                Debug << "using regular split" << endl;
+                splitType = ESplitRegular;
+        }
+        else
+        {
+                if (name.compare("heuristic") == 0)
+                {
+                        Debug << "using heuristic split" << endl;
+                        splitType = ESplitHeuristic;
+                }
+                else 
+                {
+                        cerr << "Invalid VspKdTree split type " << name << endl;
+                        exit(1);
+                }
+        }
+
+        mRoot = NULL;
+
+        mSplitCandidates = new vector<SortableEntry>;
+}
+
+
+VspKdTree::~VspKdTree()
+{
+        DEL_PTR(mRoot);
+        DEL_PTR(mSplitCandidates);
+}
+
+void VspKdStatistics::Print(ostream &app) const
+{
+        app << "===== VspKdTree statistics ===============\n";
+
+        app << "#N_RAYS ( Number of rays )\n"
+                << rays << endl;
+  
+        app << "#N_INITPVS ( Initial PVS size )\n"
+                << initialPvsSize << endl;
+  
+        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
+
+        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
+
+        app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
+  
+        for (int i=0; i<7; i++)
+                app << splits[i] <<" ";
+        app << endl;
+
+        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
+                rayRefs << "\n";
+
+        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
+                rayRefs / (double)rays << "\n";
+
+        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
+                rayRefs / (double)Leaves() << "\n";
+
+        app << "#N_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" <<
+                maxRayRefs << "\n";
+
+  //  app << setprecision(4);
+
+        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" <<
+                maxDepthNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" <<
+                minPvsNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" <<
+                minRaysNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<<
+                minSizeNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" <<
+                maxRayContribNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<<
+                addedRayRefs << endl;
+
+        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n"<<
+                removedRayRefs << endl;
+
+        //  app << setprecision(4);
+
+        app << "#N_( Maximal PVS size / leaf)\n"
+                << maxPvsSize << endl;
+
+        app << "#N_CTIME  ( Construction time [s] )\n"
+                << Time() << " \n";
+
+        app << "===== END OF VspKdTree statistics ==========\n";
+}
+
+
+void VspKdTree::CollectViewCells(ViewCellContainer &viewCells) const
+{
+        stack<VspKdNode *> nodeStack;
+        nodeStack.push(mRoot);
+
+        ViewCell::NewMail();
+
+        while (!nodeStack.empty()) 
+        {
+                VspKdNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                if (node->IsLeaf()) 
+                {
+                        ViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
+
+                        if (!viewCell->Mailed()) 
+                        {
+                                viewCell->Mail();
+                                viewCells.push_back(viewCell);
+                        }
+                }
+                else 
+                {
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
+
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+}
+
+void VspKdTree::Construct(const VssRayContainer &rays,
+                                                  AxisAlignedBox3 *forcedBoundingBox)
 {
         mStat.Start();
@@ -459 +511 @@
         DEL_PTR(mRoot);
 
-        mRoot = new VspKdTreeLeaf(NULL, (int)rays.size());
+        mRoot = new VspKdLeaf(NULL, (int)rays.size());
 
         // first construct a leaf that will get subdivided
-        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(mRoot);
+        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(mRoot);
         
         mStat.nodes = 1;
@@ -523 +575 @@
 
 
-VspKdTreeNode *VspKdTree::Subdivide(const TraversalData &tdata)
-{
-        VspKdTreeNode *result = NULL;
+VspKdNode *VspKdTree::Subdivide(const TraversalData &tdata)
+{
+        VspKdNode *result = NULL;
 
         priority_queue<TraversalData> tStack;
@@ -562 +614 @@
                 tStack.pop();    
                 
-                VspKdTreeNode *node = SubdivideNode((VspKdTreeLeaf *) data.mNode,
+                VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode,
                                                                                         data.mBox, backBox,     frontBox);
                 if (result == NULL)
@@ -569 +621 @@
                 if (!node->IsLeaf()) 
                 {
-                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
                         // push the children on the stack
@@ -586 +638 @@
 
 // returns selected plane for subdivision
-int VspKdTree::SelectPlane(VspKdTreeLeaf *leaf,
+int VspKdTree::SelectPlane(VspKdLeaf *leaf,
                                                    const AxisAlignedBox3 &box,
                                                    float &position,
@@ -641 +693 @@
 
                                                         
-float VspKdTree::EvalCostRatio(VspKdTreeLeaf *leaf,
+float VspKdTree::EvalCostRatio(VspKdLeaf *leaf,
                                                            const int axis,
                                                            const float position,
@@ -711 +763 @@
 }
 
-float VspKdTree::BestCostRatioRegular(VspKdTreeLeaf *leaf,
+float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf,
                                                                           int &axis,
                                                                           float &position,
@@ -772 +824 @@
 }
 
-float VspKdTree::BestCostRatioHeuristic(VspKdTreeLeaf *leaf,
+float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf,
                                                                                 int &axis,
                                                                                 float &position,
@@ -895 +947 @@
 }
 
-void VspKdTree::SortSplitCandidates(VspKdTreeLeaf *node,
+void VspKdTree::SortSplitCandidates(VspKdLeaf *node,
                                                                         const int axis)
 {
@@ -930 +982 @@
 {
         // the node became a leaf -> evaluate stats for leafs
-        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode);
+        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode);
 
         if (leaf->GetPvsSize() > mStat.maxPvsSize)
@@ -956 +1008 @@
 
 
-inline bool VspKdTree::TerminationCriteriaMet(const VspKdTreeLeaf *leaf, 
+inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf, 
                                                                                           const AxisAlignedBox3 &box) const
 {
         return ((leaf->GetPvsSize() < mTermMinPvs) || 
                     (leaf->mRays.size() < mTermMinRays) ||
-                        (leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
+                        //(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
                         (leaf->mDepth >= mTermMaxDepth) || 
                         (SqrMagnitude(box.Size()) <= mTermMinSize));
@@ -967 +1019 @@
 
 
-VspKdTreeNode *VspKdTree::SubdivideNode(VspKdTreeLeaf *leaf,
+VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf,
                                                                                 const AxisAlignedBox3 &box,
                                                                                 AxisAlignedBox3 &backBBox,
@@ -1005 +1057 @@
 
         // add the new nodes to the tree
-        VspKdTreeInterior *node = new VspKdTreeInterior(leaf->mParent);
+        VspKdInterior *node = new VspKdInterior(leaf->mParent);
 
         node->mAxis = axis;
@@ -1014 +1066 @@
         frontBBox = box;
 
-        VspKdTreeLeaf *back = new VspKdTreeLeaf(node, raysBack);
+        VspKdLeaf *back = new VspKdLeaf(node, raysBack);
         back->SetPvsSize(pvsBack);
-        VspKdTreeLeaf *front = new VspKdTreeLeaf(node, raysFront);
+        VspKdLeaf *front = new VspKdLeaf(node, raysFront);
         front->SetPvsSize(pvsFront);
 
@@ -1025 +1077 @@
         node->SetupChildLinks(back, front);
         
-        if (axis <= VspKdTreeNode::SPLIT_Z) 
+        if (axis <= VspKdNode::SPLIT_Z) 
         {
                 backBBox.SetMax(axis, position);
@@ -1110 +1162 @@
 int VspKdTree::ReleaseMemory(const int time)
 {
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
 
         // find a node in the tree which subtree will be collapsed
@@ -1120 +1172 @@
         while (!tstack.empty())
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
     
                 if (!node->IsLeaf()) 
                 {
-                        VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
                         // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
                         if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime) 
@@ -1156 +1208 @@
 
 
-VspKdTreeNode *VspKdTree::SubdivideLeaf(VspKdTreeLeaf *leaf,
+VspKdNode *VspKdTree::SubdivideLeaf(VspKdLeaf *leaf,
                                                                                 const float sizeThreshold)
 {
-        VspKdTreeNode *node = leaf;
+        VspKdNode *node = leaf;
 
         AxisAlignedBox3 leafBBox = GetBBox(leaf);
@@ -1188 +1240 @@
                                                    VssRayContainer &add)
 {
-        VspKdTreeLeaf::NewMail();
+        VspKdLeaf::NewMail();
 
         // schedule rays for removal
@@ -1218 +1270 @@
 
 void VspKdTree::RemoveRay(VssRay *ray,
-                                                  vector<VspKdTreeLeaf *> *affectedLeaves,
+                                                  vector<VspKdLeaf *> *affectedLeaves,
                                                   const bool removeAllScheduledRays)
 {
@@ -1243 +1295 @@
                         // remove the ray from the leaf
                         // find the ray in the leaf and swap it with the last ray...
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.mNode;
+                        VspKdLeaf *leaf = (VspKdLeaf *)data.mNode;
       
                         if (!leaf->Mailed()) 
@@ -1329 +1381 @@
                         // remove the ray from the leaf
                         // find the ray in the leaf and swap it with the last ray
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode);
 
                         leaf->AddRay(data.mRayData);
@@ -1340 +1392 @@
                                                                          stack<RayTraversalData> &tstack)
 {
-        VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(data.mNode);
-  
-        if (in->mAxis <= VspKdTreeNode::SPLIT_Z) 
+        VspKdInterior *in = dynamic_cast<VspKdInterior *>(data.mNode);
+  
+        if (in->mAxis <= VspKdNode::SPLIT_Z) 
         {
             // determine the side of this ray with respect to the plane
@@ -1387 +1439 @@
 
 
-int VspKdTree::CollapseSubtree(VspKdTreeNode *sroot, const int time)
+int VspKdTree::CollapseSubtree(VspKdNode *sroot, const int time)
 {
         // first count all rays in the subtree
         // use mail 1 for this purpose
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
         
         int rayCount = 0;
@@ -1413 +1465 @@
                 ++ collapsedNodes;
                 
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *) node;
+                        VspKdLeaf *leaf = (VspKdLeaf *) node;
                         
                         for(RayInfoContainer::iterator ri = leaf->mRays.begin();
@@ -1433 +1485 @@
                 else 
                 {
-                        tstack.push(((VspKdTreeInterior *)node)->GetFront());
-                        tstack.push(((VspKdTreeInterior *)node)->GetBack());
+                        tstack.push(((VspKdInterior *)node)->GetFront());
+                        tstack.push(((VspKdInterior *)node)->GetBack());
                 }
         }
@@ -1441 +1493 @@
 
         // create a new node that will hold the rays
-        VspKdTreeLeaf *newLeaf = new VspKdTreeLeaf(sroot->mParent, rayCount);
+        VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount);
         
         if (newLeaf->mParent)
@@ -1450 +1502 @@
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
 
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
                         for(RayInfoContainer::iterator ri = leaf->mRays.begin();
@@ -1476 +1528 @@
                 else 
                 {
-                        VspKdTreeInterior *interior = 
-                                dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = 
+                                dynamic_cast<VspKdInterior *>(node);
                         tstack.push(interior->GetBack());
                         tstack.push(interior->GetFront());
@@ -1486 +1538 @@
         DEL_PTR(sroot);
   
-        // for(VspKdTreeNode::SRayContainer::iterator ri = newleaf->mRays.begin();
+        // for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin();
     //      ri != newleaf->mRays.end(); ++ ri)
         //     (*ri).ray->UnMail(2);
@@ -1510 +1562 @@
 
 
-int VspKdTree::GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const
-{
-        stack<VspKdTreeNode *> tstack;
+int VspKdTree::GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const
+{
+        stack<VspKdNode *> tstack;
         tstack.push(mRoot);
 
@@ -1520 +1572 @@
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
     
           if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+                        VspKdLeaf *leaf = (VspKdLeaf *)node;
                         for (RayInfoContainer::iterator ri = leaf->mRays.begin();
                                  ri != leaf->mRays.end(); ++ ri)
@@ -1552 +1604 @@
                 else 
                 {
-                        VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
         
                         if (in->mAxis < 3) 
@@ -1578 +1630 @@
                                                                                          float &avgRayContribution)
 {
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
         tstack.push(mRoot);
         
@@ -1589 +1641 @@
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
                 if (node->IsLeaf()) 
                 {
                         leaves++;
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+                        VspKdLeaf *leaf = (VspKdLeaf *)node;
                         float c = leaf->GetAvgRayContribution();
 
@@ -1605 +1657 @@
                 } 
                 else {
-                        VspKdTreeInterior *in = (VspKdTreeInterior *)node;
+                        VspKdInterior *in = (VspKdInterior *)node;
                         // both nodes for directional splits
                         tstack.push(in->GetFront());
@@ -1621 +1673 @@
                                                         SimpleRayContainer &rays)
 {
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
         tstack.push(mRoot);
         
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
                 
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
                         float c = leaf->GetAvgRayContribution();
@@ -1649 +1701 @@
                 else 
                 {
-                        VspKdTreeInterior *in = 
-                                dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *in = 
+                                dynamic_cast<VspKdInterior *>(node);
                         // both nodes for directional splits
                         tstack.push(in->GetFront());
@@ -1663 +1715 @@
 float VspKdTree::GetAvgPvsSize()
 {
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
         tstack.push(mRoot);
 
@@ -1671 +1723 @@
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
                 
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+                        VspKdLeaf *leaf = (VspKdLeaf *)node;
                         // update pvs size
                         leaf->UpdatePvsSize();
@@ -1684 +1736 @@
                 else 
                 {
-                        VspKdTreeInterior *in = (VspKdTreeInterior *)node;
+                        VspKdInterior *in = (VspKdInterior *)node;
                         // both nodes for directional splits
                         tstack.push(in->GetFront());
@@ -1694 +1746 @@
 }
 
-VspKdTreeNode *VspKdTree::GetRoot() const
+VspKdNode *VspKdTree::GetRoot() const
 {
         return mRoot;
 }
 
-AxisAlignedBox3 VspKdTree::GetBBox(VspKdTreeNode *node) const
+AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const
 {
         if (node->mParent == NULL)
@@ -1705 +1757 @@
 
         if (!node->IsLeaf())
-                return (dynamic_cast<VspKdTreeInterior *>(node))->mBox;
+                return (dynamic_cast<VspKdInterior *>(node))->mBox;
 
         if (node->mParent->mAxis >= 3)
@@ -1740 +1792 @@
         return 
                 (sizeof(VspKdTree) + 
-                 mStat.Leaves() * sizeof(VspKdTreeLeaf) +
-                 mStat.Interior() * sizeof(VspKdTreeInterior) +
+                 mStat.Leaves() * sizeof(VspKdLeaf) +
+                 mStat.Interior() * sizeof(VspKdInterior) +
                  mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
 }
@@ -1750 +1802 @@
 }
 
-int VspKdTree::ComputePvsSize(VspKdTreeNode *node, 
+int VspKdTree::ComputePvsSize(VspKdNode *node, 
                                                           const RayInfoContainer &globalRays) const
 {
@@ -1766 +1818 @@
 }
 
-void VspKdTree::CollectLeaves(vector<VspKdTreeLeaf *> &leaves) const
-{
-        stack<VspKdTreeNode *> nodeStack;
+void VspKdTree::CollectLeaves(vector<VspKdLeaf *> &leaves) const
+{
+        stack<VspKdNode *> nodeStack;
         nodeStack.push(mRoot);
 
         while (!nodeStack.empty()) 
         {
-                VspKdTreeNode *node = nodeStack.top();
+                VspKdNode *node = nodeStack.top();
                 
                 nodeStack.pop();
@@ -1779 +1831 @@
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
                         leaves.push_back(leaf);
                 } 
                 else 
                 {
-                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
                         nodeStack.push(interior->GetBack());
@@ -1792 +1844 @@
 }
 
-int VspKdTree::FindNeighbors(VspKdTreeLeaf *n,
-                                                         vector<VspKdTreeLeaf *> &neighbors,
+int VspKdTree::FindNeighbors(VspKdLeaf *n,
+                                                         vector<VspKdLeaf *> &neighbors,
                                                          bool onlyUnmailed)
 {
-        stack<VspKdTreeNode *> nodeStack;
+        stack<VspKdNode *> nodeStack;
   
         nodeStack.push(mRoot);
@@ -1804 +1856 @@
         while (!nodeStack.empty()) 
         {
-                VspKdTreeNode *node = nodeStack.top();
+                VspKdNode *node = nodeStack.top();
                 nodeStack.pop();
 
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
                         if (leaf != n && (!onlyUnmailed || !leaf->Mailed())) 
@@ -1816 +1868 @@
                 else 
                 {
-                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
                         if (interior->mPosition > box.Max(interior->mAxis))
@@ -1837 +1889 @@
 }
 
-void VspKdTree::MergeLeaves()
-{
-        vector<VspKdTreeLeaf *> leaves;
-        priority_queue<LeafPair> mergeCandidates;
-        vector<VspKdTreeLeaf *> neighbors;
-
+
+
+void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm)
+{
+        mViewCellsManager = vcm;
+}
+
+
+int VspKdTree::CastRay(Ray &ray)
+{
+        int hits = 0;
+  
+        stack<RayTraversalData> tStack;
+  
+        float maxt = 1e6;
+        float mint = 0;
+
+        Intersectable::NewMail();
+
+        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
+                return 0;
+
+        if (mint < 0)
+                mint = 0;
+  
+        maxt += Limits::Threshold;
+  
+        Vector3 entp = ray.Extrap(mint);
+        Vector3 extp = ray.Extrap(maxt);
+  
+        VspKdNode *node = mRoot;
+        VspKdNode *farChild;
+
+        float position;
+        int axis;
+  
+        while (1) 
+        {
+                if (!node->IsLeaf()) 
+                {
+                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
+                        position = in->mPosition;
+                        axis = in->mAxis;
+
+                        if (entp[axis] <= position) 
+                        {
+                                if (extp[axis] <= position) 
+                                {
+                                        node = in->mBack;
+                                        // cases N1,N2,N3,P5,Z2,Z3
+                                        continue;
+                                } else 
+                                {
+                                        // case N4
+                                        node = in->mBack;
+                                        farChild = in->mFront;
+                                }
+                        }
+                        else 
+                        {
+                                if (position <= extp[axis]) 
+                                {
+                                        node = in->mFront;
+                                        // cases P1,P2,P3,N5,Z1
+                                        continue;
+                                } 
+                                else 
+                                {
+                                        node = in->mFront;
+                                        farChild = in->mBack;
+                                        // case P4
+                                }
+                        }
+
+                        // $$ modification 3.5.2004 - hints from Kamil Ghais
+                        // case N4 or P4
+                        float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis);
+                        //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO
+                        extp = ray.GetLoc() + ray.GetDir()*tdist;
+                        maxt = tdist;
+                } 
+                else 
+                {
+                        // compute intersection with all objects in this leaf
+                        /*KdLeaf *leaf = (KdLeaf *) node;
+                        if (ray.mFlags & Ray::STORE_KDLEAVES)
+                                ray.kdLeaves.push_back(leaf);
+                        
+                        ObjectContainer::const_iterator mi;
+                        for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); mi++) 
+                        {
+                                Intersectable *object = *mi;
+                                if (!object->Mailed() ) 
+                                {
+                                        object->Mail();
+                                        if (ray.mFlags & Ray::STORE_TESTED_OBJECTS)
+                                                ray.testedObjects.push_back(object);
+                                        hits += object->CastRay(ray);
+                                }
+                        }
+                        
+                        if (hits && ray.GetType() == Ray::LOCAL_RAY)
+                                if (ray.intersections[0].mT <= maxt)
+                                        break;
+                        
+                        // get the next node from the stack
+                        if (tStack.empty())
+                                break;
+                        
+                        entp = extp;
+                        mint = maxt;
+                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
+                                break;
+                        
+                        RayTraversalData &s  = tStack.top();
+                        node = s.mNode;
+                        extp = s.mExitPoint;
+                        maxt = s.mMaxT;
+                        tStack.pop();
+                        */
+                }
+        }
+        
+        return hits;
+}
+
+
+void VspKdTree::GenerateViewCell(VspKdLeaf *leaf)
+{
+        RayInfoContainer::const_iterator it, it_end = leaf->GetRays().end();
+
+        VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCellsManager->GenerateViewCell());
+        leaf->SetViewCell(vc);
+
+        vc->SetSize(GetBBox(leaf).GetVolume());
+        vc->mVspKdLeaves.push_back(leaf);
+
+        for (it = leaf->GetRays().begin(); it != it_end; ++ it)
+        {
+                VssRay *ray = (*it).mRay;
+
+                if (ray->mTerminationObject)
+                        vc->GetPvs().AddSample(ray->mTerminationObject);
+                
+                if (ray->mOriginObject)
+                        vc->GetPvs().AddSample(ray->mOriginObject);
+        }
+}
+
+
+void VspKdTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const
+{
+        vcStat.Reset();
+
+        stack<VspKdNode *> nodeStack;
+        nodeStack.push(mRoot);
+
+        ViewCell::NewMail();
+
+        // exclude root cell
+        //mRootCell->Mail();
+
+        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->mVspKdLeaves.size() > vcStat.maxLeaves)
+                                        vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size();          
+                        }
+                }
+                else 
+                {
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
+
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+}
+
+
+bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2)
+{
+        //-- change pointer to view cells of all leaves associated with the previous view cells
+        VspKdViewCell *fVc = l1->GetViewCell();
+        VspKdViewCell *bVc = l2->GetViewCell();
+
+        VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(
+                mViewCellsManager->MergeViewCells(*fVc, *bVc));
+
+        // if merge was unsuccessful
+        if (!vc) return false;
+
+        // set new size of view cell
+        vc->SetSize(fVc->GetSize() + bVc->GetSize());
+
+        vector<VspKdLeaf *> fLeaves = fVc->mVspKdLeaves;
+        vector<VspKdLeaf *> bLeaves = bVc->mVspKdLeaves;
+
+        vector<VspKdLeaf *>::const_iterator it;
+
+        //-- change view cells of all the other leaves the view cell belongs to
+        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
+        {
+                (*it)->SetViewCell(vc);
+                vc->mVspKdLeaves.push_back(*it);
+        }
+
+        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
+        {
+                (*it)->SetViewCell(vc);
+                vc->mVspKdLeaves.push_back(*it);
+        }
+
+        // clean up old view cells
+        DEL_PTR(fVc);
+        DEL_PTR(bVc);
+
+        return true;
+}
+
+
+
+int VspKdTree::MergeLeaves()
+{
+        vector<VspKdLeaf *> leaves;
+        priority_queue<MergeCandidate> mergeQueue;
+        
+        // collect the leaves, e.g., the "voxels" that will build the view cells
         CollectLeaves(leaves);
 
-        VspKdTreeLeaf::NewMail();
-
-        vector<VspKdTreeLeaf *>::const_iterator it, it_end = leaves.end();
-
-
+        int vcSize = (int)leaves.size();
+
+        VspKdLeaf::NewMail();
+
+        vector<VspKdLeaf *>::const_iterator it, it_end = leaves.end();
+
+        // generate view cells
         for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                VspKdTreeLeaf *leaf = *it;
-
+                GenerateViewCell(*it);
+
+        // find merge candidates and push them into queue
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                VspKdLeaf *leaf = *it;
+                
+                // no leaf is part of two merge candidates
                 if (!leaf->Mailed())
                 {
+                        leaf->Mail();
+
+                        vector<VspKdLeaf *> neighbors;
                         FindNeighbors(leaf, neighbors, true);
 
-                        vector<VspKdTreeLeaf *>::const_iterator nit, nit_end = neighbors.end();
-
-                        for (nit = neighbors.begin(); nit != neighbors.end(); ++ nit)
-                                mergeCandidates.push(LeafPair(leaf, *nit));
+                        vector<VspKdLeaf *>::const_iterator nit, 
+                                nit_end = neighbors.end();
+
+                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+                                mergeQueue.push(MergeCandidate(leaf, *nit));
+                }
+        }
+
+        int merged = 0;
+
+        float savedMaxCostRatio = 0;
+
+        Debug << "merge cost " << mergeQueue.top().GetMergeCost() << " of " << mMaxCostRatio << endl;
+
+        // use priority queue to merge leaves
+        while (!mergeQueue.empty() && 
+                   ((mMaxViewCells < vcSize) ||
+                    (mergeQueue.top().GetMergeCost() < mMaxCostRatio)))
+        {
+                ViewCell::NewMail();
+
+                Debug << "=====================" << endl;
+                MergeCandidate mc = mergeQueue.top();
+                mergeQueue.pop();
+                
+                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
+                // both view cells the same!
+                {
+                        Debug << "same view cell!!" << endl;
+                        -- vcSize;
+
+                        continue;
+                }
+
+                if (mc.Valid())
+                {
+                        mc.GetLeaf1()->GetViewCell()->Mail();
+                        mc.GetLeaf2()->GetViewCell()->Mail();
                         
-                        leaf->Mail();
-                }
-        }
-}
-
+                        Debug << "merging cells with cost " << mc.GetMergeCost() << " of " << mMaxCostRatio << endl;
+                        savedMaxCostRatio = mc.GetMergeCost();
+
+                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
+                        
+                        ++ merged;
+                        -- vcSize;
+                }
+                // merge candidate not valid, because one of the leaves was already
+                // merged with another one
+                else 
+                {
+                        Debug << "not valid " << mc.GetMergeCost() << endl;
+                        
+                        // validate and reinsert into queue
+                        mc.SetValid();
+                        Debug << "ag. valid " << mc.GetMergeCost() << endl;
+
+                        mergeQueue.push(mc);
+                }
+        }
+
+        if (mergeQueue.empty())
+                Debug << "empty queue" << endl;
+        
+        Debug << "max cost ratio: " << savedMaxCostRatio << endl;
+
+        return merged;
+}
 
 
@@ -1875 +2243 @@
 
 
-MergeCandidate::MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2):
-mLeaf1(l1), mLeaf2(l2)
-{}
-
-float MergeCandidate::EvaluateMergeCost() const
-{
-        // pvs difference
-        VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell());
-        VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell());
+MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):
+mMergeCost(0),
+mLeaf1(l1),
+mLeaf2(l2),
+mLeaf1Id(l1->GetViewCell()->mMailbox),
+mLeaf2Id(l2->GetViewCell()->mMailbox)
+{
+        EvalMergeCost();
+}
+
+
+void MergeCandidate::EvalMergeCost()
+{
+        // compute pvs differences
+        VspKdViewCell *vc1 = mLeaf1->GetViewCell();
+        VspKdViewCell *vc2 = mLeaf2->GetViewCell();
+        
+        //VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell());
+        //VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell());
 
         const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-        
-        //const int diff2 = vc2->GetPvs().Diff(vc1->GetPvs());
-        //const float simDiff = (float)max(diff1, diff2);
-
+        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
+
+        //-- compute ratio of old cost 
+        //-- (added size of left and right view cell times pvs size)
+        //-- to new rendering cost (size of merged view cell times pvs size)
         const float oldCost = 
-                vc1->GetSize() * vc1->GetPvs().GetSize() + 
-                vc2->GetSize() * vc2->GetPvs().GetSize();
-
-        const float mergedPvsCost = 
-                (diff1 + vc1->GetPvs().GetSize()) *
-                (vc1->GetSize() + vc2->GetSize());
-
-        return mergedPvsCost / oldCost;
-}
+                (float)vc1->GetPvs().GetSize() * vc1->GetSize() + 
+                (float)vc2->GetPvs().GetSize() * vc2->GetSize();
+
+        const float newCost = 
+                (float)vcPvs * (vc1->GetSize() + vc2->GetSize());
+
+        mMergeCost = newCost / oldCost;
+
+        Debug << "******************************" << endl;
+        Debug << "pvs size: " << vcPvs << " max: " << sMaxPvsSize << endl;
+        if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
+                mMergeCost += 1.0;
+
+        Debug << "old cost: " << oldCost << endl;
+        Debug << "new cost: " << newCost << endl;
+}
+
+void MergeCandidate::SetLeaf1(VspKdLeaf *l)
+{
+        mLeaf1 = l;
+}
+
+void MergeCandidate::SetLeaf2(VspKdLeaf *l)
+{
+        mLeaf2 = l;
+}
+
+VspKdLeaf *MergeCandidate::GetLeaf1()
+{
+        return mLeaf1;
+}
+
+VspKdLeaf *MergeCandidate::GetLeaf2()
+{
+        return mLeaf2;
+}
+
+bool MergeCandidate::Valid() const
+{       
+        //Debug << mLeaf1->GetViewCell()->mMailbox << " " << mLeaf1Id << endl;
+        //Debug << mLeaf2->GetViewCell()->mMailbox << " " << mLeaf2Id << endl;
+
+        return 
+                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) && 
+                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
+}
+
+float MergeCandidate::GetMergeCost() const
+{
+        return mMergeCost;
+}
+
+void MergeCandidate::SetValid()
+{
+        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
+        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
+        
+        EvalMergeCost();
+}