Changeset 473

Timestamp:

12/20/05 20:33:42 (18 years ago)

Author:

mattausch

Message:

worked on new features,
removed Random Bug (took only 32000 values),
removed bug when choosing new candidates (totally wrong)
introduced new candidate plane method
implemented priority queue for vsp bsp

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (7 diffs)
• src/Environment.cpp (modified) (3 diffs)
• src/Preprocessor.cpp (modified) (2 diffs)
• src/RenderSimulator.cpp (modified) (3 diffs)
• src/RenderSimulator.h (modified) (1 diff)
• src/RssPreprocessor.cpp (modified) (3 diffs)
• src/SamplingPreprocessor.cpp (modified) (2 diffs)
• src/ViewCellBsp.cpp (modified) (11 diffs)
• src/ViewCellBsp.h (modified) (3 diffs)
• src/ViewCellsManager.cpp (modified) (13 diffs)
• src/VspBspTree.cpp (modified) (22 diffs)
• src/VspBspTree.h (modified) (6 diffs)
• src/VspKdTree.cpp (modified) (2 diffs)
• src/VspKdTree.h (modified) (1 diff)
• src/VssPreprocessor.cpp (modified) (2 diffs)
• src/VssTree.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -13 +13 @@
 #;../data/vienna/vienna-plane.x3d
 #       filename ../data/vienna/viewcells-25-sel.x3d
-#       filename ../data/atlanta/atlanta2.x3d
+        filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
-        filename ../data/soda/soda5.dat
+#       filename ../data/soda/soda5.dat
 }
 
@@ -71 +71 @@
 
 RssTree {
-        useRss    false
+        #useRss    false
         epsilon         1e-6
 
@@ -146 +146 @@
         loadFromFile false
         #type kdTree
-        type vspKdTree
+        #type vspKdTree
         #type bspTree
-        #type vspBspTree
+        type vspBspTree
         
         #type sceneDependent
@@ -172 +172 @@
 #       filename ../data/vienna/viewcells-25.x3d
 #       filename ../data/vienna/viewcells-large-sel.x3d
+}
+
+
+Simulation {
+        objRenderCost 1.0
+        vcOverhead 7.0
+        moveSpeed 3.0
+}
+
+
+VspKdTree {
+        epsilon         1e-6
+
+        Construction {
+                samples 300000
+        }
+        
+        Termination {
+                maxDepth                40
+                minPvs                  5
+                minRays                 500
+                minSize                 0.1
+                maxCostRatio            0.9
+                missTolerance           4
+                maxRayContribution      0.2
+        }
+        
+        maxTotalMemory  400
+        maxStaticMemory 200
+
+        splitType       regular
+        #splitType      heuristics
+        ct_div_ci       0.0
+        
+        # maximal cost for merging a view cell
+        PostProcess {
+                maxCostRatio 5000000
+                minViewCells 100
+                maxPvsSize   50000
+        }
+        
+        
+        Visualization {
+                exportRays true
+                exportGeometry false
+        }
+}
+
+VspBspTree {
+        Construction {
+                samples 100000
+                epsilon 0.005
+        }
+
+
+        # random polygon       = 1
+        # axis aligned         = 2
+        # least ray splits     = 256
+        # balanced rays        = 512
+        # pvs                  = 1024
+
+        splitPlaneStrategy 1024
+        
+        # maximal candidates for split planes
+        maxPolyCandidates 50
+        maxRayCandidates 50
+        
+        # maximal tested rays for split cost heuristics
+        maxTests 10000
+        
+        # factors for evaluating split plane costs
+        Factor {
+                leastRaySplits 1.0
+                balancedRays 1.0
+                pvs 1.0
+        }
+        
+        Termination {
+                # parameters used for autopartition
+                minRays                 100
+                minPolygons             -1
+                maxDepth                30
+                minPvs                  100
+                minArea                 0.01
+                maxRayContribution      0.005
+                maxCostRatio            0.9
+                missTolerance           1
+                #maxAccRayLength        100
+                
+                # used for pvs criterium
+                ct_div_ci 0.0
+        
+                # axis aligned splits
+                AxisAligned {
+                        minPolys 5000
+                        minRays 500
+                        minObjects 10
+                        ct_div_ci 0.5
+                }
+        }
+        
+        AxisAligned {
+                splitBorder 0.01
+        }
+        
+        
+        Visualization {
+                # x3d visualization of the split planes
+                exportSplits true
+                exportRays true
+                exportGeometry true
+        }
 }
 
@@ -247 +359 @@
                 ct_div_ci 0.0
         
+                maxCostRatio 0.9
+                
                 # axis aligned splits
                 AxisAligned {
@@ -252 +366 @@
                         minRays 500
                         minObjects 10
-                        maxCostRatio 0.9
                         ct_div_ci 0.5
                 }
@@ -269 +382 @@
         }
 }
