Changeset 587 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

Timestamp:

02/04/06 12:46:14 (18 years ago)

Author:

mattausch

Message:

updated vspkdtree for regular sudbivision

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp (modified) (45 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -10 +10 @@
 #include "Triangle3.h"
 #include "Tetrahedron3.h"
-
-#include <stack>
-
+#include "ViewCellsManager.h"
 #include "Exporter.h"
 #include "Plane3.h"
+#include <stack>
 
 //-- static members
@@ -214 +213 @@
 BspTree::BspTree():  
 mRoot(NULL), 
-mUseAreaForPvs(true),
+mUseAreaForPvs(false),
 mGenerateViewCells(true)
 {
@@ -227 +226 @@
         environment->GetIntValue("BspTree.Termination.minPolygons", mTermMinPolys);
         environment->GetIntValue("BspTree.Termination.minRays", mTermMinRays);
-        environment->GetFloatValue("BspTree.Termination.minArea", mTermMinArea);        
+        environment->GetFloatValue("BspTree.Termination.minProbability", mTermMinProbability);  
         environment->GetFloatValue("BspTree.Termination.maxRayContribution", mTermMaxRayContribution);
         environment->GetFloatValue("BspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
@@ -258 +257 @@
         environment->GetFloatValue("BspTree.AxisAligned.splitBorder", mSplitBorder);
         environment->GetIntValue("BspTree.maxTests", mMaxTests);
+        environment->GetIntValue("BspTree.Termination.maxViewCells", mMaxViewCells);
 
         environment->GetFloatValue("BspTree.Construction.epsilon", mEpsilon);
@@ -263 +263 @@
     Debug << "BSP max depth: " << mTermMaxDepth << endl;
         Debug << "BSP min PVS: " << mTermMinPvs << endl;
-        Debug << "BSP min area: " << mTermMinArea << endl;
+        Debug << "BSP min probability: " << mTermMinProbability << endl;
         Debug << "BSP max polys: " << mTermMinPolys << endl;
         Debug << "BSP max rays: " << mTermMinRays << endl;
@@ -413 +413 @@
                 << maxCostNodes * 100 / (double)Leaves() << endl;
 
-        app << "#N_PMINAREALEAVES  ( Percentage of leaves with mininum probability )\n"
+        app << "#N_PMINPROBABILITYAREALEAVES  ( Percentage of leaves with mininum probability )\n"
                 << minProbabilityNodes * 100 / (double)Leaves() << endl;
 
@@ -480 +480 @@
                                                                  new BoundedRayContainer(), 
                                                                  0, 
-                                                                 mBox.SurfaceArea(), 
+                                                                 mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
                                                                  new BspNodeGeometry()));
 
@@ -519 +519 @@
                                                                                    tData.mRays,
                                                                                    tData.mPvs,
-                                                                                   mBox.SurfaceArea(),
+                                                                                   mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
                                                                                    new BspNodeGeometry());
 
@@ -528 +528 @@
                                                                                   tData.mRays,
                                                                                   tData.mPvs,
-                                                                                  mBox.SurfaceArea(),
+                                                                                   mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
                                                                                   new BspNodeGeometry());
 
@@ -583 +583 @@
 }
 
+
 int BspTree::AddToPolygonSoup(const ViewCellContainer &viewCells, 
                                                           PolygonContainer &polys, 
@@ -604 +605 @@
 }
 
-int BspTree::AddToPolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
-{
-        int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
+
+int BspTree::AddToPolygonSoup(const ObjectContainer &objects,
+                                                          PolygonContainer &polys, 
+                                                          int maxObjects,
+                                                          bool addToBbox)
+{
+        int limit = (maxObjects > 0) ? 
+                Min((int)objects.size(), maxObjects) : (int)objects.size();
   
         for (int i = 0; i < limit; ++i)
@@ -629 +635 @@
         if (mesh) // copy the mesh data to polygons
                 {
-                        mBox.Include(object->GetBox()); // add to BSP tree aabb
+                        if (addToBbox)
+                        {
+                                mBox.Include(object->GetBox()); // add to BSP tree aabb
+                        }
+                
                         AddMeshToPolygons(mesh, polys, mRootCell);
                 }
@@ -636 +646 @@
         return (int)polys.size();
 }
+
 
 void BspTree::Construct(const ViewCellContainer &viewCells)
@@ -668 +679 @@
 }
 
