Changeset 478

Timestamp:

12/22/05 18:32:39 (18 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (5 diffs)
• src/Environment.cpp (modified) (4 diffs)
• src/Preprocessor.cpp (modified) (1 diff)
• src/ViewCell.cpp (modified) (3 diffs)
• src/ViewCell.h (modified) (2 diffs)
• src/ViewCellBsp.cpp (modified) (4 diffs)
• src/ViewCellBsp.h (modified) (2 diffs)
• src/ViewCellsManager.cpp (modified) (17 diffs)
• src/ViewCellsManager.h (modified) (3 diffs)
• src/VspBspTree.cpp (modified) (13 diffs)
• src/VspBspTree.h (modified) (7 diffs)
• src/VspKdTree.cpp (modified) (4 diffs)

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
 }
 
@@ -155 +155 @@
         maxViewCells 100
         
-        PostProcessing {
+        PostProcess {
                 minPvsDif 100
                 minPvs 10
@@ -240 +240 @@
         
         # maximal tested rays for split cost heuristics
-        maxTests 1000
+        maxTests 10000
         
         # factors for evaluating split plane costs
@@ -261 +261 @@
                 #maxAccRayLength        100
                 
+                maxViewCells            1500
+                
                 # used for pvs criterium
                 ct_div_ci 0.0
@@ -283 +285 @@
                 exportRays true
                 exportGeometry false
+        }
+        
+        PostProcess {
+                maxCostRatio 5000000
+                minViewCells 1000
+                maxPvsSize   50000
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1187 +1187 @@
                  "bspTree");
 
-  RegisterOption("ViewCells.PostProcessing.samples",
+  RegisterOption("ViewCells.PostProcess.samples",
           optInt,
-          "-bsp_postprocessing_samples=",
+          "-view_cells_postprocess_samples=",
           "200000");
 
@@ -1207 +1207 @@
                  "0");
 
-  RegisterOption("ViewCells.PostProcessing.minPvsDif",
+  RegisterOption("ViewCells.PostProcess.minPvsDif",
                  optInt,
-                 "-view_cells_post_processing_min_pvs_dif",
+                 "-view_cells_post_process_min_pvs_dif",
                  "10");
 
-  RegisterOption("ViewCells.PostProcessing.maxPvs",
+  RegisterOption("ViewCells.PostProcess.maxPvs",
                  optInt,
-                 "-view_cells_post_processing_max_pvs",
+                 "-view_cells_post_process_max_pvs",
                  "300");
 
-  RegisterOption("ViewCells.PostProcessing.minPvs",
+  RegisterOption("ViewCells.PostProcess.minPvs",
                  optString,
-                 "-view_cells_post_processing_min_pvs",
+                 "-view_cells_post_process_min_pvs",
                  "10");
 
@@ -1667 +1667 @@
                         "1.5");
 
+        RegisterOption("VspBspTree.Termination.maxViewCells",
+                        optInt,
+                        "-vsp_bsp_term_axis_aligned_max_view_cells=",
+                        "1000");
+
         RegisterOption("VspBspTree.Termination.maxCostRatio",
                 optFloat,
@@ -1750 +1755 @@
         RegisterOption("VspBspTree.Factor.pvs", optFloat, "-vsp_bsp_factor_pvs=", "1.0");
 
+        RegisterOption("VspBspTree.PostProcess.maxCostRatio",
+                        optFloat,
+                        "-vsp_bsp_post_process_max_cost_ratio=",
+                        "1.5");
+
+        RegisterOption("VspBspTree.PostProcess.minViewCells", 
+                optInt, 
+                "vsp_bsp_term_post_process_min_view_cells=", 
+                "1000");
+
+        RegisterOption("VspBspTree.PostProcess.maxPvsSize", 
+                optInt, 
+                "vsp_bsp_term_post_process_max_pvs_size=", 
+                "100");
+        
         //////////////////////////////////////////////////////////////////////////////////
 }

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -231 +231 @@
         int visSamples = 0;
 
-        environment->GetIntValue("ViewCells.PostProcessing.samples", postProcessSamples);
+        environment->GetIntValue("ViewCells.PostProcess.samples", postProcessSamples);
         environment->GetIntValue("ViewCells.Visualization.samples", visSamples);
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -7 +7 @@
 #include <iomanip>
 
-ViewCell::ViewCell(): MeshInstance(NULL), mPiercingRays(0)
+ViewCell::ViewCell(): 
+MeshInstance(NULL), 
+mPiercingRays(0),
+mArea(0),
+mVolume(0)
 {
 }
 
-ViewCell::ViewCell(Mesh *mesh): MeshInstance(mesh), mPiercingRays(0)
+ViewCell::ViewCell(Mesh *mesh): 
+MeshInstance(mesh), 
+mPiercingRays(0),
+mArea(0),
+mVolume(0)
 {
 }
@@ -35 +43 @@
 }
 
+
 float ViewCell::GetVolume() const
 {
@@ -40 +49 @@
 }
 
+
 void ViewCell::SetVolume(float volume) 
 {
         mVolume = volume;
 }
+
+
+float ViewCell::GetArea() const
+{
+        return mArea;
+}
+
+
+void ViewCell::SetArea(float area) 
+{
+        mArea = area;
+}
+
 
 /************************************************************************/

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -45 +45 @@
         /** Returns volume of the view cell.
         */
-        virtual float GetVolume() const;
+        float GetVolume() const;
 
-        /** Sets volume of the view cell.
+        /** Returns area of the view cell.
         */
-        void SetVolume(float size);
+        float GetArea() const;
+
+        /** Sets the volume of the view cell.
+        */
+        void SetVolume(float volume);
+        
+        /** Sets the area of the view cell.
+        */
+        void SetArea(float area);
 
         /// Ray set description of the rays passing through this node.
@@ -63 +71 @@
 
         float mVolume;
+        float mArea;
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -1148 +1148 @@
         if (!data.mPolygons->empty())
                 {
-                        Polygon3 *nextPoly = (*data.mPolygons)[(int)RandomValue(0, (int)data.mPolygons->size() - 1)];
+                        Polygon3 *nextPoly = 
+                                (*data.mPolygons)[(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1))];
                         return nextPoly->GetSupportingPlane();
                 }
@@ -1175 +1176 @@
 }
 
