Changeset 542

Timestamp:

01/16/06 03:23:29 (18 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (15 diffs)
• src/AxisAlignedBox3.cpp (modified) (1 diff)
• src/AxisAlignedBox3.h (modified) (2 diffs)
• src/Beam.cpp (modified) (1 diff)
• src/Beam.h (modified) (2 diffs)
• src/Environment.cpp (modified) (1 diff)
• src/GlRenderer.cpp (modified) (2 diffs)
• src/ViewCellsManager.cpp (modified) (19 diffs)
• src/ViewCellsManager.h (modified) (1 diff)
• src/VspBspTree.cpp (modified) (31 diffs)
• src/VspBspTree.h (modified) (7 diffs)
• src/VspKdTree.cpp (modified) (2 diffs)
• src/common.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -13 +13 @@
 #;../data/vienna/vienna-plane.x3d
 #       filename ../data/vienna/viewcells-25-sel.x3d
-#       filename ../data/atlanta/atlanta2.x3d
+        filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
-        filename ../data/soda/soda5.dat
+#       filename ../data/soda/soda5.dat
 }
 
@@ -21 +21 @@
         # stored sample rays
         samplesFilename rays.out
-        useGlRenderer true
+        useGlRenderer false
 #       type sampling
         type vss
@@ -29 +29 @@
 VssPreprocessor {
         samplesPerPass  100000
-        initialSamples 200000
-        vssSamples 200000
+        initialSamples 300000
+        vssSamples 1000000
         vssSamplesPerPass 100000
         useImportanceSampling true
@@ -52 +52 @@
         maxDepth        40
         minPvs          30
-        minRays         500
+        minRays         800
         minSize         0.001
         maxCostRatio    1.5
         maxRayContribution 0.5
                 
-        maxTotalMemory  200
-        maxStaticMemory 100
+        maxTotalMemory  50
+        maxStaticMemory 20
         
         splitType regular
@@ -66 +66 @@
         
         interleaveDirSplits     true
-    dirSplitDepth 10
+    dirSplitDepth 0
         
         numberOfEndPointDomains 10000
@@ -174 +174 @@
         #type kdTree
         #type vspKdTree
-        #type bspTree
+        type bspTree
         type vspBspTree
         
@@ -182 +182 @@
         maxViewCells 100000
         #percentage of total visible objects where pvs is considered invalid
-        maxPvsRatio 0.5
-                
-        delayedConstruction false
+        maxPvsRatio 0.3
+                
+        delayedConstruction true
                 
                 
         PostProcess {
                 # how much samples are used for post processing
-                samples 20000
+                samples 200000
         }
 
@@ -224 +224 @@
 
         Construction {
-                samples 300000
+                samples 500000
         }
         
@@ -230 +230 @@
                 maxDepth                40
                 minPvs                  50
-                minRays                 700
+                minRays                 800
                 minSize                 0.001
                 maxCostRatio            0.9
                 missTolerance           4
-                maxRayContribution      0.05
+                maxRayContribution      0.5
         }
         
         maxTotalMemory  100
-        maxStaticMemory 50
+        maxStaticMemory 40
 
         splitType       regular
         #splitType      heuristics
-        splitUseOnlyDrivingAxis true
+        splitUseOnlyDrivingAxis false
         ct_div_ci       0.0
         
@@ -248 +248 @@
         PostProcess {
                 maxCostRatio 0.005
-                minViewCells 200
+                minViewCells 1000
                 maxPvsSize   50000
         }