-void BspTree::Construct(const RayContainer &sampleRays)
+
+void BspTree::Construct(const RayContainer &sampleRays,
+                                                AxisAlignedBox3 *forcedBoundingBox)
 {
     mStat.nodes = 1;
         mBox.Initialize();      // initialise BSP tree bounding box
         
+        if (forcedBoundingBox)
+                mBox = *forcedBoundingBox;
+
         PolygonContainer *polys = new PolygonContainer();
         BoundedRayContainer *rays = new BoundedRayContainer();
@@ -724 +740 @@
 
         // compute bounding box
-        Polygon3::IncludeInBox(*polys, mBox);
+        if (!forcedBoundingBox)
+                Polygon3::IncludeInBox(*polys, mBox);
 
         //-- store rays
@@ -746 +763 @@
 }
 
-void BspTree::Construct(const ObjectContainer &objects, const RayContainer &sampleRays)
+
+void BspTree::Construct(const ObjectContainer &objects, 
+                                                const RayContainer &sampleRays,
+                                                AxisAlignedBox3 *forcedBoundingBox)
 {
     mStat.nodes = 1;
         mBox.Initialize();      // initialise BSP tree bounding box
         
+        if (forcedBoundingBox)
+                mBox = *forcedBoundingBox;
+
         BoundedRayContainer *rays = new BoundedRayContainer();
         PolygonContainer *polys = new PolygonContainer();
@@ -757 +780 @@
 
         // copy mesh instance polygons into one big polygon soup
-        mStat.polys = AddToPolygonSoup(objects, *polys);
+        mStat.polys = AddToPolygonSoup(objects, *polys, 0, !forcedBoundingBox);
+
 
         RayContainer::const_iterator rit, rit_end = sampleRays.end();
@@ -776 +800 @@
 }
 
+
 void BspTree::Construct(PolygonContainer *polys, BoundedRayContainer *rays)
 {
@@ -786 +811 @@
         ConstructGeometry(mRoot, *geom);
 
-        BspTraversalData tData(mRoot, polys, 0, mRootCell, rays, 
-                                                   ComputePvsSize(*rays), geom->GetArea(), geom);
+        BspTraversalData tData(mRoot, 
+                                                   polys, 
+                                                   0, 
+                                                   mRootCell, 
+                                                   rays, 
+                                                   ComputePvsSize(*rays), 
+                                                   mUseAreaForPvs ? geom->GetArea() : geom->GetVolume(), 
+                                                   geom);
 
         tStack.push(tData);
@@ -804 +835 @@
 
                 if (r == mRoot)
-                        Debug << "BSP tree construction time spent at root: " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
+            Debug << "BSP tree construction time spent at root: " 
+                                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
         }
 
@@ -818 +850 @@
                  ((int)data.mRays->size() <= mTermMinRays) ||
                  (data.mPvs <= mTermMinPvs) ||
-                 (data.mArea <= mTermMinArea) ||
+                 (data.mProbability <= mTermMinProbability) ||
                  (data.mDepth >= mTermMaxDepth) ||
-                 (data.GetAvgRayContribution() < mTermMaxRayContribution));
+                 (mStat.Leaves() >= mMaxViewCells) ||
+                 (data.GetAvgRayContribution() > mTermMaxRayContribution));
 }
 
@@ -842 +875 @@
                 viewCell->mLeaf = leaf;
 
+                if (mUseAreaForPvs)
+                        viewCell->SetArea(tData.mProbability);
+                else
+                        viewCell->SetVolume(tData.mProbability);
+                
                 //-- add pvs
                 if (viewCell != mRootCell)
@@ -880 +918 @@
                 SubdivideNode(tData, tFrontData, tBackData, coincident);
 
-#ifdef _DEBUG   
-//      if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
-//      {       for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
-//                      Debug << (*it) << " " << (*it)->GetArea() << " " << (*it)->mParent << endl ;
-//              Debug << endl;}
-#endif
 
         // extract view cells from coincident polygons according to plane normal
@@ -951 +983 @@
         BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
 
-        Debug << "*********************" << endl;
-        long startTime = GetTime();
+        long startTime;
+        if (0)
+        {
+                Debug << "*********************" << endl;
+                startTime = GetTime();
+        }
         
         // select subdivision plane
         BspInterior *interior = 
                 new BspInterior(SelectPlane(leaf, tData)); 
