Changeset 547 for trunk/VUT/GtpVisibilityPreprocessor/src

Timestamp:

01/17/06 23:28:10 (19 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• AxisAlignedBox3.cpp (modified) (1 diff)
• Environment.cpp (modified) (1 diff)
• ViewCell.cpp (modified) (3 diffs)
• ViewCell.h (modified) (2 diffs)
• ViewCellBsp.cpp (modified) (5 diffs)
• ViewCellBsp.h (modified) (5 diffs)
• ViewCellsManager.cpp (modified) (13 diffs)
• ViewCellsManager.h (modified) (13 diffs)
• VspBspTree.cpp (modified) (66 diffs)
• VspBspTree.h (modified) (20 diffs)
• X3dExporter.cpp (modified) (1 diff)
• default.env (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp

@@ -2082 +2082 @@
     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/Environment.cpp

@@ -1708 +1708 @@
                                         "vsp_bsp_term_min_pvs=",
                                         "20");
-        RegisterOption("VspBspTree.Termination.minArea",
+        RegisterOption("VspBspTree.Termination.minProbability",
                                         optFloat,
-                                        "vsp_bsp_term_min_area=",
+                                        "vsp_bsp_term_min_probability=",
                                         "0.001");
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -11 +11 @@
 mPiercingRays(0),
 mArea(0),
-mVolume(0)
+mVolume(0),
+mValid(true)
 {
 }
@@ -19 +20 @@
 mPiercingRays(0),
 mArea(0),
-mVolume(0)
+mVolume(0),
+mValid(true)
 {
 }
@@ -96 +98 @@
 
 
+void ViewCell::SetValid(const bool valid)
+{
+        mValid = true;
+}
+
+
+bool ViewCell::GetValid() const
+{
+        return mValid;
+}
+
+
 /************************************************************************/
 /*                class ViewCellsStatistics implementation              */

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -131 +131 @@
         void SetMesh(Mesh *mesh);
 
+        void SetValid(const bool valid);
+        bool GetValid() const;
+
 protected:
 
@@ -138 +141 @@
         float mVolume;
         float mArea;
+
+
+        bool mValid;
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -212 +212 @@
 BspTree::BspTree():  
 mRoot(NULL), 
-mPvsUseArea(true),
+mUseAreaForPvs(true),
 mGenerateViewCells(true)
 {
@@ -410 +410 @@
                 << maxCostNodes * 100 / (double)Leaves() << endl;
 
-        app << "#N_PMINAREALEAVES  ( Percentage of leaves with mininum area )\n"
-                << minAreaNodes * 100 / (double)Leaves() << endl;
+        app << "#N_PMINAREALEAVES  ( Percentage of leaves with mininum probability )\n"
+                << minProbabilityNodes * 100 / (double)Leaves() << endl;
 
         app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" 
@@ -1535 +1535 @@
                 GenerateUniqueIdsForPvs();
 
-                if (mPvsUseArea) // use front and back cell areas to approximate volume
+                if (mUseAreaForPvs) // use front and back cell areas to approximate volume
                 {
                         // construct child geometry with regard to the candidate split plane
@@ -1607 +1607 @@
                         AddObjToPvs(ray->sourceObject.mObject, cf, frontPvs, backPvs);
                         
-                        if (mPvsUseArea)
+                        if (mUseAreaForPvs)
                         {
                                 float len = 1;
@@ -1830 +1830 @@
         
         if (data.mGeometry->GetArea() <= mTermMinArea) 
-                ++ mStat.minAreaNodes;
+                ++ mStat.minProbabilityNodes;
 
 #ifdef _DEBUG

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -130 +130 @@
         int maxRayContribNodes;
         // minimum area nodes
-        int minAreaNodes;
+        int minProbabilityNodes;
         /// nodes termination because of max cost ratio;
         int maxCostNodes;
@@ -181 +181 @@
                 minRaysNodes = 0;
                 maxRayContribNodes = 0;
-                minAreaNodes = 0;
+                minProbabilityNodes = 0;
                 maxCostNodes = 0;
 
@@ -310 +310 @@
 /** BSP leaf node implementation.
 */
-class BspLeaf : public BspNode 
+class BspLeaf: public BspNode 
 {
         friend class BspTree;
@@ -340 +340 @@
         ObjectPvs *mPvs;
 
-        /// leaf area
-        float mArea;
+        /// Probability that the view point lies in this leaf
+        float mProbability;
 
 protected:
@@ -886 +886 @@
 
         /// if area or accumulated ray lenght should be used for PVS heuristics
-        bool mPvsUseArea;
+        bool mUseAreaForPvs;
 
         /// epsilon where two points are still considered equal

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -25 +25 @@
 mTotalAreaValid(false),
 mTotalArea(0.0f),
-mViewCellsFinished(false)
+mViewCellsFinished(false),
+mMaxPvsSize(99999)
 {
         mViewSpaceBox.Initialize();
@@ -49 +50 @@
         environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
         environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
+        environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
 
         char buf[50];
@@ -105 +107 @@
         return (int)rays.size();
 }
+
+
+bool ViewCellsManager::CheckValid(ViewCell *vc) const
+{
+        if (vc->GetPvs().GetSize() > mMaxPvsSize)
+                return false;
+
+        return true;
+}
+
 
 bool ViewCellsManager::LoadViewCells(const string filename, ObjectContainer *objects)
@@ -347 +359 @@
 }
 
+
 ViewCellContainer &ViewCellsManager::GetViewCells()
 {
@@ -375 +388 @@
         // has to be recomputed
         mTotalAreaValid = false;
+}
+
+
+int ViewCellsManager::GetMaxPvsSize() const
+{
+        return mMaxPvsSize;
 }
 
@@ -1797 +1816 @@
 float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
 {
-#if 0
-        return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
-#else
-        return GetArea(viewCell) / GetAccVcArea();
-#endif
+        if (mVspBspTree->mUseAreaForPvs)
+                return GetArea(viewCell) / GetAccVcArea();
+        else
+                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
 }
 
@@ -1807 +1825 @@
 void VspBspViewCellsManager::CollectViewCells()
 {
-        mVspBspTree->CollectViewCells(mViewCells);
+        mVspBspTree->CollectViewCells(mViewCells, false);
 }
 
@@ -1852 +1870 @@
         Debug << "saved rays: " << (int)savedRays.size() << endl;
 
+        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
+        
         mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
 
@@ -1929 +1949 @@
 
         // TODO: should be done BEFORE the ray casting
-        merged = mVspBspTree->MergeViewCells(rays);
+        merged = mVspBspTree->MergeViewCells(rays, objects);
 
         //-- stats and visualizations
@@ -2300 +2320 @@
                                                                                  ViewCell *vc) const
 {
-        if (mColorCode == 0) // Random color
+        if (CheckValid(vc) && (mColorCode == 0)) // Random color
                 return;
 
         float importance = 0;
-
+        
+        Material m;
+        
         switch (mColorCode)
         {
@@ -2319 +2341 @@
                         importance = (float)bspVc->mLeaves.size() /
                                 (float)mViewCellsStats.maxLeaves;
+
+                        if (CheckValid(vc))
+                                m.mDiffuseColor.b = 1.0f;
+                        m.mDiffuseColor.r = importance;
+                        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
                 }
                 break;
@@ -2325 +2352 @@
                         importance = (float)GetMaxTreeDiff(vc) /
                                 (float)(mVspBspTree->GetStatistics().maxDepth * 2);
+
+                        if (CheckValid(vc))
+                                m.mDiffuseColor.b = 1.0f;
+                        m.mDiffuseColor.r = importance;
+                        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
                 }
                 break;
@@ -2331 +2363 @@
         }
 
-        Material m;
-        m.mDiffuseColor.b = 1.0f;
+        m.mDiffuseColor.b = CheckValid(vc) ? 1.0f : 0.0f;
         m.mDiffuseColor.r = importance;
         m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
+
         //Debug << "importance: " << importance << endl;
         exporter->SetForcedMaterial(m);

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -251 +251 @@
         virtual int CastBeam(Beam &beam);
 
+        /** Checks if view cell is considered as valid.
+        */
+        virtual bool CheckValid(ViewCell *vc) const;
+
+        /** Returns maximal allowed pvs size.
+        */
+        int GetMaxPvsSize() const;
+
+
+        /** Exports view cell geometry.
+        */
+        virtual void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const = 0;
+
 protected:
 
@@ -258 +271 @@
         */
         void CreateUniqueViewCellIds();
+
         /** Recollects view cells and resets statistics.
         */
@@ -281 +295 @@
         virtual void ExportColor(Exporter *exporter, ViewCell *vc) const = 0;
 
-        /** Exports view cell geometry.
-        */
-        virtual void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const = 0;
-
+        
         /** Creates meshes from the view cells.
         */
@@ -316 +327 @@
         float mTotalAreaValid;
         float mTotalArea;
+
+        int mMaxPvsSize;
+
+        float mMaxPvsRatio;
 
         ViewCellsStatistics mViewCellsStats;
@@ -324 +339 @@
         /// if view cells should be exported
         bool mExportViewCells;
+
+
         //-- visualization options
         
@@ -380 +397 @@
         void CreateMesh(ViewCell *vc);
 
+        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+
 protected:
 
@@ -396 +415 @@
 
         void ExportColor(Exporter *exporter, ViewCell *vc) const;
-        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+        
+
 
         /// the BSP tree.
@@ -453 +473 @@
         void CreateMesh(ViewCell *vc);
 
+        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+
 protected:
 
@@ -459 +481 @@
 
         void ExportColor(Exporter *exporter, ViewCell *vc) const;
-        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+
 
         /// the BSP tree.
@@ -509 +531 @@
         void CreateMesh(ViewCell *vc);
 
+        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+
 protected:
 
@@ -517 +541 @@
 
         void ExportColor(Exporter *exporter, ViewCell *vc) const;
-        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+
 
 
@@ -573 +597 @@
         int CastBeam(Beam &beam);
 
+        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+
 protected:
 
@@ -591 +617 @@
 
         void ExportColor(Exporter *exporter, ViewCell *vc) const;
-        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
-
 
         /// the view space partition BSP tree.

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -36 +36 @@
 
 float BspMergeCandidate::sOverallCost = 0;
+bool BspMergeCandidate::sUseArea = false;
 
 /********************************************************************/
@@ -43 +44 @@
 VspBspTree::VspBspTree():
 mRoot(NULL),
-mPvsUseArea(true),
+mUseAreaForPvs(false),
 mCostNormalizer(Limits::Small),
 mViewCellsManager(NULL),
 mOutOfBoundsCell(NULL),
-mShowInvalidSpace(false),
 mStoreRays(false)
 {
@@ -59 +59 @@
         environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
         environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
-        environment->GetFloatValue("VspBspTree.Termination.minArea", mTermMinArea);
+        environment->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
         environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
         environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
@@ -89 +89 @@
         environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
 
-        environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
 
         //-- termination criteria for axis aligned split
@@ -100 +99 @@
         environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
 
+        
+        mStats.open("bspStats.log");
+
         //-- debug output
         Debug << "******* VSP BSP options ******** " << endl;
     Debug << "max depth: " << mTermMaxDepth << endl;
         Debug << "min PVS: " << mTermMinPvs << endl;
-        Debug << "min area: " << mTermMinArea << endl;
+        Debug << "min probabiliy: " << mTermMinProbability << endl;
         Debug << "min rays: " << mTermMinRays << endl;
         Debug << "max ray contri: " << mTermMaxRayContribution << endl;
@@ -158 +160 @@
                 mOutOfBoundsCell = new BspViewCell();
                 mOutOfBoundsCell->SetId(-1);
-        }
+                mOutOfBoundsCell->SetValid(false);
+        }
+
         return mOutOfBoundsCell;
 }
@@ -311 +315 @@
                 }
         }
