Changeset 1545 for GTP/trunk/Lib

Timestamp:

09/29/06 22:42:25 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BoundingBoxConverter.h (modified) (1 diff)
• Environment.cpp (modified) (4 diffs)
• GvsPreprocessor.cpp (modified) (15 diffs)
• GvsPreprocessor.h (modified) (2 diffs)
• Preprocessor.cpp (modified) (3 diffs)
• Preprocessor.h (modified) (1 diff)
• Preprocessor.vcproj (modified) (2 diffs)
• RayCaster.cpp (modified) (1 diff)
• RayCaster.h (modified) (1 diff)
• ViewCell.cpp (modified) (2 diffs)
• ViewCell.h (modified) (2 diffs)
• ViewCellBsp.cpp (modified) (59 diffs)
• ViewCellBsp.h (modified) (10 diffs)
• ViewCellsManager.cpp (modified) (47 diffs)
• ViewCellsManager.h (modified) (13 diffs)
• VspBspTree.cpp (modified) (3 diffs)
• VspBspTree.h (modified) (1 diff)
• VspTree.cpp (modified) (3 diffs)
• X3dExporter.cpp (modified) (3 diffs)
• X3dParser.cpp (modified) (1 diff)
• main.cpp (modified) (1 diff)

GTP/trunk/Lib/Vis/Preprocessing/src/BoundingBoxConverter.h

@@ -13 +13 @@
 
         IndexedBoundingBox(int idx, const AxisAlignedBox3 &box): IndexedBoundingBoxParent(idx, box)
-        {
-
-        }
+        {}
 };
 

GTP/trunk/Lib/Vis/Preprocessing/src/Environment.cpp

@@ -236 +236 @@
 bool
 Environment::GetParam(const char name,
-                       const int index,
-                       char *value) const
+                                          const int index,
+                                          char *value) const
 {
   int column;
@@ -1522 +1522 @@
                 "0");
 
-        
+        RegisterOption("ViewCells.loadGeometry",
+                optBool, 
+                "view_cells_load_geometry=", 
+                "false");
+        
+        RegisterOption("ViewCells.geometryFilename",
+                optString,
+                "view_cells_geometry_filename=",
+                "viewCellsGeometry.x3d");
+
+        RegisterOption("ViewCells.useBaseTrianglesAsGeometry",
+                optBool, 
+                "view_cells_use_base_triangles_as_geometry=", 
+                "false");
+
+        
+
         /****************************************************************************/
         /*                     Render simulation related options                    */
@@ -1667 +1683 @@
         RegisterOption("BspTree.Visualization.exportSplits",
                 optBool,
-                "bsp_visualization.export_splits",
+                "bsp_visualization.export_splits=",
                 "false");
 
@@ -2495 +2511 @@
                                         "-1");
 
-        RegisterOption("Hierarchy.Construction.useMultiLevelConstruction",
-                                        optBool,
-                                        "hierarchy_construction_use_multilevel_construction=",
+        RegisterOption("Hierarchy.Construction.useMultiLevel",
+                                        optBool,
+                                        "hierarchy_construction_multilevel=",
                                         "false");
 

GTP/trunk/Lib/Vis/Preprocessing/src/GvsPreprocessor.cpp

@@ -9 +9 @@
 #include "RayCaster.h"
 #include "Exporter.h"
+#include "SamplingStrategy.h"
 
 
@@ -24 +25 @@
 
 GvsPreprocessor::GvsPreprocessor(): 
-Preprocessor(), mSamplingType(0), mSampleContriPerPass(0), mTotalSampleContri(0),
-mReverseSamples(0), mBorderSamples(0)
+Preprocessor(), 
+//mSamplingType(SamplingStrategy::DIRECTION_BASED_DISTRIBUTION),
+mSamplingType(SamplingStrategy::DIRECTION_BOX_BASED_DISTRIBUTION),
+mSampleContriPerPass(0), 
+mTotalSampleContri(0),
+mReverseSamples(0), 
+mBorderSamples(0)
 {
         Environment::GetSingleton()->GetIntValue("GvsPreprocessor.totalSamples", mTotalSamples);
@@ -53 +59 @@
 #if 0
         if ((dist - newDist) > mThresHold)
-#else // rather take relative distance
+#else 
+        // rather take relative distance
         if ((dist / newDist) > mThreshold)
 #endif
@@ -62 +69 @@
                         delete newRay;
                 }
-
                 return true;
         }
@@ -79 +85 @@
                 //cout << " h " << mSampleContriPerPass << " " << mSamplesPerPass << " " << mTotalSamples << endl;
                 mRayQueue.push(vssRay);
-                mVssRays.push_back(new VssRay(*vssRay));
-        
-                ++ mSampleContriPerPass;
+                //mVssRays.push_back(new VssRay(*vssRay));
+        ++ mSampleContriPerPass;
 
                 return true;
@@ -179 +184 @@
                 SimpleRay sray(oldRay.mOrigin, p - oldRay.mOrigin);
         
-                VssRay *newRay = mRayCaster->CastSingleRay(sray, mViewSpaceBox);
-
+                VssRay *newRay = mRayCaster->CastRay(sray, mViewSpaceBox, false);
+                //cout << "\np1: " << p1 << "\np : " <<  p << "\np2: " << p2 << endl;
                 if (!newRay) 
                         return 0;
-
+cout << "here42" << endl;
                 const bool enqueued = HandleRay(newRay);
                 
@@ -230 +235 @@
                 simpleRays.AddRay(sr);
         }
-
+#if 0
         VizStruct dummy;
         dummy.enlargedTriangle = new Polygon3(enlargedTriangle);
@@ -236 +241 @@
         //dummy.ray = new VssRay(currentRay);
         vizContainer.push_back(dummy);
+#endif
 
         // cast rays to triangle vertices and determine visibility
@@ -260 +266 @@
 #endif
 
-        mBorderSamples = castRays;
+        mBorderSamples += castRays;
         return castRays;
 }
@@ -322 +328 @@
         VssRayContainer samples;
         CastRays(simpleRays, samples, true);
-        
         // add to ray queue
         EnqueueRays(samples);
 
-        Debug << "generated " <<  numSamples << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+        //Debug << "generated " <<  numSamples << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
 
         return (int)samples.size();
@@ -346 +351 @@
 int GvsPreprocessor::Pass()
 {
-        const int mSampleType = 0;
         // reset samples
         int castSamples = 0;
         mSampleContriPerPass = 0;
-        
+
         while (castSamples < mSamplesPerPass) 
         {       
                 // Ray queue empty => 
-                // cast a number of uniform samples to fill ray Queue
-                castSamples += CastInitialSamples(mInitialSamples, mSampleType);
+                // cast a number of uniform samples to fill ray queue
+                castSamples += CastInitialSamples(mInitialSamples, mSamplingType);
                 castSamples += ProcessQueue();
-                cout << "\ncast " << castSamples << " samples in a processing pass" << endl;
+                //cout << "\ncast " << castSamples << " samples in a processing pass" << endl;
         }
 
@@ -369 +373 @@
 {
         int castSamples = 0;
+        ++ mGvsPass;
 
         while (!mRayQueue.empty()) 
@@ -375 +380 @@
                 VssRay *ray = mRayQueue.top();
                 mRayQueue.pop();
-        
+
                 castSamples += AdaptiveBorderSampling(*ray);
-                
                 delete ray;
         }
@@ -388 +392 @@
 {
         cout << "Gvs Preprocessor started\n" << flush;
-
+        const long startTime = GetTime();
+
+        mViewSpaceBox = mKdTree->GetBox();
         Randomize(0);
-        const long startTime = GetTime();
+        
+        mPass = 0;
+        mGvsPass = 0;
+        mSampleContriPerPass = 0; 
+        mTotalSampleContri = 0;
+        mReverseSamples = 0;
+        mBorderSamples = 0;
+
         int castSamples = 0;
-        mViewSpaceBox = mKdTree->GetBox();
-        
+
         if (!mLoadViewCells)
         {       /// construct the view cells from the scratch
@@ -406 +418 @@
                 ////////
                 //-- stats
-                //cout << "+";
-                cout << "\nsamples cast: " << castSamples << " of " << mTotalSamples << endl;
+                cout << "\nPass " << mPass << " #samples: " << castSamples << " of " << mTotalSamples << endl;
 
                 //mVssRays.PrintStatistics(mStats);
-                mStats << "#Time\n" << TimeDiff(startTime, GetTime())*1e-3 << endl
-                           << "#TotalSamples\n" << castSamples << endl
-                           << "#ContributingSamples\n" << mTotalSampleContri << endl
-                           << "#Reverse samples\n" << mReverseSamples << endl
-                           << "#Border samples\n" << mBorderSamples << endl;
-                                
+                mStats 
+                        << "#Pass\n" << mPass << endl
+                        << "#Time\n" << TimeDiff(startTime, GetTime())*1e-3 << endl
+                        << "#TotalSamples\n" << castSamples << endl
+                        << "#ScDiff\n" << mSampleContriPerPass << endl
+                        << "#SamplesContri\n" << mTotalSampleContri << endl
+                        << "#ReverseSamples\n" << mReverseSamples << endl
+                        << "#BorderSamples\n" << mBorderSamples << endl                 
+                        << "#GvsRuns\n" << mGvsPass << endl;
+
 
                 mViewCellsManager->PrintPvsStatistics(mStats);
                 // ComputeRenderError();
-        }
-
-        Visualize();    
+                ++ mPass;
+        }
+
+        cout << 2 * castSamples / (1e3f * TimeDiff(startTime, GetTime())) << "M rays/s" << endl;
+        Visualize();
+
         return true;
 }

GTP/trunk/Lib/Vis/Preprocessing/src/GvsPreprocessor.h

@@ -116 +116 @@
 
         void Visualize();
+
         //////////////////////
 
@@ -121 +122 @@
 
         int mSamplesPerPass;
+        int mTotalSamples;
+        int mInitialSamples;
+
         RayQueue mRayQueue; 
         int mSamplingType;
-        int mTotalSamples;
-        int mInitialSamples;
+
         AxisAlignedBox3 mViewSpaceBox;
         float mEps;
         float mThreshold;
         VssRayContainer mVssRays;
+        
+        ///////////
+        // stats
         int mSampleContriPerPass;
         int mTotalSampleContri;
         int mReverseSamples;
         int mBorderSamples;
+        int mGvsPass;
 };
 

GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.cpp

