Changeset 465

Timestamp:

12/14/05 19:17:40 (19 years ago)

Author:

mattausch

Message:

worked on vspkd leaves merge, implemented post merge collapse

Location:

trunk/VUT

Files:

• GtpVisibilityPreprocessor/scripts/default.env (modified) (5 diffs)
• GtpVisibilityPreprocessor/src/Environment.cpp (modified) (2 diffs)
• GtpVisibilityPreprocessor/src/RenderSimulator.cpp (modified) (2 diffs)
• GtpVisibilityPreprocessor/src/ViewCellsManager.cpp (modified) (4 diffs)
• GtpVisibilityPreprocessor/src/VspKdTree.cpp (modified) (125 diffs)
• GtpVisibilityPreprocessor/src/VspKdTree.h (modified) (3 diffs)
• GtpVisibilityPreprocessor/src/VssPreprocessor.cpp (modified) (4 diffs)
• GtpVisibilityPreprocessor/src/X3dExporter.cpp (modified) (3 diffs)
• scripts/GtpVisibility.suo (modified) (previous)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -13 +13 @@
 #;../data/vienna/vienna-plane.x3d
 #       filename ../data/vienna/viewcells-25-sel.x3d
-        filename ../data/atlanta/atlanta2.x3d
+#       filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
-#       filename ../data/soda/soda5.dat
+        filename ../data/soda/soda5.dat
 }
 
@@ -26 +26 @@
 VssPreprocessor {
         samplesPerPass  100000
-        initialSamples 1000000
-        vssSamples 3000000
+        initialSamples 500000
+        vssSamples 200000
         vssSamplesPerPass 100000
         useImportanceSampling true
@@ -38 +38 @@
 
         maxDepth        40
-        minPvs          3
-        minRays         100
+        minPvs          30
+        minRays         1000
         minSize         0.001
-        maxCostRatio    2.0
+        maxCostRatio    0.9
         maxRayContribution 0.05
         
         maxTotalMemory  200
-        maxStaticMemory 100
+        maxStaticMemory 20
 
         splitType regular
@@ -284 +284 @@
         Termination {
                 maxDepth                40
-                minPvs                  90
-                minRays                 10
+                minPvs                  5
+                minRays                 500
                 minSize                 0.1
                 maxCostRatio            999.0
@@ -299 +299 @@
         
         # maximal cost for merging a view cell
-        maxCostRatio 1.4
+        PostProcess {
+                maxCostRatio 5000000
+                minViewCells 100
+                maxPvsSize   50000
+        }
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1398 +1398 @@
                  "100000");
 
-  RegisterOption("VspKdTree.maxCostRatio",
-                 optFloat,
-                 "-vsp_kd_max_cost_ratio=",
-                 "1.5");
-
   RegisterOption("VspKdTree.Termination.maxDepth", 
                 optInt, 
@@ -1480 +1475 @@
           "vsp_min_colldepth=", 
           "4");
-  
+
+  RegisterOption("VspKdTree.PostProcess.maxCostRatio",
+                 optFloat,
+                 "-vsp_kd_post_process_max_cost_ratio=",
+                 "1.5");
+
+  RegisterOption("VspKdTree.PostProcess.minViewCells", 
+          optInt, 
+          "vsp_term_post_process_min_view_cells=", 
+          "1000");
+
+  RegisterOption("VspKdTree.PostProcess.maxPvsSize", 
+          optInt, 
+          "vsp_term_post_process_max_pvs_size=", 
+          "100");
+
   /************************************************************************************/
   /*                   VSS Preprocessor cells related options                         */

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

@@ -338 +338 @@
 
 
-/********************************************************/
-/*     class BspRenderSimulator implementation          */
-/********************************************************/
+/*************************************************************/
+/*        class VspKdRenderSimulator implementation          */
+/*************************************************************/
 
 
@@ -358 +358 @@
 
 SimulationStatistics VspKdRenderSimulator::SimulateRendering()
-{
-        SimulationStatistics simStat;
+{SimulationStatistics simStat;
 
         simStat.Reset();
         simStat.Start();
 
-        // TODO
+        Real renderTime = 0;
+        
+        // overhead for loading the PVS of the view cells
+        float loadPvsOverhead = 0;
+        // probability that view point lies in a view cell
+        float pInVcTotal = 0;
+
+        // total probability that a view cell border is crossed
+/*      const float pCrossVcTotal = mVspBspTree->GetBoundingBox().SurfaceArea();
+
+        // collect all view cells
+        ViewCellContainer viewCells;
+        mVspBspTree->CollectViewCells(viewCells);
+
+        ViewCellContainer::const_iterator it, it_end = viewCells.end();
+
+        // surface area substitute for probability
+        PolygonContainer geom;
+float overallarea = 0;
+        for (it = viewCells.begin(); it != it_end; ++ it)
+        {
+                // compute view cell area
+                mVspBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(*it), geom);
+
+                const float area = Polygon3::GetArea(geom);
+                if (area < 0.0001)
+                        Debug << "warning, area: " << area << endl;
+                CLEAR_CONTAINER(geom);
+
+                // area substitute for view point probability
+                float pInVc = area;
+                                
+                // compute render time of PVS times probability that view point is in view cell
+                float vcCost = pInVc * RenderPvs(*(*it), mObjRenderCost);
+                //Debug << "p: " << pInVc << " rendercost: " << RenderPvs(*(*it), mObjRenderCost) << endl;
+                renderTime += vcCost;
+
+                if (vcCost > simStat.maxCost)
+                        simStat.maxCost = vcCost;
+                else if (vcCost < simStat.minCost)
+                        simStat.minCost = vcCost;
+
+                // probability that a view cell border is crossed
+                float pCrossVc = area * mMoveSpeed;
+
+                // crossing the border of a view cell is also depending on the move speed
+                loadPvsOverhead += pCrossVc * mVcOverhead;
+overallarea += area;
+                pInVcTotal += pInVc;
+        }
+        Debug << "overall area: " << overallarea << endl;
+        
+        renderTime /= pInVcTotal;
+        loadPvsOverhead /= pCrossVcTotal;
+
+        simStat.avgRtWithoutOverhead = renderTime;
+        simStat.avgRenderTime = renderTime + loadPvsOverhead;
+        
+        simStat.maxCost /= pInVcTotal;
+        simStat.minCost /= pInVcTotal;
+
         simStat.Stop();
-
+*/
         return simStat;
 }
 
 Real VspKdRenderSimulator::RenderPvs(ViewCell &viewCell, 
-                                                                          float objRenderTime) const
+                                                                         float objRenderTime) const
 {
         return 0; // TODO

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -1037 +1037 @@
                 return 0;
 
-        if (castRay)
-                mVspKdTree->CastRay(ray);
+//      if (castRay)
+//              mVspKdTree->CastRay(ray);
 
         int sampleContributions = 0;
@@ -1064 +1064 @@
         if (!ViewCellsConstructed())
                 return;
+
+        bool exportRays = true;
 
         //-- export tree leaves
@@ -1073 +1075 @@
                 exporter->ExportVspKdTree(*mVspKdTree);
 
-                if (0) 
+                if (1) 
                         exporter->ExportGeometry(objects);
-
-                bool exportRays = false;
 
                 if (exportRays) 
@@ -1149 +1149 @@
         //-- export final view cells
         Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 
-        //exporter->SetWireframe();
+        exporter->SetWireframe();
         //exporter->ExportVspKdTreeViewCells(*mVspKdTree, vcStats.maxPvs);
         exporter->ExportVspKdTreeViewCells(*mVspKdTree);
 
-        Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl;
-
-        if (0) 
+        if (1) 
+        {
+                exporter->SetFilled();
                 exporter->ExportGeometry(objects);
-
-        bool exportRays = false;
-
+        }
         if (exportRays) 
         {

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -44 +44 @@
         if (!object)
                 return;
-                
-        if (side <= 0) 
-        {
-                if (!object->Mailed() && !object->Mailed(2)) 
+
+        if (side <= 0)
+        {
+                if (!object->Mailed() && !object->Mailed(2))
                 {
                         ++ pvsBack;
@@ -57 +57 @@
                 }
         }
-        
+
         if (side >= 0)
         {
-                if (!object->Mailed(1) && !object->Mailed(2)) 
+                if (!object->Mailed(1) && !object->Mailed(2))
                 {
                         ++ pvsFront;
@@ -78 +78 @@
 // Inline constructor
 VspKdNode::VspKdNode(VspKdInterior *p):
-mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0) 
+mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)
 {}
 
-VspKdNode::~VspKdNode() 
+VspKdNode::~VspKdNode()
 {};
 
@@ -94 +94 @@
 }
 
-bool VspKdNode::IsLeaf() const 
-{ 
-        return mAxis == -1; 
-}
-  
-int VspKdNode::GetAccessTime() 
+bool VspKdNode::IsLeaf() const
+{
+        return mAxis == -1;
+}
+
+int VspKdNode::GetAccessTime()
 {
         return 0x7FFFFFF;
@@ -118 +118 @@
 }
 
-void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f) 
+void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f)
 {
         mBack = b;
@@ -126 +126 @@
 }
 
-void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild, 
+void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild,
                                                                                  VspKdNode *newChild)
 {
@@ -135 +135 @@
 }
 