-
-        mMaxPvs = (int)(mMaxPvsRatio * (float)numObj);
-        
-        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mMaxPvs << endl;
+        
+        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -334 +336 @@
         }
 
-        mTermMinArea *= mBox.SurfaceArea(); // normalize
+        if (mUseAreaForPvs)
+                mTermMinProbability *= mBox.SurfaceArea(); // normalize
+        else 
+                mTermMinProbability *= mBox.GetVolume();
+
         mStat.polys = (int)polys.size();
 
@@ -372 +378 @@
         ConstructGeometry(mRoot, *geom);
 
+        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
+
         VspBspTraversalData tData(mRoot,
                                                           new PolygonContainer(polys),
@@ -377 +385 @@
                                                           rays,
                               ComputePvsSize(*rays),
-                                                          geom->GetArea(),
+                                                          prop,
                                                           geom);
 
@@ -386 +394 @@
 
         long startTime = GetTime();     
+        // used for intermediate time measurements
         long interTime = GetTime();     
+
         mOutOfMemory = false;
 
@@ -437 +447 @@
                 (((int)data.mRays->size() <= mTermMinRays) ||
                  (data.mPvs <= mTermMinPvs)   ||
-                 (data.mArea <= mTermMinArea) ||
+                 (data.mProbability <= mTermMinProbability) ||
                  (mStat.Leaves() >= mMaxViewCells) ||
                  (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
@@ -475 +485 @@
         {
                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
-                BspViewCell *viewCell;
-
-                if (!CheckValid(tData))
-                {
-                        leaf->SetTreeValid(false);
-                        PropagateUpValidity(leaf);
-                        // view cell for invalid view space
-                        viewCell = GetOrCreateOutOfBoundsCell();
-                        ++ mStat.invalidLeaves;
-                }
-                else
-                {       // create new view cell for this leaf                   
-                        viewCell = new BspViewCell();
-                }
+                BspViewCell *viewCell = new BspViewCell();
                 
                 leaf->SetViewCell(viewCell);
@@ -506 +503 @@
                                 leaf->mVssRays.push_back((*it).mRay);
                 }
-
-                viewCell->mLeaves.push_back(leaf);
-                viewCell->SetArea(tData.mArea);
-                leaf->mArea = tData.mArea;
+                
+                if (!mViewCellsManager->CheckValid(viewCell))
+                {
+                        viewCell->SetValid(false);
+
+                        leaf->SetTreeValid(false);
+                        PropagateUpValidity(leaf);
+
+                        ++ mStat.invalidLeaves;
+                }
+                
+        viewCell->mLeaves.push_back(leaf);
+
+                if (mUseAreaForPvs)
+                        viewCell->SetArea(tData.mProbability);
+                else
+                        viewCell->SetVolume(tData.mProbability);
+
+                leaf->mProbability = tData.mProbability;
 
                 EvaluateLeafStats(tData);               
@@ -591 +603 @@
 
         // split front and back node geometry and compute area
-        if (mPvsUseArea)
-        {
-                // if geometry was not already computed
-                if (!frontData.mGeometry && !backData.mGeometry)
-                {
-                        frontData.mGeometry = new BspNodeGeometry();
-                        backData.mGeometry = new BspNodeGeometry();
-
-                        tData.mGeometry->SplitGeometry(*frontData.mGeometry,
-                                                                                   *backData.mGeometry,
-                                                                                   interior->GetPlane(),
-                                                                                   mBox,
-                                                                                   mEpsilon);
+        
+        // if geometry was not already computed
+        if (!frontData.mGeometry && !backData.mGeometry)
+        {
+                frontData.mGeometry = new BspNodeGeometry();
+                backData.mGeometry = new BspNodeGeometry();
+
+                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
+                                                                           *backData.mGeometry,
+                                                                           interior->GetPlane(),
+                                                                           mBox,
+                                                                           mEpsilon);
                 
-                        //frontData.mArea = frontData.mGeometry->GetArea();
-                        //backData.mArea = backData.mGeometry->GetArea();
-                        frontData.mArea = frontData.mGeometry->GetVolume();
-                        backData.mArea = backData.mGeometry->GetVolume();
-                }
-        }
-        else
-        {
-                frontData.mArea = (float)frontData.mRays->size();
-                backData.mArea = (float)backData.mRays->size();
-        }
+                if (mUseAreaForPvs)
+                {
+                        frontData.mProbability = frontData.mGeometry->GetArea();
+                        backData.mProbability = backData.mGeometry->GetArea();
+                }
+                else
+                {
+                        frontData.mProbability = frontData.mGeometry->GetVolume();
+                        backData.mProbability = backData.mGeometry->GetVolume();
+                }
+        }
+        
 
         //-- create front and back leaf
@@ -836 +848 @@
                                                                                  BspNodeGeometry **frontGeom,
                                                                                  BspNodeGeometry **backGeom,
-                                                                                 float &frontArea,
-                                                                                 float &backArea,
-                                                                                 bool useKdSplit)
+                                                                                 float &pFront,
+                                                                                 float &pBack,
+                                                                                 const bool useKdSplit)
 {
         const bool useCostHeuristics = false;
@@ -845 +857 @@
         float nPosition[3];
         float nCostRatio[3];
-        float nFrontArea[3];
-        float nBackArea[3];
+        float nProbFront[3];
+        float nProbBack[3];
 
         BspNodeGeometry *nFrontGeom[3];
@@ -856 +868 @@
         AxisAlignedBox3 box;
         box.Initialize();
+        
         //TODO: for kd split geometry already is box
-        if (1 && mPvsUseArea)
+        if (1 && mUseAreaForPvs)
         {
                 PolygonContainer::const_iterator it, it_end = tData.mGeometry->mPolys.end();
@@ -872 +885 @@
         }
 
-        int sAxis = box.Size().DrivingAxis();
+        const int sAxis = box.Size().DrivingAxis();
 
         for (axis = 0; axis < 3; ++ axis)
@@ -885 +898 @@
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
                                 Vector3 normal(0,0,0); normal[axis] = 1.0f;
-                                
+
+                                // allows faster split because we have axis aligned kd tree boxes
                                 if (useKdSplit)
                                 {
@@ -891 +905 @@
                                                                                                                                 box,
                                                                                                                                 axis,
-                                                                                                                                nPosition[axis]);
+                                                                                                                                nPosition[axis],
+                                                                                                                                nProbFront[axis], 
+                                                                                                                                nProbBack[axis]);
                                         
                                         Vector3 pos;
                                         
                                         pos = box.Max(); pos[axis] = nPosition[axis];