-        Debug << "time used for split plane selection: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+        
+        if (0)
+        {
+                Debug << "time used for split plane selection: " 
+                          << TimeDiff(startTime, GetTime()) * 1e-3 << "s" << endl;
+        }
 #ifdef _DEBUG
         Debug << interior << endl;
@@ -963 +1004 @@
         
 
-        Debug << "number of rays: " << (int)tData.mRays->size() << endl;
-        Debug << "number of polys: " << (int)tData.mPolygons->size() << endl;
-
-        startTime = GetTime();
+        if (0)
+        {
+                Debug << "number of rays: " << (int)tData.mRays->size() << endl;
+                Debug << "number of polys: " << (int)tData.mPolygons->size() << endl;
+
+                startTime = GetTime();
+        }       
         
         // subdivide rays into front and back rays
         SplitRays(interior->mPlane, *tData.mRays, *frontData.mRays, *backData.mRays);
         
-        Debug << "time used for rays splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
-
-        startTime = GetTime();
+        if (0)
+        {
+                Debug << "time used for rays splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+                startTime = GetTime();
+        }
+
         // subdivide polygons with plane
         mStat.polySplits += SplitPolygons(interior->GetPlane(),
@@ -981 +1028 @@
                                                                           coincident);
 
-        Debug << "time used for polygon splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+        if (0)
+        {
+                Debug << "time used for polygon splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+        }
 
     // compute pvs
@@ -997 +1047 @@
         
                 
-                frontData.mArea = frontData.mGeometry->GetArea();
-                backData.mArea = backData.mGeometry->GetArea();
+                frontData.mProbability = frontData.mGeometry->GetVolume();
+                backData.mProbability = backData.mGeometry->GetVolume();
         }
 
@@ -1186 +1236 @@
 
                 const int axis = box.Size().DrivingAxis();
-                const Vector3 position = (box.Min()[axis] + box.Max()[axis])*0.5f;
+                const Vector3 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
 
                 Vector3 norm(0,0,0); norm[axis] = 1.0f;
@@ -1196 +1246 @@
                 ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
                 ((mTermMinObjectsForAxisAligned < 0) || 
-                  (Polygon3::ParentObjectsSize(*data.mPolygons) > mTermMinObjectsForAxisAligned)))
+                 (Polygon3::ParentObjectsSize(*data.mPolygons) > mTermMinObjectsForAxisAligned)))
         {
                 Plane3 plane;
@@ -1329 +1379 @@
                 // assure that no index is taken twice
                 const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
-                //Debug << "current Idx: " << maxIdx << " cand idx " << candidateIdx << endl;
-                
+                                
                 Polygon3 *poly = (*data.mPolygons)[candidateIdx];
 
                 // swap candidate to the end to avoid testing same plane
                 std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
-        
                 //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
 
@@ -1517 +1565 @@
                                                           const BoundedRayContainer &rays,
                                                           const int pvs,
-                                                          const float area,
+                                                          const float probability,
                                                           const BspNodeGeometry &cell) const
 {
@@ -1540 +1588 @@
                 GenerateUniqueIdsForPvs();
 
-                if (mUseAreaForPvs) // use front and back cell areas to approximate volume
-                {
-                        // construct child geometry with regard to the candidate split plane
-                        BspNodeGeometry frontCell;
-                        BspNodeGeometry backCell;
-
-                        cell.SplitGeometry(frontCell, 
-                                                           backCell, 
-                                                           candidatePlane,
-                                                           mBox,
-                                                           mEpsilon);
-                
+                // construct child geometry with regard to the candidate split plane
+                BspNodeGeometry frontCell;
+                BspNodeGeometry backCell;
+
+                cell.SplitGeometry(frontCell, 
+                                                   backCell, 
+                                                   candidatePlane,
+                                                   mBox,
+                                                   mEpsilon);
+
+                if (mUseAreaForPvs)
+                {
                         pFront = frontCell.GetArea();
                         pBack = backCell.GetArea();
-
-                        pOverall = area;
-                }
+                }
+                else
+                {
+                        pFront = frontCell.GetVolume();
+                        pBack = backCell.GetVolume();
+                }
+                
+
+                pOverall = probability;
         }
                         
@@ -1611 +1665 @@
                         // add the source object
                         AddObjToPvs(ray->sourceObject.mObject, cf, frontPvs, backPvs);
