Changeset 587

Timestamp:

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

Author:

mattausch

Message:

updated vspkdtree for regular sudbivision

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (10 diffs)
• src/Environment.cpp (modified) (3 diffs)
• src/RssPreprocessor.cpp (modified) (1 diff)
• src/ViewCell.cpp (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (45 diffs)
• src/ViewCellBsp.h (modified) (14 diffs)
• src/ViewCellsManager.cpp (modified) (21 diffs)
• src/ViewCellsManager.h (modified) (1 diff)
• src/VspBspTree.cpp (modified) (6 diffs)
• src/VspBspTree.h (modified) (1 diff)
• src/VspKdTree.cpp (modified) (2 diffs)
• src/VspKdTree.h (modified) (2 diffs)
• src/VssPreprocessor.cpp (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -25 +25 @@
         type vss
 #       type rss
-        detectEmptyViewSpace false
+        detectEmptyViewSpace true
 }
 
@@ -181 +181 @@
 
         #number of active view cells
-        active 250
+        active 169
         maxStaticMemory 40
 
@@ -188 +188 @@
 
         #type kdTree
-        #type vspKdTree
-        type bspTree
+        type vspKdTree
+        #type bspTree
         #type vspBspTree
         
@@ -205 +205 @@
                 # how much samples are used for post processing
                 samples 300000
-                renderCostWeight 0.5
+                renderCostWeight 1.0
                 maxCostRatio 0.1
                 minViewCells 1
@@ -211 +211 @@
                 maxMergesPerPass 500 
                 useRaysForMerge false
-                refine true
+                refine false
                 compress false
         }
@@ -253 +253 @@
         Termination {
                 maxDepth                40
-                minPvs                  50
-                minRays                 800
+                minPvs                  0
+                minRays                 1
                 minSize                 0.001
-                maxCostRatio            0.9
+                maxCostRatio            5.9
+                maxViewCells            169
                 missTolerance           4
-                maxRayContribution      0.5
+                maxRayContribution      2.5
         }
         
@@ -266 +267 @@
         splitType       regular
         #splitType      heuristics
-        splitUseOnlyDrivingAxis false
+        splitUseOnlyDrivingAxis true
         ct_div_ci       0.0
         
@@ -272 +273 @@
         PostProcess {
                 maxCostRatio 0.005
-                minViewCells 1
+                minViewCells 10000
                 maxPvsSize   5000
         }
@@ -349 +350 @@
 BspTree {
         Construction {
-                samples 0
+                samples 50000
                 epsilon 0.005
         }
@@ -409 +410 @@
         Termination {
                 # parameters used for autopartition
-                minRays 200
+                minRays -1
                 minPolygons 1
-                maxDepth 40
-                minPvs 100
-                minArea 0.01
-                maxRayContribution 0.005
+                maxDepth 30
+                minPvs -1
+                minProbability 0.001
+                maxRayContribution 9999
                 #maxAccRayLength 100
-                
+                maxViewCells    5000
+
                 # used for pvs criterium
                 ct_div_ci 0.0

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1395 +1395 @@
                         "20");
 
-        RegisterOption("BspTree.Termination.minArea",
+        RegisterOption("BspTree.Termination.minProbability",
                         optFloat,
-                        "bsp_term_min_area=",
+                        "bsp_term_min_probability=",
                         "0.001");
 
@@ -1473 +1473 @@
                 optInt,
                 "bsp_max_tests=",
+                "5000");
+
+        RegisterOption("BspTree.Termination.maxViewCells",
+                optInt,
+                "bsp_max_view_cells=",
                 "5000");
 
@@ -1632 +1637 @@
                 "1000");
 