-                                        const AxisAlignedBox3 backBox(box.Min(), pos);
-                                        backBox.ExtractPolys(nBackGeom[axis]->mPolys);
+                                        AxisAlignedBox3 bBox(box.Min(), pos);
+                                        bBox.ExtractPolys(nBackGeom[axis]->mPolys);
                                         
                                         pos = box.Min(); pos[axis] = nPosition[axis];
-                                        const AxisAlignedBox3 frontBox(pos, box.Max());
-                                        frontBox.ExtractPolys(nFrontGeom[axis]->mPolys);
-
+                                        AxisAlignedBox3 fBox(pos, box.Max());
+                                        fBox.ExtractPolys(nFrontGeom[axis]->mPolys);
                                 }
                                 else
@@ -908 +923 @@
                                         nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), 
                                                                                                           tData, *nFrontGeom[axis], *nBackGeom[axis],
-                                                                                                          nFrontArea[axis], nBackArea[axis]);
+                                                                                                          nProbFront[axis], nProbBack[axis]);
                                 }
                         }
@@ -936 +951 @@
         //-- assign values
         axis = bestAxis;
-        frontArea = nFrontArea[bestAxis];
-        backArea = nBackArea[bestAxis];
+        pFront = nProbFront[bestAxis];
+        pBack = nProbBack[bestAxis];
 
         // assign best split nodes geometry 
