Changeset 442

Timestamp:

12/02/05 02:02:07 (19 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• ViewCellBsp.cpp (modified) (18 diffs)
• ViewCellBsp.h (modified) (7 diffs)
• ViewCellsManager.cpp (modified) (2 diffs)
• ViewCellsManager.h (modified) (2 diffs)
• VspBspTree.cpp (modified) (13 diffs)
• VspBspTree.h (modified) (8 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -265 +265 @@
 BspTree::BspTree():  
 mRoot(NULL), 
-mStoreLeavesWithRays(false),
-mPvsUseLen(false),
+mPvsUseArea(true),
 mGenerateViewCells(true)
 {
@@ -438 +437 @@
                 mRoot = new BspLeaf();
 
-        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, 
-                new BoundedRayContainer(), 0));
+        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0, 
+                                                                 mBox.SurfaceArea(), new BspNodeGeometry()));
 
         while (!tStack.empty())
@@ -475 +474 @@
                                                                                    mRootCell,   
                                                                                    tData.mRays,
-                                                                                   tData.mPvs);
+                                                                                   tData.mPvs,
+                                                                                   mBox.SurfaceArea(),
+                                                                                   new BspNodeGeometry());
 
                                 BspTraversalData backData(interior->GetBack(), 
@@ -482 +483 @@
                                                                                   mRootCell,    
                                                                                   tData.mRays,
-                                                                                  tData.mPvs);
+                                                                                  tData.mPvs,
+                                                                                  mBox.SurfaceArea(),
+                                                                                  new BspNodeGeometry());
 
                                 if (!mGenerateViewCells)
@@ -732 +735 @@
         mRoot = new BspLeaf();
 
+        // constrruct root node geometry
         BspNodeGeometry *cell = new BspNodeGeometry();
         ConstructGeometry(mRoot, *cell);
 
         BspTraversalData tData(mRoot, polys, 0, mRootCell, rays, 
-                                                   ComputePvsSize(*rays));
+                                                   ComputePvsSize(*rays), cell->GetArea(), cell);
 
         tStack.push(tData);
@@ -756 +760 @@
         }
 
-        Debug << "here2" << endl;
         cout << "finished\n";
 
@@ -768 +771 @@
                  ((int)data.mRays->size() <= mTermMinRays) ||
                  (data.mPvs <= mTermMinPvs) ||
+                 (data.mArea <= mTermMinArea) ||
                  (data.mDepth >= mTermMaxDepth) ||
                  (data.GetAvgRayContribution() < mTermMaxRayContribution));
@@ -824 +828 @@
         
         BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 
-                                                                new BoundedRayContainer(), 0);
+                                                                new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
         BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 
-                                                           new BoundedRayContainer(), 0);
+                                                           new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
 
         // create new interior node and two leaf nodes
@@ -860 +864 @@
         DEL_PTR(tData.mPolygons);
         DEL_PTR(tData.mRays);
+        DEL_PTR(tData.mGeometry);               
         
         return interior;
@@ -935 +940 @@
         frontData.mPvs = ComputePvsSize(*frontData.mRays);
         backData.mPvs = ComputePvsSize(*backData.mRays);
+
+        // split geometry and compute area
+        if (1)
+        {
+                tData.mGeometry->SplitGeometry(*frontData.mGeometry, 
+                                                                           *backData.mGeometry, 
+                                                                           *this, 
+                                                                           interior->mPlane);
+        
+                
+                frontData.mArea = frontData.mGeometry->GetArea();
+                backData.mArea = backData.mGeometry->GetArea();
+        }
 
         // compute accumulated ray length
@@ -1453 +1471 @@
 float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
                                                           const BoundedRayContainer &rays,
-                                                          const int pvs) const
+                                                          const int pvs,
+                                                          const float area,
+                                                          const BspNodeGeometry &cell) const
 {
         float val = 0;
@@ -1464 +1484 @@
 
         // probability that view point lies in child
-        float pOverall = 1;
-        float pFront = 0.5;
-        float pBack = 0.5;
+        float pOverall = 0;
+        float pFront = 0;
+        float pBack = 0;
+
+        const bool pvsUseLen = false;
 
         if (mSplitPlaneStrategy & PVS)
@@ -1472 +1494 @@
                 // create unique ids for pvs heuristics
                 GenerateUniqueIdsForPvs();
+
+                if (mPvsUseArea) // 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, *this, candidatePlane);
+                
+                        pFront = frontCell.GetArea();
+                        pBack = backCell.GetArea();
+
+                        pOverall = area;
+                }
         }
                         