+
+Plane3 BspTree::ChooseCandidatePlane(const BoundedRayContainer &rays) const
+{       return Plane3();
+        /*const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+        
+        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
+        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
+
+        const Vector3 pt = (maxPt + minPt) * 0.5;
+        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
+
+        return Plane3(normal, pt);*/
+}
+
+Plane3 BspTree::ChooseCandidatePlane2(const BoundedRayContainer &rays) const
+{       return Plane3();
+        /*Vector3 pt[3];
+        
+        int idx[3];
+        int cmaxT = 0;
+        int cminT = 0;
+        bool chooseMin = false;
+
+        for (int j = 0; j < 3; ++ j)
+        {
+                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
+                        
+                if (idx[j] >= (int)rays.size())
+                {
+                        idx[j] -= (int)rays.size();
+                                
+                        chooseMin = (cminT < 2);
+                }
+                else
+                        chooseMin = (cmaxT < 2);
+
+                RayInfo rayInf = rays[idx[j]];
+                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
+        }       
+
+        return Plane3(pt[0], pt[1], pt[2]);*/
+}
+
+Plane3 BspTree::ChooseCandidatePlane3(const BoundedRayContainer &rays) const
+{       return Plane3();/*
+        Vector3 pt[3];
+        
+        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+        // check if rays different
+        if (idx1 == idx2)
+                idx2 = (idx2 + 1) % (int)rays.size();
+
+        const RayInfo ray1 = rays[idx1];
+        const RayInfo ray2 = rays[idx2];
+
+        // normal vector of the plane parallel to both lines
+        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
+
+        // vector from line 1 to line 2
+        const Vector3 vd = (ray2.ExtrapOrigin() - ray1.ExtrapOrigin());
+        
+        // project vector on normal to get distance
+        const float dist = DotProd(vd, norm);
+
+        // point on plane lies halfway between the two planes
+        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
+
+        return Plane3(norm, planePt);*/
+}
+
+
 Plane3 BspTree::SelectPlaneHeuristics(BspLeaf *leaf, BspTraversalData &data)
 {
         float lowestCost = MAX_FLOAT;
         Plane3 bestPlane;
+        // intermediate plane
         Plane3 plane;
 
-        int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
-        
-        int candidateIdx = limit - 1;
-
+        const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
+        int maxIdx = (int)data.mPolygons->size();
+        
         for (int i = 0; i < limit; ++ i)
         {
-                candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons);
+                // assure that no index is taken twice
+                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
+                //Debug << "current Idx: " << maxIdx << " cand idx " << candidateIdx << endl;
                 
                 Polygon3 *poly = (*data.mPolygons)[candidateIdx];
+
+                // swap candidate to the end to avoid testing same plane
+                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
+        
+                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
+
                 // evaluate current candidate
                 const float candidateCost = 
@@ -1201 +1283 @@
         }
         
-        //Debug << "lowest: " << lowestCost << endl;
-
         //-- choose candidate planes extracted from rays
-        // we currently use two methods
-        // 1) take 3 ray endpoints, where two are minimum and one a maximum
-        //    point or the other way round
-        // 2) take plane normal as plane normal and the midpoint of the ray.
-        //    PROBLEM: does not resemble any point where visibility is likely to change
-        const BoundedRayContainer *rays = data.mRays;
-
-        for (int i = 0; i < mMaxRayCandidates / 2; ++ i)
-        {
-                candidateIdx = (int)RandomValue(0, (int)rays->size() - 1);
-                BoundedRay *bRay = (*rays)[candidateIdx];
-
-                Ray *ray = bRay->mRay;
-                                                
-                const Vector3 minPt = ray->Extrap(bRay->mMinT);
-                const Vector3 maxPt = ray->Extrap(bRay->mMaxT);
-
-                const Vector3 pt = (maxPt + minPt) * 0.5;
-
-                const Vector3 normal = ray->GetDir();
-                        
-                plane = Plane3(normal, pt);
-        
+        //-- different methods are available
+        for (int i = 0; i < mMaxRayCandidates; ++ i)
+        {
+                plane = ChooseCandidatePlane3(*data.mRays);
                 const float candidateCost = SplitPlaneCost(plane, data);
 
                 if (candidateCost < lowestCost)
                 {
-                        bestPlane = plane;
-                        
+                        bestPlane = plane;      
                         lowestCost = candidateCost;
                 }
         }
-
-        //Debug << "lowest: " << lowestCost << endl;
-        for (int i = 0; i < mMaxRayCandidates / 2; ++ i)
-        {
-                Vector3 pt[3];
-                int idx[3];
-                int cmaxT = 0;
-                int cminT = 0;
-                bool chooseMin = false;
-
-                for (int j = 0; j < 3; j ++)
-                {
-                        idx[j] = (int)RandomValue(0, (int)rays->size() * 2 - 1);
-                                
-                        if (idx[j] >= (int)rays->size())
-                        {
-                                idx[j] -= (int)rays->size();
-                                
-                                chooseMin = (cminT < 2);
-                        }
-                        else
-                                chooseMin = (cmaxT < 2);
-
-                        BoundedRay *bRay = (*rays)[idx[j]];
-                        pt[j] = chooseMin ? bRay->mRay->Extrap(bRay->mMinT) : 
-                                                                bRay->mRay->Extrap(bRay->mMaxT);
-                }       
-                        
-                plane = Plane3(pt[0], pt[1], pt[2]);
-
-                const float candidateCost = SplitPlaneCost(plane, data);
-
-                if (candidateCost < lowestCost)
-                {
-                        //Debug << "choose ray plane 2: " << candidateCost << endl;
-                        bestPlane = plane;
-                        
-                        lowestCost = candidateCost;
-                }
-        }       
 
 #ifdef _DEBUG
         Debug << "plane lowest cost: " << lowestCost << endl;
 #endif
+
         return bestPlane;
 }
 
-int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
-{
-        const int candidateIdx = (int)RandomValue(0, currentIdx --);
-
-        // swap candidates to avoid testing same plane 2 times
-        std::swap(polys[currentIdx], polys[candidateIdx]);
-        
-        return currentIdx;
-        //return (int)RandomValue(0, (int)polys.size() - 1);
-}
 
 float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
@@ -1331 +1342 @@
                 limit = (int)polys.size();
         }
-        
 
         for (int i = 0; i < limit; ++ i)
         {
-                const int testIdx = useRand ? (int)RandomValue(0, limit - 1) : i;
+                const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i;
 
                 Polygon3 *poly = polys[testIdx];

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -586 +586 @@
                                                 PolygonContainer *backPolys);
 