+        RegisterOption("VspKdTree.Termination.maxViewCells", 
+                optInt, 
+                "vsp_kd_term_post_process_min_view_cells=", 
+                "300");
+
         RegisterOption("VspKdTree.PostProcess.maxPvsSize", 
                 optInt, 

trunk/VUT/GtpVisibilityPreprocessor/src/RssPreprocessor.cpp

@@ -479 +479 @@
 
           //-- several visualizations and statistics
-          Debug << "view cells after construction: " << endl;
+          Debug << "view cells construction finished: " << endl;
           mViewCellsManager->PrintStatistics(Debug);
   }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -673 +673 @@
         if ((int)activeViewCells.size() > 1)
         {
-                Debug << "creating root of view cell hierarchy for " << (int)activeViewCells.size() << " view cells" << endl;
+                Debug << "creating root of view cell hierarchy for " 
+                          << (int)activeViewCells.size() << " view cells" << endl;
                 /*for (int i = 0;  i < activeViewCells.size(); ++ i){
                         Debug << "parent " << activeViewCells[i]->GetParent() << endl;
-                        Debug << "viewcell " << activeViewCells[i] << endl;*/
-                }
+                        Debug << "viewcell " << activeViewCells[i] << endl;
+                }*/
                 ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
 

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;
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -19 +19 @@
 class Ray;
 class ViewCellsStatistics;
+class ViewCellsManager;
+
+
 
 class BspNodeGeometry
@@ -374 +377 @@
                 /// rays piercing this node
                 BoundedRayContainer *mRays;
-                /// area of current node
-                float mArea;
+                /// probability of current node
+                float mProbability;
                 /// geometry of node as induced by planes
                 BspNodeGeometry *mGeometry;
@@ -397 +400 @@
                 mRays(NULL),
                 mPvs(0),
-                mArea(0.0),
+                mProbability(0.0),
                 mGeometry(NULL)
                 {}
@@ -407 +410 @@
                                                  BoundedRayContainer *rays,
                                                  int pvs,
-                                                 float area,
+                                                 float p,
                                                  BspNodeGeometry *cell): 
                 mNode(node), 
@@ -415 +418 @@
                 mRays(rays),
                 mPvs(pvs),
-                mArea(area),
+                mProbability(p),
                 mGeometry(cell)
                 {}
+
+
+                float GetCost() const
+                {
+#if 0
+                        return mPvs * mProbability;
+#endif
+#if 1
+                        return mProbability;
+#endif
+#if 0
+                        return (float)mPvs;
+#endif
+#if 0
+                        return (float)mRays->size();
+#endif
+                }
+                
+                friend bool operator<(const BspTraversalData &a, const BspTraversalData &b)
+                {
+                        return a.GetCost() < b.GetCost();
+                }
     };
         
-        typedef std::stack<BspTraversalData> BspTraversalStack;
-        
+        //typedef std::stack<BspTraversalData> BspTraversalStack;
+        typedef std::priority_queue<BspTraversalData> BspTraversalStack;
+
         /** Default constructor reading the environment file and 
                 creating an empty tree.
@@ -451 +477 @@
 
         void Construct(const ObjectContainer &objects,
-                                   const RayContainer &sampleRays);
+                                   const RayContainer &sampleRays,
+                                   AxisAlignedBox3 *forcedBoundingBox);
 
         /** Constructs the tree from a given set of rays.
@@ -458 +485 @@
                 created in the leafs and stored in the conatainer
         */
-        void Construct(const RayContainer &sampleRays);
+        void Construct(const RayContainer &sampleRays,
+                                   AxisAlignedBox3 *forcedBoundingBox);
 
         /** Returns list of BSP leaves.
@@ -513 +541 @@
         /** Construct geometry of view cell.
         */
