Changeset 390 for trunk/VUT

Timestamp:

11/08/05 19:00:49 (19 years ago)

Author:

mattausch

Message:

changed bsp splitplane choosing functions

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/Preprocessor.vcproj (modified) (4 diffs)
• src/Environment.cpp (modified) (3 diffs)
• src/Mesh.h (modified) (1 diff)
• src/Polygon3.cpp (modified) (1 diff)
• src/SamplingPreprocessor.cpp (modified) (7 diffs)
• src/SamplingPreprocessor.h (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (46 diffs)
• src/ViewCellBsp.h (modified) (21 diffs)
• src/X3dExporter.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj

@@ -20 +20 @@
                                 Name="VCCLCompilerTool"
                                 Optimization="0"
-                                AdditionalIncludeDirectories="..\include"
+                                AdditionalIncludeDirectories="..\support;..\support\devil\include;..\support\zlib\include;..\include"
                                 PreprocessorDefinitions="WIN32;_DEBUG;_LIB"
                                 MinimalRebuild="TRUE"
@@ -62 +62 @@
                         <Tool
                                 Name="VCCLCompilerTool"
-                                AdditionalIncludeDirectories="..\support;..\support\devil\include;..\support\zlib\include;&quot;$(QTDIR)\include&quot;;&quot;$(QTDIR)\include\Qt&quot;;..\include"
+                                AdditionalIncludeDirectories="..\support;..\support\devil\include;..\support\zlib\include;..\include"
                                 PreprocessorDefinitions="WIN32;NDEBUG;_LIB;"
                                 RuntimeLibrary="2"
@@ -285 +285 @@
                         </File>
                         <File
-                                RelativePath="..\src\VisibilityVector3.h">
-                        </File>
-                        <File
                                 RelativePath="..\src\VssPreprocessor.cpp">
                         </File>
@@ -365 +362 @@
                         </File>
                 </Filter>
-                <File
-                        RelativePath=".\VTune\Preprocessor.vpj">
-                </File>
         </Files>
         <Globals>

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1215 +1215 @@
                  "5");
 
+  RegisterOption("BspTree.Termination.minPvs",
+                 optInt,
+                 "-bsp_term_min_pvs=",
+                 "20");
+
    RegisterOption("BspTree.Termination.maxRays",
                  optInt,
@@ -1276 +1281 @@
 
   
-  RegisterOption("Bsptree.Visualization.samples",
+  RegisterOption("BspTree.Visualization.samples",
           optInt,
           "-bsp_visualization_samples=",
@@ -1285 +1290 @@
           "-bsp_visualization.exportSplits",
           "false");
-
-  RegisterOption("BspTree.Visualization.storePolys",
-                 optBool,
-                 "-bsp_visualization_store_polys=",
-                 "false");
 
   RegisterOption("Preprocessor.type",

trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.h

@@ -153 +153 @@
                 
         virtual ostream &Describe(ostream &s) {
-                return s<<"Mesh #vertices="<<mVertices.size()<<" #faces="<<mFaces.size();
+                return s<<"Mesh #vertices="<<(int)mVertices.size()<<" #faces="<<(int)mFaces.size();
         }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -439 +439 @@
 
         for (pit = cell.begin(); pit != cell.end(); ++ pit)
+        {
                 area += (*pit)->GetArea();
-
+        }
         return area;
 }

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -15 +15 @@
   environment->GetIntValue("BspTree.Construction.samples", mBspConstructionSamples);
   environment->GetIntValue("ViewCells.PostProcessing.samples", mPostProcessSamples);
-  environment->GetIntValue("BspTree.visualizationSamples", mVisualizationSamples);
+  environment->GetIntValue("BspTree.Visualization.samples", mVisualizationSamples);
 
   mKdPvsDepth = 100;
@@ -728 +728 @@
         }
         // save rays for post processing
-        else if ((int)mSampleRays.size() < mPostProcessSamples) ||
-                        (((int)mSampleRays.size() < mVisualizationSamples))
+        else if (((int)mSampleRays.size() < mPostProcessSamples) ||
+                         ((int)mSampleRays.size() < mVisualizationSamples))
         {
                 mSampleRays.push_back(new Ray(ray));
@@ -747 +747 @@
         for (int i = 0; i < limit; ++i)
         {  
-                Ray *ray = mSamplesRays[i];
+                Ray *ray = mSampleRays[i];
 
                 // traverse leaves stored in the rays and compare and merge consecutive
@@ -842 +842 @@
         //-- some rays for output
         const int raysOut = min((int)mSampleRays.size(), mVisualizationSamples);
+        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
         vector<Ray *> vcRays[leafOut];
 
@@ -882 +883 @@
                         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
+                                mBspTree->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();
+
+                        // 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;
+
+                mBspTree->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 = mSampleRays[k];
+
+                                for     (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
+                                {
+                                        BspLeaf *leaf = 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->SetFilled();
+
+                        ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin();
+
+                        exporter->SetFilled();//Wireframe();
 
                         Material m;//= RandomMaterial();
@@ -899 +1000 @@
                         }
 
-                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-                                        << ", piercing rays=" << (int)vcRays[i].size() << endl;
-
+                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() << endl;
+
+                        
                         // export rays piercing this view cell
-                        exporter->ExportRays(vcRays[i], 1000, RgbColor(0, 1, 0));
+                        exporter->ExportRays(vcRays[i], 10000, RgbColor(0, 1, 0));
 
                         m.mDiffuseColor = RgbColor(1, 0, 0);
@@ -919 +1020 @@
                         }
                                 
-                        // 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;
-
-                mBspTree->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 = mSampleRays[k];
-
-                                for     (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
-                                {
-                                        BspLeaf *leaf = 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->SetFilled();
-
-                        ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin();
-
-                        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
-                                mBspTree->ConstructGeometry(vc, cell);
-                                exporter->ExportPolygons(cell);
-                                CLEAR_CONTAINER(cell);
-                        }
-
-                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() << endl;
-
-                        
-                        // export rays piercing this view cell
-                        exporter->ExportRays(vcRays[i], 10000, RgbColor(0, 1, 0));
-
-                        m.mDiffuseColor = RgbColor(1, 0, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        // output PVS of view cell
-                        for (; it != vc->GetPvs().mEntries.end(); ++ it) 
-                        {
-                                Intersectable *intersect = (*it).first;
-                                if (!intersect->Mailed())
-                                {
-                                        exporter->ExportIntersectable(intersect);
-                                        intersect->Mail();
-                                }                       
-                        }
-                                
                         DEL_PTR(exporter);
                         cout << "finished" << endl;

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.h

@@ -30 +30 @@
   int mBspConstructionSamples;
   int mPostProcessSamples;
-
+  int mVisualizationSamples;
 
   void

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -15 +15 @@
 
 int BspTree::sTermMaxPolygons = 10;
+int BspTree::sTermMinPvs = 20;
 int BspTree::sTermMaxDepth = 20;
 int BspTree::sMaxPolyCandidates = 10;
@@ -46 +47 @@
 float BspTree::sPvsFactor = 1.0f;
 
-bool BspTree::sStoreSplitPolys = false;
-
 int BspNode::mailID = 1;
 
@@ -73 +72 @@
 
 BspNode::BspNode(): 
-mParent(NULL), mPolygons(NULL)
+mParent(NULL)
 {}
 
 BspNode::BspNode(BspInterior *parent): 
-mParent(parent), mPolygons(NULL)
+mParent(parent)
 {}
 
-BspNode::~BspNode()
-{
-        if (mPolygons)
-        {
-                CLEAR_CONTAINER(*mPolygons);
-                DEL_PTR(mPolygons);
-        }
-}
 
 bool BspNode::IsRoot() const 
@@ -103 +94 @@
         mParent = parent;
 }
-
-PolygonContainer *BspNode::GetPolygons()
-{
-        if (!mPolygons)
-                mPolygons = new PolygonContainer();
-
-        return mPolygons;
-}
-
-void BspNode::ProcessPolygons(PolygonContainer *polys, bool storePolys)
-{
-        if (storePolys)
-        {
-                while (!polys->empty())
-                {
-                        GetPolygons()->push_back(polys->back());
-                        polys->pop_back();
-                }
-        }
-        else CLEAR_CONTAINER(*polys);
-}
-
 
 /****************************************************************/
@@ -169 +138 @@
 }
 
-void BspInterior::ProcessPolygon(Polygon3 **poly, const bool storePolys)
-{
-        if (storePolys) 
-                GetPolygons()->push_back(*poly);
-        else
-                DEL_PTR(*poly);
-}
-
 int BspInterior::SplitPolygons(PolygonContainer &polys, 
                                                            PolygonContainer &frontPolys, 
                                                            PolygonContainer &backPolys, 
-                                                           PolygonContainer &coincident,
-                                                           const bool storePolys)
+                                                           PolygonContainer &coincident)
 {
         Polygon3 *splitPoly = NULL;
@@ -246 +206 @@
                                 Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
 #endif
-                                ProcessPolygon(&poly, storePolys);                      
+                                DEL_PTR(poly);                  
                                 break;
                         default:
@@ -449 +409 @@
                 mRoot = new BspLeaf();
 
-        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer()));
+        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0, 
+                                                                 mBox.SurfaceArea(), new BspNodeGeometry()));
 
         while (!tStack.empty())
