Changeset 1020 for GTP

Timestamp:

06/18/06 03:47:06 (18 years ago)

Author:

mattausch

Message:

worked on view-object space partition
fixed some loading bugs
fixeds some exporting bugs using line segments
enabling other methods for view space sampling in ViewCellsManager? OBJECT_DIRECTION_BASED_DISTRIBUTION)
added class interface for a sampling strategy

Location:

GTP/trunk/Lib/Vis/Preprocessing

Files:

• scripts/Preprocessor.vcproj (modified) (1 diff)
• src/Environment.cpp (modified) (2 diffs)
• src/Intersectable.h (modified) (1 diff)
• src/Mesh.cpp (modified) (5 diffs)
• src/Mesh.h (modified) (4 diffs)
• src/Parser.h (modified) (1 diff)
• src/Preprocessor.cpp (modified) (5 diffs)
• src/Preprocessor.h (modified) (3 diffs)
• src/RenderSimulator.cpp (modified) (2 diffs)
• src/SamplingStrategy.cpp (added)
• src/SamplingStrategy.h (added)
• src/ViewCellsManager.cpp (modified) (23 diffs)
• src/VrmlExporter.cpp (modified) (10 diffs)
• src/VspBspTree.cpp (modified) (44 diffs)
• src/VspBspTree.h (modified) (9 diffs)
• src/VspOspTree.cpp (modified) (31 diffs)
• src/VspOspTree.h (modified) (11 diffs)
• src/X3dExporter.cpp (modified) (2 diffs)
• src/X3dParser.cpp (modified) (11 diffs)
• src/X3dParserXerces.h (modified) (1 diff)

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

@@ -386 +386 @@
                         </File>
                         <File
+                                RelativePath="..\src\SamplingStrategy.cpp">
+                        </File>
+                        <File
+                                RelativePath="..\src\SamplingStrategy.h">
+                        </File>
+                        <File
                                 RelativePath="..\src\SceneGraph.cpp">
                         </File>

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

@@ -1314 +1314 @@
                                         "20000");
 
+        RegisterOption("ViewCells.Visualization.maxOutput",
+                                        optInt,
+                                        "view_cells_visualization_max_output=",
+                                        "20");
+
         RegisterOption("ViewCells.Filter.maxSize",
                                         optInt,
@@ -2047 +2052 @@
                         "0.5");
 
+        RegisterOption("VspBspTree.Construction.renderCostDecreaseWeight",
+                        optFloat,
+                        "vsp_bsp_post_process_render_cost_decrease_weight=",
+                        "0.99");
+
         RegisterOption("VspBspTree.Construction.randomize", 
                 optBool, 

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

@@ -48 +48 @@
 
 
-    virtual AxisAlignedBox3 GetBox() = 0;
+    virtual AxisAlignedBox3 GetBox() const = 0;
         virtual int CastRay(GtpVisibilityPreprocessor::Ray &ray) = 0;
         
-        virtual bool IsConvex() = 0;
-        virtual bool IsWatertight() = 0;
+        virtual bool IsConvex() const = 0;
+        virtual bool IsWatertight() const = 0;
         virtual float IntersectionComplexity() = 0;
   

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

@@ -412 +412 @@
 Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
 {
-  int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));
+  const int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));
   
   // assume the face is convex and generate a convex combination
   //
   Face *face = mFaces[faceIndex];
+ 
   point = Vector3(0,0,0);
   float sum = 0.0f;
+  
   for (int i = 0; i < face->mVertexIndices.size(); i++) {
     float r = RandomValue(0,1);
@@ -603 +605 @@
 
 
-Mesh::Mesh(const Mesh &rhs)
+Mesh::Mesh(const Mesh &rhs):
+mKdTree(NULL)
 {
         mVertices = rhs.mVertices;
@@ -609 +612 @@
         mId = rhs.mId;
         mMaterial = rhs.mMaterial;
-
+        
         FaceContainer::const_iterator it, it_end = rhs.mFaces.end();
 
@@ -766 +769 @@
 
 
-void TransformedMeshInstance::GetWorldTransform(Matrix4x4 &m)
+void TransformedMeshInstance::GetWorldTransform(Matrix4x4 &m) const
 {
         m = mWorldTransform;
@@ -772 +775 @@
 
 
-AxisAlignedBox3 TransformedMeshInstance::GetBox() 
+AxisAlignedBox3 TransformedMeshInstance::GetBox() const 
 {
     return Transform(mMesh->mBox, mWorldTransform);
 }
 
- void TransformedMeshInstance::GetTransformedMesh(Mesh &transformedMesh)
- {
-         // copy mesh
+
+void TransformedMeshInstance::GetTransformedMesh(Mesh &transformedMesh) const
+{
+        // copy mesh
         transformedMesh = *mMesh;
         transformedMesh.ApplyTransformation(mWorldTransform);
- }
-
-}
+}
+
+}

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

@@ -244 +244 @@
   Mesh *GetMesh() { return mMesh; }
 
-  virtual AxisAlignedBox3 GetBox() {
+  virtual AxisAlignedBox3 GetBox() const {
     return mMesh->mBox;
   }
@@ -250 +250 @@
   virtual int CastRay(Ray &ray);
 
-  virtual bool IsConvex() { return mMesh->mIsConvex; }
-  virtual bool IsWatertight() { return mMesh->mIsWatertight; }
+  virtual bool IsConvex() const { return mMesh->mIsConvex; }
+  virtual bool IsWatertight() const { return mMesh->mIsWatertight; }
   virtual float IntersectionComplexity() {  return (float)mMesh->mFaces.size(); }
 
-        virtual int NumberOfFaces() const {  return (int)mMesh->mFaces.size(); }
+  virtual int NumberOfFaces() const {  return (int)mMesh->mFaces.size(); }
 
   virtual int Type() const { return MESH_INSTANCE; }
@@ -297 +297 @@
   TransformedMeshInstance(Mesh *mesh);
   
-  virtual AxisAlignedBox3 GetBox();
+  virtual AxisAlignedBox3 GetBox() const;
    
   
@@ -318 +318 @@
   /** The transformation is returned in m.
   */
-  void GetWorldTransform(Matrix4x4 &m);
+  void GetWorldTransform(Matrix4x4 &m) const;
 
   /** Transforms a mesh according to the stored world transform.
-        @param transformedMesh returns the tranformed mesh.
-  */
-  void GetTransformedMesh(Mesh &transformedMesh);
+          @param transformedMesh returns the tranformed mesh.
+  */
+  void GetTransformedMesh(Mesh &transformedMesh) const;
 
 protected:

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

@@ -17 +17 @@
   virtual bool ParseFile(const std::string filename, 
                                                  SceneGraphNode **root, 
-                                                 const bool loadPolygonsAsMeshes = false) {return false;};
+                                                 const bool loadPolygonsAsMeshes = false) 
+  {return false;};
         
 };

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

@@ -12 +12 @@
 #include "GlRenderer.h"
 #include "PlyParser.h"
+#include "SamplingStrategy.h"
+
+
 
 namespace GtpVisibilityPreprocessor {
 
+const static bool ADDITIONAL_GEOMETRY_HACK = false;
 
 Preprocessor *preprocessor;
@@ -76 +80 @@
                 //Vector3 boxSize = sceneBox.Size() * Vector3(0.0025, 0.01, 0.0025);
                 Vector3 boxSize = sceneBox.Size() * Vector3(0.005, 0.02, 0.005);
+
                 AxisAlignedBox3 box(pt2 + 0.1, pt2 + boxSize);
                 Mesh *mesh = CreateMeshFromBox(box);
@@ -243 +248 @@
         {
                 // HACK 
-                //AddGeometry(mSceneGraph);
-          mSceneGraph->AssignObjectIds();
-                
-          int intersectables, faces;
-          mSceneGraph->GetStatistics(intersectables, faces);
-
-          cout<<filename<<" parsed successfully."<<endl;
-          cout<<"#NUM_OBJECTS (Total numner of objects)\n"<<intersectables<<endl;
-          cout<<"#NUM_FACES (Total numner of faces)\n"<<faces<<endl;
-          mSceneGraph->CollectObjects(&mObjects);
-          mSceneGraph->mRoot->UpdateBox();
-
-         /* Exporter *exporter = Exporter::GetExporter("testload.x3d");
-
-          if (exporter)
-          {
-                  exporter->ExportGeometry(mObjects);
-                  delete exporter;
-          }*/
-
+                if (ADDITIONAL_GEOMETRY_HACK)
+                        AddGeometry(mSceneGraph);
+                
+                mSceneGraph->AssignObjectIds();
+        
+                int intersectables, faces;
+                mSceneGraph->GetStatistics(intersectables, faces);
+        
+                cout<<filename<<" parsed successfully."<<endl;
+                cout<<"#NUM_OBJECTS (Total numner of objects)\n"<<intersectables<<endl;
+                cout<<"#NUM_FACES (Total numner of faces)\n"<<faces<<endl;
+                mSceneGraph->CollectObjects(&mObjects);
+                mSceneGraph->mRoot->UpdateBox();
+
+                if (0)
+                {
+                        Exporter *exporter = Exporter::GetExporter("testload.x3d");
+
+                        if (exporter)
+                        {
+                                exporter->ExportGeometry(mObjects);
+                                delete exporter;
+                        }
+                }
         }
         
@@ -594 +603 @@
 }
 
-
-
+#if 0 // matt: implemented interface samplestrategy
 bool
 Preprocessor::GenerateRays(
@@ -656 +664 @@
   return true;
 }
-
-}
+#endif
+bool Preprocessor::GenerateRays(const int number,
+                                                                const int sampleType,
+                                                                SimpleRayContainer &rays)
+{
+        Vector3 origin, direction; 
+        
+        const int startSize = (int)rays.size();
+        SamplingStrategy *strategy = GenerateSamplingStrategy(sampleType);
+
+        if (!strategy)
+                return false;
+
+        for (int i=0; (int)rays.size() - startSize < number; ++ i) 
+        {
+                SimpleRay newRay;
+                bool success = strategy->GenerateSample(newRay);
+
+                if (success)
+                        rays.AddRay(newRay);
+        }
+
+        delete strategy;
+
+    return true;
+}
+
+
+SamplingStrategy *Preprocessor::GenerateSamplingStrategy(const int strategyId) const
+{
+        switch (strategyId)
+        {
+        case OBJECT_BASED_DISTRIBUTION: 
+                return new ObjectBasedDistribution(*this);
+        case OBJECT_DIRECTION_BASED_DISTRIBUTION:
+                return new ObjectDirectionBasedDistribution(*this);
+        case DIRECTION_BASED_DISTRIBUTION:
+                return new DirectionBasedDistribution(*this);
+        case DIRECTION_BOX_BASED_DISTRIBUTION: 
+                return new DirectionBoxBasedDistribution(*this);
+        case SPATIAL_BOX_BASED_DISTRIBUTION:
+                return new SpatialBoxBasedDistribution(*this);
+        case OBJECTS_INTERIOR_DISTRIBUTION:
+                return new ObjectsInteriorDistribution(*this);
+        default: // no valid strategy
+                return NULL;
+        }
+        // should never come here
+        return NULL;
+}
+
+
+}

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

@@ -21 +21 @@
 class RenderSimulator;
 struct VssRayContainer;
+class SamplingStrategy;
 
 class GlRendererBuffer;
