Changeset 379

Timestamp:

11/05/05 12:40:40 (19 years ago)

Author:

mattausch

Message:

worked on pvs heuristics

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (3 diffs)
• src/Environment.cpp (modified) (2 diffs)
• src/Exporter.h (modified) (1 diff)
• src/SamplingPreprocessor.cpp (modified) (5 diffs)
• src/ViewCellBsp.cpp (modified) (21 diffs)
• src/ViewCellBsp.h (modified) (4 diffs)
• src/X3dExporter.cpp (modified) (3 diffs)
• src/X3dExporter.h (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -56 +56 @@
 
 Sampling {
-        totalSamples    400000
+        totalSamples    300000
         samplesPerPass  3
 }
@@ -73 +73 @@
                 minPvs 10
                 maxPvs 300
-                samples 100000
+                samples 100
         }
 
@@ -126 +126 @@
         #splitPlaneStrategy 130
         
-        splitPlaneStrategy 130
+        splitPlaneStrategy 256
         
-        maxCandidates 80
+        maxPolyCandidates 5
+        maxRayCandidates 50
         
         Termination {
                 # autopartition
-                maxRays 30
+                maxRays 1000
                 maxPolygons 1
-                maxDepth 50
+                maxDepth 10
                 
                 # axis aligned splits
                 AxisAligned {
                         maxPolys 5000
-                        maxRays 600
+                        maxRays 500
                         maxObjects 10
                         maxCostRatio 0.9

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1203 +1203 @@
           optInt,
           "-bsp_postprocessing_samples=",
-          "200000");
+          "206000");
 
   RegisterOption("BspTree.Construction.sideTolerance",
@@ -1261 +1261 @@
 
   RegisterOption("BspTree.splitPlaneStrategy",
-                                                                 optString,
-                                                                 "-bsp_split_method=",
-                                                                 "leastSplits");
-
-  RegisterOption("BspTree.maxCandidates",
+                 optString,
+                 "-bsp_split_method=",
+                 "leastSplits");
+
+  RegisterOption("BspTree.maxPolyCandidates",
           optInt,
-          "-bsp_max_candidates=",
+          "-bsp_max_poly_candidates=",
+          "20");
+
+  RegisterOption("BspTree.maxRayCandidates",
+          optInt,
+          "-bsp_max_plane_candidates=",
           "20");
 

trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h

@@ -79 +79 @@
 
   virtual void
-  ExportBspViewCellPartition(const BspTree &tree) = 0;
+  ExportBspViewCellPartition(const BspTree &tree, const int maxPvs = 0) = 0;
 
   virtual void 

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -551 +551 @@
                 Debug << "original view cell partition:\n" << stat << endl;
                 
-                cout << "starting post processing using " << mSampleRays.size() << " samples ... ";
+                if (1) // export view cells
+                {
+                        cout << "exporting view cells ... ";
+                        Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
+                        if (exporter)
+                        {
+                                //exporter->ExportBspViewCellPartition(*mBspTree, stat.maxPvs);
+                                exporter->ExportBspViewCellPartition(*mBspTree, 0);
+                                delete exporter;
+                        }
+                        cout << "finished" << endl;
+                }
+
+                cout << "starting post processing using " << (int)mSampleRays.size() << " samples ... ";
                 
                 long startTime = GetTime();
@@ -572 +585 @@
                 cout << "render time: " << rt * 1e-3 << endl;
                 Debug << "render time: " << rt * 1e-3 << endl;
+
+                if (1) // export view cells
+                {
+                        cout << "exporting view cells after merge ... ";
+                        Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
+                        if (exporter)
+                        {
+                                //exporter->ExportBspViewCellPartition(*mBspTree, stat.maxPvs);
+                                exporter->ExportBspViewCellPartition(*mBspTree, 0);
+                                delete exporter;
+                        }
+
+                        cout << "finished" << endl;
+                }
+
+                //-- visualization of the bsp splits
+                bool exportSplits = false;
+                environment->GetBoolValue("BspTree.exportSplits", exportSplits);
+
+                
+                cout << "exporting splits ... ";
+                if (exportSplits)
+                        ExportSplits(objects);
+                cout << "finished" << endl;
+
+                // export the PVS of sample view cells
+                if (1)
+                        ExportBspPvs(objects);
         }
         