@@ -958 +973 @@
                                                                                    const AxisAlignedBox3 &box,
                                                                                    const int axis,
-                                                                                   const float &position) const
-{
+                                                                                   const float &position,                                                                                 
+                                                                                   float &pFront,
+                                                                                   float &pBack) const
+{
+        int pvsTotal = 0;
         int pvsFront = 0;
         int pvsBack = 0;
-        int pvsTotal = 0;
-
+        
         // create unique ids for pvs heuristics
         GenerateUniqueIdsForPvs();
@@ -984 +1001 @@
         }
 
-        //-- only one of these options should be one
-        //-- pvs + probability heuristics
-        float pBack, pFront, pOverall;
-
-        if (1)
-        {
+        //-- pvs heuristics
+        float pOverall;
+
+        // -- simplified computation for mid split
+        
+        
+        pOverall = data.mProbability;
+
+        if (!mUseAreaForPvs)
+        {   // volume
+                pBack = pFront = pOverall * 0.5f;
                 // box length substitute for probability
+#if 0
                 const float minBox = box.Min(axis);
                 const float maxBox = box.Max(axis);
@@ -997 +1020 @@
                 pFront = maxBox - position;
                 pOverall = maxBox - minBox;
+#endif
         }
         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;
@@ -1019 +1037 @@
         //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;
 
@@ -1094 +1110 @@
         int axis;
         BspNodeGeometry *fGeom, *bGeom;
-        float fArea, bArea;
+        float pFront, pBack;
 
         candidateCost = SelectAxisAlignedPlane(plane, data, axis,
                                                                                    &fGeom, &bGeom, 
-                                                                                   fArea, bArea,
+                                                                                   pFront, pBack,
                                                                                    onlyAxisAligned);     
 
@@ -1109 +1125 @@
                 // we can do this because we always save the
                 // computed values from the axis aligned splits
+                
                 frontData.mGeometry = fGeom;
                 backData.mGeometry = bGeom;
-                frontData.mArea = fArea;
-                backData.mArea = bArea;
-
+        
+                frontData.mProbability = pFront;
+                backData.mProbability = pBack;
+                
                 //! error also computed if cost ratio is missed
                 ++ mStat.splits[axis];
@@ -1220 +1238 @@
                                                                  BspNodeGeometry &geomFront,
                                                                  BspNodeGeometry &geomBack,
-                                                                 float &areaFront,
-                                                                 float &areaBack) const
+                                                                 float &pFront,
+                                                                 float &pBack) const
 {
         float cost = 0;
@@ -1233 +1251 @@
         // probability that view point lies in back / front node
         float pOverall = 0;
-        float pFront = 0;
-        float pBack = 0;
+        pFront = 0;
+        pBack = 0;
 
         int raysFront = 0;
@@ -1290 +1308 @@
 
         const float raysSize = (float)data.mRays->size() + Limits::Small;
+
         if (mSplitPlaneStrategy & PVS)
         {
@@ -1295 +1314 @@
                 GenerateUniqueIdsForPvs();
 
-                if (mPvsUseArea) // use front and back cell areas to approximate volume
-                {
-                        // construct child geometry with regard to the candidate split plane
-                        data.mGeometry->SplitGeometry(geomFront,
-                                                                                  geomBack,
-                                                                                  candidatePlane,
-                                                                                  mBox,
-                                                                                  mEpsilon);
-
-                        
+                // construct child geometry with regard to the candidate split plane
+                data.mGeometry->SplitGeometry(geomFront,
+                                                                          geomBack,
+                                                                          candidatePlane,
+                                                                          mBox,
+                                                                          mEpsilon);
+
+                pOverall = data.mProbability;
+
+                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
+                {
                         pFront = geomFront.GetVolume();
-                        pBack = geomBack.GetVolume();
-                        //areaFront = geomFront.GetArea();
-                        //areaBack = geomBack.GetArea();
-
-                        pOverall = data.mArea;
-
-                }
-                else // use number of rays to approximate volume
-                {
-                        pOverall = (float)data.mRays->size();
-                        pFront = (float)raysFront;
-                        pBack = (float)raysBack;
+                        pBack = pOverall - geomFront.GetVolume();
+                }
+                else
+                {
+                        pFront = geomFront.GetArea();
+                        pBack = geomBack.GetArea();
                 }
         }
@@ -1471 +1485 @@
                 ++ mStat.maxRayContribNodes;
 
-        if (data.mArea <= mTermMinArea)
-                ++ mStat.minAreaNodes;
+        if (data.mProbability <= mTermMinProbability)
+                ++ mStat.minProbabilityNodes;
         
         // accumulate depth to compute average depth
@@ -1586 +1600 @@
 
 
-void VspBspTree::CollectViewCells(ViewCellContainer &viewCells) const
+void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
 {
         ViewCell::NewMail();
-        CollectViewCells(mRoot, viewCells, true);
+        CollectViewCells(mRoot, onlyValid, viewCells);
 }
 
@@ -1602 +1616 @@
         nodeStack.push(mRoot);
         
+        const bool addToUnbounded = false;
+
         while (!nodeStack.empty()) 
         {
@@ -1611 +1627 @@
                         BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
 
-                        if (node->TreeValid())
+                        if (!addToUnbounded && node->TreeValid())
                         {
                                 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
                         
-                                if (viewCell->GetPvs().GetSize() > mMaxPvs)
+                                if (!mViewCellsManager->CheckValid(viewCell))
                                 {
-                                        while (!viewCell->mLeaves.empty())
+                                        vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
+                                        for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
                                         {
-                                                BspLeaf *l = viewCell->mLeaves.back();
+                                                BspLeaf *l = *it;
+                                                
                                                 l->SetTreeValid(false);
+                                                PropagateUpValidity(l);
+                                                
+                                                if (addToUnbounded)
+                                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
+
                                                 ++ mStat.invalidLeaves;
-                                                PropagateUpValidity(l);
-
-                                                l->SetViewCell(GetOrCreateOutOfBoundsCell());
-                                                viewCell->mLeaves.pop_back();
                                         }
 
-                                        mOutOfBoundsCell->GetPvs().AddPvs(viewCell->GetPvs());
-
-                                        DEL_PTR(viewCell);
+                                        // add to unbounded view cell or set to invalid
+                                        if (addToUnbounded)
+                                        {
+                                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
+                                                DEL_PTR(viewCell);
+                                        }
+                                        else
+                                        {
+                                                viewCell->SetValid(false);
+                                        }
                                 }
                         }
@@ -1644 +1670 @@
 }
 
-void VspBspTree::CollectViewCells(BspNode *root, 
+
+void VspBspTree::CollectViewCells(BspNode *root,
+                                                                  bool onlyValid,
                                                                   ViewCellContainer &viewCells,
                                                                   bool onlyUnmailed) const
@@ -1662 +1690 @@
                 if (node->IsLeaf())
                 {
-                        if (!mShowInvalidSpace && node->TreeValid())
+                        if (!onlyValid ||node->TreeValid())
                         {
                                 ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
@@ -2357 +2385 @@
                 {
                 case -1:
-                        CollectViewCells(node, beam.mViewCells, true);
+                        CollectViewCells(node, true, beam.mViewCells, true);
                         break;
                 case 0:
@@ -2427 +2455 @@
 
         // set new size of view cell
-        vc->SetArea(fVc->GetArea() + bVc->GetArea());
-
+        if (mUseAreaForPvs)
+                vc->SetArea(fVc->GetArea() + bVc->GetArea());
+        else
+                vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
+        
         vector<BspLeaf *> fLeaves = fVc->mLeaves;
         vector<BspLeaf *> bLeaves = bVc->mLeaves;
@@ -2480 +2511 @@
 
                 BspMergeCandidate::sOverallCost += 
-                        leaf->mArea * leaf->mPvs->GetSize();
+                        leaf->mProbability * leaf->mPvs->GetSize();
 
                 // the same leaves must not be part of two merge candidates
@@ -2510 +2541 @@
         vector<BspRay *> bspRays;
 
+        ViewCell::NewMail();
         long startTime = GetTime();
         ConstructBspRays(bspRays, rays);
@@ -2525 +2557 @@
         {  
                 BspRay *ray = bspRays[i];
-          
+        
                 // traverse leaves stored in the rays and compare and 
                 // merge consecutive leaves (i.e., the neighbors in the tree)
@@ -2541 +2573 @@
 
                         BspMergeCandidate::sOverallCost += 
-                                leaf->mArea * leaf->mPvs->GetSize();
+                                leaf->mProbability * leaf->mPvs->GetSize();
                         
                         ++ numLeaves;
@@ -2566 +2598 @@
                                 
                                 BspMergeCandidate::sOverallCost += 
-                                        leaf->mArea * leaf->mPvs->GetSize();
+                                        leaf->mProbability * leaf->mPvs->GetSize();
 
                                 ++ numLeaves;
@@ -2585 +2617 @@
                                                 found = true; // already in queue
                         }
-                        
+                
                         if (!found)
                         {
@@ -2595 +2627 @@
                                 leaf->Mail();
                                 prevLeaf->Mail();
-
+                
                                 mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
                         }
@@ -2611 +2643 @@
         {
                 vector<BspLeaf *> leaves;
-                CollectLeaves(leaves, true, mMaxPvs);
+                CollectLeaves(leaves, true);
                 Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
                 CollectMergeCandidates(leaves);
@@ -2652 +2684 @@
                         //NOTE: not sorted!
                         for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+                        {
                                 ray->intersections.push_back(BspIntersection(0, *it));
+                        }
                 }
 
@@ -2660 +2694 @@
 
 
-int VspBspTree::MergeViewCells(const VssRayContainer &rays)
-{
-        BspMergeCandidate::sMaxPvsSize = mMaxPvs;
+int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
+{
+        BspMergeCandidate::sMaxPvsSize = mViewCellsManager->GetMaxPvsSize();
+        BspMergeCandidate::sUseArea = mUseAreaForPvs;
 
         MergeStatistics mergeStats;
@@ -2685 +2720 @@
 
         int nViewCells = mStat.Leaves() - mStat.invalidLeaves;
+        int pass = 0;
+        const int nextPass = 200;
 
         //-- use priority queue to merge leaf pairs
@@ -2704 +2741 @@
                 {
                         ViewCell::NewMail();
-        
+                        const float mergeCost = mc.GetMergeCost();
+
                         MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
                         -- nViewCells;
                         
-                        ++ mergeStats.merged;
                         
                         // increase absolute merge cost
                         BspMergeCandidate::sOverallCost += mc.GetMergeCost();
+
+                        
 
                         if (showMergeStats)
@@ -2723 +2762 @@
                                         mergeStats.maxTreeDist = dist;
                                 mergeStats.accTreeDist += dist;
+
+
+                                if ((mergeStats.merged % nextPass == 0) || (nViewCells == mMergeMinViewCells))
+                                {
+                                        mStats 
+                                                << "#Pass\n" << pass ++ << endl
+                                                << "#Merged\n" << mergeStats.merged << endl 
+                                                << "#Viewcells\n" << nViewCells << endl 
+                                                << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl 
+                                                << "#CurrentCost\n" << mergeCost << endl
+                                                << "#RelCost\n" << mc.GetMergeCost() / BspMergeCandidate::sOverallCost << endl
+                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl;
+
+                                        ViewCellContainer viewCells;    
+                                        CollectViewCells(mRoot, false, viewCells);
+                        
+                                        char s[64];
+                                        sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
+                                        Exporter *exporter = Exporter::GetExporter(s);
+                                
+                                        if (exporter)
+                                        {
+                                                Debug << "vc size " << viewCells.size() << endl;
+                                                ViewCellContainer::const_iterator it, it_end = viewCells.end();
+                
+                                                for (it = viewCells.begin(); it != it_end; ++ it)
+                                                {
+                                                        exporter->ExportGeometry(objects);
+                                                        mViewCellsManager->ExportVcGeometry(exporter, *it);
+                                                }
+                                        
+                                                delete exporter;
+                                        }
+                                }
                         }
+
                 }
                 // merge candidate not valid, because one of the leaves was already
@@ -2740 +2814 @@
                 Debug << mergeStats << endl << endl;
         
+
         //TODO: should return sample contributions?
         return mergeStats.merged;
@@ -2836 +2911 @@
 
 
-float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2)
+float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2, bool useArea)
 {
         //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
@@ -2842 +2917 @@
         const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
 
-        const float area1 = vc1->GetArea() - leaf->mArea;
-        const float area2 = vc2->GetArea() + leaf->mArea;
-
-        const float cost1 = pvs1 * area1;
-        const float cost2 = pvs2 * area2;
+        float p1, p2;
+
+    if (useArea)
+        {
+                p1 = vc1->GetArea() - leaf->mProbability;
+                p2 = vc2->GetArea() + leaf->mProbability;
+        }
+        else
+        {
+                p1 = vc1->GetVolume() - leaf->mProbability;
+                p2 = vc2->GetVolume() + leaf->mProbability;
+        }
+
+        const float cost1 = pvs1 * p1;
+        const float cost2 = pvs2 * p2;
 
         return cost1 + cost2;
@@ -2860 +2945 @@
         vc2->GetPvs().AddPvs(*leaf->mPvs);
         
-        vc1->SetArea(vc1->GetArea() - leaf->mArea);
-        vc2->SetArea(vc2->GetArea() + leaf->mArea);
+        if (mUseAreaForPvs)
+        {
+                vc1->SetArea(vc1->GetArea() - leaf->mProbability);
+                vc2->SetArea(vc2->GetArea() + leaf->mProbability);
+        }
+        else
+        {
+                vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);
+                vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);
+        }
 
         /// add to second view cell
@@ -2890 +2983 @@
         BspViewCell *vc2 = leaf2->GetViewCell();
 
-        const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
-        const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
+        float cost1; 
+        float cost2; 
+
+        if (mUseAreaForPvs)
+        {
+                cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
+                cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
+        }
+        else
+        {
+                cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();
+                cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();
+        }
 
         const float oldCost = cost1 + cost2;
@@ -2900 +3004 @@
         // the view cell should not be empty after the shuffle
         if (vc1->mLeaves.size() > 1)
-                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
+                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2, mUseAreaForPvs);
         if (vc2->mLeaves.size() > 1)
-                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
+                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1, mUseAreaForPvs);
 
         // shuffling unsuccessful
@@ -2921 +3025 @@
         return true;
 }
+
 
 bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
@@ -2952 +3057 @@
 
 
-bool VspBspTree::CheckValid(const VspBspTraversalData &data) const
-{
-        return data.mPvs <= mMaxPvs;
-}
-
-
 void VspBspTree::PropagateUpValidity(BspNode *node)
 {
@@ -3019 +3118 @@
 }
 
+
 float BspMergeCandidate::GetCost(ViewCell *vc) const
 {
-        return vc->GetPvs().GetSize() * vc->GetArea();
-}
+        if (sUseArea)
+                return vc->GetPvs().GetSize() * vc->GetArea();
+
+        return vc->GetPvs().GetSize() * vc->GetVolume();
+}
+
 
 float BspMergeCandidate::GetLeaf1Cost() const