@@ -1527 +1563 @@
                         AddObjToPvs(ray->sourceObject.mObject, cf, frontPvs, backPvs);
                         
-                        float len = 1;
-                        if (0){
-                        if (mPvsUseLen)
-                                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 (mPvsUseArea)
                         {
-                                if (mPvsUseLen)
+                                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)
                                 {
-                                        const Vector3 extp = ray->Extrap(maxT);
-                                        const float t = candidatePlane.FindT(ray->GetLoc(), extp);
+                                        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;
+                                                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
                                         {
-                                                pBack += len - newLen;
-                                                pFront += newLen;
+                                                ++ pFront;
+                                                ++ pBack;
                                         }
                                 }
-                                else
-                                {
-                                        ++ pFront;
-                                        ++ pBack;
-                                }
-                        }}
+                        }
                 }
         }
@@ -1575 +1614 @@
                 val += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize;
 
-        float denom = pOverall * (float)pvs * 2.0f + Limits::Small;
+        const float denom = pOverall * (float)pvs * 2.0f + Limits::Small;
 
         if (mSplitPlaneStrategy & PVS)
@@ -1583 +1622 @@
                 // give penalty to unbalanced split
                 if (1)
-                if (((pFront * 0.2 + Limits::Small) > pBack) || (pFront < (pBack * 0.2 + Limits::Small)))
+                if (((pFront * 0.2 + Limits::Small) > pBack) || 
+                        (pFront < (pBack * 0.2 + Limits::Small)))
                         val += 0.5;
         }
@@ -1670 +1710 @@
                 (mSplitPlaneStrategy & PVS))
         {
-                val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs);
+                val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs, 
+                                                          data.mArea, *data.mGeometry);
         }
 
@@ -1741 +1782 @@
                 ++ mStat.maxRayContribNodes;
         
-        //if (data.mGeometry->GetArea() <= mTermMinArea) 
-        //      ++ mStat.minAreaNodes;
+        if (data.mGeometry->GetArea() <= mTermMinArea) 
+                ++ mStat.minAreaNodes;
 
 #ifdef _DEBUG

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -364 +364 @@
                 /// rays piercing this node
                 BoundedRayContainer *mRays;
+                /// area of current node
+                float mArea;
+                /// geometry of node as induced by planes
+                BspNodeGeometry *mGeometry;
                 
                 /// pvs size
@@ -382 +386 @@
                 mViewCell(NULL),
                 mRays(NULL),
-                mPvs(0)
+                mPvs(0),
+                mArea(0.0),
+                mGeometry(NULL)
                 {}
                 
@@ -390 +396 @@
                                                  ViewCell *viewCell,
                                                  BoundedRayContainer *rays,
-                                                 int pvs): 
+                                                 int pvs,
+                                                 float area,
+                                                 BspNodeGeometry *cell): 
                 mNode(node), 
                 mPolygons(polys), 
@@ -396 +404 @@
                 mViewCell(viewCell),
                 mRays(rays),
-                mPvs(pvs)
+                mPvs(pvs),
+                mArea(area),
+                mGeometry(cell)
                 {}
     };