-int VspKdInterior::Type() const  
-{ 
-        return EInterior; 
-}
-  
+int VspKdInterior::Type() const
+{
+        return EInterior;
+}
+
 VspKdInterior::~VspKdInterior()
 {
@@ -145 +145 @@
         DEL_PTR(mFront);
 }
-  
-void VspKdInterior::Print(ostream &s) const 
+
+void VspKdInterior::Print(ostream &s) const
 {
         switch (mAxis)
@@ -163 +163 @@
         mFront->Print(s);
 }
-        
-int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 
+
+int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)
 {
         return rayData.ComputeRayIntersection(mAxis, mPosition, t);
@@ -191 +191 @@
 }
 
-VspKdLeaf::~VspKdLeaf() 
-{
-}
-
-int VspKdLeaf::Type() const  
-{ 
-        return ELeaf; 
-}
-
-void VspKdLeaf::Print(ostream &s) const 
+VspKdLeaf::~VspKdLeaf()
+{
+}
+
+int VspKdLeaf::Type() const
+{
+        return ELeaf;
+}
+
+void VspKdLeaf::Print(ostream &s) const
 {
         s << endl << "L: r = " << (int)mRays.size() << endl;
 };
 
-void VspKdLeaf::AddRay(const RayInfo &data) 
+void VspKdLeaf::AddRay(const RayInfo &data)
 {
         mValidPvs = false;
@@ -212 +212 @@
 }
 
-int VspKdLeaf::GetPvsSize() const 
+int VspKdLeaf::GetPvsSize() const
 {
         return mPvsSize;
 }
 