-        void ConstructGeometry(BspViewCell *vc, BspNodeGeometry &geom) const;
+        void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;
+
+                        
+        /** Sets pointer to view cells manager.
+        */
+        void SetViewCellsManager(ViewCellsManager *vcm);
 
         /** Returns random leaf of BSP tree.
@@ -533 +566 @@
         float GetEpsilon() const;
 
+        int CollectMergeCandidates(const vector<BspLeaf *> leaves,
+                                                           vector<MergeCandidate> &candidates);
+
+        int CollectMergeCandidates(const VssRayContainer &rays,
+                                                   vector<MergeCandidate> &candidates);
 protected:
 
@@ -608 +646 @@
                                                  const BoundedRayContainer &rays,
                                                  const int pvs,
-                                                 const float area,
+                                                 const float probability,
                                                  const BspNodeGeometry &cell) const;
 
@@ -681 +719 @@
         int AddToPolygonSoup(const ObjectContainer &objects, 
                                                  PolygonContainer &polys, 
-                                                 int maxObjects = 0);
+                                                 int maxObjects = 0,
+                                                 bool addToBbox = true);
 
         /** Extracts the meshes of the view cells and and adds them to polygons.
@@ -809 +848 @@
                                   int &sampleContributions,     
                                   int &contributingSamples);
+
+
+
 
         /// Pointer to the root of the tree.
@@ -847 +889 @@
         int mTermMaxDepth;
         /// mininum area
-        float mTermMinArea;
+        float mTermMinProbability;
         /// mininum PVS
         int mTermMinPvs;
@@ -893 +935 @@
         bool mUseAreaForPvs;
 
+        int mMaxViewCells;
+
         /// epsilon where two points are still considered equal
         float mEpsilon;
+
+        ViewCellsManager *mViewCellsManager;
+
 
 private:

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -920 +920 @@
 {
         environment->GetIntValue("BspTree.Construction.samples", mInitialSamples);
+        mBspTree->SetViewCellsManager(this);
 }
 
@@ -965 +966 @@
         {
                 // no view cells loaded
-                mBspTree->Construct(objects, constructionRays);
+                mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
                 // collect final view cells
                 mBspTree->CollectViewCells(mViewCells);
@@ -986 +987 @@
 
 
+        ResetViewCells();
+    
+        Debug << "\nView cells after " << (int)savedRays.size() 
+                  << " samples:\n" << mViewCellsStats << endl;
+
+        if (1) // export initial view cells
+        {
+                cout << "exporting initial view cells (=leaves) ... ";
+                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
+
+                if (exporter)
+                {
+                        //exporter->SetWireframe();
+                        exporter->SetFilled();
+                        ExportViewCellsForViz(exporter);
+
+                        if (0 && mExportRays)
+                                exporter->ExportRays(rays, RgbColor(1, 1, 1));
+
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+
         return sampleContributions;
 }
@@ -992 +1021 @@
 void BspViewCellsManager::CollectViewCells()
 {
-        mBspTree->CollectViewCells(mViewCells);
+        // view cells tree constructed
+        if (!ViewCellsTreeConstructed())
+        {
+                mBspTree->CollectViewCells(mViewCells);
+        }
+        else 
+        {
+                // we can use the view cells tree hierarchy to get the right set
+                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumMergedViewCells);
+        }
 }
 
@@ -1007 +1045 @@
 
 
-float BspViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
+float BspViewCellsManager::GetRendercost(ViewCell *viewCell, 
+                                                                                 float objRendercost) const
 {
         return viewCell->GetPvs().GetSize() * objRendercost;
@@ -1072 +1111 @@
 
         long startTime = GetTime();
-
+        
+        VssRayContainer postProcessRays;
+        GetRaySets(rays, mPostProcessSamples, postProcessRays);
 
         //-- merge or subdivide view cells
-        int merged = 0;
-
-        // TODO
-        
+        int merged = mViewCellsTree->ConstructMergeTree(rays, objects);
+
         //-- stats and visualizations
         cout << "finished" << endl;
@@ -1088 +1127 @@
                   << "using " << (int)rays.size() << " samples" << endl << endl;
 
+
         // reset view cells and stats
         ResetViewCells();
+        FinalizeViewCells(true);
+        
+        // for output we need unique ids for each view cell
+        CreateUniqueViewCellIds();
+
+        // write view cells to disc
+        if (mExportViewCells)
+        {
+                char buff[100];
+                environment->GetStringValue("ViewCells.filename", buff);
+                string vcFilename(buff);
+
+                ExportViewCells(buff);
+        }
 
         return merged;
@@ -1112 +1166 @@
                 return;
         
-        if (1) // export view cells
-        {
+        //BspLeaf::NewMail();
+        if (1) // export merged view cells
+        {
+
+                cout << "reseting view cells ... ";
+                ResetViewCells();
+
+                cout << "finished" << endl;
+
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
+                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
+
                 cout << "exporting view cells after merge ... ";
-                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
-
 
                 if (exporter)
                 {
+                        if (0)
+                                exporter->SetWireframe();
+                        else
+                                exporter->SetFilled();
                         ExportViewCellsForViz(exporter);
+
+                        if (mExportGeometry)
+                        {
+                                Material m;
+                                m.mDiffuseColor = RgbColor(0, 1, 0);
+                                exporter->SetForcedMaterial(m);
+                                exporter->SetFilled();
+
+                                exporter->ExportGeometry(objects);
+                        }
+
                         delete exporter;
                 }
-
                 cout << "finished" << endl;
         }
@@ -1189 +1265 @@
 
         // sort view cells to get largest view cells
-#if 0
-        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
-#endif
+        if (0)
+                stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
+
         int limit = min(leafOut, (int)mViewCells.size());
 
@@ -1208 +1284 @@
                 cout << "creating output for view cell " << i << " ... ";
 
-#if 0
-                // check whether we can add the current ray to the output rays
-                for (int k = 0; k < raysOut; ++ k)
-                {
-                        BspRay *ray = mBspRays[k];
-                        for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
+                if(0)
+                {
+                        // check whether we can add the current ray to the output rays
+                        for (int k = 0; k < raysOut; ++ k)
                         {
-                                BspLeaf *leaf = ray->intersections[j].mLeaf;
-                                if (vc == leaf->GetViewCell())
-                                        vcRays.push_back(ray->vssRay);
+                                BspRay *ray = mBspRays[k];
+                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
+                                {
+                                        BspLeaf *leaf = ray->intersections[j].mLeaf;
+                                        if (vc == leaf->GetViewCell())
+                                                vcRays.push_back(ray->vssRay);
+                                }
                         }
                 }
-#endif
+
                 //bspLeaves[j]->Mail();
                 char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
@@ -1232 +1310 @@
                 exporter->SetForcedMaterial(m);
 
-                if (vc->GetMesh())
-                        exporter->ExportViewCell(vc);
-                else
-                {
-                        BspNodeGeometry vcGeom;
-
-                        //-- export view cell
-#if VC_HISTORY
-                        mBspTree->ConstructGeometry(vc, vcGeom);
-                        exporter->ExportPolygons(vcGeom.mPolys);
-#endif
-                }
+                ExportViewCellGeometry(exporter, vc);
+                
 
                 Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc)
@@ -1284 +1352 @@
 
 
-
-void BspViewCellsManager::ConstructBspRays(const VssRayContainer &rays,
-                                                                                   const int numSamples)
-{
-        VssRayContainer::const_iterator it, it_end = rays.end();
-
-        for (it = rays.begin(); it != rays.end() && mBspRays.size() < numSamples; ++ it)
-        {
-                VssRay *vssRay = *it;
-                BspRay *ray = new BspRay(vssRay);
-
-                ViewCellContainer viewCells;
-
-                // cast line segment to get intersections with bsp leaves
-                CastLineSegment(vssRay->mTermination, vssRay->mOrigin, viewCells);
-#if VC_HISTORY
-                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
-                {
-                        ViewCell *vc = *vit;
-                        ray->intersections.push_back(BspIntersection(0, vc->mLeaf));
-                }
-#endif
-                mBspRays.push_back(ray);
-        }
-}
-
-
 void BspViewCellsManager::ExportColor(Exporter *exporter,
                                                                           ViewCell *vc) const
@@ -1354 +1394 @@
 }
 
+
 void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
-                                                                                 ViewCell *vc) const
+                                                                                                 ViewCell *vc) const
 {
         if (vc->GetMesh())
-                exporter->ExportViewCell(vc);
+        {
+                exporter->ExportMesh(vc->GetMesh());
+                return;
+        }
+
+        BspNodeGeometry geom;
+        mBspTree->ConstructGeometry(vc, geom);
+        exporter->ExportPolygons(geom.mPolys);
+}
+
+
+void BspViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        if (vc->GetMesh())
+                delete vc->GetMesh();
+
+        BspNodeGeometry geom;
+        
+        mBspTree->ConstructGeometry(vc, geom);
+
+        Mesh *mesh = new Mesh();
+        geom.AddToMesh(*mesh);
+        vc->SetMesh(mesh);
+        mMeshContainer.push_back(mesh);
+}
+
+
+void BspViewCellsManager::Finalize(ViewCell *viewCell, 
+                                                                   const bool createMesh)
+{
+        CreateMesh(viewCell);
+
+        float area = 0;
+        float volume = 0;
+
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(viewCell, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspNodeGeometry geom;
+                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                mBspTree->ConstructGeometry(leaf, geom);
+
+                area += geom.GetArea();
+                volume += geom.GetVolume();
+        }
+
+        viewCell->SetVolume(volume);
+        viewCell->SetArea(area);
+}
+
+
+ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point) const
+{
+        if (!mBspTree)
+                return NULL;
+
+        if (!mViewSpaceBox.IsInside(point))
+                return NULL;
+        
+        return mBspTree->GetViewCell(point);
+}
+
+
+void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                 vector<MergeCandidate> &candidates)
+{
+        cout << "collecting merge candidates ... " << endl;
+
+        if (mUseRaysForMerge)
+        {
+                mBspTree->CollectMergeCandidates(rays, candidates);
+        }
         else
         {
-                BspNodeGeometry geom;
-#if VC_HISTORY
-                mBspTree->ConstructGeometry(vc, geom);
-                exporter->ExportPolygons(geom.mPolys);
-#endif
-        }
-}
-
-
-void BspViewCellsManager::CreateMesh(ViewCell *vc)
-{
-        // TODO
-}
-
-
-ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point) const
-{
-  if (!mBspTree)
-        return NULL;
-
-  if (!mViewSpaceBox.IsInside(point))
-        return NULL;
-
-  return mBspTree->GetViewCell(point);
-}
-
-
-void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates)
-{
-        // TODO
+                vector<BspLeaf *> leaves;
+                mBspTree->CollectLeaves(leaves);
+                mBspTree->CollectMergeCandidates(leaves, candidates);
+        }
+
+        cout << "fininshed collecting candidates" << endl;
 }
 
@@ -1453 +1545 @@
         return 0;
 }
+
 
 bool KdViewCellsManager::ViewCellsConstructed() const
@@ -2154 +2247 @@
         VssRayContainer savedRays;
 
-        Debug << "samples used for subdivision: " << mInitialSamples << " rays: " << (int)rays.size() << endl;
+        Debug << "samples used for subdivision: " << mInitialSamples 
+                  << " rays: " << (int)rays.size() << endl;
+
         GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
 
@@ -2170 +2265 @@
         long startTime = GetTime();
         int collapsedLeaves = mVspBspTree->CollapseTree();
-        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 << " seconds" << endl;
+        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
+                  << " seconds" << endl;
+
     cout << "finished" << endl;
 
@@ -2257 +2354 @@
                 cout << "reseting view cells ... ";
                 ResetViewCells();
+
                 cout << "finished" << endl;
 
@@ -2685 +2783 @@
 
         // sort view cells to visualize the largest view cells
-#if 0
-        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
-#endif
+        if (0)
+                stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
+
         int limit = min(leafOut, (int)mViewCells.size());
 
-#if 1
+        int raysOut;
+
         //-- some rays for output
-        const int raysOut = min((int)rays.size(), mVisualizationSamples);
-
-#endif
+        if (1)
+                raysOut = min((int)rays.size(), mVisualizationSamples);
 
         for (int i = 0; i < limit; ++ i)
@@ -2709 +2807 @@
                         vc = mViewCells[Random((int)mViewCells.size())];
 
+                vector<ViewCell *> leaves;
+                mViewCellsTree->CollectLeaves(vc, leaves);
+
         if (1)
                 {
@@ -2718 +2819 @@
                                 {
                                         ViewCell *rayvc = ray->mViewCells[j];
-#if VC_HISTORY
-                                        BspLeaf *leaf = rayvc->mLeaf;
-                                        if (vc == rayvc)
+
+                                        if (leaves[0] == rayvc)
                                                 vcRays.push_back(ray);
-#endif
                                 }
                         }
@@ -3021 +3120 @@
 
 
-void VspBspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
+void VspBspViewCellsManager::Finalize(ViewCell *viewCell, 
+                                                                          const bool createMesh)
 {
         CreateMesh(viewCell);

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -509 +509 @@
         void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
         
-        void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
+        void CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                vector<MergeCandidate> &candidates);
+
+        void Finalize(ViewCell *viewCell, const bool createMesh);
 
 protected:
 
         void CollectViewCells();
-
-        void ConstructBspRays(const VssRayContainer &rays,
-                                                  const int numSamples);
 
         void ExportColor(Exporter *exporter, ViewCell *vc) const;

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -364 +364 @@
         }
 
+        // normalize
         if (mUseAreaForPvs)
-                mTermMinProbability *= mBox.SurfaceArea(); // normalize
+                mTermMinProbability *= mBox.SurfaceArea(); 
         else 
                 mTermMinProbability *= mBox.GetVolume();
@@ -385 +386 @@
 
 // return memory usage in MB
-float VspBspTree::GetMemUsage() const
+float VspBspTree::GetMemUsage(/*const VspBspTraversalStack &tstack*/) const
 {
         return
                 (sizeof(VspBspTree) +
-                 mBspStats.Leaves() * sizeof(BspLeaf) +
+                 (float)mBspStats.Leaves() * sizeof(BspLeaf) + 
+                 // the nodes in the stack is the minimal additional number of leaves
+                 //(float)tstack.size() * sizeof(BspLeaf) +
                  mBspStats.Interior() * sizeof(BspInterior) +
                  mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
@@ -428 +431 @@
 
         long startTime = GetTime();     
-        // used for intermediate time measurements
+
+        // used for intermediate time measurements and progress
         long interTime = GetTime();     
 
@@ -451 +455 @@
                 }
 
-                        // subdivide leaf node
+                // subdivide leaf node
                 BspNode *r = Subdivide(tStack, tData);
 
@@ -464 +468 @@
                         cout << "leaves=" << mBspStats.Leaves() << endl;
                         Debug << "needed "
-                          << TimeDiff(interTime, GetTime())*1e-3 << " secs to create 500 leaves" << endl;
+                                  << TimeDiff(interTime, GetTime())*1e-3 
+                                  << " secs to create 500 leaves" << endl;
                         interTime = GetTime();
                 }