-                        
-                        if (mUseAreaForPvs)
-                        {
-                                float len = 1;
-                        
-                                if (pvsUseLen)
-                                        len = SqrDistance(entP, extP);
-        
-                                // use length of rays to approximate volume
-                                if (Ray::BACK && Ray::COINCIDENT)
-                                        pBack += len;
-                                if (Ray::FRONT && Ray::COINCIDENT)
-                                        pFront += len;
-                                if (Ray::FRONT_BACK || Ray::BACK_FRONT)
-                                {
-                                        if (pvsUseLen)
-                                        {
-                                                const Vector3 extp = ray->Extrap(maxT);
-                                                const float t = candidatePlane.FindT(ray->GetLoc(), extp);
-                                
-                                                const float newT = t * maxT;
-                                                const float newLen = SqrDistance(ray->Extrap(newT), extp);
-
-                                                if (Ray::FRONT_BACK)
-                                                {
-                                                        pFront += len - newLen;
-                                                        pBack += newLen;
-                                                }
-                                                else
-                                                {
-                                                        pBack += len - newLen;
-                                                        pFront += newLen;
-                                                }
-                                        }
-                                        else
-                                        {
-                                                ++ pFront;
-                                                ++ pBack;
-                                        }
-                                }
-                        }
                 }
         }
@@ -1760 +1773 @@
         {
                 val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs, 
-                                                          data.mArea, *data.mGeometry);
+                                                          data.mProbability, *data.mGeometry);
         }
 
@@ -1834 +1847 @@
                 ++ mStat.maxRayContribNodes;
         
-        if (data.mGeometry->GetArea() <= mTermMinArea) 
+        if (data.mProbability <= mTermMinProbability) 
                 ++ mStat.minProbabilityNodes;
 
@@ -1841 +1854 @@
                   << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
                   << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
-                  << "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
+                  << "Probability: " << data.mProbability << " (min: " << mTermMinProbability << "), "
                   << "#polygons: " << (int)data.mPolygons->size() << " (max: " << mTermMinPolys << "), "
                   << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), " 
@@ -2207 +2220 @@
 }
 
-void BspTree::ConstructGeometry(BspViewCell *vc, BspNodeGeometry &geom) const
-{
-        // TODO
-/*      vector<BspLeaf *> leaves = vc->mLeaves;
-
-        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+
+void BspTree::ConstructGeometry(ViewCell *vc, 
+                                                                BspNodeGeometry &vcGeom) const
+{
+        ViewCellContainer leaves;
+        mViewCellsManager->GetViewCellsTree()->CollectLeaves(vc, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
 
         for (it = leaves.begin(); it != it_end; ++ it)
-                ConstructGeometry(*it, geom);*/
+        {
+                BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                ConstructGeometry(l, vcGeom);
+        }
+}
+
+
+void BspTree::SetViewCellsManager(ViewCellsManager *vcm)
+{
+        mViewCellsManager = vcm;
 }
 