-
-Simulation {
-        objRenderCost 1.0
-        vcOverhead 7.0
-        moveSpeed 3.0
-}
-
-
-VspKdTree {
-        epsilon         1e-6
-
-        Construction {
-                samples 300000
-        }
-        
-        Termination {
-                maxDepth                40
-                minPvs                  5
-                minRays                 500
-                minSize                 0.1
-                maxCostRatio            0.9
-                missTolerance           4
-                maxRayContribution      0.2
-        }
-        
-        maxTotalMemory  400
-        maxStaticMemory 200
-
-        splitType       regular
-        #splitType      heuristics
-        ct_div_ci       0.0
-        
-        # maximal cost for merging a view cell
-        PostProcess {
-                maxCostRatio 5000000
-                minViewCells 100
-                maxPvsSize   50000
-        }
-        
-        
-        Visualization {
-                exportRays true
-                exportGeometry false
-        }
-}
-
-VspBspTree {
-        Construction {
-                samples 100000
-                epsilon 0.005
-        }
-
-
-        # random polygon       = 1
-        # axis aligned         = 2
-        # least ray splits     = 256
-        # balanced rays        = 512
-        # pvs                  = 1024
-
-        splitPlaneStrategy 1024
-        
-        # maximal candidates for split planes
-        maxPolyCandidates 50
-        maxRayCandidates 50
-        
-        # maximal tested rays for split cost heuristics
-        maxTests 10000
-        
-        # factors for evaluating split plane costs
-        Factor {
-                leastRaySplits 1.0
-                balancedRays 1.0
-                pvs 1.0
-        }
-        
-        Termination {
-                # parameters used for autopartition
-                minRays                 100
-                minPolygons             -1
-                maxDepth                30
-                minPvs                  100
-                minArea                 0.01
-                maxRayContribution      0.005
-                maxCostRatio            0.9
-                missTolerance           4
-                #maxAccRayLength        100
-                
-                # used for pvs criterium
-                ct_div_ci 0.0
-        
-                # axis aligned splits
-                AxisAligned {
-                        minPolys 5000
-                        minRays 500
-                        minObjects 10
-                        maxCostRatio 0.9
-                        ct_div_ci 0.5
-                }
-        }
-        
-        AxisAligned {
-                splitBorder 0.01
-        }
-        
-        
-        Visualization {
-                # x3d visualization of the split planes
-                exportSplits true
-                exportRays true
-                exportGeometry false
-        }
-}

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1512 +1512 @@
                 "false");
 
-        RegisterOption("VspKdTree.Termination.maxCostRatio",
-                optFloat,
-                "-vsp_kd_term_max_cost_ratio=",
-                "1.5");
-
         RegisterOption("VspKdTree.Termination.missTolerance",
                  optInt,
@@ -1727 +1722 @@
                 "5000");
 
-        RegisterOption("VspBspTree.Visualization.exportSplits",
-                optBool,
-                "-vsp_bsp_visualization.exportSplits",
-                "false");
-
         RegisterOption("VspBspTree.Construction.samples",
                 optInt,
@@ -1746 +1736 @@
                 "-vsp_bsp_visualization.export_splits",
                 "false");
-        RegisterOption("BspTree.Visualization.exportRays",
+        RegisterOption("VspBspTree.Visualization.exportRays",
                 optBool,
                 "-vsp_bsp_visualization.export_rays",

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -175 +175 @@
 
         int constructionSamples = 0;
+        
+        if (strcmp(viewCellsStr, "kdTree") == 0)
+        {
+                mViewCellsManager = new KdViewCellsManager(mKdTree);
+        }
+        else if (strcmp(viewCellsStr, "bspTree") == 0)
+        {
+                mBspTree = new BspTree();
+
+                Debug << "view cell type: Bsp" << endl;
+
+                environment->GetIntValue("BspTree.Construction.samples", constructionSamples);
+                mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples);
+        }
+        else if (strcmp(viewCellsStr, "vspBspTree") == 0)
+        {
+                mVspBspTree = new VspBspTree();
+
+                Debug << "view cell type: VspBsp" << endl;
+
+                environment->GetIntValue("VspBspTree.Construction.samples", constructionSamples);
+                mViewCellsManager = new VspBspViewCellsManager(mVspBspTree, constructionSamples);
+        }
+        else if (strcmp(viewCellsStr, "vspKdTree") == 0)
+        {
+                mVspKdTree = new VspKdTree();           
+        
+                environment->GetIntValue("VspKdTree.Construction.samples", constructionSamples);
+        mViewCellsManager = new VspKdViewCellsManager(mVspKdTree, constructionSamples);
+        }
+        else if (strcmp(viewCellsStr, "sceneDependent") == 0)
+        {
+                //TODO
+                mBspTree = new BspTree();
+
+                Debug << "view cell type: Bsp" << endl;
+                environment->GetIntValue("BspTree.Construction.samples", constructionSamples);
+                mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples);
+        }
+        else
+        {
+                cerr<<"Wrong view cells type" << viewCellsStr << endl;
+                exit(1);
+        }
 
         float objRenderCost = 0, vcOverhead = 0, moveSpeed = 0;
@@ -182 +226 @@
         environment->GetFloatValue("Simulation.moveSpeed", moveSpeed);
 
