Ignore:
Timestamp:
12/20/05 20:33:42 (19 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/src
Files:
15 edited

Legend:

Unmodified
Added
Removed

  • trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

    r472 r473  
    15121512                "false"); 
    15131513 
    1514         RegisterOption("VspKdTree.Termination.maxCostRatio", 
    1515                 optFloat, 
    1516                 "-vsp_kd_term_max_cost_ratio=", 
    1517                 "1.5"); 
    1518  
    15191514        RegisterOption("VspKdTree.Termination.missTolerance", 
    15201515                 optInt, 
    … …  
    17271722                "5000"); 
    17281723 
    1729         RegisterOption("VspBspTree.Visualization.exportSplits", 
    1730                 optBool, 
    1731                 "-vsp_bsp_visualization.exportSplits", 
    1732                 "false"); 
    1733  
    17341724        RegisterOption("VspBspTree.Construction.samples", 
    17351725                optInt, 
    … …  
    17461736                "-vsp_bsp_visualization.export_splits", 
    17471737                "false"); 
    1748         RegisterOption("BspTree.Visualization.exportRays", 
     1738        RegisterOption("VspBspTree.Visualization.exportRays", 
    17491739                optBool, 
    17501740                "-vsp_bsp_visualization.export_rays", 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

    r469 r473  
    175175 
    176176        int constructionSamples = 0; 
     177         
     178        if (strcmp(viewCellsStr, "kdTree") == 0) 
     179        { 
     180                mViewCellsManager = new KdViewCellsManager(mKdTree); 
     181        } 
     182        else if (strcmp(viewCellsStr, "bspTree") == 0) 
     183        { 
     184                mBspTree = new BspTree(); 
     185 
     186                Debug << "view cell type: Bsp" << endl; 
     187 
     188                environment->GetIntValue("BspTree.Construction.samples", constructionSamples); 
     189                mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples); 
     190        } 
     191        else if (strcmp(viewCellsStr, "vspBspTree") == 0) 
     192        { 
     193                mVspBspTree = new VspBspTree(); 
     194 
     195                Debug << "view cell type: VspBsp" << endl; 
     196 
     197                environment->GetIntValue("VspBspTree.Construction.samples", constructionSamples); 
     198                mViewCellsManager = new VspBspViewCellsManager(mVspBspTree, constructionSamples); 
     199        } 
     200        else if (strcmp(viewCellsStr, "vspKdTree") == 0) 
     201        { 
     202                mVspKdTree = new VspKdTree();            
     203         
     204                environment->GetIntValue("VspKdTree.Construction.samples", constructionSamples); 
     205        mViewCellsManager = new VspKdViewCellsManager(mVspKdTree, constructionSamples); 
     206        } 
     207        else if (strcmp(viewCellsStr, "sceneDependent") == 0) 
     208        { 
     209                //TODO 
     210                mBspTree = new BspTree(); 
     211 
     212                Debug << "view cell type: Bsp" << endl; 
     213                environment->GetIntValue("BspTree.Construction.samples", constructionSamples); 
     214                mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples); 
     215        } 
     216        else 
     217        { 
     218                cerr<<"Wrong view cells type" << viewCellsStr << endl; 
     219                exit(1); 
     220        } 
    177221 
    178222        float objRenderCost = 0, vcOverhead = 0, moveSpeed = 0; 
    … …  
    182226        environment->GetFloatValue("Simulation.moveSpeed", moveSpeed); 
    183227 
    184         mRenderSimulator = new RenderSimulator(objRenderCost, vcOverhead, moveSpeed); 
    185          
    186         if (strcmp(viewCellsStr, "kdTree") == 0) 
    187         { 
    188                 mViewCellsManager = new KdViewCellsManager(mKdTree); 
    189         } 
    190         else if (strcmp(viewCellsStr, "bspTree") == 0) 
    191         { 
    192                 mBspTree = new BspTree(); 
    193  
    194                 Debug << "view cell type: Bsp" << endl; 
    195  
    196                 environment->GetIntValue("BspTree.Construction.samples", constructionSamples); 
    197                 mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples); 
    198         } 
    199         else if (strcmp(viewCellsStr, "vspBspTree") == 0) 
    200         { 
    201                 mVspBspTree = new VspBspTree(); 
    202  
    203                 Debug << "view cell type: VspBsp" << endl; 
    204  
    205                 environment->GetIntValue("VspBspTree.Construction.samples", constructionSamples); 
    206                 mViewCellsManager = new VspBspViewCellsManager(mVspBspTree, constructionSamples); 
    207         } 
    208         else if (strcmp(viewCellsStr, "vspKdTree") == 0) 
    209         { 
    210                 mVspKdTree = new VspKdTree();            
    211          
    212                 environment->GetIntValue("VspKdTree.Construction.samples", constructionSamples); 
    213         mViewCellsManager = new VspKdViewCellsManager(mVspKdTree, constructionSamples); 
    214         } 
    215         else if (strcmp(viewCellsStr, "sceneDependent") == 0) 
    216         { 
    217                 //TODO 
    218                 mBspTree = new BspTree(); 
    219  
    220                 Debug << "view cell type: Bsp" << endl; 
    221                 environment->GetIntValue("BspTree.Construction.samples", constructionSamples); 
    222                 mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples); 
    223         } 
    224         else 
    225         { 
    226                 cerr<<"Wrong view cells type" << viewCellsStr << endl; 
    227                 exit(1); 
    228         } 
    229  
     228        mRenderSimulator =  
     229                new RenderSimulator(mViewCellsManager, objRenderCost, vcOverhead, moveSpeed); 
     230         
    230231        int postProcessSamples = 0; 
    231232        int visSamples = 0; 

  • trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

    r468 r473  
    2626} 
    2727 
    28 RenderSimulator::RenderSimulator() 
     28RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager): 
     29Renderer(viewCellsManager) 
    2930{} 
    3031 
    31 RenderSimulator::RenderSimulator(float objRenderCost,  
     32RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager, 
     33                                                                 float objRenderCost,  
    3234                                                                 float vcOverhead,  
    3335                                                                 float moveSpeed): 
     36Renderer(viewCellsManager), 
    3437mObjRenderCost(objRenderCost),  
    3538mVcOverhead(vcOverhead),  
    … …  
    7578                // compute render time of PVS times probability that view point is in view cell 
    7679                const float vcCost = pInVc * mViewCellsManager->GetRendercost(vc, mObjRenderCost); 
    77                  
     80         
    7881                // crossing the border of a view cell is depending on the move speed 
    7982                // and the probability that a view cell border is crossed 
    … …  
    8285                //-- update statistics 
    8386                renderTime += vcCost; 
    84  
     87         
    8588                if (vcCost > mSimulationStatistics.maxCost) 
    8689                        mSimulationStatistics.maxCost = vcCost; 

  • trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.h

    r468 r473  
    4848 
    4949public: 
    50         RenderSimulator(); 
     50        RenderSimulator(ViewCellsManager *viewCellsManager); 
    5151        /** Constructor taking the estimated render cost,  
    5252                the view cell overhead, 
    5353                and the average move speed of the player into account. 
    5454        */ 
    55         RenderSimulator(float objRendercost, float vcOverhead, float moveSpeed); 
     55        RenderSimulator(ViewCellsManager *viewCellsManager,  
     56                                        float objRendercost,  
     57                                        float vcOverhead,  
     58                                        float moveSpeed); 
    5659 
    5760        /** Sets estimated render time for a single object in the PVS. 

  • trunk/VUT/GtpVisibilityPreprocessor/src/RssPreprocessor.cpp

    r469 r473  
    397397   
    398398  int totalSamples = 0; 
    399  
    400   /// Rays used for post processing and visualizations. 
    401   RayContainer storedRays; 
    402399 
    403400  AxisAlignedBox3 *box = new AxisAlignedBox3(mKdTree->GetBox()); 
    … …  
    507504                                          mViewCellsManager->GetVisualizationSamples()); 
    508505        float p = desired/(float)mVssRays.size(); 
    509         //      rssTree->CollectRays(storedRays, desired); 
     506         
    510507        for (int i=0; i < mVssRays.size(); i++) { 
    511508          if (Random(1.0f) < p) 
    … …  
    520517        if (1)  
    521518          mViewCellsManager->Visualize(mObjects, selectedRays); 
    522  
    523         CLEAR_CONTAINER(storedRays); 
    524519  } 
    525520 

  • trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

    r469 r473  
    151151                // pickup a random face of each mesh  
    152152                Mesh *mesh = mi->GetMesh(); 
    153                 int face = (int)Random((int)mesh->mFaces.size()); 
     153                int face = (int)RandomValue(0, (int)mesh->mFaces.size() - 1); 
    154154                 
    155155                Polygon3 poly(mesh->mFaces[face], mesh); 
    156156                poly.Scale(1.001f); 
    157157                // now extend a random edge of the face 
    158                 int edge = Random((int)poly.mVertices.size()); 
     158                int edge = (int)RandomValue(0, (int)poly.mVertices.size() - 1); 
    159159                float t = RandomValue(0.0f, 1.0f); 
    160160                Vector3 target = t*poly.mVertices[edge] + (1.0f-t)*poly.mVertices[(edge + 1)% 
    … …  
    192192                Debug << "Finding random neighbour" << endl;     
    193193                for (int tries = 0; tries < 10; tries++) { 
    194                         int index = Random(pvsSize); 
     194                        int index = (int)RandomValue(0, pvsSize - 1); 
    195195                        KdPvsData data; 
    196196                        KdNode *node; 

  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r472 r473  
    355355 
    356356        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n"  
    357                 <<      minRaysNodes * 100 / (double)Leaves() << endl; 
     357                << minRaysNodes * 100 / (double)Leaves() << endl; 
     358 
     359        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n" 
     360                << maxCostNodes * 100 / (double)Leaves() << endl; 
    358361 
    359362        app << "#N_PMINAREALEAVES  ( Percentage of leaves with mininum area )\n" 
    … …  
    412415                mRoot = new BspLeaf(); 
    413416 
    414         tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0,  
    415                                                                  mBox.SurfaceArea(), new BspNodeGeometry())); 
     417        tStack.push(BspTraversalData(mRoot,  
     418                                                                 polys,  
     419                                                                 0,  
     420                                                                 mRootCell,  
     421                                                                 new BoundedRayContainer(),  
     422                                                                 0,  
     423                                                                 mBox.SurfaceArea(),  
     424                                                                 new BspNodeGeometry())); 
    416425 
    417426        while (!tStack.empty()) 
    … …  
    11421151        if (!data.mPolygons->empty()) 
    11431152                { 
    1144                         Polygon3 *nextPoly = (*data.mPolygons)[Random((int)data.mPolygons->size())]; 
     1153                        Polygon3 *nextPoly = (*data.mPolygons)[(int)RandomValue(0, (int)data.mPolygons->size() - 1)]; 
    11451154                        return nextPoly->GetSupportingPlane(); 
    11461155                } 
    11471156                else 
    11481157                { 
    1149                         const int candidateIdx = Random((int)data.mRays->size()); 
     1158                        const int candidateIdx = (int)RandomValue(0, (int)data.mRays->size() - 1); 
    11501159                        BoundedRay *bRay = (*data.mRays)[candidateIdx]; 
    11511160 
    … …  
    11771186        int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates); 
    11781187         
    1179         int candidateIdx = limit; 
     1188        int candidateIdx = limit - 1; 
    11801189 
    11811190        for (int i = 0; i < limit; ++ i) 
    … …  
    12071216        for (int i = 0; i < mMaxRayCandidates / 2; ++ i) 
    12081217        { 
    1209                 candidateIdx = Random((int)rays->size()); 
     1218                candidateIdx = (int)RandomValue(0, (int)rays->size() - 1); 
    12101219                BoundedRay *bRay = (*rays)[candidateIdx]; 
    12111220 
    … …  
    12421251                for (int j = 0; j < 3; j ++) 
    12431252                { 
    1244                         idx[j] = Random((int)rays->size() * 2); 
     1253                        idx[j] = (int)RandomValue(0, (int)rays->size() * 2 - 1); 
    12451254                                 
    12461255                        if (idx[j] >= (int)rays->size()) 
    … …  
    12791288int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys) 
    12801289{ 
    1281         const int candidateIdx = Random(currentIdx --); 
     1290        const int candidateIdx = (int)RandomValue(0, currentIdx --); 
    12821291 
    12831292        // swap candidates to avoid testing same plane 2 times 
    … …  
    12851294         
    12861295        return currentIdx; 
    1287         //return Random((int)polys.size()); 
     1296        //return (int)RandomValue(0, (int)polys.size() - 1); 
    12881297} 
    12891298 
    … …  
    13291338        for (int i = 0; i < limit; ++ i) 
    13301339        { 
    1331                 const int testIdx = useRand ? Random(limit) : i; 
     1340                const int testIdx = useRand ? (int)RandomValue(0, limit - 1) : i; 
    13321341 
    13331342                Polygon3 *poly = polys[testIdx]; 
    … …  
    14941503        for (int i = 0; i < limit; ++ i) 
    14951504        { 
    1496                 const int testIdx = useRand ? Random(limit) : i; 
     1505                const int testIdx = useRand ? (int)RandomValue(0, limit - 1) : i; 
    14971506         
    14981507                BoundedRay *bRay = rays[testIdx]; 
    … …  
    20762085{ 
    20772086        int splits = 0; 
    2078  
     2087         
    20792088        while (!rays.empty()) 
    20802089        { 

  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r472 r473  
    102102        // minimum area nodes 
    103103        int minAreaNodes; 
    104  
     104        /// nodes termination because of max cost ratio; 
     105        int maxCostNodes; 
    105106        // max number of rays per node 
    106107        int maxObjectRefs; 
    … …  
    144145                maxRayContribNodes = 0; 
    145146                minAreaNodes = 0; 
     147                maxCostNodes = 0; 
    146148 
    147149                contributingSamples = 0; 
    … …  
    346348         
    347349        typedef std::stack<BspTraversalData> BspTraversalStack; 
    348         //typedef std::priority_queue<BspTraversalData> BspTraversalStack; 
    349  
    350         /** Default constructor creating an empty tree. 
     350         
     351        /** Default constructor reading the environment file and  
     352                creating an empty tree. 
    351353        */  
    352354        BspTree(); 
    353          
     355        /** Destroys tree and nodes. 
     356        */ 
    354357        ~BspTree(); 
    355358 

  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

    r471 r473  
    266266                                                                  VssRayContainer &savedRays) const 
    267267{ 
    268         const int limit = min (mConstructionSamples, (int)sourceRays.size()); 
    269  
     268        const int limit = min(mConstructionSamples, (int)sourceRays.size()); 
     269 
     270        Debug << "size: " << sourceRays.size() << " limit " << limit << endl; 
    270271        VssRayContainer::const_iterator it, it_end = sourceRays.end(); 
     272         
     273        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small); 
    271274 
    272275        for (it = sourceRays.begin(); it != it_end; ++ it) 
    273276        { 
    274                 if (Random((int)constructionRays.size()) > limit) 
     277                if (Random(1.0f) < prop) 
    275278                        constructionRays.push_back(*it); 
    276279                else 
    … …  
    350353        VssRayContainer::const_iterator it, it_end = rays.end(); 
    351354 
     355        const float prop = (float)limit / ((float)rays.size() + Limits::Small); 
     356 
    352357        for (it = rays.begin(); it != it_end; ++ it) 
    353358        { 
    354                 if (Random((int)constructionRays.size()) > limit) 
     359                if (Random(1.0f) < prop) 
    355360                        constructionRays.push_back(new Ray(*(*it))); 
    356361                else 
    … …  
    602607                bool exportGeometry = false; 
    603608 
    604                 environment->GetBoolValue("BspViewCellsManager.Visualization.exportRays", exportRays); 
    605                 environment->GetBoolValue("BspViewCellsManager.Visualization.exportGeometry", exportGeometry); 
     609                environment->GetBoolValue("BspTree.Visualization.exportRays", exportRays); 
     610                environment->GetBoolValue("BspTree.Visualization.exportGeometry", exportGeometry); 
    606611 
    607612                // export rays 
    … …  
    11861191 
    11871192        mVspKdTree->Construct(constructionRays, sceneBbox); 
    1188  
     1193         
    11891194        // collect view cells 
    11901195        mVspKdTree->CollectViewCells(mViewCells); 
    … …  
    12271232        bool exportGeometry = false; 
    12281233 
    1229         environment->GetBoolValue("BspViewCellsManager.Visualization.exportRays", exportRays); 
    1230         environment->GetBoolValue("BspViewCellsManager.Visualization.exportGeometry", exportGeometry); 
     1234        environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays); 
     1235        environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry); 
    12311236 
    12321237        if (!ViewCellsConstructed()) 
    … …  
    12781283 
    12791284                        // export geometry 
    1280                         VspKdLeaf *leaf = leafContainer[Random((int)leafContainer.size())];  
     1285                        VspKdLeaf *leaf = leafContainer[(int)RandomValue(0.0, (Real)((int)leafContainer.size() - 1))];  
    12811286                        AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf); 
    12821287 
    … …  
    14091414                return 0; 
    14101415 
    1411         Debug << "Constructing bsp view cells" << endl; 
     1416        Debug << "Constructing vsp bsp view cells" << endl; 
    14121417 
    14131418        int sampleContributions = 0; 
    … …  
    14171422 
    14181423        GetRaySets(rays, constructionRays, savedRays); 
    1419  
     1424        Debug << "rays " << rays.size() << " construction rays " << constructionRays.size() << endl; 
    14201425        mVspBspTree->Construct(constructionRays); 
     1426         
    14211427        mVspBspTree->CollectViewCells(mViewCells); 
    14221428         
    … …  
    14331439                                                                                const VssRayContainer &rays) 
    14341440{ 
     1441        Debug << "Post processing view cells" << endl; 
    14351442        if (!ViewCellsConstructed()) 
    14361443        { 
    … …  
    14381445                return 0; 
    14391446        } 
    1440  
    14411447 
    14421448        //-- post processing of bsp view cells 
    … …  
    16251631        bool exportGeometry = false; 
    16261632 
    1627         environment->GetBoolValue("BspViewCellsManager.Visualization.exportRays", exportRays); 
    1628         environment->GetBoolValue("BspViewCellsManager.Visualization.exportGeometry", exportGeometry); 
     1633        Debug << "here344" << endl; 
     1634        environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays); 
     1635        environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry); 
    16291636 
    16301637        const int leafOut = 10; 
    … …  
    16671674                        } 
    16681675#endif 
    1669  
    16701676                        Intersectable::NewMail(); 
    16711677 
    … …  
    18371843                } 
    18381844        } 
     1845        Debug << "here222211" << endl; 
    18391846} 
    18401847 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

    r472 r473  
    7575        environment->GetIntValue("VspBspTree.maxTests", mMaxTests); 
    7676 
    77     Debug << "BSP max depth: " << mTermMaxDepth << endl; 
    78         Debug << "BSP min PVS: " << mTermMinPvs << endl; 
    79         Debug << "BSP min area: " << mTermMinArea << endl; 
    80         Debug << "BSP min rays: " << mTermMinRays << endl; 
    81         Debug << "BSP max polygon candidates: " << mMaxPolyCandidates << endl; 
    82         Debug << "BSP max plane candidates: " << mMaxRayCandidates << endl; 
     77        // maximum number of view cells 
     78        environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 
     79 
     80        //-- 
     81        Debug << "******* VSP BSP options ******** " << endl; 
     82    Debug << "max depth: " << mTermMaxDepth << endl; 
     83        Debug << "min PVS: " << mTermMinPvs << endl; 
     84        Debug << "min area: " << mTermMinArea << endl; 
     85        Debug << "min rays: " << mTermMinRays << endl; 
     86        Debug << "max ray contri: " << mTermMaxRayContribution << endl; 
     87        //Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl; 
     88        Debug << "max cost ratio: " << mTermMaxCostRatio << endl; 
     89        Debug << "miss tolerance: " << mTermMissTolerance << endl; 
     90        Debug << "max view cells: " << mMaxViewCells << endl; 
     91        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl; 
     92        Debug << "max plane candidates: " << mMaxRayCandidates << endl; 
    8393 
    8494        Debug << "Split plane strategy: "; 
    … …  
    310320 
    311321                if (r == mRoot) 
    312                         Debug << "BSP tree construction time spent at root: "  
     322                        Debug << "VSP BSP tree construction time spent at root: "  
    313323                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 
    314324        } 
    … …  
    319329} 
    320330 
    321 bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const 
     331bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data,  
     332                                                                                const int numLeaves) const 
    322333{ 
    323334        return  
    324335                (((int)data.mRays->size() <= mTermMinRays) || 
    325                  (data.mPvs <= mTermMinPvs) || 
     336                 (data.mPvs <= mTermMinPvs)   || 
    326337                 (data.mArea <= mTermMinArea) || 
     338                 (numLeaves >= mMaxViewCells) || 
    327339                // (data.GetAvgRayContribution() >= mTermMaxRayContribution) || 
    328340                 (data.mDepth >= mTermMaxDepth)); 
    … …  
    332344                                                           VspBspTraversalData &tData) 
    333345{ 
     346        BspNode *newNode = tData.mNode; 
     347 
     348        if (!TerminationCriteriaMet(tData, (int)tStack.size())) 
     349        { 
     350                PolygonContainer coincident; 
     351         
     352                VspBspTraversalData tFrontData; 
     353                VspBspTraversalData tBackData; 
     354 
     355                // create new interior node and two leaf nodes 
     356                // or return leaf as it is (if maxCostRatio missed) 
     357                newNode = SubdivideNode(tData, tFrontData, tBackData, coincident); 
     358 
     359                if (!newNode->IsLeaf()) //-- continue subdivision 
     360                { 
     361                        // push the children on the stack 
     362                        tStack.push(tFrontData); 
     363                        tStack.push(tBackData); 
     364 
     365                        // delete old leaf node 
     366                        DEL_PTR(tData.mNode);    
     367                } 
     368        } 
     369         
    334370        //-- terminate traversal   
    335         if (TerminationCriteriaMet(tData))               
    336         { 
    337                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 
    338          
     371        if (newNode->IsLeaf()) 
     372        { 
     373                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode); 
     374         
     375                // create new view cell for this leaf 
    339376                BspViewCell *viewCell = new BspViewCell(); 
    340                  
    341377                leaf->SetViewCell(viewCell); 
    342378                viewCell->mLeaves.push_back(leaf); 
    343379 
    344                 //-- add pvs 
    345                 if (viewCell != mRootCell) 
    346                 { 
    347                         int conSamp = 0, sampCon = 0; 
    348                         AddToPvs(leaf, *tData.mRays, conSamp, sampCon); 
     380                //-- update pvs 
     381                int conSamp = 0, sampCon = 0; 
     382                AddToPvs(leaf, *tData.mRays, conSamp, sampCon); 
    349383                         
    350                         mStat.contributingSamples += conSamp; 
    351                         mStat.sampleContributions += sampCon; 
    352                 } 
    353  
     384                mStat.contributingSamples += conSamp; 
     385                mStat.sampleContributions += sampCon; 
     386                 
    354387                EvaluateLeafStats(tData); 
    355          
    356                 //-- clean up    
    357                 DEL_PTR(tData.mPolygons); 
    358                 DEL_PTR(tData.mRays); 
    359                 DEL_PTR(tData.mGeometry); 
    360  
    361                 return leaf; 
    362         } 
    363  
    364         //-- continue subdivision 
    365         PolygonContainer coincident; 
    366          
    367         VspBspTraversalData tFrontData(new PolygonContainer(),  
    368                                                                    tData.mDepth + 1, 
    369                                                                    new RayInfoContainer(),  
    370                                                                    new BspNodeGeometry()); 
    371  
    372         VspBspTraversalData tBackData(new PolygonContainer(),  
    373                                                                   tData.mDepth + 1, 
    374                                                                   new RayInfoContainer(),  
    375                                                                   new BspNodeGeometry()); 
    376  
    377         // create new interior node and two leaf nodes 
    378         BspNode *newNode = SubdivideNode(tData, tFrontData, tBackData, coincident); 
    379  
    380         // subdivide further 
    381         if (!newNode->IsLeaf()) 
    382         { 
    383                 BspInterior *interior = dynamic_cast<BspInterior *>(newNode); 
    384                  
    385 #ifdef _DEBUG    
    386 //      if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2)) 
    387 //      {       for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it) 
    388 //                      Debug << (*it) << " " << (*it)->GetArea() << " " << (*it)->mParent << endl ; 
    389 //              Debug << endl;} 
    390 #endif 
    391  
    392                 // push the children on the stack 
    393                 tStack.push(tFrontData); 
    394                 tStack.push(tBackData); 
    395  
    396                 // delete old leaf node 
    397                 DEL_PTR(tData.mNode);    
    398         } 
    399  
    400         // cleanup 
     388        } 
     389         
     390                 
     391        //-- cleanup 
    401392        DEL_PTR(tData.mPolygons); 
    402393        DEL_PTR(tData.mRays); 
    … …  
    411402                                                                   PolygonContainer &coincident) 
    412403{ 
    413         mStat.nodes += 2; 
    414          
    415404        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 
    416          
     405 
    417406        int maxCostMisses = tData.mMaxCostMisses; 
    418407 
    … …  
    423412                ++ maxCostMisses; 
    424413 
    425                 if (maxCostMisses >= mTermMissTolerance) 
     414                /*if (maxCostMisses >= mTermMissTolerance) 
     415                { 
     416                        // terminate branch because of max cost 
     417                        ++ mStat.maxCostNodes;  
    426418            return leaf; 
    427         } 
    428  
    429         // subdivide further 
     419                }*/ 
     420        } 
     421 
     422        mStat.nodes += 2; 
     423 
     424        //-- subdivide further 
    430425        BspInterior *interior = new BspInterior(splitPlane);  
    431426 
    … …  
    434429#endif 
    435430         
    436         // subdivide rays into front and back rays 
     431        //-- the front and back traversal data is filled with the new values 
     432        frontData.mPolygons = new PolygonContainer(); 
     433        frontData.mDepth = tData.mDepth + 1; 
     434        frontData.mRays = new RayInfoContainer(); 
     435        frontData.mGeometry = new BspNodeGeometry(); 
     436 
     437        backData.mPolygons = new PolygonContainer(); 
     438        backData.mDepth = tData.mDepth + 1; 
     439        backData.mRays = new RayInfoContainer(); 
     440        backData.mGeometry = new BspNodeGeometry(); 
     441 
     442        // subdivide rays 
    437443        SplitRays(interior->GetPlane(),  
    438444                          *tData.mRays,  
    … …  
    440446                          *backData.mRays); 
    441447         
    442         // subdivide polygons with plane 
     448        // subdivide polygons 
    443449        mStat.splits += SplitPolygons(interior->GetPlane(), 
    444450                                                                  *tData.mPolygons,  
    … …  
    447453                                                                  coincident); 
    448454 
    449      
    450         //-- set left and right traversal data 
     455         
     456        // how often was max cost ratio missed in this branch? 
    451457        frontData.mMaxCostMisses = maxCostMisses; 
    452458        backData.mMaxCostMisses = maxCostMisses; 
    … …  
    464470                                                                           mBox, 
    465471                                                                           mEpsilon); 
    466                          
     472         
    467473                // area is normalized with view space area 
    468474                frontData.mArea = frontData.mGeometry->GetArea() / mBox.SurfaceArea(); 
    … …  
    494500        frontData.mNode = interior->GetFront(); 
    495501        backData.mNode = interior->GetBack(); 
    496          
     502 
    497503        //DEL_PTR(leaf); 
    498504        return interior; 
    … …  
    536542                                                                         vector<SortableEntry> &splitCandidates) const 
    537543{ 
    538   splitCandidates.clear(); 
     544        splitCandidates.clear(); 
    539545   
    540   int requestedSize = 2 * (int)polys.size(); 
    541   // creates a sorted split candidates array   
    542   splitCandidates.reserve(requestedSize); 
     546        const int requestedSize = 2 * (int)polys.size(); 
     547         
     548        // creates a sorted split candidates array   
     549        splitCandidates.reserve(requestedSize); 
    543550   
    544   PolygonContainer::const_iterator it, it_end = polys.end(); 
    545  
    546   AxisAlignedBox3 box; 
    547  
    548   // insert all queries  
    549   for(it = polys.begin(); it != it_end; ++ it) 
    550   { 
    551           box.Initialize(); 
    552           box.Include(*(*it)); 
     551        PolygonContainer::const_iterator it, it_end = polys.end(); 
     552 
     553        AxisAlignedBox3 box; 
     554 
     555        // insert all queries  
     556        for(it = polys.begin(); it != it_end; ++ it) 
     557        { 
     558                box.Initialize(); 
     559                box.Include(*(*it)); 
    553560           
    554           splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it)); 
    555       splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it)); 
    556   } 
     561                splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it)); 
     562                splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it)); 
     563        } 
    557564   
    558   stable_sort(splitCandidates.begin(), splitCandidates.end()); 
     565        stable_sort(splitCandidates.begin(), splitCandidates.end()); 
    559566} 
    560567 
    … …  
    687694        if (!data.mPolygons->empty()) 
    688695                { 
    689                         const int randIdx = Random((int)data.mPolygons->size()); 
     696                        const int randIdx = (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1)); 
    690697                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx]; 
    691698 
    … …  
    696703                { 
    697704                        //-- choose plane on midpoint of a ray 
    698                         const int candidateIdx = Random((int)data.mRays->size()); 
     705                        const int candidateIdx = (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)); 
    699706                                                                         
    700707                        const Vector3 minPt = (*data.mRays)[candidateIdx].ExtrapOrigin(); 
    … …  
    716723} 
    717724 
     725Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const 
     726{        
     727        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 
     728         
     729        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin(); 
     730        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination(); 
     731 
     732        const Vector3 pt = (maxPt + minPt) * 0.5; 
     733        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir()); 
     734 
     735        return Plane3(normal, pt); 
     736} 
     737 
     738Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const 
     739{        
     740        Vector3 pt[3]; 
     741         
     742        int idx[3]; 
     743        int cmaxT = 0; 
     744        int cminT = 0; 
     745        bool chooseMin = false; 
     746 
     747        for (int j = 0; j < 3; ++ j) 
     748        { 
     749                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1)); 
     750                         
     751                if (idx[j] >= (int)rays.size()) 
     752                { 
     753                        idx[j] -= (int)rays.size(); 
     754                                 
     755                        chooseMin = (cminT < 2); 
     756                } 
     757                else 
     758                        chooseMin = (cmaxT < 2); 
     759 
     760                RayInfo rayInf = rays[idx[j]]; 
     761                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination(); 
     762        }        
     763 
     764        return Plane3(pt[0], pt[1], pt[2]); 
     765} 
     766 
     767Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const 
     768{        
     769        Vector3 pt[3]; 
     770         
     771        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 
     772        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 
     773 
     774        // check if rays different 
     775        if (idx1 == idx2) 
     776                idx2 = (idx2 + 1) % (int)rays.size(); 
     777 
     778        const RayInfo ray1 = rays[idx1]; 
     779        const RayInfo ray2 = rays[idx2]; 
     780 
     781        // normal vector of the plane parallel to both lines 
     782        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir())); 
     783 
     784        // vector from line 1 to line 2 
     785        const Vector3 vd = (ray2.ExtrapOrigin() - ray1.ExtrapOrigin()); 
     786         
     787        // project vector on normal to get distance 
     788        const float dist = DotProd(vd, norm); 
     789 
     790        // point on plane lies halfway between the two planes 
     791        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5; 
     792 
     793        return Plane3(norm, planePt); 
     794} 
     795 
    718796bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane,  
    719797                                                                           BspLeaf *leaf,  
    … …  
    725803 
    726804        const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates); 
    727         int candidateIdx = limit; 
     805        int maxIdx = (int)data.mPolygons->size(); 
    728806         
    729807        for (int i = 0; i < limit; ++ i) 
    730808        { 
    731                 candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons); 
    732                  
     809                // assure that no index is taken twice 
     810                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx)); 
     811                //Debug << "current Idx: " << maxIdx << " cand idx " << candidateIdx << endl; 
     812 
    733813                Polygon3 *poly = (*data.mPolygons)[candidateIdx]; 
     814                 
     815                // swap candidate to the end to avoid testing same plane 
     816                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]); 
     817 
     818                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)]; 
    734819 
    735820                // evaluate current candidate 
    … …  
    747832 
    748833        //-- choose candidate planes extracted from rays 
    749         // we currently use different two methods chosen with 
     834        // we use different methods chosen with 
    750835        // equal probability 
    751          
    752         // take 3 ray endpoints, where two are minimum and one a maximum 
    753         // point or the other way round 
    754         for (int i = 0; i < mMaxRayCandidates / 2; ++ i) 
    755         { 
    756                 candidateIdx = Random((int)data.mRays->size()); 
    757          
    758                 RayInfo rayInf = (*data.mRays)[candidateIdx]; 
    759  
    760                 const Vector3 minPt = rayInf.ExtrapOrigin(); 
    761                 const Vector3 maxPt = rayInf.ExtrapTermination(); 
    762  
    763                 const Vector3 pt = (maxPt + minPt) * 0.5; 
    764                 const Vector3 normal = Normalize(rayInf.mRay->GetDir()); 
    765  
    766                 plane = Plane3(normal, pt); 
     836        for (int i = 0; i < mMaxRayCandidates; ++ i) 
     837        { 
     838                plane = ChooseCandidatePlane3(*data.mRays); 
    767839 
    768840                const float candidateCost = SplitPlaneCost(plane, data); 
    … …  
    774846                } 
    775847        } 
    776  
    777         // take plane normal as plane normal and the midpoint of the ray. 
    778         // PROBLEM: does not resemble any point where visibility is likely to change 
    779         //Debug << "lowest2: " << lowestCost << endl; 
    780         for (int i = 0; i < mMaxRayCandidates / 2; ++ i) 
    781         { 
    782                 Vector3 pt[3]; 
    783                 int idx[3]; 
    784                 int cmaxT = 0; 
    785                 int cminT = 0; 
    786                 bool chooseMin = false; 
    787  
    788                 for (int j = 0; j < 3; j ++) 
    789                 { 
    790                         idx[j] = Random((int)data.mRays->size() * 2); 
    791                                  
    792                         if (idx[j] >= (int)data.mRays->size()) 
    793                         { 
    794                                 idx[j] -= (int)data.mRays->size(); 
    795                                  
    796                                 chooseMin = (cminT < 2); 
    797                         } 
    798                         else 
    799                                 chooseMin = (cmaxT < 2); 
    800  
    801                         RayInfo rayInf = (*data.mRays)[idx[j]]; 
    802                         pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination(); 
    803                 }        
    804                          
    805                 plane = Plane3(pt[0], pt[1], pt[2]); 
    806  
    807                 const float candidateCost = SplitPlaneCost(plane, data); 
    808  
    809                 if (candidateCost < lowestCost) 
    810                 { 
    811                         //Debug << "choose ray plane 2: " << candidateCost << endl; 
    812                         bestPlane = plane; 
    813                          
    814                         lowestCost = candidateCost; 
    815                 } 
    816         }        
    817848 
    818849        // cost ratio miss 
    … …  
    825856 
    826857        return true; 
    827 } 
    828  
    829 int VspBspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys) 
    830 { 
    831         const int candidateIdx = Random(currentIdx --); 
    832  
    833         // swap candidates to avoid testing same plane 2 times 
    834         std::swap(polys[currentIdx], polys[candidateIdx]); 
    835          
    836         return currentIdx; 
    837         //return Random((int)polys.size()); 
    838858} 
    839859 
    … …  
    905925        for (int i = 0; i < limit; ++ i) 
    906926        { 
    907                 const int testIdx = useRand ? Random(limit) : i; 
     927                const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i; 
    908928                RayInfo rayInf = (*data.mRays)[testIdx]; 
    909929 
    … …  
    13531373        { 
    13541374                RayInfo bRay = rays.back(); 
     1375                rays.pop_back(); 
     1376 
    13551377                VssRay *ray = bRay.mRay; 
    1356  
    1357                 rays.pop_back(); 
    13581378                float t; 
    1359                 // get classification and receive new t 
     1379 
     1380                        // get classification and receive new t 
    13601381                const int cf = bRay.ComputeRayIntersection(plane, t); 
    1361  
     1382         
    13621383                switch (cf) 
    13631384                { 
    … …  
    13701391                case 0:  
    13711392                        //-- split ray 
    1372  
    1373                         // if start point behind plane 
     1393                        //--  look if start point behind or in front of plane 
    13741394                        if (plane.Side(bRay.ExtrapOrigin()) <= 0) 
    13751395                        {        

  • trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

    r472 r473  
    6060                /// how often this branch has missed the max-cost ratio 
    6161                int mMaxCostMisses; 
     62 
     63 
    6264                /** Returns average ray contribution. 
    6365                */ 
    … …  
    8082                 
    8183                VspBspTraversalData(BspNode *node,  
    82                                                  PolygonContainer *polys,  
    83                                                  const int depth,  
    84                                                  RayInfoContainer *rays, 
    85                                                  int pvs, 
    86                                                  float area, 
    87                                                  BspNodeGeometry *geom):  
     84                                                        PolygonContainer *polys,  
     85                                                        const int depth,  
     86                                                        RayInfoContainer *rays, 
     87                                                        int pvs, 
     88                                                        float area, 
     89                                                        BspNodeGeometry *geom):  
    8890                mNode(node),  
    8991                mPolygons(polys),  
    … …  
    359361        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent); 
    360362 
    361         /** returns next candidate index and reorders polygons so no candidate is chosen two times 
    362                 @param the current candidate index 
    363                 @param max the range of candidates 
    364         */ 
    365         int GetNextCandidateIdx(int currentIdx, PolygonContainer &polys); 
    366          
    367363        /** Computes best cost ratio for the suface area heuristics for axis aligned 
    368364                splits. This heuristics minimizes the cost for ray traversal. 
    … …  
    431427        /** Returns true if tree can be terminated. 
    432428        */ 
    433         inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const; 
     429        inline bool TerminationCriteriaMet(const VspBspTraversalData &data, const int numLeaves) const; 
    434430 
    435431        /** Computes accumulated ray lenght of this rays. 
    … …  
    465461 
    466462 
    467  
     463        /** Take 3 ray endpoints, where two are minimum and one a maximum 
     464                point or the other way round. 
     465        */ 
     466        Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const; 
     467 
     468        /** Take plane normal as plane normal and the midpoint of the ray. 
     469                PROBLEM: does not resemble any point where visibility is likely to change 
     470        */ 
     471        Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const; 
     472 
     473        /** Fit the plane between the two lines so that the plane has equal shortest  
     474                distance to both lines. 
     475        */ 
     476        Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const; 
    468477   
    469478        /// Pointer to the root of the tree 
    … …  
    537546        /// number of different bsp split plane criteria 
    538547        int mNumCriteria; 
     548        /// maximal number of view cells 
     549        int mMaxViewCells; 
    539550 
    540551private: 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

    r472 r473  
    382382        Debug << "min rays: "<< mTermMinRays << endl; 
    383383        Debug << "max ray contribution: "<< mTermMaxRayContribution << endl; 
    384         Debug << "max cost ratio: "<< mTermMaxCostRatio << endl; 
    385         Debug << "min size: "<<mTermMinSize << endl; 
     384        Debug << "max cost ratio: " << mTermMaxCostRatio << endl; 
     385        Debug << "min size: " << mTermMinSize << endl; 
    386386 
    387387        if (name.compare("regular") == 0) 
    … …  
    23102310 
    23112311 
     2312void VspKdTree::RefineViewCells() 
     2313{ 
     2314} 
     2315 
     2316 
    23122317/*********************************************************************/ 
    23132318/*                MergeCandidate implementation                      */ 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

    r472 r473  
    601601        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const; 
    602602 
     603        /** Refines view cells in a post processing step. 
     604        */ 
     605        void RefineViewCells(); 
     606 
    603607protected: 
    604608 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

    r469 r473  
    562562        mViewCellsManager->Visualize(mObjects, storedRays); 
    563563 
    564         CLEAR_CONTAINER(storedRays); 
    565   } 
    566  
    567   //-- render simulation after merge 
    568   cout << "\nevaluating bsp view cells render time after merge ... "; 
     564        Debug << "here2" << endl; 
     565  } 
    569566 
    570567  //-- render simulation after merge 
    … …  
    572569   
    573570  mRenderSimulator->RenderScene(); 
     571  Debug << "here3" << endl; 
    574572  SimulationStatistics ss; 
    575573  mRenderSimulator->GetStatistics(ss); 
    576  
     574  Debug << "here244" << endl; 
    577575  cout << " finished" << endl; 
    578576  cout << ss << endl; 
    579577  Debug << ss << endl; 
    580578 
    581  
    582579  delete vssTree; 
    583580 
     581  Debug << "here4" << endl; 
    584582  return true; 
    585583} 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.cpp

    r469 r473  
    17201720  for (int i=0; i < numberOfRays; i++) { 
    17211721        // pickup 3 random rays 
    1722         int r1 = Random(nrays-1); 
    1723         int r2 = Random(nrays-1); 
    1724         int r3 = Random(nrays-1); 
     1722        int r1 = (int)RandomValue(0, nrays-1); 
     1723        int r2 = (int)RandomValue(0, nrays-1); 
     1724        int r3 = (int)RandomValue(0, nrays-1); 
    17251725                 
    17261726        Vector3 o1 = leaf->rays[r1].Extrap(RandomValue(leaf->rays[r1].GetMinT(),  
Note: See TracChangeset for help on using the changeset viewer.