@@ -3030 +3134 @@
 }
 
+
 float BspMergeCandidate::GetLeaf2Cost() const
 {
@@ -3035 +3140 @@
         return GetCost(vc);
 }
+
 
 void BspMergeCandidate::EvalMergeCost()
@@ -3050 +3156 @@
         const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
 
-        const float newCost =
-                (float)newPvs * (vc1->GetArea() + vc2->GetArea());
+    const float newCost = sUseArea ? 
+                (float)newPvs * (vc1->GetArea() + vc2->GetArea()) :
+                (float)newPvs * (vc1->GetVolume() + vc2->GetVolume());
+
 
         if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -52 +52 @@
                 /// rays piercing this node
                 RayInfoContainer *mRays;
-                /// area of current node
-                float mArea;
+                /// the probability that this node contains view point
+                float mProbability;
                 /// geometry of node as induced by planes
                 BspNodeGeometry *mGeometry;
@@ -77 +77 @@
                 mRays(NULL),
                 mPvs(0),
-                mArea(0.0),
+                mProbability(0.0),
                 mGeometry(NULL),
                 mMaxCostMisses(0)
@@ -87 +87 @@
                                                         const int depth, 
                                                         RayInfoContainer *rays,
-                                                        int pvs,
-                                                        float area,
+                                                        const int pvs,
+                                                        const float p,
                                                         BspNodeGeometry *geom): 
                 mNode(node), 