@@ -259 +259 @@
 VspBspTree {
         Construction {
-                samples 100000
+                samples 300000
                 epsilon 0.005
                 randomize false
@@ -280 +280 @@
         maxTests 10000
         
+        maxTotalMemory  50
+        maxStaticMemory 50
+        
         # factors for evaluating split plane costs
         Factor {
@@ -289 +292 @@
         Termination {
                 # parameters used for autopartition
-                minRays                 1000
+                minRays                 500
                 minPolygons             -1
                 maxDepth                30
                 minPvs                  10
-                minArea                 0.00008
-                #minArea                0.000
-                maxRayContribution      0.3
-                maxCostRatio            0.93
+                #minArea                0.0001
+                minArea                 -1
+                maxRayContribution      0.9
+                maxCostRatio            99999.93
                 missTolerance           3
                 #maxAccRayLength        100
                 
-                maxViewCells            200
+                maxViewCells            2001
                 
                 # used for pvs criterium
@@ -306 +309 @@
                 
                 AxisAligned {
-                        minRays                 5000
+                        minRays                 4000
                         maxRayContribution      0.5
                 }
@@ -315 +318 @@
         Visualization {
                 # x3d visualization of the split planes
-                exportSplits false
+                exportSplits true
         }
         
         PostProcess {
-                maxCostRatio 0.1
+                maxCostRatio 0.001
                 minViewCells 1000
-                maxPvsSize   10000
                 useRaysForMerge true
         }

trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp

@@ -2030 +2030 @@
         mesh->AddFace(new Face(index + 0, index + 4, index + 5, index + 1) );
         mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) );
-
-}
+}
+
+
+void AxisAlignedBox3::ExtractPolys(PolygonContainer &polys) const
+{
+        Polygon3 *face1 = new Polygon3();
+        polys.push_back(face1);   
+
+    face1->mVertices.push_back(Vector3(mMin.x,mMin.y,mMax.z));
+        face1->mVertices.push_back(Vector3(mMin.x,mMax.y,mMax.z));
+        face1->mVertices.push_back(Vector3(mMin.x,mMax.y,mMin.z));
+        face1->mVertices.push_back(Vector3(mMin.x,mMin.y,mMin.z));
+
+        Polygon3 *face2 = new Polygon3();  
+        polys.push_back(face2);
+
+    face2->mVertices.push_back(Vector3(mMax.x,mMin.y,mMin.z));
+    face2->mVertices.push_back(Vector3(mMax.x,mMax.y,mMin.z));
+    face2->mVertices.push_back(Vector3(mMax.x,mMax.y,mMax.z));
+    face2->mVertices.push_back(Vector3(mMax.x,mMin.y,mMax.z));
+  
+        Polygon3 *face3 = new Polygon3();  
+        polys.push_back(face3);
+
+    face3->mVertices.push_back(Vector3(mMax.x,mMin.y,mMin.z));
+        face3->mVertices.push_back(Vector3(mMax.x,mMin.y,mMax.z));
+        face3->mVertices.push_back(Vector3(mMin.x,mMin.y,mMax.z));
+        face3->mVertices.push_back(Vector3(mMin.x,mMin.y,mMin.z));
+
+        Polygon3 *face4 = new Polygon3();  
+        polys.push_back(face4);
+
+        face4->mVertices.push_back(Vector3(mMin.x,mMax.y,mMin.z));
+        face4->mVertices.push_back(Vector3(mMin.x,mMax.y,mMax.z));
+        face4->mVertices.push_back(Vector3(mMax.x,mMax.y,mMax.z));
+        face4->mVertices.push_back(Vector3(mMax.x,mMax.y,mMin.z));
+    
+        Polygon3 *face5 = new Polygon3();  
+        polys.push_back(face5);
+
+        face5->mVertices.push_back(Vector3(mMin.x,mMax.y,mMin.z));
+    face5->mVertices.push_back(Vector3(mMax.x,mMax.y,mMin.z));
+    face5->mVertices.push_back(Vector3(mMax.x,mMin.y,mMin.z));
+        face5->mVertices.push_back(Vector3(mMin.x,mMin.y,mMin.z));
+
+        Polygon3 *face6 = new Polygon3();  
+        polys.push_back(face6);  
+  
+    face6->mVertices.push_back(Vector3(mMin.x,mMin.y,mMax.z));
+    face6->mVertices.push_back(Vector3(mMax.x,mMin.y,mMax.z));
+    face6->mVertices.push_back(Vector3(mMax.x,mMax.y,mMax.z));
+    face6->mVertices.push_back(Vector3(mMin.x,mMax.y,mMax.z));
+}

trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h

@@ -6 +6 @@
 #include "Vector3.h"
 #include "Plane3.h"
+#include "Containers.h"
 
 class Ray;
 class Polygon3;
 class Mesh;
+
 // --------------------------------------------------------
 // CAABox class.
@@ -356 +358 @@
   void AddBoxToMesh(Mesh *mesh) const;
 
+  void ExtractPolys(PolygonContainer &polys) const;
+
 #define __EXTENT_HACK
   // get the extent of face

trunk/VUT/GtpVisibilityPreprocessor/src/Beam.cpp

@@ -71 +71 @@
   }
   return result;
+}
+
+
+Beam::~Beam()
+{
+        DEL_PTR(mMesh);
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Beam.h

@@ -89 +89 @@
                                                                  const AxisAlignedBox3 &sceneBBox) const;
 
-  /* Computes parameters for glOrtho.
+  /** Computes parameters for glOrtho.
   */
   void ComputeOrthoFrustum(float &left, float &right,
@@ -107 +107 @@
   }
 
+  ~Beam();
+
+  /** Creates beam mesh bounded at zfar.
+  */
   void CreateMesh(const float zfar);
 };

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1820 +1820 @@
                 "1000");
 