@@ -603 +644 @@
         //-- several visualizations and statistics
         if (1) {
-                if (mBspTree && (ViewCell::sHierarchy == ViewCell::BSP))
-        {
-                bool exportSplits = false;
-                environment->GetBoolValue("BspTree.exportSplits", exportSplits);
-
-                // export the bsp splits
-                cout << "exporting splits ... ";
-                if (exportSplits)
-                        ExportSplits(objects);
-                cout << "finished" << endl;
-
-                ExportBspPvs(objects);
-        }
+        
    for (int k=0; k < pvsOut; k++) {
                  Intersectable *object = objects[k];
@@ -901 +930 @@
                 cout << "finished" << endl;
         }
-
-        if (1) // export view cells and leaves
-        {
-                cout << "exporting view cells and leaves ... ";
-                Exporter *exporter = Exporter::GetExporter("viewCells.x3d");
-                if (exporter)
-                {
-                        exporter->ExportBspViewCellPartition(*mBspTree);
-                        delete exporter;
-                }
-
-                exporter = Exporter::GetExporter("bspLeaves.x3d");
-
-                if (exporter)
-                {
-                        exporter->ExportBspLeaves(*mBspTree);
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
-
 }
 
@@ -940 +948 @@
         const float vcOverhead = 0.01f;
         
-        float totalArea = 0;
+        // total area of view cells
+        float totalArea = 0;//= mKdTree->GetBox().SurfaceArea();
 
         ViewCellContainer viewCells;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -16 +16 @@
 int BspTree::sTermMaxPolygons = 10;
 int BspTree::sTermMaxDepth = 20;
-int BspTree::sMaxCandidates = 10;
+int BspTree::sMaxPolyCandidates = 10;
+int BspTree::sMaxRayCandidates = 10;
 int BspTree::sSplitPlaneStrategy = BALANCED_POLYS; 
 int BspTree::sConstructionMethod = FROM_INPUT_VIEW_CELLS;
@@ -1050 +1051 @@
                                                         const BoundedRayContainer &rays)
 {
-        if (polys.empty())
+        if (polys.empty() && rays.empty())
         {
                 Debug << "Warning: No autopartition polygon candidate available\n";
@@ -1082 +1083 @@
         if (sSplitPlaneStrategy & RANDOM_POLYGON)
         {
-                return polys[Random((int)polys.size())]->GetSupportingPlane();
+                Vector3 pt[3];
+                for (int j = 0; j < 3; j ++)
+                {
+                        int idx = Random((int)rays.size());
+                        pt[j] = rays[idx]->mRay->Extrap(rays[idx]->mMaxT);
+                }
+
+                return Plane3(pt[0], pt[1], pt[2]);
+
+        //return polys[Random((int)polys.size())]->GetSupportingPlane();
         }
 
         // use heuristics to find appropriate plane
-        return SelectPlaneHeuristics(polys, rays, sMaxCandidates);
+        return SelectPlaneHeuristics(polys, rays, sMaxPolyCandidates, sMaxRayCandidates);
 }
 
 Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer &polys,
                                                                           const BoundedRayContainer &rays,
-                                                                          const int maxTests)
+                                                                          const int maxPolyCandidates,
+                                                                          const int maxRayCandidates)
 {
         float lowestCost = MAX_FLOAT;
         int bestPlaneIdx = 0;
         
-        int limit = maxTests > 0 ? Min((int)polys.size(), maxTests) : (int)polys.size();
+        int limit = maxPolyCandidates > 0 ? Min((int)polys.size(), maxPolyCandidates) : (int)polys.size();
         
         int candidateIdx = limit;
-        
-        for (int i = 0; i < limit; ++ i)
+
+        //Debug << endl;
+        /*for (int i = 0; i < limit; ++ i)
         {
                 candidateIdx = GetNextCandidateIdx(candidateIdx, polys);
 
                 Plane3 candidatePlane = polys[candidateIdx]->GetSupportingPlane();
-                
+                //Debug << polys[candidateIdx] << endl;
                 // evaluate current candidate
                 float candidateCost = SplitPlaneCost(candidatePlane, polys, rays);
@@ -1114 +1126 @@
                         lowestCost = candidateCost;
                 }
-        }
-        
+        }*/
+        
+        //limit = maxRaysCandidates > 0 ? Min((int)rays.size(), maxRayCandidates) : (int)rays.size();
+        bool chooseFromRays = false;
+        int bestIdx[3];
+
+        for (int i = 0; i < maxRayCandidates; ++ i)
+        {
+                Vector3 pt[3];
+                int idx[3];
+
+                for (int j = 0; j < 3; j ++)
+                {
+                        idx[j] = Random((int)rays.size());
+                        pt[j] = rays[idx[j]]->mRay->Extrap(rays[idx[j]]->mMaxT);
+                }
+
+                float candidateCost = SplitPlaneCost(Plane3(pt[0], pt[1], pt[2]), polys, rays);
+
+                if (candidateCost < lowestCost)
+                {
+                        chooseFromRays = true;
+                        bestIdx[0] = idx[0]; bestIdx[1]= idx[1]; bestIdx[2] = idx[2];
+                        
+                        lowestCost = candidateCost;
+                }
+        }
+
+        if (chooseFromRays)
+        {
+                return Plane3(rays[bestIdx[0]]->mRay->Extrap(rays[bestIdx[0]]->mMaxT),
+                                          rays[bestIdx[1]]->mRay->Extrap(rays[bestIdx[1]]->mMaxT),
+                                          rays[bestIdx[2]]->mRay->Extrap(rays[bestIdx[2]]->mMaxT));
+        }
+
         //Debug << "Plane lowest cost: " << lowestCost << endl;
         return polys[bestPlaneIdx]->GetSupportingPlane();
@@ -1126 +1171 @@
         // swap candidates to avoid testing same plane 2 times
         std::swap(polys[currentIdx], polys[candidateIdx]);
-
-        /*Polygon3 *p = polys[candidateIdx];
-        polys[candidateIdx] = polys[currentIdx];
-        polys[currentIdx] = p;*/
         
         return currentIdx;
@@ -1281 +1322 @@
         float sumBalancedRays = 0;
         float sumRaySplits = 0;
-        float pvsSize = 0;
+        float frontPvs = 0;
+        float backPvs = 0;
+
         float totalSize = 0;
-
-        // need three unique ids for small pvs criterium
-        Intersectable::NewMail();
-        const int backId = ViewCell::sMailId;
-        Intersectable::NewMail();
-        const int frontId = ViewCell::sMailId;
-        Intersectable::NewMail();
-        const int frontAndBackId = ViewCell::sMailId;
-        //Debug << "f " << frontId <<  " b " << backId << " fb " << frontAndBackId << endl;
-
+        
+        // create three unique ids for pvs heuristics
+        Intersectable::NewMail(); const int backId = ViewCell::sMailId;
+        Intersectable::NewMail(); const int frontId = ViewCell::sMailId;
+        Intersectable::NewMail(); const int frontAndBackId = ViewCell::sMailId;
+
+        /*PolygonContainer cell;
+        PolygonContainer front;
+        PolygonContainer back;
+
+        ConstructGeometry(currentNode, cell);
+        ConstructChildrenGeometry(front, cell, planes, sides);
+        ConstructChildrenGeometry(back, cell, planes, sides);*/
+
+
+        int frontRays = 0;
+        int backRays = 0;
+
+        // todo create geometry of left and right leaves
+        
         BoundedRayContainer::const_iterator rit, rit_end = rays.end();
 
@@ -1316 +1369 @@
                 if (sSplitPlaneStrategy & PVS)
                 {
-                        vector<Ray::Intersection>::const_iterator it, 
-                                it_end = ray->intersections.end();
-
                         if (!ray->intersections.empty())
                         {
-
+                                // in case the ray intersects an objcrs
                                 // assure that we only count a object 
                                 // once for the front and once for the back side of the plane
-                                pvsSize += PvsValue(*ray->intersections[0].mObject, 
-                                                                        cf, 
-                                                                        frontId, 
-                                                                        backId, 
-                                                                        frontAndBackId);
-
-                                // always add 2 for each object (= maximal large PVS)
-                                //if (inc > 0.01)       totalSize += 2.0;
+                                ComputePvs(*ray->intersections[0].mObject, 
+                                                   frontPvs, 
+                                               backPvs, 
+                                                   cf, 
+                                                   frontId, 
+                                                   backId, 
+                                                   frontAndBackId);
                         }
-                        //todo emerging obj
+
+                        // the source object in the origin of the ray
+                        ComputePvs(*ray->sourceObject.mObject, 
+                                           frontPvs, 
+                                       backPvs, 
+                                           cf, 
+                                           frontId, 
+                                           backId, 
+                                           frontAndBackId);
+
+                        if ((cf == Ray::BACK) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
+                                ++ backRays;
+                        if ((cf == Ray::FRONT) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
+                                ++ frontRays;
                 }
         }
@@ -1346 +1408 @@
 
         if (sSplitPlaneStrategy & PVS)
-                if (!rays.empty()) // HACK (should be maximal possible pvs)
-                        val += sPvsFactor * pvsSize / (float)rays.size(); 
+                if (!rays.empty()) // HACK (should divide by maximal possible pvs)
+                        val += sPvsFactor * (frontPvs * (float)frontRays + (backPvs * (float)backRays)) / 
+                        (float)rays.size(); 
 
         //Debug << "pvs: " << pvsSize << " val " << val << endl;
@@ -1354 +1417 @@
 
 
-float BspTree::PvsValue(Intersectable &obj, 
-                                            const int cf, 
-                                            const int frontId, 
-                                            const int backId, 
-                                            const int frontAndBackId) const
-{
-        float pvsVal = 0;
-
+/*void BspTree::CreateChildrenGeometry(PolygonContainer &cell, 
+                                                                         PolygonContainer &front, 
+                                                                         PolygonContainer &back, 
+                                                                         Plane3 &splitPlane)
+{
+}*/
+
+void BspTree::ComputePvs(Intersectable &obj, 
+                                                 float &frontPvs,
+                                                 float &backPvs,
+                                                 const int cf, 
+                                                 const int frontId, 
+                                                 const int backId, 
+                                                 const int frontAndBackId) const
+{
         if (cf == Ray::COINCIDENT)
-                return pvsVal;
+                return;
 
         if (cf == Ray::FRONT)
@@ -1369 +1439 @@
                 if ((obj.mMailbox != frontId) && 
                         (obj.mMailbox != frontAndBackId))
-                        pvsVal = 1.0;
+                        frontPvs += 1.0;
 
                 if (obj.mMailbox != backId)
@@ -1381 +1451 @@
                         (obj.mMailbox != frontAndBackId))
                 {
-                        pvsVal = 1.0;
+                        backPvs += 1.0;
 
                         if (obj.mMailbox != frontId)
@@ -1391 +1461 @@
         else if ((cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
         {
-                if ((obj.mMailbox == backId) || (obj.mMailbox == frontId))
-                        pvsVal = 1.0;
-                else if (obj.mMailbox != frontAndBackId)
-                        pvsVal = 2.0;
-                        
+                if (obj.mMailbox == backId)
+                        frontPvs += 1.0;
+                else if (obj.mMailbox == frontId)
+                        backPvs += 1.0;
+                else if (obj.mMailbox != frontAndBackId) // can add to both PVS
+                {
+                        frontPvs += 1.0;
+                        backPvs += 1.0;
+                }
                 obj.mMailbox = frontAndBackId;
         }
-
-        return pvsVal;
 }
 
@@ -1477 +1549 @@
                                                          sTermMaxObjectsForAxisAligned);
         //-- partition criteria
-        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
+        environment->GetIntValue("BspTree.maxPolyCandidates", sMaxPolyCandidates);
+        environment->GetIntValue("BspTree.maxRayCandidates", sMaxRayCandidates);
         environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
         environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder);
@@ -1493 +1566 @@
     Debug << "BSP max depth: " << sTermMaxDepth << endl;
         Debug << "BSP max polys: " << sTermMaxPolygons << endl;
-        Debug << "BSP max candidates: " << sMaxCandidates << endl;
-        
+        Debug << "BSP max rays: " << sTermMaxRays << endl;
+        Debug << "BSP max polygon candidates: " << sMaxPolyCandidates << endl;
+        Debug << "BSP max plane candidates: " << sMaxRayCandidates << endl;
+
         Debug << "Split plane strategy: ";
         if (sSplitPlaneStrategy & RANDOM_POLYGON)
@@ -1512 +1587 @@
         if (sSplitPlaneStrategy & BLOCKED_RAYS)
                 Debug << "blocked rays ";
+        if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
+                Debug << "least ray splits ";
+        if (sSplitPlaneStrategy & BALANCED_RAYS)
+                Debug << "balanced rays ";
         if (sSplitPlaneStrategy & PVS)
                 Debug << "pvs";
@@ -1939 +2018 @@
 }
 
-struct Candidate
-{
-        Polygon3 *mPoly;
-        Plane3 mPlane;
-        bool mSide;
-
-        Candidate(Polygon3 *poly, const Plane3 &plane, const bool &side):
-        mPoly(poly), mPlane(plane), mSide(side)
-        {}
-};
-
-void BspTree::AddHalfspace(PolygonContainer &cell, 
-                                                   vector<Plane3> &planes,
-                                                   vector<bool> &sides,
-                                                   const Plane3 &halfspace, 
-                                                   const bool side) const
-{
-        Polygon3 *poly = GetBoundingBox().CrossSection(halfspace);
+bool BspTree::ComputeChildrenGeometry(PolygonContainer &newCell,
+                                                                          const PolygonContainer &cell,
+                                                                          const vector<Plane3> &planes,
+                                                                          const vector<bool> &sides,
+                                                                          const Plane3 &splitPlane,
+                                                                          const bool side) const
+{
+        // get cross section of new polygon
+        Polygon3 *planePoly = GetBoundingBox().CrossSection(splitPlane);
 
         bool inside = true;
@@ -1963 +2033 @@
         for (int i = 0; (i < planes.size()) && inside; ++ i)
         {
-                VertexContainer splitPts;
-                Polygon3 *frontPoly, *backPoly;
-
-                const int cf = poly->ClassifyPlane(planes[i]);
+                const int cf = planePoly->ClassifyPlane(planes[i]);
                         
                 // split new polygon with all previous planes
@@ -1972 +2039 @@
                 {
                         case Polygon3::SPLIT:
-                                frontPoly = new Polygon3();
-                                backPoly = new Polygon3();
-
-                                poly->Split(planes[i], *frontPoly, *backPoly, splitPts);
-                                DEL_PTR(poly);
-
-                                if(sides[i] == true)
                                 {
-                                        poly = frontPoly;
-                                        DEL_PTR(backPoly);
-                                }
+                                        VertexContainer splitPts;
+                                
+                                        Polygon3 *frontPoly = new Polygon3();
+                                        Polygon3 *backPoly = new Polygon3();
+
+                                        planePoly->Split(planes[i], *frontPoly, *backPoly, splitPts);
+                                        DEL_PTR(planePoly);
+
+                                        if(sides[i] == true)
+                                        {
+                                                planePoly = frontPoly;
+                                                DEL_PTR(backPoly);
+                                        }
                                         else
                                         {
-                                                poly = backPoly;
+                                                planePoly = backPoly;
                                                 DEL_PTR(frontPoly);
                                         }
+                                        
                                         inside = true;
-                                        break;
+                                }
+                                break;
                         case Polygon3::BACK_SIDE:
                                 if (sides[i]) 
@@ -2002 +2074 @@
                 }
         }
+        
+        //-- finally add polygon
+        if (inside)
+                newCell.push_back(planePoly);
+        else
+        {
+                //just copy polygons
+                DEL_PTR(planePoly);
+                PolygonContainer::const_iterator it, it_end = cell.end();
+                
+                for (it = cell.begin(); it != it_end; ++ it)
+                        newCell.push_back(*it);
+
+                return false;
+        }
 
         //-- plane poly splits all other candidates
-
-    // some polygons may fall out => rebuild cell
-        vector<Candidate> candidates;
-
         for (int i = 0; i < (int)cell.size(); ++ i)
         {
-                candidates.push_back(Candidate(cell[i], planes[i], sides[i]));
-        }
-
-        cell.clear();
-        planes.clear();
-        sides.clear();
-
-        for (int i = 0; i < (int)candidates.size(); ++ i)
-        {
-                bool candidateInside = true;
-
-                VertexContainer splitPts;
-                Polygon3 *frontPoly, *backPoly;
-
-                const int cf = poly->ClassifyPlane(halfspace);
+                inside = true;
+                
+                const int cf = cell[i]->ClassifyPlane(splitPlane);
                         
                 // split new polygon with all previous planes
@@ -2030 +2101 @@
                 {
                         case Polygon3::SPLIT:
-                                frontPoly = new Polygon3();
-                                backPoly = new Polygon3();
-
-                                poly->Split(halfspace, *frontPoly, *backPoly, splitPts);
-                                DEL_PTR(candidates[i].mPoly);
-
-                                if (sides[i] == true)
                                 {
-                                        candidates[i].mPoly = frontPoly;
-                                        DEL_PTR(backPoly);
+                                        Polygon3 *poly = new Polygon3(*cell[i]);
+
+                                        Polygon3 *frontPoly = new Polygon3();
+                                        Polygon3 *backPoly = new Polygon3();
+                                
+                                        VertexContainer splitPts;
+                                                
+                                        poly->Split(splitPlane, *frontPoly, *backPoly, splitPts);
+                                        DEL_PTR(poly);
+
+                                        if (sides[i] == true)
+                                        {
+                                                newCell.push_back(frontPoly);
+                                                DEL_PTR(backPoly);
+                                        }
+                                        else
+                                        {
+                                                newCell.push_back(backPoly);
+                                                DEL_PTR(frontPoly);
+                                        }
                                 }
-                                else
-                                {
-                                        candidates[i].mPoly = backPoly;
-                                        DEL_PTR(frontPoly);
-                                }
-                                inside = true;
                                 break;
                         case Polygon3::BACK_SIDE:
-                                if (candidates[i].mSide) 
-                                        candidateInside = false;
+                                if (!sides[i]) 
+                                        newCell.push_back(new Polygon3(*cell[i]));
+                        
                                 break;
                         case Polygon3::FRONT_SIDE:
-                                if (!candidates[i].mSide)
-                                        candidateInside = false;
+                                if (sides[i])
+                                        newCell.push_back(new Polygon3(*cell[i]));
+                                        inside = false;
                                 break;
                         default:
                                 break;
                 }
-                
-                if (candidateInside)
-                {
-                        cell.push_back(candidates[i].mPoly);
-                        sides.push_back(candidates[i].mSide);
-                        planes.push_back(candidates[i].mPlane);
-                }
-                else
-                {
-                        DEL_PTR(candidates[i].mPoly);
-                }
-        }
-
-        //-- finally add polygon
-        if (inside)
-        {
-                cell.push_back(poly);
-                planes.push_back(halfspace);
-                sides.push_back(side);
-        }
-        else
-        {
-                DEL_PTR(poly);
-        }
+        }
+
+        return true;
 }
 
@@ -2340 +2397 @@
         return NULL;
 }