@@ -1621 +1626 @@
                   << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
                   << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
-          //              << "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
+          //              << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
                   << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
                   << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -591 +591 @@
         void ExportNode(BspNode *node, ofstream &stream);
 
-        /** Returns memory usage of tree.
-        */
+        /** Returns estimated memory usage of tree.
+        */
+        //float GetMemUsage(const VspBspTraversalStack &tstack) const;
         float GetMemUsage() const;
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -433 +433 @@
 
         environment->GetBoolValue("VspKdTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
+        environment->GetIntValue("VspKdTree.Termination.maxViewCells", mMaxViewCells);
 
         //-- output
@@ -1149 +1150 @@
                         (leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
                         (leaf->mDepth >= mTermMaxDepth) ||
+                        (mStat.Leaves() >= mMaxViewCells) ||
                         (SqrMagnitude(box.Size()) <= mTermMinSize));
 }

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -540 +540 @@
                                 leafb->rays.size() * b.mBox.GetVolume();
 #endif
-#if 1
+#if 0
                         return
                                 leafa->GetPvsSize() * a.mBox.GetVolume()
@@ -564 +564 @@
                                 leafb->GetPvsSize() * (float)leafb->rays.size();
 #endif
+#if 1
+                        return a.mDepth > b.mDepth;
+#endif
                 }
         };

trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

@@ -543 +543 @@
 
           //-- several visualizations and statistics
-          Debug << "view cells after construction: " << endl;
+          Debug << "view cells construction finished: " << endl;
           mViewCellsManager->PrintStatistics(Debug);
   }
@@ -750 +750 @@
   }
 
-  Debug << vssTree->stat << endl;
+  if (0)
+          Debug << vssTree->stat << endl;
 
   if (0)