@@ -80 +81 @@
   bool PrepareViewCells();
   
+  /** Returns the specified sample strategy, NULL if no valid strategy.
+  */
+  SamplingStrategy *GenerateSamplingStrategy(const int strategyId) const;
+
   bool
   Export( const string filename,
@@ -115 +120 @@
         RSS_SILHOUETTE_BASED_DISTRIBUTION,
         VSS_BASED_DISTRIBUTION,
-        OBJECT_DIRECTION_BASED_DISTRIBUTION
+        OBJECT_DIRECTION_BASED_DISTRIBUTION,
+        OBJECTS_INTERIOR_DISTRIBUTION
   };
   

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

@@ -12 +12 @@
 void SimulationStatistics::Print(ostream &app) const
 {
-        app << "===== Render Simulation statistics ===============\n";
+        app << "============== Render Simulation statistics ==============\n";
 
         app << setprecision(4);
@@ -36 +36 @@
                 << validAvgRtWithoutOverhead << "\n";
         
-        app << "===== END OF Render Simulation statistics ==========\n";
+        app << "=========== END OF Render Simulation statistics ==========\n";
 }
+
 
 RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager):

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

@@ -8 +8 @@
 #include "ViewCellBsp.h"
 #include "KdTree.h"
-//#include "VspOspTree.h"
+#include "VspOspTree.h"
 #include "Exporter.h"
 #include "VspBspTree.h"
@@ -104 +104 @@
 
         
+        // sampling type for view cells construction samples
         if (strcmp(buf, "box") == 0)
         {
@@ -112 +113 @@
                 mSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION;
         }
-        else 
+        else if (strcmp(buf, "interior") == 0)
+        {
+                mSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION;
+        }
+        else if (strcmp(buf, "object_directional") == 0)
+        {
+                mSamplingType = Preprocessor::OBJECT_DIRECTION_BASED_DISTRIBUTION;
+        }
+        else
         {
                 Debug << "error! wrong sampling type" << endl;
@@ -118 +127 @@
         }
 
+        // sampling type for evaluation samples
         Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.samplingType", buf);
         
@@ -128 +138 @@
                 mEvaluationSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION;
         }
-        else 
+        else if (strcmp(buf, "object_directional") == 0)
+        {
+                mEvaluationSamplingType = Preprocessor::OBJECT_DIRECTION_BASED_DISTRIBUTION;
+        }
+        else if (strcmp(buf, "interior") == 0)
+        {
+                mEvaluationSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION;
+        }
+        else
         {
                 Debug << "error! wrong sampling type" << endl;
@@ -201 +219 @@
 ViewCellsManager::~ViewCellsManager()
 {
-        //DEL_PTR(mRenderer);
-
+        // HACK: if view cells tree does not 
+        // take care of view cells, we have to do it
+        // question: rather create view cells resource manager?
         if (!ViewCellsTreeConstructed())
                 CLEAR_CONTAINER(mViewCells);
-        //else
+        
         DEL_PTR(mViewCellsTree);
 }
@@ -855 +874 @@
         Debug << "view cell stats prefix: " << statsPrefix << endl;
 
-        
         // should directional sampling be used?
         bool dirSamples = (mEvaluationSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION);
-
 
         cout << "reseting pvs ... ";
@@ -1366 +1383 @@
         ViewCellContainer::const_iterator it, it_end = mViewCells.end();
 
-
         //-- compute expected value
-
         totalRenderCost = 0;
         totalPvs = 0;
@@ -2480 +2495 @@
         if (1) // export final view cells
         {
-                mColorCode = 1;
-
+                mColorCode = 1; // hack color code
                 Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
         
@@ -2494 +2508 @@
 
                         //exporter->SetFilled();
-                        bool b = mUseClipPlaneForViz;
+                        const bool b = mUseClipPlaneForViz;
                         mUseClipPlaneForViz = false;
+
                         ExportViewCellsForViz(exporter);
+                        
                         mUseClipPlaneForViz = b;
                         delete exporter;
@@ -3101 +3117 @@
 }
 
+
 int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
                                                                         const VssRayContainer &rays)
@@ -3106 +3123 @@
         return 0;
 }
+
 
 void KdViewCellsManager::Visualize(const ObjectContainer &objects,
@@ -3956 +3974 @@
                 mColorCode = 1;
         
-                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
                 
                 if (exporter)
@@ -3976 +3994 @@
 
                         // export rays
-                        if (mExportRays)
+                        if (1 && mExportRays)
                         {
                                 exporter->ExportRays(visRays, RgbColor(0, 1, 0));
@@ -3982 +4000 @@
 
                         //exporter->SetFilled();
+
                         // HACK: export without clip plane
                         const bool b = mUseClipPlaneForViz;
                         mUseClipPlaneForViz = false;
+
                         ExportViewCellsForViz(exporter);
+                        
                         mUseClipPlaneForViz = b;
-                
                         delete exporter;
+
                         cout << "finished" << endl;
                 }
@@ -4107 +4128 @@
                                                                                   const VssRayContainer &rays)
 {
-        const int leafOut = 20;
+        int leafOut;
+        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
 
         ViewCell::NewMail();
@@ -4116 +4138 @@
 
         const bool sortViewCells = true;
-        
-
         // sort view cells to visualize the largest view cells
         if (sortViewCells)
@@ -4145 +4165 @@
 
                 //bspLeaves[j]->Mail();
-                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
+                char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i);
                 Exporter *exporter = Exporter::GetExporter(s);
                 
@@ -4151 +4171 @@
 
                 //-- export the sample rays
-                if (1 || mExportRays)
+                if (mExportRays)
                 {
                         // output rays stored with the view cells during subdivision
@@ -4219 +4239 @@
                 
 
+                //-- export view cell geometry
                 exporter->SetWireframe();
 
@@ -4228 +4249 @@
         
                 exporter->SetFilled();
+
 
                 //-- export pvs
@@ -4314 +4336 @@
         case 1: // pvs
                 {
-                        importance = (float)mViewCellsTree->GetPvsSize(vc) / (float)mCurrentViewCellsStats.maxPvs;
+                        if (mCurrentViewCellsStats.maxPvs)
+                                importance = (float)mViewCellsTree->GetPvsSize(vc) / (float)mCurrentViewCellsStats.maxPvs;
                 }
                 break;
@@ -4469 +4492 @@
                         if (i != j)
                         {
-
                                 BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaf;
                                 

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

@@ -42 +42 @@
   stream<<"}"<<endl;
   
-  stream<<"IndexedLineSet { coordIndex=\""<<endl;
+  stream<<"geometry IndexedLineSet { coordIndex [" << endl;
 
   int index = 0;
@@ -51 +51 @@
   }
   
-  stream << "}"<<endl;
-  
-  stream<<"<Coordinate  point=\""<<endl;
+  stream << "]"<<endl;
+  
+  stream << "coord Coordinate { point [" << endl;
   
   ri = rays.begin();
@@ -77 +77 @@
           stream << b.x << " " << b.y << " " << b.z << " ,\n";
   }
-  
+  stream << "]" << endl;
   stream << "}" << endl;
   stream << "}" << endl;
   stream << "}" << endl;
-  stream << "}" << endl;
+  //stream << "}" << endl;
 
   return true;
@@ -99 +99 @@
   stream << "}" << endl; // end appearance
   
-  stream << "IndexedLineSet { coordIndex=\"" << endl;
+  stream << "geometry IndexedLineSet { coordIndex [" << endl;
 
   int index = 0;
@@ -108 +108 @@
   }
   
-  stream << "}" << endl;
-  
-  stream << "Coordinate  point= {" << endl;
+  stream << "]" << endl;
+  
+  stream << "coord Coordinate { point [" << endl;
   
   ri = rays.begin();
@@ -121 +121 @@
         stream<<b.x<<" "<<b.y<<" "<<b.z<<" ,\n";
   }
-  
+  stream << "]" << endl;
   stream << "}" << endl;
   stream << "}" << endl;
   stream << "}" << endl;
-  stream << "}" << endl;
+  //stream << "}" << endl;
         
   return true;
@@ -215 +215 @@
         tStack.push(pair<BspNode *, BspNodeGeometry *>(tree.GetRoot(), geom));
 
-        if (maxPvs > 0)
+        if (maxPvs)
                 mUseForcedMaterial = true;