@@ -2301 +2326 @@
 
 
-int BspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 
+typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
+
+
+int BspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
                                                    const bool onlyUnmailed) const
 {
-        BspNodeGeometry geom;
-        ConstructGeometry(n, geom);
-
-        stack<BspNode *> nodeStack;
-        nodeStack.push(mRoot);
-                
-        // planes needed to verify that we found neighbor leaf.
+        stack<bspNodePair> nodeStack;
+        
+        BspNodeGeometry nodeGeom;
+        ConstructGeometry(n, nodeGeom);
+        
+        // split planes from the root to this node
+        // needed to verify that we found neighbor leaf
+        // TODO: really needed?
         vector<Plane3> halfSpaces;
         ExtractHalfSpaces(n, halfSpaces);
 
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
+
+        BspNodeGeometry *rgeom = new BspNodeGeometry();
+        ConstructGeometry(mRoot, *rgeom);
+
+        nodeStack.push(bspNodePair(mRoot, rgeom));
+
+        while (!nodeStack.empty())
+        {
+                BspNode *node = nodeStack.top().first;
+                BspNodeGeometry *geom = nodeStack.top().second;
+        
                 nodeStack.pop();
 
                 if (node->IsLeaf())
                 {
-            if (node != n && (!onlyUnmailed || !node->Mailed()))
+                        // test if this leaf is in valid view space
+                        if (node->TreeValid() &&
+                                (node != n) && 
+                                (!onlyUnmailed || !node->Mailed()))
                         {
-                                // test all planes of current node if neighbour 
-                                // candidate really is neighbour
-                                BspNodeGeometry candidateGeom;
-                                ConstructGeometry(node, candidateGeom);
-                                
                                 bool isAdjacent = true;
-                                for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
+
+                                if (1)
                                 {
-                                        const int cf = 
-                                                Polygon3::ClassifyPlane(candidateGeom.mPolys, 
-                                                                                                halfSpaces[i],
-                                                                                                mEpsilon);
-
-                                        if (cf == Polygon3::BACK_SIDE)
-                                                isAdjacent = false;
+                                        // test all planes of current node if still adjacent
+                                        for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
+                                        {
+                                                const int cf =
+                                                        Polygon3::ClassifyPlane(geom->mPolys,
+                                                                                                        halfSpaces[i],
+                                                                                                        mEpsilon);
+
+                                                if (cf == Polygon3::BACK_SIDE)
+                                                {
+                                                        isAdjacent = false;
+                                                }
+                                        }
                                 }
-
+                                else
+                                {
+                                        // TODO: why is this wrong??
+                                        // test all planes of current node if still adjacent
+                                        for (int i = 0; (i < (int)nodeGeom.mPolys.size()) && isAdjacent; ++ i)
+                                        {
+                                                Polygon3 *poly = nodeGeom.mPolys[i];
+
+                                                const int cf =
+                                                        Polygon3::ClassifyPlane(geom->mPolys,
+                                                                                                        poly->GetSupportingPlane(),
+                                                                                                        mEpsilon);
+
+                                                if (cf == Polygon3::BACK_SIDE)
+                                                {
+                                                        isAdjacent = false;
+                                                }
+                                        }
+                                }
+                                // neighbor was found
                                 if (isAdjacent)
+                                {       
                                         neighbors.push_back(dynamic_cast<BspLeaf *>(node));
+                                }
                         }
                 }
-                else 
+                else
                 {
                         BspInterior *interior = dynamic_cast<BspInterior *>(node);
-        
-                        const int cf = Polygon3::ClassifyPlane(geom.mPolys, 
-                                                                                                   interior->mPlane,
+
+                        const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
+                                                                                                   interior->GetPlane(),
                                                                                                    mEpsilon);
-
+                        
+                        BspNode *front = interior->GetFront();
+                        BspNode *back = interior->GetBack();
+            
+                        BspNodeGeometry *fGeom = new BspNodeGeometry();
+                        BspNodeGeometry *bGeom = new BspNodeGeometry();
+
+                        geom->SplitGeometry(*fGeom,
+                                                                *bGeom,
+                                                                interior->GetPlane(),
+                                                                mBox,
+                                                                mEpsilon);
+                
                         if (cf == Polygon3::FRONT_SIDE)
-                                nodeStack.push(interior->GetFront());
+                        {
+                                nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
+                                DEL_PTR(bGeom);
+                        }
                         else
+                        {
                                 if (cf == Polygon3::BACK_SIDE)
-                                        nodeStack.push(interior->GetBack());
-                                else 
                                 {
-                                        // random decision
-                                        nodeStack.push(interior->GetBack());
-                                        nodeStack.push(interior->GetFront());
+                                        nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
+                                        DEL_PTR(fGeom);
                                 }
-                }
-        }
-        
+                                else
+                                {       // random decision
+                                        nodeStack.push(bspNodePair(front, fGeom));
+                                        nodeStack.push(bspNodePair(back, bGeom));
+                                }
+                        }
+                }
+        
+                DEL_PTR(geom);
+        }
+
         return (int)neighbors.size();
 }
@@ -2421 +2505 @@
 }
 
+
 BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
 {
@@ -2455 +2540 @@
         return NULL;
 }
+
 
 void BspTree::AddToPvs(BspLeaf *leaf,
@@ -2495 +2581 @@
 }
 
+
 int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
 {
@@ -2528 +2615 @@
 }
 