@@ -95 +95 @@
                 mRays(rays),
                 mPvs(pvs),
-                mArea(area),
+                mProbability(p),
                 mGeometry(geom),
                 mMaxCostMisses(0)
@@ -109 +109 @@
                 mRays(rays),
                 mPvs(0),
-                mArea(0),
+                mProbability(0),
                 mGeometry(geom),
                 mMaxCostMisses(0)
@@ -119 +119 @@
                 {
 #if 1
-                        return mPvs * mArea;
+                        return mPvs * mProbability;
 #endif
 #if 0
@@ -128 +128 @@
 #endif
 #if 0
-                        return mArea * (float)mRays->size();
+                        return mProbabiliy * (float)mRays->size();
 #endif
                 }
@@ -190 +190 @@
                 @param viewCells returns the view cells 
         */
-        void CollectViewCells(ViewCellContainer &viewCells) const;
+        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
 
         /** A ray is cast possible intersecting the tree.
@@ -250 +250 @@
         /** Merges view cells according to some cost heuristics.
         */
-        int MergeViewCells(const VssRayContainer &rays);
+        int MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
         
         /** Refines view cells using shuffling, i.e., border leaves 
@@ -298 +298 @@
 
         void CollectViewCells(BspNode *root, 
+                                                  bool onlyValid, 
                                                   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.
@@ -339 +337 @@
         };
 
+        /** faster evaluation of split plane cost for kd axis aligned cells.
+        */
         float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
                                                                    const AxisAlignedBox3 &box,
                                                                    const int axis,