-
+        
         while (!tStack.empty()) 
         {
@@ -242 +242 @@
                 else
                 {
-                        if (maxPvs > 0)
+                        if (maxPvs)
                         {
                                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
 
                                 mForcedMaterial.mDiffuseColor.b = 1.0f;
-                                float importance = (float)leaf->GetViewCell()->GetPvs().GetSize() / (float)maxPvs;
+                                const float importance = (float)leaf->GetViewCell()->GetPvs().GetSize() / (float)maxPvs;
 
                                 mForcedMaterial.mDiffuseColor.r = importance;
@@ -599 +599 @@
         //Mesh *mesh = new Mesh;
   
-        if (maxPvs > 0)
+        if (maxPvs)
                 mUseForcedMaterial = true;
 
@@ -632 +632 @@
                         mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) );
 
-                        if (maxPvs > 0)
+                        if (maxPvs)
                         {
                                 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);

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

@@ -21 +21 @@
 
 #define USE_FIXEDPOINT_T 0
-
-
+#define COUNT_ORIGIN_OBJECTS 1
+
+        
 //-- static members
-
 
 int VspBspTree::sFrontId = 0;
 int VspBspTree::sBackId = 0;
 int VspBspTree::sFrontAndBackId = 0;
+
+
 
 typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
@@ -113 +115 @@
 
         Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
+        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
         Environment::GetSingleton()->GetBoolValue("VspBspTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable);
 
@@ -161 +164 @@
         Debug << "maxband: " << mMaxBand << endl;
         Debug << "use driving axis for max cost: " << mUseDrivingAxisIfMaxCostViolated << endl;
+        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
 
         Debug << "Split plane strategy: ";
@@ -189 +193 @@
 
 
-        mSplitCandidates = new vector<SortableEntry>;
+        mLocalSplitCandidates = new vector<SortableEntry>;
 
         Debug << endl;
@@ -236 +240 @@
 {
         DEL_PTR(mRoot);
-        DEL_PTR(mSplitCandidates);
+        DEL_PTR(mLocalSplitCandidates);
 }
 
@@ -497 +501 @@
         const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
 
+        /// first traversal data
         VspBspTraversalData tData(mRoot,
                                                           new PolygonContainer(polys),
@@ -520 +525 @@
         mTotalPvsSize = tData.mPvs;
         
-        // first stats
-        mSubdivisionStats 
-                        << "#ViewCells\n1" <<  endl
-                        << "#RenderCostDecrease\n0" << endl 
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-
-
+        // first subdivison statistics
+        AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize);
+    
         mBspStats.Start();
         cout << "Constructing vsp bsp tree ... \n";
@@ -586 +584 @@
 
         Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
-        cout << "finished\n";
+        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
 
         mBspStats.Stop();
@@ -624 +622 @@
         mTotalPvsSize = tData.mPvs;
         
-        mSubdivisionStats 
-                        << "#ViewCells\n1\n" <<  endl
-                        << "#RenderCostDecrease\n0\n" << endl 
-                        << "#SplitCandidateCost\n0\n" << endl
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-        
-        
-        mBspStats.Start();
+        // first subdivison statistics
+        AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize);
+   
+    mBspStats.Start();
         cout << "Constructing vsp bsp tree ... \n";
 
@@ -654 +645 @@
 
                 // cost ratio of cost decrease / totalCost
-                float costRatio = splitCandidate.GetCost() / mTotalCost;
+                float costRatio = splitCandidate.GetPriority() / mTotalCost;
 
                 //Debug << "cost ratio: " << costRatio << endl;
@@ -716 +707 @@
 
 
+void VspBspTree::AddSubdivisionStats(const int viewCells,
+                                                                         const float renderCostDecr,
+                                                                         const float splitCandidateCost,
+                                                                         const float totalRenderCost,
+                                                                         const float avgRenderCost)
+{
+        mSubdivisionStats 
+                        << "#ViewCells\n" << viewCells << endl
+                        << "#RenderCostDecrease\n" << renderCostDecr << endl 
+                        << "#SplitCandidateCost\n" << splitCandidateCost << endl
+                        << "#TotalRenderCost\n" << totalRenderCost << endl
+                        << "#AvgRenderCost\n" << avgRenderCost << endl;
+}
+
+
 bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const
 {
@@ -726 +732 @@
 
 
-
 BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
                                                            VspBspTraversalData &tData)
@@ -785 +790 @@
                         if (1)
                         {
-                                float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
-                                float cBack = (float)tBackData.mPvs * tBackData.mProbability;
-                                float cData = (float)tData.mPvs * tData.mProbability;;
-
-                float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
+                                const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+                                const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+                                const float cData = (float)tData.mPvs * tData.mProbability;;
+
+                const float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
 
                                 mTotalCost += costDecr;
                                 mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
 
-                                mSubdivisionStats 
-                                                << "#ViewCells\n" << mBspStats.Leaves() << endl
-                                                << "#RenderCostDecrease\n" << -costDecr << endl 
-                                                << "#TotalRenderCost\n" << mTotalCost << endl
-                                                << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
+                                AddSubdivisionStats(mBspStats.Leaves(),
+                                                                    -costDecr,
+                                                                        0,
+                                                                        mTotalCost,
+                                                                        (float)mTotalPvsSize / (float)mBspStats.Leaves());
                         }
 
@@ -814 +819 @@
         {
                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+                
                 BspViewCell *viewCell = new BspViewCell();
-                
                 leaf->SetViewCell(viewCell);
         
@@ -860 +865 @@
                 leaf->mProbability = tData.mProbability;
 
+                // finally evaluate stats until this leaf
                 EvaluateLeafStats(tData);               
         }
@@ -906 +912 @@
                 tBackData.mMaxCostMisses = maxCostMisses;
                         
-                
+                // statistics
                 if (1)
                 {
@@ -920 +926 @@
                         mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
 
-                        mSubdivisionStats 
-                                        << "#ViewCells\n" << mBspStats.Leaves() << endl
-                                        << "#RenderCostDecrease\n" << -costDecr << endl
-                                        << "#SplitCandidateCost\n" << splitCandidate.GetCost() << endl
-                                        << "#TotalRenderCost\n" << mTotalCost << endl
-                                        << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
+                        AddSubdivisionStats(mBspStats.Leaves(), 
+                                                                -costDecr,  
+                                                                splitCandidate.GetPriority(), 
+                                                                mTotalCost, 
+                                                                (float)mTotalPvsSize / (float)mBspStats.Leaves());
                 }
 
@@ -948 +953 @@
         {
                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+
                 BspViewCell *viewCell = new BspViewCell();
-
         leaf->SetViewCell(viewCell);
                 
@@ -974 +979 @@
                 }
 
-                // should I check here?
+                
                 viewCell->mLeaf = leaf;
 
@@ -984 +989 @@
         leaf->mProbability = tData.mProbability;
 
+                // finally evaluate stats until this leaf
                 EvaluateLeafStats(tData);               
         }
@@ -1029 +1035 @@
         
         // compute global decrease in render cost
-        splitData.mRenderCost = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
+        splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
         splitData.mParentData = tData;
         splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
@@ -1192 +1198 @@
           
                 // only count termination objects?
-                if (1 && ray->mOriginObject) 
+                if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject) 
                 {
                         if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
                                 madeContrib = true;
+
                         sc += contribution;
                 }
@@ -1214 +1221 @@
                                                                          float maxBand)
 {
-        mSplitCandidates->clear();
+        mLocalSplitCandidates->clear();
 
         int requestedSize = 2 * (int)(rays.size());
         // creates a sorted split candidates array
-        if (mSplitCandidates->capacity() > 500000 &&
-                requestedSize < (int)(mSplitCandidates->capacity() / 10) )
-        {
-        delete mSplitCandidates;
-                mSplitCandidates = new vector<SortableEntry>;
-        }
-
-        mSplitCandidates->reserve(requestedSize);
+        if (mLocalSplitCandidates->capacity() > 500000 &&
+                requestedSize < (int)(mLocalSplitCandidates->capacity() / 10) )
+        {
+        delete mLocalSplitCandidates;
+                mLocalSplitCandidates = new vector<SortableEntry>;
+        }
+
+        mLocalSplitCandidates->reserve(requestedSize);
 
         float pos;
@@ -1245 +1252 @@
                 if (0) ClipValue(pos, minBand, maxBand);
                 
-                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
+                mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
                                                                         pos, (*ri).mRay));
 
@@ -1252 +1259 @@
                 if (0) ClipValue(pos, minBand, maxBand);
 
-                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
+                mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
                                                                         pos, (*ri).mRay));
         }
 
-        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
+        stable_sort(mLocalSplitCandidates->begin(), mLocalSplitCandidates->end());
 }
 
@@ -1307 +1314 @@
                 Intersectable *tObject = (*ri).mRay->mTerminationObject;
 
-                if (oObject)
+                if (COUNT_ORIGIN_OBJECTS && oObject)
                 {
                         if (!oObject->Mailed())
@@ -1319 +1326 @@
                         }
                 }
+
                 if (tObject)
                 {
@@ -1335 +1343 @@
         Intersectable::NewMail();
 
-        vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
-
-        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
+        vector<SortableEntry>::const_iterator ci, ci_end = mLocalSplitCandidates->end();
+
+        for (ci = mLocalSplitCandidates->begin(); ci != ci_end; ++ ci)
         {
                 VssRay *ray;
@@ -1350 +1358 @@
                         case SortableEntry::ERayMin:
                                 {
-                                        if (oObject && !oObject->Mailed())
+                                        if (COUNT_ORIGIN_OBJECTS && oObject && !oObject->Mailed())
                                         {
                                                 oObject->Mail();
                                                 ++ pvsl;
                                         }
+
                                         if (tObject && !tObject->Mailed())
                                         {
@@ -1360 +1369 @@
                                                 ++ pvsl;
                                         }
+
                                         break;
                                 }
                         case SortableEntry::ERayMax:
                                 {
-                                        if (oObject)
+                                        if (COUNT_ORIGIN_OBJECTS && oObject)
                                         {
                                                 if (-- oObject->mCounter == 0)
@@ -1379 +1389 @@
                                 }
                 }
-
-                
-                
-                // Note: sufficient to compare size of bounding boxes of front and back side?
+                
+                
+                // Note: we compare size of bounding boxes of front and back side because
+                // of efficiency reasons (otherwise a new geometry would have to be computed
+                // in each step and incremential evaluation would be difficult.
+                // but then errors happen if the geometry is not an axis aligned box 
+                // (i.e., if a geometry aligned split was taken before)
+                // question: is it sufficient to make this approximation?
                 if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
                 {
@@ -1873 +1887 @@
                 // find front and back pvs for origing and termination object
                 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+
+                if (COUNT_ORIGIN_OBJECTS) 
+                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
         }
 
@@ -1910 +1926 @@
 
         // -- pvs rendering heuristics
+
+        // upper and lower bounds
         const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
         const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
 
-        // only render cost heuristics or combined with standard deviation
-        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
+        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
                         
         const float oldRenderCost = pOverall * penaltyOld;
@@ -1924 +1941 @@
         const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume();
         
-
-#if 1
+        const float weight = mRenderCostDecreaseWeight;
         // take render cost of node into account to avoid being stuck in a local minimum
         const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
         
-        //Debug << "rendercostdecr: " << 0.99f * renderCostDecrease << " old render cost: " << 0.01f * normalizedOldRenderCost << endl;
-        return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
-#else
-        return renderCostDecrease;
-#endif
+        //Debug << "rendercostdecr: " << weight * renderCostDecrease << " old render cost: " << (1.0f - weight) * normalizedOldRenderCost << endl;
+        return weight * renderCostDecrease + (1.0f - weight) * normalizedOldRenderCost;
 }
 
@@ -1944 +1957 @@
                                                                          float &pBack) const
 {
-        float cost = 0;
-
         float totalPvs = 0;
         float pvsFront = 0;
@@ -1957 +1968 @@
         pBack = 0;
 
-
-        int limit;
-        bool useRand;
-
+        int numTests; // the number of tests
+
+        // if random samples shold be taken instead of testing all the rays
+        bool useRand; 
+
+        if ((int)data.mRays->size() > mMaxTests)
+        {
+                useRand = true;
+                numTests = mMaxTests;
+        }
+        else
+        {
+                useRand = false;
+                numTests = (int)data.mRays->size();
+        }
+        
         // create unique ids for pvs heuristics
         GenerateUniqueIdsForPvs();
 
-        // choose test rays randomly if too much
-        if ((int)data.mRays->size() > mMaxTests)
-        {
-                useRand = true;
-                limit = mMaxTests;
-        }
-        else
-        {
-                useRand = false;
-                limit = (int)data.mRays->size();
-        }
-        
-        for (int i = 0; i < limit; ++ i)
+        for (int i = 0; i < numTests; ++ i)
         {
                 const int testIdx = useRand ? 
@@ -1988 +1999 @@
                 // find front and back pvs for origing and termination object
                 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+
+                if (COUNT_ORIGIN_OBJECTS) 
+                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
         }
 
@@ -2057 +2070 @@
         }
 
-        cost += mPvsFactor * newCost / (oldCost + Limits::Small);
+        const float cost = mPvsFactor * newCost / (oldCost + Limits::Small);
                 
 
@@ -2165 +2178 @@
         for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
         {
-                //if (!(*rit).mRay->IsActive()) continue;
-
                 // determine the side of this ray with respect to the plane
                 float t;
@@ -2172 +2183 @@
         
                 AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
-                AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
-        }
+
+                if (COUNT_ORIGIN_OBJECTS) 
+                        AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
+        }
+
 
         //-- pvs heuristics
-        float pOverall;
-
-        //-- compute heurstics
-        //-- we take simplified computation for mid split
-                
-        pOverall = data.mProbability;
-
+
+        float pOverall = data.mProbability;
+
+        // note: we use a simplified computation assuming that we always do a
+        // spatial mid split    
+        
         if (!mUseAreaForPvs)
-        {   // volume
+        {   
+                // volume
                 pBack = pFront = pOverall * 0.5f;
-                
 #if 0
                 // box length substitute for probability
@@ -3220 +3233 @@
                 VssRay *ray = (*rit).mRay;
 
-                if (ray->mOriginObject)
+                if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject)
                 {
                         if (!ray->mOriginObject->Mailed())
@@ -3228 +3241 @@
                         }
                 }