-void VspKdLeaf::SetPvsSize(const int s) 
+void VspKdLeaf::SetPvsSize(const int s)
 {
         mPvsSize = s;
@@ -223 +223 @@
 
 void VspKdLeaf::Mail()
-{ 
-        mMailbox = sMailId; 
-}
-
-void VspKdLeaf::NewMail() 
-{ 
-        ++ sMailId; 
-}
-
-bool VspKdLeaf::Mailed() const 
-{ 
-        return mMailbox == sMailId; 
+{
+        mMailbox = sMailId;
+}
+
+void VspKdLeaf::NewMail()
+{
+        ++ sMailId;
+}
+
+bool VspKdLeaf::Mailed() const
+{
+        return mMailbox == sMailId;
 }
 
@@ -247 +247 @@
 }
 
-float VspKdLeaf::GetAvgRayContribution() const 
+float VspKdLeaf::GetAvgRayContribution() const
 {
         return GetPvsSize() / ((float)mRays.size() + Limits::Small);
 }
 
-float VspKdLeaf::GetSqrRayContribution() const 
+float VspKdLeaf::GetSqrRayContribution() const
 {
         return sqr(GetAvgRayContribution());
@@ -296 +296 @@
 void VspKdLeaf::UpdatePvsSize()
 {
-        if (!mValidPvs) 
+        if (!mValidPvs)
         {
                 Intersectable::NewMail();
                 int pvsSize = 0;
-                for(RayInfoContainer::iterator ri = mRays.begin(); 
+                for(RayInfoContainer::iterator ri = mRays.begin();
                         ri != mRays.end(); ++ ri)
                 {
-                        if ((*ri).mRay->IsActive()) 
+                        if ((*ri).mRay->IsActive())
                         {
                                 Intersectable *object;
 #if BIDIRECTIONAL_RAY
                                 object = (*ri).mRay->mOriginObject;
-                        
-                                if (object && !object->Mailed()) 
+
+                                if (object && !object->Mailed())
                                 {
                                         ++ pvsSize;
@@ -316 +316 @@
 #endif
                                 object = (*ri).mRay->mTerminationObject;
-                                if (object && !object->Mailed()) 
+                                if (object && !object->Mailed())
                                 {
                                         ++ pvsSize;
@@ -336 +336 @@
 
 VspKdTree::VspKdTree(): mOnlyDrivingAxis(true)
-{         
+{
         environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
         environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
@@ -348 +348 @@
         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
+        //environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
+
+        environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMinViewCells);
+        environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMaxCostRatio);
+        environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize",
+                                                         MergeCandidate::sMaxPvsSize);
 
         // split type
@@ -364 +366 @@
         environment->GetStringValue("VspKdTree.splitType", sname);
         string name(sname);
-                
+
         Debug << "======= vsp kd tree options ========" << endl;
         Debug << "max depth: "<< mTermMaxDepth << endl;
@@ -385 +387 @@
                         splitType = ESplitHeuristic;
                 }
-                else 
+                else
                 {
                         cerr << "Invalid VspKdTree split type " << name << endl;
@@ -410 +412 @@
         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";
 
@@ -419 +421 @@
 
         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] <<" ";
@@ -478 +480 @@
         ViewCell::NewMail();
 
-        while (!nodeStack.empty()) 
+        while (!nodeStack.empty())
         {
                 VspKdNode *node = nodeStack.top();
                 nodeStack.pop();
 
-                if (node->IsLeaf()) 
+                if (node->IsLeaf())
                 {
                         ViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
 
-                        if (!viewCell->Mailed()) 
+                        if (!viewCell->Mailed())
                         {
                                 viewCell->Mail();
@@ -493 +495 @@
                         }
                 }
-                else 
+                else
                 {
                         VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
@@ -507 +509 @@
 {
         mStat.Start();
- 
+
         mMaxMemory = mMaxStaticMemory;
         DEL_PTR(mRoot);
@@ -515 +517 @@
         // first construct a leaf that will get subdivided
         VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(mRoot);
-        
+
         mStat.nodes = 1;
         mBox.Initialize();
@@ -528 +530 @@
                 mBox.Include((*ri)->GetOrigin());
                         if ((*ri)->mTerminationObject)
-                                mBox.Include((*ri)->GetTermination()); 
+                                mBox.Include((*ri)->GetTermination());
                 }
 
@@ -537 +539 @@
                 //leaf->AddRay(RayInfo(*ri));
                 VssRay *ray = *ri;
-                
+
                 float minT, maxT;
 
@@ -544 +546 @@
                 {
                         float len = ray->Length();
-                        
-                        if (!len) 
+
+                        if (!len)
                                 len = Limits::Small;
-                
-                        leaf->AddRay(RayInfo(ray, minT / len, maxT / len)); 
-                }
-        }
-        
+
+                        leaf->AddRay(RayInfo(ray, minT / len, maxT / len));
+                }
+        }
+
         mStat.rays = (int)leaf->mRays.size();
         leaf->UpdatePvsSize();
-        
+
         mStat.initialPvsSize = leaf->GetPvsSize();
-        
+
         // Subdivide();
         mRoot = Subdivide(TraversalData(leaf, mBox, 0));
 
-        if (mSplitCandidates) 
+        if (mSplitCandidates)
         {
                 // force release of this vector
@@ -566 +568 @@
                 mSplitCandidates = new vector<SortableEntry>;
         }
-  
+
         mStat.Stop();
 
@@ -581 +583 @@
         priority_queue<TraversalData> tStack;
         //stack<TraversalData> tStack;
-  
+
         tStack.push(tdata);
 
         AxisAlignedBox3 backBox;
         AxisAlignedBox3 frontBox;
-  
+
         int lastMem = 0;
 
-        while (!tStack.empty()) 
+        while (!tStack.empty())
         {
                 float mem = GetMemUsage();
-                
-                if (lastMem / 10 != ((int)mem) / 10) 
+
+                if (lastMem / 10 != ((int)mem) / 10)
                 {
                         Debug << mem << " MB" << endl;
                 }
                 lastMem = (int)mem;
-                
-                if (1 && mem > mMaxMemory) 
+
+                if (1 && mem > mMaxMemory)
                 {
                         Debug << "memory limit reached: " << mem << endl;
                         // count statistics on unprocessed leafs
-                        while (!tStack.empty()) 
+                        while (!tStack.empty())
                         {
                                 EvaluateLeafStats(tStack.top());
@@ -610 +612 @@
                         break;
                 }
-    
+
                 TraversalData data = tStack.top();
-                tStack.pop();    
-                
+                tStack.pop();
+
                 VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode,
                                                                                         data.mBox, backBox,     frontBox);
                 if (result == NULL)
                         result = node;
-    
-                if (!node->IsLeaf()) 
+
+                if (!node->IsLeaf())
                 {
                         VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
@@ -626 +628 @@
                         tStack.push(TraversalData(interior->GetBack(), backBox, data.mDepth + 1));
                         tStack.push(TraversalData(interior->GetFront(), frontBox, data.mDepth + 1));
-                } 
-                else 
+                }
+                else
                 {
                         EvaluateLeafStats(data);
@@ -649 +651 @@
         int axis = 0;
         float costRatio = 0;
-        
-        if (splitType == ESplitRegular) 
+
+        if (splitType == ESplitRegular)
         {
                 costRatio = BestCostRatioRegular(leaf,
@@ -659 +661 @@
                                                                                  pvsBack,
                                                                                  pvsFront);
-        } 
+        }
         else if (splitType == ESplitHeuristic)
         {
                         costRatio = BestCostRatioHeuristic(leaf,
-                                                                                           axis,        
+                                                                                           axis,
                                                                                            position,
                                                                                            raysBack,
@@ -670 +672 @@
                                                                                            pvsFront);
         }
-        else 
+        else
         {
                 cerr << "VspKdTree: Unknown split heuristics\n";
@@ -676 +678 @@
         }
 
-        if (costRatio > mTermMaxCostRatio) 
+        if (costRatio > mTermMaxCostRatio)
         {
                 Debug << "Too big cost ratio " << costRatio << endl;
@@ -683 +685 @@
 
         if (0)
-                Debug << "pvs=" << leaf->mPvsSize 
-                          << " rays=" << (int)leaf->mRays.size() 
-                          << " rc=" << leaf->GetAvgRayContribution() 
+                Debug << "pvs=" << leaf->mPvsSize
+                          << " rays=" << (int)leaf->mRays.size()
+                          << " rc=" << leaf->GetAvgRayContribution()
                           << " axis=" << axis << endl;
-        
+
         return axis;
 }
 
 
-                                                        
+
 float VspKdTree::EvalCostRatio(VspKdLeaf *leaf,
                                                            const int axis,
@@ -709 +711 @@
 
         Intersectable::NewMail(3);
-        
+
         // eval pvs size
         int pvsSize = leaf->GetPvsSize();
@@ -719 +721 @@
                         ri != leaf->mRays.end(); ++ ri)
                 {
- if (!(*ri).mRay->IsActive()) 
+ if (!(*ri).mRay->IsActive())
                                                                 continue;
-                                                                
+
                                                                 // determine the side of this ray with respect to the plane
                                                                 float t;
                                                                 int side = (*ri).ComputeRayIntersection(axis, position, t);
                 //                              (*ri).mRay->mSide = side;
-                        
+
                 if (side <= 0)
                         ++ raysBack;
-                                
+
                 if (side >= 0)
                         ++ raysFront;
-                                
+
                 AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
-        }       
+        }
 
         if (0)
@@ -743 +745 @@
                 return sum / oldCost;
         }
-        else 
+        else
         {
                 AxisAlignedBox3 box = GetBBox(leaf);
-        
+
                 float minBox = box.Min(axis);
                 float maxBox = box.Max(axis);
                 float sizeBox = maxBox - minBox;
-                
+
                 // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position);
                 const float sum = pvsBack * (position - minBox) + pvsFront * (maxBox - position);
 
                 newCost = mCtDivCi + sum  / sizeBox;
-        
+
                 //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
                 //  float oldCost = leaf->mRays.size();
                 const float oldCost = (float)pvsSize;
-                
+
                 return newCost / oldCost;
         }
@@ -778 +780 @@
         float nCostRatio[3];
         int bestAxis = -1;
-        
+
         AxisAlignedBox3 sBox = GetBBox(leaf);
 
         const int sAxis = sBox.Size().DrivingAxis();
 
-        for (axis = 0; axis < 3; ++ axis) 
-        {
-                if (!mOnlyDrivingAxis || axis == sAxis) 
-                {
-                        
+        for (axis = 0; axis < 3; ++ axis)
+        {
+                if (!mOnlyDrivingAxis || axis == sAxis)
+                {
+
                         nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis]) * 0.5f;
-                                                
+
                         nCostRatio[axis] = EvalCostRatio(leaf,
                                                                                          axis,
@@ -803 +805 @@
                         else if (nCostRatio[axis] < nCostRatio[bestAxis])
                         {
-                                /*Debug << "pvs front " << nPvsBack[axis] 
+                                /*Debug << "pvs front " << nPvsBack[axis]
                                           << " pvs back " << nPvsFront[axis]
                                           << " overall pvs " << leaf->GetPvsSize() << endl;*/
                                 bestAxis = axis;
                         }
-                        
+
                 }
         }
@@ -821 +823 @@
         pvsBack = nPvsBack[bestAxis];
         pvsFront = nPvsFront[bestAxis];
-        
+
         return nCostRatio[bestAxis];
 }
@@ -835 +837 @@
         AxisAlignedBox3 box = GetBBox(leaf);
         //      AxisAlignedBox3 dirBox = GetDirBBox(node);
-        
+
         axis = box.Size().DrivingAxis();
-                
+
         SortSplitCandidates(leaf, axis);
-  
+
         // go through the lists, count the number of objects left and right
         // and evaluate the following cost funcion:
         // C = ct_div_ci  + (ql*rl + qr*rr)/queries
-        
+
         int rl = 0, rr = (int)leaf->mRays.size();
         int pl = 0, pr = leaf->GetPvsSize();
@@ -850 +852 @@
         float maxBox = box.Max(axis);
         float sizeBox = maxBox - minBox;
-        
+
         float minBand = minBox + 0.1f*(maxBox - minBox);
         float maxBand = minBox + 0.9f*(maxBox - minBox);
-        
+
         float sum = rr*sizeBox;
         float minSum = 1e20f;
-        
+
         Intersectable::NewMail();
 
@@ -866 +868 @@
                 {
                         Intersectable *object = (*ri).mRay->mTerminationObject;
-                        
+
                         if (object)
-                                if (!object->Mailed()) 
+                                if (!object->Mailed())
                                 {
                                         object->Mail();
                                         object->mCounter = 1;
-                                } 
+                                }
                                 else
                                         ++ object->mCounter;
                 }
         }
-        
+
         Intersectable::NewMail();
-        
+
         for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
-                ci < mSplitCandidates->end(); ++ ci) 
+                ci < mSplitCandidates->end(); ++ ci)
         {
                 VssRay *ray;
-                        
-                switch ((*ci).type) 
-                {
-                        case SortableEntry::ERayMin: 
+
+                switch ((*ci).type)
+                {
+                        case SortableEntry::ERayMin:
                                 {
                                         ++ rl;
                                         ray = (VssRay *) (*ci).data;
                                         Intersectable *object = ray->mTerminationObject;
-                                        if (object && !object->Mailed()) 
+                                        if (object && !object->Mailed())
                                         {
                                                 object->Mail();
@@ -899 +901 @@
                                         break;
                                 }
-                        case SortableEntry::ERayMax: 
+                        case SortableEntry::ERayMax:
                                 {
                                         -- rr;
-                                        
+
                                         ray = (VssRay *) (*ci).data;
                                         Intersectable *object = ray->mTerminationObject;
-                                        
+
                                         if (object)
                                         {
@@ -911 +913 @@
                                                 -- pr;
                                         }
-                                                
+
                                         break;
                                 }
                 }
-                        
-                if ((*ci).value > minBand && (*ci).value < maxBand) 
+
+                if ((*ci).value > minBand && (*ci).value < maxBand)
                 {
                         sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
-                
+
                         //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
                         // cout<<"cost= "<<sum<<endl;
-                        
-                        if (sum < minSum) 
+
+                        if (sum < minSum)
                         {
                                 minSum = sum;
                                 position = (*ci).value;
-                        
+
                                 raysBack = rl;
                                 raysFront = rr;
-                        
+
                                 pvsBack = pl;
                                 pvsFront = pr;
-                                
+
                         }
                 }
@@ -941 +943 @@
         float newCost = mCtDivCi + minSum / sizeBox;
         float ratio = newCost / oldCost;
-  
+
         //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
         //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
-        
+
         return ratio;
 }
@@ -952 +954 @@
 {
         mSplitCandidates->clear();
-  
+
         int requestedSize = 2 * (int)(node->mRays.size());
         // creates a sorted split candidates array
         if (mSplitCandidates->capacity() > 500000 &&
-                requestedSize < (int)(mSplitCandidates->capacity()/10) ) 
+                requestedSize < (int)(mSplitCandidates->capacity()/10) )
         {
         DEL_PTR(mSplitCandidates);
                 mSplitCandidates = new vector<SortableEntry>;
         }
-  
+
         mSplitCandidates->reserve(requestedSize);
 
-        // insert all queries 
+        // insert all queries
         for(RayInfoContainer::const_iterator ri = node->mRays.begin();
-                ri < node->mRays.end(); ++ ri) 
+                ri < node->mRays.end(); ++ ri)
         {
                 bool positive = (*ri).mRay->HasPosDir(axis);
-                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
+                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
                                                                                                   (*ri).ExtrapOrigin(axis), (void *)&*ri));