-                                                                   const float &position) const;
+                                                                   const float &position,
+                                                                   float &pFront,
+                                                                   float &pBack) const;
 
         /** Returns view cell corresponding to 
@@ -409 +411 @@
                                                  BspNodeGeometry &geomFront,
                                                  BspNodeGeometry &geomBack,
-                                                 float &areaFront,
-                                                 float &areaBack) const;
+                                                 float &pFront,
+                                                 float &pBack) const;
 
         /** Subdivide leaf.
@@ -464 +466 @@
                                                                  BspNodeGeometry **frontGeom,
                                                                  BspNodeGeometry **backGeom,
-                                                                 float &frontArea,
-                                                                 float &backArea,
-                                                                 bool useKdSplit);
+                                                                 float &pFront,
+                                                                 float &pBack,
+                                                                 const bool useKdSplit);
 
         /** Sorts split candidates for surface area heuristics for axis aligned splits.
@@ -482 +484 @@
                                                                   const int &axis,
                                                                   float &position);
-
-        /** Evaluates cost ratio for axis aligned splits.
-        */
-        /*float EvalCostRatio(const VspBspTraversalData &tData,
-                                                const AxisAlignedBox3 &box,
-                                                const int axis,
-                                                const float position,
-                                                int &raysBack,
-                                                int &raysFront,
-                                                int &pvsBack,
-                                                int &pvsFront);*/
 
         /** Selects an axis aligned split plane.
@@ -606 +597 @@
                                          BspViewCell *vc2) const;
 
-        /**
-                Checks if this traversal data corresponds to
-                a valid view space region.
-        */
-        bool CheckValid(const VspBspTraversalData &data) const;
-
+        
         /** Propagates valid flag up the tree.
         */