+        /** Take 3 ray endpoints, where two are minimum and one a maximum
+                point or the other way round.
+        */
+        Plane3 ChooseCandidatePlane(const BoundedRayContainer &rays) const;
+
+        /** Take plane normal as plane normal and the midpoint of the ray.
+                PROBLEM: does not resemble any point where visibility is likely to change
+        */
+        Plane3 ChooseCandidatePlane2(const BoundedRayContainer &rays) const;
+
+        /** Fit the plane between the two lines so that the plane has equal shortest 
+                distance to both lines.
+        */
+        Plane3 ChooseCandidatePlane3(const BoundedRayContainer &rays) const;
+
         /** Selects the split plane in order to construct a tree with
                 certain characteristics (e.g., balanced tree, least splits, 
@@ -619 +634 @@
         */
         int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
-
-        /** returns next candidate index and reorders polygons so no candidate is chosen two times
-                @param the current candidate index
-                @param max the range of candidates
-        */
-        int GetNextCandidateIdx(int currentIdx, PolygonContainer &polys);
 
         /** Helper function which extracts a view cell on the front and the back

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -22 +22 @@
 {
         // post processing stuff
-        environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);
-        environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);
-        environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);
+        environment->GetIntValue("ViewCells.PostProcess.minPvsDif", mMinPvsDif);
+        environment->GetIntValue("ViewCells.PostProcess.minPvs", mMinPvs);
+        environment->GetIntValue("ViewCells.PostProcess.maxPvs", mMaxPvs);
 }
 
@@ -34 +34 @@
 {
         // post processing stuff
-        environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);
-        environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);
-        environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);
+        environment->GetIntValue("ViewCells.PostProcess.minPvsDif", mMinPvsDif);
+        environment->GetIntValue("ViewCells.PostProcess.minPvs", mMinPvs);
+        environment->GetIntValue("ViewCells.PostProcess.maxPvs", mMaxPvs);
 }
 
@@ -75 +75 @@
 {
         mViewCells.push_back(viewCell);
+}
+
+float ViewCellsManager::GetArea(ViewCell *viewCell) const
+{
+        return viewCell->GetArea();
+}
+
+
+float ViewCellsManager::GetVolume(ViewCell *viewCell) const
+{
+        return viewCell->GetVolume();
 }
 
@@ -282 +293 @@
 
 
-float ViewCellsManager::GetVolume(ViewCell *viewCell) const
-{
-        return viewCell->GetVolume();
-}
-
-
-float ViewCellsManager::GetArea(ViewCell *viewCell) const
-{
-        return 0.0f;
-}
-
-
 float ViewCellsManager::GetAccVcArea()
 {
@@ -390 +389 @@
 
         return sampleContributions;
-}
-
-float BspViewCellsManager::GetArea(ViewCell *viewCell) const
-{
-        PolygonContainer geom;
-
-        // compute view cell area
-        mBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(viewCell), geom);
-        
-        const float area = Polygon3::GetArea(geom);
-        CLEAR_CONTAINER(geom);
-
-        return area;
 }
 
@@ -656 +642 @@
         //-- some rays for output
         const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
+        
         cout << "visualization using " << mVisualizationSamples << " samples" << endl;
         Debug << "\nOutput view cells: " << endl;
-
-        if (1)
-        {
-                //-- some random view cells and rays for output
-                vector<BspLeaf *> vspBspLeaves;
-
-                for (int i = 0; i < leafOut; ++ i)
-                        vspBspLeaves.push_back(mBspTree->GetRandomLeaf());      
-                
-                for (int i = 0; i < (int)vspBspLeaves.size(); ++ i)
-                {
-                        VssRayContainer vcRays;
-                        cout << "creating output for view cell " << i << " ... ";
-
-                        // check whether we can add the current ray to the output rays
-                        for (int k = 0; k < raysOut; ++ k) 
+        
+        // sort view cells to get largest view cells
+#if 0
+        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
+#endif
+        int limit = min(leafOut, (int)mViewCells.size()); 
+                
+        for (int i = 0; i < limit; ++ i)
+        {
+                cout << "creating output for view cell " << i << " ... ";
+                VssRayContainer vcRays;
+                Intersectable::NewMail();
+#if 0
+                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
+#else
+                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[Random((int)mViewCells.size())]);
+#endif
+                cout << "creating output for view cell " << i << " ... ";
+
+#if 0
+                // check whether we can add the current ray to the output rays
+                for (int k = 0; k < raysOut; ++ k) 
+                {
+                        BspRay *ray = mBspRays[k];
+                        for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
                         {
-                                BspRay *ray = mBspRays[k];
-
-                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
-                                {
-                                        BspLeaf *leaf = ray->intersections[j].mLeaf;
-
-                                        if (vspBspLeaves[i]->GetViewCell() == leaf->GetViewCell()) 
-                                        {
-                                                vcRays.push_back(ray->vssRay);
-                                        }
-                                }
+                                BspLeaf *leaf = ray->intersections[j].mLeaf;
+                                if (vc == leaf->GetViewCell()) 
+                                        vcRays.push_back(ray->vssRay);
                         }
-
-                        Intersectable::NewMail();
-
-                        BspViewCell *vc = dynamic_cast<BspViewCell *>
-                                (vspBspLeaves[i]->GetViewCell());
-
-                        //bspLeaves[j]->Mail();
-                        char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
-
-                        Exporter *exporter = Exporter::GetExporter(s);
-                        exporter->SetFilled();
-
-                        ObjectPvsMap::iterator it = vc->GetPvs().mEntries.begin();
-
-                        exporter->SetWireframe();
-                        //exporter->SetFilled();
-
-                        Material m;//= RandomMaterial();
-                        m.mDiffuseColor = RgbColor(0, 1, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        if (vc->GetMesh())
-                                exporter->ExportViewCell(vc);
-                        else
+                }
+#endif
+                //bspLeaves[j]->Mail();
+                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
+
+                Exporter *exporter = Exporter::GetExporter(s);
+                        
+                exporter->SetWireframe();
+
+                Material m;//= RandomMaterial();
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+
+                if (vc->GetMesh())
+                        exporter->ExportViewCell(vc);
+                else
+                {
+                        PolygonContainer vcGeom;
+                        
+                        //-- export view cell
+                        mBspTree->ConstructGeometry(vc, vcGeom);
+                        exporter->ExportPolygons(vcGeom);
+                        CLEAR_CONTAINER(vcGeom);
+                }
+                        
+                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
+                          << ", piercing rays=" << (int)vcRays.size() << endl;
+
+                        
+                // export rays piercing this view cell
+#if 0
+                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
+#else
+                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
+                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
+                        exporter->ExportRays((*lit)->mVssRays);
+#endif
+                m.mDiffuseColor = RgbColor(1, 0, 0);
+                exporter->SetForcedMaterial(m);
+
+                ObjectPvsMap::const_iterator it,
+                        it_end = vc->GetPvs().mEntries.end();
+
+                exporter->SetFilled();
+
+                // output PVS of view cell
+                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
+                {
+                        Intersectable *intersect = (*it).first;
+
+                        if (!intersect->Mailed())
                         {
-                                PolygonContainer vcGeom;
-
-                                // export view cell geometry
-                                mBspTree->ConstructGeometry(vc, vcGeom);
-                                exporter->ExportPolygons(vcGeom);
-                                CLEAR_CONTAINER(vcGeom);
-                        }
-
-                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-                                        << ", piercing rays=" << (int)vcRays.size() << endl;
-
-                        // export rays piercing this view cell
-                        if (exportRays)
-                        {
-                                //exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
-                                exporter->ExportRays(vspBspLeaves[i]->mVssRays, RgbColor(1, 1, 1));
-                        }
-
-                        m.mDiffuseColor = RgbColor(0, 1, 1);
-                        exporter->SetForcedMaterial(m);
-
-                        //exporter->SetWireframe();
-                        exporter->SetFilled();
-
-                        // output PVS of view cell
-                        for (; it != vc->GetPvs().mEntries.end(); ++ it) 
-                        {
-                                Intersectable *intersect = (*it).first;
-                                if (!intersect->Mailed())
-                                {
-                                        exporter->ExportIntersectable(intersect);
-                                        intersect->Mail();
-                                }                       
-                        }
-                        Debug << "here1 exportgeom: " << exportGeometry << endl;
-                        // output rest of the objects
-                        if (exportGeometry)
-                        {
-                                Material m;//= RandomMaterial();
-                                m.mDiffuseColor = RgbColor(0, 0, 1);
+                                Material m = RandomMaterial();
                                 exporter->SetForcedMaterial(m);
 
-                                for (int j = 0; j < objects.size(); ++ j)
-                                        if (!objects[j]->Mailed())
-                                        {
-                                                exporter->SetForcedMaterial(m);
-                                                exporter->ExportIntersectable(objects[j]);
-                                                objects[j]->Mail();
-                                        }
-                        }
-                        DEL_PTR(exporter);
-                        cout << "finished" << endl;
-                }
-        }
-        else
-        {
-                ViewCellContainer viewCells;
-
-                mBspTree->CollectViewCells(viewCells);
-                stable_sort(viewCells.begin(), viewCells.end(), vc_gt);
-
-                int limit = min(leafOut, (int)viewCells.size()); 
-                
-                for (int i = 0; i < limit; ++ i)
-                {
-                        cout << "creating output for view cell " << i << " ... ";
-                        VssRayContainer vcRays;
-            Intersectable::NewMail();
-                        BspViewCell *vc = dynamic_cast<BspViewCell *>(viewCells[i]);
-
-                        cout << "creating output for view cell " << i << " ... ";
-
-                        // check whether we can add the current ray to the output rays
-                        for (int k = 0; k < raysOut; ++ k) 
-                        {
-                                BspRay *ray = mBspRays[k];
-
-                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
-                                {
-                                        BspLeaf *leaf = ray->intersections[j].mLeaf;
-
-                                        if (vc == leaf->GetViewCell()) 
-                                        {
-                                                vcRays.push_back(ray->vssRay);
-                                        }
-                                }
-                        }
-
-                        //bspLeaves[j]->Mail();
-                        char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
-
-                        Exporter *exporter = Exporter::GetExporter(s);
-                        
-                        exporter->SetWireframe();
-
-                        Material m;//= RandomMaterial();
-                        m.mDiffuseColor = RgbColor(0, 1, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        if (vc->GetMesh())
-                                exporter->ExportViewCell(vc);
-                        else
-                        {
-                                PolygonContainer vcGeom;
-                                // export view cell
-                                mBspTree->ConstructGeometry(vc, vcGeom);
-                                exporter->ExportPolygons(vcGeom);
-                                CLEAR_CONTAINER(vcGeom);
-                        }
-
-                        
-                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-                                  << ", piercing rays=" << (int)vcRays.size() << endl;
-
-                        
-                        // export rays piercing this view cell
-                        exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
-        
-                        m.mDiffuseColor = RgbColor(1, 0, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        ObjectPvsMap::const_iterator it,
-                                it_end = vc->GetPvs().mEntries.end();
-
-                        // output PVS of view cell
-                        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
-                        {
-                                Intersectable *intersect = (*it).first;
-
-                                if (!intersect->Mailed())
-                                {
-                                        Material m = RandomMaterial();
-                        
-                                        exporter->SetForcedMaterial(m);
-
-                                        exporter->ExportIntersectable(intersect);
-                                        intersect->Mail();
-                                }                       
-                        }
+                                exporter->ExportIntersectable(intersect);
+                                intersect->Mail();
+                        }                       
+                }
                                 
-                        DEL_PTR(exporter);
-                        cout << "finished" << endl;
-                }
+                DEL_PTR(exporter);
+                cout << "finished" << endl;
         }
 
@@ -864 +746 @@
 {
         BspViewCell *viewCell = 
-                dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(), *back->GetViewCell()));
+                dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(), 
+                                                                                                   *back->GetViewCell()));
         
         if (!viewCell)
@@ -1207 +1090 @@
 
 
-
 /**********************************************************************/
 /*                   VspKdViewCellsManager implementation             */