-        RegisterOption("VspBspTree.PostProcess.maxPvsSize", 
-                optInt, 
-                "vsp_bsp_term_post_process_max_pvs_size=", 
-                "100");
-
         RegisterOption("VspBspTree.PostProcess.useRaysForMerge", 
                 optBool, 

trunk/VUT/GtpVisibilityPreprocessor/src/GlRenderer.cpp

@@ -977 +977 @@
 }
 
+
 void GlRendererBuffer::ComputeRays(Intersectable *sourceObj, VssRayContainer &rays)
 {
@@ -1017 +1018 @@
                         ObjectContainer::iterator oit =
                                 lower_bound(objects.begin(), objects.end(), &dummy, ilt);
-                        obj = *oit;
-                        if (!obj->Mailed())
+                        
+                        
+                        if (//(oit != oit.end()) && 
+                                ((*oit)->GetId() == id) && 
+                                !obj->Mailed())
                         {
+                                obj = *oit;
                                 obj->Mail();
                                 ++ pvsSize;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -27 +27 @@
 mViewCellsFinished(false)
 {
-        mSceneBox.Initialize();
+        mViewSpaceBox.Initialize();
         ParseEnvironment();
 }
@@ -39 +39 @@
 mViewCellsFinished(false)
 {
-        mSceneBox.Initialize();
+        mViewSpaceBox.Initialize();
         ParseEnvironment();
 }
@@ -77 +77 @@
 int ViewCellsManager::Construct(VssRayContainer &rays)
 {
-        VssPreprocessor preprocessor;
-
-
-
-        return 0;
+/*      VssPreprocessor preprocessor;
+
+        VssRayContainer vssRays;
+        preprocessor->GenerateVssRays(mConstructionSamples, vssRays);
+        Construct(preprocessor->mObjects, vssRays);
+        
+        // add rays to output rays
+        while (!vssRays.empty)
+        {
+                rays.push_back(vssRays.back());
+                vssRays.pop_back();
+        }
+
+        const int importanceRays = 1000000;
+        preprocessor->GenerateVssRays(max(importanceRays, mPostProcessSamples);
+
+        PostProcess(preprocesor->mObjects, importanceRays);
+        Visualize(preprocessor->mObjects, importanceRays);
+
+        // add rays to output rays
+        while (!importanceRays.empty)
+        {
+                rays.push_back(importanceRays.back());
+                importanceRays.pop_back();
+        }
+*/
+        return (int)rays.size();
 }
 
@@ -99 +121 @@
 bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
 {
-        viewPoint = mSceneBox.GetRandomPoint();
+        viewPoint = mViewSpaceBox.GetRandomPoint();
 
         return true;
@@ -107 +129 @@
 bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
 {
-        return mSceneBox.IsInside(viewPoint);
+        return mViewSpaceBox.IsInside(viewPoint);
 }
 
@@ -333 +355 @@
 void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
 {
-        mSceneBox = box;
+        mViewSpaceBox = box;
 }
 
@@ -339 +361 @@
 AxisAlignedBox3 ViewCellsManager::GetViewSpaceBox() const
 {
-        return mSceneBox;
+        return mViewSpaceBox;
 }
 
@@ -358 +380 @@
 void ViewCellsManager::ComputeSampleContributions(VssRay &ray)
 {
-  ViewCellContainer viewcells;
-
-  ray.mPvsContribution = 0;
-  ray.mRelativePvsContribution = 0.0f;
-
-  // matt TODO: remove this!!
-  Ray hray(ray);
-  float tmin = 0, tmax = 1.0;
-
-  //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
-  if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
+        ViewCellContainer viewcells;
+
+        ray.mPvsContribution = 0;
+        ray.mRelativePvsContribution = 0.0f;
+
+        // matt TODO: remove this!!
+        Ray hray(ray);
+        float tmin = 0, tmax = 1.0;
+
+        //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
+        if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
         return;
 
-  Vector3 origin = hray.Extrap(tmin);
-  Vector3 termination = hray.Extrap(tmax);
-
-  CastLineSegment(origin,
-                                  termination,
-                                  viewcells);
-  //Debug << "constribution: " << (int)viewcells.size() << endl;
-  // copy viewcells memory efficiently
-  const bool storeViewcells = false;
-  if (storeViewcells) {
-        ray.mViewCells.reserve(viewcells.size());
-        ray.mViewCells = viewcells;
-  }
-
-  ViewCellContainer::const_iterator it = viewcells.begin();
-
-  bool addInPlace = false;
-
-  if (addInPlace) {
-        for (; it != viewcells.end(); ++it) {
-          ViewCell *viewcell = *it;
-
-          // if ray not outside of view space
-          float contribution;
-          bool added =
-                viewcell->GetPvs().AddSample(ray.mTerminationObject,
-                                                                         contribution
-                                                                         );
-          if (added)
-                ray.mPvsContribution++;
-
-          ray.mRelativePvsContribution += contribution;
-        }
-  } else {
-    for (; it != viewcells.end(); ++it) {
-          ViewCell *viewcell = *it;
-          // if ray not outside of view space
-          float contribution;
-          if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
-                                                                                                   contribution
-                                                                                                   ))
-                ray.mPvsContribution++;
-
-          ray.mRelativePvsContribution += contribution;
-        }
-
-        for (it = viewcells.begin(); it != viewcells.end(); ++it) {
-          ViewCell *viewcell = *it;
-          // if ray not outside of view space
-          viewcell->GetPvs().AddSample(ray.mTerminationObject);
-        }
-  }
+        Vector3 origin = hray.Extrap(tmin);
+        Vector3 termination = hray.Extrap(tmax);
+
+        CastLineSegment(origin,
+                                        termination,
+                                        viewcells);
+        //Debug << "constribution: " << (int)viewcells.size() << endl;
+        // copy viewcells memory efficiently
+        const bool storeViewcells = false;
+        if (storeViewcells)
+        {
+                ray.mViewCells.reserve(viewcells.size());
+                ray.mViewCells = viewcells;
+        }
+
+        ViewCellContainer::const_iterator it = viewcells.begin();
+
+        bool addInPlace = false;
+
+        if (addInPlace) 
+        {
+                for (; it != viewcells.end(); ++it) {
+                        ViewCell *viewcell = *it;
+
+                        // if ray not outside of view space
+                        float contribution;
+                        bool added =
+                        viewcell->GetPvs().AddSample(ray.mTerminationObject,
+                                                                                        contribution
+                                                                                        );
+                        if (added)
+                        ray.mPvsContribution++;
+
+                        ray.mRelativePvsContribution += contribution;
+                }
+        } 
+        else 
+        {
+                for (; it != viewcells.end(); ++it) {
+                        ViewCell *viewcell = *it;
+                        // if ray not outside of view space
+                        float contribution;
+                        if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
+                                                                                                                contribution
+                                                                                                                ))
+                        ray.mPvsContribution++;
+                        ray.mRelativePvsContribution += contribution;
+                }
+
+                for (it = viewcells.begin(); it != viewcells.end(); ++it) {
+                        ViewCell *viewcell = *it;
+                        // if ray not outside of view space
+                        viewcell->GetPvs().AddSample(ray.mTerminationObject);
+                }
+        }
 }
 