@@ -584 +594 @@
         float SplitPlaneCost(const Plane3 &candidatePlane, 
                                                  const BoundedRayContainer &rays,
-                                                 const int pvs) const;
+                                                 const int pvs,
+                                                 const float area,
+                                                 const BspNodeGeometry &cell) const;
 
         /** Filters next view cell down the tree and inserts it into the appropriate leaves
@@ -820 +832 @@
         float mCtDivCi;
 
-        /// if intersected leaves should be stored with a sample
-        bool mStoreLeavesWithRays;
-
         /// axis aligned split criteria
         float mAaCtDivCi;
@@ -840 +849 @@
 
         /// if area or accumulated ray lenght should be used for PVS heuristics
-        bool mPvsUseLen;
+        bool mPvsUseArea;
 
 private:

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -10 +10 @@
 #include "VspKdTree.h"
 #include "Exporter.h"
-
+#include "VspBspTree.h"
 
 
@@ -1121 +1121 @@
         return VSP_KD;
 }
+
+
+/**********************************************************************/
+/*                 VspBspViewCellsManager implementation              */
+/**********************************************************************/
+
+VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree, 
+                                                                                           int constructionSamples):
+ViewCellsManager(constructionSamples), 
+mVspBspTree(vspBspTree)
+{
+   mRenderSimulator = NULL;// TODO new VspBspRenderSimulator(bspTree);
+   //InitRenderSimulator();
+}
+
+bool VspBspViewCellsManager::ViewCellsConstructed() const
+{
+        return mVspBspTree->GetRoot() != NULL;
+}
+
+ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new BspViewCell(mesh);
+}
+
+int VspBspViewCellsManager::Construct(const ObjectContainer &objects, 
+                                                                          const VssRayContainer &rays,
+                                                                          AxisAlignedBox3 *sceneBbox)
+{
+        // if view cells were already constructed
+        if (ViewCellsConstructed())
+                return 0;
+
+        Debug << "Constructing bsp view cells" << endl;
+
+        int sampleContributions = 0;
+        
+        VssRayContainer sampleRays;
+
+        int limit = min (mConstructionSamples, (int)rays.size());
+
+    for (int i = 0; i < limit; ++ i)
+                sampleRays.push_back(rays[i]);
+
+        mVspBspTree->Construct(sampleRays);
+        
+        Debug << mVspBspTree->GetStatistics() << endl;
+
+        return sampleContributions;
+}
+
+int VspBspViewCellsManager::ComputeSampleContributions(Ray &ray, const bool castRay)
+{
+        // view cells not yet constructed
+        if (!ViewCellsConstructed())
+                return 0;
+
+        int contributingSamples = 0;
+
+        if (castRay)
+                mVspBspTree->CastRay(ray);
+
+        Intersectable *tObject = 
+                !ray.intersections.empty() ? ray.intersections[0].mObject : NULL;
+
+        Intersectable *sObject = ray.sourceObject.mObject;
+
+        if (sObject || tObject)
+        {
+                // object can be seen from the view cell => add to view cell pvs
+                for (int j = 0; j < (int)ray.bspIntersections.size(); ++ j)
+                {       
+                        VspBspLeaf *leaf = NULL;  //TODO ray.bspIntersections[j].mLeaf;
+                
+                        // if ray not in unbounded space
+                        if (leaf->GetViewCell() != mVspBspTree->GetRootCell())
+                        {
+                                if (sObject)
+                                {
+                                        contributingSamples += 
+                                                leaf->GetViewCell()->GetPvs().AddSample(sObject);
+                                }
+
+                                if (tObject)
+                                {
+                                        contributingSamples += 
+                                                leaf->GetViewCell()->GetPvs().AddSample(tObject);
+                                }
+                        }
+                }
+        }
+
+        // rays passing through this viewcell
+        if (0)
+                for (int j = 1; j < ((int)ray.bspIntersections.size() - 1); ++ j) 
+                {
+                        VspBspLeaf *leaf = NULL;// TODO = ray.bspIntersections[j].mLeaf;
+
+                        if (leaf->GetViewCell() != mVspBspTree->GetRootCell())
+                                leaf->GetViewCell()->
+                                        AddPassingRay(ray, contributingSamples ? 1 : 0);
+                }
+
+        return contributingSamples;
+}
+
+int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects, 
+                                                                                const RayContainer &rays)
+{
+        if (!ViewCellsConstructed())
+        {
+                Debug << "view cells not constructed" << endl;
+                return 0;
+        }
+
+
+        //-- post processing of bsp view cells
+    int vcSize = 0;
+        int pvsSize = 0;
+
+        BspViewCellsStatistics vcStats;
+        mVspBspTree->EvaluateViewCellsStats( vcStats);
+        Debug << "original view cell partition:\n" << vcStats << endl;
+                
+        if (1) // export view cells
+        {
+                cout << "exporting initial view cells (=leaves) ... ";
+                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
+        
+                if (exporter)
+                {
+                        exporter->SetWireframe();
+                        //exporter->ExportBspLeaves(*mVspBspTree, stat.maxPvs);
+                                
+                        if (0)
+                        {
+                                Material m;
+                                m.mDiffuseColor = RgbColor(0, 1, 0);
+                                exporter->SetForcedMaterial(m);
+                                exporter->SetWireframe();
+
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
+                
+        long startTime = GetTime();
+
+
+        //-- merge or subdivide view cells
+        int merged = 0;
+
+        RayContainer::const_iterator rit, rit_end = rays.end();
+        vector<Ray::BspIntersection>::const_iterator iit;
+
+        int limit = min((int)rays.size(), mPostProcessSamples);
+
+        for (int i = 0; i < limit; ++ i)
+        {  
+                Ray *ray = rays[i];
+
+                // traverse leaves stored in the rays and compare and merge consecutive
+                // leaves (i.e., the neighbors in the tree)
+                if (ray->bspIntersections.size() < 2)
+                        continue;
+
+                iit = ray->bspIntersections.begin();
+
+                BspLeaf *previousLeaf = (*iit).mLeaf;
+                ++ iit;
+                
+                for (; iit != ray->bspIntersections.end(); ++ iit)
+                {
+                        BspLeaf *leaf = (*iit).mLeaf;
+
+                        if (ShouldMerge(leaf, previousLeaf))
+                        {                       
+                                MergeBspLeafViewCells(leaf, previousLeaf);
+
+                                ++ merged;
+                        }
+                
+                        previousLeaf = leaf;
+                }
+        }
+
+        //-- stats and visualizations
+        cout << "finished" << endl;
+        cout << "merged " << merged << " view cells in "
+                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
+
+        return merged;
+}
+
+int VspBspViewCellsManager::GetType() const
+{
+        return VSP_BSP;
+}
+
+
+void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                           const RayContainer &sampleRays)
+{
+        if (!ViewCellsConstructed())
+                return;
+
+        //-- recount pvs
+        BspViewCellsStatistics vcStats;
+        mVspBspTree->EvaluateViewCellsStats(vcStats);
+
+        if (1) // export view cells
+        {
+                cout << "exporting view cells after merge ... ";
+                /*Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
+
+                if (exporter)
+                {
+                        exporter->ExportBspViewCellPartition(*mVspBspTree, vcStats.maxPvs);
+                        delete exporter;
+                }
+                */
+                cout << "finished" << endl;
+        }       
+
+        //-- visualization of the BSP splits
+        bool exportSplits = false;
+                environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
+        
+        if (exportSplits)
+        {
+                cout << "exporting splits ... ";
+                ExportSplits(objects, sampleRays);
+                cout << "finished" << endl;
+        }
+
+        ExportVspBspPvs(objects, sampleRays);
+}
+
+
+void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
+                                                                                  const RayContainer &sampleRays)
+{
+        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
+
+        if (exporter) 
+        {       
+                Material m; 
+                m.mDiffuseColor = RgbColor(1, 0, 0);
+                exporter->SetForcedMaterial(m);
+                exporter->SetWireframe();
+                // TODO
+                //exporter->ExportBspSplits(*mVspBspTree, true);
+
+                // take forced material, else big scenes cannot be viewed
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+                exporter->SetFilled();
+
+                exporter->ResetForcedMaterial();
+                
+                // export rays
+                if (0)
+                {
+                        RayContainer outRays;
+                
+                        int raysSize = min((int)sampleRays.size(), mVisualizationSamples);
+
+                        for (int i = 0; i < raysSize; ++ i)
+                        {
+                                // only rays piercing geometry
+                                if (!sampleRays[i]->intersections.empty())
+                                        outRays.push_back(sampleRays[i]);
+                        }
+                        
+                        // export rays 
+                        exporter->ExportRays(outRays, 1000, RgbColor(1, 1, 0));
+                }
+
+                if (0)
+                        exporter->ExportGeometry(objects);
+
+                delete exporter;
+        }
+}
+
+void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
+                                                                                  const RayContainer &sampleRays)
+{
+        const int leafOut = 10;
+        
+        ViewCell::NewMail();
+
+        //-- some rays for output
+        const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
+        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
+        vector<Ray *> vcRays[leafOut];
+
+        if (0)
+        {
+                //-- some random view cells and rays for output
+                vector<VspBspLeaf *> vspBspLeaves;
+
+                for (int i = 0; i < leafOut; ++ i)
+                        vspBspLeaves.push_back(mVspBspTree->GetRandomLeaf());   
+                
+                for (int i = 0; i < (int)vspBspLeaves.size(); ++ i)
+                {
+                        cout << "creating output for view cell " << i << " ... ";
+                        // check whether we can add the current ray to the output rays
+                        for (int k = 0; k < raysOut; ++ k) 
+                        {
+                                Ray *ray = sampleRays[k];
+
+                                for     (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
+                                {
+                                        BspLeaf *leaf = ray->bspIntersections[j].mLeaf;
+
+                                        if (vspBspLeaves[i]->GetViewCell() == leaf->GetViewCell()) 
+                                        {
+                                                vcRays[i].push_back(ray);
+                                        }
+                                }
+                        }
+
+                        Intersectable::NewMail();
+
+                        BspViewCell *vc = dynamic_cast<BspViewCell *>
+                                (vspBspLeaves[i]->GetViewCell());
+
+                        //bspLeaves[j]->Mail();
+                        char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
+
+                        Exporter *exporter = Exporter::GetExporter(s);
+                        exporter->SetFilled();
+
+                        ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin();
+
+                        exporter->SetWireframe();
+                        //exporter->SetFilled();
+
+                        Material m;//= RandomMaterial();
+                        m.mDiffuseColor = RgbColor(0, 1, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        if (vc->GetMesh())
+                                exporter->ExportViewCell(vc);
+                        else
+                        {
+                                PolygonContainer cell;
+                                // export view cell geometry
+                                mVspBspTree->ConstructGeometry(vc, cell);
+                                exporter->ExportPolygons(cell);
+                                CLEAR_CONTAINER(cell);
+                        }
+
+                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
+                                        << ", piercing rays=" << (int)vcRays[i].size() << endl;
+
+                        // export rays piercing this view cell
+                        exporter->ExportRays(vcRays[i], 1000, RgbColor(0, 1, 0));
+
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        // exporter->SetWireframe();
+                        exporter->SetFilled();
+
+                        // output PVS of view cell
+                        for (; it != vc->GetPvs().mEntries.end(); ++ it) 
+                        {
+                                Intersectable *intersect = (*it).first;
+                                if (!intersect->Mailed())
+                                {
+                                        exporter->ExportIntersectable(intersect);
+                                        intersect->Mail();
+                                }                       
+                        }
+                                
+                        // output rest of the objects
+                        if (0)
+                        {
+                                Material m;//= RandomMaterial();
+                                m.mDiffuseColor = RgbColor(0, 0, 1);
+                                exporter->SetForcedMaterial(m);
+
+                                for (int j = 0; j < objects.size(); ++ j)
+                                        if (!objects[j]->Mailed())
+                                        {
+                                                exporter->SetForcedMaterial(m);
+                                                exporter->ExportIntersectable(objects[j]);
+                                                objects[j]->Mail();
+                                        }
+                        }
+                        DEL_PTR(exporter);
+                        cout << "finished" << endl;
+                }
+        }
+        else
+        {
+                ViewCellContainer viewCells;
+
+                mVspBspTree->CollectViewCells(viewCells);
+                stable_sort(viewCells.begin(), viewCells.end(), vc_gt);
+
+                int limit = min(leafOut, (int)viewCells.size()); 
+                
+                for (int i = 0; i < limit; ++ i)
+                {
+                        cout << "creating output for view cell " << i << " ... ";
+                        
+            Intersectable::NewMail();
+                        BspViewCell *vc = dynamic_cast<BspViewCell *>(viewCells[i]);
+
+                        cout << "creating output for view cell " << i << " ... ";
+                        // check whether we can add the current ray to the output rays
+                        for (int k = 0; k < raysOut; ++ k) 
+                        {
+                                Ray *ray = sampleRays[k];
+
+                                for     (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
+                                {
+                                        VspBspLeaf *leaf; // TODO = ray->bspIntersections[j].mLeaf;
+
+                                        if (vc == leaf->GetViewCell()) 
+                                        {
+                                                vcRays[i].push_back(ray);
+                                        }
+                                }
+                        }
+
+                        //bspLeaves[j]->Mail();
+                        char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
+
+                        Exporter *exporter = Exporter::GetExporter(s);
+                        
+                        exporter->SetWireframe();
+
+                        Material m;//= RandomMaterial();
+                        m.mDiffuseColor = RgbColor(0, 1, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        if (vc->GetMesh())
+                                exporter->ExportViewCell(vc);
+                        else
+                        {
+                                PolygonContainer cell;
+                                // export view cell
+                                mVspBspTree->ConstructGeometry(vc, cell);
+                                exporter->ExportPolygons(cell);
+                                CLEAR_CONTAINER(cell);
+                        }
+
+                        
+                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
+                                        << ", piercing rays=" << (int)vcRays[i].size() << endl;
+
+                        
+                        // export rays piercing this view cell
+                        exporter->ExportRays(vcRays[i], 1000, RgbColor(0, 1, 0));
+        
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        ViewCellPvsMap::const_iterator it,
+                                it_end = vc->GetPvs().mEntries.end();
+
+                        // output PVS of view cell
+                        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
+                        {
+                                Intersectable *intersect = (*it).first;
+
+                                if (!intersect->Mailed())
+                                {
+                                        Material m = RandomMaterial();
+                        
+                                        exporter->SetForcedMaterial(m);
+
+                                        exporter->ExportIntersectable(intersect);
+                                        intersect->Mail();
+                                }                       
+                        }
+                                
+                        DEL_PTR(exporter);
+                        cout << "finished" << endl;
+                }
+        }
+}
+
+
+bool VspBspViewCellsManager::MergeVspBspLeafViewCells(VspBspLeaf *front, 
+                                                                                                          VspBspLeaf *back) const
+{
+        BspViewCell *viewCell = 
+                dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(), 
+                                                                                                   *back->GetViewCell()));
+        
+        if (!viewCell)
+                return false;
+
+        // change view cells of all leaves associated with the
+        // previous view cells
+
+        BspViewCell *fVc = front->GetViewCell();
+        BspViewCell *bVc = back->GetViewCell();
+
+        // TODO
+        /*vector<VspBspLeaf *> fLeaves = fVc->mBspLeaves;
+        vector<VspBspLeaf *> bLeaves = bVc->mBspLeaves;
+
+        vector<VspBspLeaf *>::const_iterator it;
+        
+        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
+        {
+                (*it)->SetViewCell(viewCell);
+                viewCell->mBspLeaves.push_back(*it);
+        }
+        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
+        {
+                (*it)->SetViewCell(viewCell);
+                viewCell->mBspLeaves.push_back(*it);
+        }
+        
+        DEL_PTR(fVc);
+        DEL_PTR(bVc);
+*/
+        return true;
+}
+
+bool VspBspViewCellsManager::ShouldMerge(VspBspLeaf *front, VspBspLeaf *back) const
+{
+        ViewCell *fvc = front->GetViewCell();
+        ViewCell *bvc = back->GetViewCell();
+
+        if ((fvc == mVspBspTree->GetRootCell()) || 
+                (bvc == mVspBspTree->GetRootCell()) || 
+                (fvc == bvc))
+                return false;
+
+        int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
+
+        if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
+        {
+                if ((fvc->GetPvs().GetSize() < mMinPvs) ||      
+                        (bvc->GetPvs().GetSize() < mMinPvs) ||
+                        ((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
+                {
+                        return true;
+                }
+        }
+        
+        return false;
+}
+

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -20 +20 @@
 class VspKdTree;
 class AxisAlignedBox3;
+class VspBspLeaf;
+
 /**
         Manages different higher order operations on the view cells.
@@ -316 +318 @@
 
 
+
+/**
+        Manages different higher order operations on the view cells.
+*/
+class VspBspViewCellsManager: public ViewCellsManager
+{
+
+public:
+
+        VspBspViewCellsManager(VspBspTree *tree, int constructionSamples);
+
+        int Construct(const ObjectContainer &objects, 
+                                  const VssRayContainer &rays,
+                                  AxisAlignedBox3 *sceneBbox);
+
+        int ComputeSampleContributions(Ray &ray, const bool castRay = false);
+
+        int PostProcess(const ObjectContainer &objects, 
+                                        const RayContainer &rays);
+
+        void Visualize(const ObjectContainer &objects,
+                                   const RayContainer &sampleRays);
+
+        int GetType() const;
+        
+        ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;
+
+        bool ViewCellsConstructed() const;
+
+protected:
+
+        /** Merges view cells front and back leaf view cell.
+        */
+        bool MergeVspBspLeafViewCells(VspBspLeaf *front, VspBspLeaf *back) const;
+
+        /** Returns true if front and back leaf should be merged.
+        */
+        bool ShouldMerge(VspBspLeaf *front, VspBspLeaf *back) const;
+
+        /// the view space partition BSP tree.
+        VspBspTree *mVspBspTree;
+
+
+private:
+
+
+        /** Exports visualization of the BSP splits.
+        */
+        void ExportSplits(const ObjectContainer &objects, const RayContainer &sampleRays);
+
+        /** Exports visualization of the BSP PVS.
+        */
+        void ExportBspPvs(const ObjectContainer &objects, const RayContainer &sampleRays);
+
+};
+
 #endif

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -218 +218 @@
 /****************************************************************/
 
-VspBspTree::VspBspTree(BspViewCell *viewCell): 
-mRootCell(viewCell), 
-mRoot(NULL), 
-mStoreLeavesWithRays(false),
-mPvsUseLen(true)
-{
+VspBspTree::VspBspTree(): 
+mRoot(NULL),
+mPvsUseArea(true)
+{
+        mRootCell = new BspViewCell();
+
         Randomize(); // initialise random generator for heuristics
 
@@ -349 +349 @@
 {
         DEL_PTR(mRoot);
+        DEL_PTR(mRootCell);
 }
 
@@ -485 +486 @@
 
         VspBspTraversalData tData(mRoot, polys, 0, mRootCell, rays, 
-                                                   ComputePvsSize(*rays));
+                                                   ComputePvsSize(*rays), cell->GetArea(), cell);
 
         tStack.push(tData);
@@ -515 +516 @@
                 (((int)data.mRays->size() <= mTermMinRays) ||
                  (data.mPvs <= mTermMinPvs) ||
+                 (data.mArea <= mTermMinArea) ||
                  (data.mDepth >= mTermMaxDepth) ||
                  (data.GetAvgRayContribution() < mTermMaxRayContribution));
@@ -547 +549 @@
                 DEL_PTR(tData.mPolygons);
                 DEL_PTR(tData.mRays);
-                //DEL_PTR(tData.mGeometry);
+                DEL_PTR(tData.mGeometry);
                 
                 return leaf;
@@ -556 +558 @@
         
         VspBspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 
-                                                                new RayInfoContainer(), 0);
+                                                                new RayInfoContainer(), 0, 0, new VspBspNodeGeometry());
         VspBspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 
-                                                           new RayInfoContainer(), 0);
+                                                           new RayInfoContainer(), 0, 0, new VspBspNodeGeometry());
 
         // create new interior node and two leaf nodes
@@ -582 +584 @@
         DEL_PTR(tData.mPolygons);
         DEL_PTR(tData.mRays);
-        //DEL_PTR(tData.mGeometry);             
+        DEL_PTR(tData.mGeometry);               
 
         return interior;
@@ -615 +617 @@
         frontData.mPvs = ComputePvsSize(*frontData.mRays);
         backData.mPvs = ComputePvsSize(*backData.mRays);
+
+        // split geometry and compute area
+        if (1)
+        {
+                tData.mGeometry->SplitGeometry(*frontData.mGeometry, 
+                                                                           *backData.mGeometry, 
+                                                                           *this, 
+                                                                           interior->mPlane);
+        
+                
+                frontData.mArea = frontData.mGeometry->GetArea();
+                backData.mArea = backData.mGeometry->GetArea();
+        }
 
         // compute accumulated ray length
@@ -991 +1006 @@
         float pBack = 0;
 
+        const bool pvsUseLen = false;
+
         if (mSplitPlaneStrategy & PVS)
+        {
                 // create unique ids for pvs heuristics
                 GenerateUniqueIdsForPvs();
         
+                if (mPvsUseArea) // use front and back cell areas to approximate volume
+                {       
+                        // construct child geometry with regard to the candidate split plane
+                        VspBspNodeGeometry frontCell;
+                        VspBspNodeGeometry backCell;
+
+                        data.mGeometry->SplitGeometry(frontCell, backCell, *this, candidatePlane);
+                
+                        pFront = frontCell.GetArea();
+                        pBack = backCell.GetArea();
+
+                        pOverall = data.mArea;
+                }
+        }
                         
         RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
@@ -1026 +1058 @@
                         AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
                         
-                        float len = 1;
-
-                        if (mPvsUseLen) // use front and back cell areas to approximate volume
-                                len = (*rit).SqrSegmentLength();
+                        // use number or length of rays to approximate volume
+                        if (!mPvsUseArea)
+                        {
+                                float len = 1;
+
+                                if (pvsUseLen) // use length of rays
+                                        len = (*rit).SqrSegmentLength();
                         
-                        pOverall += len;
-
-                        // use length of rays to approximate volume
-                        if (cf == 1)
-                                pFront += len;
-                        if (cf == -1)
-                                pBack += len;
-                        if (cf == 0)
-                        {
-                                if (mPvsUseLen)
+                                pOverall += len;
+
+                                if (cf == 1)
+                                        pFront += len;
+                                if (cf == -1)
+                                        pBack += len;
+                                if (cf == 0)
                                 {
-                                        float newLen = len * 
-                                                ((*rit).GetMaxT() - (*rit).mRay->mT) / 
-                                                ((*rit).GetMaxT() - (*rit).GetMinT());
-
-                                
-                                        if (candidatePlane.Side((*rit).ExtrapOrigin()) <= 0)
+                                        // use length of rays to approximate volume
+                                        if (pvsUseLen) 
                                         {
-                                                pBack += newLen;
-                                                pFront += len - newLen;
+                                                float newLen = len * 
+                                                        ((*rit).GetMaxT() - (*rit).mRay->mT) / 
+                                                        ((*rit).GetMaxT() - (*rit).GetMinT());
+                
+                                                if (candidatePlane.Side((*rit).ExtrapOrigin()) <= 0)
+                                                {
+                                                        pBack += newLen;
+                                                        pFront += len - newLen;
+                                                }
+                                                else
+                                                {
+                                                        pFront += newLen;
+                                                        pBack += len - newLen;
+                                                }
                                         }
                                         else
                                         {
-                                                pFront += newLen;
-                                                pBack += len - newLen;
+                                                ++ pFront;
+                                                ++ pBack;
                                         }
                                 }
-                                else
-                                {
-                                        ++ pFront;
-                                        ++ pBack;
-                                }
                         }
                 }
@@ -1083 +1118 @@
                 // give penalty to unbalanced split
                 if (0)
-                if (((pFront * 0.2 + Limits::Small) > pBack) || (pFront < (pBack * 0.2 + Limits::Small)))
+                if (((pFront * 0.2 + Limits::Small) > pBack) || 
+                        (pFront < (pBack * 0.2 + Limits::Small)))
                         val += 0.5;
         }
@@ -1199 +1235 @@
                 ++ mStat.maxRayContribNodes;
         
+        if (data.mGeometry->GetArea() <= mTermMinArea) 
+                ++ mStat.minAreaNodes;
 
 #ifdef _DEBUG
@@ -1984 +2022 @@
         app << "===== END OF VspBspViewCells statistics ==========\n";
 }