@@ -1436 +1318 @@
 mVspBspTree(vspBspTree)
 {
+        mVspBspTree->SetViewCellsManager(this);
 }
 
@@ -1468 +1351 @@
 }
 
-
 float VspBspViewCellsManager::GetRendercost(ViewCell *viewCell, 
                                                                                         float objRendercost) const
@@ -1511 +1393 @@
         mVspBspTree->CollectViewCells(mViewCells);
         mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);
-        
+
         Debug << mVspBspTree->GetStatistics() << endl;
         
@@ -1551 +1433 @@
                                                                                 const VssRayContainer &rays)
 {
+        if (!ViewCellsConstructed())
+        {
+                Debug << "view cells not constructed" << endl;
+                return 0;
+        }
+
         if (mBspRays.empty())
                 ConstructBspRays(rays, mConstructionSamples);
-        
-        if (!ViewCellsConstructed())
-        {
-                Debug << "view cells not constructed" << endl;
-                return 0;
-        }
 
         //-- post processing of bsp view cells
@@ -1575 +1457 @@
                         //exporter->SetWireframe();
                         exporter->SetFilled();
-                        exporter->ExportBspViewCellPartition(*mVspBspTree, mViewCellsStats.maxPvs);
-                                
+                        //exporter->ExportBspViewCellPartition(*mVspBspTree, mViewCellsStats.maxPvs);
+                        exporter->ExportBspViewCellPartition(*mVspBspTree);
+
                         if (0)
                         {
@@ -1605 +1488 @@
         vector<BspIntersection>::const_iterator iit;
 
+        if (0)
         for (int i = 0; i < (int)mBspRays.size(); ++ i)
         {  
@@ -1633 +1517 @@
                 }
         }
+        else
+        {
+                merged = mVspBspTree->MergeLeaves();
+        }
 
         //-- stats and visualizations
@@ -1668 +1556 @@
         if (1) // export view cells
         {
-                cout << "exporting view cells after merge ... ";
+                cout << "exporting view cells after post process ... ";
                 Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
 
                 if (exporter)
                 {
-                        exporter->ExportBspViewCellPartition(*mVspBspTree, mViewCellsStats.maxPvs);
+                        //exporter->ExportBspViewCellPartition(*mVspBspTree, mViewCellsStats.maxPvs);
+                        exporter->ExportBspViewCellPartition(*mVspBspTree);
                         delete exporter;
                 }
@@ -1751 +1640 @@
         //-- some rays for output
         const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
+        
         cout << "visualization using " << mVisualizationSamples << " samples" << endl;
         Debug << "\nOutput view cells: " << endl;
-
-        if (1)
-        {
-                //-- some random view cells and rays for output
-                vector<BspLeaf *> vspBspLeaves;
-
-                for (int i = 0; i < leafOut; ++ i)
-                        vspBspLeaves.push_back(mVspBspTree->GetRandomLeaf());   
-                
-                for (int i = 0; i < (int)vspBspLeaves.size(); ++ i)
-                {
-                        VssRayContainer vcRays;
-                        cout << "creating output for view cell " << i << " ... ";
-
-                        // check whether we can add the current ray to the output rays
-                        for (int k = 0; k < raysOut; ++ k) 
+        
+        // sort view cells to get largest view cells
+#if 0
+        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
+#endif
+        int limit = min(leafOut, (int)mViewCells.size()); 
+                
+        for (int i = 0; i < limit; ++ i)
+        {
+                cout << "creating output for view cell " << i << " ... ";
+                VssRayContainer vcRays;
+           Intersectable::NewMail();
+#if 0
+                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
+#else
+                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[Random((int)mViewCells.size())]);
+#endif
+                cout << "creating output for view cell " << i << " ... ";
+
+#if 0
+                // check whether we can add the current ray to the output rays
+                for (int k = 0; k < raysOut; ++ k) 
+                {
+                        BspRay *ray = mBspRays[k];
+                        for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
                         {
-                                BspRay *ray = mBspRays[k];
-
-                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
-                                {
-                                        BspLeaf *leaf = ray->intersections[j].mLeaf;
-
-                                        if (vspBspLeaves[i]->GetViewCell() == leaf->GetViewCell()) 
-                                        {
-                                                vcRays.push_back(ray->vssRay);
-                                        }
-                                }
+                                BspLeaf *leaf = ray->intersections[j].mLeaf;
+                                if (vc == leaf->GetViewCell()) 
+                                        vcRays.push_back(ray->vssRay);
                         }
-
-                        Intersectable::NewMail();
-
-                        BspViewCell *vc = dynamic_cast<BspViewCell *>
-                                (vspBspLeaves[i]->GetViewCell());
-
-                        //bspLeaves[j]->Mail();
-                        char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
-
-                        Exporter *exporter = Exporter::GetExporter(s);
-                        exporter->SetFilled();
-
-                        ObjectPvsMap::iterator it = vc->GetPvs().mEntries.begin();
-
-                        exporter->SetWireframe();
-                        //exporter->SetFilled();
-
-                        Material m;//= RandomMaterial();
-                        m.mDiffuseColor = RgbColor(0, 1, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        if (vc->GetMesh())
-                                exporter->ExportViewCell(vc);
-                        else
+                }
+#endif
+                //bspLeaves[j]->Mail();
+                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
+
+                Exporter *exporter = Exporter::GetExporter(s);
+                        
+                exporter->SetWireframe();
+
+                Material m;//= RandomMaterial();
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+
+                if (vc->GetMesh())
+                        exporter->ExportViewCell(vc);
+                else
+                {
+                        PolygonContainer vcGeom;
+                        // export view cell
+                        mVspBspTree->ConstructGeometry(vc, vcGeom);
+                        exporter->ExportPolygons(vcGeom);
+                        CLEAR_CONTAINER(vcGeom);
+                }
+                        
+                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
+                          << ", piercing rays=" << (int)vcRays.size() << endl;
+
+                        
+                // export rays piercing this view cell
+#if 0
+                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
+#else
+                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
+                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
+                        exporter->ExportRays((*lit)->mVssRays);
+#endif
+                m.mDiffuseColor = RgbColor(1, 0, 0);
+                exporter->SetForcedMaterial(m);
+
+                ObjectPvsMap::const_iterator it,
+                        it_end = vc->GetPvs().mEntries.end();
+
+                exporter->SetFilled();
+
+                // output PVS of view cell
+                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
+                {
+                        Intersectable *intersect = (*it).first;
+
+                        if (!intersect->Mailed())
                         {
-                                PolygonContainer vcGeom;
-
-                                // export view cell geometry
-                                mVspBspTree->ConstructGeometry(vc, vcGeom);
-                                exporter->ExportPolygons(vcGeom);
-                                CLEAR_CONTAINER(vcGeom);
-                        }
-
-                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-                                        << ", piercing rays=" << (int)vcRays.size() << endl;
-
-                        // export rays piercing this view cell
-                        if (exportRays)
-                        {
-                                //exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
-                                exporter->ExportRays(vspBspLeaves[i]->mVssRays, RgbColor(1, 1, 1));
-                        }
-
-                        m.mDiffuseColor = RgbColor(0, 1, 1);
-                        exporter->SetForcedMaterial(m);
-
-                        //exporter->SetWireframe();
-                        exporter->SetFilled();
-
-                        // output PVS of view cell
-                        for (; it != vc->GetPvs().mEntries.end(); ++ it) 
-                        {
-                                Intersectable *intersect = (*it).first;
-                                if (!intersect->Mailed())
-                                {
-                                        exporter->ExportIntersectable(intersect);
-                                        intersect->Mail();
-                                }                       
-                        }
-                        Debug << "here1 exportgeom: " << exportGeometry << endl;
-                        // output rest of the objects
-                        if (exportGeometry)
-                        {
-                                Material m;//= RandomMaterial();
-                                m.mDiffuseColor = RgbColor(0, 0, 1);
+                                Material m = RandomMaterial();
                                 exporter->SetForcedMaterial(m);
 
-                                for (int j = 0; j < objects.size(); ++ j)
-                                        if (!objects[j]->Mailed())
-                                        {
-                                                exporter->SetForcedMaterial(m);
-                                                exporter->ExportIntersectable(objects[j]);
-                                                objects[j]->Mail();
-                                        }
-                        }
-                        DEL_PTR(exporter);
-                        cout << "finished" << endl;
-                }
-        }
-        else
-        {
-                ViewCellContainer viewCells;
-
-                mVspBspTree->CollectViewCells(viewCells);
-                stable_sort(viewCells.begin(), viewCells.end(), vc_gt);
-
-                int limit = min(leafOut, (int)viewCells.size()); 
-                
-                for (int i = 0; i < limit; ++ i)
-                {
-                        cout << "creating output for view cell " << i << " ... ";
-                        VssRayContainer vcRays;
-            Intersectable::NewMail();
-                        BspViewCell *vc = dynamic_cast<BspViewCell *>(viewCells[i]);
-
-                        cout << "creating output for view cell " << i << " ... ";
-
-                        // check whether we can add the current ray to the output rays
-                        for (int k = 0; k < raysOut; ++ k) 
-                        {
-                                BspRay *ray = mBspRays[k];
-
-                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
-                                {
-                                        BspLeaf *leaf = ray->intersections[j].mLeaf;
-
-                                        if (vc == leaf->GetViewCell()) 
-                                        {
-                                                vcRays.push_back(ray->vssRay);
-                                        }
-                                }
-                        }
-
-                        //bspLeaves[j]->Mail();
-                        char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
-
-                        Exporter *exporter = Exporter::GetExporter(s);
-                        
-                        exporter->SetWireframe();
-
-                        Material m;//= RandomMaterial();
-                        m.mDiffuseColor = RgbColor(0, 1, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        if (vc->GetMesh())
-                                exporter->ExportViewCell(vc);
-                        else
-                        {
-                                PolygonContainer vcGeom;
-                                // export view cell
-                                mVspBspTree->ConstructGeometry(vc, vcGeom);
-                                exporter->ExportPolygons(vcGeom);
-                                CLEAR_CONTAINER(vcGeom);
-                        }
-
-                        
-                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-                                  << ", piercing rays=" << (int)vcRays.size() << endl;
-
-                        
-                        // export rays piercing this view cell
-                        exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
-        
-                        m.mDiffuseColor = RgbColor(1, 0, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        ObjectPvsMap::const_iterator it,
-                                it_end = vc->GetPvs().mEntries.end();
-
-                        // output PVS of view cell
-                        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
-                        {
-                                Intersectable *intersect = (*it).first;
-
-                                if (!intersect->Mailed())
-                                {
-                                        Material m = RandomMaterial();
-                        
-                                        exporter->SetForcedMaterial(m);
-
-                                        exporter->ExportIntersectable(intersect);
-                                        intersect->Mail();
-                                }                       
-                        }
+                                exporter->ExportIntersectable(intersect);
+                                intersect->Mail();
+                        }                       
+                }
                                 
-                        DEL_PTR(exporter);
-                        cout << "finished" << endl;
-                }
+                DEL_PTR(exporter);
+                cout << "finished" << endl;
         }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -198 +198 @@
   /** Returns area of one view cell.
   */
-  float GetArea(ViewCell *viewCell) const;
+  virtual float GetArea(ViewCell *viewCell) const;
 
   /** Returns volume of view cells.
   */
-  float GetVolume(ViewCell *viewCell) const;
+  virtual float GetVolume(ViewCell *viewCell) const;
 
   virtual AxisAlignedBox3 GetSceneBbox() const = 0;
@@ -273 +273 @@
         float GetRendercost(ViewCell *viewCell, float objRendercost) const;
 
-        float GetArea(ViewCell *viewCell) const;
-
         AxisAlignedBox3 GetSceneBbox() const;
 
@@ -320 +318 @@
                                   AxisAlignedBox3 *sceneBbox);
 
-  int CastLineSegment(const Vector3 &origin,
-                                          const Vector3 &termination,
-                                          ViewCellContainer &viewcells
-                                          ) ;
+        int CastLineSegment(const Vector3 &origin,
+                                                const Vector3 &termination,
+                                                ViewCellContainer &viewcells);
 
         int PostProcess(const ObjectContainer &objects, 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ +1 @@
+#include <stack>
+#include <time.h>
+#include <iomanip>
+
 #include "Plane3.h"
 #include "VspBspTree.h"
@@ -8 +12 @@
 #include "Ray.h"
 #include "AxisAlignedBox3.h"
-#include <stack>
-#include <time.h>
-#include <iomanip>
 #include "Exporter.h"
 #include "Plane3.h"
 #include "ViewCellBsp.h"
+#include "ViewCellsManager.h"
+
 
 //-- static members
@@ -30 +33 @@
 int VspBspTree::sFrontAndBackId = 0;
 
+float BspMergeCandidate::sOverallCost = Limits::Small;
 
 /****************************************************************/
@@ -38 +42 @@
 mRoot(NULL),
 mPvsUseArea(true),
-mCostNormalizer(Limits::Small)
+mCostNormalizer(Limits::Small),
+mViewCellsManager(NULL),
+mStoreRays(true)
 {
         mRootCell = new BspViewCell();
@@ -75 +81 @@
         environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
 
-        // maximum number of view cells
-        environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
-
-        //--
+        // maximum and minimum number of view cells
+        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
+        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
+        environment->GetIntValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
+
+
+        //-- debug output
         Debug << "******* VSP BSP options ******** " << endl;
     Debug << "max depth: " << mTermMaxDepth << endl;
@@ -313 +322 @@
         long startTime = GetTime();
         
-        while (!tStack.empty()) 
+        while (!tStack.empty())
         {
                 tData = tStack.top();
 
             tStack.pop();
+
                 // subdivide leaf node
                 BspNode *r = Subdivide(tStack, tData);
@@ -331 +341 @@
 }
 
-bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data, 
-                                                                                const int numLeaves) const
+bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
 {
         return 
@@ -338 +347 @@
                  (data.mPvs <= mTermMinPvs)   ||
                  (data.mArea <= mTermMinArea) ||
-                 ((mStat.nodes / 2 + 1) >= mMaxViewCells) ||
+                 (mStat.nodes / 2 + 1 >= mMaxViewCells) ||
                 // (data.GetAvgRayContribution() >= mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
@@ -348 +357 @@
         BspNode *newNode = tData.mNode;
 
-        if (!TerminationCriteriaMet(tData, (int)tStack.size()))
+        if (!TerminationCriteriaMet(tData))
         {
                 PolygonContainer coincident;
@@ -370 +379 @@
         }
         
-        //-- terminate traversal  
+        //-- terminate traversal and create new view cell
         if (newNode->IsLeaf())
         {
@@ -378 +387 @@
                 BspViewCell *viewCell = new BspViewCell();
                 leaf->SetViewCell(viewCell);
+                
+                if (mStoreRays)
+                {
+                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
+                        for (it = tData.mRays->begin(); it != it_end; ++ it)
+                                leaf->mVssRays.push_back((*it).mRay);
+                }
+
                 viewCell->mLeaves.push_back(leaf);
+                viewCell->SetArea(tData.mArea);
 
                 //-- update pvs
@@ -392 +410 @@
                 
         //-- cleanup
-        DEL_PTR(tData.mPolygons);
-        DEL_PTR(tData.mRays);
-        DEL_PTR(tData.mGeometry);
+        tData.Clear();
 
         return newNode;
@@ -1872 +1888 @@
         return hits;
 }
+
+int VspBspTree::MergeLeaves()
+{
+        vector<BspLeaf *> leaves;
+        priority_queue<BspMergeCandidate> mergeQueue;
+
+        // collect the leaves, e.g., the "voxels" that will build the view cells
+        CollectLeaves(leaves);
+
+        int vcSize = (int)leaves.size();
+        int savedVcSize = vcSize;
+
+        BspLeaf::NewMail();
+
+        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+        // find merge candidates and push them into queue
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspLeaf *leaf = *it;
+
+                // no leaf is part of two merge candidates
+                if (!leaf->Mailed())
+                {
+                        leaf->Mail();
+
+                        vector<BspLeaf *> neighbors;
+                        FindNeighbors(leaf, neighbors, true);
+
+                        vector<BspLeaf *>::const_iterator nit,
+                                nit_end = neighbors.end();
+
+                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+                        {
+                                BspMergeCandidate mc = BspMergeCandidate(leaf, *nit);
+                                mergeQueue.push(mc);
+
+                                BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
+                                BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
+                        }
+                }
+        }
+
+        int merged = 0;
+
+        Debug << "here234: " << mMergeMaxCostRatio << endl;
+
+        // use priority queue to merge leaves
+        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) )//&&
+                   //(mergeQueue.top().GetMergeCost() < 
+                    //mMergeMaxCostRatio / BspMergeCandidate::sOverallCost))
+        {
+                Debug << "mergecost: " << mergeQueue.top().GetMergeCost() << " " << mMergeMaxCostRatio << endl;
+                BspMergeCandidate mc = mergeQueue.top();
+                mergeQueue.pop();
+
+                // both view cells equal!
+                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
+                        continue;
+
+                if (mc.Valid())
+                {
+                        ViewCell::NewMail();
+                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
+
+                        ++ merged;
+                        -- vcSize;
+                        // increase absolute merge cost
+                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
+                }
+                // merge candidate not valid, because one of the leaves was already
+                // merged with another one
+                else
+                {
+                        // validate and reinsert into queue
+                        mc.SetValid();
+                        mergeQueue.push(mc);
+                        //Debug << "validate " << mc.GetMergeCost() << endl;
+                }
+        }
+
+        // collapse tree according to view cell partition
+        //CollapseTree(mRoot);
+
+        // revalidate leaves
+        //ValidateViewCellLeaves();
+
+        //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl;
+
+        //TODO: should return sample contributions
+        return merged;
+}
+
+
+bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2)
+{
+        //-- change pointer to view cells of all leaves associated 
+        //-- with the previous view cells
+        BspViewCell *fVc = l1->GetViewCell();
+        BspViewCell *bVc = l2->GetViewCell();
+
+        BspViewCell *vc = dynamic_cast<BspViewCell *>(
+                mViewCellsManager->MergeViewCells(*fVc, *bVc));
+
+        // if merge was unsuccessful
+        if (!vc) return false;
+
+        // set new size of view cell
+        vc->SetArea(fVc->GetVolume() + bVc->GetVolume());
+
+        vector<BspLeaf *> fLeaves = fVc->mLeaves;
+        vector<BspLeaf *> bLeaves = bVc->mLeaves;
+
+        vector<BspLeaf *>::const_iterator it;
+
+        //-- change view cells of all the other leaves the view cell belongs to
+        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
+        {
+                (*it)->SetViewCell(vc);
+                vc->mLeaves.push_back(*it);
+        }
+
+        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
+        {
+                (*it)->SetViewCell(vc);
+                vc->mLeaves.push_back(*it);
+        }
+
+        vc->Mail();
+
+        // clean up old view cells
+        DEL_PTR(fVc);
+        DEL_PTR(bVc);
+
+        return true;
+}
+
+
+void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
+{
+        mViewCellsManager = vcm;
+}
+
+/************************************************************************/
+/*                BspMergeCandidate implementation                      */
+/************************************************************************/
+
+
+BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
+mMergeCost(0),
+mLeaf1(l1),
+mLeaf2(l2),
+mLeaf1Id(l1->GetViewCell()->mMailbox),
+mLeaf2Id(l2->GetViewCell()->mMailbox)
+{
+        EvalMergeCost();
+}
+
+float BspMergeCandidate::GetLeaf1Cost() const
+{
+        BspViewCell *vc = mLeaf1->GetViewCell();
+        return vc->GetPvs().GetSize() * vc->GetArea();
+}
+
+float BspMergeCandidate::GetLeaf2Cost() const
+{
+        BspViewCell *vc = mLeaf2->GetViewCell();
+        return vc->GetPvs().GetSize() * vc->GetVolume();
+}
+
+void BspMergeCandidate::EvalMergeCost()
+{
+        //-- compute pvs difference
+        BspViewCell *vc1 = mLeaf1->GetViewCell();
+        BspViewCell *vc2 = mLeaf2->GetViewCell();
+
+        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
+        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
+
+        //-- 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)
+        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
+        
+        const float newCost =
+                (float)vcPvs * (vc1->GetArea() + vc2->GetArea());
+
+        mMergeCost = newCost - oldCost;
+
+//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
+//              mMergeCost += 1.0;
+}
+
+void BspMergeCandidate::SetLeaf1(BspLeaf *l)
+{
+        mLeaf1 = l;
+}
+
+void BspMergeCandidate::SetLeaf2(BspLeaf *l)
+{
+        mLeaf2 = l;
+}
+
+BspLeaf *BspMergeCandidate::GetLeaf1()
+{
+        return mLeaf1;
+}
+
+BspLeaf *BspMergeCandidate::GetLeaf2()
+{
+        return mLeaf2;
+}
+
+bool BspMergeCandidate::Valid() const
+{
+        return
+                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
+                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
+}
+
+float BspMergeCandidate::GetMergeCost() const
+{
+        return mMergeCost;
+}
+
+void BspMergeCandidate::SetValid()
+{
+        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
+        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
+
+        EvalMergeCost();
+}

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -20 +20 @@
 class Ray;
 class ViewCellsStatistics;
-
-/*class BspNodeGeometry;
-class BspTreeStatistics;
-class ViewCellsStatistics;
-class BspNode;
-class BspLeaf;
-class BspInterior;
-*/
+class ViewCellsManager;
+
 
 /**
@@ -130 +124 @@
                 }
 
+                // deletes contents and sets them to NULL
+                void Clear()
+                {
+                        DEL_PTR(mPolygons);
+                        DEL_PTR(mRays);
+                        DEL_PTR(mGeometry);
+                }
+
                 friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
                 {
@@ -237 +239 @@
 
 
-    int
-        CastLineSegment(const Vector3 &origin,
-                                        const Vector3 &termination,
-                                        ViewCellContainer &viewcells
-                                        );
+    int CastLineSegment(const Vector3 &origin,
+                                                const Vector3 &termination,
+                                                ViewCellContainer &viewcells);
+
+        /** Merges leaves with similar PVS.
+        */
+        int MergeLeaves();
+
+
+                
+        /** Sets pointer to view cells manager.
+        */
+        void SetViewCellsManager(ViewCellsManager *vcm);
 
 protected:
@@ -428 +438 @@
         /** Returns true if tree can be terminated.
         */
-        inline bool TerminationCriteriaMet(const VspBspTraversalData &data, const int numLeaves) const;
+        inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const;
 
         /** Computes accumulated ray lenght of this rays.
@@ -477 +487 @@
         Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
   
+        /** Merge view cells of leaves l1 and l2.
+        */
+        bool MergeViewCells(BspLeaf *l1, BspLeaf *l2);
+
         /// Pointer to the root of the tree
         BspNode *mRoot;
@@ -549 +563 @@
         /// maximal number of view cells
         int mMaxViewCells;
+        /// minimal number of view cells
+        int mMergeMinViewCells;
+        /// maximal cost ratio for the merge
+        int mMergeMaxCostRatio;
+
+        ViewCellsManager *mViewCellsManager;
+
+        // if rays should be stored in leaves
+        bool mStoreRays;
 
 private:
@@ -567 +590 @@
 };
 