-
-int BspTree::CountPvs(const BoundedRayContainer &rays) const
-{
-        int pvsSize = 0;
-
-        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
-        vector<Ray::BspIntersection>::const_iterator iit;
-
-        ViewCell::NewMail();
-
-        for (rit = rays.begin(); rit != rit_end; ++ rit)
-        {
-                Ray *ray = (*rit)->mRay;
-                
-                for (iit = ray->bspIntersections.begin(); 
-                         iit != ray->bspIntersections.end(); ++ iit)
-                {
-                        BspViewCell *vc = (*iit).mLeaf->mViewCell;
-
-                        if (vc->Mailed())
-                        {
-                                pvsSize += vc->GetPvs().GetSize();
-                        }
-                }
-        }
-
-        return pvsSize;
-}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -455 +455 @@
         BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
 
-        /** Adds halfspace to cell definition.
-                @param side indicates which side of halfspace is added
-        */
-        void AddHalfspace(PolygonContainer &cell, 
-                                          vector<Plane3> &planes,
-                                          vector<bool> &sides,
-                                          const Plane3 &halfspace, 
-                                          const bool side) const;
+        /** Computes new cell based on the old cell definition and a new split plane
+                @param side indicates which side of the halfspace 
+                @returns true if plane contributes to the cell.
+        */
+        bool ComputeChildrenGeometry(PolygonContainer &newCell,
+                                                        const PolygonContainer &cell,
+                                                        const vector<Plane3> &planes,
+                                                        const vector<bool> &sides,
+                                                        const Plane3 &splitPlane,
+                                                        const bool side) const;
+
 
         /** Returns true if merge criteria are reached.
@@ -602 +605 @@
                 @param polygons container of polygons
                 @param rays bundle of rays on which the split can be based
-                @param maxTests the maximal number of candidate tests
+                @param maxPolyCandidates the maximal number of tested polygon candidates
+                @param maxRayCandidates the maximal number of ray candidates
         */
         Plane3 SelectPlaneHeuristics(PolygonContainer &polys, 
                                                                  const BoundedRayContainer &rays,
-                                                                 const int maxTests);
+                                                                 const int maxPolyCandidates,
+                                                                 const int maxRayCandidates);
 
         /** Extracts the meshes of the objects and adds them to polygons. 
@@ -710 +715 @@
         void ExtractSplitPlanes(BspNode *n, vector<Plane3 *> &planes, vector<bool> &sides) const;
 
-        int CountPvs(const BoundedRayContainer &rays) const;
-        
-        float PvsValue(Intersectable &obj, 
-                                   const int cf, 
-                                   const int frontId, 
-                                   const int backId, 
-                                   const int frontAndBackId) const;
+        /** Computes the pvs of the front and back leaf with a given classification.
+        */
+        void ComputePvs(Intersectable &obj, 
+                                        float &frontPvs,
+                                        float &backPvs,
+                                        const int cf, 
+                                        const int frontId, 
+                                        const int backId, 
+                                        const int frontAndBackId) const;
         
         /// Pointer to the root of the tree
         BspNode *mRoot;