-                
+
                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
                                                                                                   (*ri).ExtrapTermination(axis), (void *)&*ri));
         }
-        
+
         stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
 }
@@ -994 +996 @@
         if (data.mDepth >= mTermMaxDepth)
                 ++ mStat.maxDepthNodes;
-  
+
         if (leaf->GetPvsSize() < mTermMinPvs)
                 ++ mStat.minPvsNodes;
@@ -1003 +1005 @@
         if (leaf->GetAvgRayContribution() > mTermMaxRayContribution)
                 ++ mStat.maxRayContribNodes;
-        
-        if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize) 
+
+        if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize)
                 ++ mStat.minSizeNodes;
 }
 
 
-inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf, 
+inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf,
                                                                                           const AxisAlignedBox3 &box) const
 {
-        return ((leaf->GetPvsSize() < mTermMinPvs) || 
+        return ((leaf->GetPvsSize() < mTermMinPvs) ||
                     (leaf->mRays.size() < mTermMinRays) ||
                         //(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
-                        (leaf->mDepth >= mTermMaxDepth) || 
+                        (leaf->mDepth >= mTermMaxDepth) ||
                         (SqrMagnitude(box.Size()) <= mTermMinSize));
 }
@@ -1027 +1029 @@
         if (TerminationCriteriaMet(leaf, box))
         {
-                if (1 && leaf->mDepth >= mTermMaxDepth) 
+                if (1 && leaf->mDepth >= mTermMaxDepth)
                 {
                         Debug << "Warning: max depth reached depth=" << (int)leaf->mDepth<<" rays=" << (int)leaf->mRays.size() << endl;
@@ -1033 +1035 @@
                 }
                 //Debug << "depth: " << (int)leaf->mDepth << " pvs: " << leaf->GetPvsSize() << " rays: " << leaf->mRays.size() << endl;
-                
+
                 return leaf;
         }
-        
+
         float position;
         // first count ray sides
@@ -1043 +1045 @@
         int pvsBack;
         int pvsFront;
-        
+
         // select subdivision axis
         const int axis = SelectPlane(leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
@@ -1049 +1051 @@
         //Debug << "rays back=" << raysBack << " rays front=" << raysFront << " pvs back=" << pvsBack << " pvs front=" <<       pvsFront << endl;
 
-        if (axis == -1) 
+        if (axis == -1)
         {
                 return leaf;
         }
-  
+
         mStat.nodes += 2;
         //++ mStat.splits[axis];
@@ -1063 +1065 @@
         node->mPosition = position;
         node->mBox = box;
-          
+
         backBBox = box;
         frontBBox = box;
@@ -1077 +1079 @@
         // and setup child links
         node->SetupChildLinks(back, front);
-        
-        if (axis <= VspKdNode::SPLIT_Z) 
+
+        if (axis <= VspKdNode::SPLIT_Z)
         {
                 backBBox.SetMax(axis, position);
                 frontBBox.SetMin(axis, position);
-                
+
                 for(RayInfoContainer::iterator ri = leaf->mRays.begin();
-                                ri != leaf->mRays.end(); ++ ri) 
-                {
-                        if ((*ri).mRay->IsActive()) 
+                                ri != leaf->mRays.end(); ++ ri)
+                {
+                        if ((*ri).mRay->IsActive())
                         {
                                 // first unref ray from the former leaf
@@ -1094 +1096 @@
                                 int side = node->ComputeRayIntersection(*ri, t);
 
-                                if (side == 0) 
+                                if (side == 0)
                                 {
-                                        if ((*ri).mRay->HasPosDir(axis)) 
+                                        if ((*ri).mRay->HasPosDir(axis))
                                         {
                                                 back->AddRay(RayInfo((*ri).mRay,
@@ -1104 +1106 @@
                                                                                           t,
                                                                                           (*ri).mMaxT));
-                                        } 
-                                        else 
+                                        }
+                                        else
                                         {
                                                 back->AddRay(RayInfo((*ri).mRay,
@@ -1114 +1116 @@
                                                                                           t));
                                         }
-                                } 
+                                }
                                 else
-                                        if (side == 1) 
+                                        if (side == 1)
                                                 front->AddRay(*ri);
                                         else
@@ -1123 +1125 @@
                                 (*ri).mRay->Unref();
                 }
-        } 
-        else 
+        }
+        else
         {
                 // rays front/back
-    
+
         for (RayInfoContainer::iterator ri = leaf->mRays.begin();
-                        ri != leaf->mRays.end(); ++ ri) 
-                {
-                        if ((*ri).mRay->IsActive()) 
+                        ri != leaf->mRays.end(); ++ ri)
+                {
+                        if ((*ri).mRay->IsActive())
                         {
                                 // first unref ray from the former leaf
@@ -1141 +1143 @@
                                 else
                                         side = -1;
-                                
+
                                 if (side == 1)
                                         front->AddRay(*ri);
                                 else
-                                        back->AddRay(*ri);              
-                        } 
+                                        back->AddRay(*ri);
+                        }
                         else
                                 (*ri).mRay->Unref();
                 }
         }