@@ -1456 +1481 @@
                   << (int)constructionRays.size() << " samples" << endl;
 
-        mVspKdTree->Construct(constructionRays, &mSceneBox);
+        mVspKdTree->Construct(constructionRays, &mViewSpaceBox);
         Debug << mVspKdTree->GetStatistics() << endl;
 
@@ -1468 +1493 @@
         mVspKdTree->RefineViewCells(rays);
 
-                // collapse siblings belonging to the same view cell
+        // collapse siblings belonging to the same view cell
         mVspKdTree->CollapseTree();
 
@@ -1827 +1852 @@
         Debug << "saved rays: " << (int)savedRays.size() << endl;
 
-        mVspBspTree->Construct(constructionRays, &mSceneBox);
+        mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
 
         Debug << mVspBspTree->GetStatistics() << endl;
@@ -1982 +2007 @@
         }
 
-        EvaluateViewCellsStats();
-
-        // view cells already finished post processing step
+        
+        // view cells already finished before post processing step (i.e. because they were loaded)
         if (mViewCellsFinished)
+        {
+                EvaluateViewCellsStats();
                 return 0;
+        }
+        
+
+        // check if new view cells turned invalid
+        mVspBspTree->CheckValidy();
+        ResetViewCells();
+
 
         VssRayContainer postProcessRays;