@@ -396 +396 @@
 Preprocessor::Export( const string filename,
                                           const bool scene,
-                                          const bool kdtree,
-                                          const bool bsptree
+                                          const bool kdtree
                                           )
 {
@@ -403 +402 @@
         
   if (exporter) {
-    if (0 && scene)
+    if (2 && scene)
       exporter->ExportScene(mSceneGraph->GetRoot());
 
-    if (0 && kdtree) {
+    if (1 && kdtree) {
       exporter->SetWireframe();
       exporter->ExportKdTree(*mKdTree);
     }
-
-        if (0 && bsptree) {
-                //exporter->SetWireframe();
-                exporter->ExportBspTree(*mBspTree);
-        }
 
     delete exporter;
@@ -447 +441 @@
                 // default view space is the extent of the scene
                 mViewCellsManager->SetViewSpaceBox(mSceneGraph->GetBox());
+
+                bool loadVcGeometry;
+                Environment::GetSingleton()->GetBoolValue("ViewCells.loadGeometry", loadVcGeometry);
+
+                bool extrudeBaseTriangles;
+                Environment::GetSingleton()->GetBoolValue("ViewCells.useBaseTrianglesAsGeometry", extrudeBaseTriangles);
+
+                char vcGeomFilename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.geometryFilename", vcGeomFilename);
+                
+                if (mViewCellsManager->GetType() == ViewCellsManager::BSP)
+                {
+                        if (!mViewCellsManager->LoadViewCellsGeometry(vcGeomFilename, extrudeBaseTriangles))
+                        {
+                                cerr << "loading view cells geometry failed" << endl;
+                        }
+                }
+                else
+                {
+                        cerr << "loading view cells geometry is not implemented for this manager" << endl;
+                }
         }
         

GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.h

@@ -98 +98 @@
   SamplingStrategy *GenerateSamplingStrategy(const int strategyId) const;
 
+  /** Export preprocessor data.
+  */
   bool Export(
                 const string filename, 
                 const bool scene, 
-                const bool kdtree, 
-                const bool bsptree);  
+                const bool kdtree);  
   
   virtual void KdTreeStatistics(ostream &s);

GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.vcproj

@@ -748 +748 @@
                                 RelativePath="..\src\X3dParser.h">
                         </File>
-                        <File
-                                RelativePath="..\src\X3dParserXerces.h">
-                        </File>
                 </Filter>
                 <Filter
@@ -788 +785 @@
                         <File
                                 RelativePath="..\include\ViewCell.h">
+                        </File>
+                        <File
+                                RelativePath="..\src\X3dParserXerces.h">
                         </File>
                 </Filter>

GTP/trunk/Lib/Vis/Preprocessing/src/RayCaster.cpp

@@ -22 +22 @@
 
 
-VssRay *RayCaster::CastSingleRay(const SimpleRay &simpleRay,
-                                                                 const AxisAlignedBox3 &box)
+VssRay *RayCaster::CastRay(const SimpleRay &simpleRay,
+                                                   const AxisAlignedBox3 &box,
+                                                   const bool castDoubleRay)
 {
         VssRayContainer rays;
-        CastRay(simpleRay, rays, box, false);
+        CastRay(simpleRay, rays, box, castDoubleRay);
 
         if (!rays.empty())

GTP/trunk/Lib/Vis/Preprocessing/src/RayCaster.h

@@ -41 +41 @@
 
         /** Wrapper for casting single ray.
+                @returns ray or NULL if invalid
         */
-        VssRay *CastSingleRay(
+        VssRay *CastRay(
                 const SimpleRay &simpleRay,
-            const AxisAlignedBox3 &box
+            const AxisAlignedBox3 &box,
+                const bool castDoubleRay
                 );
 

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.cpp

@@ -273 +273 @@
 
         for (it = mChildren.begin(); it != it_end; ++ it)
+        {
                 delete (*it);
+        }
 }
 
@@ -1856 +1858 @@
         int pvsSize = 0;
 
+        /////////////
         //-- compressed pvs
 

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.h

@@ -232 +232 @@
 
 
-        ////////////////////////////////////////////
+        ////////////////
         //-- mailing stuff
 
@@ -255 +255 @@
         static int sMailId;
         static int sReservedMailboxes;
-        //int mMailbox;
-        
+        
+
 protected:
 
         /// parent view cell in the view cell hierarchy
         ViewCellInterior *mParent;
+        
         /// the potentially visible objects
         ObjectPvs mPvs;
+        
         /// the volume of this view cell
         float mVolume;
         
+        /// the area of this view cell
         float mArea;
+
         /// the cost that were paid for merging this view cells from two others.
         float mMergeCost;
+        
         /// if the view cell is valid view space
         bool mValid;
+        
         /// color used for consistent visualization
         RgbColor mColor;
+        
         /// store pvs size, used for evaluation purpose when pvss are stored only in the leaves
         int mPvsSize;

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.cpp

@@ -17 +17 @@
 namespace GtpVisibilityPreprocessor {
 
-
+//////////////
 //-- static members
 
@@ -168 +168 @@
 mRoot(NULL), 
 mUseAreaForPvs(false),
-mGenerateViewCells(true),
-mTimeStamp(1)
+mUsePredefinedViewCells(false),
+mTimeStamp(1),
+mViewCellsTree(NULL),
+ mOutOfBoundsCellPartOfTree(false)
 {
         Randomize(); // initialise random generator for heuristics
-
-        mOutOfBoundsCell = GetOrCreateOutOfBoundsCell();
-
+        mOutOfBoundsCell = new BspViewCell();
+
+        /////////
         //-- termination criteria for autopartition
+
         Environment::GetSingleton()->GetIntValue("BspTree.Termination.maxDepth", mTermMaxDepth);
         Environment::GetSingleton()->GetIntValue("BspTree.Termination.minPvs", mTermMinPvs);
@@ -184 +187 @@
         Environment::GetSingleton()->GetFloatValue("BspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
 
+        
+        /////////
         //-- factors for bsp tree split plane heuristics
+
         Environment::GetSingleton()->GetFloatValue("BspTree.Factor.verticalSplits", mVerticalSplitsFactor);
         Environment::GetSingleton()->GetFloatValue("BspTree.Factor.largestPolyArea", mLargestPolyAreaFactor);
@@ -196 +202 @@
         Environment::GetSingleton()->GetFloatValue("BspTree.Termination.ct_div_ci", mCtDivCi);
 
+
+        ///////////
         //-- termination criteria for axis aligned split
+
         Environment::GetSingleton()->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi);
         Environment::GetSingleton()->GetFloatValue("BspTree.Termination.maxCostRatio", mMaxCostRatio);
@@ -205 +214 @@
         Environment::GetSingleton()->GetIntValue("BspTree.Termination.AxisAligned.minObjects", 
                                                          mTermMinObjectsForAxisAligned);
+        
+        
+        //////////////
         //-- partition criteria
+
         Environment::GetSingleton()->GetIntValue("BspTree.maxPolyCandidates", mMaxPolyCandidates);
         Environment::GetSingleton()->GetIntValue("BspTree.maxRayCandidates", mMaxRayCandidates);
@@ -219 +232 @@
         mSubdivisionStats.open(subdivisionStatsLog);
 
+        /////////////////////7
+
+        Debug << "BSP options: " << endl;
     Debug << "BSP max depth: " << mTermMaxDepth << endl;
         Debug << "BSP min PVS: " << mTermMinPvs << endl;
@@ -401 +417 @@
 {
         DEL_PTR(mRoot);
-
-        // TODO must be deleted if used!!
-        //if (mGenerateViewCells) DEL_PTR(mOutOfBoundsCell);
-}
-
-BspViewCell *BspTree::GetOutOfBoundsCell()
-{
-        return mOutOfBoundsCell;
+        
+        if (!mOutOfBoundsCellPartOfTree)
+        {
+                // out of bounds cell not part of tree =>
+                // delete manually
+                DEL_PTR(mOutOfBoundsCell);
+        }
 }
 
@@ -418 +433 @@
 
 
-BspViewCell *BspTree::GetOrCreateOutOfBoundsCell()
-{
-        if (!mOutOfBoundsCell)
-        {
-                mOutOfBoundsCell = new BspViewCell();
-                mOutOfBoundsCell->SetId(-1);
-                mOutOfBoundsCell->SetValid(false);
-        }
-
-        return mOutOfBoundsCell;
+void BspTree::SetViewCellsTree(ViewCellsTree *viewCellsTree)
+{
+        mViewCellsTree = viewCellsTree;
 }
 
@@ -433 +441 @@
 void BspTree::InsertViewCell(ViewCellLeaf *viewCell)
 {
+        // don't generate new view cell, insert this view cell
+        mUsePredefinedViewCells = true;
         PolygonContainer *polys = new PolygonContainer();
 
-        // don't generate new view cell, insert this one
-        mGenerateViewCells = false;
         // extract polygons that guide the split process
         mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
-        mBox.Include(viewCell->GetBox()); // add to BSP aabb
+        mBbox.Include(viewCell->GetBox()); // add to BSP aabb
 
         InsertPolygons(polys);
@@ -459 +467 @@
                                                                  new BoundedRayContainer(), 
                                                                  0, 
-                                                                 mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
+                                                                 mUseAreaForPvs ? mBbox.SurfaceArea() : mBbox.GetVolume(), 
                                                                  new BspNodeGeometry()));
 
@@ -472 +480 @@
                         BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
 
+                        ///////////////////
                         //-- filter view cell polygons down the tree until a leaf is reached
                         if (!tData.mPolygons->empty())
@@ -489 +498 @@
                                 
                                 // extract view cells associated with the split polygons
-                                ViewCellLeaf *frontViewCell = GetOrCreateOutOfBoundsCell();
-                                ViewCellLeaf *backViewCell = GetOrCreateOutOfBoundsCell();
+                                ViewCellLeaf *frontViewCell = mOutOfBoundsCell;
+                                ViewCellLeaf *backViewCell = mOutOfBoundsCell;
                         
                                 BspTraversalData frontData(interior->GetFront(), 
@@ -498 +507 @@
                                                                                    tData.mRays,
                                                                                    tData.mPvs,
-                                                                                   mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
+                                                                                   mUseAreaForPvs ? mBbox.SurfaceArea() : mBbox.GetVolume(), 
                                                                                    new BspNodeGeometry());
 
@@ -507 +516 @@
                                                                                   tData.mRays,
                                                                                   tData.mPvs,
-                                                                                   mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
+                                                                                   mUseAreaForPvs ? mBbox.SurfaceArea() : mBbox.GetVolume(), 
                                                                                   new BspNodeGeometry());
 
-                                if (!mGenerateViewCells)
+                                if (mUsePredefinedViewCells)
                                 {
                                         ExtractViewCells(frontData,
@@ -558 +567 @@
                 }
                 else
+                {
                         DEL_PTR(poly);
+                }
         }
         return (int)mesh->mFaces.size();
@@ -572 +583 @@
   
         int polysSize = 0;
-
+        cout << "here55 " << mBbox << endl;
+        
+cout << "here99";
         for (int i = 0; i < limit; ++ i)
-        {
-                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
-                {
-                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
-                        polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
-                }
-        }
-
+        {cout << "q";
+        Mesh *mesh = viewCells[i]->GetMesh();
+                if (mesh) 
+                {cout << "w";
+                        // copy the mesh into polygons and add to BSP tree aabb
+                        mBbox.Include(viewCells[i]->GetBox()); 
+                        polysSize += AddMeshToPolygons(mesh, polys, viewCells[i]);
+                }
+        }
+cout << "here155 " << mBbox << endl;
         return polysSize;
 }
@@ -593 +608 @@
         int limit = (maxObjects > 0) ? 
                 Min((int)objects.size(), maxObjects) : (int)objects.size();
-  
+  cout << "here88";
         for (int i = 0; i < limit; ++i)
-        {
+        {cout << "e";
                 Intersectable *object = objects[i];
-
                 Mesh *mesh = NULL;
 
@@ -616 +630 @@
                                 mesh = new Mesh();
                                 mi->GetTransformedMesh(*mesh);
-                                
                                 break;
                         }
@@ -624 +637 @@
                 }
                 
-        if (mesh) // copy the mesh data to polygons
-                {
-                        if (addToBbox)
-                                mBox.Include(object->GetBox()); // add to BSP tree aabb
-                                
-                        AddMeshToPolygons(mesh, polys, mOutOfBoundsCell);
-
-                        // cleanup
-                        if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
-                                DEL_PTR(mesh);
+        if (!mesh) continue;
+                // copy the mesh data to polygons
+                if (addToBbox)
+                {cout << "b";
+                        mBbox.Include(object->GetBox()); // add to BSP tree aabb
+                }
+
+                AddMeshToPolygons(mesh, polys, mOutOfBoundsCell);
+
+                // cleanup
+                if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
+                {
+                        DEL_PTR(mesh);
                 }       
         }
@@ -640 +656 @@
 }
 
-
+        
 void BspTree::Construct(const ViewCellContainer &viewCells)
 {
+        cout << "here5500000000" << endl;
+        // construct hierarchy over the given view cells
+        mUsePredefinedViewCells = true;
+
         mStat.nodes = 1;
-        mBox.Initialize();      // initialise bsp tree bounding box
+        mBbox.Initialize(); // initialise bsp tree bounding box
 
         // copy view cell meshes into one big polygon soup
@@ -650 +670 @@
         mStat.polys = AddToPolygonSoup(viewCells, *polys);
 
-        // view cells are given
-        mGenerateViewCells = false;
+        Exporter *expo = Exporter::GetExporter("dummy2.wrl");
+        expo->ExportPolygons(*polys);
+        delete expo;
         // construct tree from the view cell polygons
         Construct(polys, new BoundedRayContainer());
@@ -659 +680 @@
 void BspTree::Construct(const ObjectContainer &objects)
 {
+        // generate new view cells for this type
+        mUsePredefinedViewCells = false;
+
         mStat.nodes = 1;
-        mBox.Initialize();      // initialise bsp tree bounding box
+        mBbox.Initialize();     // initialise bsp tree bounding box
         
         PolygonContainer *polys = new PolygonContainer();
 
-        mGenerateViewCells = true;
         // copy mesh instance polygons into one big polygon soup
         mStat.polys = AddToPolygonSoup(objects, *polys);
@@ -677 +700 @@
         // preprocess: throw out polygons coincident to the view space box (not needed)
         PolygonContainer boxPolys;
-        mBox.ExtractPolys(boxPolys);
+        mBbox.ExtractPolys(boxPolys);
         vector<Plane3> boxPlanes;
 
@@ -722 +745 @@
 
 
-
 void BspTree::Construct(const RayContainer &sampleRays,
                                                 AxisAlignedBox3 *forcedBoundingBox)
 {
+        // generate new view cells for this contruction type
+        mUsePredefinedViewCells = false;
+
     mStat.nodes = 1;
-        mBox.Initialize();      // initialise BSP tree bounding box
-        
+
         if (forcedBoundingBox)
-                mBox = *forcedBoundingBox;
+        {
+                mBbox = *forcedBoundingBox;
+        }
+        else
+        {
+                mBbox.Initialize(); // initialise BSP tree bounding box 
+        }
 
         PolygonContainer *polys = new PolygonContainer();
@@ -737 +767 @@
         RayContainer::const_iterator rit, rit_end = sampleRays.end();
 
-        // generate view cells
-        mGenerateViewCells = true;
-
         long startTime = GetTime();
-
         Debug << "**** Extracting polygons from rays ****\n";
 
         std::map<Face *, Polygon3 *> facePolyMap;
 
-        //-- extract polygons intersected by the rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
         {
+                //////////////
+                //-- extract polygons intersected by the rays
                 Ray *ray = *rit;
         
@@ -803 +830 @@
         // compute bounding box
         if (!forcedBoundingBox)
-                mBox.Include(*polys);
-
+        {
+                mBbox.Include(*polys);
+        }
+
+        ////////////
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -812 +842 @@
 
                 float minT, maxT;
-                if (mBox.GetRaySegment(*ray, minT, maxT))
+                if (mBbox.GetRaySegment(*ray, minT, maxT))
                         rays->push_back(new BoundedRay(ray, minT, maxT));
         }
@@ -833 +863 @@
                                                 AxisAlignedBox3 *forcedBoundingBox)
 {
+        // generate new view cells for this construction type
+        mUsePredefinedViewCells = false;
+
     mStat.nodes = 1;
-        mBox.Initialize();      // initialise BSP tree bounding box
+        mBbox.Initialize();     // initialise BSP tree bounding box
         
         if (forcedBoundingBox)
-                mBox = *forcedBoundingBox;
+        {
+                mBbox = *forcedBoundingBox;
+        }
 
         BoundedRayContainer *rays = new BoundedRayContainer();
         PolygonContainer *polys = new PolygonContainer();
         
-        mGenerateViewCells = true;
-
         // copy mesh instance polygons into one big polygon soup
         mStat.polys = AddToPolygonSoup(objects, *polys, 0, !forcedBoundingBox);
 
-
+        ///////
+        //-- store rays
         RayContainer::const_iterator rit, rit_end = sampleRays.end();
-
-        //-- store rays
+        
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
         {
@@ -857 +890 @@
 
                 float minT, maxT;
-                if (mBox.GetRaySegment(*ray, minT, maxT))
+                if (mBbox.GetRaySegment(*ray, minT, maxT))
                         rays->push_back(new BoundedRay(ray, minT, maxT));
         }
@@ -870 +903 @@
 {
         BspTraversalStack tStack;
-
         mRoot = new BspLeaf();
 
@@ -880 +912 @@
                                                    polys, 
                                                    0, 
-                                                   GetOrCreateOutOfBoundsCell(), 
+                                                   mOutOfBoundsCell, 
                                                    rays, 
                                                    ComputePvsSize(*rays), 
@@ -886 +918 @@
                                                    geom);
 
-        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
+        mTotalCost = tData.mPvs * tData.mProbability / mBbox.GetVolume();
         mTotalPvsSize = tData.mPvs;
         
@@ -950 +982 @@
 BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
 {
-        //-- terminate traversal  
+        ////////
+        //-- terminate traversal
+
         if (TerminationCriteriaMet(tData))              
         {
@@ -957 +991 @@
                 BspViewCell *viewCell;
 
-                // generate new view cell for each leaf
-                if (mGenerateViewCells)
-                {
+                if (!mUsePredefinedViewCells)
+                {       // generate new view cell for each leaf
                         viewCell = new BspViewCell();
                 }
                 else
                 {
-                        // add view cell to leaf
+                        // add predefined view cell to leaf
                         viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
+                
+                        /// out of bounds cell can be handled as any other cell
+                        if (viewCell == mOutOfBoundsCell)
+                                mOutOfBoundsCellPartOfTree = true;
                 }
 
@@ -979 +1016 @@
                         viewCell->SetVolume(probability);
 
-                //-- add pvs
+                
+                ///////////
+                //-- add pvs contribution of rays
+
                 if (viewCell != mOutOfBoundsCell)
                 {
@@ -989 +1029 @@
                 }
 
-                if (1)
-                        EvaluateLeafStats(tData);
-                
+                if (1)EvaluateLeafStats(tData);
+                
+
+                ////////
                 //-- clean up
-                
+
                 // discard polygons
                 CLEAR_CONTAINER(*tData.mPolygons);
@@ -1006 +1047 @@
         }
 
+        ///////////
         //-- continue subdivision
+
         PolygonContainer coincident;
         
@@ -1019 +1062 @@
                 SubdivideNode(tData, tFrontData, tBackData, coincident);
 
-
         if (1)
         {
@@ -1028 +1070 @@
                 float cBack = (float)tBackData.mPvs * tBackData.mProbability;
 
-                float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
+                float costDecr = (cFront + cBack - cData) / mBbox.GetVolume();
                 
                 mTotalCost += costDecr;
@@ -1040 +1082 @@
         }
 
-        // extract view cells from coincident polygons according to plane normal
-    // only if front or back polygons are empty
-        if (!mGenerateViewCells)
+        // extract view cells from coincident polygons 
+        // with respect to the orientation of their normal
+    // note: if front or back polygons are empty, 
+        // we get the valid in - out classification for the view cell
+
+        if (mUsePredefinedViewCells)
         {
                 ExtractViewCells(tFrontData,
@@ -1057 +1102 @@
         tStack.push(tBackData);
 
-        // cleanup
+        ////////
+        //-- cleanup
+
         DEL_PTR(tData.mNode);
-
         DEL_PTR(tData.mPolygons);
         DEL_PTR(tData.mRays);
@@ -1080 +1126 @@
                 coincident.begin(), it_end = coincident.end();
 
+        //////////
         //-- find first view cells in front and back leafs
+
         for (; !(foundFront && foundBack) && (it != it_end); ++ it)
         {
@@ -1108 +1156 @@
         // select subdivision plane
         BspInterior *interior = new BspInterior(SelectPlane(leaf, tData)); 
-        
         
 #ifdef _DEBUG
@@ -1135 +1182 @@
                                                                            *backData.mGeometry, 
                                                                            interior->mPlane,
-                                                                           mBox,
+                                                                           mBbox,
                                                                            //0.000000000001);
                                                                            mEpsilon);
@@ -1274 +1321 @@
         const float ratio = newCost / oldCost;
 
-
-#if 0
+#ifdef _DEBUG
   Debug << "====================" << endl;
   Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
@@ -1430 +1476 @@
         return Plane3(pt[0], pt[1], pt[2]);
 }
+
 
 Plane3 BspTree::ChooseCandidatePlane3(const BoundedRayContainer &rays) const
@@ -1697 +1744 @@
                                                            geomBack, 
                                                            candidatePlane,
-                                                           mBox,
+                                                           mBbox,
                                                            mEpsilon);
 
@@ -1856 +1903 @@
         if (mSplitPlaneStrategy & VERTICAL_AXIS)
         {
-                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
+                Vector3 tinyAxis(0,0,0); tinyAxis[mBbox.Size().TinyAxis()] = 1.0f;
                 // we put a penalty on the dot product between the "tiny" vertical axis
                 // and the split plane axis
@@ -1915 +1962 @@
 AxisAlignedBox3 BspTree::GetBoundingBox() const
 {
-        return mBox;
+        return mBbox;
 }
 
@@ -1972 +2019 @@
         float maxt, mint;
 
-        if (!mBox.GetRaySegment(ray, mint, maxt))
+        if (!mBbox.GetRaySegment(ray, mint, maxt))
                 return 0;
 
@@ -2194 +2241 @@
                 }
         }
+
+        // also add out of bounds cell
+        if (0 && !mOutOfBoundsCell->Mailed())
+        {
+                mOutOfBoundsCell->Mail();
+                viewCells.push_back(mOutOfBoundsCell);
+        }
+
+        cout << "here555 " << viewCells.size() << endl;
+
 }
 
@@ -2247 +2304 @@
                 case Ray::COINCIDENT: // TODO: should really discard ray?
                         frontRays.push_back(bRay);
-                        //DEL_PTR(bRay);
                         break;
                 case Ray::BACK:
@@ -2322 +2378 @@
                                                                 BspNodeGeometry &vcGeom) const
 {
+        // if false, cannot construct geometry for interior leaf
+        if (!mViewCellsTree)
+                return;
+
         ViewCellContainer leaves;
         mViewCellsTree->CollectLeaves(vc, leaves);
@@ -2364 +2424 @@
 
                 for (int j = 0; j < 4; ++ j)
-                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
+                        vertices.push_back(mBbox.GetFace(i).mVertices[j]);
 
                 Polygon3 *poly = new Polygon3(vertices);
@@ -2533 +2593 @@
                                                                 *bGeom,
                                                                 interior->GetPlane(),
-                                                                mBox,
+                                                                mBbox,
                                                                 //0.0000001f);
                                                                 mEpsilon);
@@ -2807 +2867 @@
         Debug << "leaves in queue: " << numLeaves << endl;
 
-
+#if 0
+        //////////
         //-- collect the leaves which haven't been found by ray casting
-#if 0
         cout << "finding additional merge candidates using geometry" << endl;
         vector<BspLeaf *> leaves;
@@ -2822 +2882 @@
 
 
-
 /***************************************************************/
 /*              BspNodeGeometry Implementation                 */
@@ -3050 +3109 @@
 bool BspNodeGeometry::Valid() const
 {
+        // geometry is degenerated
         if (mPolys.size() < 4)
                 return false;
@@ -3294 +3354 @@
                 int id = -1;
                 if (leaf->GetViewCell() != mOutOfBoundsCell)
+                {
                         id = leaf->GetViewCell()->GetId();
+                }
 
                 stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h

@@ -27 +27 @@
 {
 public:
+        /** Default constructor.
+        */
         BspNodeGeometry()
         {};  
@@ -343 +345 @@
 {
         friend class BspTree;
+
 public:
         /** Standard contructor taking split plane as argument.
@@ -438 +441 @@
         }
         
-
         /// Rays piercing this leaf.
         VssRayContainer mVssRays;
@@ -444 +446 @@
         /// leaf pvs
         ObjectPvs *mPvs;
-
+        
         /// Probability that the view point lies in this leaf
         float mProbability;
@@ -607 +609 @@
         BspNode *GetRoot() const;
 
-        
-        //bool Export(const string filename);
-
         /** Collects the leaf view cells of the tree
                 @param viewCells returns the view cells 
@@ -629 +628 @@
   
         /// bsp tree construction types
-        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
+        //enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
 
         /** Returns statistics.
@@ -678 +677 @@
         bool Export(ofstream &stream);
 
-
-        /** Returns view cell corresponding to 
-                the invalid view space. If it does not exist, it is created.
-        */
-        BspViewCell *GetOutOfBoundsCell();
-
-        ViewCellsTree *mViewCellsTree;
-        
+        /** Pointer to the view cells tree.
+        */
+        void SetViewCellsTree(ViewCellsTree *vct);
+                
 protected:
-
-        // --------------------------------------------------------------
-        // For sorting objects
-        // --------------------------------------------------------------
-        struct SortableEntry
-        {
-                enum {POLY_MIN, POLY_MAX};
-    
-                int type;
-                float value;
-                Polygon3 *poly;
-                SortableEntry() {}
-                SortableEntry(const int t, const float v, Polygon3 *poly): 
-                type(t), value(v), poly(poly) {}
-                
-                bool operator<(const SortableEntry &b) const 
-                {
-                        return value < b.value;
-                }  
-        };
-
-        void ExportNode(BspNode *node, ofstream &stream);
-
-        /** Evaluates tree stats in the BSP tree leafs.
-        */
-        void EvaluateLeafStats(const BspTraversalData &data);
-
-        /** Subdivides node with respect to the traversal data.
-            @param tStack current traversal stack
-                @param tData traversal data also holding node to be subdivided
-                @returns new root of the subtree
-        */
-        BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData);
-
-        /** Constructs the tree from the given list of polygons and rays.
-                @param polys stores set of polygons on which subdivision may be based
-                @param rays storesset of rays on which subdivision may be based
-        */
-        void Construct(PolygonContainer *polys, BoundedRayContainer *rays);
-
-        /** Selects the best possible splitting plane. 
-                @param leaf the leaf to be split
-                @param polys the polygon list on which the split decition is based
-                @param rays ray container on which selection may be based
-                @note the polygons can be reordered in the process
-                @returns the split plane
-        */
-        Plane3 SelectPlane(BspLeaf *leaf, 
-                                           BspTraversalData &data);
-
-        /** Evaluates the contribution of the candidate split plane.
-                
-                @param candidatePlane the candidate split plane
-                @param polys the polygons the split can be based on
-                @param rays the rays the split can be based on
-
-                @returns the cost of the candidate split plane
-        */
-        float SplitPlaneCost(const Plane3 &candidatePlane,
-                                                 BspTraversalData &data) const;
-
-        /** Strategies where the effect of the split plane is tested
-            on all input rays.
-                @returns the cost of the candidate split plane
-        */
-        float SplitPlaneCost(const Plane3 &candidatePlane,
-                                                 const PolygonContainer &polys) const;
-
-        /** Strategies where the effect of the split plane is tested
-            on all input rays.
-
-                @returns the cost of the candidate split plane
-        */
-        float SplitPlaneCost(const Plane3 &candidatePlane, 
-                                                 const BoundedRayContainer &rays,
-                                                 const int pvs,
-                                                 const float probability,
-                                                 const BspNodeGeometry &cell) const;
-
-        /** Filters next view cell down the tree and inserts it into the appropriate leaves
-                (i.e., possibly more than one leaf).
-        */
-        void InsertViewCell(ViewCellLeaf *viewCell);
-        /** Inserts polygons down the tree. The polygons are filtered until a leaf is reached,
-                then further subdivided.
-        */
-        void InsertPolygons(PolygonContainer *polys);
-
-        /** Subdivide leaf.
-                @param leaf the leaf to be subdivided
-                
-                @param polys the polygons to be split
-                @param frontPolys returns the polygons in front of the split plane
-                @param backPolys returns the polygons in the back of the split plane
-                
-                @param rays the polygons to be filtered
-                @param frontRays returns the polygons in front of the split plane
-                @param backRays returns the polygons in the back of the split plane
-
-                @returns the root of the subdivision
-        */
-
-        BspInterior *SubdivideNode(BspTraversalData &tData,
-                                                           BspTraversalData &frontData,
-                                                           BspTraversalData &backData,
-                                                           PolygonContainer &coincident);
-
-        /** Filters polygons down the tree.
-                @param node the current BSP node
-                @param polys the polygons to be filtered
-                @param frontPolys returns the polygons in front of the split plane
-                @param backPolys returns the polygons in the back of the split plane
-        */
-        void FilterPolygons(BspInterior *node, 
-                                                PolygonContainer *polys, 
-                                                PolygonContainer *frontPolys, 
-                                                PolygonContainer *backPolys);
-
-        /** Take 3 ray endpoints, where two are minimum and one a maximum
-                point or the other way round.
-        */
-        Plane3 ChooseCandidatePlane(const BoundedRayContainer &rays) const;
-
-        /** Take plane normal as plane normal and the midpoint of the ray.
-                PROBLEM: does not resemble any point where visibility is likely to change
-        */
-        Plane3 ChooseCandidatePlane2(const BoundedRayContainer &rays) const;
-
-        /** Fit the plane between the two lines so that the plane has equal shortest 
-                distance to both lines.
-        */
-        Plane3 ChooseCandidatePlane3(const BoundedRayContainer &rays) const;
-
-        /** Selects the split plane in order to construct a tree with
-                certain characteristics (e.g., balanced tree, least splits, 
-                2.5d aligned)
-                @param polygons container of polygons
-                @param rays bundle of rays on which the split can be based
-        */
-        Plane3 SelectPlaneHeuristics(BspLeaf *leaf,
-                                                                 BspTraversalData &data);
-
-        /** Extracts the meshes of the objects and adds them to polygons. 
-                Adds object aabb to the aabb of the tree.
-                @param maxPolys the maximal number of objects to be stored as polygons
-                @returns the number of polygons
-        */
-        int AddToPolygonSoup(const ObjectContainer &objects, 
-                                                 PolygonContainer &polys, 
-                                                 int maxObjects = 0,
-                                                 bool addToBbox = true);
-
-        /** Extracts the meshes of the view cells and and adds them to polygons.
-                Adds view cell aabb to the aabb of the tree.
-                @param maxPolys the maximal number of objects to be stored as polygons
-                @returns the number of polygons
-        */
-        int AddToPolygonSoup(const ViewCellContainer &viewCells, 
-                                                 PolygonContainer &polys, 
-                                                 int maxObjects = 0);
-
-        /** Extract polygons of this mesh and add to polygon container.
-                @param mesh the mesh that drives the polygon construction
-                @param parent the parent intersectable this polygon is constructed from
-                @returns number of polygons
-        */
-        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
-
-        /** Helper function which extracts a view cell on the front and the back
-                of the split plane.
-                @param backViewCell returns view cell on the back of the split plane
-                @param frontViewCell returns a view cell on the front of the split plane
-                @param coincident container of polygons coincident to the split plane
-                @param splitPlane the split plane which decides about back and front
-                @param extractBack if a back view cell is extracted
-                @param extractFront if a front view cell is extracted
-        */
-        void ExtractViewCells(BspTraversalData &frontData,
-                                                  BspTraversalData &backData, 
-                                                  const PolygonContainer &coincident,
-                                                  const Plane3 &splitPlane) const;
-        
-        /** Computes best cost ratio for the suface area heuristics for axis aligned
-                splits. This heuristics minimizes the cost for ray traversal.
-                @param polys the polygons guiding the ratio computation
-                @param box the bounding box of the leaf
-                @param axis the current split axis
-                @param position returns the split position
-                @param objectsBack the number of objects in the back of the split plane
-                @param objectsFront the number of objects in the front of the split plane
-        */
-        float BestCostRatio(const PolygonContainer &polys,
-                                                const AxisAlignedBox3 &box,
-                                                const int axis,
-                                                float &position,
-                                                int &objectsBack,
-                                                int &objectsFront) const;
-        
-        /** Sorts split candidates for cost heuristics using axis aligned splits.
-                @param polys the input for choosing split candidates
-                @param axis the current split axis
-                @param splitCandidates returns sorted list of split candidates
-        */
-        void SortSubdivisionCandidates(const PolygonContainer &polys, 
-                                                         const int axis, 
-                                                         vector<SortableEntry> &splitCandidates) const;
-
-        /** Selects an axis aligned split plane.
-                Returns true if split is valied
-        */
-        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
-
-        /** Subdivides the rays into front and back rays according to the split plane.
-                
-                @param plane the split plane
-                @param rays contains the rays to be split. The rays are 
-                           distributed into front and back rays.
-                @param frontRays returns rays on the front side of the plane
-                @param backRays returns rays on the back side of the plane
-                
-                @returns the number of splits
-        */
-        int SplitRays(const Plane3 &plane,
-                                  BoundedRayContainer &rays, 
-                              BoundedRayContainer &frontRays, 
-                                  BoundedRayContainer &backRays);
-
-
-        /** Extracts the split planes representing the space bounded by node n.
-        */
-        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
-
-        /** Adds the object to the pvs of the front and back leaf with a given classification.
-
-                @param obj the object to be added
-                @param cf the ray classification regarding the split plane
-                @param frontPvs returns the PVS of the front partition
-                @param backPvs returns the PVS of the back partition
-        
-        */
-        void AddObjToPvs(Intersectable *obj, const int cf, int &frontPvs, int &backPvs) const;
-
-        /** Computes PVS size induced by the rays.
-        */
-        int ComputePvsSize(const BoundedRayContainer &rays) const;
-
-        /** Returns true if tree can be terminated.
-        */
-        inline bool TerminationCriteriaMet(const BspTraversalData &data) const;
-
-        /** Computes accumulated ray lenght of this rays.
-        */
-        float AccumulatedRayLength(BoundedRayContainer &rays) const;
-
-        /** Splits polygons with respect to the split plane.
-                @param polys the polygons to be split. the polygons are consumed and
-                           distributed to the containers frontPolys, backPolys, coincident.
-                @param frontPolys returns the polygons in the front of the split plane
-                @param backPolys returns the polygons in the back of the split plane
-                @param coincident returns the polygons coincident to the split plane
-
-                @returns the number of splits   
-        */
-        int SplitPolygons(const Plane3 &plane,
-                                          PolygonContainer &polys, 
-                                          PolygonContainer &frontPolys, 
-                                          PolygonContainer &backPolys, 
-                                          PolygonContainer &coincident) const;
-
-        /** Adds ray sample contributions to the PVS.
-                @param sampleContributions the number contributions of the samples
-                @param contributingSampels the number of contributing rays
-                
-        */
-        void AddToPvs(BspLeaf *leaf,
-                                  const BoundedRayContainer &rays, 
-                                  int &sampleContributions,     
-                                  int &contributingSamples);
-
-        /** Preprocesses polygons and throws out all polygons which 
-                are coincident to the view space box faces:
-                These polygons can can be problematic for bsp because they create
-                bad view cells.
-        */
-        void PreprocessPolygons(PolygonContainer &polys);
-
-        /** Returns view cell corresponding to the invalid view space. 
-                If it does not exist, it is created.
-        */
-        BspViewCell *GetOrCreateOutOfBoundsCell();
-
-        /// Pointer to the root of the tree.
-        BspNode *mRoot;
-
-        /// Stores statistics during traversal.
-        BspTreeStatistics mStat;
 
         /// Strategies for choosing next split plane.
@@ -999 +698 @@
                 };
 
+        /** 
+                For sorting polygons
+        */
+        struct SortableEntry
+        {
+                enum {POLY_MIN, POLY_MAX};
+    
+                int type;
+                float value;
+                Polygon3 *poly;
+                SortableEntry() {}
+                SortableEntry(const int t, const float v, Polygon3 *poly): 
+                type(t), value(v), poly(poly) {}
+                
+                bool operator<(const SortableEntry &b) const 
+                {
+                        return value < b.value;
+                }  
+        };
+
+        void ExportNode(BspNode *node, ofstream &stream);
+
+        /** Evaluates tree stats in the BSP tree leafs.
+        */
+        void EvaluateLeafStats(const BspTraversalData &data);
+
+        /** Subdivides node with respect to the traversal data.
+            @param tStack current traversal stack
+                @param tData traversal data also holding node to be subdivided
+                @returns new root of the subtree
+        */
+        BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData);
+
+        /** Constructs the tree from the given list of polygons and rays.
+                @param polys stores set of polygons on which subdivision may be based
+                @param rays storesset of rays on which subdivision may be based
+        */
+        void Construct(PolygonContainer *polys, BoundedRayContainer *rays);
+
+        /** Selects the best possible splitting plane. 
+                @param leaf the leaf to be split
+                @param polys the polygon list on which the split decition is based
+                @param rays ray container on which selection may be based
+                @note the polygons can be reordered in the process
+                @returns the split plane
+        */
+        Plane3 SelectPlane(BspLeaf *leaf, 
+                                           BspTraversalData &data);
+
+        /** Evaluates the contribution of the candidate split plane.
+                
+                @param candidatePlane the candidate split plane
+                @param polys the polygons the split can be based on
+                @param rays the rays the split can be based on
+
+                @returns the cost of the candidate split plane
+        */
+        float SplitPlaneCost(const Plane3 &candidatePlane,
+                                                 BspTraversalData &data) const;
+
+        /** Strategies where the effect of the split plane is tested
+            on all input rays.
+                @returns the cost of the candidate split plane
+        */
+        float SplitPlaneCost(const Plane3 &candidatePlane,
+                                                 const PolygonContainer &polys) const;
+
+        /** Strategies where the effect of the split plane is tested
+            on all input rays.
+
+                @returns the cost of the candidate split plane
+        */
+        float SplitPlaneCost(const Plane3 &candidatePlane, 
+                                                 const BoundedRayContainer &rays,
+                                                 const int pvs,
+                                                 const float probability,
+                                                 const BspNodeGeometry &cell) const;
+
+        /** Filters next view cell down the tree and inserts it into the appropriate leaves
+                (i.e., possibly more than one leaf).
+        */
+        void InsertViewCell(ViewCellLeaf *viewCell);
+        /** Inserts polygons down the tree. The polygons are filtered until a leaf is reached,
+                then further subdivided.
+        */
+        void InsertPolygons(PolygonContainer *polys);
+
+        /** Subdivide leaf.
+                @param leaf the leaf to be subdivided
+                
+                @param polys the polygons to be split
+                @param frontPolys returns the polygons in front of the split plane
+                @param backPolys returns the polygons in the back of the split plane
+                
+                @param rays the polygons to be filtered
+                @param frontRays returns the polygons in front of the split plane
+                @param backRays returns the polygons in the back of the split plane
+
+                @returns the root of the subdivision
+        */
+
+        BspInterior *SubdivideNode(BspTraversalData &tData,
+                                                           BspTraversalData &frontData,
+                                                           BspTraversalData &backData,
+                                                           PolygonContainer &coincident);
+
+        /** Filters polygons down the tree.
+                @param node the current BSP node
+                @param polys the polygons to be filtered
+                @param frontPolys returns the polygons in front of the split plane
+                @param backPolys returns the polygons in the back of the split plane
+        */
+        void FilterPolygons(BspInterior *node, 
+                                                PolygonContainer *polys, 
+                                                PolygonContainer *frontPolys, 
+                                                PolygonContainer *backPolys);
+
+        /** Take 3 ray endpoints, where two are minimum and one a maximum
+                point or the other way round.
+        */
+        Plane3 ChooseCandidatePlane(const BoundedRayContainer &rays) const;
+
+        /** Take plane normal as plane normal and the midpoint of the ray.
+                PROBLEM: does not resemble any point where visibility is likely to change
+        */
+        Plane3 ChooseCandidatePlane2(const BoundedRayContainer &rays) const;
+
+        /** Fit the plane between the two lines so that the plane has equal shortest 
+                distance to both lines.
+        */
+        Plane3 ChooseCandidatePlane3(const BoundedRayContainer &rays) const;
+
+        /** Selects the split plane in order to construct a tree with
+                certain characteristics (e.g., balanced tree, least splits, 
+                2.5d aligned)
+                @param polygons container of polygons
+                @param rays bundle of rays on which the split can be based
+        */
+        Plane3 SelectPlaneHeuristics(BspLeaf *leaf,
+                                                                 BspTraversalData &data);
+
+        /** Extracts the meshes of the objects and adds them to polygons. 
+                Adds object aabb to the aabb of the tree.
+                @param maxPolys the maximal number of objects to be stored as polygons
+                @returns the number of polygons
+        */
+        int AddToPolygonSoup(const ObjectContainer &objects, 
+                                                 PolygonContainer &polys, 
+                                                 int maxObjects = 0,
+                                                 bool addToBbox = true);
+
+        /** Extracts the meshes of the view cells and and adds them to polygons.
+                Adds view cell aabb to the aabb of the tree.
+                @param maxPolys the maximal number of objects to be stored as polygons
+                @returns the number of polygons
+        */
+        int AddToPolygonSoup(const ViewCellContainer &viewCells, 
+                                                 PolygonContainer &polys, 
+                                                 int maxObjects = 0);
+
+        /** Extract polygons of this mesh and add to polygon container.
+                @param mesh the mesh that drives the polygon construction
+                @param parent the parent intersectable this polygon is constructed from
+                @returns number of polygons
+        */
+        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
+
+        /** Helper function which extracts a view cell on the front and the back
+                of the split plane.
+                @param backViewCell returns view cell on the back of the split plane
+                @param frontViewCell returns a view cell on the front of the split plane
+                @param coincident container of polygons coincident to the split plane
+                @param splitPlane the split plane which decides about back and front
+                @param extractBack if a back view cell is extracted
+                @param extractFront if a front view cell is extracted
+        */
+        void ExtractViewCells(BspTraversalData &frontData,
+                                                  BspTraversalData &backData, 
+                                                  const PolygonContainer &coincident,
+                                                  const Plane3 &splitPlane) const;
+        
+        /** Computes best cost ratio for the suface area heuristics for axis aligned
+                splits. This heuristics minimizes the cost for ray traversal.
+                @param polys the polygons guiding the ratio computation
+                @param box the bounding box of the leaf
+                @param axis the current split axis
+                @param position returns the split position
+                @param objectsBack the number of objects in the back of the split plane
+                @param objectsFront the number of objects in the front of the split plane
+        */
+        float BestCostRatio(const PolygonContainer &polys,
+                                                const AxisAlignedBox3 &box,
+                                                const int axis,
+                                                float &position,
+                                                int &objectsBack,
+                                                int &objectsFront) const;
+        
+        /** Sorts split candidates for cost heuristics using axis aligned splits.
+                @param polys the input for choosing split candidates
+                @param axis the current split axis
+                @param splitCandidates returns sorted list of split candidates
+        */
+        void SortSubdivisionCandidates(const PolygonContainer &polys, 
+                                                         const int axis, 
+                                                         vector<SortableEntry> &splitCandidates) const;
+
+        /** Selects an axis aligned split plane.
+                Returns true if split is valied
+        */
+        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
+
+        /** Subdivides the rays into front and back rays according to the split plane.
+                
+                @param plane the split plane
+                @param rays contains the rays to be split. The rays are 
+                           distributed into front and back rays.
+                @param frontRays returns rays on the front side of the plane
+                @param backRays returns rays on the back side of the plane
+                
+                @returns the number of splits
+        */
+        int SplitRays(const Plane3 &plane,
+                                  BoundedRayContainer &rays, 
+                              BoundedRayContainer &frontRays, 
+                                  BoundedRayContainer &backRays);
+
+
+        /** Extracts the split planes representing the space bounded by node n.
+        */
+        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
+
+        /** Adds the object to the pvs of the front and back leaf with a given classification.
+
+                @param obj the object to be added
+                @param cf the ray classification regarding the split plane
+                @param frontPvs returns the PVS of the front partition
+                @param backPvs returns the PVS of the back partition
+        
+        */
+        void AddObjToPvs(Intersectable *obj, const int cf, int &frontPvs, int &backPvs) const;
+
+        /** Computes PVS size induced by the rays.
+        */
+        int ComputePvsSize(const BoundedRayContainer &rays) const;
+
+        /** Returns true if tree can be terminated.
+        */
+        inline bool TerminationCriteriaMet(const BspTraversalData &data) const;
+
+        /** Computes accumulated ray lenght of this rays.
+        */
+        float AccumulatedRayLength(BoundedRayContainer &rays) const;
+
+        /** Splits polygons with respect to the split plane.
+                @param polys the polygons to be split. the polygons are consumed and
+                           distributed to the containers frontPolys, backPolys, coincident.
+                @param frontPolys returns the polygons in the front of the split plane
+                @param backPolys returns the polygons in the back of the split plane
+                @param coincident returns the polygons coincident to the split plane
+
+                @returns the number of splits   
+        */
+        int SplitPolygons(const Plane3 &plane,
+                                          PolygonContainer &polys, 
+                                          PolygonContainer &frontPolys, 
+                                          PolygonContainer &backPolys, 
+                                          PolygonContainer &coincident) const;
+
+        /** Adds ray sample contributions to the PVS.
+                @param sampleContributions the number contributions of the samples
+                @param contributingSampels the number of contributing rays
+                
+        */
+        void AddToPvs(BspLeaf *leaf,
+                                  const BoundedRayContainer &rays, 
+                                  int &sampleContributions,     
+                                  int &contributingSamples);
+
+        /** Preprocesses polygons and throws out all polygons which 
+                are coincident to the view space box faces:
+                These polygons can can be problematic for bsp because they create
+                bad view cells.
+        */
+        void PreprocessPolygons(PolygonContainer &polys);
+
+
+        ///////////////////////////////////
+                
+        /// Pointer to the root of the tree.
+        BspNode *mRoot;
+
+        /// Stores statistics during traversal.
+        BspTreeStatistics mStat;
+
         /// box around the whole view domain
-        AxisAlignedBox3 mBox;
+        AxisAlignedBox3 mBbox;
 
         /// view cell corresponding to unbounded space
@@ -1006 +999 @@
 
         /// if view cells should be generated or the given view cells should be used.
-        bool mGenerateViewCells;
+        bool mUsePredefinedViewCells;
 
         /// maximal number of polygons before subdivision termination
@@ -1076 +1069 @@
         ofstream  mSubdivisionStats;
 
+        ViewCellsTree *mViewCellsTree;
+
+        bool mOutOfBoundsCellPartOfTree;
 private:
         

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp

@@ -23 +23 @@
 #include "BvHierarchy.h"
 #include "SamplingStrategy.h"
+#include "SceneGraph.h"
 
 
 // should not count origin object for sampling because it disturbs heuristics
 #define SAMPLE_ORIGIN_OBJECTS 0
-
 
 
@@ -63 +63 @@
 mViewCellPvsIsUpdated(false),
 mPreprocessor(NULL),
-mViewCellsTree(viewCellsTree)
+mViewCellsTree(viewCellsTree),
+mUsePredefinedViewCells(false)
 {
         mViewSpaceBox.Initialize();
@@ -649 +650 @@
 {
         if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
+        {
                 return false;
+        }
 
         cout << "exporting view cells to xml ... ";
@@ -1044 +1047 @@
 
         const int n = min(mMaxFilterSize, (int)neighborhood.size());
+        
+        /////////////////
         //-- use priority queue to merge leaf pairs
-
-        //cout << "neighborhood: " << neighborhood.size() << endl;
-        //const float maxAvgCost = 350;
+        
         for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
         {
@@ -1058 +1061 @@
                 neighborhood.pop_back();
         
-                //              cout << "vc idx: " << bestViewCellIdx << endl;
                 if (!bestViewCell || !root)
-                        cout << "warning!!" << endl;
+            cout << "warning!!" << endl;
                 
                 // create new root of the hierarchy
@@ -1174 +1176 @@
                                                            const float filterWidth)
 {
-
-        
-
-        
-  ViewCell *currentViewCell = GetViewCell(viewPoint);
-
-  if (mMaxFilterSize < 1) {
-        prvs.mViewCell = currentViewCell;
-        return;
-  }
-  
-  const AxisAlignedBox3 box = GetFilterBBox(viewPoint, filterWidth);
-  
-  if (currentViewCell) {
-        ViewCellContainer viewCells;
-        ComputeBoxIntersections(box, viewCells);
-
-
-        ViewCell *root = ConstructLocalMergeTree2(currentViewCell, viewCells);
-        prvs.mViewCell = root;
-        
-  } else
-        prvs.mViewCell = NULL;
-  //prvs.mPvs = root->GetPvs();
+        ViewCell *currentViewCell = GetViewCell(viewPoint);
+
+        if (mMaxFilterSize < 1) {
+                prvs.mViewCell = currentViewCell;
+                return;
+        }
+
+        const AxisAlignedBox3 box = GetFilterBBox(viewPoint, filterWidth);
+
+        if (currentViewCell) 
+        {
+                ViewCellContainer viewCells;
+                ComputeBoxIntersections(box, viewCells);
+
+                ViewCell *root = ConstructLocalMergeTree2(currentViewCell, viewCells);
+                prvs.mViewCell = root;
+
+        } 
+        else
+        {
+                prvs.mViewCell = NULL;
+                //prvs.mPvs = root->GetPvs();
+        }
 }
 
@@ -1262 +1263 @@
 
 
-bool ViewCellsManager::LoadViewCellsGeometry(const string filename)
-{
+bool ViewCellsManager::LoadViewCellsGeometry(const string filename, 
+                                                                                         const bool extrudeBaseTriangles)
+{
+        bool success;
+
+        /// we use predefined view cells from now on
+        mUsePredefinedViewCells = true;
         X3dParser parser;
-
-        Environment::GetSingleton()->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
-
-        bool success = parser.ParseFile(filename, *this);
-        Debug << (int)mViewCells.size() << " view cells loaded" << endl;
+        
+        if (extrudeBaseTriangles)
+        {
+                Environment::GetSingleton()->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
+                success = parser.ParseFile(filename, *this);
+        }
+        else
+        {
+                // hack: use standard mesh loading
+                // create temporary scene graph for loading the view cells geometry
+                SceneGraphNode *root = new SceneGraphNode();
+                success = parser.ParseFile(filename, root, true);
+                                
+                if (success)
+                {
+                        ObjectContainer::const_iterator oit, oit_end = root->mGeometry.end();
+                        for (oit = root->mGeometry.begin(); oit != oit_end; ++ oit)
+                        {
+                                if ((*oit)->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
+                                {
+                                        TransformedMeshInstance *mit = dynamic_cast<TransformedMeshInstance *>(*oit);
+                                        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
+                                        mit->GetTransformedMesh(*mesh);
+                                        mesh->ComputeBoundingBox();
+                                        mViewCells.push_back(GenerateViewCell(mesh));
+                                }
+                                else if ((*oit)->Type() == Intersectable::MESH_INSTANCE)
+                                {
+                                        MeshInstance *mit = dynamic_cast<MeshInstance *>(*oit);
+                                        mViewCells.push_back(GenerateViewCell(mit->GetMesh()));
+                                }                       
+                        }
+                }
+                DEL_PTR(root);
+        }
+
+        if (success)
+        {
+                // set view space box to bounding box of the view cells
+                /*AxisAlignedBox3 bbox;
+                bbox.Initialize();
+                ViewCellContainer::iterator it = mViewCells.begin(), it_end = mViewCells.end();
+                for (; it != it_end; ++ it) 
+                {
+                        bbox.Include(GetViewCellBox(*it));
+                }
+                SetViewSpaceBox(bbox);*/
+        
+                cout << "generated " << (int)mViewCells.size() << " view cells using the geometry from file " << filename << endl;
+        }
 
         return success;
@@ -1396 +1447 @@
 
 
-
-void ViewCellsManager::AddViewCell(ViewCell *viewCell)
-{
-        mViewCells.push_back(viewCell);
-}
-
-
 float ViewCellsManager::GetArea(ViewCell *viewCell) const
 {
@@ -1412 +1456 @@
 {
         return viewCell->GetVolume();
-}
-
-
-void ViewCellsManager::DeriveViewCellsFromObjects(const ObjectContainer &objects,
-                                                                                                  ViewCellContainer &viewCells,
-                                                                                                  const int maxViewCells) const
-{
-        // maximal max viewcells
-        int limit = maxViewCells > 0 ?
-                Min((int)objects.size(), maxViewCells) : (int)objects.size();
-
-        for (int i = 0; i < limit; ++ i)
-        {
-                Intersectable *object = objects[i];
-
-                // extract the mesh instances
-                if (object->Type() == Intersectable::MESH_INSTANCE)
-                {
-                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
-
-                        ViewCell *viewCell = GenerateViewCell(inst->GetMesh());
-                        viewCells.push_back(viewCell);
-                }
-                else if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
-                {
-                        TransformedMeshInstance *mi = dynamic_cast<TransformedMeshInstance *>(object);
-
-                        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
-                        
-                        // transform mesh
-                        mi->GetTransformedMesh(*mesh);
-                        
-                        // create bb + kd tree
-                        mesh->Preprocess();
-
-                        ViewCell *viewCell = GenerateViewCell(mi->GetMesh());
-                        viewCells.push_back(viewCell);
-
-                        break;
-                }
-        }
 }
 
@@ -1462 +1465 @@
         Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
 
+        ////////////
         //-- construct prism
 
@@ -1473 +1477 @@
         mesh->mFaces.push_back(new Face(3, 5, 2, 0));
 
-        //--- extrude new vertices for top of prism
+
+        /////////////
+        //-- extrude new vertices for top of prism
+
         Vector3 triNorm = baseTri.GetNormal();
-
         Triangle3 topTri;
 
         // add base vertices and calculate top vertices
         for (int i = 0; i < 3; ++ i)
+        {
                 mesh->mVertices.push_back(baseTri.mVertices[i]);
+        }
 
         // add top vertices
         for (int i = 0; i < 3; ++ i)
+        {
                 mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
-
-        mesh->Preprocess();
-
+        }
+
+        // do we have to preprocess this mesh (we don't want to trace view cells!)?
+        mesh->ComputeBoundingBox();
+        
         return GenerateViewCell(mesh);
 }
@@ -1875 +1886 @@
                                 // if view point is valid, add new object to the pvs
                                 if (ray.mTerminationObject)
-                                {cout <<"here22" << endl;
+                                {
                                         viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
                                 }                               
@@ -2007 +2018 @@
         mNumActiveViewCells = n;
         mViewCells.clear();
+        // implemented in subclasses
         CollectViewCells();
 }
@@ -2497 +2509 @@
         Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
         mBspTree->SetViewCellsManager(this);
-        mBspTree->mViewCellsTree = mViewCellsTree;
+        mBspTree->SetViewCellsTree(mViewCellsTree);
 }
 
@@ -2516 +2528 @@
                                                                                           const VssRayContainer &rays)
 {
-        // if view cells were already constructed
+        // if view cells were already constructed, we can finish
         if (ViewCellsConstructed())
                 return 0;
@@ -2540 +2552 @@
         }
 
-    if (mViewCells.empty())
+    if (!mUsePredefinedViewCells)
         {
                 // no view cells loaded
@@ -2548 +2560 @@
         }
         else
-        {
+        {       cout << "here222" << endl;
+                // use predefined view cells geometry => 
+                // contruct bsp hierarchy over them
                 mBspTree->Construct(mViewCells);
         }
@@ -2575 +2589 @@
 
 void BspViewCellsManager::CollectViewCells()
-{
-        // view cells tree constructed
+{       
         if (!ViewCellsTreeConstructed())
-        {               
+        {       // view cells tree constructed  
                 mBspTree->CollectViewCells(mViewCells);
         }
         else 
-        {
-                // we can use the view cells tree hierarchy to get the right set
-                mViewCellsTree->CollectBestViewCellSet(mViewCells, 
-                                                                                           mNumActiveViewCells);
+        {       // we can use the view cells tree hierarchy to get the right set
+                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
         }
 }
@@ -2592 +2603 @@
 float BspViewCellsManager::GetProbability(ViewCell *viewCell)
 {
-        // compute view cell area as subsititute for probability
         if (1)
                 return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
         else
+                // compute view cell area as subsititute for probability
                 return GetArea(viewCell) / GetAccVcArea();
 }
@@ -2609 +2620 @@
 
 
+void BspViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
+{
+        // save color code
+        const int savedColorCode = mColorCode;
+
+        // export merged view cells
+        mColorCode = 0; // use random colors
+
+        Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
+
+        cout << "exporting view cells after merge ... ";
+
+        if (exporter)
+        {
+                if (mExportGeometry)
+                {
+                        exporter->ExportGeometry(objects);
+                }
+
+                exporter->SetFilled();
+                ExportViewCellsForViz(exporter, NULL, GetClipPlane());
+
+                delete exporter;
+        }
+        cout << "finished" << endl;
+
+        // export merged view cells using pvs color coding
+        mColorCode = 1;
+
+        exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
+        cout << "exporting view cells after merge (pvs size) ... ";     
+
+        if (exporter)
+        {
+                if (mExportGeometry)
+                {
+                        exporter->ExportGeometry(objects);
+                }
+
+                exporter->SetFilled();
+                ExportViewCellsForViz(exporter, NULL, GetClipPlane());
+
+                delete exporter;
+        }
+        cout << "finished" << endl;
+        
+        mColorCode = savedColorCode;
+}
+
+
 int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
                                                                          const VssRayContainer &rays)
@@ -2628 +2689 @@
         }
 
-    int vcSize = 0;
-        int pvsSize = 0;
-        
-
+if (mUsePredefinedViewCells) return 0;
         //////////////////
         //-- merge leaves of the view cell hierarchy    
@@ -2649 +2707 @@
         {
                 cout << "constructing spatial merge tree" << endl;
-
-                // create spatial merge hierarchy
-                ViewCell *root = ConstructSpatialMergeTree(mBspTree->GetRoot());
+                ViewCell *root;
+                // the spatial merge tree is difficult to build for 
+                // this type of construction, as view cells cover several
+                // leaves => create dummy tree which is only 2 levels deep
+                if (mUsePredefinedViewCells) 
+                {
+                        root = ConstructDummyMergeTree(mBspTree->GetRoot());
+                }
+                else
+                {
+                        // create spatial merge hierarchy
+                        root = ConstructSpatialMergeTree(mBspTree->GetRoot());
+                }
+                
                 mViewCellsTree->SetRoot(root);
 
@@ -2657 +2726 @@
                 ObjectPvs pvs;
                 UpdatePvsForEvaluation(root, pvs);
+                
         }
 
@@ -2680 +2750 @@
         Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
 
-        // save color code
-        const int savedColorCode = mColorCode;
-        
-        if (1) // export merged view cells
-        {
-                mColorCode = 0; // use random colors
-                Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
+        if (1) ExportMergedViewCells(objects);
+
+        // only for debugging purpose: test if the subdivision is valid
+        if (0) TestSubdivision();
+
+        // compute final meshes and volume / area
+        if (1) FinalizeViewCells(true);
+
+        // write view cells to disc
+        if (1 && mExportViewCells)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
+                ExportViewCells(filename, mExportPvs, objects);
+        }
+        
+        return 0;
+}
+
+
+BspViewCellsManager::~BspViewCellsManager()
+{
+}
+
+
+int BspViewCellsManager::GetType() const
+{
+        return BSP;
+}
+
+
+void BspViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                        const VssRayContainer &sampleRays)
+{
+        if (!ViewCellsConstructed())
+                return;
+        
+        int savedColorCode = mColorCode;
                 
-                cout << "exporting view cells after merge ... ";
+        if (1) // export final view cells
+        {
+                mColorCode = 1; // hack color code
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
+        
+                cout << "exporting view cells after merge (pvs size) ... ";     
 
                 if (exporter)
@@ -2697 +2803 @@
                         }
 
-                        exporter->SetFilled();
-                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
-
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
-
-        if (1) 
-        {
-                // export merged view cells using pvs color coding
-                mColorCode = 1;
-
-                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
-                cout << "exporting view cells after merge (pvs size) ... ";     
-
-                if (exporter)
-                {
-                        if (mExportGeometry)
-                        {
-                                exporter->ExportGeometry(objects);
-                        }
-                        
-                        exporter->SetFilled();
-                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
-
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
-        
-        // only for debugging purpose: test if the subdivision is valid
-        if (0) TestSubdivision();
-
-        mColorCode = savedColorCode;
-
-        // compute final meshes and volume / area
-        if (1) FinalizeViewCells(true);
-
-        // write view cells to disc
-        if (1 && mExportViewCells)
-        {
-                char filename[100];
-                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
-                ExportViewCells(filename, mExportPvs, objects);
-        }
-        
-        return 0;
-}
-
-
-BspViewCellsManager::~BspViewCellsManager()
-{
-}
-
-
-int BspViewCellsManager::GetType() const
-{
-        return BSP;
-}
-
-
-void BspViewCellsManager::Visualize(const ObjectContainer &objects,
-                                                                        const VssRayContainer &sampleRays)
-{
-        if (!ViewCellsConstructed())
-                return;
-        
-        int savedColorCode = mColorCode;
-        
-        
-        if (1) // export final view cells
-        {
-                mColorCode = 1; // hack color code
-                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
-        
-                cout << "exporting view cells after merge (pvs size) ... ";     
-
-                if (exporter)
-                {
-                        if (mExportGeometry)
-                        {
-                                exporter->ExportGeometry(objects);
-                        }
-
                         ExportViewCellsForViz(exporter, NULL, GetClipPlane());
                         delete exporter;
@@ -2787 +2808 @@
                 cout << "finished" << endl;
         }
-
+        // reset color code
         mColorCode = savedColorCode;
 
@@ -2816 +2837 @@
         {
                 //exporter->SetFilled();
-
                 if (mExportGeometry)
+                {
                         exporter->ExportGeometry(objects);
+                }
 
                 Material m;
@@ -2827 +2849 @@
                 exporter->ExportBspSplits(*mBspTree, true);
 
-                //NOTE: take forced material, else big scenes cannot be viewed
+                // NOTE: take forced material, else big scenes cannot be viewed
                 m.mDiffuseColor = RgbColor(0, 1, 0);
                 exporter->SetForcedMaterial(m);
@@ -2840 +2862 @@
 {
         const int leafOut = 10;
-
         ViewCell::NewMail();
 
+        //////////
         //-- some rays for output
         const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
@@ -2861 +2883 @@
                 ViewCell *vc;
 
-                if (0)
+                if (0 || ((int)mViewCells.size() <= limit))
                         vc = mViewCells[i];
                 else
@@ -2878 +2900 @@
                                         BspLeaf *leaf = ray->intersections[j].mLeaf;
                                         if (vc == leaf->GetViewCell())
+                                        {
                                                 vcRays.push_back(ray->vssRay);
+                                        }
                                 }
                         }
@@ -3080 +3104 @@
 {
         if (!ViewCellsConstructed())
+        {
                 return NULL;
+        }
 
         if (!mViewSpaceBox.IsInside(point))
+        {
                 return NULL;
-        
+        }
+
         return mBspTree->GetViewCell(point);
 }
@@ -3154 +3182 @@
 #endif
         return true;
+}
+
+
+ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root)
+{
+        ViewCellInterior *vcRoot = new ViewCellInterior();
+                
+        // evaluate merge cost for priority traversal
+        const float mergeCost = 1.0f / (float)root->mTimeStamp;
+        vcRoot->SetMergeCost(mergeCost);
+
+        float volume = 0;
+        vector<BspLeaf *> leaves;
+        mBspTree->CollectLeaves(leaves);
+        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
+        
+        for (lit = leaves.begin(); lit != lit_end; ++ lit)
+        {
+                BspLeaf *leaf = *lit;
+                ViewCell *vc = leaf->GetViewCell();
+
+                vc->SetMergeCost(0.0f);
+                vcRoot->SetupChildLink(vc);
+        
+                volume += vc->GetVolume();
+                volume += vc->GetVolume();      
+
+                vcRoot->SetVolume(volume);
+        }
+        
+        return vcRoot;
 }
 
@@ -3180 +3239 @@
 
 
+        ////////////
         //-- recursivly compute child hierarchies
+
         ViewCell *backVc = ConstructSpatialMergeTree(back);
         ViewCell *frontVc = ConstructSpatialMergeTree(front);
-
 
         viewCellInterior->SetupChildLink(backVc);
@@ -3528 +3588 @@
 void VspBspViewCellsManager::CollectViewCells()
 {
-        // view cells tree constructed
+        // view cells tree constructed?
         if (!ViewCellsTreeConstructed())
         {
@@ -3581 +3641 @@
         // if view cells were already constructed
         if (ViewCellsConstructed())
+        {
                 return 0;
+        }
 
         int sampleContributions = 0;
-
         VssRayContainer sampleRays;
 
-        int limit = min (mInitialSamples, (int)rays.size());
-
-        VssRayContainer constructionRays;
-        VssRayContainer savedRays;
+        const int limit = min(mInitialSamples, (int)rays.size());
 
         Debug << "samples used for vsp bsp subdivision: " << mInitialSamples 
                   << ", actual rays: " << (int)rays.size() << endl;
 
-        GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
-
-        Debug << "initial rays: " << (int)constructionRays.size() << endl;
-        Debug << "saved rays: " << (int)savedRays.size() << endl;
-
-        long startTime;
-
-        if (1)
-        {
+        VssRayContainer savedRays;
+
+        if (SAMPLE_AFTER_SUBDIVISION)
+        {
+                VssRayContainer constructionRays;
+                
+                GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
+
+                Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
+                Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
+        
                 mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
         }
         else
         {
+                Debug << "rays used for initial construction: " << (int)rays.size() << endl;
                 mVspBspTree->Construct(rays, &mViewSpaceBox);
         }
@@ -3613 +3674 @@
         // collapse invalid regions
         cout << "collapsing invalid tree regions ... ";
-        startTime = GetTime();
+        long startTime = GetTime();
+
         const int collapsedLeaves = mVspBspTree->CollapseTree();
         Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
@@ -3630 +3692 @@
 
         //////////////////////
-        //-- recast rest of rays
+        //-- recast the rest of the rays
         startTime = GetTime();
 
@@ -3646 +3708 @@
 
         if (0)
-        {
+        {       ////////
                 //-- real meshes are contructed at this stage
                 cout << "finalizing view cells ... ";
@@ -4179 +4241 @@
                 // export rays
                 if (mExportRays)
+                {
                         exporter->ExportRays(rays, RgbColor(1, 1, 0));
+                }
 
                 if (mExportGeometry)
+                {
                         exporter->ExportGeometry(objects);
+                }
 
                 delete exporter;
@@ -4783 +4849 @@
         mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
 
-        VssRayContainer::const_iterator vit, vit_end = constructionRays.end();
-
-        for (vit = constructionRays.begin(); vit != vit_end; ++ vit)
-        {
-                storedRays.push_back(new VssRay(*(*vit)));
-        }
-
-        ////////////
+        
+        /////////////////////////
         //-- print satistics for subdivision and view cells
 
@@ -4805 +4865 @@
 
 
-        //////////
+        //////////////
         //-- recast rest of rays
         
@@ -4818 +4878 @@
 
         if (0)
-        {
-                // real meshes are constructed at this stage
+        {       // real meshes are constructed at this stage
                 cout << "finalizing view cells ... ";
                 FinalizeViewCells(true);
@@ -4961 +5020 @@
         VspNode *back = interior->GetBack();
 
-
         ObjectPvs frontPvs, backPvs;
 
+        /////////
         //-- recursivly compute child hierarchies
+
         ViewCell *backVc = ConstructSpatialMergeTree(back);
         ViewCell *frontVc = ConstructSpatialMergeTree(front);
-
 
         viewCellInterior->SetupChildLink(backVc);
@@ -5093 +5152 @@
                         AxisAlignedBox3 bbox = mHierarchyManager->GetViewSpaceBox();
                         bbox.Scale(Vector3(0.5, 1, 0.5));
-                                
                         if (CLAMP_TO_BOX)
                         {       
@@ -5101 +5159 @@
                         }
                                 
-                        ///////////////////
-
                         if (0 && mExportGeometry)
                         {
                                 exporter->ExportGeometry(objects, true, CLAMP_TO_BOX ? &bbox : NULL);
                         }
-
-                        // export rays
+                        
                         if (0 && mExportRays)
-                        {
+                        {       
                                 exporter->ExportRays(visRays, RgbColor(0, 1, 0));
                         }
@@ -5650 +5705 @@
         }
 
-        Debug << "\nrendercost hack: " << rc / mHierarchyManager->GetVspTree()->GetBoundingBox().GetVolume() << endl;
+        Debug << "\nrendercost hack: " << rc / mHierarchyManager->GetViewSpaceBox() << endl;
         mViewCellsTree->ExportStats(fileName);
         cout << "finished" << endl;

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.h

@@ -70 +70 @@
                 float avgPvs;
                 int viewcells;
-  };
+        };
 
         /// view cell container types
@@ -78 +78 @@
         enum {PER_OBJECT, PER_TRIANGLE};
 
+        friend class X3dViewCellsParseHandlers;
         /** Default constructor.
         */
@@ -144 +145 @@
 
         /** Load the input viewcells. The input viewcells should be given as a collection
-                of meshes. Each mesh is assume to form a bounded polyhedron defining the interior of
-                the viewcell. The method then builds a BSP tree of these view cells.
+                of meshes. Each mesh is assume to form a bounded polyhedron 
+                defining the interior of the viewcell. The view cells manager
+                is responsible for building a hierarchy over these view cells.
                 
                 @param filename file to load
                 @return true on success
     */
-    virtual bool LoadViewCellsGeometry(const string filename);
-        
+    virtual bool LoadViewCellsGeometry(const string filename, const bool extrudeBaseTriangle);
+        
+        /** Merges two view cells.
+                @note the piercing rays of the front and back will be ordered   
+                @returns new view cell based on the merging.
+        */
+        ViewCellInterior *MergeViewCells(ViewCell *front, ViewCell *back) const;
+
+        /** Merges a container of view cells.
+                @returns new view cell based on the merging.
+        */
+        ViewCellInterior *MergeViewCells(ViewCellContainer &children) const;
+        
+        /** Generates view cell of the type specified by this manager
+        */
+        virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const = 0;
+
         /** Constructs view cell from base triangle. 
                 The view cell is extruded along the normal vector.
@@ -158 +175 @@
         */
         ViewCell *ExtrudeViewCell(const Triangle3 &baseTri, const float height) const;
-
-        /** Merges two view cells.
-                @note the piercing rays of the front and back will be ordered   
-                @returns new view cell based on the merging.
-        */
-        ViewCellInterior *MergeViewCells(ViewCell *front, ViewCell *back) const;
-
-        /** Merges a container of view cells.
-                @returns new view cell based on the merging.
-        */
-        ViewCellInterior *MergeViewCells(ViewCellContainer &children) const;
-        
-        /** Generates view cell of type specified by this manager
-        */
-        virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const = 0;
-
-        /** Adds a new view cell to the list of predefined view cells.
-        */
-        void AddViewCell(ViewCell *viewCell);
-
-        /** Derive view cells from scene objects. The view ells are created by taking the object
-                geometry into account.
-        */
-        void DeriveViewCellsFromObjects(const ObjectContainer &objects, 
-                                                                        ViewCellContainer &viewCells, 
-                                                                        const int maxViewCells) const;
 
         /** Sets maximal number of samples used for the 
@@ -338 +329 @@
         void SetValidityPercentage(const float minValid, const float maxValid);
 
+        /** Returns number of valid view cells.
+        */
     int CountValidViewcells() const;
 
@@ -378 +371 @@
         ViewCellsTree *GetViewCellsTree();
 
+        /** Collect candidates for the view cell merge.
+        */
         virtual void CollectMergeCandidates(const VssRayContainer &rays, 
                                                                                 vector<MergeCandidate> &candidates);
@@ -438 +433 @@
         bool GetExportPvs() const;
 
+        /////////////////////////////
+        // static members
+        
         /** Loads view cells from file. The view cells manager is created with 
                 respect to the loaded view cells.
@@ -569 +567 @@
         */
         virtual void ExportColor(Exporter *exporter, ViewCell *vc) const;
+        
         /** Creates meshes from the view cells.
         */
         void CreateViewCellMeshes();
-        /** Creates clip plane for visualization.
+
+    /** Creates clip plane for visualization.
         */
         void CreateClipPlane();
 
         AxisAlignedPlane *GetClipPlane();
+        
         ///////////////////////
 
@@ -663 +664 @@
         int mMaxFilterSize;
 
+        bool mStoreObjectPvs;
+
+        //////////////////
         //-- visualization options
         
         /// color code for view cells visualization
+                bool mShowVisualization;
         int mColorCode;
         bool mExportGeometry;
         bool mExportRays;
-
         bool mViewCellsFinished;
-
         bool mEvaluateViewCells;
-
-        bool mShowVisualization;
-
         int mRenderCostEvaluationType;
 
@@ -681 +681 @@
         bool mExportPvs;
 
-        bool mStoreObjectPvs;
-
-        VssRayContainer storedRays;
+        bool mUsePredefinedViewCells;
 };
 
 
-/**
-        Manages different higher order operations on the view cells.
+/** Manages different higher order operations on the view cells.
 */
 class BspViewCellsManager: public ViewCellsManager
@@ -754 +751 @@
         ViewCell *ConstructSpatialMergeTree(BspNode *root);
 
-        
+
 protected:
 
         void CollectViewCells();
-
         
         /// the BSP tree.
         BspTree *mBspTree;
-        
         vector<BspRay *> mBspRays;
 
 private:
 
+        /** Constructs a spatial merge tree only 2 levels deep.
+        */
+        ViewCell *ConstructDummyMergeTree(BspNode *root);
+
         /** Exports visualization of the BSP splits.
         */
@@ -778 +777 @@
         */
         void TestSubdivision();
+
+        void ExportMergedViewCells(const ObjectContainer &objects);
 };
+
 
 /**
@@ -1091 +1093 @@
 
 
-/*class ViewCellsManagerFactory
-{
-public:
-        ViewCellsManager *Create(const string mName);
-};*/
-
 }
 

GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp

@@ -265 +265 @@
 
         int polysSize = 0;
-
+        
         for (int i = 0; i < limit; ++ i)
         {
-                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
-                {
-                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
-                        polysSize +=
-                                AddMeshToPolygons(viewCells[i]->GetMesh(),
-                                                                  polys,
-                                                                  viewCells[i]);
-                }
-        }
-
+                Mesh *mesh = viewCells[i]->GetMesh();
+                if (mesh) 
+                {       // // copy the mesh into polygons and add to BSP tree aabb
+                        mBox.Include(viewCells[i]->GetBox()); 
+                        polysSize += AddMeshToPolygons(mesh,
+                                                                                   polys,
+                                                                                   viewCells[i]);
+                }
+        }
+        
         return polysSize;
 }
@@ -2588 +2588 @@
 {
         ViewCell::NewMail();
-        
         CollectViewCells(mRoot, onlyValid, viewCells, true);
 }
-
-
-void VspBspTree::CollapseViewCells()
-{
-// TODO
-#if HAS_TO_BE_REDONE
-        stack<BspNode *> nodeStack;
-
-        if (!mRoot)
-                return;
-
-        nodeStack.push(mRoot);
-        
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
-                nodeStack.pop();
-                
-                if (node->IsLeaf())
-        {
-                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
-
-                        if (!viewCell->GetValid())
-                        {
-                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
-        
-                                ViewCellContainer leaves;
-                                mViewCellsTree->CollectLeaves(viewCell, leaves);
-
-                                ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-                                for (it = leaves.begin(); it != it_end; ++ it)
-                                {
-                                        BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
-                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
-                                        ++ mBspStats.invalidLeaves;
-                                }
-
-                                // add to unbounded view cell
-                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
-                                DEL_PTR(viewCell);
-                        }
-                }
-                else
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-                
-                        nodeStack.push(interior->GetFront());
-                        nodeStack.push(interior->GetBack());
-                }
-        }
-
-        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
-#endif
-}
-
-
-void VspBspTree::CollectRays(VssRayContainer &rays)
-{
-        vector<BspLeaf *> leaves;
-
-        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
-
-        for (lit = leaves.begin(); lit != lit_end; ++ lit)
-        {
-                BspLeaf *leaf = *lit;
-                VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
-
-                for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
-                        rays.push_back(*rit);
-        }
-}
-
-
-void VspBspTree::ValidateTree()
-{
-        stack<BspNode *> nodeStack;
-
-        if (!mRoot)
-                return;
-
-        nodeStack.push(mRoot);
-        
-        mBspStats.invalidLeaves = 0;
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top();
-                nodeStack.pop();
-                
-                if (node->IsLeaf())
-                {
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
-
-                        if (!leaf->GetViewCell()->GetValid())
-                                ++ mBspStats.invalidLeaves;
-
-                        // validity flags don't match => repair
-                        if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
-                        {
-                                leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
-                                PropagateUpValidity(leaf);
-                        }
-                }
-                else
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-                
-                        nodeStack.push(interior->GetFront());
-                        nodeStack.push(interior->GetBack());
-                }
-        }
-
-        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
-}
-
 
 
@@ -2748 +2632 @@
                 }
         }
-
+}
+
+
+void VspBspTree::CollapseViewCells()
+{
+// TODO
+#if HAS_TO_BE_REDONE
+        stack<BspNode *> nodeStack;
+
+        if (!mRoot)
+                return;
+
+        nodeStack.push(mRoot);
+        
+        while (!nodeStack.empty()) 
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+                
+                if (node->IsLeaf())
+        {
+                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+
+                        if (!viewCell->GetValid())
+                        {
+                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+        
+                                ViewCellContainer leaves;
+                                mViewCellsTree->CollectLeaves(viewCell, leaves);
+
+                                ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+                                for (it = leaves.begin(); it != it_end; ++ it)
+                                {
+                                        BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
+                                        ++ mBspStats.invalidLeaves;
+                                }
+
+                                // add to unbounded view cell
+                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
+                                DEL_PTR(viewCell);
+                        }
+                }
+                else
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+
+        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
+#endif
+}
+
+
+void VspBspTree::CollectRays(VssRayContainer &rays)
+{
+        vector<BspLeaf *> leaves;
+
+        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
+
+        for (lit = leaves.begin(); lit != lit_end; ++ lit)
+        {
+                BspLeaf *leaf = *lit;
+                VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
+
+                for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
+                        rays.push_back(*rit);
+        }
+}
+
+
+void VspBspTree::ValidateTree()
+{
+        stack<BspNode *> nodeStack;
+
+        if (!mRoot)
+                return;
+
+        nodeStack.push(mRoot);
+        
+        mBspStats.invalidLeaves = 0;
+        while (!nodeStack.empty()) 
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+                
+                if (node->IsLeaf())
+                {
+                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+                        if (!leaf->GetViewCell()->GetValid())
+                                ++ mBspStats.invalidLeaves;
+
+                        // validity flags don't match => repair
+                        if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
+                        {
+                                leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
+                                PropagateUpValidity(leaf);
+                        }
+                }
+                else
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+
+        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
 }
 

GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h

@@ -151 +151 @@
                 }
     };