-
                 
         BspTreeStatistics mStat;
@@ -764 +770 @@
         static int sSplitPlaneStrategy;
         /// number of candidates evaluated for the next split plane
-        static int sMaxCandidates;
+        static int sMaxPolyCandidates;
+        static int sMaxRayCandidates;
         /// BSP tree construction method
         static int sConstructionMethod;

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -179 +179 @@
 
 void 
-X3dExporter::ExportBspViewCellPartition(const BspTree &tree)
+X3dExporter::ExportBspViewCellPartition(const BspTree &tree, const int maxPvs)
 {
         ViewCellContainer viewCells;
@@ -186 +186 @@
         ViewCellContainer::const_iterator it, it_end = viewCells.end();
 
+
+        if (maxPvs == 0)
+                mUseForcedMaterial = true;
+
         for (it = viewCells.begin(); it != it_end; ++ it)
         {
+                mForcedMaterial.mDiffuseColor.b = 1.0f;
+  
+                float importance = 0;
+
+                if (maxPvs > 0)
+                        importance = (float)(*it)->GetPvs().GetSize() / (float)maxPvs;
+
+                mForcedMaterial.mDiffuseColor.r = importance;
+                mForcedMaterial.mDiffuseColor.g = 1.0f - mForcedMaterial.mDiffuseColor.r;
+                
                 if ((*it)->GetMesh())
                         ExportViewCell(*it);
@@ -194 +208 @@
                         PolygonContainer cell;
                         tree.ConstructGeometry(dynamic_cast<BspViewCell *>(*it), cell);
+
                         ExportPolygons(cell);
                 }

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h

@@ -86 +86 @@
 
   virtual void
-  ExportBspViewCellPartition(const BspTree &tree);
+  ExportBspViewCellPartition(const BspTree &tree, const int maxPvs = 0);
 
   virtual void