+
                 if (ray->mTerminationObject)
                 {
@@ -3343 +3357 @@
                         }
                         else // one of the ray end points is on the plane
-                        {       // NOTE: what to do if ray is coincident with plane?
+                        {       
+                                // NOTE: what to do if ray is coincident with plane?
                                 if (extSide < 0)
                                         node = in->GetBack();
@@ -3365 +3380 @@
                         ViewCell *viewCell;
                         
+                        // question: always contribute to leaf or to currently active view cell?
                         if (0)
                                 viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());

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

@@ -168 +168 @@
                 VspBspTraversalData mParentData;
                 // prioriry of this split
-                float mRenderCost;
-
-                VspBspSplitCandidate(): mRenderCost(0) 
+                float mPriority;
+
+                VspBspSplitCandidate(): mPriority(0) 
                 {};
 
                 VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 
-                mSplitPlane(plane), mParentData(tData), mRenderCost(0)
+                mSplitPlane(plane), mParentData(tData), mPriority(0)
                 {}
 
                 /** Returns cost of the traversal data.
                 */
-                float GetCost() const
+                float GetPriority() const
                 {
 #if 1
-                        return mRenderCost;
+                        return mPriority;
 #else
                         return (float) (-mDepth); // for kd tree
@@ -190 +190 @@
                 friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b)
                 {
-                        return a.GetCost() < b.GetCost();
+                        return a.GetPriority() < b.GetPriority();
                 }
     };
@@ -211 +211 @@
         /** Constructs the tree from a given set of rays.
                 @param sampleRays the set of sample rays the construction is based on
-                @param viewCells if not NULL, new view cells are 
-                created in the leafs and stored in the container
+                @param forcedBoundingBox overwrites the view space box
         */
         void Construct(const VssRayContainer &sampleRays,
@@ -454 +453 @@
                                            VspBspTraversalData &tData);
 
+        /** Subdivides node using a best split priority queue.
+            @param tQueue the best split priority queue
+                @param splitCandidate the candidate for the next split
+                @returns new root of the subtree
+        */
         BspNode *Subdivide(VspBspSplitQueue &tQueue,
                                            VspBspSplitCandidate &splitCandidate);
@@ -459 +463 @@
         /** Constructs the tree from the given traversal data.
                 @param polys stores set of polygons on which subdivision may be based
-                @param rays storesset of rays on which subdivision may be based
+                @param rays stores set of rays on which subdivision may be based
         */
         void Construct(const PolygonContainer &polys, RayInfoContainer *rays);
@@ -496 +500 @@
 
         /** Subdivides 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 tData data object holding, e.g., a pointer to the leaf
+                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
+                @param backData returns the data (e.g.,  pointer to the leaf) 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
+                @param coincident returns the polygons which are coincident to the plane and thus discarded 
+                for traversal
 
                 @returns the root of the subdivision
@@ -699 +703 @@
 
 
+        /** Adds stats to subdivision log file.
+        */
+        void AddSubdivisionStats(const int viewCells,
+                                                         const float renderCostDecr,
+                                                         const float splitCandidateCost,
+                                                         const float totalRenderCost,
+                                                         const float avgRenderCost);
 
         ///////////////////////////////////////////////////////////
@@ -716 +727 @@
 
         /// sorted split candidates used for sweep-heuristics
-        vector<SortableEntry> *mSplitCandidates;
+        vector<SortableEntry> *mLocalSplitCandidates;
 
         /// box around the whole view domain
@@ -837 +848 @@
         // if rays should be stored in leaves
         bool mStoreRays;
-        /// render cost weight between expected value and variance
+        /// weight between  render cost (expected value) and variance
         float mRenderCostWeight;
-        
+        /// weight between  render cost decrease and node render cost
+        float mRenderCostDecreaseWeight;
 
         //-- subdivision statistics

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

@@ -16 +16 @@
 #include "ViewCellsManager.h"
 #include "Beam.h"
+#include "KdTree.h"
+
 
 namespace GtpVisibilityPreprocessor {
@@ -381 +383 @@
 
 
-void VspTree::Construct(const VssRayContainer &sampleRays,
-                                                   AxisAlignedBox3 *forcedBoundingBox)
+void VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
+                                                                  AxisAlignedBox3 *forcedBoundingBox) 
 {
         mVspStats.nodes = 1;
-        mBox.Initialize();      // initialise BSP tree bounding box
+        mBoundingBox.Initialize();      // initialise vsp tree bounding box
 
         if (forcedBoundingBox)
-                mBox = *forcedBoundingBox;
-        
-        PolygonContainer polys;
-        RayInfoContainer *rays = new RayInfoContainer();
-
+                mBoundingBox = *forcedBoundingBox;
+        
         VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
 
-        long startTime = GetTime();
-
-        cout << "Extracting polygons from rays ... ";
-
         Intersectable::NewMail();
 
-        int numObj = 0;
-
-        //-- store rays
+        //-- compute bounding box
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
         {
                 VssRay *ray = *rit;
 
-                float minT, maxT;
-
-                static Ray hray;
-                hray.Init(*ray);
-
-                // TODO: not very efficient to implictly cast between rays types
-                if (mBox.GetRaySegment(hray, minT, maxT))
-                {
-                        float len = ray->Length();
-
-                        if (!len)
-                                len = Limits::Small;
-
-                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
-                }
-        }
-
-        mTermMinProbability *= mBox.GetVolume();
-
+                // compute bounding box of view space
+                if (!forcedBoundingBox)
+                {
+                        mBoundingBox.Include(ray->GetTermination());
+                        mBoundingBox.Include(ray->GetOrigin());
+                }
+        }
+
+        mTermMinProbability *= mBoundingBox.GetVolume();
         mGlobalCostMisses = 0;
-
-        cout << "finished" << endl;
-
-        // use split cost priority queue
-        Construct(rays);
+}
+
+
+void VspTree::AddSubdivisionStats(const int viewCells,
+                                                                  const float renderCostDecr,
+                                                                  const float splitCandidateCost,
+                                                                  const float totalRenderCost,
+                                                                         const float avgRenderCost)
+{
+        mSubdivisionStats 
+                        << "#ViewCells\n" << viewCells << endl
+                        << "#RenderCostDecrease\n" << renderCostDecr << endl 
+                        << "#SplitCandidateCost\n" << splitCandidateCost << endl
+                        << "#TotalRenderCost\n" << totalRenderCost << endl
+                        << "#AvgRenderCost\n" << avgRenderCost << endl;
 }
 
@@ -449 +442 @@
 
 
-void VspTree::Construct(RayInfoContainer *rays)
-{
-#if TODO
-        VspSplitQueue tQueue;
-        /// create new vsp tree
-        mRoot = new VspLeaf();
-        /// we use the overall probability as normalizer
-        const float prop = mBox.GetVolume();
-
-        VspTraversalData tData(mRoot,
-                                                  0,
-                                                  rays,
-                          ComputePvsSize(*rays),
-                                                  prop,
-                                                  mBox);
-
-
-        // compute first split candidate
-        VspSplitCandidate splitCandidate;
-        EvalSplitCandidate(tData, splitCandidate);
-
-        tQueue.push(splitCandidate);
-
-        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
-        mTotalPvsSize = tData.mPvs;
-        
-        mSubdivisionStats 
-                        << "#ViewCells\n1\n" <<  endl
-                        << "#RenderCostDecrease\n0\n" << endl 
-                        << "#SplitCandidateCost\n0\n" << endl
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-        
-        
-        mVspStats.Start();
-        cout << "Constructing vsp bsp tree ... \n";
-
-        long startTime = GetTime();     
-        int nLeaves = 500;
-        int nViewCells = 500;
-
-        // used for intermediate time measurements and progress
-        long interTime = GetTime();     
-
-        mOutOfMemory = false;
-
-        mCreatedViewCells = 0;
-        
-        while (!tQueue.empty())
-        {
-                splitCandidate = tQueue.top();
-            tQueue.pop();               
-
-                // cost ratio of cost decrease / totalCost
-                float costRatio = splitCandidate.GetCost() / mTotalCost;
-
-                //Debug << "cost ratio: " << costRatio << endl;
-
-                if (costRatio < mTermMinGlobalCostRatio)
-                        ++ mGlobalCostMisses;
-                
-                if (0 && !mOutOfMemory)
-                {
-                        float mem = GetMemUsage();
-
-                        if (mem > mMaxMemory)
-                        {
-                                mOutOfMemory = true;
-                                Debug << "memory limit reached: " << mem << endl;
-                        }
-                }
-
-                // subdivide leaf node
-                VspNode *r = Subdivide(tQueue, splitCandidate);
-
-                if (r == mRoot)
-                        Debug << "VSP BSP tree construction time spent at root: "
-                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
-
-                if (mVspStats.Leaves() >= nLeaves)
-                {
-                        nLeaves += 500;
-
-                        cout << "leaves=" << mVspStats.Leaves() << endl;
-                        Debug << "needed "
-                                  << TimeDiff(interTime, GetTime())*1e-3 
-                                  << " secs to create 500 view cells" << endl;
-                        interTime = GetTime();
-                }
-
-                if (mCreatedViewCells == nViewCells)
-                {
-                        nViewCells += 500;
-
-                        cout << "generated " << mCreatedViewCells << " viewcells" << endl;
-                }
-        }
-
-        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
-        cout << "finished\n";
-
-        mVspStats.Stop();
-#endif
-}
-
-
 bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
 {
@@ -577 +462 @@
 
 
-// subdivide using a split plane queue
 VspNode *VspTree::Subdivide(SplitQueue &tQueue,
-                                                        VspSplitCandidate &splitCandidate)
+                                                        VspSplitCandidate &splitCandidate,
+                                                        const bool globalCriteriaMet)
 {
         VspTraversalData &tData = splitCandidate.mParentData;
@@ -585 +470 @@
         VspNode *newNode = tData.mNode;
 
-        if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
+        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
         {       
                 VspTraversalData tFrontData;
@@ -594 +479 @@
                 // create new interior node and two leaf node
                 const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
-
                 newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
         
@@ -604 +488 @@
                 tBackData.mMaxCostMisses = maxCostMisses;
                         
-                
+                //-- statistics
                 if (1)
                 {
-                        float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
-                        float cBack = (float)tBackData.mPvs * tBackData.mProbability;
-                        float cData = (float)tData.mPvs * tData.mProbability;
-
-                        
-                        float costDecr = 
-                                (cFront + cBack - cData) / mBox.GetVolume();
+                        const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+                        const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+                        const float cData = (float)tData.mPvs * tData.mProbability;
+        
+                        const float costDecr = 
+                                (cFront + cBack - cData) / mBoundingBox.GetVolume();
 
                         mTotalCost += costDecr;
                         mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
 
-                        mSubdivisionStats 
-                                        << "#ViewCells\n" << mVspStats.Leaves() << endl
-                                        << "#RenderCostDecrease\n" << -costDecr << endl
-                                        << "#SplitCandidateCost\n" << splitCandidate.GetPriority() << endl
-                                        << "#TotalRenderCost\n" << mTotalCost << endl
-                                        << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mVspStats.Leaves() << endl;
-                }
-
-        
-                //-- push the new split candidates on the stack
-                VspSplitCandidate frontCandidate;
-                VspSplitCandidate backCandidate;
-
-                EvalSplitCandidate(tFrontData, frontCandidate);
-                EvalSplitCandidate(tBackData, backCandidate);
-#if TODO
+                        AddSubdivisionStats(mVspStats.Leaves(),
+                                                                -costDecr,
+                                                                splitCandidate.GetPriority(),
+                                                                mTotalCost,
+                                                                (float)mTotalPvsSize / (float)mVspStats.Leaves());
+                }
+
+        
+                //-- push the new split candidates on the queue
+                VspSplitCandidate *frontCandidate = new VspSplitCandidate();
+                VspSplitCandidate *backCandidate = new VspSplitCandidate();
+
+                EvalSplitCandidate(tFrontData, *frontCandidate);
+                EvalSplitCandidate(tBackData, *backCandidate);
+
                 tQueue.push(frontCandidate);
                 tQueue.push(backCandidate);
-#endif
+
                 // delete old leaf node
                 DEL_PTR(tData.mNode);
@@ -646 +528 @@
         {
                 VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode);
+        
                 VspViewCell *viewCell = new VspViewCell();
-
         leaf->SetViewCell(viewCell);
                 
@@ -671 +553 @@
                         }
                 }