-        mRenderSimulator = new RenderSimulator(objRenderCost, vcOverhead, moveSpeed);
-        
-        if (strcmp(viewCellsStr, "kdTree") == 0)
-        {
-                mViewCellsManager = new KdViewCellsManager(mKdTree);
-        }
-        else if (strcmp(viewCellsStr, "bspTree") == 0)
-        {
-                mBspTree = new BspTree();
-
-                Debug << "view cell type: Bsp" << endl;
-
-                environment->GetIntValue("BspTree.Construction.samples", constructionSamples);
-                mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples);
-        }
-        else if (strcmp(viewCellsStr, "vspBspTree") == 0)
-        {
-                mVspBspTree = new VspBspTree();
-
-                Debug << "view cell type: VspBsp" << endl;
-
-                environment->GetIntValue("VspBspTree.Construction.samples", constructionSamples);
-                mViewCellsManager = new VspBspViewCellsManager(mVspBspTree, constructionSamples);
-        }
-        else if (strcmp(viewCellsStr, "vspKdTree") == 0)
-        {
-                mVspKdTree = new VspKdTree();           
-        
-                environment->GetIntValue("VspKdTree.Construction.samples", constructionSamples);
-        mViewCellsManager = new VspKdViewCellsManager(mVspKdTree, constructionSamples);
-        }
-        else if (strcmp(viewCellsStr, "sceneDependent") == 0)
-        {
-                //TODO
-                mBspTree = new BspTree();
-
-                Debug << "view cell type: Bsp" << endl;
-                environment->GetIntValue("BspTree.Construction.samples", constructionSamples);
-                mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples);
-        }
-        else
-        {
-                cerr<<"Wrong view cells type" << viewCellsStr << endl;
-                exit(1);
-        }
-
+        mRenderSimulator = 
+                new RenderSimulator(mViewCellsManager, objRenderCost, vcOverhead, moveSpeed);
+        
         int postProcessSamples = 0;
         int visSamples = 0;

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

@@ -26 +26 @@
 }
 
-RenderSimulator::RenderSimulator()
+RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager):
+Renderer(viewCellsManager)
 {}
 
-RenderSimulator::RenderSimulator(float objRenderCost, 
+RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager,
+                                                                 float objRenderCost, 
                                                                  float vcOverhead, 
                                                                  float moveSpeed):
+Renderer(viewCellsManager),
 mObjRenderCost(objRenderCost), 
 mVcOverhead(vcOverhead), 
@@ -75 +78 @@
                 // compute render time of PVS times probability that view point is in view cell
                 const float vcCost = pInVc * mViewCellsManager->GetRendercost(vc, mObjRenderCost);
-                
+        
                 // crossing the border of a view cell is depending on the move speed
                 // and the probability that a view cell border is crossed
@@ -82 +85 @@
                 //-- update statistics
                 renderTime += vcCost;
-
+        
                 if (vcCost > mSimulationStatistics.maxCost)
                         mSimulationStatistics.maxCost = vcCost;

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.h

@@ -48 +48 @@
 
 public:
-        RenderSimulator();
+        RenderSimulator(ViewCellsManager *viewCellsManager);
         /** Constructor taking the estimated render cost, 
                 the view cell overhead,
                 and the average move speed of the player into account.
         */