@@ -2038 +2071 @@
         for (int i = 0; i < limit; ++ i)
         {
-                viewPoint = mSceneBox.GetRandomPoint();
+                viewPoint = mViewSpaceBox.GetRandomPoint();
                 if (mVspBspTree->ViewPointValid(viewPoint))
                 {
@@ -2051 +2084 @@
 bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
 {
-        return mSceneBox.IsInside(viewPoint) &&
+        return mViewSpaceBox.IsInside(viewPoint) &&
                    mVspBspTree->ViewPointValid(viewPoint);
 }
@@ -2072 +2105 @@
                 if (exporter)
                 {
+                        if (1)
+                        {
+                                exporter->SetWireframe();
+                                exporter->ExportBox(mViewSpaceBox);
+                                exporter->SetFilled();
+                        }
+
                         if (mExportGeometry)
+                        {
                                 exporter->ExportGeometry(objects);
+                        }
 
                         // export rays
@@ -2099 +2141 @@
         }
 
-        // export single view cells
+        //-- export single view cells
         ExportBspPvs(objects, visRays);
 }
@@ -2167 +2209 @@
                 VssRayContainer vcRays;
                 Intersectable::NewMail();
-#if 0
+#if 0 // largest view cell pvs first
                 BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
 #else
@@ -2301 +2343 @@
                                                                                           ViewCell *vc) const
 {
-#if 1
-    if (vc->GetMesh())
+        if (vc->GetMesh())
         {
                 exporter->ExportMesh(vc->GetMesh());
@@ -2312 +2353 @@
                 ConstructGeometry(dynamic_cast<BspViewCell *>(vc), geom);
         exporter->ExportPolygons(geom.mPolys);
-#else
-
-        Material m2;
-        m2.mDiffuseColor.b = 0.3f + Random(0.7f);
-        m2.mDiffuseColor.r = 0.0f;//0.3f + Random(0.7f);
-        m2.mDiffuseColor.g = 0.3f + Random(0.7f);
-        Material m;
-        m.mDiffuseColor.b = 0.0f;
-        m.mDiffuseColor.r = 1.0f;
-        m.mDiffuseColor.g = 0.0f;
-
-        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
-        vector<BspLeaf *>::const_iterator it, it_end = bspVc->mLeaves.end();
-
-        for (it = bspVc->mLeaves.begin(); it != it_end; ++ it)
-        {
-                if ((*it)->Mailed())
-                        exporter->SetForcedMaterial(m);
-                else
-                        exporter->SetForcedMaterial(m2);
-                        //exporter->ResetForcedMaterial();
-                BspNodeGeometry geom;
-                mVspBspTree->ConstructGeometry(*it, geom);
-                exporter->ExportPolygons(geom.mPolys);
-        }
-#endif
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -319 +319 @@
         ViewCellsStatistics mViewCellsStats;
         /// the scene bounding box
-        AxisAlignedBox3 mSceneBox;
+        AxisAlignedBox3 mViewSpaceBox;
         /// holds the view cell meshes
         MeshContainer mMeshContainer;

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -278 +278 @@
 
         int numObj = 0;
+
         //-- extract polygons intersected by the rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -313 +314 @@
         mMaxPvs = (int)(mMaxPvsRatio * (float)numObj);
         
-        Debug << "maximal pvs (i.e., view cell considered as valid: " << mMaxPvs << endl;
+        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mMaxPvs << endl;
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -382 +383 @@
 
         mStat.Start();
-        cout << "Contructing vsp bsp tree ... ";
-
-        long startTime = GetTime();
-        
-        bool mOutOfMemory = false;
+        cout << "Contructing vsp bsp tree ... \n";
+
+        long startTime = GetTime();     
+        long interTime = GetTime();     
+        mOutOfMemory = false;
+
+        int nleaves = 500;
 
         while (!tStack.empty())
@@ -404 +407 @@
                 }
 
-                // subdivide leaf node
+                        // subdivide leaf node
                 BspNode *r = Subdivide(tStack, tData);
 
                 if (r == mRoot)
                         Debug << "VSP BSP tree construction time spent at root: "
-                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl << endl;
-        }
-
-        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl;
+                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+
+                if (mStat.Leaves() >= nleaves)
+                {
+                        nleaves += 500;
+                                
+                        cout << "leaves=" << mStat.Leaves() << endl;
+                        Debug << "needed "
+                          << TimeDiff(interTime, GetTime())*1e-3 << " secs to create 500 leaves" << endl;
+                        interTime = GetTime();
+                }
+        }
+
+        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
         cout << "finished\n";
 
@@ -436 +449 @@
         BspNode *newNode = tData.mNode;
 