-        
 
         typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
-        
         
         class VspBspSubdivisionCandidate

GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp

@@ -1856 +1856 @@
 
                                 // add to unbounded view cell
-                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
+                                ViewCell *outOfBounds = GetOrCreateOutOfBoundsCell();
+                                outOfBounds->GetPvs().AddPvs(viewCell->GetPvs());
                                 DEL_PTR(viewCell);
                         }
@@ -1900 +1901 @@
 void VspTree::ValidateTree()
 {
-        mVspStats.invalidLeaves = 0;
-
-        stack<VspNode *> nodeStack;
-
         if (!mRoot)
                 return;
+
+        mVspStats.invalidLeaves = 0;
+        stack<VspNode *> nodeStack;
 
         nodeStack.push(mRoot);
@@ -1947 +1947 @@
                                                                   bool onlyUnmailed) const
 {
-        stack<VspNode *> nodeStack;
-
         if (!root)
                 return;
 
+        stack<VspNode *> nodeStack;
         nodeStack.push(root);
         

GTP/trunk/Lib/Vis/Preprocessing/src/X3dExporter.cpp

@@ -998 +998 @@
 }
 
+
 void X3dExporter::ExportBspSplits(const BspTree &tree,
                                                                   const bool exportDepth)
@@ -1007 +1008 @@
 }
 
+
 void X3dExporter::ExportBspSplits(const VspBspTree &tree,
                                                                   const bool exportDepth)
@@ -1015 +1017 @@
                                                 tree.GetEpsilon());
 }
+
 
 void X3dExporter::ExportBspSplitPlanes(const BspTree &tree)

GTP/trunk/Lib/Vis/Preprocessing/src/X3dParser.cpp

@@ -918 +918 @@
 
                 // create view cell from base triangle
-                mViewCellsManager->AddViewCell(
-                        mViewCellsManager->ExtrudeViewCell(baseTri, 
-                        mViewCellHeight));
+                ViewCell *vc = mViewCellsManager->ExtrudeViewCell(baseTri, mViewCellHeight);
+                mViewCellsManager->mViewCells.push_back(vc);
         }
 }

GTP/trunk/Lib/Vis/Preprocessing/src/main.cpp

@@ -172 +172 @@
         if (0) 
         {
-                preprocessor->Export(filename + "-out.x3d", true, false, false);
-                preprocessor->Export(filename + "-kdtree.x3d", false, true, false);     
+                preprocessor->Export(filename + "-out.x3d", true, false);
+                preprocessor->Export(filename + "-kdtree.x3d", false, true);    
         }