-        RenderSimulator(float objRendercost, float vcOverhead, float moveSpeed);
+        RenderSimulator(ViewCellsManager *viewCellsManager, 
+                                        float objRendercost, 
+                                        float vcOverhead, 
+                                        float moveSpeed);
 
         /** Sets estimated render time for a single object in the PVS.

trunk/VUT/GtpVisibilityPreprocessor/src/RssPreprocessor.cpp

@@ -397 +397 @@
   
   int totalSamples = 0;
-
-  /// Rays used for post processing and visualizations.
-  RayContainer storedRays;
 
   AxisAlignedBox3 *box = new AxisAlignedBox3(mKdTree->GetBox());
@@ -507 +504 @@
                                           mViewCellsManager->GetVisualizationSamples());
         float p = desired/(float)mVssRays.size();
-        //      rssTree->CollectRays(storedRays, desired);
+        
         for (int i=0; i < mVssRays.size(); i++) {
           if (Random(1.0f) < p)
@@ -520 +517 @@
         if (1) 
           mViewCellsManager->Visualize(mObjects, selectedRays);
-
-        CLEAR_CONTAINER(storedRays);
   }
 

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -151 +151 @@
                 // pickup a random face of each mesh 
                 Mesh *mesh = mi->GetMesh();
-                int face = (int)Random((int)mesh->mFaces.size());
+                int face = (int)RandomValue(0, (int)mesh->mFaces.size() - 1);
                 
                 Polygon3 poly(mesh->mFaces[face], mesh);
                 poly.Scale(1.001f);
                 // now extend a random edge of the face
-                int edge = Random((int)poly.mVertices.size());
+                int edge = (int)RandomValue(0, (int)poly.mVertices.size() - 1);
                 float t = RandomValue(0.0f, 1.0f);
                 Vector3 target = t*poly.mVertices[edge] + (1.0f-t)*poly.mVertices[(edge + 1)%
@@ -192 +192 @@
                 Debug << "Finding random neighbour" << endl;    
                 for (int tries = 0; tries < 10; tries++) {
-                        int index = Random(pvsSize);
+                        int index = (int)RandomValue(0, pvsSize - 1);
                         KdPvsData data;
                         KdNode *node;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -355 +355 @@
 
         app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" 
-                <<      minRaysNodes * 100 / (double)Leaves() << endl;
+                << minRaysNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
+                << maxCostNodes * 100 / (double)Leaves() << endl;
 
         app << "#N_PMINAREALEAVES  ( Percentage of leaves with mininum area )\n"
@@ -412 +415 @@
                 mRoot = new BspLeaf();
 
-        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0, 
-                                                                 mBox.SurfaceArea(), new BspNodeGeometry()));
+        tStack.push(BspTraversalData(mRoot, 
+                                                                 polys, 
+                                                                 0, 
+                                                                 mRootCell, 
+                                                                 new BoundedRayContainer(), 
+                                                                 0, 
+                                                                 mBox.SurfaceArea(), 
+                                                                 new BspNodeGeometry()));
 
         while (!tStack.empty())
@@ -1142 +1151 @@
         if (!data.mPolygons->empty())
                 {
-                        Polygon3 *nextPoly = (*data.mPolygons)[Random((int)data.mPolygons->size())];
+                        Polygon3 *nextPoly = (*data.mPolygons)[(int)RandomValue(0, (int)data.mPolygons->size() - 1)];
                         return nextPoly->GetSupportingPlane();
                 }
                 else
                 {
-                        const int candidateIdx = Random((int)data.mRays->size());
+                        const int candidateIdx = (int)RandomValue(0, (int)data.mRays->size() - 1);
                         BoundedRay *bRay = (*data.mRays)[candidateIdx];
 
@@ -1177 +1186 @@
         int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
         
-        int candidateIdx = limit;
+        int candidateIdx = limit - 1;
 
         for (int i = 0; i < limit; ++ i)
@@ -1207 +1216 @@
         for (int i = 0; i < mMaxRayCandidates / 2; ++ i)
         {
-                candidateIdx = Random((int)rays->size());
+                candidateIdx = (int)RandomValue(0, (int)rays->size() - 1);
                 BoundedRay *bRay = (*rays)[candidateIdx];
 
@@ -1242 +1251 @@
                 for (int j = 0; j < 3; j ++)
                 {
-                        idx[j] = Random((int)rays->size() * 2);
+                        idx[j] = (int)RandomValue(0, (int)rays->size() * 2 - 1);
                                 
                         if (idx[j] >= (int)rays->size())
@@ -1279 +1288 @@
 int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
 {
-        const int candidateIdx = Random(currentIdx --);
+        const int candidateIdx = (int)RandomValue(0, currentIdx --);
 
         // swap candidates to avoid testing same plane 2 times
@@ -1285 +1294 @@
         
         return currentIdx;
-        //return Random((int)polys.size());
+        //return (int)RandomValue(0, (int)polys.size() - 1);
 }
 
@@ -1329 +1338 @@
         for (int i = 0; i < limit; ++ i)
         {
-                const int testIdx = useRand ? Random(limit) : i;
+                const int testIdx = useRand ? (int)RandomValue(0, limit - 1) : i;
 
                 Polygon3 *poly = polys[testIdx];
@@ -1494 +1503 @@
         for (int i = 0; i < limit; ++ i)
         {
-                const int testIdx = useRand ? Random(limit) : i;
+                const int testIdx = useRand ? (int)RandomValue(0, limit - 1) : i;
         
                 BoundedRay *bRay = rays[testIdx];
@@ -2076 +2085 @@
 {
         int splits = 0;
-
+        
         while (!rays.empty())
         {

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -102 +102 @@
         // minimum area nodes
         int minAreaNodes;
-
+        /// nodes termination because of max cost ratio;
+        int maxCostNodes;
         // max number of rays per node
         int maxObjectRefs;
@@ -144 +145 @@
                 maxRayContribNodes = 0;
                 minAreaNodes = 0;
+                maxCostNodes = 0;
 
                 contributingSamples = 0;
@@ -346 +348 @@
         
         typedef std::stack<BspTraversalData> BspTraversalStack;
-        //typedef std::priority_queue<BspTraversalData> BspTraversalStack;
-
-        /** Default constructor creating an empty tree.
+        
+        /** Default constructor reading the environment file and 
+                creating an empty tree.
         */ 
         BspTree();