+
+BspViewCell *VspBspTree::GetRootCell() const
+{
+        return mRootCell;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -349 +349 @@
                 /// rays piercing this node
                 RayInfoContainer *mRays;
+                /// area of current node
+                float mArea;
+                /// geometry of current node induced by split planes
+                VspBspNodeGeometry *mGeometry;
 
                 /// pvs size
@@ -367 +371 @@
                 mViewCell(NULL),
                 mRays(NULL),
-                mPvs(0)
+                mPvs(0),
+                mArea(0.0),
+                mGeometry(NULL)
                 {}
                 
@@ -375 +381 @@
                                                  ViewCell *viewCell,
                                                  RayInfoContainer *rays,
-                                                 int pvs): 
+                                                 int pvs,
+                                                 float area,
+                                                 VspBspNodeGeometry *cell): 
                 mNode(node), 
                 mPolygons(polys), 
@@ -381 +389 @@
                 mViewCell(viewCell),
                 mRays(rays),
-                mPvs(pvs)
+                mPvs(pvs),
+                mArea(area),
+                mGeometry(cell)
                 {}
     };
@@ -388 +398 @@
 
         /** Default constructor creating an empty tree.
-                @param viewCell view cell corresponding to unbounded space
         */ 
-        VspBspTree(BspViewCell *viewCell);
+        VspBspTree();
 
         ~VspBspTree();
@@ -478 +487 @@
         void EvaluateViewCellsStats(VspBspViewCellsStatistics &stat) const;
 
+
+        /** Returns view cell corresponding to unbounded space.
+        */
+        BspViewCell *GetRootCell() const;
 
 protected:
@@ -731 +744 @@
         float mCtDivCi;
 
-        /// if intersected leaves should be stored with a sample
-        bool mStoreLeavesWithRays;
-
         /// axis aligned split criteria
         float mAaCtDivCi;
@@ -752 +762 @@
 
         /// if area or accumulated ray lenght should be used for PVS heuristics
-        bool mPvsUseLen;
+        bool mPvsUseArea;
 
 private: