Changeset 362 for trunk/VUT

Timestamp:

11/01/05 02:37:51 (19 years ago)

Author:

mattausch

Message:

added post merging bsp view cells
fixed bug at per ray subdivision

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (6 diffs)
• src/Camera.cpp (modified) (2 diffs)
• src/Environment.cpp (modified) (4 diffs)
• src/Exporter.h (modified) (2 diffs)
• src/KdTree.cpp (modified) (1 diff)
• src/Plane3.h (modified) (1 diff)
• src/Polygon3.cpp (modified) (3 diffs)
• src/Polygon3.h (modified) (1 diff)
• src/Pvs.h (modified) (1 diff)
• src/Ray.cpp (modified) (1 diff)
• src/Ray.h (modified) (2 diffs)
• src/SamplingPreprocessor.cpp (modified) (11 diffs)
• src/SamplingPreprocessor.h (modified) (2 diffs)
• src/ViewCell.cpp (modified) (1 diff)
• src/ViewCell.h (modified) (2 diffs)
• src/ViewCellBsp.cpp (modified) (48 diffs)
• src/ViewCellBsp.h (modified) (17 diffs)
• src/X3dExporter.h (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -9 +9 @@
 #       filename vienna.x3d
 #       filename ../data/vienna/vienna-simple.x3d
-        filename ../data/vienna/vienna-buildings.x3d
+#       filename ../data/vienna/vienna-buildings.x3d
 #       filename ../data/vienna/viewcells-25-sel.x3d
-#       filename ../data/atlanta/atlanta2.x3d
+        filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
 #       filename ../data/soda/soda5.dat
@@ -56 +56 @@
 
 Sampling {
-        totalSamples    20000
-        samplesPerPass  2
+        totalSamples    200000
+        samplesPerPass  3
 }
 
@@ -68 +68 @@
         maxViewCells 0
         
+        minPvsDif 10
+        
 #       filename ../data/atlanta/atlanta_viewcells_large.x3d
         filename ../data/vienna/viewcells-25-sel.x3d
@@ -76 +78 @@
 BspTree {
         Construction {
-        #       input fromRays
-                input fromViewCells
+                input fromRays
+        #       input fromViewCells
         #       input fromSceneGeometry
-                samples 15000
+                samples 100000
                 sideTolerance 0.005
         }
@@ -116 +118 @@
         #splitPlaneStrategy 130
         
-        splitPlaneStrategy 66
+        splitPlaneStrategy 130
         
         maxCandidates 80
@@ -122 +124 @@
         Termination {
                 # autopartition
-                maxRays -1
+                maxRays 80
                 maxPolygons 0
                 maxDepth 100
                 
                 # axis aligned splits
-                maxPolysForAxisAligned 400
-                maxCostRatio 0.9
-                ct_div_ci 0.5
+                AxisAligned {
+                        maxPolys 500
+                        maxRays 300
+                        maxObjects 20
+                        maxCostRatio 0.9
+                        ct_div_ci 0.5
+                }
         }
         
-        #axis aligned split
-        splitBorder 0.01
-        
+        AxisAligned {
+                splitBorder 0.01
+        }
+                
         # if split polys are stored for visualization
         storeSplitPolys false

trunk/VUT/GtpVisibilityPreprocessor/src/Camera.cpp

@@ -102 +102 @@
     int k =0;
     for (int j=0; j < rays.size(); j++)
-      if (rays[j].leaves.size()) {
+      if (rays[j].kdLeaves.size()) {
         Ray *ray = &(rays[j]);
         int i;
         if (1)
-        for (i= 0; i < ray->leaves.size(); i++)
-          exporter->ExportBox(tree->GetBox(ray->leaves[i]));
+        for (i= 0; i < ray->kdLeaves.size(); i++)
+          exporter->ExportBox(tree->GetBox(ray->kdLeaves[i]));
         if (0)
         for (i= 0; i < ray->meshes.size(); i++)
@@ -130 +130 @@
 
   ray.intersections.clear();
-  ray.leaves.clear();
+  ray.kdLeaves.clear();
   ray.meshes.clear();
-  
+  ray.bspLeaves.clear();
+
   ray.Init(mPosition, target, Ray::LOCAL_RAY);
   

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1147 +1147 @@
   RegisterOption("Sampling.samplesPerPass",
                  optInt,
-                 "-total_samples=",
+                 "-samples_per_pass=",
                  "10");
 
@@ -1155 +1155 @@
                  "bspTree");
 
+  RegisterOption("ViewCells.minPvsDif",
+                 optString,
+                 "-view_cells_min_pvs_dif",
+                 "10");
+
   RegisterOption("ViewCells.filename",
                  optString,
@@ -1190 +1195 @@
                  "-1");
 
-  RegisterOption("BspTree.Termination.maxPolysForAxisAligned",
+  RegisterOption("BspTree.Termination.AxisAligned.maxCostRatio",
+                 optFloat,
+                 "-bsp_term_max_cost_ratio=",
+                 "1.5");
+
+  RegisterOption("BspTree.Termination.AxisAligned.ct_div_ci",
+                 optFloat,
+                 "-bsp_term_ct_div_ci=",
+                 "1.0");
+
+  RegisterOption("BspTree.AxisAligned.splitBorder",
+                 optFloat,
+                 "-bsp_split_border=",
+                 "0.1");
+
+  RegisterOption("BspTree.Termination.AxisAligned.maxPolys",
                  optInt,
                  "-bsp_term_max_polygons=",
                  "50");
+
+   RegisterOption("BspTree.Termination.AxisAligned.maxObjects",
+                 optInt,
+                 "-bsp_term_max_objects=",
+                 "3");
+
+  RegisterOption("BspTree.Termination.AxisAligned.maxRays",
+                 optInt,
+                 "-bsp_term_max_rays=",
+                 "-1");
 
   RegisterOption("BspTree.Termination.maxDepth",
@@ -1199 +1229 @@
                  "-bsp_term_max_depth=",
                  "100");
-  
-  RegisterOption("BspTree.Termination.maxCostRatio",
-                 optFloat,
-                 "-bsp_term_max_cost_ratio=",
-                 "1.5");
-
-  RegisterOption("BspTree.Termination.ct_div_ci",
-                 optFloat,
-                 "-bsp_term_ct_div_ci=",
-                 "1.0");
-
-  RegisterOption("BspTree.splitBorder",
-                 optFloat,
-                 "-bsp_split_border=",
-                 "0.1");
 
   RegisterOption("BspTree.storeSplitPolys",

trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h

@@ -16 +16 @@
 class Intersectable;
 class BspLeaf;
+class Polygon3;
 
 class Exporter
@@ -74 +75 @@
   ExportLeavesGeometry(const BspTree &tree, const vector<BspLeaf *> &leaves) = 0;
         
+  virtual void 
+  ExportPolygons(const PolygonContainer &polys) = 0;
+
   void SetExportRayDensity(const bool d) { mExportRayDensity = d; }
   

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

@@ -572 +572 @@
       // compute intersection with all objects in this leaf
       KdLeaf *leaf = (KdLeaf *) node;
-      ray.leaves.push_back(leaf);
+      ray.kdLeaves.push_back(leaf);
       
       ObjectContainer::const_iterator mi;

trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

@@ -55 +55 @@
         }
         
+        if (coplanar) (*coplanar) = false;
     float u = - Distance(a) / dv; // TODO: could be done more efficiently
     
-        if (coplanar) (*coplanar) = false;
         if (t) (*t) = u;
         
-        //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl;
-    //return a - Distance(a) * b / dv + Distance(a) * a / dv; // NOTE: gives better precision than calclulating a + u * v
     return a + u * v;
   }
   
+  float FindT(const Vector3 &a,
+                          const Vector3 &b) const 
+  {       
+          const Vector3 v = b - a; // line from A to B
+          const float dv = DotProd(v, mNormal);
+    
+          if (signum(dv) == 0)
+                  return 1;
+        
+          return - Distance(a) / dv; // TODO: could be done more efficiently
+  }
+
   friend bool
   PlaneIntersection(const Plane3 &a, const Plane3 &b, const Plane3 &c, Vector3 &result);

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -147 +147 @@
         for (it = mVertices.begin(); it != mVertices.end(); ++ it)
         {
-                int side = plane.Side(*it, Vector3::sDistTolerance);
+                const int side = plane.Side(*it, Vector3::sDistTolerance);
                 
                 if (side > 0)
@@ -395 +395 @@
                 if ((cf == SPLIT) || (cf == COINCIDENT) || (onFrontSide && onBackSide))
                 {
-                        Debug << "here" << endl;
                         return SPLIT;
                 }
@@ -411 +410 @@
         return SPLIT;
 }
+
+int Polygon3::CountIntersectables(const PolygonContainer &polys)
+{
+        int count = 0;
+
+        PolygonContainer::const_iterator it, it_end = polys.end();
+
+        MeshInstance::NewMail();
+
+        for (it = polys.begin(); it != it_end; ++ it)
+        {
+                if ((*it)->mParent && !(*it)->mParent->Mailed())
+                {
+                        ++ count;
+                        (*it)->mParent->Mail();
+                }
+        }
+        return count;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -118 +118 @@
         void InheritRays(Polygon3 &front_piece, 
                                          Polygon3 &back_piece) const;
+
+
+        /** Counts the number of different intersectables associated with the polygons.
+        */
+        static int CountIntersectables(const PolygonContainer &polys);
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.h

@@ -37 +37 @@
         int GetSize() {return (int)mEntries.size();}
         bool Empty() {return mEntries.size() == 0;}
+        /** Merges pvs of a and pvs of b into this pvs.
+        */
         void Merge(const Pvs<T> &a, const Pvs<T> &b);
+    /** Difference of pvs to pvs b.
+                @returns number of different entries.
+        */
+        int Diff(const Pvs<T> &b);
 
         PvsData<T> *Find(T sample);
         int AddSample(T sample);
 
-        void GetData(const int index,
-               T &entry,
-               PvsData<T> &data);
+        void GetData(const int index, T &entry, PvsData<T> &data);
         std::map<T, PvsData<T>, LtSample<T> > mEntries;
 };
 
 template <typename T>
+int Pvs<T>::Diff(const Pvs<T> &b)
+{
+        int dif = 0;
+
+        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
+
+        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
+        {
+                PvsData<T> *data = Find((*it).first);           
+                if (!data) ++ dif;
+        }
+
+        return dif;
+}
+
+template <typename T>
 void Pvs<T>::Merge(const Pvs<T> &a, const Pvs<T> &b)
 {
-        //std::merge(a.mEntries.begin(), a.mEntries.end(), 
-        //             b.mEntries.begin(), b.mEntries.end(), mEntries.begin());
+        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;
+
+        // todo: copy all elements instead of inserting
+        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
+        {
+                mEntries.insert(*it);
+        }
+
+        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
+        {
+                PvsData<T> *data = Find((*it).first);
+                
+                if (data)
+                        data->mVisibleSamples += (*it).second.mVisibleSamples;
+                else
+                        mEntries.insert(*it);
+        }
 }
+
 
 template <typename T>

trunk/VUT/GtpVisibilityPreprocessor/src/Ray.cpp

@@ -168 +168 @@
         const int extSide = plane.Side(extp);
 
-        if ((entSide == 0) && (extSide == 0)) 
+        if (entSide < 0)
         {
-                return COINCIDENT;
-        }
-        else if ((entSide <= 0) && (extSide <= 0))
-        {
+                if (extSide >= 0)
+                {
+                        return BACK_FRONT;
+                }
                 return BACK;
         }
-        else if ((entSide >= 0) && (extSide >= 0))
+        else if (entSide > 0)
         {
+                if (extSide <= 0)
+                        return FRONT_BACK;
+
                 return FRONT;
         }
-        else if ((entSide <= 0) && (extSide >= 0))
-                return BACK_FRONT;
+        else if (entSide == 0)
+        {
+                if (extSide > 0)
+                        return BACK_FRONT;
+                else if (extSide < 0)
+                        return FRONT_BACK;
+        }
         
-        return FRONT_BACK;
+        return COINCIDENT;
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Ray.h

@@ -12 +12 @@
 class MeshInstance;
 class ViewCell;
+class BspLeaf;
 
 // -------------------------------------------------------------------
@@ -61 +62 @@
   
   vector<Intersection> intersections;
-  vector<KdLeaf *> leaves;
+  vector<KdLeaf *> kdLeaves;
   vector<MeshInstance *> meshes;
-  vector<ViewCell *> viewCells;
+  vector<BspLeaf *> bspLeaves;
   
   // constructors

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -32 +32 @@
 {
   ray.intersections.clear();
-  ray.leaves.clear();
+  ray.kdLeaves.clear();
   ray.meshes.clear();
-  ray.viewCells.clear();
+  ray.bspLeaves.clear();
 
   //  cout<<point<<" "<<direction<<endl;
@@ -68 +68 @@
                 mSceneGraph->CollectObjects(&objects);
                 mBspTree->Construct(objects);
-                
-                mBspTree->CollectViewCells(mViewCells);
                 break;
         case BspTree::FROM_RAYS:
@@ -75 +73 @@
                 mBspTree->SetGenerateViewCells(true);
                 mBspTree->Construct(mSampleRays);
-                
-                mBspTree->CollectViewCells(mViewCells);
                 break;
         default:
@@ -94 +90 @@
   int contributingSamples = 0;
   int j;
-  for (j=0; j < ray.leaves.size(); j++) {
-    KdNode *node = GetNodeForPvs( ray.leaves[j] );
+  for (j=0; j < ray.kdLeaves.size(); j++) {
+    KdNode *node = GetNodeForPvs( ray.kdLeaves[j] );
     contributingSamples += object->mKdPvs.AddSample(node);
   }
    
   if (mPass > 10)
-    for (j=1; j < ((int)ray.leaves.size() - 1); j++) {
-      ray.leaves[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
+    for (j=1; j < ((int)ray.kdLeaves.size() - 1); j++) {
+      ray.kdLeaves[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
   }
   
@@ -114 +110 @@
  
         // object can be seen from the view cell => add to view cell pvs
-        for (j=0; j < ray.viewCells.size(); ++ j) 
+        for (j=0; j < ray.bspLeaves.size(); ++ j) 
         {       // if ray not in unbounded space
-                if (ray.viewCells[j] != &mUnbounded)
-                        contributingSamples += ray.viewCells[j]->GetPvs().AddSample(obj);
+                if (ray.bspLeaves[j]->GetViewCell() != &mUnbounded)
+                        contributingSamples += 
+                                ray.bspLeaves[j]->GetViewCell()->GetPvs().AddSample(obj);
         }
  
         // rays passing through this viewcell
         if (mPass > 1)
-                for (j=1; j < ((int)ray.viewCells.size() - 1); ++ j) 
-                {
-                        if (ray.viewCells[j] != &mUnbounded)
-                                ray.viewCells[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
+                for (j=1; j < ((int)ray.bspLeaves.size() - 1); ++ j) 
+                {
+                        if (ray.bspLeaves[j]->GetViewCell() != &mUnbounded)
+                                ray.bspLeaves[j]->GetViewCell()->
+                                        AddPassingRay(ray, contributingSamples ? 1 : 0);
                 }
  
@@ -183 +181 @@
         else
                 {
-                        if (ray.leaves.size()) {
+                        if (ray.kdLeaves.size()) {
                                 if (!reverseRay)
                                         sampleContributions += AddNodeSamples(object, ray);
@@ -372 +370 @@
 
   vector<Ray> rays[10];
-
-  vector<Ray> vcRays[5];
-  ViewCellContainer pvsViewCells;
-  vector<Ray> viewCellRays; // used for BSP tree construction
 
   while (totalSamples < mTotalSamples) {
@@ -462 +456 @@
                                         }
                                         //-------------------
-
                                         if (mViewCellsType == BSP_VIEW_CELLS) 
                                         {
-                                                // save rays for bsp tree construction
-                                                if (collectSamplesForBsp)
-                                                {
-                                                        // also add origin to sample in order to extract it as input polygons
-                                                        MeshInstance *mi = dynamic_cast<MeshInstance *>(object);
-                                                        ray.sourceObject = Ray::Intersection(0.0, mi, faceIndex);
-                                                        
-                            mSampleRays.push_back(new Ray(ray));
-                                                }
-                                                else
-                                                {
-                                                        // construct BSP tree using the samples
-                                                        if (!mBspTree)
-                                                        {
-                                                                BuildBspTree();
-
-                                                                cout << "generated " << (int)mViewCells.size() << " view cells" << endl;
-
-                                                                passContributingSamples += mBspTree->GetStat().contributingSamples;
-                                                                passSampleContributions += mBspTree->GetStat().sampleContributions;
-
-                                                                BspTreeStatistics(Debug);       
-                                                                Export("vc_bsptree.x3d", false, false, true);
-                                                        }
-                                                                
-                                                        // some random view cells for output
-                                                        if (pvsViewCells.empty())
-                                                        {
-                                                                int vcPvsOut = Min((int)mViewCells.size(), 5);
-                                                        
-                                                                for (int j = 0; j < vcPvsOut; ++ j)
-                                                                {
-                                                                        int idx = Random((int)mViewCells.size());
-                                                                        Debug << "output view cell=" << idx << endl;
-                                                                        pvsViewCells.push_back(mViewCells[Random((int)mViewCells.size())]);
-                                                                }
-                                                        }
-                                                        else
-                                                        {       
-                                                                // check whether we can add the current ray to the rays
-                                                                for (int k = 0; k < (int)ray.viewCells.size(); ++ k)
-                                                                        for (int j = 0; j < (int)pvsViewCells.size(); ++ j) 
-                                                                                if (pvsViewCells[j] == ray.viewCells[k]) 
-                                                                                        vcRays[j].push_back(ray);                                                       
-                                                        }
-                                                }
+                                                ProcessBspViewCells(collectSamplesForBsp,
+                                                                                        ray,
+                                                                                        object,
+                                                                                        faceIndex,
+                                                                                        passContributingSamples,
+                                                                                        passSampleContributions);
                                         }
-                
                                 }
                         } else {
@@ -580 +532 @@
                 cout << "#totalPvsSize=" << mKdTree->CollectLeafPvs() << endl;
   
+        // merge or subdivide view cells
+        if (mBspTree)
+        {
+                int merged = PostprocessViewCells(mSampleRays);
+                Debug << "merged " << merged << " view cells" << endl;
+
+                ViewCellContainer vc;
+                mBspTree->CollectViewCells(vc);
+
+                ViewCellContainer::const_iterator it, it_end = vc.end();
+
+                int mergedPvs = 0;
+                for (it = vc.begin(); it != it_end; ++ it)
+                        mergedPvs += (*it)->GetPvs().GetSize();
+
+                Debug << "merged pvs size: " << mergedPvs << endl;
+
+        }
+        
   //  HoleSamplingPass();
-  if (0) {
-    Exporter *exporter = Exporter::GetExporter("ray-density.x3d");
-    exporter->SetExportRayDensity(true);
-    exporter->ExportKdTree(*mKdTree);
-
+        if (0) {
+                Exporter *exporter = Exporter::GetExporter("ray-density.x3d"); 
+                exporter->SetExportRayDensity(true);
+                exporter->ExportKdTree(*mKdTree);
+
+                if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS))
+                        exporter->ExportBspTree(*mBspTree);
+
+                delete exporter;
+        }
+  
+        bool exportRays = false;
+        if (exportRays) {
+                Exporter *exporter = NULL;
+                exporter = Exporter::GetExporter("sample-rays.x3d");
+                exporter->SetWireframe();
+                exporter->ExportKdTree(*mKdTree);
+                exporter->ExportBspTree(*mBspTree);
+
+                for (i=0; i < pvsOut; i++) 
+                exporter->ExportRays(rays[i], 1000, RgbColor(1, 0, 0));
+                exporter->SetFilled();
+                  
+                delete exporter;
+        }
+
+        //-- several visualizations and statistics
+        if (1) {
         if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS))
-                exporter->ExportBspTree(*mBspTree);
-
-    delete exporter;
-  }
-  
-  bool exportRays = false;
-  if (exportRays) {
-    Exporter *exporter = NULL;
-    exporter = Exporter::GetExporter("sample-rays.x3d");
-    exporter->SetWireframe();
-    exporter->ExportKdTree(*mKdTree);
-        exporter->ExportBspTree(*mBspTree);
-
-    for (i=0; i < pvsOut; i++) 
-      exporter->ExportRays(rays[i], 1000, RgbColor(1, 0, 0));
-    exporter->SetFilled();
-          
-    delete exporter;
-  }
-
-  //-- several visualizations and statistics
-  if (1) {
-  if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS))
-  {
-          bool exportSplits = false;
-          environment->GetBoolValue("BspTree.exportSplits", exportSplits);
-
-          // export the bsp splits
-          if (exportSplits)
-                  ExportSplits(objects);
-        
-          Exporter *exporter = Exporter::GetExporter("viewCells.x3d");
-
-          // export leaves
-          if (0 && exporter)
-          {
-                  vector<BspLeaf *> leaves;
-                  mBspTree->CollectLeaves(leaves);
-                  vector<BspLeaf *> randLeaves;
-                  vector<BspLeaf *> neighbors;
-
-                  for (int k = 0; k < 1; ++ k) 
-                  {
-                          BspLeaf *leaf = leaves[Random((int)leaves.size())];
-                          randLeaves.push_back(leaf);
-                          mBspTree->FindNeighbors(leaf, neighbors, false);
-                  }     
-
-                  exporter->ExportLeavesGeometry(*mBspTree, randLeaves);
-                  exporter->SetWireframe();
-          exporter->ExportLeavesGeometry(*mBspTree, neighbors); 
-                        
-          delete exporter;
-          }
-
-           vector<BspLeaf *> leaves;
-           mBspTree->CollectLeaves(leaves);
-           
-           for (int k = 0; k < 100; ++ k) 
-           {
-                   vector<BspLeaf *> randLeaves;
-                   vector<BspLeaf *> neighbors;
-                   
-                   char s[64]; sprintf(s, "bsp-vc%04d.x3d", k);
-                   Exporter *exporter = Exporter::GetExporter(s);
-
-                   BspLeaf *leaf = leaves[Random((int)leaves.size())];
-                   Debug << "\noutput leaf " << k << endl;
-                   randLeaves.push_back(leaf);
-                   mBspTree->FindNeighbors(leaf, neighbors, false);
-
-                   exporter->ExportLeavesGeometry(*mBspTree, randLeaves);
-                   exporter->SetWireframe();
-                   exporter->ExportLeavesGeometry(*mBspTree, neighbors);        
-                        
-                   delete exporter;
-           }    
-
-          for (int j = 0; j < pvsViewCells.size(); ++ j)
-          {
-                  ViewCell *vc = pvsViewCells[j];
-
-                  Intersectable::NewMail();
-                  char s[64]; sprintf(s, "bsp-pvs%04d.x3d", j);
-
-                  Exporter *exporter = Exporter::GetExporter(s);
-                  exporter->SetFilled();
-
-                  ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin();
-
-                  Material m;//= RandomMaterial();
-                  m.mDiffuseColor = RgbColor(0, 1, 0);
-                  exporter->SetForcedMaterial(m);
-
-                  exporter->ExportViewCell(vc);
-
-                  Debug << j << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-                            << ", piercing rays=" << (int)vcRays[j].size() << endl;
-
-                  exporter->SetWireframe();
-
-                  // export view cells
-                  m.mDiffuseColor = RgbColor(1, 0, 1);
-                  exporter->SetForcedMaterial(m);
-                  exporter->ExportViewCells(mViewCells);
-                        
-                  // export rays piercing this view cell
-                  exporter->ExportRays(vcRays[j], 1000, 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();
-                          }                     
-                  }
-                
-                  // 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())
-                                  {
-                                          //if (j == 2198)m.mDiffuseColor = RgbColor(1, 0, 1);
-                                          //else m.mDiffuseColor = RgbColor(1, 1, 0);
-                                          exporter->SetForcedMaterial(m);
-                                          exporter->ExportIntersectable(objects[j]);
-                                          objects[j]->Mail();
-                                  }
-                  }
-                  DEL_PTR(exporter);
-                }
-  }  
-
+        {
+                bool exportSplits = false;
+                environment->GetBoolValue("BspTree.exportSplits", exportSplits);
+
+                // export the bsp splits
+                if (exportSplits)
+                        ExportSplits(objects);
+                
+                ExportBspPvs(objects);
+        }
    for (int k=0; k < pvsOut; k++) {
       Intersectable *object = objects[k];
@@ -772 +632 @@
 }
 
+bool SamplingPreprocessor::ProcessBspViewCells(bool collectSamplesForBsp,
+                                                                                           Ray &ray,
+                                                                                           Intersectable *object,
+                                                                                           int faceIndex,
+                                                                                           int &contributingSamples,
+                                                                                           int &sampleContributions)
+{
+        // save rays for bsp tree construction
+        if (collectSamplesForBsp)
+        {
+                // also add origin to sample in order to extract it as input polygons
+                MeshInstance *mi = dynamic_cast<MeshInstance *>(object);
+                ray.sourceObject = Ray::Intersection(0.0, mi, faceIndex);
+                                                        
+        mSampleRays.push_back(new Ray(ray));
+                
+                return false;
+        }
+        
+        // construct BSP tree using the samples
+        if (!mBspTree)
+        {
+                BuildBspTree();
+                
+                contributingSamples += mBspTree->GetStat().contributingSamples;
+                sampleContributions += mBspTree->GetStat().sampleContributions;
+
+                BspTreeStatistics(Debug);       
+                if (0) Export("vc_bsptree.x3d", false, false, true);
+        }
+
+        return true;
+}
+
+// merge or subdivide view cells
+int SamplingPreprocessor::PostprocessViewCells(const RayContainer &rays)
+{
+        int merged = 0;
+        RayContainer::const_iterator rit, rit_end = rays.end();
+        vector<BspLeaf *>::const_iterator lit;
+if (0)
+        for (rit = rays.begin(); rit != rays.end(); ++ rit)
+        {  
+                // traverse leaves stored in the rays and compare and merge consecutive
+                // leaves (i.e., the neighbors in the tree)
+                lit = (*rit)->bspLeaves.begin();
+
+                BspLeaf *previousLeaf = *lit;
+                ++ lit;
+                
+                for (; lit != (*rit)->bspLeaves.end(); ++ lit)
+                {
+                        BspLeaf *leaf = *lit;
+                        if (mBspTree->ShouldMerge(leaf, previousLeaf))
+                        {                       
+                                mBspTree->MergeViewCells(leaf, previousLeaf);
+                                ++ merged;
+                        }
+                        previousLeaf = leaf;
+                }
+        }
+        return merged;
+}
 
 void SamplingPreprocessor::ExportSplits(const ObjectContainer &objects)
@@ -829 +752 @@
         }
 }
+
+void SamplingPreprocessor::ExportBspPvs(const ObjectContainer &objects)
+{
+        //-- some random view cells and rays for output
+        const int leafOut = 10;
+
+        vector<Ray> vcRays[leafOut];
+        vector<BspLeaf *> bspLeaves;
+                        
+        for (int i = 0; i < leafOut; ++ i)
+                bspLeaves.push_back(mBspTree->GetRandomLeaf());
+        
+        const int raysOut = min((int)mSampleRays.size(), 20000);
+
+        // 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->bspLeaves.size(); ++ j)
+                {
+                        for (int i = 0; i < (int)bspLeaves.size(); ++ i)
+                        {
+                                if (bspLeaves[i] == ray->bspLeaves[j]) 
+                                {
+                                        vcRays[i].push_back(*ray);
+                                }
+                        }
+                }
+        }
+
+        ViewCell::NewMail();
+
+        for (int i = 0; i < bspLeaves.size(); ++ i)
+        {
+                Intersectable::NewMail();
+
+                ViewCell *vc = bspLeaves[i]->GetViewCell();
+
+                //bspLeaves[j]->Mail();
+                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
+
+                Exporter *exporter = Exporter::GetExporter(s);
+                exporter->SetFilled();
+
+                ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin();
+
+                Material m;//= RandomMaterial();
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+
+                exporter->SetWireframe();
+
+                if (vc->GetMesh())
+                        exporter->ExportViewCell(vc);
+                else
+                {
+            PolygonContainer cell;
+
+                        mBspTree->ConstructGeometry(bspLeaves[i], cell);
+                        exporter->ExportPolygons(cell);
+                        CLEAR_CONTAINER(cell);
+
+                        /*vector<BspLeaf *> neighbors;
+                        mBspTree->FindNeighbors(bspLeaves[j], neighbors);
+                        for (int j = 0; j < (int)neighbors.size(); ++ j)
+                        {       if (neighbors[j]->mViewCell == bspLeaves[j]->mViewCell)
+                                {}}*/
+                }
+
+                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
+                                << ", piercing rays=" << (int)vcRays[i].size() << endl;
+
+                // export view cells
+                if (0)
+                {
+                        m.mDiffuseColor = RgbColor(1, 0, 1);
+                        exporter->SetForcedMaterial(m);
+                        exporter->ExportViewCells(mViewCells);
+                }
+
+                // export rays piercing this view cell
+                exporter->ExportRays(vcRays[i], 1000, 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();
+                        }                       
+                }
+                        
+                // 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())
+                                {
+                                        //if (j == 2198)m.mDiffuseColor = RgbColor(1, 0, 1);
+                                        //else m.mDiffuseColor = RgbColor(1, 1, 0);
+                                        exporter->SetForcedMaterial(m);
+                                        exporter->ExportIntersectable(objects[j]);
+                                        objects[j]->Mail();
+                                }
+                }
+                DEL_PTR(exporter);
+        }
+}

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.h

@@ -64 +64 @@
                                                                         );
 
-        /** Adds objects samples to view cells.
+        /** Processes the BSP based view cells during a pass.
+                @param collectSamplesForBps if still in sample collection phase
+                @param ray the current ray
+                @param object the currently processed object
+                @param faceIndex the sampled face of the object
+                @param contributingSamples samples contributing to pvs
+                @param sampleContributions contribution of the samples
+
+                @returns true if BSP tree has been constructed, false if not yet
+
+        */
+        bool ProcessBspViewCells(bool collectSamplesForBsp,
+                                                         Ray &ray,
+                                                         Intersectable *object,
+                                                         int faceIndex,
+                                                         int &contributingSamples,
+                                                         int &sampleContributions);
+
+        /** Adds objects samples to bsp view cells.
         */
         int AddObjectSamples(Intersectable *obj, const Ray &ray);
@@ -71 +89 @@
 
         void ExportSplits(const ObjectContainer &objects);
+
+        void ExportBspPvs(const ObjectContainer &objects);
+
+        /** Post processes view cells (i.e., merges or subdivides view cells based
+                on the PVS and the ray sets.
+                @returns number of merged view cells.
+        */
+        int PostprocessViewCells(const RayContainer &rays);
+
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -81 +81 @@
 }
 
-ViewCell *ViewCell::MergeViewCells(const ViewCell &front, const ViewCell &back)
+ViewCell *ViewCell::Merge(ViewCell &front, ViewCell &back)
 {
-        /*stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end());
+        ViewCell *vc = new ViewCell();
+        // merge pvs
+        vc->mPvs.Merge(front.mPvs, back.mPvs);
+
+        // merge ray sets
+        stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end());
         stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end());
 
-        ViewCell *vc = front.Merge(back);
+        std::merge(front.mPiercingRays.begin(), front.mPiercingRays.end(),
+                           back.mPiercingRays.begin(), back.mPiercingRays.end(), 
+                           vc->mPiercingRays.begin());
 
-        if (vc)
-                return vc;
-
-        return back.Merge(front);*/return NULL;
+        return vc;
 }
-
-ViewCell *ViewCell::Merge(const ViewCell &other) const
-{
-        //-- compute set differences
-        const float minDif = 10;
-
-        RayContainer diff;
-
-        set_difference(mPiercingRays.begin(), mPiercingRays.end(), 
-                                   other.mPiercingRays.begin(), other.mPiercingRays.end(),
-                                   diff.begin());
-
-        if (diff.size() < minDif)
-        {
-                ViewCell *vc = new ViewCell();
-
-                RayContainer::const_iterator it, it_end = other.mPiercingRays.end();
-
-                for (it = other.mPiercingRays.begin(); it != it_end; ++ it)
-                        vc->mPiercingRays.push_back(*it);
-
-                while (!diff.empty())
-                {
-                        vc->mPiercingRays.push_back(diff.back());
-                        diff.pop_back();
-                }
-
-                return vc;
-        }
-
-        return NULL;
-}
-
 
 void ViewCell::AddPassingRay(const Ray &ray, const int contributions)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -48 +48 @@
         static ViewCell *ExtrudeViewCell(const Triangle3 &baseTri, const float height);
 
-        /** Merges two view cells based on some criteria
-                @returns new view cell if merge was success. NULL if merge failed.
+        /** Merges two view cells.
+                @note the piercing rays of the front and back will be ordered   
+                @returns new view cell based on the merging.
         */
-        static ViewCell *MergeViewCells(const ViewCell &front, const ViewCell &back);
+        static ViewCell *Merge(ViewCell &front, ViewCell &back);
 
 
@@ -61 +62 @@
 
 protected:
-        
-        /** Merges view cell with other view cell if certain criteria are met.
-                @note because of performance issues the precondition is that the piercing rays are ordered.
-        */
-        ViewCell *Merge(const ViewCell &other) const;
 
         /// the potentially visible objects

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -20 +20 @@
 int BspTree::sConstructionMethod = FROM_INPUT_VIEW_CELLS;
 int BspTree::sTermMaxPolysForAxisAligned = 50;
+int BspTree::sTermMaxObjectsForAxisAligned = 50;
+int BspTree::sTermMaxRaysForAxisAligned = -1;
 int BspTree::sTermMaxRays = -1;
+int BspTree::sMinPvsDif = 10;
 
 float BspTree::sCt_div_ci = 1.0f;
@@ -31 +34 @@
 float BspTree::sBalancedPolysFactor = 1.0f;
 float BspTree::sBalancedViewCellsFactor = 1.0f;
+
 // NOTE:  very important criterium for 2.5d scenes
 float BspTree::sVerticalSplitsFactor = 1.0f;
@@ -285 +289 @@
 }
 
-void BspLeaf::GenerateViewCell(const RayContainer &rays, 
+void BspLeaf::GenerateViewCell(const BoundedRayContainer &rays, 
                                                            int &sampleContributions,
                                                            int &contributingSamples,
@@ -295 +299 @@
         mViewCell = new ViewCell();
 
-    RayContainer::const_iterator it, it_end = rays.end();
+    BoundedRayContainer::const_iterator it, it_end = rays.end();
 
         // add contributions from samples to the PVS
@@ -301 +305 @@
         {
                 int contribution = 0;
-
-                if (!(*it)->intersections.empty())
+                Ray *ray = (*it)->mRay;
+                        
+                if (!ray->intersections.empty())
                 {       
-            contribution +=  mViewCell->GetPvs().AddSample((*it)->intersections[0].mObject);
-                }
-
-                contribution +=  mViewCell->GetPvs().AddSample((*it)->sourceObject.mObject);
+            contribution += mViewCell->GetPvs().AddSample(ray->intersections[0].mObject);
+                }
+
+                contribution += mViewCell->GetPvs().AddSample(ray->sourceObject.mObject);
 
                 if (contribution > 0)
@@ -315 +320 @@
                 }
 
+                ray->bspLeaves.push_back(this);
+
                 if (storeRays)
-                        mViewCell->mPiercingRays.push_back(*it);
+                        mViewCell->mPiercingRays.push_back(ray);
         }
 }
@@ -414 +421 @@
                 mRoot = new BspLeaf();
 
-        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new RayContainer()));
+        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer()));
 
         while (!tStack.empty())
@@ -472 +479 @@
                                                                                          tData.mDepth + 1, 
                                                                                          backViewCell,
-                                                                                         new RayContainer()));
+                                                                                         new BoundedRayContainer()));
                         }
 
@@ -570 +577 @@
 
         // construct tree from the view cell polygons
-        Construct(polys, new RayContainer());
+        Construct(polys, new BoundedRayContainer());
 }
 
@@ -585 +592 @@
 
         // construct tree from polygon soup
-        Construct(polys, new RayContainer());
+        Construct(polys, new BoundedRayContainer());
 }
 
@@ -591 +598 @@
 {
         mStat.nodes = 1;
-        mBox.Initialize();      // initialise bsp tree bounding box
+        mBox.Initialize();      // initialise BSP tree bounding box
         
         PolygonContainer *polys = new PolygonContainer();
-        RayContainer *rays = new RayContainer();
+        BoundedRayContainer *rays = new BoundedRayContainer();
 
         RayContainer::const_iterator rit, rit_end = sampleRays.end();
@@ -608 +615 @@
         {
                 Ray *ray = *rit;
-                ray->SetId(-1); // reset id
-                rays->push_back(ray);
-
-                //Debug << "extracting ray with intersections" << ray->intersections.size() << endl;
-
+        
                 // get ray-face intersection. Store polygon representing the rays together
                 // with rays intersecting the face.
@@ -629 +632 @@
                         {
                                 Polygon3 *poly = new Polygon3(face, obj->GetMesh());
+                                poly->mParent = obj;
                                 polys->push_back(poly);
                                 poly->mPiercingRays.push_back(ray);
@@ -638 +642 @@
         
         Polygon3::IncludeInBox(*polys, mBox);
+
+        //-- store rays
+        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+        {
+                Ray *ray = *rit;
+        ray->SetId(-1); // reset id
+
+                float minT, maxT;
+                if (BoundRay(*ray, minT, maxT))
+                        rays->push_back(new BoundedRay(ray, minT, maxT));
+        }
+
         mStat.polys = (int)polys->size();
 
@@ -647 +663 @@
 }
 
-void BspTree::Construct(PolygonContainer *polys, RayContainer *rays)
+void BspTree::Construct(PolygonContainer *polys, BoundedRayContainer *rays)
 {
         std::stack<BspTraversalData> tStack;
@@ -705 +721 @@
                 leaf->ProcessPolygons(tData.mPolygons, sStoreSplitPolys);
                 DEL_PTR(tData.mPolygons);
+                // discard rays
+                CLEAR_CONTAINER(*tData.mRays);
                 DEL_PTR(tData.mRays);
 
@@ -717 +735 @@
         PolygonContainer *backPolys = new PolygonContainer();
 
-        RayContainer *frontRays = new RayContainer();
-        RayContainer *backRays = new RayContainer();
+        BoundedRayContainer *frontRays = new BoundedRayContainer();
+        BoundedRayContainer *backRays = new BoundedRayContainer();
         
         // create new interior node and two leaf nodes
@@ -810 +828 @@
                                                                         PolygonContainer &backPolys,
                                                                         PolygonContainer &coincident,
-                                                                        RayContainer &rays,
-                                                                        RayContainer &frontRays,
-                                                                        RayContainer &backRays)
+                                                                        BoundedRayContainer &rays,
+                                                                        BoundedRayContainer &frontRays,
+                                                                        BoundedRayContainer &backRays)
 {
         mStat.nodes += 2;
@@ -827 +845 @@
         SplitRays(interior->mPlane, rays, frontRays, backRays);
         
-        // split polygons with split plane
-        mStat.splits +=interior->SplitPolygons(polys, 
-                                                                               frontPolys, 
-                                                                       backPolys, 
-                                                                       coincident, 
-                                                                       sStoreSplitPolys);
+        // subdivide polygons with plane
+        mStat.splits += 
+                interior->SplitPolygons(polys, frontPolys, backPolys, 
+                                                                coincident, sStoreSplitPolys);
 
         BspInterior *parent = leaf->GetParent();
@@ -995 +1011 @@
 Plane3 BspTree::SelectPlane(BspLeaf *leaf, 
                                                         PolygonContainer &polys, 
-                                                        const RayContainer &rays)
+                                                        const BoundedRayContainer &rays)
 {
         if (polys.empty())
@@ -1014 +1030 @@
                 return Plane3(norm, position);
         }
-
+        
         if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
-                ((int)polys.size() > sTermMaxPolysForAxisAligned))
+                ((int)polys.size() > sTermMaxPolysForAxisAligned) &&
+                ((int)rays.size() > sTermMaxRaysForAxisAligned) &&
+                ((sTermMaxObjectsForAxisAligned < 0) || 
+                  (Polygon3::CountIntersectables(polys) > sTermMaxObjectsForAxisAligned)))
         {
                 Plane3 plane;
@@ -1034 +1053 @@
 
 Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer &polys,
-                                                                          const RayContainer &rays,
+                                                                          const BoundedRayContainer &rays,
                                                                           const int maxTests)
 {
@@ -1093 +1112 @@
         int totalViewCells = 0;
 
-        // needed for balanced view cells criterium
+        // need three unique ids for each type of view cell
+        // for balanced view cells criterium
         ViewCell::NewMail();
         const int backId = ViewCell::sMailId;
@@ -1206 +1226 @@
                 minT = 0;
 
-        //Debug << "ray intersections " << ray.intersections.size() << endl;
         // bound ray or line segment
         if ((ray.GetType() == Ray::LOCAL_RAY) && 
@@ -1219 +1238 @@
 
 float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
-                                                          const RayContainer &rays) const
+                                                          const BoundedRayContainer &rays) const
 {
         float val = 0;
@@ -1226 +1245 @@
         float sumRaySplits = 0;
 
-        RayContainer::const_iterator rit, rit_end = rays.end();
+        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
 
         for (rit = rays.begin(); rit != rays.end(); ++ rit)
         {
-                Ray *ray = *rit;
-
-                float minT, maxT;
-                if (!BoundRay(*ray, minT, maxT))
-                        continue;
+                Ray *ray = (*rit)->mRay;
+                const float minT = (*rit)->mMinT;
+                const float maxT = (*rit)->mMaxT;
 
                 const int classification = 
@@ -1263 +1280 @@
 float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
                                                           const PolygonContainer &polys,                                                          
-                                                          const RayContainer &rays) const
+                                                          const BoundedRayContainer &rays) const
 {
         float val = 0;
@@ -1326 +1343 @@
 
         //-- termination criteria for axis aligned split
-        environment->GetFloatValue("BspTree.Termination.ct_div_ci", sCt_div_ci);
-        environment->GetFloatValue("BspTree.Termination.maxCostRatio", sMaxCostRatio);
-        environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned", 
+        environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", sCt_div_ci);
+        environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", sMaxCostRatio);
+        environment->GetIntValue("BspTree.Termination.AxisAligned.maxPolys", 
                                                          sTermMaxPolysForAxisAligned);
-        
+        environment->GetIntValue("BspTree.Termination.AxisAligned.maxRays", 
+                                                         sTermMaxRaysForAxisAligned);
+        environment->GetIntValue("BspTree.Termination.AxisAligned.maxObjects", 
+                                                         sTermMaxObjectsForAxisAligned);
         //-- partition criteria
         environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
         environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
-        environment->GetFloatValue("BspTree.splitBorder", sSplitBorder);
+        environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder);
         
         environment->GetBoolValue("BspTree.storeSplitPolys", sStoreSplitPolys);
@@ -1340 +1360 @@
         environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
         Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
+
+        environment->GetIntValue("ViewCells.minPvsDif", sMinPvsDif);
 
     Debug << "BSP max depth: " << sTermMaxDepth << endl;
@@ -1440 +1462 @@
         float maxt, mint;
 
+        if (!BoundRay(ray, mint, maxt))
+                return 0;
+
         Intersectable::NewMail();
 
-        BoundRay(ray, mint, maxt);
-        
         Vector3 entp = ray.Extrap(mint);
         Vector3 extp = ray.Extrap(maxt);
@@ -1458 +1481 @@
                         Plane3 *splitPlane = in->GetPlane();
 
-                        float t = 0;
-                        bool coplanar = false;
-                
                         int entSide = splitPlane->Side(entp);
                         int extSide = splitPlane->Side(extp);
@@ -1494 +1514 @@
 
                         // find intersection of ray segment with plane
-                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
+                        float t;
+                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &t);
+                        maxt *= t;
                         
                 } else // reached leaf => intersection with view cell
@@ -1502 +1524 @@
                         if (!leaf->mViewCell->Mailed())
                         {
-                                ray.viewCells.push_back(leaf->mViewCell);
+                                ray.bspLeaves.push_back(leaf);
                                 leaf->mViewCell->Mail();
                                 ++ hits;
@@ -1514 +1536 @@
                         mint = maxt; // NOTE: need this?
 
-                         if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
+                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
                                 break;
 
@@ -1522 +1544 @@
                         extp = s.mExitPoint;
                         maxt = s.mMaxT;
-
-                        //Debug << "leaf: new entrypt: " << entp << " new extp: " << extp << endl;
 
                         tStack.pop();
@@ -1577 +1597 @@
 }
 
-int BspTree::MergeViewCells()
-{
-        stack<BspNode *> nodeStack;
-        nodeStack.push(mRoot);
-
-        BspLeaf *storedLeaf = NULL;
-
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
-                nodeStack.pop();
-
-                if (node->IsLeaf()) 
-                {
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
-
-                        if (storedLeaf)
-                                MergeLeafs(leaf, storedLeaf);
-
-                        // store current leaf
-                        storedLeaf = leaf;
-                }
-                else 
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        nodeStack.push(interior->mFront);
-                        nodeStack.push(interior->mBack);
-                }
-        }
-        return 0;
-}
-
-void BspTree::MergeLeafs(BspLeaf *front, BspLeaf *back) const
-{
-        //std::merge(front->mPvs.mEntries.begin(), back->mPvs.mEntries.begin());
-        ViewCell *viewCell = ViewCell::MergeViewCells(*front->mViewCell, *back->mViewCell);
-        //viewCell->GetPvs().Merge(front->mViewCell->GetPvs(), back->mViewCell->GetPvs());
-
-        if (viewCell)
-        {
-                DEL_PTR(front->mViewCell);
-                DEL_PTR(back->mViewCell);
-
-                front->SetViewCell(viewCell);
-                back->SetViewCell(viewCell);
-        }
+
+bool BspTree::MergeViewCells(BspLeaf *front, BspLeaf *back) const
+{
+        ViewCell *viewCell = ViewCell::Merge(*front->mViewCell, *back->mViewCell);
+        
+        if (!viewCell)
+                return false;
+
+        DEL_PTR(front->mViewCell);
+        DEL_PTR(back->mViewCell);
+
+        front->SetViewCell(viewCell);
+        back->SetViewCell(viewCell);
+
+        return true;
+}
+
+bool BspTree::ShouldMerge(BspLeaf *front, BspLeaf *back) const
+{
+        if (front->mViewCell->GetPvs().Diff(back->mViewCell->GetPvs()) < 
+                sMinPvsDif)
+                return true;
+        
+        if (back->mViewCell->GetPvs().Diff(front->mViewCell->GetPvs()) < 
+                sMinPvsDif)
+                return true;
+
+        return false;
 }
 
@@ -1637 +1638 @@
 
 int BspTree::SplitRays(const Plane3 &plane,
-                                           RayContainer &rays, 
-                                           RayContainer &frontRays, 
-                                           RayContainer &backRays)
+                                           BoundedRayContainer &rays, 
+                                           BoundedRayContainer &frontRays, 
+                                           BoundedRayContainer &backRays)
 {
         int splits = 0;
@@ -1645 +1646 @@
         while (!rays.empty())
         {
-                Ray *ray = rays.back();
+                BoundedRay *bRay = rays.back();
+                Ray *ray = bRay->mRay;
                 rays.pop_back();
-
-                //-- ray-plane intersection
-                float maxT, minT;
-        
-                if (!BoundRay(*ray, minT, maxT))
-                        continue;
-                                
-                const int classification = ray->ClassifyPlane(plane, minT, maxT);
                 
-                ray->SetId(classification);
-
-                switch (classification)
+                const int cf = 
+                        ray->ClassifyPlane(plane, bRay->mMinT, bRay->mMaxT);
+                
+                ray->SetId(cf);
+
+                switch (cf)
                 {
                 case Ray::COINCIDENT:
+                        frontRays.push_back(bRay);
                         break;
                 case Ray::BACK:
-                        backRays.push_back(ray);
+                        backRays.push_back(bRay);
                         break;
                 case Ray::FRONT:
-                        frontRays.push_back(ray);
+                        frontRays.push_back(bRay);
                         break;
                 case Ray::FRONT_BACK:
-                        ray->SetId(Ray::FRONT_BACK);
-                        backRays.push_back(ray);
-                        ++ splits;                      
+                        {
+                                // find intersection of ray segment with plane
+                                const Vector3 extp = ray->Extrap(bRay->mMaxT);
+                                const float t = plane.FindT(ray->GetLoc(), extp);
+                                
+                                const float newT = t * bRay->mMaxT;
+
+                                frontRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
+                                backRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
+
+                                DEL_PTR(bRay);
+
+                                ++ splits;
+                        }
                         break;
                 case Ray::BACK_FRONT:
-                        frontRays.push_back(ray);
-                        ++ splits;
+                        {
+                                // find intersection of ray segment with plane
+                                const Vector3 extp = ray->Extrap(bRay->mMaxT);
+                                const float t = plane.FindT(ray->GetLoc(), extp);
+                                const float newT = t * bRay->mMaxT;
+
+                                backRays.push_back(new BoundedRay(ray, bRay->mMinT, newT));
+                                frontRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT));
+                                
+                                DEL_PTR(bRay);
+
+                                ++ splits;
+                        }
                         break;
                 default:
@@ -1686 +1706 @@
 }
 
-void BspTree::ExtractSplitPlanes(BspNode *n, vector<Plane3 *> &planes, vector<bool> &sides) const
+void BspTree::ExtractSplitPlanes(BspNode *n, 
+                                                                 vector<Plane3 *> &planes, 
+                                                                 vector<bool> &sides) const
 {
         BspNode *lastNode;
@@ -1692 +1714 @@
         {
                 lastNode = n;
+
+                // want to get planes defining geometry of this node => don't take
+                // split plane of node itself
                 n = n->GetParent();
                 
@@ -1705 +1730 @@
 }
 
+struct Candidate
+{
+        Polygon3 *mPoly;
+        Plane3 mPlane;
+        bool mSide;
+
+        Candidate(Polygon3 *poly, const Plane3 &plane, const bool &side):
+        mPoly(poly), mPlane(plane), mSide(side)
+        {}
+};
+
+void BspTree::AddHalfspace(PolygonContainer &cell, 
+                                                   vector<Plane3> &planes,
+                                                   vector<bool> &sides,
+                                                   const Plane3 &halfspace, 
+                                                   const bool side) const
+{
+        Polygon3 *poly = GetBoundingBox().CrossSection(halfspace);
+
+        bool inside = true;
+
+        // polygon is split by all other planes
+        for (int i = 0; (i < planes.size()) && inside; ++ i)
+        {
+                VertexContainer splitPts;
+                Polygon3 *frontPoly, *backPoly;
+
+                const int cf = poly->ClassifyPlane(planes[i]);
+                        
+                // split new polygon with all previous planes
+                switch (cf)
+                {
+                        case Polygon3::SPLIT:
+                                frontPoly = new Polygon3();
+                                backPoly = new Polygon3();
+
+                                poly->Split(planes[i], *frontPoly, *backPoly, splitPts);
+                                DEL_PTR(poly);
+
+                                if(sides[i] == true)
+                                {
+                                        poly = frontPoly;
+                                        DEL_PTR(backPoly);
+                                }
+                                        else
+                                        {
+                                                poly = backPoly;
+                                                DEL_PTR(frontPoly);
+                                        }
+                                        inside = true;
+                                        break;
+                        case Polygon3::BACK_SIDE:
+                                if (sides[i]) 
+                                        inside = false;
+                                break;
+                        case Polygon3::FRONT_SIDE:
+                                if (!sides[i])
+                                        inside = false;
+                                break;
+                        default:
+                                break;
+                }
+        }
+
+        //-- plane poly splits all other candidates
+
+    // some polygons may fall out => rebuild cell
+        vector<Candidate> candidates;
+
+        for (int i = 0; i < (int)cell.size(); ++ i)
+        {
+                candidates.push_back(Candidate(cell[i], planes[i], sides[i]));
+        }
+
+        cell.clear();
+        planes.clear();
+        sides.clear();
+
+        for (int i = 0; i < (int)candidates.size(); ++ i)
+        {
+                bool candidateInside = true;
+
+                VertexContainer splitPts;
+                Polygon3 *frontPoly, *backPoly;
+
+                const int cf = poly->ClassifyPlane(halfspace);
+                        
+                // split new polygon with all previous planes
+                switch (cf)
+                {
+                        case Polygon3::SPLIT:
+                                frontPoly = new Polygon3();
+                                backPoly = new Polygon3();
+
+                                poly->Split(halfspace, *frontPoly, *backPoly, splitPts);
+                                DEL_PTR(candidates[i].mPoly);
+
+                                if (sides[i] == true)
+                                {
+                                        candidates[i].mPoly = frontPoly;
+                                        DEL_PTR(backPoly);
+                                }
+                                else
+                                {
+                                        candidates[i].mPoly = backPoly;
+                                        DEL_PTR(frontPoly);
+                                }
+                                inside = true;
+                                break;
+                        case Polygon3::BACK_SIDE:
+                                if (candidates[i].mSide) 
+                                        candidateInside = false;
+                                break;
+                        case Polygon3::FRONT_SIDE:
+                                if (!candidates[i].mSide)
+                                        candidateInside = false;
+                                break;
+                        default:
+                                break;
+                }
+                
+                if (candidateInside)
+                {
+                        cell.push_back(candidates[i].mPoly);
+                        sides.push_back(candidates[i].mSide);
+                        planes.push_back(candidates[i].mPlane);
+                }
+                else
+                {
+                        DEL_PTR(candidates[i].mPoly);
+                }
+        }
+
+        //-- finally add polygon
+        if (inside)
+        {
+                cell.push_back(poly);
+                planes.push_back(halfspace);
+                sides.push_back(side);
+        }
+        else
+        {
+                DEL_PTR(poly);
+        }
+}
+
+
 void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
 {
@@ -1716 +1888 @@
         PolygonContainer candidatePolys;
 
-        // bounded plane is added to the polygons
+        // bounded planes are added to the polygons
         for (int i = 0; i < (int)planes.size(); ++ i)
         {
@@ -1722 +1894 @@
         }
 
+        // add faces of bounding box (also could be faces of the cell)
         for (int i = 0; i < 6; ++ i)
         {
@@ -1736 +1909 @@
                 bool inside = true;
 
-                // polygon is split with all other planes
+                // polygon is split by all other planes
                 for (int j = 0; (j < planes.size()) && inside; ++ j)
                 {
@@ -1747 +1920 @@
                         Polygon3 *frontPoly, *backPoly;
 
-                        int cf = candidatePolys[i]->ClassifyPlane(*plane);
+                        const int cf = candidatePolys[i]->ClassifyPlane(*plane);
                         
-                        // split new polygon with all previous planes
-                        switch(cf)
+                        switch (cf)
                         {
                                 case Polygon3::SPLIT:
@@ -1756 +1928 @@
                                         backPoly = new Polygon3();
 
-                                        candidatePolys[i]->Split(*plane, *frontPoly, *backPoly, splitPts);
+                                        candidatePolys[i]->Split(*plane, *frontPoly, 
+                                                                                         *backPoly, splitPts);
                                         DEL_PTR(candidatePolys[i]);
 
@@ -1835 +2008 @@
                                 if (isAdjacent)
                                         neighbors.push_back(dynamic_cast<BspLeaf *>(node));
+
+                                CLEAR_CONTAINER(neighborCandidate);
                         }
                 }
@@ -1857 +2032 @@
         }
         
+        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;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -14 +14 @@
 class Ray;
 
+/** Data structure used for optimized ray casting.
+*/
 struct BspRayTraversalData 
 {
@@ -26 +28 @@
         {}
 };
+
+/** Data used for passing ray data down the tree.
+*/
+struct BoundedRay
+{
+        Ray *mRay;
+        float mMinT;
+        float mMaxT;
+                
+        BoundedRay(): mMinT(0), mMaxT(1e6), mRay(NULL)
+        {}
+        BoundedRay(Ray *r, float minT, float maxT):
+        mRay(r), mMinT(minT), mMaxT(maxT)
+        {}
+};
+
+typedef vector<BoundedRay *> BoundedRayContainer;
 
 class BspTreeStatistics
@@ -230 +249 @@
                 @param storeRays if ray set should be stored in view cell
         */
-        void BspLeaf::GenerateViewCell(const RayContainer &rays, 
-                                                           int &sampleContributions,
-                                                           int &contributingSamples,
-                                                           const bool storeRays = false);
+        void GenerateViewCell(const BoundedRayContainer &rays, 
+                                              int &sampleContributions,
+                                                  int &contributingSamples,
+                                                  const bool storeRays = false);
 
 protected:
@@ -246 +265 @@
 {
 public:
-                
+        
         /** Additional data which is passed down the BSP tree during traversal.
         */
@@ -260 +279 @@
                 ViewCell *mViewCell;
                 /// rays piercing this node
-                RayContainer *mRays;
+                BoundedRayContainer *mRays;
 
                 BspTraversalData():
@@ -274 +293 @@
                                                  const int depth, 
                                                  ViewCell *viewCell,
-                                                 RayContainer *rays): 
+                                                 BoundedRayContainer *rays): 
                 mNode(node), 
                 mPolygons(polys), 
@@ -344 +363 @@
         int CastRay(Ray &ray);
 
+        /** Set to true if new view cells shall be generated in each leaf.
+        */
+        void SetGenerateViewCells(int generateViewCells);
+
+        /// bsp tree construction types
+        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_RAYS};
+
+        /** Returns statistics.
+        */
+        BspTreeStatistics &GetStat();
+
+        /** finds neighbouring leaves of this tree node.
+        */
+        int FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 
+                                          const bool onlyUnmailed) const;
+
+        /** Extracts geometry associated with the split plane leading to this node.
+        */
+        void ConstructGeometry(BspNode *n, PolygonContainer &polys) const;
+        
+        /** Returns random leaf of BSP tree.
+                @param halfspace defines the halfspace from which the leaf is taken.
+        */
+        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
+
+        /** Returns random leaf of BSP tree.
+                @param onlyUnmailed if only unmailed leaves should be returned.
+        */
+        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
+
+        /** Adds halfspace to cell definition.
+                @param side indicates which side of halfspace is added
+        */
+        void AddHalfspace(PolygonContainer &cell, 
+                                          vector<Plane3> &planes,
+                                          vector<bool> &sides,
+                                          const Plane3 &halfspace, 
+                                          const bool side) const;
+
+        /** Returns true if merge criteria are reached.
+        */
+    bool ShouldMerge(BspLeaf *front, BspLeaf *back) const;
+
         /** Merges view cells based on some criteria
             E.g., empty view cells can pe purged, view cells which have 
-                a very similar PVS can be merged to one larger view cell farther up 
-                in the BSP tree.
-                @returns the number of merged view cells
-        */
-        int MergeViewCells();
-
-        /** Set to true if new view cells shall be generated in each leaf.
-        */
-        void SetGenerateViewCells(int generateViewCells);
-
-        /// bsp tree construction types
-        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_RAYS};
-
-        /** Returns statistics.
-        */
-        BspTreeStatistics &GetStat();
-
-        /** finds neighbouring leaves of this tree node.
-        */
-        int FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 
-                                          const bool onlyUnmailed) const;
-
-        /** Extracts geometry associated with the split plane leading to this node.
-        */
-        void ConstructGeometry(BspNode *n, PolygonContainer &polys) const;
+                a very similar PVS can be merged to one larger view cell.
+
+                @returns true if merge was successful.
+        */
+        bool MergeViewCells(BspLeaf *front, BspLeaf *back) const;
 
 protected:
@@ -394 +436 @@
         };
 
-        /** Merges view cells of leafs.
-        */
-        void MergeLeafs(BspLeaf *front, BspLeaf *back) const;
-
         /** Evaluates tree stats in the BSP tree leafs.
         */
@@ -413 +451 @@
                 @param rays storesset of rays on which subdivision may be based
         */
-        void Construct(PolygonContainer *polys, RayContainer *rays);
+        void Construct(PolygonContainer *polys, BoundedRayContainer *rays);
 
         /** Selects the best possible splitting plane. 
@@ -424 +462 @@
         Plane3 SelectPlane(BspLeaf *leaf, 
                                            PolygonContainer &polys,
-                                           const RayContainer &ray);
+                                           const BoundedRayContainer &ray);
 
         /** Evaluates the contribution of the candidate split plane.
@@ -435 +473 @@
         float SplitPlaneCost(const Plane3 &candidatePlane,
                                                  const PolygonContainer &polys,                                                  
-                                                 const RayContainer &rays) const;
+                                                 const BoundedRayContainer &rays) const;
 
         /** Strategies where the effect of the split plane is tested
@@ -449 +487 @@
         */
         float SplitPlaneCost(const Plane3 &candidatePlane,
-                                                 const RayContainer &polys) const;
+                                                 const BoundedRayContainer &polys) const;
 
         /** Filters next view cell down the tree and inserts it into the appropriate leaves
@@ -478 +516 @@
                                                            PolygonContainer &backPolys,
                                                            PolygonContainer &coincident,
-                                                           RayContainer &rays,
-                                                           RayContainer &frontRays,
-                                                            RayContainer &backRays);
+                                                           BoundedRayContainer &rays,
+                                                           BoundedRayContainer &frontRays,
+                                                           BoundedRayContainer &backRays);
 
         /** Filters polygons down the tree.
@@ -501 +539 @@
         */
         Plane3 SelectPlaneHeuristics(PolygonContainer &polys, 
-                                                                 const RayContainer &rays,
+                                                                 const BoundedRayContainer &rays,
                                                                  const int maxTests);
 
@@ -597 +635 @@
         */
         int SplitRays(const Plane3 &plane,
-                                  RayContainer &rays, 
-                              RayContainer &frontRays, 
-                                  RayContainer &backRays);
+                                  BoundedRayContainer &rays, 
+                              BoundedRayContainer &frontRays, 
+                                  BoundedRayContainer &backRays);
 
 
@@ -656 +694 @@
         /// BSP tree construction method
         static int sConstructionMethod;
-        /// maximal number of polygons where we do axis aligned splits
+        /// maximal number of polygons for axis aligned split
         static int sTermMaxPolysForAxisAligned;
+        /// maximal number of rays for axis aligned split
+        static int sTermMaxRaysForAxisAligned;
+        /// maximal number of objects for axis aligned split
+        static int sTermMaxObjectsForAxisAligned;
 
         /// axis aligned split criteria
@@ -677 +719 @@
         static bool sStoreSplitPolys;
 
+        /// threshold where view cells are merged
+        static int sMinPvsDif;
+
 private:
         /** Evaluates split plane classification with respect to the plane's 

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h

@@ -50 +50 @@
   ExportPolygon(Polygon3 *poly);
 
-  virtual void ExportPolygons(const PolygonContainer &polys);
+  virtual void 
+  ExportPolygons(const PolygonContainer &polys);
 
   virtual bool