-
-                // should I check here?
+                
                 viewCell->mLeaf = leaf;
 
@@ -678 +559 @@
         leaf->mProbability = tData.mProbability;
 
-                EvaluateLeafStats(tData);               
+                // finally evaluate stats until this leaf
+                EvaluateLeafStats(tData);
         }
 
         //-- cleanup
         tData.Clear();
-
+        
         return newNode;
 }
@@ -691 +573 @@
                                                                  VspSplitCandidate &splitData)
 {
-        VspTraversalData frontData;
-        VspTraversalData backData;
-
+        float frontProb;
+        float backtProb;
+        
         VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
-
+        
         // compute locally best split plane
         const bool success = 
                 SelectPlane(tData, splitData.mSplitPlane,
-                                        frontData.mProbability, backData.mProbability);
+                                        frontProb, backtProb);
 
         //TODO
@@ -789 +671 @@
         return interior;
 }
-
-/*
-KdNode *VspOpsTree::SubdivideSpatialNode(KdLeaf *leaf,
-                                                                                 const AxisAlignedPlane &splitPlane,
-                                                                                 const AxisAlignedBox3 &box,
-                                                                                 AxisAlignedBox3 &backBBox,
-                                                                                 AxisAlignedBox3 &frontBBox)
-{
-        float position;
-
-#if TODO
-    mSpatialStat.nodes += 2;
-        mSpatialStat.splits[axis];
-#endif
-
-        // add the new nodes to the tree
-        KdInterior *node = new KdInterior(leaf->mParent);
-
-        node->mAxis = splitPlane.mAxis;
-        node->mPosition = splitPlane.mPosition;
-        node->mBox = box;
-
-    backBBox = box;
-        frontBBox = box;
-  
-        // first count ray sides
-        int objectsBack = 0;
-        int objectsFront = 0;
-  
-        backBBox.SetMax(axis, position);
-        frontBBox.SetMin(axis, position);
-
-        SplitObjects(leaf->m
-        ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
-
-        for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi) 
-        {
-                // determine the side of this ray with respect to the plane
-                AxisAlignedBox3 box = (*mi)->GetBox();
-                
-                if (box.Max(axis) > position ) 
-                        ++ objectsFront;
-    
-                if (box.Min(axis) < position )
-      objectsBack++;
-  }
-
-  
-  KdLeaf *back = new KdLeaf(node, objectsBack);
-  KdLeaf *front = new KdLeaf(node, objectsFront);
-
-  // replace a link from node's parent
-  if (  leaf->mParent )
-    leaf->mParent->ReplaceChildLink(leaf, node);
-
-  // and setup child links
-  node->SetupChildLinks(back, front);
-  
-  for (mi = leaf->mObjects.begin();
-       mi != leaf->mObjects.end();
-       mi++) {
-    // determine the side of this ray with respect to the plane
-    AxisAlignedBox3 box = (*mi)->GetBox();
-
-    if (box.Max(axis) >= position )
-      front->mObjects.push_back(*mi);
-    
-    if (box.Min(axis) < position )
-      back->mObjects.push_back(*mi);
-    
-    mStat.objectRefs -= (int)leaf->mObjects.size();
-    mStat.objectRefs += objectsBack + objectsFront;
-  }
-  
-  delete leaf;
-  return node;
-}
-*/
-
 
 
@@ -1267 +1070 @@
                 
 
-        // -- pvs rendering heuristics
+        //-- pvs rendering heuristics
         const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
         const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
 
-        // only render cost heuristics or combined with standard deviation
-        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+        //-- only render cost heuristics or combined with standard deviation
+        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
+        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
                         
         const float oldRenderCost = pOverall * penaltyOld;
@@ -1280 +1083 @@
 
         //Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
-        const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume();
+        const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
         
 
 #if 1
-        // take render cost of node into account to avoid being stuck in a local minimum
-        const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
+        // take render cost of node into account 
+        // otherwise danger of being stuck in a local minimum!!
+        const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
         return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
 #else
@@ -1434 +1238 @@
 AxisAlignedBox3 VspTree::GetBoundingBox() const
 {
-        return mBox;
+        return mBoundingBox;
 }
 
@@ -1581 +1385 @@
 void VspTree::ValidateTree()
 {
+        mVspStats.invalidLeaves = 0;
+
         stack<VspNode *> nodeStack;
 
@@ -1587 +1393 @@
 
         nodeStack.push(mRoot);
-        
-        mVspStats.invalidLeaves = 0;
+
         while (!nodeStack.empty()) 
         {
@@ -1662 +1467 @@
                 }
         }
-
 }
 
 
 int VspTree::FindNeighbors(VspLeaf *n,
-                                                          vector<VspLeaf *> &neighbors,
-                                                          const bool onlyUnmailed) const
+                                                   vector<VspLeaf *> &neighbors,
+                                                   const bool onlyUnmailed) const
 {
         stack<VspNode *> nodeStack;
-
         nodeStack.push(mRoot);
 
@@ -1946 +1749 @@
         float maxt, mint;
 
-        if (!mBox.GetRaySegment(ray, mint, maxt))
+        if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
                 return 0;
 
@@ -1978 +1781 @@
                                         // cases N1,N2,N3,P5,Z2,Z3
                                         continue;
-                                } else
+                                } 
+                                else
                                 {
                                         // case N4
@@ -2020 +1824 @@
                                 ++ hits;
                         }
-
 #if 0
-                                leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
+                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
 #endif
                         // get the next node from the stack
@@ -2088 +1891 @@
 {
         int collapsed = 0;
-        //TODO
-#if HAS_TO_BE_REDONE
+
         (void)CollapseTree(mRoot, collapsed);
-
         // revalidate leaves
         RepairViewCellsLeafLists();
-#endif
+
         return collapsed;
 }
@@ -2286 +2087 @@
 
 int VspTree::SplitRays(const AxisAlignedPlane &plane,
-                                                  RayInfoContainer &rays,
-                                                  RayInfoContainer &frontRays,
-                                                  RayInfoContainer &backRays) const
+                                           RayInfoContainer &rays,
+                                           RayInfoContainer &frontRays,
+                                           RayInfoContainer &backRays) const
 {
         int splits = 0;
@@ -2338 +2139 @@
 {
         if (!node->GetParent())
-                return mBox;
+                return mBoundingBox;
 
         if (!node->IsLeaf())
@@ -2358 +2159 @@
 
 
+
+/*****************************************************************/
+/*                class OpsTree implementation                   */
+/*****************************************************************/
+
+
+void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
+                                                   const ObjectContainer &objects,
+                                                   ObjectContainer &back,
+                                                   ObjectContainer &front)
+{
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+    for (oit = objects.begin(); oit != oit_end; ++ oit) 
+        {
+                // determine the side of this ray with respect to the plane
+                const AxisAlignedBox3 box = (*oit)->GetBox();
+
+                if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
+            front.push_back(*oit);
+    
+                if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
+                        back.push_back(*oit);
+#if TODO    
+                mStat.objectRefs -= (int)objects.size();
+                mStat.objectRefs += objectsBack + objectsFront;
+#endif
+        }
+}
+
+
+KdInterior *OspTree::SubdivideNode(KdLeaf *leaf,
+                                                                   const AxisAlignedPlane &splitPlane,
+                                                                   const AxisAlignedBox3 &box,
+                                                                   AxisAlignedBox3 &backBBox,
+                                                                   AxisAlignedBox3 &frontBBox)
+{
+#if TODO
+    mSpatialStat.nodes += 2;
+        mSpatialStat.splits[axis];
+#endif
+
+        // add the new nodes to the tree
+        KdInterior *node = new KdInterior(leaf->mParent);
+
+        const int axis = splitPlane.mAxis;
+        const float position = splitPlane.mPosition;
+
+        node->mAxis = axis;
+        node->mPosition = position;
+        node->mBox = box;
+
+    backBBox = box;
+        frontBBox = box;
+  
+        // first count ray sides
+        int objectsBack = 0;
+        int objectsFront = 0;
+  
+        backBBox.SetMax(axis, position);
+        frontBBox.SetMin(axis, position);
+
+        ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
+
+        for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi) 
+        {
+                // determine the side of this ray with respect to the plane
+                const AxisAlignedBox3 box = (*mi)->GetBox();
+                
+                if (box.Max(axis) > position) 
+                        ++ objectsFront;
+    
+                if (box.Min(axis) < position)
+                        ++ objectsBack;
+        }
+
+        KdLeaf *back = new KdLeaf(node, objectsBack);
+        KdLeaf *front = new KdLeaf(node, objectsFront);
+
+        // replace a link from node's parent
+        if (leaf->mParent)
+                leaf->mParent->ReplaceChildLink(leaf, node);
+
+        // and setup child links
+        node->SetupChildLinks(back, front);
+
+        SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
+  
+        //delete leaf;
+        return node;
+}
+
+
+KdNode *OspTree::Subdivide(SplitQueue &tQueue,
+                                                   OspSplitCandidate &splitCandidate,
+                                                   const bool globalCriteriaMet)
+{
+        OspTraversalData &tData = splitCandidate.mParentData;
+
+        KdNode *newNode = tData.mNode;
+
+        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
+        {       
+                OspTraversalData tFrontData;
+                OspTraversalData tBackData;
+
+                //-- continue subdivision
+                
+                // create new interior node and two leaf node
+                const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
+                newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode), 
+                                                                splitPlane, 
+                                                                tData.mBoundingBox, 
+                                                                tFrontData.mBoundingBox, 
+                                                                tBackData.mBoundingBox);
+        
+                const int maxCostMisses = splitCandidate.mMaxCostMisses;
+
+                // how often was max cost ratio missed in this branch?
+                tFrontData.mMaxCostMisses = maxCostMisses;
+                tBackData.mMaxCostMisses = maxCostMisses;
+                        
+                //-- push the new split candidates on the queue
+                OspSplitCandidate *frontCandidate = new OspSplitCandidate();
+                OspSplitCandidate *backCandidate = new OspSplitCandidate();
+
+                EvalSplitCandidate(tFrontData, *frontCandidate);
+                EvalSplitCandidate(tBackData, *backCandidate);
+
+                tQueue.push(frontCandidate);
+                tQueue.push(backCandidate);
+
+                // delete old leaf node
+                DEL_PTR(tData.mNode);
+        }
+
+
+        //-- terminate traversal
+        if (newNode->IsLeaf())
+        {
+                //KdLeaf *leaf = dynamic_cast<KdLeaf *>(newNode);
+                EvaluateLeafStats(tData);               
+        }
+
+        //-- cleanup
+        tData.Clear();
+        
+        return newNode;
+}
+
+
+void OspTree::EvalSplitCandidate(OspTraversalData &tData,
+                                                                 OspSplitCandidate &splitData)
+{
+        float frontProb;
+        float backtProb;
+        
+        KdLeaf *leaf = dynamic_cast<KdLeaf *>(tData.mNode);
+
+        // compute locally best split plane
+        const bool success = false;
+#if TODO
+        SelectPlane(tData, splitData.mSplitPlane,
+                                frontData.mProbability, backData.mProbability);
+
+        //TODO
+        // compute global decrease in render cost
+        splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
+        splitData.mParentData = tData;
+        splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
+#endif
+}
+
+
 /*****************************************************************/
 /*              class HierarchyManager implementation            */