@@ -471 +432 @@
                 
                                 // split viewcell polygons with respect to split plane
-                                splits += interior->SplitPolygons(*tData.mPolygons, 
+                                splits += interior->SplitPolygons(*tData.mPolygons,
                                                                                                   *frontPolys, 
                                                                                                   *backPolys,
-                                                                                                  coincident,
-                                                                                                  sStoreSplitPolys);
+                                                                                                  coincident);
                                 
                                 // extract view cells associated with the split polygons
                                 ViewCell *frontViewCell = mRootCell;
                                 ViewCell *backViewCell = mRootCell;
-        
+                        
+                                BspTraversalData frontData(interior->GetFront(), 
+                                                                                   frontPolys, 
+                                                                                   tData.mDepth + 1,
+                                                                                   mRootCell,   
+                                                                                   tData.mRays,
+                                                                                   tData.mPvs,
+                                                                                   mBox.SurfaceArea(),
+                                                                                   new BspNodeGeometry());
+
+                                BspTraversalData backData(interior->GetBack(), 
+                                                                                  backPolys,
+                                                                                  tData.mDepth + 1,
+                                                                                  mRootCell,    
+                                                                                  tData.mRays,
+                                                                                  tData.mPvs,
+                                                                                  mBox.SurfaceArea(),
+                                                                                  new BspNodeGeometry());
+
                                 if (!mGenerateViewCells)
                                 {
-                                        ExtractViewCells(&backViewCell,
-                                                                         &frontViewCell,
-                                                                         coincident, 
-                                                                         interior->mPlane, 
-                                                                         frontPolys->empty(), 
-                                                                         backPolys->empty());
+                                        ExtractViewCells(frontData,
+                                                                         backData,
+                                                                         coincident,
+                                                                         interior->mPlane);
                                 }
 
                                 // don't need coincident polygons anymore
-                                interior->ProcessPolygons(&coincident, sStoreSplitPolys);
+                                CLEAR_CONTAINER(coincident);
 
                                 mStat.splits += splits;
 
                                 // push the children on the stack
-                                tStack.push(BspTraversalData(interior->GetFront(), 
-                                                                                         frontPolys, 
-                                                                                         tData.mDepth + 1, 
-                                                                                         frontViewCell,
-                                                                                         tData.mRays));
-
-                                tStack.push(BspTraversalData(interior->GetBack(), 
-                                                                                         backPolys, 
-                                                                                         tData.mDepth + 1, 
-                                                                                         backViewCell,
-                                                                                         new BoundedRayContainer()));
+                                tStack.push(frontData);
+                                tStack.push(backData);
                         }
 
@@ -704 +671 @@
         mRoot = new BspLeaf();
 
-        BspTraversalData tData(mRoot, polys, 0, mRootCell, rays);
+        BspNodeGeometry *cell = new BspNodeGeometry();
+        ConstructGeometry(mRoot, *cell);
+
+        BspTraversalData tData(mRoot, polys, 0, mRootCell, rays, 
+                                                   ComputePvsSize(*rays), cell->GetArea(), cell);
+
         tStack.push(tData);
 
@@ -728 +700 @@
         //-- terminate traversal  
         if (((int)tData.mPolygons->size() <= sTermMaxPolygons) || 
-                ((int)tData.mRays->size() <= sTermMaxRays) ||
-                (tData.mDepth >= sTermMaxDepth))
+                ((int)tData.mRays->size() <= sTermMaxRays)         ||
+                ((int)tData.mPvs <= sTermMinPvs)            ||
+                 (tData.mDepth >= sTermMaxDepth))
                 
         {
@@ -754 +727 @@
                 //-- clean up
                 
-                // remaining polygons are discarded or added to node
-                leaf->ProcessPolygons(tData.mPolygons, sStoreSplitPolys);
-                DEL_PTR(tData.mPolygons);
+                // discard polygons
+                CLEAR_CONTAINER(*tData.mPolygons);
                 // discard rays
                 CLEAR_CONTAINER(*tData.mRays);
+
+                DEL_PTR(tData.mPolygons);
                 DEL_PTR(tData.mRays);
-
+                DEL_PTR(tData.mCell);
+                
                 return leaf;
         }
@@ -774 +749 @@
         BoundedRayContainer *backRays = new BoundedRayContainer();
         
+        BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 
+                                                                new BoundedRayContainer(), 0, NULL, 0);
+        BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 
+                                                           new BoundedRayContainer(), 0, NULL, 0);
+
         // create new interior node and two leaf nodes
-        BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode), 
-                                                                                  *tData.mPolygons,
-                                                                                  *frontPolys,
-                                                                                  *backPolys,
-                                                                                  coincident,
-                                                                                  *tData.mRays,
-                                                                                  *frontRays,
-                                                                                  *backRays);
-        ViewCell *frontViewCell = mRootCell;
-        ViewCell *backViewCell = mRootCell;
-
-        
+        BspInterior *interior = SubdivideNode(tData,
+                                                                                  tFrontData,
+                                                                                  tBackData,
+                                                                                  coincident);
+
 #ifdef _DEBUG   
         if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
@@ -798 +771 @@
         if (!mGenerateViewCells)
         {
-                ExtractViewCells(&backViewCell,
-                                                 &frontViewCell,
+                ExtractViewCells(tFrontData,
+                                                 tBackData,
                                                  coincident,
-                                                 interior->mPlane,
-                                                 backPolys->empty(),
-                                                 frontPolys->empty());
-        }
-        
-        // don't need coincident polygons anymore
-        interior->ProcessPolygons(&coincident, sStoreSplitPolys);
+                                                 interior->mPlane);
+                                                 
+        }
+
+        // don't need coincident polygons anymory
+        CLEAR_CONTAINER(coincident);
 
         // push the children on the stack
-        tStack.push(BspTraversalData(interior->GetBack(), 
-                                                                 backPolys, 
-                                                                 tData.mDepth + 1, 
-                                                                 backViewCell, 
-                                                                 backRays));
-
-        tStack.push(BspTraversalData(interior->GetFront(), 
-                                                                 frontPolys, 
-                                                                 tData.mDepth + 1, 
-                                                                 frontViewCell, 
-                                                                 frontRays));
+        tStack.push(tFrontData);
+        tStack.push(tBackData);
 
         // cleanup
@@ -826 +789 @@
         DEL_PTR(tData.mPolygons);
         DEL_PTR(tData.mRays);
+        DEL_PTR(tData.mCell);           
 
         return interior;
 }
 
-void BspTree::ExtractViewCells(ViewCell **backViewCell, 
-                                                           ViewCell **frontViewCell,
+void BspTree::ExtractViewCells(BspTraversalData &frontData,
+                                                           BspTraversalData &backData, 
                                                            const PolygonContainer &coincident,
-                                                           const Plane3 splitPlane, 
-                                                           const bool extractBack,
-                                                           const bool extractFront) const
-{
-        bool foundFront = !extractFront, foundBack = !extractBack;
+                                                           const Plane3 splitPlane) const
+{
+        // if not empty, tree is further subdivided => don't have to find view cell
+        bool foundFront = !frontData.mPolygons->empty();
+        bool foundBack = !frontData.mPolygons->empty();
 
         PolygonContainer::const_iterator it = 
@@ -847 +811 @@
                 if (DotProd((*it)->GetNormal(), splitPlane.mNormal) > 0)
                 {
-                        *backViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
+                        backData.mViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
                         foundBack = true;
                 }
                 else
                 {
-                        *frontViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
+                        frontData.mViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
                         foundFront = true;
                 }
         }
-        //if (extractFront && foundFront)       Debug << "front view cell: " << *frontViewCell << endl;
-        //if (extractBack && foundBack) Debug << "back view cell: " << *backViewCell << endl;
-}
-
-BspInterior *BspTree::SubdivideNode(BspLeaf *leaf, 
-                                                                        PolygonContainer &polys,
-                                                                        PolygonContainer &frontPolys,
-                                                                        PolygonContainer &backPolys,
-                                                                        PolygonContainer &coincident,
-                                                                        BoundedRayContainer &rays,
-                                                                        BoundedRayContainer &frontRays,
-                                                                        BoundedRayContainer &backRays)
+}
+
+BspInterior *BspTree::SubdivideNode(BspTraversalData &tData,
+                                                                        BspTraversalData &frontData,
+                                                                        BspTraversalData &backData,
+                                                                        PolygonContainer &coincident)
 {
         mStat.nodes += 2;
         
+        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
         // select subdivision plane
         BspInterior *interior = 
-                new BspInterior(SelectPlane(leaf, polys, rays)); 
+                new BspInterior(SelectPlane(leaf, tData, frontData, backData)); 
 
 #ifdef _DEBUG
@@ -880 +839 @@
         
         // subdivide rays into front and back rays
-        SplitRays(interior->mPlane, rays, frontRays, backRays);
+        SplitRays(interior->mPlane, *tData.mRays, *frontData.mRays, *backData.mRays);
         
         // subdivide polygons with plane
-        mStat.splits += interior->SplitPolygons(polys, 
-                                                    frontPolys, 
-                                                                                        backPolys, 
-                                                                                        coincident, 
-                                                                                        sStoreSplitPolys);
+        mStat.splits += interior->SplitPolygons(*tData.mPolygons, 
+                                                    *frontData.mPolygons, 
+                                                                                        *backData.mPolygons, 
+                                                                                        coincident);
 
         BspInterior *parent = leaf->GetParent();
@@ -904 +862 @@
         // and setup child links
         interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
+        
+        frontData.mNode = interior->mFront;
+        backData.mNode = interior->mBack;
         
         return interior;
@@ -1049 +1010 @@
 
 Plane3 BspTree::SelectPlane(BspLeaf *leaf, 
-                                                        PolygonContainer &polys, 
-                                                        const BoundedRayContainer &rays)
-{
-        if (polys.empty() && rays.empty())
+                                                        BspTraversalData &data,
+                                                        BspTraversalData &frontData,
+                                                        BspTraversalData &backData)
+{
+        if (data.mPolygons->empty() && data.mRays->empty())
         {
                 Debug << "Warning: No autopartition polygon candidate available\n";
@@ -1061 +1023 @@
         
                 // create bounding box of region
-                Polygon3::IncludeInBox(polys, box);
+                Polygon3::IncludeInBox(*data.mPolygons, box);
 
                 const int axis = box.Size().DrivingAxis();
@@ -1071 +1033 @@
         
         if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
-                ((int)polys.size() > sTermMaxPolysForAxisAligned) &&
-                ((int)rays.size() > sTermMaxRaysForAxisAligned) &&
+                ((int)data.mPolygons->size() > sTermMaxPolysForAxisAligned) &&
+                ((int)data.mRays->size() > sTermMaxRaysForAxisAligned) &&
                 ((sTermMaxObjectsForAxisAligned < 0) || 
-                  (Polygon3::ParentObjectsSize(polys) > sTermMaxObjectsForAxisAligned)))
+                  (Polygon3::ParentObjectsSize(*data.mPolygons) > sTermMaxObjectsForAxisAligned)))
         {
                 Plane3 plane;
-                if (SelectAxisAlignedPlane(plane, polys))
+                if (SelectAxisAlignedPlane(plane, *data.mPolygons))
                         return plane;
         }
@@ -1084 +1046 @@
         if (sSplitPlaneStrategy & RANDOM_POLYGON)
         {
-                return polys[Random((int)polys.size())]->GetSupportingPlane();
+                Polygon3 *nextPoly = (*data.mPolygons)[Random((int)data.mPolygons->size())];
+                return nextPoly->GetSupportingPlane();
         }
 
         // use heuristics to find appropriate plane
-        return SelectPlaneHeuristics(leaf, polys, rays, sMaxPolyCandidates, 
-                                                                 sMaxRayCandidates);
+        return SelectPlaneHeuristics(leaf, data, frontData, backData); 
 }
 
 Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf,
-                                                                          PolygonContainer &polys,
-                                                                          const BoundedRayContainer &rays,
-                                                                          const int maxPolyCandidates,
-                                                                          const int maxRayCandidates)
+                                                                          BspTraversalData &data,
+                                                                          BspTraversalData &frontData,
+                                                                          BspTraversalData &backData)
 {
         float lowestCost = MAX_FLOAT;
-        int bestPlaneIdx = 0;
-        
-        int limit = maxPolyCandidates > 0 ? 
-                Min((int)polys.size(), maxPolyCandidates) : (int)polys.size();
+        Plane3 bestPlane;
+        
+        int limit = sMaxPolyCandidates > 0 ? 
+                Min((int)data.mPolygons->size(), sMaxPolyCandidates) : (int)data.mPolygons->size();
         
         int candidateIdx = limit;
 
-        // only for pvs criterium
-        PolygonContainer cell;
-        vector<Plane3 *> planes;
-        vector<bool> sides;
-        int pvsSize = 0;
-
-        if (sSplitPlaneStrategy & PVS)
-        {
-                ConstructGeometry(leaf, cell);
-                ExtractSplitPlanes(leaf, planes, sides);
-                pvsSize = ComputePvsSize(rays);
-        }
-
         for (int i = 0; i < limit; ++ i)
         {
-                candidateIdx = GetNextCandidateIdx(candidateIdx, polys);
-                
+                candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons);
+                
+                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
                 // evaluate current candidate
                 const float candidateCost = 
-                        SplitPlaneCost(polys[candidateIdx]->GetSupportingPlane(), 
-                                                   polys, rays, cell, planes, sides, pvsSize);
-
-                //Debug << polys[candidateIdx] << endl;
+                        SplitPlaneCost(poly->GetSupportingPlane(), data, frontData, backData);
+
+                Debug << "cost: " << candidateCost << ", lowest: " << lowestCost << endl;
+
                 if (candidateCost < lowestCost)
                 {
-                        bestPlaneIdx = candidateIdx;
+                        bestPlane = poly->GetSupportingPlane();
                         lowestCost = candidateCost;
                 }
         }
         
-        //limit = maxRaysCandidates > 0 ? Min((int)rays.size(), maxRayCandidates) : (int)rays.size();
-        bool chooseFromRays = false;
-        int bestIdx[3];
-
-        for (int i = 0; i < maxRayCandidates; ++ i)
-        {
-                Vector3 pt[3];
-                int idx[3];
-
-                for (int j = 0; j < 3; j ++)
-                {
-                        idx[j] = Random((int)rays.size() * 2);
+        //limit = maxRaysCandidates > 0 ? Min((int)rays.size(), maxRayCandidates) : (int)rays.size();   
+        const BoundedRayContainer *rays = data.mRays;
+
+        for (int i = 0; i < sMaxRayCandidates; ++ i)
+        {
+                Plane3 plane;
+
+                if (1)
+                {
+                        Vector3 pt[3];
+                        int idx[3];
+                        
+                        for (int j = 0; j < 3; j ++)
+                        {
+                                idx[j] = Random((int)rays->size() * 2);
                                 
-                        if (idx[j] < (int)rays.size())
-                                pt[j] = rays[idx[j]]->mRay->Extrap(rays[idx[j]]->mMinT);
-                        else
-                        {
-                                idx[j] -= (int)rays.size();
-                                pt[j] = rays[idx[j]]->mRay->Extrap(rays[idx[j]]->mMaxT);
-                        }
-                                        
-                }
-
-                const float candidateCost =
-                        SplitPlaneCost(Plane3(pt[0], pt[1], pt[2]), 
-                                                   polys, rays, cell, planes, sides, pvsSize);
+                                BoundedRay *bRay = (*rays)[idx[j]];
+                                Ray *ray = bRay->mRay;
+
+                                if (idx[j] < (int)rays->size())
+                                        pt[j] = ray->Extrap(bRay->mMinT);
+                                else
+                                {
+                                        idx[j] -= (int)rays->size();
+                                        pt[j] = ray->Extrap(bRay->mMaxT);
+                                }
+                        }       
+                
+                        plane = Plane3(pt[0], pt[1], pt[2]);
+                }
+                else
+                {
+                        candidateIdx = Random((int)rays->size());
+                        BoundedRay *bRay = (*rays)[candidateIdx];
+
+                        Ray *ray = bRay->mRay;
+                                                
+                        const Vector3 minPt = ray->Extrap(bRay->mMinT);
+                        const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
+
+                        const Vector3 pt = (maxPt + minPt) * 0.5;
+
+                        const Vector3 normal = ray->GetDir();
+                        
+                        plane = Plane3(normal, pt);
+                }
+                
+                const float candidateCost = 
+                        SplitPlaneCost(plane, data, frontData, backData);
 
                 if (candidateCost < lowestCost)
                 {
-                        chooseFromRays = true;
-                        bestIdx[0] = idx[0]; bestIdx[1]= idx[1]; bestIdx[2] = idx[2];
+                        Debug << "choose ray plane: " << lowestCost << endl;
+                        bestPlane = plane;
                         
                         lowestCost = candidateCost;
                 }
-        }
-
-        CLEAR_CONTAINER(cell);
-
-        if (chooseFromRays)
-        {
-                Debug << "choose ray plane: " << lowestCost << endl;
-                return Plane3(rays[bestIdx[0]]->mRay->Extrap(rays[bestIdx[0]]->mMaxT),
-                                          rays[bestIdx[1]]->mRay->Extrap(rays[bestIdx[1]]->mMaxT),
-                                          rays[bestIdx[2]]->mRay->Extrap(rays[bestIdx[2]]->mMaxT));
+                else
+                        Debug << "ray cost: " << candidateCost << ", lowest: " << lowestCost << endl;
         }
 
         //Debug << "Plane lowest cost: " << lowestCost << endl;
-        return polys[bestPlaneIdx]->GetSupportingPlane();
+        return bestPlane;
 }
 
@@ -1337 +1301 @@
 float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
                                                           const BoundedRayContainer &rays,
-                                                          const float frontArea,
-                                                          const float backArea,
-                                                          const int pvsSize) const
+                                                          const int pvs,
+                                                          const float area,
+                                                          const BspNodeGeometry &cell, 
+                                                          BspTraversalData &frontData,
+                                                          BspTraversalData &backData) const
 {
         float val = 0;
@@ -1345 +1311 @@
         float sumBalancedRays = 0;
         float sumRaySplits = 0;
-        float frontPvs = 0;
-        float backPvs = 0;
-
-        float totalSize = 0;
-        
-        // create three unique ids for pvs heuristics
-        Intersectable::NewMail(); const int backId = ViewCell::sMailId;
-        Intersectable::NewMail(); const int frontId = ViewCell::sMailId;
-        Intersectable::NewMail(); const int frontAndBackId = ViewCell::sMailId;
-
-        int frontRays = 0;
-        int backRays = 0;
-                
+        
+        int backId = 0;
+        int frontId = 0;
+        int frontAndBackId = 0;
+
+        frontData.mPvs = 0;
+        backData.mPvs = 0;
+        frontData.mArea = 0;
+        backData.mArea = 0;
+
+        // probability that view point lies in child
+        float pOverall = 0;
+        float pFront = 0;
+        float pBack = 0;
+
+        if (sSplitPlaneStrategy & PVS)
+        {
+                // create three unique ids for pvs heuristics
+                Intersectable::NewMail(); backId = ViewCell::sMailId;
+                Intersectable::NewMail(); frontId = ViewCell::sMailId;
+                Intersectable::NewMail(); frontAndBackId = ViewCell::sMailId;
+
+                if (1) // use front and back cell areas to approximate volume
+                {
+                        //-- compute area
+                
+                        // construct child geometry with regard to the candidate split plane
+                        frontData.mCell = cell.ConstructChild(*this, candidatePlane, true);
+                        backData.mCell = cell.ConstructChild(*this, candidatePlane, false);
+
+                        frontData.mArea = frontData.mCell->GetArea();
+                        backData.mArea = backData.mCell->GetArea();
+
+                        pFront = frontData.mArea;
+                        pBack = backData.mArea;
+
+                        pOverall = area;
+                }
+                else
+                {
+                        pOverall = (float)rays.size();
+                }
+        }
+                        
         BoundedRayContainer::const_iterator rit, rit_end = rays.end();
 
@@ -1386 +1383 @@
                                 // assure that we only count a object 
                                 // once for the front and once for the back side of the plane
-                                AddToPvs(*ray->intersections[0].mObject, 
-                                                   frontPvs, backPvs, 
-                                                   cf, frontId, backId, frontAndBackId);
+                                AddToPvs(*ray->intersections[0].mObject, frontData.mPvs, backData.mPvs, 
+                                                 cf, frontId, backId, frontAndBackId);
                         }
 
                         // the source object in the origin of the ray
-                        AddToPvs(*ray->sourceObject.mObject, 
-                                           frontPvs, backPvs, 
-                                           cf, frontId, backId, frontAndBackId);
-
+                        AddToPvs(*ray->sourceObject.mObject, frontData.mPvs, backData.mPvs, 
+                                         cf, frontId, backId, frontAndBackId);
+
+                        // use #rays to approximate volume
                         if (0)
                         {
                                 if ((cf == Ray::BACK) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
-                                        ++ backRays;
+                                        ++ pFront;
                                 if ((cf == Ray::FRONT) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
-                                        ++ frontRays;
+                                        ++ pBack;
                         }
                 }
         }
 
-        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
-                if (!rays.empty())
+        if ((sSplitPlaneStrategy & LEAST_RAY_SPLITS) && !rays.empty())
                         val += sLeastRaySplitsFactor * sumRaySplits / (float)rays.size();
 
-        if (sSplitPlaneStrategy & BALANCED_RAYS)
-                if (!rays.empty())
+        if ((sSplitPlaneStrategy & BALANCED_RAYS) && !rays.empty())
                         val += sBalancedRaysFactor * fabs(sumBalancedRays) / (float)rays.size();
 
-        if (sSplitPlaneStrategy & PVS)
-                if (0 && !rays.empty()) // HACK (should divide by maximal possible pvs)
-                        val += sPvsFactor * (frontPvs * (float)frontRays + (backPvs * (float)backRays)) / (float)rays.size(); 
-                else
-                        val += sPvsFactor * (frontPvs * frontArea + (backPvs * backArea)) /
-                                ((frontArea + backArea) * (float)pvsSize);
-
-        //Debug << "pvs: " << pvsSize << " val " << val << endl;
+        if ((sSplitPlaneStrategy & PVS) && area && pvs)
+                val += sPvsFactor * (frontData.mPvs * pFront + (backData.mPvs * pBack)) /       (pOverall * (float)pvs * 2);
+
+        Debug << "pvs: " << pvs << " totalArea: " << area 
+                  << " frontpvs: " << frontData.mPvs << " pFront: " << pFront 
+                  << " backpvs: " << backData.mPvs << " pBack: " << pBack 
+                  << " val " << val << endl;
+
         return val;
 }
 
 void BspTree::AddToPvs(Intersectable &obj,
-                                           float &frontPvs,
-                                           float &backPvs,
+                                           int &frontPvs,
+                                           int &backPvs,
                                            const int cf, 
                                            const int frontId, 
@@ -1441 +1435 @@
                         (obj.mMailbox != frontAndBackId))
                 {
-                        frontPvs += 1.0;
+                        ++ frontPvs;
 
                         if (obj.mMailbox != backId)
@@ -1454 +1448 @@
                         (obj.mMailbox != frontAndBackId))
                 {
-                        backPvs += 1.0;
+                        ++ backPvs;
 
                         if (obj.mMailbox != frontId)
@@ -1468 +1462 @@
                 {
                         if (obj.mMailbox != frontId)
-                                frontPvs += 1.0;
+                                ++ frontPvs;
                         if (obj.mMailbox != backId)
-                                backPvs += 1.0;
+                                ++ backPvs;
                 
                         obj.mMailbox = frontAndBackId;
@@ -1477 +1471 @@
 }
 
-float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
-                                                          const PolygonContainer &polys,                                                          
-                                                          const BoundedRayContainer &rays,
-                                                          const PolygonContainer &cell,
-                                                          const vector<Plane3 *> &planes,
-                                                          const vector<bool> &sides,
-                                                          const int pvsSize) const
+float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,
+                                                          BspTraversalData &data,
+                                                          BspTraversalData &frontData,
+                                                          BspTraversalData &backData) const
 {
         float val = 0;
@@ -1503 +1494 @@
                 (sSplitPlaneStrategy & BLOCKED_RAYS))
         {
-        val += SplitPlaneCost(candidatePlane, polys);
+                val += SplitPlaneCost(candidatePlane, *data.mPolygons);
         }
 
@@ -1511 +1502 @@
                 (sSplitPlaneStrategy & PVS))
         {
-                float frontArea = 0;
-                float backArea = 0;
-
-                if (sSplitPlaneStrategy & PVS)
-                {
-                        PolygonContainer frontCell;
-                        PolygonContainer backCell;
-
-                        // construct child geometry with regard to the candidate split plane
-                        ConstructChildGeometry(frontCell, cell, planes, sides, candidatePlane, true);
-                        ConstructChildGeometry(backCell, cell, planes, sides, candidatePlane, false);
-
-                        frontArea = Polygon3::GetArea(frontCell);
-                        backArea = Polygon3::GetArea(backCell);
-
-                        CLEAR_CONTAINER(frontCell);
-                        CLEAR_CONTAINER(backCell);
-                }
-                
-                val += SplitPlaneCost(candidatePlane, rays, frontArea, backArea, pvsSize);
+                val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs, 
+                                                          data.mArea, *data.mCell, frontData, backData);
         }
 
@@ -1562 +1535 @@
         //-- termination criteria for autopartition
         environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
+        environment->GetIntValue("BspTree.Termination.minPvs", sTermMinPvs);
         environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
         environment->GetIntValue("BspTree.Termination.maxRays", sTermMaxRays);
@@ -1579 +1553 @@
         environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
         environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder);
-        
-        environment->GetBoolValue("BspTree.Visualization.storePolys", sStoreSplitPolys);
 
         environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
@@ -1591 +1563 @@
 
     Debug << "BSP max depth: " << sTermMaxDepth << endl;
+        Debug << "BSP min PVS: " << sTermMinPvs << endl;
         Debug << "BSP max polys: " << sTermMaxPolygons << endl;
         Debug << "BSP max rays: " << sTermMaxRays << endl;
@@ -1673 +1646 @@
                 mStat.minDepth = data.mDepth;
 
+        // store minimal and maximal pvs
+        /*if (data.mPvs > mStat.pvs)
+                mStat.pvs = data.mPvs;
+        
+        if (data.mPvs < mStat.pvs)
+                mStat.pvs = data.mPvs;*/
+
         // accumulate depth to compute average
         mStat.accumDepth += data.mDepth;
@@ -1679 +1659 @@
         Debug << "BSP stats: "
                   << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
+                   << "PVS: " << data.mPvs << " (max: " << sTermMinPvs << "), "
                   << "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
                   << "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << "), " 
@@ -1975 +1956 @@
                 {
                 case Ray::COINCIDENT:
-                        frontRays.push_back(bRay);
+                        //frontRays.push_back(bRay);
                         break;
                 case Ray::BACK:
@@ -2024 +2005 @@
 
 void BspTree::ExtractSplitPlanes(BspNode *n, 
-                                                                 vector<Plane3 *> &planes, 
+                                                                 vector<Plane3> &planes, 
                                                                  vector<bool> &sides) const
 {
@@ -2040 +2021 @@
                         BspInterior *interior = dynamic_cast<BspInterior *>(n);
 
-                        planes.push_back(dynamic_cast<BspInterior *>(interior)->GetPlane());
+                        planes.push_back(* dynamic_cast<BspInterior *>(interior)->GetPlane());
                         sides.push_back(interior->mFront == lastNode);
                 }
@@ -2047 +2028 @@
 }
 
-bool BspTree::ConstructChildGeometry(PolygonContainer &childCell,
-                                                                         const PolygonContainer &cell,
-                                                                         const vector<Plane3 *> &planes,
-                                                                         const vector<bool> &sides,
-                                                                         const Plane3 &splitPlane,
-                                                                         const bool side) const
-{
+void BspTree::ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const
+{
+        stack<BspNode *> tStack;
+
+        vector<Plane3> planes;
+        vector<bool> sides;
+
+        ExtractSplitPlanes(n, cell.mPlanes, cell.mSides);
+
+        PolygonContainer candidatePolys;
+
+        // bounded planes are added to the polygons
+        for (int i = 0; i < (int)cell.mPlanes.size(); ++ i)
+        {
+                candidatePolys.push_back(GetBoundingBox().CrossSection(cell.mPlanes[i]));
+        }
+
+        // add faces of bounding box (also could be faces of the cell)
+        for (int i = 0; i < 6; ++ i)
+        {
+                VertexContainer vertices;
+        
+                for (int j = 0; j < 4; ++ j)
+                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
+
+                candidatePolys.push_back(new Polygon3(vertices));
+        }
+
+        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
+        {
+                bool inside = true;
+
+                // polygon is split by all other planes
+                for (int j = 0; (j < cell.mPlanes.size()) && inside; ++ j)
+                {
+                        if (i == j) // same plane
+                                continue;
+
+                        VertexContainer splitPts;
+                        Polygon3 *frontPoly, *backPoly;
+
+                        const int cf = candidatePolys[i]->ClassifyPlane(cell.mPlanes[j]);
+                        
+                        switch (cf)
+                        {
+                                case Polygon3::SPLIT:
+                                        frontPoly = new Polygon3();
+                                        backPoly = new Polygon3();
+                                
+                                        candidatePolys[i]->Split(cell.mPlanes[j], *frontPoly, 
+                                                                                         *backPoly, splitPts);
+                                        DEL_PTR(candidatePolys[i]);
+
+                                        if(sides[j] == true)
+                                        {
+                                                candidatePolys[i] = frontPoly;
+                                                DEL_PTR(backPoly);
+                                        }
+                                        else
+                                        {
+                                                candidatePolys[i] = backPoly;
+                                                DEL_PTR(frontPoly);
+                                        }
+                                        
+                                        break;
+
+                                case Polygon3::BACK_SIDE:
+                                        if (cell.mSides[j]) 
+                                                inside = false;
+                                        break;
+                                case Polygon3::FRONT_SIDE:
+                                        if (!cell.mSides[j])
+                                                inside = false;
+                                        break;
+                                case Polygon3::COINCIDENT:
+                                        break;
+                                default:
+                                        break;
+                        }
+                }
+                
+                if (inside)
+                        cell.mPolys.push_back(candidatePolys[i]);
+                else
+                        DEL_PTR(candidatePolys[i]);
+        }
+}
+
+void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
+{
+        stack<BspNode *> tStack;
+
+        vector<Plane3> planes;
+        vector<bool> sides;
+
+        ExtractSplitPlanes(n, planes, sides);
+
+        PolygonContainer candidatePolys;
+
+        // bounded planes are added to the polygons
+        for (int i = 0; i < (int)planes.size(); ++ i)
+        {
+                candidatePolys.push_back(GetBoundingBox().CrossSection(planes[i]));
+        }
+
+        // add faces of bounding box (also could be faces of the cell)
+        for (int i = 0; i < 6; ++ i)
+        {
+                VertexContainer vertices;
+        
+                for (int j = 0; j < 4; ++ j)
+                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
+
+                candidatePolys.push_back(new Polygon3(vertices));
+        }
+
+        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
+        {
+                bool inside = true;
+
+                // polygon is split by all other planes
+                for (int j = 0; (j < planes.size()) && inside; ++ j)
+                {
+                        if (i == j) // same plane
+                                continue;
+
+                        VertexContainer splitPts;
+                        Polygon3 *frontPoly, *backPoly;
+
+                        const int cf = candidatePolys[i]->ClassifyPlane(planes[j]);
+                        
+                        switch (cf)
+                        {
+                                case Polygon3::SPLIT:
+                                        frontPoly = new Polygon3();
+                                        backPoly = new Polygon3();
+
+                                        candidatePolys[i]->Split(planes[j], *frontPoly, 
+                                                                                         *backPoly, splitPts);
+                                        DEL_PTR(candidatePolys[i]);
+
+                                        if(sides[j] == true)
+                                        {
+                                                candidatePolys[i] = frontPoly;
+                                                DEL_PTR(backPoly);
+                                        }
+                                        else
+                                        {
+                                                candidatePolys[i] = backPoly;
+                                                DEL_PTR(frontPoly);
+                                        }
+                                        
+                                        break;
+
+                                case Polygon3::BACK_SIDE:
+                                        if (sides[j]) 
+                                                inside = false;
+                                        break;
+                                case Polygon3::FRONT_SIDE:
+                                        if (!sides[j])
+                                                inside = false;
+                                        break;
+                                case Polygon3::COINCIDENT:
+                                        break;
+                                default:
+                                        break;
+                        }
+                }
+                
+                if (inside)
+                        cell.push_back(candidatePolys[i]);
+                else
+                        DEL_PTR(candidatePolys[i]);
+        }
+}
+
+void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
+{
+        vector<BspLeaf *> leaves = vc->mBspLeaves;
+
+        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+                ConstructGeometry(*it, cell);
+}
+
+int BspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 
+                                                   const bool onlyUnmailed) const
+{
+        PolygonContainer cell;
+
+        ConstructGeometry(n, cell);
+
+        stack<BspNode *> nodeStack;
+        nodeStack.push(mRoot);
+                
+        // planes needed to verify that we found neighbor leaf.
+        vector<Plane3> planes;
+        vector<bool> sides;
+
+        ExtractSplitPlanes(n, planes, sides);
+
+        while (!nodeStack.empty()) 
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                if (node->IsLeaf())
+                {
+            if (node != n && (!onlyUnmailed || !node->Mailed()))
+                        {
+                                // test all planes of current node on neighbour
+                                PolygonContainer neighborCandidate;
+                                ConstructGeometry(node, neighborCandidate);
+                                
+                                bool isAdjacent = true;
+                                for (int i = 0; (i < planes.size()) && isAdjacent; ++ i)
+                                {
+                                        const int cf = 
+                                                Polygon3::ClassifyPlane(neighborCandidate, planes[i]);
+
+                                        if ((cf == Polygon3::BACK_SIDE) && sides[i])
+                                                isAdjacent = false;
+                                        else if ((cf == Polygon3::FRONT_SIDE) && !sides[i])
+                                                isAdjacent = false;
+                                }
+
+                                if (isAdjacent)
+                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
+
+                                CLEAR_CONTAINER(neighborCandidate);
+                        }
+                }
+                else 
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+        
+                        const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
+
+                        if (cf == Polygon3::FRONT_SIDE)
+                                nodeStack.push(interior->mFront);
+                        else
+                                if (cf == Polygon3::BACK_SIDE)
+                                        nodeStack.push(interior->mBack);
+                                else 
+                                {
+                                        // random decision
+                                        nodeStack.push(interior->mBack);
+                                        nodeStack.push(interior->mFront);
+                                }
+                }
+        }
+        
+        CLEAR_CONTAINER(cell);
+        return (int)neighbors.size();
+}
+
+BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
+{
+    stack<BspNode *> nodeStack;
+        nodeStack.push(mRoot);
+        
+        int mask = rand();
+  
+        while (!nodeStack.empty()) 
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+          
+                if (node->IsLeaf()) 
+                {
+                        return dynamic_cast<BspLeaf *>(node);
+                } 
+                else 
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        
+                        BspNode *next;
+        
+                        PolygonContainer cell;
+
+                        // todo: not very efficient: constructs full cell everytime
+                        ConstructGeometry(interior, cell);
+
+                        const int cf = Polygon3::ClassifyPlane(cell, halfspace);
+
+                        if (cf == Polygon3::BACK_SIDE)
+                                next = interior->mFront;
+                        else
+                                if (cf == Polygon3::FRONT_SIDE)
+                                        next = interior->mFront;
+                        else 
+                        {
+                                // random decision
+                                if (mask & 1)
+                                        next = interior->mBack;
+                                else
+                                        next = interior->mFront;
+                                mask = mask >> 1;
+                        }
+
+                        nodeStack.push(next);
+                }
+        }
+        
+        return NULL;
+}
+
+BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
+{
+        stack<BspNode *> nodeStack;
+        
+        nodeStack.push(mRoot);
+
+        int mask = rand();
+        
+        while (!nodeStack.empty()) 
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+                
+                if (node->IsLeaf()) 
+                {
+                        if ( (!onlyUnmailed || !node->Mailed()) )
+                                return dynamic_cast<BspLeaf *>(node);
+                }
+                else 
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+                        // random decision
+                        if (mask & 1)
+                                nodeStack.push(interior->mBack);
+                        else
+                                nodeStack.push(interior->mFront);
+
+                        mask = mask >> 1;
+                }
+        }
+        
+        return NULL;
+}
+
+int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
+{
+        int pvsSize = 0;
+
+        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
+
+        Intersectable::NewMail();
+
+        for (rit = rays.begin(); rit != rays.end(); ++ rit)
+        {
+                Ray *ray = (*rit)->mRay;
+                
+                if (!ray->intersections.empty())
+                {
+                        if (!ray->intersections[0].mObject->Mailed())
+                        {
+                                ray->intersections[0].mObject->Mail();
+                                ++ pvsSize;
+                        }
+                }
+                if (!ray->sourceObject.mObject->Mailed())
+                {
+                        ray->sourceObject.mObject->Mail();
+                        ++ pvsSize;
+                }
+        }
+
+        return pvsSize;
+}
+
+/*************************************************************
+ *            BspNodeGeometry Implementation                 *
+ *************************************************************/
+
+BspNodeGeometry::BspNodeGeometry(const PolygonContainer &polys, 
+                                                                 const vector<Plane3> &planes, 
+                                                                 const vector<bool> &sides):
+mPolys(polys), mPlanes(planes), mSides(sides)
+{}                                         
+
+BspNodeGeometry::BspNodeGeometry(const vector<Plane3> &planes, 
+                                                                 const vector<bool> &sides):
+mPlanes(planes), mSides(sides)
+{}
+
+BspNodeGeometry::~BspNodeGeometry()
+{
+        CLEAR_CONTAINER(mPolys);
+}
+
+float BspNodeGeometry::GetArea() const 
+{ 
+        return Polygon3::GetArea(mPolys);
+}
+
+BspNodeGeometry *BspNodeGeometry::ConstructChild(const BspTree &tree,
+                                                                                                 const Plane3 &splitPlane,
+                                                                                                 const bool side) const
+{
+        BspNodeGeometry *childCell = new BspNodeGeometry(mPlanes, mSides);
+
         // get cross section of new polygon
-        Polygon3 *planePoly = GetBoundingBox().CrossSection(splitPlane);
+        Polygon3 *planePoly = tree.GetBoundingBox().CrossSection(splitPlane);
 
         // polygon is split by all other planes
-        for (int i = 0; (i < (int)planes.size()) && planePoly; ++ i)
-        {
-                const int cf = planePoly->ClassifyPlane(*planes[i]);
+        for (int i = 0; (i < (int)mPlanes.size()) && planePoly; ++ i)
+        {
+                const int cf = planePoly->ClassifyPlane(mPlanes[i]);
                         
                 // split new polygon with all previous planes
@@ -2072 +2450 @@
                                         Polygon3 *backPoly = new Polygon3();
 
-                                        planePoly->Split(*planes[i], *frontPoly, *backPoly, splitPts);
+                                        planePoly->Split(mPlanes[i], *frontPoly, *backPoly, splitPts);
                                         DEL_PTR(planePoly);
 
-                                        if(sides[i] == true)
+                                        if(mSides[i] == true)
                                         {
                                                 planePoly = frontPoly;
@@ -2091 +2469 @@
                                 break;
                         case Polygon3::BACK_SIDE:
-                                if (sides[i]) 
+                                if (mSides[i]) 
                                         DEL_PTR(planePoly);
                                 break;
                         case Polygon3::FRONT_SIDE:
-                                if (!sides[i])
+                                if (!mSides[i])
                                         DEL_PTR(planePoly);
                                 break;
@@ -2108 +2486 @@
         {
                 //geometry is not changed at all, hence just copy polygons
-                PolygonContainer::const_iterator it, it_end = cell.end();
-                
-                for (it = cell.begin(); it != it_end; ++ it)
-                        childCell.push_back(new Polygon3((*it)->mVertices));
-
-                return false;
+                PolygonContainer::const_iterator it, it_end = mPolys.end();
+                for (it = mPolys.begin(); it != it_end; ++ it)
+                        childCell->mPolys.push_back(new Polygon3((*it)->mVertices));
+                
+                return childCell;
         }
 
         //-- plane poly splits all other cell polygons
-        for (int i = 0; i < (int)cell.size(); ++ i)
-        {
-                const int cf = cell[i]->ClassifyPlane(splitPlane);
+        for (int i = 0; i < (int)mPolys.size(); ++ i)
+        {
+                const int cf = mPolys[i]->ClassifyPlane(splitPlane);
                         
                 // split new polygon with all previous planes
@@ -2126 +2503 @@
                         case Polygon3::SPLIT:
                                 {
-                                        Polygon3 *poly = new Polygon3(cell[i]->mVertices);
+                                        Polygon3 *poly = new Polygon3(mPolys[i]->mVertices);
 
                                         Polygon3 *frontPoly = new Polygon3();
@@ -2149 +2526 @@
                                                 DEL_PTR(poly);
                                         else
-                                                childCell.push_back(poly);
+                                                childCell->mPolys.push_back(poly);
                                 }
                                 
@@ -2155 +2532 @@
                         case Polygon3::BACK_SIDE:
                                 if (!side) 
-                                        childCell.push_back(new Polygon3(cell[i]->mVertices));                  
+                                        childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));                        
                                 break;
                         case Polygon3::FRONT_SIDE:
                                 if (side)
-                                        childCell.push_back(new Polygon3(cell[i]->mVertices));  
+                                        childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));        
                                 break;
                         case Polygon3::COINCIDENT:
-                                childCell.push_back(new Polygon3(cell[i]->mVertices));
+                                childCell->mPolys.push_back(new Polygon3(mPolys[i]->mVertices));
                                 break;
                         default:
@@ -2171 +2548 @@
 
         //-- finally add the new polygon
-        childCell.push_back(planePoly);
-        
-        return true;
-}
-
-
-void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
-{
-        stack<BspNode *> tStack;
-
-        vector<Plane3 *> planes;
-        vector<bool> sides;
-
-        ExtractSplitPlanes(n, planes, sides);
-
-        PolygonContainer candidatePolys;
-
-        // bounded planes are added to the polygons
-        for (int i = 0; i < (int)planes.size(); ++ i)
-        {
-                candidatePolys.push_back(GetBoundingBox().CrossSection(*planes[i]));
-        }
-
-        // add faces of bounding box (also could be faces of the cell)
-        for (int i = 0; i < 6; ++ i)
-        {
-                VertexContainer vertices;
-        
-                for (int j = 0; j < 4; ++ j)
-                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
-
-                candidatePolys.push_back(new Polygon3(vertices));
-        }
-
-        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
-        {
-                bool inside = true;
-
-                // polygon is split by all other planes
-                for (int j = 0; (j < planes.size()) && inside; ++ j)
-                {
-                        Plane3 *plane = planes[j];
-
-                        if (i == j) // same plane
-                                continue;
-
-                        VertexContainer splitPts;
-                        Polygon3 *frontPoly, *backPoly;
-
-                        const int cf = candidatePolys[i]->ClassifyPlane(*plane);
-                        
-                        switch (cf)
-                        {
-                                case Polygon3::SPLIT:
-                                        frontPoly = new Polygon3();
-                                        backPoly = new Polygon3();
-
-                                        candidatePolys[i]->Split(*plane, *frontPoly, 
-                                                                                         *backPoly, splitPts);
-                                        DEL_PTR(candidatePolys[i]);
-
-                                        if(sides[j] == true)
-                                        {
-                                                candidatePolys[i] = frontPoly;
-                                                DEL_PTR(backPoly);
-                                        }
-                                        else
-                                        {
-                                                candidatePolys[i] = backPoly;
-                                                DEL_PTR(frontPoly);
-                                        }
-                                        
-                                        break;
-
-                                case Polygon3::BACK_SIDE:
-                                        if (sides[j]) 
-                                                inside = false;
-                                        break;
-                                case Polygon3::FRONT_SIDE:
-                                        if (!sides[j])
-                                                inside = false;
-                                        break;
-                                case Polygon3::COINCIDENT:
-                                        break;
-                                default:
-                                        break;
-                        }
-                }
-                
-                if (inside)
-                        cell.push_back(candidatePolys[i]);
-                else
-                        DEL_PTR(candidatePolys[i]);
-        }
-}
-
-void BspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const
-{
-        vector<BspLeaf *> leaves = vc->mBspLeaves;
-
-        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
-
-        for (it = leaves.begin(); it != it_end; ++ it)
-                ConstructGeometry(*it, cell);
-}
-
-int BspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 
-                                                   const bool onlyUnmailed) const
-{
-        PolygonContainer cell;
-
-        ConstructGeometry(n, cell);
-
-        stack<BspNode *> nodeStack;
-        nodeStack.push(mRoot);
-                
-        // planes needed to verify that we found neighbor leaf.
-        vector<Plane3 *> planes;
-        vector<bool> sides;
-
-        ExtractSplitPlanes(n, planes, sides);
-
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
-                nodeStack.pop();
-
-                if (node->IsLeaf())
-                {
-            if (node != n && (!onlyUnmailed || !node->Mailed()))
-                        {
-                                // test all planes of current node on neighbour
-                                PolygonContainer neighborCandidate;
-                                ConstructGeometry(node, neighborCandidate);
-                                
-                                bool isAdjacent = true;
-                                for (int i = 0; (i < planes.size()) && isAdjacent; ++ i)
-                                {
-                                        const int cf = 
-                                                Polygon3::ClassifyPlane(neighborCandidate, *planes[i]);
-
-                                        if ((cf == Polygon3::BACK_SIDE) && sides[i])
-                                                isAdjacent = false;
-                                        else if ((cf == Polygon3::FRONT_SIDE) && !sides[i])
-                                                isAdjacent = false;
-                                }
-
-                                if (isAdjacent)
-                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
-
-                                CLEAR_CONTAINER(neighborCandidate);
-                        }
-                }
-                else 
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-        
-                        const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
-
-                        if (cf == Polygon3::FRONT_SIDE)
-                                nodeStack.push(interior->mFront);
-                        else
-                                if (cf == Polygon3::BACK_SIDE)
-                                        nodeStack.push(interior->mBack);
-                                else 
-                                {
-                                        // random decision
-                                        nodeStack.push(interior->mBack);
-                                        nodeStack.push(interior->mFront);
-                                }
-                }
-        }
-        
-        CLEAR_CONTAINER(cell);
-        return (int)neighbors.size();
-}
-
-BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace)
-{
-    stack<BspNode *> nodeStack;
-        nodeStack.push(mRoot);
-        
-        int mask = rand();
-  
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
-                nodeStack.pop();
-          
-                if (node->IsLeaf()) 
-                {
-                        return dynamic_cast<BspLeaf *>(node);
-                } 
-                else 
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-                        
-                        BspNode *next;
-        
-                        PolygonContainer cell;
-
-                        // todo: not very efficient: constructs full cell everytime
-                        ConstructGeometry(interior, cell);
-
-                        const int cf = Polygon3::ClassifyPlane(cell, halfspace);
-
-                        if (cf == Polygon3::BACK_SIDE)
-                                next = interior->mFront;
-                        else
-                                if (cf == Polygon3::FRONT_SIDE)
-                                        next = interior->mFront;
-                        else 
-                        {
-                                // random decision
-                                if (mask & 1)
-                                        next = interior->mBack;
-                                else
-                                        next = interior->mFront;
-                                mask = mask >> 1;
-                        }
-
-                        nodeStack.push(next);
-                }
-        }
-        
-        return NULL;
-}
-
-BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed)
-{
-        stack<BspNode *> nodeStack;
-        
-        nodeStack.push(mRoot);
-
-        int mask = rand();
-        
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
-                nodeStack.pop();
-                
-                if (node->IsLeaf()) 
-                {
-                        if ( (!onlyUnmailed || !node->Mailed()) )
-                                return dynamic_cast<BspLeaf *>(node);
-                }
-                else 
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        // random decision
-                        if (mask & 1)
-                                nodeStack.push(interior->mBack);
-                        else
-                                nodeStack.push(interior->mFront);
-
-                        mask = mask >> 1;
-                }
-        }
-        
-        return NULL;
-}
-
-int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
-{
-        int pvsSize = 0;
-
-        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
-
-        Intersectable::NewMail();
-
-        for (rit = rays.begin(); rit != rays.end(); ++ rit)
-        {
-                Ray *ray = (*rit)->mRay;
-                
-                if (!ray->intersections.empty())
-                {
-                        if (!ray->intersections[0].mObject->Mailed())
-                        {
-                                ray->intersections[0].mObject->Mail();
-                                ++ pvsSize;
-                        }
-                }
-                if (!ray->sourceObject.mObject->Mailed())
-                {
-                        ray->sourceObject.mObject->Mail();
-                        ++ pvsSize;
-                }
-        }
-
-        return pvsSize;
-}
+        childCell->mPolys.push_back(planePoly);
+        childCell->mPlanes.push_back(splitPlane);
+        childCell->mSides.push_back(side);
+
+        return childCell;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -4 +4 @@
 #include "Mesh.h"
 #include "Containers.h"
+#include "Polygon3.h"
 #include <stack>
 
@@ -11 +12 @@
 class BspTree;  
 class BspInterior;
-class Polygon3;
+//class Polygon3;
 class AxisAlignedBox3;
 class Ray;
+
+class BspNodeGeometry
+{
+public:
+        BspNodeGeometry()
+        {};
+
+        BspNodeGeometry(const PolygonContainer &polys, 
+                                        const vector<Plane3> &planes, 
+                                        const vector<bool> &sides);
+        BspNodeGeometry(const vector<Plane3> &planes, 
+                                        const vector<bool> &sides);        
+
+        ~BspNodeGeometry();
+
+        float GetArea() const;
+        
+        /** Computes new cell based on the old cell definition and a new split plane
+                @param side indicates which side of the halfspace 
+                @returns true if plane contributes to the cell.
+        */
+        BspNodeGeometry *ConstructChild(const BspTree &tree,
+                                                                        const Plane3 &splitPlane,
+                                                                        const bool side) const;
+
+        vector<Plane3> mPlanes;
+        vector<bool> mSides;
+        PolygonContainer mPolys;
+};
 
 /** Data structure used for optimized ray casting.
@@ -176 +206 @@
 public:
         BspNode();
-        virtual ~BspNode();
+        virtual ~BspNode(){};
         BspNode(BspInterior *parent);
 
@@ -192 +222 @@
         */
         BspInterior *GetParent();
+
         /** Sets parent node.
         */
         void SetParent(BspInterior *parent);
 
-        /** Returns pointer to polygons.
-        */
-        PolygonContainer *GetPolygons();
-        /** Stores polygons in node or discards them according to storePolys.
-        */
-        void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
-
+        
         static int mailID;
         int mailbox;
@@ -210 +235 @@
         bool Mailed() const { return mailbox == mailID; }
 
-//int mViewCellIdx;
 protected:
 
         /// parent of this node
         BspInterior *mParent;
-
-        /// store polygons created during BSP splits
-        PolygonContainer *mPolygons;
 };
 
@@ -247 +268 @@
                 @param backPolys returns the polygons in the back of the split plane
                 @param coincident returns the polygons coincident to the split plane
-                @param storePolys if the polygons should be stored in the node
-                
+
                 @returns the number of splits   
         */
@@ -254 +274 @@
                                           PolygonContainer &frontPolys, 
                                           PolygonContainer &backPolys, 
-                                          PolygonContainer &coincident,
-                                          const bool storePolys = false);
-
-        /** Stores polygon in node or discards them according to storePolys.
-                @param polys the polygons
-                @param storePolys if the polygons should be stored or discarded
-        */
-        void ProcessPolygon(Polygon3 **poly, const bool storePolys);
+                                          PolygonContainer &coincident);
 
         friend ostream &operator<<(ostream &s, const BspInterior &A)
@@ -337 +350 @@
                 /// rays piercing this node
                 BoundedRayContainer *mRays;
-
+                /// area of current node
+                float mArea;
+                BspNodeGeometry *mCell;
+
+                /// pvs size
+                int mPvs;
+                
                 BspTraversalData():
                 mNode(NULL),
@@ -343 +362 @@
                 mDepth(0),
                 mViewCell(NULL),
-                mRays(NULL)
+                mRays(NULL),
+                mPvs(0),
+                mArea(0.0),
+                mCell(NULL)
                 {}
                 
@@ -350 +372 @@
                                                  const int depth, 
                                                  ViewCell *viewCell,
-                                                 BoundedRayContainer *rays): 
+                                                 BoundedRayContainer *rays,
+                                                 int pvs,
+                                                 float area,
+                                                 BspNodeGeometry *cell): 
                 mNode(node), 
                 mPolygons(polys), 
                 mDepth(depth), 
                 mViewCell(viewCell),
-                mRays(rays)
+                mRays(rays),
+                mPvs(pvs),
+                mArea(area),
+                mCell(cell)
                 {}
     };
@@ -445 +473 @@
         void ConstructGeometry(BspViewCell *vc, PolygonContainer &cell) const;
 
+        void ConstructGeometry(BspNode *n, BspNodeGeometry &cell) const;
+
         /** Returns random leaf of BSP tree.
                 @param halfspace defines the halfspace from which the leaf is taken.
@@ -454 +484 @@
         */
         BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
-
-        /** Computes new cell based on the old cell definition and a new split plane
-                @param side indicates which side of the halfspace 
-                @returns true if plane contributes to the cell.
-        */
-        bool ConstructChildGeometry(PolygonContainer &childCell,
-                                                            const PolygonContainer &cell,
-                                                            const vector<Plane3 *> &planes,
-                                                            const vector<bool> &sides,
-                                                            const Plane3 &splitPlane,
-                                                            const bool side) const;
-
 
         /** Returns true if merge criteria are reached.
@@ -530 +548 @@
         */
         Plane3 SelectPlane(BspLeaf *leaf, 
-                                           PolygonContainer &polys,
-                                           const BoundedRayContainer &ray);
+                                           BspTraversalData &data,
+                                           BspTraversalData &frontData,
+                                           BspTraversalData &backData);
 
         /** Evaluates the contribution of the candidate split plane.
@@ -542 +561 @@
         */
         float SplitPlaneCost(const Plane3 &candidatePlane,
-                                                 const PolygonContainer &polys,                                                  
-                                                 const BoundedRayContainer &rays,
-                                                 const PolygonContainer &cell,
-                                                 const vector<Plane3 *> &plane,
-                                                 const vector<bool> &sides,
-                                                 const int pvsSize) const;
+                                                 BspTraversalData &data,
+                                                 BspTraversalData &frontData,
+                                                 BspTraversalData &backData) const;
 
         /** Strategies where the effect of the split plane is tested
@@ -557 +573 @@
 
         /** Strategies where the effect of the split plane is tested
-            on all input polygons.
+            on all input rays.
 
                 @returns the cost of the candidate split plane
         */
-        float SplitPlaneCost(const Plane3 &candidatePlane,
+        float SplitPlaneCost(const Plane3 &candidatePlane, 
                                                  const BoundedRayContainer &rays,
-                                                 const float frontArea,
-                                                 const float backArea,
-                                                 const int pvsSize) const;
+                                                 const int pvs,
+                                                 const float area,
+                                                 const BspNodeGeometry &cell, 
+                                                 BspTraversalData &frontData,
+                                                 BspTraversalData &backData) const;
 
         /** Filters next view cell down the tree and inserts it into the appropriate leaves
@@ -589 +607 @@
                 @returns the root of the subdivision
         */
-        BspInterior *SubdivideNode(BspLeaf *leaf, 
-                                                           PolygonContainer &polys,
-                                                           PolygonContainer &frontPolys,
-                                                           PolygonContainer &backPolys,
-                                                           PolygonContainer &coincident,
-                                                           BoundedRayContainer &rays,
-                                                           BoundedRayContainer &frontRays,
-                                                           BoundedRayContainer &backRays);
+
+        BspInterior *SubdivideNode(BspTraversalData &tData,
+                                                           BspTraversalData &frontData,
+                                                           BspTraversalData &backData,
+                                                           PolygonContainer &coincident);
 
         /** Filters polygons down the tree.
@@ -614 +629 @@
                 @param polygons container of polygons
                 @param rays bundle of rays on which the split can be based
-                @param maxPolyCandidates the maximal number of tested polygon candidates
-                @param maxRayCandidates the maximal number of ray candidates
         */
         Plane3 SelectPlaneHeuristics(BspLeaf *leaf,
-                                         PolygonContainer &polys, 
-                                                                 const BoundedRayContainer &rays,
-                                                                 const int maxPolyCandidates,
-                                                                 const int maxRayCandidates);
+                                                                 BspTraversalData &data,
+                                                                 BspTraversalData &frontData,
+                                                                 BspTraversalData &backData);
 
         /** Extracts the meshes of the objects and adds them to polygons. 
@@ -663 +675 @@
                 @param extractFront if a front view cell is extracted
         */
-        void ExtractViewCells(ViewCell **backViewCell, 
-                                                  ViewCell **frontViewCell,
+        void ExtractViewCells(BspTraversalData &frontData,
+                                                  BspTraversalData &backData, 
                                                   const PolygonContainer &coincident,
-                                                  const Plane3 splitPlane, 
-                                                  const bool extractBack,
-                                                  const bool extractFront) const;
+                                                  const Plane3 splitPlane) const;
         
         /** Computes best cost ratio for the suface area heuristics for axis aligned
@@ -723 +733 @@
         /** Extracts the split planes representing the space bounded by node n.
         */
-        void ExtractSplitPlanes(BspNode *n, vector<Plane3 *> &planes, vector<bool> &sides) const;
+        void ExtractSplitPlanes(BspNode *n, vector<Plane3> &planes, vector<bool> &sides) const;
 
         /** Computes the pvs of the front and back leaf with a given classification.
         */
         void AddToPvs(Intersectable &obj, 
-                                        float &frontPvs,
-                                        float &backPvs,
-                                        const int cf, 
-                                        const int frontId, 
-                                        const int backId, 
-                                        const int frontAndBackId) const;
+                                  int &frontPvs,
+                                  int &backPvs,
+                                  const int cf, 
+                                  const int frontId, 
+                                  const int backId, 
+                                  const int frontAndBackId) const;
         
         int ComputePvsSize(const BoundedRayContainer &rays) const;
@@ -779 +789 @@
         /// maximal possible depth
         static int sTermMaxDepth;
+        /// mininam pvs
+        static int sTermMinPvs;
         /// strategy to get the best split plane
         static int sSplitPlaneStrategy;
@@ -809 +821 @@
         static float sPvsFactor;
 
-        /// if polygons should be stored in the tree
-        static bool sStoreSplitPolys;
-
         //-- thresholds used for view cells are merging
         static int sMinPvsDif;

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -547 +547 @@
                 SetFilled();
 
-        //ViewCellContainer foundViewCells;
-
-        if (BspTree::sStoreSplitPolys)
-        {
-                while (!tStack.empty()) 
-                {
-            BspNode *node = tStack.top();
-    
-                        tStack.pop();
-        
-                        PolygonContainer::const_iterator it;
-                        PolygonContainer::const_iterator it_end = node->GetPolygons()->end();
-
-                        for (it = node->GetPolygons()->begin(); it != it_end; ++ it)
-                                ExportPolygon(*it);
-                        
-                        if (!node->IsLeaf()) 
-                        {
-                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
-      
-                                tStack.push(interior->GetFront());
-                                tStack.push(interior->GetBack());
-
-                        }
-                }
-        }
         // export view cells
         ExportBspViewCellPartition(tree);