+
 float BspTree::GetEpsilon() const
 {
@@ -2534 +2622 @@
 
 
-/*************************************************************/
-/*            BspNodeGeometry Implementation                 */
-/*************************************************************/
+int BspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
+                                                                        vector<MergeCandidate> &candidates)
+{
+        BspLeaf::NewMail();
+        
+        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+        int numCandidates = 0;
+
+        // find merge candidates and push them into queue
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspLeaf *leaf = *it;
+                
+                // the same leaves must not be part of two merge candidates
+                leaf->Mail();
+                vector<BspLeaf *> neighbors;
+                FindNeighbors(leaf, neighbors, true);
+
+                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
+
+                // TODO: test if at least one ray goes from one leaf to the other
+                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+                {
+                        if ((*nit)->GetViewCell() != leaf->GetViewCell())
+                        {
+                                MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
+                                candidates.push_back(mc);
+
+                                ++ numCandidates;
+                                if ((numCandidates % 1000) == 0)
+                                {
+                                        cout << "collected " << numCandidates << " merge candidates" << endl;
+                                }
+                        }
+                }
+        }
+
+        Debug << "merge queue: " << (int)candidates.size() << endl;
+        Debug << "leaves in queue: " << numCandidates << endl;
+        
+
+        return (int)leaves.size();
+}
+
+
+int BspTree::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                        vector<MergeCandidate> &candidates)
+{
+        ViewCell::NewMail();
+        long startTime = GetTime();
+        
+        map<BspLeaf *, vector<BspLeaf*> > neighborMap;
+        ViewCellContainer::const_iterator iit;
+
+        int numLeaves = 0;
+        
+        BspLeaf::NewMail();
+
+        for (int i = 0; i < (int)rays.size(); ++ i)
+        {  
+                VssRay *ray = rays[i];
+        
+                // traverse leaves stored in the rays and compare and 
+                // merge consecutive leaves (i.e., the neighbors in the tree)
+                if (ray->mViewCells.size() < 2)
+                        continue;
+//TODO viewcellhierarchy
+                iit = ray->mViewCells.begin();
+                BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
+                BspLeaf *leaf = bspVc->mLeaf;
+                
+                // traverse intersections 
+                // consecutive leaves are neighbors => add them to queue
+                for (; iit != ray->mViewCells.end(); ++ iit)
+                {
+                        // next pair
+                        BspLeaf *prevLeaf = leaf;
+                        bspVc = dynamic_cast<BspViewCell *>(*iit);
+            leaf = bspVc->mLeaf;
+
+                        // view space not valid or same view cell
+                        if (!leaf->TreeValid() || !prevLeaf->TreeValid() ||
+                                (leaf->GetViewCell() == prevLeaf->GetViewCell()))
+                                continue;
+
+                vector<BspLeaf *> &neighbors = neighborMap[leaf];
+                        
+                        bool found = false;
+
+                        // both leaves inserted in queue already =>
+                        // look if double pair already exists
+                        if (leaf->Mailed() && prevLeaf->Mailed())
+                        {
+                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
+                                
+                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
+                                        if (*it == prevLeaf)
+                                                found = true; // already in queue
+                        }
+                
+                        if (!found)
+                        {
+                                // this pair is not in map yet
+                                // => insert into the neighbor map and the queue
+                                neighbors.push_back(prevLeaf);
+                                neighborMap[prevLeaf].push_back(leaf);
+
+                                leaf->Mail();
+                                prevLeaf->Mail();
+                
+                                MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
+                                
+                                candidates.push_back(mc);
+
+                                if (((int)candidates.size() % 1000) == 0)
+                                {
+                                        cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
+                                }
+                        }
+        }
+        }
+
+        Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
+        Debug << "merge queue: " << (int)candidates.size() << endl;
+        Debug << "leaves in queue: " << numLeaves << endl;
+
+
+        //-- collect the leaves which haven't been found by ray casting
+#if 0
+        cout << "finding additional merge candidates using geometry" << endl;
+        vector<BspLeaf *> leaves;
+        CollectLeaves(leaves, true);
+        Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
+        CollectMergeCandidates(leaves, candidates);
+#endif
+
+        return numLeaves;
+}
+
+
+
+
+/***************************************************************/
+/*              BspNodeGeometry Implementation                 */
+/***************************************************************/
 
 
@@ -2574 +2805 @@
 
         // note: can take arbitrary point, e.g., the origin. However,
-        // center of mass prevents precision errors
+        // we rather take the center of mass to prevents precision errors
         const Vector3 center = CenterOfMass();
 
@@ -2701 +2932 @@
                 front.mPolys.push_back(planePoly->CreateReversePolygon());
         }
-
-        //Debug << "returning new geometry " << mPolys.size() << " f: " << front.mPolys.size() << " b: " << back.mPolys.size() << endl;
-        //Debug << "old area " << GetArea() << " f: " << front.GetArea() << " b: " << back.GetArea() << endl;
 }