-        
+
         // update stats
         mStat.rayRefs -= (int)leaf->mRays.size();
@@ -1175 +1177 @@
                 VspKdNode *node = tstack.top();
                 tstack.pop();
-    
-                if (!node->IsLeaf()) 
+
+                if (!node->IsLeaf())
                 {
                         VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
                         // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
-                        if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime) 
+                        if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime)
                         {
                                 released = CollapseSubtree(node, time);
                                 break;
                         }
-                        if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime()) 
+                        if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime())
                         {
                                 tstack.push(in->GetFront());
                                 tstack.push(in->GetBack());
-                        } 
-                        else 
+                        }
+                        else
                         {
                                 tstack.push(in->GetBack());
@@ -1198 +1200 @@
         }
 
-        while (tstack.empty()) 
+        while (tstack.empty())
         {
                 // could find node to collaps...
@@ -1204 +1206 @@
                 break;
         }
-  
+
         return released;
 }
@@ -1218 +1220 @@
         static int pass = 0;
         ++ pass;
-        
+
         // check if we should perform a dynamic subdivision of the leaf
         if (// leaf->mRays.size() > (unsigned)termMinCost &&
-                (leaf->GetPvsSize() >= mTermMinPvs) && 
+                (leaf->GetPvsSize() >= mTermMinPvs) &&
                 (SqrMagnitude(leafBBox.Size()) > sizeThreshold) )
         {
         // memory check and release
-                if (GetMemUsage() > mMaxTotalMemory) 
+                if (GetMemUsage() > mMaxTotalMemory)
                         ReleaseMemory(pass);
-                
+
                 AxisAlignedBox3 backBBox, frontBBox;
 
@@ -1245 +1247 @@
         // schedule rays for removal
         for(VssRayContainer::const_iterator ri = remove.begin();
-                ri != remove.end(); ++ ri) 
-        {
-                (*ri)->ScheduleForRemoval();  
+                ri != remove.end(); ++ ri)
+        {
+                (*ri)->ScheduleForRemoval();
         }
 
         int inactive = 0;
 
-        for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri) 
+        for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri)
         {
                 if ((*ri)->ScheduledForRemoval())
@@ -1263 +1265 @@
 
         //  cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
-        for (VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri) 
+        for (VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri)
         {
                 AddRay(*ri);
@@ -1277 +1279 @@
 
         tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
-  
+
         RayTraversalData data;
 
         // cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
-        while (!tstack.empty()) 
+        while (!tstack.empty())
         {
                 data = tstack.top();
                 tstack.pop();
 
-                if (!data.mNode->IsLeaf()) 
+                if (!data.mNode->IsLeaf())
                 {
                         // split the set of rays in two groups intersecting the
                         // two subtrees
                         TraverseInternalNode(data, tstack);
-        } 
-                else 
+        }
+                else
                 {
                         // remove the ray from the leaf
                         // find the ray in the leaf and swap it with the last ray...
                         VspKdLeaf *leaf = (VspKdLeaf *)data.mNode;
-      
-                        if (!leaf->Mailed()) 
+
+                        if (!leaf->Mailed())
                         {
                                 leaf->Mail();
-                                
+
                                 if (affectedLeaves)
                                         affectedLeaves->push_back(leaf);
-        
-                                if (removeAllScheduledRays) 
+
+                                if (removeAllScheduledRays)
                                 {
                                         int tail = (int)leaf->mRays.size() - 1;
 
-                                        for (int i=0; i < (int)(leaf->mRays.size()); ++ i) 
+                                        for (int i=0; i < (int)(leaf->mRays.size()); ++ i)
                                         {
-                                                if (leaf->mRays[i].mRay->ScheduledForRemoval()) 
+                                                if (leaf->mRays[i].mRay->ScheduledForRemoval())
                                                 {
                                                         // find a ray to replace it with
-                                                        while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval()) 
+                                                        while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval())
                                                         {
                                                                 ++ mStat.removedRayRefs;
                                                                 leaf->mRays[tail].mRay->Unref();
                                                                 leaf->mRays.pop_back();
-                                                                
+
                                                                 -- tail;
                                                         }
-                                                        
+
                                                         if (tail < i)
                                                                 break;
-              
+
                                                         ++ mStat.removedRayRefs;
-              
+
                                                         leaf->mRays[i].mRay->Unref();
                                                         leaf->mRays[i] = leaf->mRays[tail];
@@ -1336 +1338 @@
                                 }
                         }
-      
+
                         if (!removeAllScheduledRays)
-                                for (int i=0; i < (int)leaf->mRays.size(); i++) 
+                                for (int i=0; i < (int)leaf->mRays.size(); i++)
                                 {
-                                        if (leaf->mRays[i].mRay == ray) 
+                                        if (leaf->mRays[i].mRay == ray)
                                         {
                                                 ++ mStat.removedRayRefs;
@@ -1353 +1355 @@
         }
 
-        if (ray->RefCount() != 0) 
+        if (ray->RefCount() != 0)
         {
                 cerr << "Error: Number of remaining refs = " << ray->RefCount() << endl;
@@ -1364 +1366 @@
 {
         stack<RayTraversalData> tstack;
-  
+
         tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
-  
+
         RayTraversalData data;
-  
-        while (!tstack.empty()) 
+
+        while (!tstack.empty())
         {
                 data = tstack.top();
                 tstack.pop();
 
-                if (!data.mNode->IsLeaf()) 
+                if (!data.mNode->IsLeaf())
                 {
                         TraverseInternalNode(data, tstack);
-                } 
-                else 
+                }
+                else
                 {
                         // remove the ray from the leaf
@@ -1390 +1392 @@
 }
 
-void VspKdTree::TraverseInternalNode(RayTraversalData &data, 
+void VspKdTree::TraverseInternalNode(RayTraversalData &data,
                                                                          stack<RayTraversalData> &tstack)
 {
         VspKdInterior *in = dynamic_cast<VspKdInterior *>(data.mNode);
-  
-        if (in->mAxis <= VspKdNode::SPLIT_Z) 
+
+        if (in->mAxis <= VspKdNode::SPLIT_Z)
         {
             // determine the side of this ray with respect to the plane
- float t; 
+ float t;
  int side = in->ComputeRayIntersection(data.mRayData, t);
-    
-                if (side == 0) 
-                {
-                        if (data.mRayData.mRay->HasPosDir(in->mAxis)) 
-                        {
-                                tstack.push(RayTraversalData(in->GetBack(), 
+
+                if (side == 0)
+                {
+                        if (data.mRayData.mRay->HasPosDir(in->mAxis))
+                        {
+                                tstack.push(RayTraversalData(in->GetBack(),
                                                         RayInfo(data.mRayData.mRay, data.mRayData.mMinT, t)));
-                                
+
                                 tstack.push(RayTraversalData(in->GetFront(),
                                                         RayInfo(data.mRayData.mRay, t, data.mRayData.mMaxT)));
-        
-                        } 
-                        else 
+
+                        }
+                        else
                         {
                                 tstack.push(RayTraversalData(in->GetBack(),
@@ -1429 +1431 @@
                         else
                                 tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
-        } 
-        else 
+        }
+        else
         {
                 // directional split
@@ -1446 +1448 @@
         // use mail 1 for this purpose
         stack<VspKdNode *> tstack;
-        
+
         int rayCount = 0;
         int totalRayCount = 0;
@@ -1462 +1464 @@
         tstack.push(sroot);
         VssRay::NewMail();
-        
-        while (!tstack.empty()) 
+
+        while (!tstack.empty())
         {
                 ++ collapsedNodes;
-                
+
                 VspKdNode *node = tstack.top();
                 tstack.pop();
-                if (node->IsLeaf()) 
+                if (node->IsLeaf())
                 {
                         VspKdLeaf *leaf = (VspKdLeaf *) node;
-                        
+
                         for(RayInfoContainer::iterator ri = leaf->mRays.begin();
-                                        ri != leaf->mRays.end(); ++ ri) 
+                                        ri != leaf->mRays.end(); ++ ri)
                         {
                                 ++ totalRayCount;
-                                
-                                if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed()) 
+
+                                if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed())
                                 {
                                         (*ri).mRay->Mail();
@@ -1484 +1486 @@
                                 }
                         }
-                } 
-                else 
+                }
+                else
                 {
                         tstack.push(((VspKdInterior *)node)->GetFront());
@@ -1491 +1493 @@
                 }
         }
-  
+
         VssRay::NewMail();
 
         // create a new node that will hold the rays
         VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount);
-        
+
         if (newLeaf->mParent)
                 newLeaf->mParent->ReplaceChildLink(sroot, newLeaf);
@@ -1502 +1504 @@
         tstack.push(sroot);
 
-        while (!tstack.empty()) 
+        while (!tstack.empty())
         {
                 VspKdNode *node = tstack.top();
                 tstack.pop();
 
-                if (node->IsLeaf()) 
+                if (node->IsLeaf())
                 {
                         VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
                         for(RayInfoContainer::iterator ri = leaf->mRays.begin();
-                                        ri != leaf->mRays.end(); ++ ri) 
-                        {
-                                // unref this ray from the old node             
-                                if ((*ri).mRay->IsActive()) 
+                                        ri != leaf->mRays.end(); ++ ri)
+                        {
+                                // unref this ray from the old node
+                                if ((*ri).mRay->IsActive())
                                 {
                                         (*ri).mRay->Unref();
-                                        if (!(*ri).mRay->Mailed()) 
+                                        if (!(*ri).mRay->Mailed())
                                         {
                                                 (*ri).mRay->Mail();
                                                 newLeaf->AddRay(*ri);
                                         }
-                                } 
+                                }
                                 else
                                         (*ri).mRay->Unref();
                         }
-                } 
-                else 
-                {
-                        VspKdInterior *interior = 
+                }
+                else
+                {
+                        VspKdInterior *interior =
                                 dynamic_cast<VspKdInterior *>(node);
                         tstack.push(interior->GetBack());
@@ -1536 +1538 @@
                 }
         }
-  
+
         // delete the node and all its children
         DEL_PTR(sroot);
-  
+
         // for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin();
     //      ri != newleaf->mRays.end(); ++ ri)
@@ -1550 +1552 @@
         mStat.nodes -= collapsedNodes - 1;
         mStat.rayRefs -= totalRayCount - rayCount;
-  
+
 #if DEBUG_COLLAPSE
         cout << "collapsed nodes" << collapsedNodes << endl;
@@ -1571 +1573 @@
         Intersectable::NewMail();
         int pvsSize = 0;
-        
-        while (!tstack.empty()) 
+
+        while (!tstack.empty())
         {
                 VspKdNode *node = tstack.top();
                 tstack.pop();
-    
-          if (node->IsLeaf()) 
+
+          if (node->IsLeaf())
                 {
                         VspKdLeaf *leaf = (VspKdLeaf *)node;
@@ -1583 +1585 @@
                                  ri != leaf->mRays.end(); ++ ri)
                         {
-                                if ((*ri).mRay->IsActive()) 
+                                if ((*ri).mRay->IsActive())
                                 {
                                         Intersectable *object;
 #if BIDIRECTIONAL_RAY
                                         object = (*ri).mRay->mOriginObject;
-                                        
-                                        if (object && !object->Mailed()) 
+
+                                        if (object && !object->Mailed())
                                         {
                                                 ++ pvsSize;
@@ -1596 +1598 @@
 #endif
                                         object = (*ri).mRay->mTerminationObject;
-                                        if (object && !object->Mailed()) 
+                                        if (object && !object->Mailed())
                                         {
                                                 ++ pvsSize;
@@ -1602 +1604 @@
                                         }
                                 }
-                        } 
-                }
-                else 
+                        }
+                }
+                else
                 {
                         VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
-        
-                        if (in->mAxis < 3) 
+
+                        if (in->mAxis < 3)
                         {
                                 if (box.Max(in->mAxis) >= in->mPosition)
                                         tstack.push(in->GetFront());
-                                
+
                                 if (box.Min(in->mAxis) <= in->mPosition)
                                         tstack.push(in->GetBack());
-                        } 
-                        else 
+                        }
+                        else
                         {
                                 // both nodes for directional splits
@@ -1634 +1636 @@
         stack<VspKdNode *> tstack;
         tstack.push(mRoot);
-        
+
         minRayContribution = 1.0f;
         maxRayContribution = 0.0f;
@@ -1641 +1643 @@
         int leaves = 0;
 
-        while (!tstack.empty()) 
+        while (!tstack.empty())
         {
                 VspKdNode *node = tstack.top();
                 tstack.pop();
-                if (node->IsLeaf()) 
+                if (node->IsLeaf())
                 {
                         leaves++;
@@ -1656 +1658 @@
                                 minRayContribution = c;
                         sumRayContribution += c;
-                        
-                } 
+
+                }
                 else {
                         VspKdInterior *in = (VspKdInterior *)node;
@@ -1665 +1667 @@
                 }
         }
-        
+
         Debug << "sum=" << sumRayContribution << endl;
         Debug << "leaves=" << leaves << endl;
@@ -1677 +1679 @@
         stack<VspKdNode *> tstack;
         tstack.push(mRoot);
-        
-        while (!tstack.empty()) 
+
+        while (!tstack.empty())
         {
                 VspKdNode *node = tstack.top();
                 tstack.pop();
-                
-                if (node->IsLeaf()) 
+
+                if (node->IsLeaf())
                 {
                         VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
@@ -1691 +1693 @@
                         //                      cout<<num<<" ";
 
-                        for (int i=0; i < num; i++) 
+                        for (int i=0; i < num; i++)
                         {
                                 Vector3 origin = GetBBox(leaf).GetRandomPoint();
@@ -1699 +1701 @@
                                 rays.push_back(SimpleRay(origin, direction));*/
                         }
-                        
-                } 
-                else 
-                {
-                        VspKdInterior *in = 
+
+                }
+                else
+                {
+                        VspKdInterior *in =
                                 dynamic_cast<VspKdInterior *>(node);
                         // both nodes for directional splits
@@ -1722 +1724 @@
         int sumPvs = 0;
         int leaves = 0;
-        
-        while (!tstack.empty()) 
+
+        while (!tstack.empty())
         {
                 VspKdNode *node = tstack.top();
                 tstack.pop();
-                
-                if (node->IsLeaf()) 
+
+                if (node->IsLeaf())
                 {
                         VspKdLeaf *leaf = (VspKdLeaf *)node;
@@ -1735 +1737 @@
                         sumPvs += leaf->GetPvsSize();
                         leaves++;
-                } 
-                else 
+                }
+                else
                 {
                         VspKdInterior *in = (VspKdInterior *)node;
@@ -1763 +1765 @@
         if (node->mParent->mAxis >= 3)
                 return node->mParent->mBox;
-    
+
         AxisAlignedBox3 box(node->mParent->mBox);
         if (node->mParent->GetFront() == node)
@@ -1773 +1775 @@
 }
 
-int     VspKdTree::GetRootPvsSize() const 
+int     VspKdTree::GetRootPvsSize() const
 {
         return GetPvsSize(mRoot, mBox);
 }
 
-const VspKdStatistics &VspKdTree::GetStatistics() const 
+const VspKdStatistics &VspKdTree::GetStatistics() const
 {
         return mStat;
@@ -1788 +1790 @@
         UpdateRays(remove, add);
 }
- 
+
 // return memory usage in MB
-float VspKdTree::GetMemUsage() const 
-{
-        return 
-                (sizeof(VspKdTree) + 
+float VspKdTree::GetMemUsage() const
+{
+        return
+                (sizeof(VspKdTree) +
                  mStat.Leaves() * sizeof(VspKdLeaf) +
                  mStat.Interior() * sizeof(VspKdInterior) +
                  mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
 }
-        
-float VspKdTree::GetRayMemUsage() const 
+
+float VspKdTree::GetRayMemUsage() const
 {
         return mStat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f);
 }
 
-int VspKdTree::ComputePvsSize(VspKdNode *node, 
+int VspKdTree::ComputePvsSize(VspKdNode *node,
                                                           const RayInfoContainer &globalRays) const
 {
@@ -1816 +1818 @@
         for (it = globalRays.begin(); it != globalRays.end(); ++ it)
                 pvsSize += box.GetMinMaxT(*(*it).mRay, NULL, NULL);
-        
+
         return pvsSize;
 }
@@ -1825 +1827 @@
         nodeStack.push(mRoot);
 
-        while (!nodeStack.empty()) 
+        while (!nodeStack.empty())
         {
                 VspKdNode *node = nodeStack.top();
-                
+
                 nodeStack.pop();
-                
-                if (node->IsLeaf()) 
+
+                if (node->IsLeaf())
                 {
                         VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
                         leaves.push_back(leaf);
-                } 
-                else 
+                }
+                else
                 {
                         VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
@@ -1851 +1853 @@
 {
         stack<VspKdNode *> nodeStack;
-  
+
         nodeStack.push(mRoot);
 
         AxisAlignedBox3 box = GetBBox(n);
 
-        while (!nodeStack.empty()) 
+        while (!nodeStack.empty())
         {
                 VspKdNode *node = nodeStack.top();
                 nodeStack.pop();
 
-                if (node->IsLeaf()) 
+                if (node->IsLeaf())
                 {
                         VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
-                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed())) 
+                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed()))
                                 neighbors.push_back(leaf);
-                } 
-                else 
+                }
+                else
                 {
                         VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
@@ -1878 +1880 @@
                                 if (interior->mPosition < box.Min(interior->mAxis))
                                         nodeStack.push(interior->mFront);
-                                else 
+                                else
                                 {
                                         // random decision
@@ -1902 +1904 @@
 {
         int hits = 0;
-  
+
         stack<RayTraversalData> tStack;
-  
+
         float maxt = 1e6;
         float mint = 0;
@@ -1915 +1917 @@
         if (mint < 0)
                 mint = 0;
-  
+
         maxt += Limits::Threshold;
-  
+
         Vector3 entp = ray.Extrap(mint);
         Vector3 extp = ray.Extrap(maxt);
-  
+
         VspKdNode *node = mRoot;
         VspKdNode *farChild;
@@ -1926 +1928 @@
         float position;
         int axis;
-  
-        while (1) 
-        {
-                if (!node->IsLeaf()) 
+
+        while (1)
+        {
+                if (!node->IsLeaf())
                 {
                         VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
@@ -1935 +1937 @@
                         axis = in->mAxis;
 
-                        if (entp[axis] <= position) 
-                        {
-                                if (extp[axis] <= position) 
+                        if (entp[axis] <= position)
+                        {
+                                if (extp[axis] <= position)
                                 {
                                         node = in->mBack;
                                         // cases N1,N2,N3,P5,Z2,Z3
                                         continue;
-                                } else 
+                                } else
                                 {
                                         // case N4
@@ -1949 +1951 @@
                                 }
                         }
-                        else 
-                        {
-                                if (position <= extp[axis]) 
+                        else
+                        {
+                                if (position <= extp[axis])
                                 {
                                         node = in->mFront;
                                         // cases P1,P2,P3,N5,Z1
                                         continue;
-                                } 
-                                else 
+                                }
+                                else
                                 {
                                         node = in->mFront;
@@ -1971 +1973 @@
                         extp = ray.GetLoc() + ray.GetDir()*tdist;
                         maxt = tdist;
-                } 
-                else 
+                }
+                else
                 {
                         // compute intersection with all objects in this leaf
@@ -1978 +1980 @@
                         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++) 
+                        for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); mi++)
                         {
                                 Intersectable *object = *mi;
-                                if (!object->Mailed() ) 
+                                if (!object->Mailed() )
                                 {
                                         object->Mail();
@@ -1991 +1993 @@
                                 }
                         }
-                        
+
                         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;
@@ -2013 +2015 @@
                 }
         }
-        
+
         return hits;
 }
@@ -2034 +2036 @@
                 if (ray->mTerminationObject)
                         vc->GetPvs().AddSample(ray->mTerminationObject);
-                
+
                 if (ray->mOriginObject)
                         vc->GetPvs().AddSample(ray->mOriginObject);
@@ -2050 +2052 @@
         ViewCell::NewMail();
 
-        // exclude root cell
-        //mRootCell->Mail();
-
-        while (!nodeStack.empty()) 
+        while (!nodeStack.empty())
         {
                 VspKdNode *node = nodeStack.top();
                 nodeStack.pop();
 
-                if (node->IsLeaf()) 
+                if (node->IsLeaf())
                 {
                         ++ vcStat.leaves;
@@ -2064 +2063 @@
                         VspKdViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
 
-                        if (!viewCell->Mailed()) 
+                        if (!viewCell->Mailed())
                         {
                                 viewCell->Mail();
-                                
+
                                 ++ vcStat.viewCells;
                                 const int pvsSize = viewCell->GetPvs().GetSize();
@@ -2083 +2082 @@
 
                                 if ((int)viewCell->mVspKdLeaves.size() > vcStat.maxLeaves)
-                                        vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size();          
-                        }
-                }
-                else 
+                                        vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size();
+                        }
+                }
+                else
                 {
                         VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
@@ -2095 +2094 @@
         }
 }
+
 
 
@@ -2130 +2130 @@
         }
 
+        vc->Mail();
+
         // clean up old view cells
         DEL_PTR(fVc);
@@ -2143 +2145 @@
         vector<VspKdLeaf *> leaves;
         priority_queue<MergeCandidate> mergeQueue;
-        
+
         // collect the leaves, e.g., the "voxels" that will build the view cells
         CollectLeaves(leaves);
@@ -2161 +2163 @@
         {
                 VspKdLeaf *leaf = *it;
-                
+
                 // no leaf is part of two merge candidates
                 if (!leaf->Mailed())
@@ -2170 +2172 @@
                         FindNeighbors(leaf, neighbors, true);
 
-                        vector<VspKdLeaf *>::const_iterator nit, 
+                        vector<VspKdLeaf *>::const_iterator nit,
                                 nit_end = neighbors.end();
 
@@ -2180 +2182 @@
         int merged = 0;
 
-        float savedMaxCostRatio = 0;
-
-        Debug << "merge cost " << mergeQueue.top().GetMergeCost() << " of " << mMaxCostRatio << endl;
+        //Debug << mMinViewCells << " " << mMaxCostRatio << endl;
 
         // use priority queue to merge leaves
-        while (!mergeQueue.empty() && 
-                   ((mMaxViewCells < vcSize) ||
-                    (mergeQueue.top().GetMergeCost() < mMaxCostRatio)))
-        {
-                ViewCell::NewMail();
-
-                Debug << "=====================" << endl;
+        while (!mergeQueue.empty() &&
+                   (vcSize > mMinViewCells))// &&
+                   //(mergeQueue.top().GetMergeCost() < mMaxCostRatio))
+        {
+                //Debug << mergeQueue.top().GetMergeCost() << " " << mMaxCostRatio << endl;
                 MergeCandidate mc = mergeQueue.top();
                 mergeQueue.pop();
-                
+
+                // both view cells equal!
                 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();
-                        
-                        Debug << "merging cells with cost " << mc.GetMergeCost() << " of " << mMaxCostRatio << endl;
-                        savedMaxCostRatio = mc.GetMergeCost();
-
+                        ViewCell::NewMail();
                         MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-                        
+
                         ++ merged;
                         -- vcSize;
@@ -2219 +2207 @@
                 // merge candidate not valid, because one of the leaves was already
                 // merged with another one
-                else 
-                {
-                        Debug << "not valid " << mc.GetMergeCost() << endl;
-                        
+                else
+                {
                         // 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;
+                        //Debug << "validate " << mc.GetMergeCost() << endl;
+                }
+        }
+
+        // collapse tree according to view cell partition
+        CollapseTree(mRoot);
+
+        // revalidate leaves
+        ValidateViewCellLeaves();
+
 
         return merged;
+}
+
+
+void VspKdTree::ValidateViewCellLeaves()
+{
+        // list not valid anymore => clear
+        stack<VspKdNode *> nodeStack;
+        nodeStack.push(mRoot);
+
+        ViewCell::NewMail();
+
+        while (!nodeStack.empty())
+        {
+                VspKdNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                if (node->IsLeaf())
+                {
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
+
+                        VspKdViewCell *viewCell = leaf->GetViewCell();
+
+                        if (!viewCell->Mailed())
+                        {
+                                Debug << "jhere2" << endl;
+                                viewCell->mVspKdLeaves.clear();
+                                viewCell->Mail();
+                        }
+
+                        viewCell->mVspKdLeaves.push_back(leaf);
+                }
+                else
+                {
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
+
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+}
+
+VspKdNode *VspKdTree::CollapseTree(VspKdNode *node)
+{
+    if (node->IsLeaf())
+                return node;
+
+        Debug << "here554444" << endl;
+        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
+
+        VspKdNode *front = CollapseTree(interior->GetFront());
+        VspKdNode *back = CollapseTree(interior->GetBack());
+
+        if (front->IsLeaf() && back->IsLeaf())
+        {
+                VspKdLeaf *frontLeaf = dynamic_cast<VspKdLeaf *>(front);
+                VspKdLeaf *backLeaf = dynamic_cast<VspKdLeaf *>(back);
+
+                //-- collapse tree
+                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
+                {
+                        VspKdViewCell *vc = frontLeaf->GetViewCell();
+
+                        VspKdLeaf *leaf = new VspKdLeaf(interior->GetParent(), 0);
+                        leaf->SetViewCell(vc);
+
+                        // replace a link from node's parent
+                        if (leaf->mParent)
+                                leaf->mParent->ReplaceChildLink(node, leaf);
+
+                        delete interior;
+
+                        return leaf;
+                }
+        }
+
+        return node;
 }
 
@@ -2258 +2321 @@
 void MergeCandidate::EvalMergeCost()
 {
-        // compute pvs differences
+        //-- compute pvs difference
         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 vcPvs = diff1 + vc1->GetPvs().GetSize();
 
-        //-- compute ratio of old cost 
+        //-- 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 = 
-                (float)vc1->GetPvs().GetSize() * vc1->GetSize() + 
+        const float oldCost =
+                (float)vc1->GetPvs().GetSize() * vc1->GetSize() +
                 (float)vc2->GetPvs().GetSize() * vc2->GetSize();
 
-        const float newCost = 
+        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;
+        mMergeCost = newCost - oldCost;
+
+//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
+//              mMergeCost += 1.0;
 }
 
@@ -2310 +2365 @@
 
 bool MergeCandidate::Valid() const
-{       
-        //Debug << mLeaf1->GetViewCell()->mMailbox << " " << mLeaf1Id << endl;
-        //Debug << mLeaf2->GetViewCell()->mMailbox << " " << mLeaf2Id << endl;
-
-        return 
-                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) && 
+{
+        return
+                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
                 (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
 }
@@ -2328 +2380 @@
         mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
         mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
-        
+
         EvalMergeCost();
 }

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -299 +299 @@
 {
 public:
+
         friend class VspKdTree;
 
@@ -670 +671 @@
         bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2);
 
-        
+        /** Collapses the tree with respect to the view cell partition.
+                @returns node of type leaf if the node could be collapsed, this node otherwise
+        */
+        VspKdNode *CollapseTree(VspKdNode *node);
+        
+        /** Helper function revalidating the view cell leaf list after merge.
+        */
+        void ValidateViewCellLeaves();
+
 protected:
         
@@ -749 +758 @@
         int mMaxViewCells;
 
+        /// minimal number of view cells
+        int mMinViewCells;
+
         /////////////////////////////
         VspKdStatistics mStat;  

trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

@@ -462 +462 @@
   cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl;
   
-  ExportVssTree("vss-tree-100.x3d", vssTree, Vector3(1,0,0));
-  ExportVssTree("vss-tree-001.x3d", vssTree, Vector3(0,0,1));
-  ExportVssTree("vss-tree-101.x3d", vssTree, Vector3(1,0,1));
-  ExportVssTree("vss-tree-101m.x3d", vssTree, Vector3(-1,0,-1));
-
-  ExportVssTreeLeaves(vssTree, 10);
+  if (0)
+  {
+          ExportVssTree("vss-tree-100.x3d", vssTree, Vector3(1,0,0));
+          ExportVssTree("vss-tree-001.x3d", vssTree, Vector3(0,0,1));
+          ExportVssTree("vss-tree-101.x3d", vssTree, Vector3(1,0,1));
+          ExportVssTree("vss-tree-101m.x3d", vssTree, Vector3(-1,0,-1));
+          ExportVssTreeLeaves(vssTree, 10);
+  }
 
   // viewcells->UpdatePVS(newVssRays);
@@ -543 +545 @@
 
         /// compute view cell contribution of rays
-        mViewCellsManager->ComputeSampleContributions(passRays,
+/*      mViewCellsManager->ComputeSampleContributions(passRays,
                                                                                                   sampleContributions, 
                                                                                                   contributingSamples);
@@ -560 +562 @@
                 CLEAR_CONTAINER(passRays);
         }
-
+*/
         samples+=num;
         float pvs = vssTree->GetAvgPvsSize();
@@ -574 +576 @@
   }
 
+  cout << "here" << endl;
   //-- post process view cells
   mViewCellsManager->PostProcess(objects, storedRays);

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -357 +357 @@
     stream<<"<IndexedLineSet coordIndex=\""<<endl;
   else
-    stream<<"<IndexedFaceSet ccw=\"TRUE\" coordIndex=\""<<endl;
+    //stream<<"<IndexedFaceSet ccw=\"TRUE\" coordIndex=\""<<endl;
+        stream << "<IndexedFaceSet coordIndex=\"" << endl;
 
   FaceContainer::const_iterator fi = mesh->mFaces.begin();
@@ -431 +432 @@
         //-- create and write indices
         if (mWireframe)
-                stream << "<IndexedLineSet ccw=\"TRUE\" coordIndex=\"" << endl;
+                stream<<"<IndexedLineSet coordIndex=\""<<endl;
         else
-                stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl;
-
+                //stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl;
+                stream << "<IndexedFaceSet coordIndex=\"" << endl;
         int index = 0;
         
@@ -497 +498 @@
         //-- create and write indices
         if (mWireframe)
-                stream << "<IndexedLineSet ccw=\"TRUE\" coordIndex=\"" << endl;
+                stream<<"<IndexedLineSet coordIndex=\""<<endl;
         else
-                stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl;
+                //stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl;
+                stream << "<IndexedFaceSet coordIndex=\"" << endl;
 
         int index = 0;