@@ -2376 +2351 @@
 
 
-void HierarchyManager::PrepareTraversal()
-{
-
-#if TODO
-        /// create new vsp tree
-        mRoot = new VspLeaf();
-        /// we use the overall probability as normalizer
-        const float prop = mBoundingBox.GetVolume();
-
-        VspTraversalData tData(mRoot,
-                                                   0,
-                                                   rays,
-                           ComputePvsSize(*rays),
-                                                   prop,
-                                                   mBoundingBox);
-
-
-        // compute first split candidates
-        VspTree::VspSplitCandidate vspSplitCandidate = new VspTree::VspSplitCandidate();
-        EvalSplitCandidate(tData, *vspSplitCandidate);
-        mTQueue.push(splitCandidate);
-
-    OspSplitCandidate ospSplitCandidate = new OspSplitCandidate();
-        EvalSplitCandidate(tData, *ospSplitCandidate);
-        mTQueue.push(ospSplitCandidate);
-
-        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
-        mTotalPvsSize = tData.mPvs;
-        
-        mSubdivisionStats 
-                        << "#ViewCells\n1\n" <<  endl
-                        << "#RenderCostDecrease\n0\n" << endl 
-                        << "#SplitCandidateCost\n0\n" << endl
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-
-#endif
+void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
+                                                                                   AxisAlignedBox3 *forcedViewSpace,
+                                                                                   RayInfoContainer &rays)
+{
+        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+        long startTime = GetTime();
+
+        cout << "storing rays ... ";
+
+        Intersectable::NewMail();
+
+        mVspTree->PrepareConstruction(sampleRays, forcedViewSpace);
+
+        //-- store rays
+        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+        {
+                VssRay *ray = *rit;
+
+                float minT, maxT;
+
+                static Ray hray;
+                hray.Init(*ray);
+
+                // TODO: not very efficient to implictly cast between rays types
+                if (mBoundingBox.GetRaySegment(hray, minT, maxT))
+                {
+                        float len = ray->Length();
+
+                        if (!len)
+                                len = Limits::Small;
+
+                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
+                }
+        }
+
+        cout << "finished" << endl;
+
+        //mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
+}
+
+
+bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
+{
+        if (candidate->Type() == SplitCandidate::VIEW_SPACE)
+        {
+                VspTree::VspSplitCandidate *sc = 
+                        dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
+                
+                return mVspTree->GlobalTerminationCriteriaMet(sc->mParentData);
+        }
+
+        return true;
 }
 
@@ -2420 +2409 @@
 void HierarchyManager::Construct(const VssRayContainer &sampleRays,
                                                                  const ObjectContainer &objects,
-                                                                 AxisAlignedBox3 *forcedBoundingBox)
-{
-#if TODO
-        //-- store rays
-        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
-        {
-                VssRay *ray = *rit;
-
-                float minT, maxT;
-
-                static Ray hray;
-                hray.Init(*ray);
-
-                // TODO: not very efficient to implictly cast between rays types
-                if (mBoundingBox.GetRaySegment(hray, minT, maxT))
-                {
-                        float len = ray->Length();
-
-                        if (!len)
-                                len = Limits::Small;
-
-                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
-                }
-        }
-#endif
-}
-
-
-bool HierarchyManager::FinishedConstruction()
-{
-        return mTQueue.empty();
-}
-
-
-void HierarchyManager::Construct(RayInfoContainer *rays)
-{
-        PrepareTraversal();
+                                                                 AxisAlignedBox3 *forcedViewSpace)
+{
+        RayInfoContainer *rays = new RayInfoContainer();
+        
+        // prepare vsp and osp trees for traversal
+        PrepareConstruction(sampleRays, forcedViewSpace, *rays);
 
         mVspTree->mVspStats.Start();
-        cout << "Constructing vsp bsp tree ... \n";
-
+
+        cout << "Constructing view space / object space tree ... \n";
         const long startTime = GetTime();       
 
@@ -2467 +2425 @@
                 SplitCandidate *splitCandidate = NextSplitCandidate();
             
+                const bool globalTerminationCriteriaMet = 
+                        GlobalTerminationCriteriaMet(splitCandidate);
+
                 // cost ratio of cost decrease / totalCost
                 const float costRatio = splitCandidate->GetPriority() / mTotalCost;
-                
                 //Debug << "cost ratio: " << costRatio << endl;
 
@@ -2475 +2435 @@
                         ++ mGlobalCostMisses;
         
-                // subdivide leaf node
-                // either object space or view space
+                //-- subdivide leaf node
+                //-- either a object space or view space split
                 if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE)
                 {
@@ -2482 +2442 @@
                                 dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
 
-                        VspNode *r = mVspTree->Subdivide(mTQueue, *sc);
-                }
-                else // object space
+                        VspNode *r = mVspTree->Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
+                }
+                else // object space split
                 {
 #if TODO
@@ -2490 +2450 @@
 #endif
                 }
-        }
-
-        cout << "finished\n";
+
+                DEL_PTR(splitCandidate);
+        }
+
+        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
 
         mVspTree->mVspStats.Stop();
 }
 
-}
+
+bool HierarchyManager::FinishedConstruction()
+{
+        return mTQueue.empty();
+}
+
+
+}

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

@@ -28 +28 @@
 class VspLeaf;
 class VspNode;
-
+class KdNode;
+class KdInterior;
+class KdLeaf;
+
+class KdTreeStatistics;
 
 /** A definition for an axis aligned plane.
@@ -36 +40 @@
 public:
 
+        /** Computes intersection of this plane with the ray segment.
+        */
         int ComputeRayIntersection(const RayInfo &rayData, float &t) const
         {
@@ -41 +47 @@
         }
 
+        /// the split axis: one of 0=x, 1=y, 2=z
         int mAxis;
+        /// the absolute position of the split axis
         float mPosition;
 };
+
 
 /** Candidate for a view space / object space split.
@@ -184 +193 @@
 };
 
+
+/** View space partition statistics.
+*/
+class OspTreeStatistics: public StatisticsBase
+{
+public:
+        // total number of nodes
+        int nodes;
+        // number of splits
+        int splits[3];
+        
+        // totals number of rays
+        int rays;
+        // maximal reached depth
+        int maxDepth;
+        // minimal depth
+        int minDepth;
+        
+        // max depth nodes
+        int maxDepthNodes;
+        // minimum depth nodes
+        int minDepthNodes;
+        // max depth nodes
+        int minPvsNodes;
+        // nodes with minimum PVS
+        int minRaysNodes;
+        // max ray contribution nodes
+        int maxRayContribNodes;
+        // minimum area nodes
+        int minProbabilityNodes;
+        /// nodes termination because of max cost ratio;
+        int maxCostNodes;
+        // max number of rays per node
+        int maxObjectRefs;
+        /// samples contributing to pvs
+        int contributingSamples;
+        /// sample contributions to pvs
+        int sampleContributions;
+        /// largest pvs
+        int maxPvs;
+        /// number of invalid leaves
+        int invalidLeaves;
+        /// accumulated number of rays refs
+        int accumRays;
+        int pvs;
+        // accumulated depth (used to compute average)
+        int accumDepth;
+
+        // Constructor
+        OspTreeStatistics() 
+        {
+                Reset();
+        }
+
+        int Nodes() const {return nodes;}
+        int Interior() const { return nodes / 2; }
+        int Leaves() const { return (nodes / 2) + 1; }
+        
+        // TODO: computation wrong
+        double AvgDepth() const { return accumDepth / (double)Leaves();}; 
+        double AvgRays() const { return accumRays / (double)Leaves();}; 
+
+        void Reset() 
+        {
+                nodes = 0;
+                for (int i = 0; i < 3; ++ i)
+                        splits[i] = 0;
+                
+                maxDepth = 0;
+                minDepth = 99999;
+                accumDepth = 0;
+        pvs = 0;
+                maxDepthNodes = 0;
+                minPvsNodes = 0;
+                minRaysNodes = 0;
+                maxRayContribNodes = 0;
+                minProbabilityNodes = 0;
+                maxCostNodes = 0;
+
+                contributingSamples = 0;
+                sampleContributions = 0;
+
+                maxPvs = 0;
+                invalidLeaves = 0;
+                accumRays = 0;
+        }
+
+        void Print(ostream &app) const;
+
+        friend ostream &operator<<(ostream &s, const OspTreeStatistics &stat) 
+        {
+                stat.Print(s);
+                return s;
+        } 
+};
+
+
 /**
     VspNode abstract class serving for interior and leaf node implementation
 */
-class VspNode 
+class VspNode
 {
 public:
@@ -530 +636 @@
         AxisAlignedBox3 GetBBox(VspNode *node) const;
 
-        /** Constructs the tree from a given set of rays.
-                @param sampleRays the set of sample rays the construction is based on
-                @param forcedBoundingBox a given bounding box is taken as view space
-        */
-        void Construct(const VssRayContainer &sampleRays,
-                                   AxisAlignedBox3 *forcedBoundingBox);
-
         /** Returns list of BSP leaves with pvs smaller than
                 a certain threshold.
@@ -701 +800 @@
                                                 float &pBack) const;
 
+        void PrepareConstruction(const VssRayContainer &sampleRays,
+                                                         AxisAlignedBox3 *forcedBoundingBox);
+
         /** Evaluates candidate for splitting.
         */
@@ -713 +815 @@
         float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
                                                                  const VspTraversalData &data) const;
-
-        /** Constructs tree using the split priority queue.
-        */
-        void Construct(RayInfoContainer *rays);
 
         /** Collects view cells in the subtree under root.
@@ -747 +845 @@
         void EvaluateLeafStats(const VspTraversalData &data);
 
-        /** Subdivides node with respect to the traversal data.
-            @param tStack current traversal stack
-                @param tData traversal data also holding node to be subdivided
+        /** Subdivides node using a best split priority queue.
+            @param tQueue the best split priority queue
+                @param splitCandidate the candidate for the next split
+                @param globalCriteriaMet if the global termination criteria were already met
                 @returns new root of the subtree
         */
         VspNode *Subdivide(SplitQueue &tQueue,
-                                           VspSplitCandidate &splitCandidate);
-
+                                           VspSplitCandidate &splitCandidate,
+                                           const bool globalCriteriaMet);
+
+        /** Adds stats to subdivision log file.
+        */
+        void AddSubdivisionStats(const int viewCells,
+                                                         const float renderCostDecr,
+                                                         const float splitCandidateCost,
+                                                         const float totalRenderCost,
+                                                         const float avgRenderCost);
         
         /** Subdivides 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 tData data object holding, e.g., a pointer to the leaf
+                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
+                @param backData returns the data (e.g.,  pointer to the leaf) 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
         */