@@ -646 +632 @@
         /// maximal possible depth
         int mTermMaxDepth;
-        /// mininum area
-        float mTermMinArea;
+        /// mininum probability
+        float mTermMinProbability;
         /// mininum PVS
         int mTermMinPvs;
@@ -654 +640 @@
         /// minimal accumulated ray length
         float mTermMinAccRayLength;
+
+        ofstream mStats;
 
         //-- termination criteria for axis aligned split
@@ -686 +674 @@
         float mPvsFactor;
 
-        /// if area or accumulated ray lenght should be used for PVS heuristics
-        bool mPvsUseArea;
+        /// if area or volume should be used for PVS heuristics
+        bool mUseAreaForPvs;
         /// tolerance for polygon split
         float mEpsilon;
@@ -719 +707 @@
         bool mUseRaysForMerge;
         
-        /// maximal allowed pvs so that view cell is valid
-        int mMaxPvs;
-
-        float mMaxPvsRatio;
-
         /// View cell corresponding to the space outside the valid view space
         BspViewCell *mOutOfBoundsCell;
-
-        /// if invalid space should be shown
-        bool mShowInvalidSpace;
 
         int mCurrentViewCellsId;
@@ -797 +777 @@
         /// overall cost used to normalize cost ratio
         static float sOverallCost;
+        // if area or volume should be used for the merge heuristics
+        static bool sUseArea;
 
         /** Evaluates the merge costs of the leaves.

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -517 +517 @@
 {
   Mesh *mesh = new Mesh;
-  // add 6 vertices of the box
+  // add 8 vertices of the box
   int index = (int)mesh->mVertices.size();
   for (int i=0; i < 8; i++) {

trunk/VUT/GtpVisibilityPreprocessor/src/default.env

@@ -289 +289 @@
                 maxDepth                30
                 minPvs                  2
-                #minArea                0.0001
-                minArea                 0.000
+                #minProbability         0.0001
+                minProbabilty           0.000
                 maxRayContribution      0.005
                 maxCostRatio            0.9