+/**
+        Candidate for leaf merging based on priority.
+*/
+class BspMergeCandidate
+{  
+public:
+
+        BspMergeCandidate(BspLeaf *l1, BspLeaf *l2);
+
+        /** If this merge pair is still valid.
+        */
+        bool Valid() const;
+
+        /** Sets this merge candidate to be valid.
+        */
+        void SetValid();
+
+        friend bool operator<(const BspMergeCandidate &leafa, const BspMergeCandidate &leafb)
+        {
+                return leafb.GetMergeCost() < leafa.GetMergeCost();
+        }
+
+        void SetLeaf1(BspLeaf *l);
+        void SetLeaf2(BspLeaf *l);
+
+        BspLeaf *GetLeaf1();
+        BspLeaf *GetLeaf2();
+
+        /** Merge cost of this candidate pair.
+        */
+        float GetMergeCost() const;
+
+        /** Returns cost of leaf 1.
+        */
+        float GetLeaf1Cost() const;
+        /** Returns cost of leaf 2.
+        */
+        float GetLeaf2Cost() const;
+
+        /// maximal pvs size
+        static int sMaxPvsSize;
+        /// overall cost used to normalize cost ratio
+        static float sOverallCost;
+
+protected:
+        
+        /** Evaluates the merge costs of the leaves.
+        */
+        void EvalMergeCost();
+
+        int mLeaf1Id;
+        int mLeaf2Id;
+
+        float mMergeCost;
+        
+        BspLeaf *mLeaf1;
+        BspLeaf *mLeaf2;
+};
+
+
 #endif

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -1910 +1910 @@
 
 
-
 void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm)
 {
@@ -2023 +2022 @@
         leaf->SetViewCell(vc);
 
-        vc->SetVolume(GetBBox(leaf).GetVolume());
+        vc->SetArea(GetBBox(leaf).GetVolume());
         vc->mLeaves.push_back(leaf);
 
@@ -2107 +2106 @@
 
         // set new size of view cell
-        vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
+        vc->SetArea(fVc->GetVolume() + bVc->GetVolume());
 
         vector<VspKdLeaf *> fLeaves = fVc->mLeaves;
@@ -2229 +2228 @@
         ValidateViewCellLeaves();
 
-        Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl;
+        //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl;
 
         //TODO: should return sample contributions