-
         VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
                                                            VspTraversalData &tData,
@@ -884 +988 @@
 
         /// box around the whole view domain
-        AxisAlignedBox3 mBox;
+        AxisAlignedBox3 mBoundingBox;
 
 
@@ -973 +1077 @@
 
 
-class KdTree;
+/** View Space Partitioning tree.
+*/
+class OspTree 
+{
+        friend class ViewCellsParseHandlers;
+        friend class HierarchyManager;
+
+public:
+        
+        /** Additional data which is passed down the BSP tree during traversal.
+        */
+        class OspTraversalData
+        {  
+        public:
+                /// the current node
+                KdNode *mNode;
+                /// current depth
+                int mDepth;
+                /// rays piercing this node
+                RayInfoContainer *mRays;
+                /// the probability that this node contains view point
+                float mProbability;
+                /// the bounding box of the node
+                AxisAlignedBox3 mBoundingBox;
+                /// pvs size
+                int mPvs;
+                /// how often this branch has missed the max-cost ratio
+                int mMaxCostMisses;
+                // current axis
+                int mAxis;
+                // current priority
+                float mPriority;
+
+                
+                /** Returns average ray contribution.
+                */
+                float GetAvgRayContribution() const
+                {
+                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
+                }
+
+
+                OspTraversalData():
+                mNode(NULL),
+                mDepth(0),
+                mRays(NULL),
+                mPvs(0),
+                mProbability(0.0),
+                mMaxCostMisses(0), 
+                mPriority(0),
+                mAxis(0)
+                {}
+                
+                OspTraversalData(KdNode *node, 
+                                                 const int depth, 
+                                                 RayInfoContainer *rays,
+                                                 const int pvs,
+                                                 const float p,
+                                                 const AxisAlignedBox3 &box):
+                mNode(node), 
+                mDepth(depth), 
+                mRays(rays),
+                mPvs(pvs),
+                mProbability(p),
+                mBoundingBox(box),
+                mMaxCostMisses(0),
+                mPriority(0),
+                mAxis(0)
+                {}
+
+                OspTraversalData(const int depth, 
+                                                 RayInfoContainer *rays,
+                                                 const AxisAlignedBox3 &box): 
+                mNode(NULL), 
+                mDepth(depth), 
+                mRays(rays),
+                mPvs(0),
+                mProbability(0),
+                mMaxCostMisses(0),
+                mAxis(0),
+                mBoundingBox(box)
+                {}
+
+                /** Returns cost of the traversal data.
+                */
+                float GetCost() const
+                {
+                        //cout << mPriority << endl;
+                        return mPriority;
+                }
+
+                // deletes contents and sets them to NULL
+                void Clear()
+                {
+                        DEL_PTR(mRays);
+                }
+
+                friend bool operator<(const OspTraversalData &a, const OspTraversalData &b)
+                {
+                        return a.GetCost() < b.GetCost();
+                }
+    };
+
+        /** Candidate for a view space split.
+        */
+        class OspSplitCandidate: public SplitCandidate
+        {  
+        public:
+                /// parent data
+                OspTraversalData mParentData;
+                
+                OspSplitCandidate()
+                {};
+
+                int Type() const { return VIEW_SPACE; }
+
+                OspSplitCandidate(const AxisAlignedPlane &plane, const OspTraversalData &tData): 
+                SplitCandidate(plane), mParentData(tData)
+                {}
+        };
+
+        /** Struct for traversing line segment.
+        */
+        struct LineTraversalData 
+        {
+                KdNode *mNode;
+                Vector3 mExitPoint;
+                
+                float mMaxT;
+    
+                LineTraversalData () {}
+                LineTraversalData (KdNode *n, const Vector3 &p, const float maxt):
+                mNode(n), mExitPoint(p), mMaxT(maxt) {}
+        };
+
+        //typedef std::priority_queue<VspTraversalData> VspOspTraversalQueue;
+
+        /** Default constructor creating an empty tree.
+        */ 
+        OspTree();
+
+        /** Default destructor.
+        */
+        ~OspTree();
+
+        /** Returns BSP Tree statistics.
+        */
+        const KdTreeStatistics &GetStatistics() const; 
+  
+        /** Returns bounding box of the specified node.
+        */
+        AxisAlignedBox3 GetBoundingBox(KdNode *node) const;
+
+        /** Returns list of BSP leaves with pvs smaller than
+                a certain threshold.
+                @param onlyUnmailed if only the unmailed leaves should be considered
+                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
+        */
+        void CollectLeaves(vector<VspLeaf *> &leaves, 
+                                           const bool onlyUnmailed = false,
+                                           const int maxPvs = -1) const;
+
+        /** Returns box which bounds the whole tree.
+        */
+        AxisAlignedBox3 GetBoundingBox()const;
+
+        /** Returns root of the view space partitioning tree.
+        */
+        KdNode *GetRoot() const;
+
+        /** Collects the leaf view cells of the tree
+                @param viewCells returns the view cells 
+        */
+        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
+
+        /** A ray is cast possible intersecting the tree.
+                @param the ray that is cast.
+                @returns the number of intersections with objects stored in the tree.
+        */
+        int CastRay(Ray &ray);
+
+        /** finds neighbouring leaves of this tree node.
+        */
+        int FindNeighbors(KdLeaf *n, 
+                                          vector<VspLeaf *> &neighbors, 
+                                          const bool onlyUnmailed) const;
+
+        /** Returns random leaf of BSP tree.
+                @param halfspace defines the halfspace from which the leaf is taken.
+        */
+        KdLeaf *GetRandomLeaf(const Plane3 &halfspace);
+
+        /** Returns random leaf of BSP tree.
+                @param onlyUnmailed if only unmailed leaves should be returned.
+        */
+        KdLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
+
+        /** Returns epsilon of this tree.
+        */
+        float GetEpsilon() const;
+
+        /** Casts line segment into the tree.
+                @param origin the origin of the line segment
+                @param termination the end point of the line segment
+                @returns view cells intersecting the line segment.
+        */
+    int CastLineSegment(const Vector3 &origin,
+                                                const Vector3 &termination,
+                                                ViewCellContainer &viewcells);
+                
+        /** Sets pointer to view cells manager.
+        */
+        void SetViewCellsManager(ViewCellsManager *vcm);
+
+        /** Writes tree to output stream
+        */
+#if ZIPPED_VIEWCELLS
+        bool Export(ogzstream &stream);
+#else
+        bool Export(ofstream &stream);
+#endif
+
+        /** Collects rays stored in the leaves.
+        */
+        void CollectRays(VssRayContainer &rays);
+
+        /** Intersects box with the tree and returns the number of intersected boxes.
+                @returns number of view cells found
+        */
+        int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
+                                                                ViewCellContainer &viewCells) const;
+
+
+        /// pointer to the hierarchy of view cells
+        ViewCellsTree *mViewCellsTree;
+
+
+protected:
+
+        // --------------------------------------------------------------
+        // For sorting objects
+        // --------------------------------------------------------------
+        struct SortableEntry
+        {
+                enum EType 
+                {
+                        ERayMin,
+                        ERayMax
+                };
+
+                int type;
+                float value;
+                VssRay *ray;
+  
+                SortableEntry() {}
+                SortableEntry(const int t, const float v, VssRay *r):type(t),
+                                          value(v), ray(r) 
+                {
+                }
+                
+                friend bool operator<(const SortableEntry &a, const SortableEntry &b) 
+                {
+                        return a.value < b.value;
+                }
+        };
+
+        /** faster evaluation of split plane cost for kd axis aligned cells.
+        */
+        float EvalSplitCost(const OspTraversalData &data,
+                                                const AxisAlignedBox3 &box,
+                                                const int axis,
+                                                const float &position,
+                                                float &pFront,
+                                                float &pBack) const;
+
+        /** Evaluates candidate for splitting.
+        */
+        void EvalSplitCandidate(OspTraversalData &tData, OspSplitCandidate &splitData);
+
+        /** Computes priority of the traversal data and stores it in tData.
+        */
+        void EvalPriority(OspTraversalData &tData) const;
+
+        /** Evaluates render cost decrease of next split.
+        */
+        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
+                                                                 const OspTraversalData &data) const;
+
+        /** Collects view cells in the subtree under root.
+        */
+        void CollectViewCells(KdNode *root, 
+                                                  bool onlyValid, 
+                                                  ViewCellContainer &viewCells,
+                                                  bool onlyUnmailed = false) const;
+
+        /** Evaluates tree stats in the BSP tree leafs.
+        */
+        void EvaluateLeafStats(const OspTraversalData &data);
+
+        /** Subdivides node using a best split priority queue.
+            @param tQueue the best split priority queue
+                @param splitCandidate the candidate for the next split
+                @param globalCriteriaMet if the global termination criteria were already met
+                @returns new root of the subtree
+        */
+        KdNode *Subdivide(SplitQueue &tQueue,
+                                          OspSplitCandidate &splitCandidate,
+                                          const bool globalCriteriaMet);
+        
+        /** Subdivides 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
+        */
+        void SplitObjects(const AxisAlignedPlane & splitPlane,
+                                          const ObjectContainer &objects,
+                                          ObjectContainer &back,
+                                          ObjectContainer &front);
+
+        KdInterior *SubdivideNode(KdLeaf *leaf,
+                                                          const AxisAlignedPlane &splitPlane,
+                                                          const AxisAlignedBox3 &box,
+                                                          AxisAlignedBox3 &backBBox,
+                                                          AxisAlignedBox3 &frontBBox);
+
+        /*KdInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
+                                                          OspTraversalData &tData,
+                                                          OspTraversalData &frontData,
+                                                          OspTraversalData &backData);*/
+
+        /** Selects an axis aligned for the next split.
+                @returns cost for this split
+        */
+        float SelectPlane(const OspTraversalData &tData,
+                                          AxisAlignedPlane &plane,
+                                          float &pFront,
+                                          float &pBack);
+
+        /** Sorts split candidates for surface area heuristics for 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 SortSplitCandidates(const RayInfoContainer &rays, 
+                                                         const int axis, 
+                                                         float minBand, 
+                                                         float maxBand);
+
+        /** Computes best cost for axis aligned planes.
+        */
+        float BestCostRatioHeuristics(const RayInfoContainer &rays,
+                                                                  const AxisAlignedBox3 &box,
+                                                                  const int pvsSize,
+                                                                  const int axis,
+                                                                  float &position);
+
+        /** 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 AxisAlignedPlane &plane,
+                                  RayInfoContainer &rays, 
+                              RayInfoContainer &frontRays, 
+                                  RayInfoContainer &backRays) 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, 
+                                         float &frontPvs, 
+                                         float &backPvs, 
+                                         float &totalPvs) const;
+        
+        /** Computes PVS size induced by the rays.
+        */
+        int ComputePvsSize(const RayInfoContainer &rays) const;
+
+        /** Returns true if tree can be terminated.
+        */
+        inline bool LocalTerminationCriteriaMet(const OspTraversalData &data) const;
+
+        /** Returns true if global tree can be terminated.
+        */
+        inline bool GlobalTerminationCriteriaMet(const OspTraversalData &data) 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(VspLeaf *leaf,
+                                  const RayInfoContainer &rays, 
+                                  float &sampleContributions,
+                                  int &contributingSamples);
+
+        /** Propagates valid flag up the tree.
+        */
+        void PropagateUpValidity(KdNode *node);
+
+        /** Writes the node to disk
+                @note: should be implemented as visitor.
+        */
+#if ZIPPED_VIEWCELLS
+        void ExportNode(KdNode *node, ogzstream &stream);
+#else
+        void ExportNode(KdNode *node, ofstream &stream);
+#endif
+
+        /** Returns estimated memory usage of tree.
+        */
+        float GetMemUsage() const;
+
+
+protected:
+
+        ViewCellsManager *mViewCellsManager;
+        vector<SortableEntry> *mSplitCandidates;
+
+        /// Pointer to the root of the tree
+        KdNode *mRoot;
+                
+        OspTreeStatistics mOspStats;
+        
+        /// box around the whole view domain
+        AxisAlignedBox3 mBoundingBox;
+
+
+        //-- local termination
+
+        /// minimal number of rays before subdivision termination
+        int mTermMinRays;
+        /// maximal possible depth
+        int mTermMaxDepth;
+        /// mininum probability
+        float mTermMinProbability;
+        /// mininum PVS
+        int mTermMinPvs;
+        /// maximal contribution per ray
+        float mTermMaxRayContribution;
+        /// maximal acceptable cost ratio
+        float mTermMaxCostRatio;
+        /// tolerance value indicating how often the max cost ratio can be failed
+        int mTermMissTolerance;
+
+
+        //-- global criteria
+        float mTermMinGlobalCostRatio;
+        int mTermGlobalCostMissTolerance;
+        int mGlobalCostMisses;
+
+        /// maximal number of view cells
+        int mMaxViewCells;
+        /// maximal tree memory
+        float mMaxMemory;
+        /// the tree is out of memory
+        bool mOutOfMemory;
+
+
+
+        //-- split heuristics based parameters
+        
+        bool mUseCostHeuristics;
+        /// balancing factor for PVS criterium
+        float mCtDivCi; 
+        /// if only driving axis should be used for split
+        bool mOnlyDrivingAxis;
+        /// if random split axis should be used
+        bool mUseRandomAxis;
+        /// if vsp bsp tree should simulate octree
+        bool mCirculatingAxis;
+        /// minimal relative position where the split axis can be placed
+        float mMinBand;
+        /// maximal relative position where the split axis can be placed
+        float mMaxBand;
+
+
+        /// current time stamp (used for keeping split history)
+        int mTimeStamp;
+        // if rays should be stored in leaves
+        bool mStoreRays;
+
+        /// epsilon for geometric comparisons
+        float mEpsilon;
+
+        /// if we should use breath first priority for the splits
+        int mNodePriorityQueueType;
+
+
+        /// subdivision stats output file
+        ofstream  mSubdivisionStats;
+        /// keeps track of cost during subdivision
+        float mTotalCost;
+        /// keeps track of overall pvs size during subdivision
+        int mTotalPvsSize;
+        /// number of currenly generated view cells
+        int mCreatedViewCells;
+
+private:
+
+        /// Generates unique ids for PVS criterium
+        static void GenerateUniqueIdsForPvs();
+
+        //-- unique ids for PVS criterium
+        static int sFrontId; 
+        static int sBackId;
+        static int sFrontAndBackId;
+};
+
 
 /** This class implements a structure holding two different hierarchies,
@@ -1011 +1642 @@
         void Construct(const VssRayContainer &sampleRays,
                                    const ObjectContainer &objects,
-                                   AxisAlignedBox3 *forcedBoundingBox);
+                                   AxisAlignedBox3 *forcedViewSpace);
 
 public:
         VspTree *mVspTree;
-        KdTree *mKdTree;
+        OspTree *mOspTree;
 
 protected:
 
-        void Construct(RayInfoContainer *rays);
-        void PrepareTraversal();
+        bool GlobalTerminationCriteriaMet(SplitCandidate *candidate) const;
+
+        void PrepareConstruction(const VssRayContainer &sampleRays,
+                                                         AxisAlignedBox3 *forcedViewSpace,
+                                                         RayInfoContainer &rays);
+
         bool FinishedConstruction();
         SplitCandidate *NextSplitCandidate();

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

@@ -211 +211 @@
         tStack.push(pair<BspNode *, BspNodeGeometry *>(tree.GetRoot(), geom));
 
-        if (maxPvs > 0)
+        if (maxPvs)
                 mUseForcedMaterial = true;
 
@@ -238 +238 @@
                 else
                 {
-                        if (maxPvs > 0)
+                        if (maxPvs)
                         {
                                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
 
                                 mForcedMaterial.mDiffuseColor.b = 1.0f;
-                                float importance = (float)leaf->GetViewCell()->GetPvs().GetSize() / (float)maxPvs;
+                                const float importance = (float)leaf->GetViewCell()->GetPvs().GetSize() / (float)maxPvs;
 
                                 mForcedMaterial.mDiffuseColor.r = importance;

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

@@ -30 +30 @@
 #include "ViewCellsManager.h"
 #include "ResourceManager.h"
+#include <assert.h>
 
 namespace GtpVisibilityPreprocessor {
@@ -80 +81 @@
 //  StdInParseHandlers: Constructors and Destructor
 // ---------------------------------------------------------------------------
-X3dParseHandlers::X3dParseHandlers(SceneGraphNode *root, const bool loadPolygonsAsMeshes):
+X3dParseHandlers::X3dParseHandlers(SceneGraphNode *root, 
+                                                                   const bool loadPolygonsAsMeshes):
   mElementCount(0)
   , mAttrCount(0)
@@ -96 +98 @@
 X3dParseHandlers::~X3dParseHandlers()
 {
-        if (!mTransformations.empty())
+        assert(mTransformations.empty());
+        if (0 && !mTransformations.empty())
                 cout << "error: transformation stack size: " << (int)mTransformations.size() << endl;
 }
@@ -166 +169 @@
                         float angle;
                                 
-                        if (sscanf(ptr, "%f %f %f", &axis.x, &axis.y, &axis.z, &angle) == 4)
+                        if (sscanf(ptr, "%f %f %f %f", &axis.x, &axis.y, &axis.z, &angle) == 4)
                         {
                                 rotm = new Matrix4x4(RotationAxisMatrix(axis, angle));
@@ -224 +227 @@
          if (mLoadPolygonsAsMeshes)
          {
+                 cout << "m";   
                  FaceContainer::const_iterator fit, fit_end = mCurrentMesh->mFaces.end();
-
-                 cout << "m";
                 
                  for (fit = mCurrentMesh->mFaces.begin(); fit != fit_end; ++ fit)
                  {
                          cout << "f";
-
                          Face *face = *fit;
                 
@@ -240 +241 @@
                 
                          int i = 0;
+                         // dummy vertex indices container
                          VertexIndexContainer vcIndices;
 
@@ -250 +252 @@
                                  mesh->mVertices.push_back(mCurrentMesh->mVertices[index]);
 
-                                 // indices don't make much sense if mesh = face, but
-                                 // we need them anyway ...
+                                 // indices don't make much sense if mesh == face, 
+                                 // but we need them anyway ...
                                  vcIndices.push_back(i);
                          }
@@ -257 +259 @@
                          mesh->mFaces.push_back(new Face(vcIndices));
 
-                         // NOTE: should rather be written into trafo of mesh instance
+                         // write transformations directly in mesh 
+                         // note: could be transformed in parent mesh, save some transformations
                          ApplyTransformations(mTransformations, mesh);
 
                          mesh->Preprocess();
                                 
-                         // make an instance of this mesh
-                         MeshInstance *mi = new MeshInstance(mesh);
-                         mCurrentNode->mGeometry.push_back(mi);
+                         if (mesh->mFaces.empty())
+                         {
+                                 cout << "error: empy mesh" << endl;
+                         }
+                         else
+                         {
+                                 // make an instance of this mesh
+                                 MeshInstance *mi = new MeshInstance(mesh);
+                                 mCurrentNode->mGeometry.push_back(mi);
+
+                                 if (mCurrentMaterial)
+                                 {
+                                         // HACK: add the material to the mesh directly if no material yet
+                                         if (!mCurrentMesh->mMaterial)
+                                                 mCurrentMesh->mMaterial = mCurrentMaterial;
+                                 }
+                         }
                  }
 
                  // this mesh is not needed, unless it is used as a definition
-                 if (!mUsingMeshDefinition) 
+                 if (!mUsingMeshDefinition)
+                 {
                          MeshManager::GetSingleton()->DestroyEntry(mCurrentMesh->GetId());
+                 }
         }
         else // default usage: create a mesh instance from the current mesh
@@ -275 +294 @@
                 MeshInstance *mi;
 
-                if (mCurrentMesh->mFaces.empty())
-                        cout << "warning: empy mesh" << endl;
-
                 if (!mUsingMeshDefinition) 
                 {
                         // make an instance of this mesh
-            mi = new MeshInstance(mCurrentMesh);
+                        mi = new MeshInstance(mCurrentMesh);
 
                         // this mesh is used only once => write transformations directly into it
@@ -289 +305 @@
                 {
                          // make an instance of this mesh
-                         TransformedMeshInstance *tmi = new TransformedMeshInstance(mCurrentMesh);
+                        TransformedMeshInstance *tmi = new TransformedMeshInstance(mCurrentMesh);
 
                          // apply transformation on the instance of the mesh 
                          ApplyTransformations(mTransformations, tmi);
-
                          mi = tmi;
                 }
-                
+                        
                 if (mCurrentMaterial)
                 {
                         // HACK: add the material to the mesh directly if no material yet
-                        if (mCurrentMesh->mMaterial)
+                        if (!mCurrentMesh->mMaterial)
                         {
                                 mCurrentMesh->mMaterial = mCurrentMaterial;
@@ -309 +324 @@
                         }
                 }
-
+                
                 // create local mesh kd tree
                 mCurrentMesh->Preprocess();
-                // add to scene graph
-                mCurrentNode->mGeometry.push_back(mi);
-        
+
+                if (mCurrentMesh->mFaces.empty())
+                {
+                        cout << "warning: empy mesh!!" << endl;
+                        delete mi;
+                }
+                else
+                {
+                        // add to scene graph
+                        mCurrentNode->mGeometry.push_back(mi);
+                }
+
                 // reset current mesh
                 mCurrentMesh = NULL;

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

@@ -121 +121 @@
                 AttributeList&  attributes);
   
-  /// applies transformation m to this mesh
+  /** applies transformation matrix m to this mesh.
+  */
   void ApplyTransformation(Mesh *mesh, const Matrix4x4 &m) const;
 
-  /// transforms mesh using the given transformations
+  /** transforms mesh using the given transformations.
+  */
   void ApplyTransformations(TrafoStack trafos, Mesh *mesh) const;
   void ApplyTransformations(TrafoStack trafos, TransformedMeshInstance *mi) const;