-        if (!mOutOfMemory || !TerminationCriteriaMet(tData))
+        if (!mOutOfMemory && !TerminationCriteriaMet(tData))
         {
                 PolygonContainer coincident;
@@ -508 +521 @@
 
 
+
+
 BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
                                                                    VspBspTraversalData &frontData,
@@ -517 +532 @@
         // select subdivision plane
         Plane3 splitPlane;
+        
         int maxCostMisses = tData.mMaxCostMisses;
-        bool success = SelectPlane(splitPlane, 
-                                                           leaf, 
-                                                           tData,
-                                                           frontData,
-                                                           backData);
+
+        const bool success = 
+                SelectPlane(splitPlane, leaf, tData, frontData, backData);
+
         if (!success)
         {
@@ -578 +593 @@
         if (mPvsUseArea)
         {
-                // if not already computed
+                // if geometry was not already computed
                 if (!frontData.mGeometry && !backData.mGeometry)
                 {
@@ -820 +835 @@
                                                                                  BspNodeGeometry **backGeom,
                                                                                  float &frontArea,
-                                                                                 float &backArea)
+                                                                                 float &backArea,
+                                                                                 bool useKdSplit)
 {
         const bool useCostHeuristics = false;
@@ -838 +854 @@
         AxisAlignedBox3 box;
         box.Initialize();
-        
+        //TODO: for kd split geometry already is box
         if (1 && mPvsUseArea)
         {
@@ -868 +884 @@
                                 Vector3 normal(0,0,0); normal[axis] = 1;
                                 
-                                nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), 
-                                                                                                  tData, *nFrontGeom[axis], *nBackGeom[axis],
-                                                                                                  nFrontArea[axis], nBackArea[axis]);
+                                if (useKdSplit)
+                                {
+                                        nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
+                                                                                                                                box,
+                                                                                                                                axis,
+                                                                                                                                nPosition[axis]);
+                                        
+                                        Vector3 pos = box.Max(); pos[axis] = nPosition[axis];
+                                        AxisAlignedBox3 frontBox(box.Min(), pos);
+                                        frontBox.ExtractPolys(nFrontGeom[axis]->mPolys);
+                                        
+                                        pos = box.Min(); pos[axis] = nPosition[axis];
+                                        AxisAlignedBox3 backBox(pos, box.Max());
+                                        backBox.ExtractPolys(nBackGeom[axis]->mPolys);
+
+                                }
+                                else
+                                {
+                                        nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), 
+                                                                                                          tData, *nFrontGeom[axis], *nBackGeom[axis],
+                                                                                                          nFrontArea[axis], nBackArea[axis]);
+                                }
                         }
                         else
@@ -903 +938 @@
         *frontGeom = nFrontGeom[bestAxis];
         *backGeom = nBackGeom[bestAxis];
+
         // and delete other geometry
         delete nFrontGeom[(bestAxis + 1) % 3];
@@ -913 +949 @@
         return nCostRatio[bestAxis];
 }
+
+
+float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
+                                                                                   const AxisAlignedBox3 &box,
+                                                                                   const int axis,
+                                                                                   const float &position) const
+{
+        int pvsFront = 0;
+        int pvsBack = 0;
+        int pvsTotal = 0;
+
+        // create unique ids for pvs heuristics
+        GenerateUniqueIdsForPvs();
+
+        const int pvsSize = data.mPvs;
+
+        // this is the main ray classification loop!
+        for(RayInfoContainer::iterator ri = data.mRays->begin();
+                ri != data.mRays->end(); ++ ri)
+        {
+                if (!(*ri).mRay->IsActive())
+                        continue;
+
+                // determine the side of this ray with respect to the plane
+                float t;
+                int side = (*ri).ComputeRayIntersection(axis, position, t);
+        
+                AddObjToPvs((*ri).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
+                AddObjToPvs((*ri).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
+        }
+
+        //-- only one of these options should be one
+        //-- pvs + probability heuristics
+        float pBack, pFront, pOverall;
+
+        if (1)
+        {
+                // box length substitute for probability
+                const float minBox = box.Min(axis);
+                const float maxBox = box.Max(axis);
+
+                pBack = position - minBox;
+                pFront = maxBox - position;
+                pOverall = maxBox - minBox;
+        }
+        else //-- area substitute for probability
+        {
+                pOverall = box.SurfaceArea();
+
+                const bool useMidSplit = true;
+                //const bool useMidSplit = false;       
+                                        
+                //-- simplified computation for mid split
+                const int axis2 = (axis + 1) % 3;
+                const int axis3 = (axis + 2) % 3;
+
+                const float faceArea = 
+                        (box.Max(axis2) - box.Min(axis2)) *
+                        (box.Max(axis3) - box.Min(axis3));
+
+                pBack = pFront = pOverall * 0.5f + faceArea;
+        }
+
+        //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
+        //Debug << pFront << " " << pBack << " " << pOverall << endl;
+
+        // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position);
+        const float newCost = pvsBack * pBack + pvsFront * pFront;
+        //  float oldCost = leaf->mRays.size();
+        const float oldCost = (float)pvsSize * pOverall;
+
+        return  (mCtDivCi + newCost) / oldCost;
+}
+
 
 
@@ -984 +1094 @@
         candidateCost = SelectAxisAlignedPlane(plane, data, axis,
                                                                                    &fGeom, &bGeom, 
-                                                                                   fArea, bArea);                                                
+                                                                                   fArea, bArea,
+                                                                                   onlyAxisAligned);     
 
         if (candidateCost < lowestCost)
@@ -991 +1102 @@
                 lowestCost = candidateCost;
 
-                //-- assign already computed values
+                // assign already computed values
+                // we can do this because we always save the
+                // computed values from the axis aligned splits
                 frontData.mGeometry = fGeom;
                 backData.mGeometry = bGeom;
@@ -1123 +1236 @@
         int totalPvs = 0;
 
+        int limit;
+        bool useRand;
+
+        // 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)
+        {
+                const int testIdx = useRand ? 
+                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
+                RayInfo rayInf = (*data.mRays)[testIdx];
+
+                float t;
+                VssRay *ray = rayInf.mRay;
+                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
+
+        if (cf >= 0)
+                        ++ raysFront;
+                if (cf <= 0)
+                        ++ raysBack;
+
+                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+                {
+                        sumBalancedRays += cf;
+                }
+
+                if (mSplitPlaneStrategy & BALANCED_RAYS)
+                {
+                        if (cf == 0)
+                                ++ sumRaySplits;
+                }
+
+                if (mSplitPlaneStrategy & PVS)
+                {
+                        // find front and back pvs for origing and termination object
+                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
+                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+                }
+        }
+
+        const float raysSize = (float)data.mRays->size() + Limits::Small;
         if (mSplitPlaneStrategy & PVS)
         {
@@ -1136 +1299 @@
                                                                                   mBox,
                                                                                   mEpsilon);
-
+#if 0
+                        AxisAlignedBox3 fbox;
+                        AxisAlignedBox3 bbox;
+                        AxisAlignedBox3 box;
+                        fbox.Initialize();
+                        bbox.Initialize();
+                        box.Initialize();
+
+                        geomFront.IncludeInBox(fbox);
+                        geomBack.IncludeInBox(bbox);
+                        data.mGeometry->IncludeInBox(box);
+
+                        areaFront = fbox.GetVolume();
+                        areaBack = bbox.GetVolume();
+
+                        pOverall = box.GetVolume();
+#else
                         areaFront = geomFront.GetArea();
                         areaBack = geomBack.GetArea();
 
+                        pOverall = data.mArea;
+#endif
                         pBack = areaBack;
                         pFront = areaFront;
-                        pOverall = data.mArea;
                 }
                 else // use number of rays to approximate volume
@@ -1152 +1332 @@
         }
 
-        int limit;
-        bool useRand;
-
-        // 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)
-        {
-                const int testIdx = useRand ? 
-                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
-                RayInfo rayInf = (*data.mRays)[testIdx];
-
-                float t;
-                VssRay *ray = rayInf.mRay;
-                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
-
-        if (cf >= 0)
-                        ++ raysFront;
-                if (cf <= 0)
-                        ++ raysBack;
-
-                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-                {
-                        sumBalancedRays += cf;
-                }
-
-                if (mSplitPlaneStrategy & BALANCED_RAYS)
-                {
-                        if (cf == 0)
-                                ++ sumRaySplits;
-                }
-
-                if (mSplitPlaneStrategy & PVS)
-                {
-                        // find front and back pvs for origing and termination object
-                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
-                }
-        }
-
-        const float raysSize = (float)data.mRays->size() + Limits::Small;
 
         if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
@@ -1473 +1603 @@
 }
 
+
+
+void VspBspTree::CheckValidy()
+{
+        stack<BspNode *> nodeStack;
+
+        if (!mRoot)
+                return;
+
+        nodeStack.push(mRoot);
+        
+        while (!nodeStack.empty()) 
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+                
+                if (node->IsLeaf())
+                {
+                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+                        if (node->TreeValid())
+                        {
+                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+                        
+                                if (viewCell->GetPvs().GetSize() > mMaxPvs)
+                                {
+                                        while (!viewCell->mLeaves.empty())
+                                        {
+                                                BspLeaf *l = viewCell->mLeaves.back();
+                                                l->SetTreeValid(false);
+                                                PropagateUpValidity(l);
+
+                                                l->SetViewCell(GetOrCreateOutOfBoundsCell());
+                                                viewCell->mLeaves.pop_back();
+                                        }
+
+                                        mOutOfBoundsCell->GetPvs().AddPvs(viewCell->GetPvs());
+
+                                        DEL_PTR(viewCell);
+                                }
+                        }
+                }
+                else
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+}
 
 void VspBspTree::CollectViewCells(BspNode *root, 
@@ -2438 +2619 @@
 
         //-- collect the leaves which haven't been found by ray casting
-        vector<BspLeaf *> leaves;
-        CollectLeaves(leaves, true, mMaxPvs);
-        Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
-        // TODO
-        CollectMergeCandidates(leaves);
+        if (0)
+        {
+                vector<BspLeaf *> leaves;
+                CollectLeaves(leaves, true, mMaxPvs);
+                Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
+                CollectMergeCandidates(leaves);
+        }
 
         return numLeaves;
@@ -2519 +2702 @@
                     mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
         {
-                //Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
-                //        << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
-                //        << " max ratio: " << mMergeMaxCostRatio << endl;
+                /*Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
+                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
+                          << " max ratio: " << mMergeMaxCostRatio << endl;*/
                 BspMergeCandidate mc = mMergeQueue.top();
                 mMergeQueue.pop();
@@ -2532 +2715 @@
                 {
                         ViewCell::NewMail();
+        
                         MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
                         -- nViewCells;
@@ -2709 +2893 @@
 
         leaf->SetViewCell(vc2); // finally change view cell
-        
-        //Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
-        //        << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
-
 }
 
@@ -2741 +2921 @@
         if (shuffledCost1 < shuffledCost2)
         {
-                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl;
                 ShuffleLeaf(leaf1, vc1, vc2);
                 leaf1->Mail();
@@ -2747 +2926 @@
         else
         {
-                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl;
                 ShuffleLeaf(leaf2, vc2, vc1);
                 leaf2->Mail();
@@ -2879 +3057 @@
 
         //-- compute ratio of old cost
-        //-- (added size of left and right view cell times pvs size)
-        //-- to new rendering cost (size of merged view cell times pvs size)
+        //   (i.e., added size of left and right view cell times pvs size)
+        //   to new rendering cost (i.e, size of merged view cell times pvs size)
         const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
 
@@ -2886 +3064 @@
                 (float)newPvs * (vc1->GetArea() + vc2->GetArea());
 
-        mMergeCost = newCost - oldCost;
         if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
-                mMergeCost += 1.0;
-}
+        {
+                mMergeCost = 1e15f;
+        }
+        else
+        {
+                mMergeCost = newCost - oldCost;
+        }
+}
+
 
 void BspMergeCandidate::SetLeaf1(BspLeaf *l)
@@ -2896 +3080 @@
 }
 
+
 void BspMergeCandidate::SetLeaf2(BspLeaf *l)
 {
@@ -2901 +3086 @@
 }
 
+
 BspLeaf *BspMergeCandidate::GetLeaf1()
 {
@@ -2906 +3092 @@
 }
 
+
 BspLeaf *BspMergeCandidate::GetLeaf2()
 {
         return mLeaf2;
 }
+
 
 bool BspMergeCandidate::Valid() const
@@ -2918 +3106 @@
 }
 