-        
+        /** Destroys tree and nodes.
+        */
         ~BspTree();
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -266 +266 @@
                                                                   VssRayContainer &savedRays) const
 {
-        const int limit = min (mConstructionSamples, (int)sourceRays.size());
-
+        const int limit = min(mConstructionSamples, (int)sourceRays.size());
+
+        Debug << "size: " << sourceRays.size() << " limit " << limit << endl;
         VssRayContainer::const_iterator it, it_end = sourceRays.end();
+        
+        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
 
         for (it = sourceRays.begin(); it != it_end; ++ it)
         {
-                if (Random((int)constructionRays.size()) > limit)
+                if (Random(1.0f) < prop)
                         constructionRays.push_back(*it);
                 else
@@ -350 +353 @@
         VssRayContainer::const_iterator it, it_end = rays.end();
 
+        const float prop = (float)limit / ((float)rays.size() + Limits::Small);
+
         for (it = rays.begin(); it != it_end; ++ it)
         {
-                if (Random((int)constructionRays.size()) > limit)
+                if (Random(1.0f) < prop)
                         constructionRays.push_back(new Ray(*(*it)));
                 else
@@ -602 +607 @@
                 bool exportGeometry = false;
 
-                environment->GetBoolValue("BspViewCellsManager.Visualization.exportRays", exportRays);
-                environment->GetBoolValue("BspViewCellsManager.Visualization.exportGeometry", exportGeometry);
+                environment->GetBoolValue("BspTree.Visualization.exportRays", exportRays);
+                environment->GetBoolValue("BspTree.Visualization.exportGeometry", exportGeometry);
 
                 // export rays
@@ -1186 +1191 @@
 
         mVspKdTree->Construct(constructionRays, sceneBbox);
-
+        
         // collect view cells
         mVspKdTree->CollectViewCells(mViewCells);
@@ -1227 +1232 @@
         bool exportGeometry = false;
 
-        environment->GetBoolValue("BspViewCellsManager.Visualization.exportRays", exportRays);
-        environment->GetBoolValue("BspViewCellsManager.Visualization.exportGeometry", exportGeometry);
+        environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays);
+        environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry);
 
         if (!ViewCellsConstructed())
@@ -1278 +1283 @@
 
                         // export geometry
-                        VspKdLeaf *leaf = leafContainer[Random((int)leafContainer.size())]; 
+                        VspKdLeaf *leaf = leafContainer[(int)RandomValue(0.0, (Real)((int)leafContainer.size() - 1))]; 
                         AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
 
@@ -1409 +1414 @@
                 return 0;
 
-        Debug << "Constructing bsp view cells" << endl;
+        Debug << "Constructing vsp bsp view cells" << endl;
 
         int sampleContributions = 0;
@@ -1417 +1422 @@
 
         GetRaySets(rays, constructionRays, savedRays);
-
+        Debug << "rays " << rays.size() << " construction rays " << constructionRays.size() << endl;
         mVspBspTree->Construct(constructionRays);
+        
         mVspBspTree->CollectViewCells(mViewCells);
         
@@ -1433 +1439 @@
                                                                                 const VssRayContainer &rays)
 {
+        Debug << "Post processing view cells" << endl;
         if (!ViewCellsConstructed())
         {
@@ -1438 +1445 @@
                 return 0;
         }
-
 
         //-- post processing of bsp view cells
@@ -1625 +1631 @@
         bool exportGeometry = false;
 
-        environment->GetBoolValue("BspViewCellsManager.Visualization.exportRays", exportRays);
-        environment->GetBoolValue("BspViewCellsManager.Visualization.exportGeometry", exportGeometry);
+        Debug << "here344" << endl;
+        environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays);
+        environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry);
 
         const int leafOut = 10;
@@ -1667 +1674 @@
                         }
 #endif
-
                         Intersectable::NewMail();
 
@@ -1837 +1843 @@
                 }
         }
+        Debug << "here222211" << endl;
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -75 +75 @@
         environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
 
-    Debug << "BSP max depth: " << mTermMaxDepth << endl;
-        Debug << "BSP min PVS: " << mTermMinPvs << endl;
-        Debug << "BSP min area: " << mTermMinArea << endl;
-        Debug << "BSP min rays: " << mTermMinRays << endl;
-        Debug << "BSP max polygon candidates: " << mMaxPolyCandidates << endl;
-        Debug << "BSP max plane candidates: " << mMaxRayCandidates << endl;
+        // maximum number of view cells
+        environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
+
+        //--
+        Debug << "******* VSP BSP options ******** " << endl;
+    Debug << "max depth: " << mTermMaxDepth << endl;
+        Debug << "min PVS: " << mTermMinPvs << endl;
+        Debug << "min area: " << mTermMinArea << endl;
+        Debug << "min rays: " << mTermMinRays << endl;
+        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
+        //Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl;
+        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
+        Debug << "miss tolerance: " << mTermMissTolerance << endl;
+        Debug << "max view cells: " << mMaxViewCells << endl;
+        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
+        Debug << "max plane candidates: " << mMaxRayCandidates << endl;
 
         Debug << "Split plane strategy: ";
@@ -310 +320 @@
 
                 if (r == mRoot)
-                        Debug << "BSP tree construction time spent at root: " 
+                        Debug << "VSP BSP tree construction time spent at root: " 
                                   << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
         }
@@ -319 +329 @@
 }
 
-bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
+bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data, 
+                                                                                const int numLeaves) const
 {
         return 
                 (((int)data.mRays->size() <= mTermMinRays) ||
-                 (data.mPvs <= mTermMinPvs) ||
+                 (data.mPvs <= mTermMinPvs)   ||
                  (data.mArea <= mTermMinArea) ||
+                 (numLeaves >= mMaxViewCells) ||
                 // (data.GetAvgRayContribution() >= mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
@@ -332 +344 @@
                                                            VspBspTraversalData &tData)
 {
+        BspNode *newNode = tData.mNode;
+
+        if (!TerminationCriteriaMet(tData, (int)tStack.size()))
+        {
+                PolygonContainer coincident;
+        
+                VspBspTraversalData tFrontData;
+                VspBspTraversalData tBackData;
+
+                // create new interior node and two leaf nodes
+                // or return leaf as it is (if maxCostRatio missed)
+                newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
+
+                if (!newNode->IsLeaf()) //-- continue subdivision
+                {
+                        // push the children on the stack
+                        tStack.push(tFrontData);
+                        tStack.push(tBackData);
+
+                        // delete old leaf node
+                        DEL_PTR(tData.mNode);   
+                }
+        }
+        
         //-- terminate traversal  
-        if (TerminationCriteriaMet(tData))              
-        {
-                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
-        
+        if (newNode->IsLeaf())
+        {
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+        
+                // create new view cell for this leaf
                 BspViewCell *viewCell = new BspViewCell();
-                
                 leaf->SetViewCell(viewCell);
                 viewCell->mLeaves.push_back(leaf);
 
-                //-- add pvs
-                if (viewCell != mRootCell)
-                {
-                        int conSamp = 0, sampCon = 0;
-                        AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
+                //-- update pvs
+                int conSamp = 0, sampCon = 0;
+                AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
                         
-                        mStat.contributingSamples += conSamp;
-                        mStat.sampleContributions += sampCon;
-                }
-
+                mStat.contributingSamples += conSamp;
+                mStat.sampleContributions += sampCon;
+                
                 EvaluateLeafStats(tData);
-        
-                //-- clean up   
-                DEL_PTR(tData.mPolygons);
-                DEL_PTR(tData.mRays);
-                DEL_PTR(tData.mGeometry);
-
-                return leaf;
-        }
-
-        //-- continue subdivision
-        PolygonContainer coincident;
-        
-        VspBspTraversalData tFrontData(new PolygonContainer(), 
-                                                                   tData.mDepth + 1,
-                                                                   new RayInfoContainer(), 
-                                                                   new BspNodeGeometry());
-
-        VspBspTraversalData tBackData(new PolygonContainer(), 
-                                                                  tData.mDepth + 1,
-                                                                  new RayInfoContainer(), 
-                                                                  new BspNodeGeometry());
-
-        // create new interior node and two leaf nodes
-        BspNode *newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
-
-        // subdivide further
-        if (!newNode->IsLeaf())
-        {
-                BspInterior *interior = dynamic_cast<BspInterior *>(newNode);
-                
-#ifdef _DEBUG   
-//      if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
-//      {       for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it)
-//                      Debug << (*it) << " " << (*it)->GetArea() << " " << (*it)->mParent << endl ;
-//              Debug << endl;}
-#endif
-
-                // push the children on the stack
-                tStack.push(tFrontData);
-                tStack.push(tBackData);
-
-                // delete old leaf node
-                DEL_PTR(tData.mNode);   
-        }
-
-        // cleanup
+        }
+        
+                
+        //-- cleanup
         DEL_PTR(tData.mPolygons);
         DEL_PTR(tData.mRays);
@@ -411 +402 @@
                                                                    PolygonContainer &coincident)
 {
-        mStat.nodes += 2;
-        
         BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
-        
+
         int maxCostMisses = tData.mMaxCostMisses;
 
@@ -423 +412 @@
                 ++ maxCostMisses;
 
-                if (maxCostMisses >= mTermMissTolerance)
+                /*if (maxCostMisses >= mTermMissTolerance)
+                {
+                        // terminate branch because of max cost
+                        ++ mStat.maxCostNodes; 
             return leaf;
-        }
-
-        // subdivide further
+                }*/
+        }
+
+        mStat.nodes += 2;
+
+        //-- subdivide further
         BspInterior *interior = new BspInterior(splitPlane); 
 
@@ -434 +429 @@
 #endif
         
-        // subdivide rays into front and back rays
+        //-- the front and back traversal data is filled with the new values
+        frontData.mPolygons = new PolygonContainer();
+        frontData.mDepth = tData.mDepth + 1;
+        frontData.mRays = new RayInfoContainer();
+        frontData.mGeometry = new BspNodeGeometry();
+
+        backData.mPolygons = new PolygonContainer();
+        backData.mDepth = tData.mDepth + 1;
+        backData.mRays = new RayInfoContainer();
+        backData.mGeometry = new BspNodeGeometry();
+
+        // subdivide rays
         SplitRays(interior->GetPlane(), 
                           *tData.mRays, 
@@ -440 +446 @@
                           *backData.mRays);
         
-        // subdivide polygons with plane
+        // subdivide polygons
         mStat.splits += SplitPolygons(interior->GetPlane(),
                                                                   *tData.mPolygons, 
@@ -447 +453 @@
                                                                   coincident);
 
-    
-        //-- set left and right traversal data
+        
+        // how often was max cost ratio missed in this branch?
         frontData.mMaxCostMisses = maxCostMisses;
         backData.mMaxCostMisses = maxCostMisses;
@@ -464 +470 @@
                                                                            mBox,
                                                                            mEpsilon);