+
 float BspMergeCandidate::GetMergeCost() const
 {
         return mMergeCost;
 }
+
 
 void BspMergeCandidate::SetValid()

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -60 +60 @@
                 /// how often this branch has missed the max-cost ratio
                 int mMaxCostMisses;
-        
+                /// bounding box of current view space.
+                ///AxisAlignedBox3 mBbox;
+                
                 /** Returns average ray contribution.
                 */
@@ -78 +80 @@
                 mGeometry(NULL),
                 mMaxCostMisses(0)
+                //,mIsAxisAligned(false)
                 {}
                 
@@ -297 +300 @@
                                                   ViewCellContainer &viewCells,
                                                   bool onlyUnmailed = false) const;
+
+        /** returns maximal valid pvs.
+        */
+        int GetMaxPvs() { return mMaxPvs;}
+
+        /** Checks validy of view cells.
+                if not valid, sets regions invalid and deletes view cell.
+        */
+        void CheckValidy();
+
 protected:
 
@@ -326 +339 @@
         };
 
+        float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
+                                                                   const AxisAlignedBox3 &box,
+                                                                   const int axis,
+                                                                   const float &position) const;
+
         /** Returns view cell corresponding to 
                 the invalid view space. If it does not exist, it is created.
@@ -447 +465 @@
                                                                  BspNodeGeometry **backGeom,
                                                                  float &frontArea,
-                                                                 float &backArea);
+                                                                 float &backArea,
+                                                                 bool useKdSplit);
 
         /** Sorts split candidates for surface area heuristics for axis aligned splits.
@@ -779 +798 @@
         static float sOverallCost;
 
+        /** Evaluates the merge costs of the leaves.
+        */
+        void EvalMergeCost();
+
 protected:
 
@@ -784 +807 @@
         */
         float GetCost(ViewCell *vc) const;
-        /** Evaluates the merge costs of the leaves.
-        */
-        void EvalMergeCost();
-
+        
         int mLeaf1Id;
         int mLeaf2Id;

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -832 +832 @@
         float pBack, pFront, pOverall;
 
-        if (0)
+        if (1)
         {
                 // box length substitute for probability
@@ -843 +843 @@
         }
 
-        if (1) //-- area substitute for probability
+        if (0) //-- area substitute for probability
         {
                 pOverall = box.SurfaceArea();

trunk/VUT/GtpVisibilityPreprocessor/src/common.cpp

@@ -46 +46 @@
 Real Limits::Threshold = 1e-6f;
 Real Limits::Small = 0.01f;
-Real Limits::Infinity = 1e20f;
+Real Limits::Infinity = 1e20;