-                        
+        
                 // area is normalized with view space area
                 frontData.mArea = frontData.mGeometry->GetArea() / mBox.SurfaceArea();
@@ -494 +500 @@
         frontData.mNode = interior->GetFront();
         backData.mNode = interior->GetBack();
-        
+
         //DEL_PTR(leaf);
         return interior;
@@ -536 +542 @@
                                                                          vector<SortableEntry> &splitCandidates) const
 {
-  splitCandidates.clear();
+        splitCandidates.clear();
   
-  int requestedSize = 2 * (int)polys.size();
-  // creates a sorted split candidates array  
-  splitCandidates.reserve(requestedSize);
+        const int requestedSize = 2 * (int)polys.size();
+        
+        // creates a sorted split candidates array  
+        splitCandidates.reserve(requestedSize);
   
-  PolygonContainer::const_iterator it, it_end = polys.end();
-
-  AxisAlignedBox3 box;
-
-  // insert all queries 
-  for(it = polys.begin(); it != it_end; ++ it)
-  {
-          box.Initialize();
-          box.Include(*(*it));
+        PolygonContainer::const_iterator it, it_end = polys.end();
+
+        AxisAlignedBox3 box;
+
+        // insert all queries 
+        for(it = polys.begin(); it != it_end; ++ it)
+        {
+                box.Initialize();
+                box.Include(*(*it));
           
-          splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
-      splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
-  }
+                splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
+                splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
+        }
   
-  stable_sort(splitCandidates.begin(), splitCandidates.end());
+        stable_sort(splitCandidates.begin(), splitCandidates.end());
 }
 
@@ -687 +694 @@
         if (!data.mPolygons->empty())
                 {
-                        const int randIdx = Random((int)data.mPolygons->size());
+                        const int randIdx = (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
                         Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
 
@@ -696 +703 @@
                 {
                         //-- choose plane on midpoint of a ray
-                        const int candidateIdx = Random((int)data.mRays->size());
+                        const int candidateIdx = (int)RandomValue(0, (Real)((int)data.mRays->size() - 1));
                                                                         
                         const Vector3 minPt = (*data.mRays)[candidateIdx].ExtrapOrigin();
@@ -716 +723 @@
 }
 
+Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
+{       
+        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 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
+{       
+        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 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
+{       
+        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);
+}
+
 bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane, 
                                                                            BspLeaf *leaf, 
@@ -725 +803 @@
 
         const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
-        int candidateIdx = limit;
+        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
@@ -747 +832 @@
 
         //-- choose candidate planes extracted from rays
-        // we currently use different two methods chosen with
+        // we use different methods chosen with
         // equal probability
-        
-        // take 3 ray endpoints, where two are minimum and one a maximum
-        // point or the other way round
-        for (int i = 0; i < mMaxRayCandidates / 2; ++ i)
-        {
-                candidateIdx = Random((int)data.mRays->size());
-        
-                RayInfo rayInf = (*data.mRays)[candidateIdx];
-
-                const Vector3 minPt = rayInf.ExtrapOrigin();
-                const Vector3 maxPt = rayInf.ExtrapTermination();
-
-                const Vector3 pt = (maxPt + minPt) * 0.5;
-                const Vector3 normal = Normalize(rayInf.mRay->GetDir());
-
-                plane = Plane3(normal, pt);
+        for (int i = 0; i < mMaxRayCandidates; ++ i)
+        {
+                plane = ChooseCandidatePlane3(*data.mRays);
 
                 const float candidateCost = SplitPlaneCost(plane, data);
@@ -774 +846 @@
                 }
         }
-
-        // take plane normal as plane normal and the midpoint of the ray.
-        // PROBLEM: does not resemble any point where visibility is likely to change
-        //Debug << "lowest2: " << 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] = Random((int)data.mRays->size() * 2);
-                                
-                        if (idx[j] >= (int)data.mRays->size())
-                        {
-                                idx[j] -= (int)data.mRays->size();
-                                
-                                chooseMin = (cminT < 2);
-                        }
-                        else
-                                chooseMin = (cmaxT < 2);
-
-                        RayInfo rayInf = (*data.mRays)[idx[j]];
-                        pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
-                }       
-                        
-                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;
-                }
-        }       
 
         // cost ratio miss
@@ -825 +856 @@
 
         return true;
-}
-
-int VspBspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
-{
-        const int candidateIdx = Random(currentIdx --);
-
-        // swap candidates to avoid testing same plane 2 times
-        std::swap(polys[currentIdx], polys[candidateIdx]);
-        
-        return currentIdx;
-        //return Random((int)polys.size());
 }
 
@@ -905 +925 @@
         for (int i = 0; i < limit; ++ i)
         {
-                const int testIdx = useRand ? Random(limit) : i;
+                const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i;
                 RayInfo rayInf = (*data.mRays)[testIdx];
 
@@ -1353 +1373 @@
         {
                 RayInfo bRay = rays.back();
+                rays.pop_back();
+
                 VssRay *ray = bRay.mRay;
-
-                rays.pop_back();
                 float t;
-                // get classification and receive new t
+
+                        // get classification and receive new t
                 const int cf = bRay.ComputeRayIntersection(plane, t);
-
+        
                 switch (cf)
                 {
@@ -1370 +1391 @@
                 case 0: 
                         //-- split ray
-
-                        // if start point behind plane
+                        //--  look if start point behind or in front of plane
                         if (plane.Side(bRay.ExtrapOrigin()) <= 0)
                         {       

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -60 +60 @@
                 /// how often this branch has missed the max-cost ratio
                 int mMaxCostMisses;
+
+
                 /** Returns average ray contribution.
                 */
@@ -80 +82 @@
                 
                 VspBspTraversalData(BspNode *node, 
-                                                 PolygonContainer *polys, 
-                                                 const int depth, 
-                                                 RayInfoContainer *rays,
-                                                 int pvs,
-                                                 float area,
-                                                 BspNodeGeometry *geom): 
+                                                        PolygonContainer *polys, 
+                                                        const int depth, 
+                                                        RayInfoContainer *rays,
+                                                        int pvs,
+                                                        float area,
+                                                        BspNodeGeometry *geom): 
                 mNode(node), 
                 mPolygons(polys), 
@@ -359 +361 @@
         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);
-        
         /** Computes best cost ratio for the suface area heuristics for axis aligned
                 splits. This heuristics minimizes the cost for ray traversal.
@@ -431 +427 @@
         /** Returns true if tree can be terminated.
         */
-        inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const;
+        inline bool TerminationCriteriaMet(const VspBspTraversalData &data, const int numLeaves) const;
 
         /** Computes accumulated ray lenght of this rays.
@@ -465 +461 @@
 
 
-
+        /** Take 3 ray endpoints, where two are minimum and one a maximum
+                point or the other way round.
+        */
+        Plane3 ChooseCandidatePlane(const RayInfoContainer &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 RayInfoContainer &rays) const;
+
+        /** Fit the plane between the two lines so that the plane has equal shortest 
+                distance to both lines.
+        */
+        Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
   
         /// Pointer to the root of the tree
@@ -537 +546 @@
         /// number of different bsp split plane criteria
         int mNumCriteria;
+        /// maximal number of view cells
+        int mMaxViewCells;
 
 private:

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -382 +382 @@
         Debug << "min rays: "<< mTermMinRays << endl;
         Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
-        Debug << "max cost ratio: "<< mTermMaxCostRatio << endl;
-        Debug << "min size: "<<mTermMinSize << endl;
+        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
+        Debug << "min size: " << mTermMinSize << endl;
 
         if (name.compare("regular") == 0)
@@ -2310 +2310 @@
 
 
+void VspKdTree::RefineViewCells()
+{
+}
+
+
 /*********************************************************************/
 /*                MergeCandidate implementation                      */

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -601 +601 @@
         void EvaluateViewCellsStats(ViewCellsStatistics &stat) const;
 
+        /** Refines view cells in a post processing step.
+        */
+        void RefineViewCells();
+
 protected:
 

trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

@@ -562 +562 @@
         mViewCellsManager->Visualize(mObjects, storedRays);
 
-        CLEAR_CONTAINER(storedRays);
-  }
-
-  //-- render simulation after merge
-  cout << "\nevaluating bsp view cells render time after merge ... ";
+        Debug << "here2" << endl;
+  }
 
   //-- render simulation after merge
@@ -572 +569 @@
   
   mRenderSimulator->RenderScene();
+  Debug << "here3" << endl;
   SimulationStatistics ss;
   mRenderSimulator->GetStatistics(ss);
-
+  Debug << "here244" << endl;
   cout << " finished" << endl;
   cout << ss << endl;
   Debug << ss << endl;
 
-
   delete vssTree;
 
+  Debug << "here4" << endl;
   return true;
 }

trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.cpp

@@ -1720 +1720 @@
   for (int i=0; i < numberOfRays; i++) {
         // pickup 3 random rays
-        int r1 = Random(nrays-1);
-        int r2 = Random(nrays-1);
-        int r3 = Random(nrays-1);
+        int r1 = (int)RandomValue(0, nrays-1);
+        int r2 = (int)RandomValue(0, nrays-1);
+        int r3 = (int)RandomValue(0, nrays-1);
                 
         Vector3 o1 = leaf->rays[r1].Extrap(RandomValue(leaf->rays[r1].GetMinT(),