Changeset 586


Ignore:
Timestamp:
02/03/06 23:02:07 (18 years ago)
Author:
mattausch
Message:

changed shuffling (but does not work yet...)

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

    r582 r586  
    190190        #type vspKdTree 
    191191        type bspTree 
    192         type vspBspTree 
     192        #type vspBspTree 
    193193         
    194194        #type sceneDependent 
    … …  
    211211                maxMergesPerPass 500  
    212212                useRaysForMerge false 
     213                refine true 
     214                compress false 
    213215        } 
    214216 
    … …  
    347349BspTree { 
    348350        Construction { 
    349                 samples 50000 
     351                samples 0 
    350352                epsilon 0.005 
    351353        } 
    … …  
    385387        #splitPlaneStrategy 130 
    386388         
    387         splitPlaneStrategy 1024 
    388          
    389         maxPolyCandidates 50 
    390         maxRayCandidates 50 
     389        splitPlaneStrategy 32 
     390         
     391        maxPolyCandidates 100 
     392        maxRayCandidates 0 
    391393         
    392394        maxTests 10000 
    … …  
    408410                # parameters used for autopartition 
    409411                minRays 200 
    410                 minPolygons -1 
     412                minPolygons 1 
    411413                maxDepth 40 
    412414                minPvs 100 

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

    r582 r586  
    12351235                                        "false"); 
    12361236 
     1237        RegisterOption("ViewCells.PostProcess.refine", 
     1238                                        optBool, 
     1239                                        "view_cells_refine", 
     1240                                        "false"); 
     1241 
     1242 
     1243        RegisterOption("ViewCells.PostProcess.compress", 
     1244                                        optBool, 
     1245                                        "view_cells_compress", 
     1246                                        "false"); 
     1247 
    12371248        RegisterOption("ViewCells.exportToFile", 
    12381249                                        optBool, 

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

    r585 r586  
    279279 
    280280 
     281void ViewCellInterior::RemoveChildLink(ViewCell *l) 
     282{ 
     283        // erase leaf from old view cell 
     284        ViewCellContainer::iterator it = mChildren.begin(); 
     285 
     286        for (; (*it) != l; ++ it); 
     287        if (it == mChildren.end()) 
     288                Debug << "error" << endl; 
     289        else 
     290                mChildren.erase(it); 
     291} 
    281292 
    282293/************************************************************************/ 
    … …  
    335346        environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells); 
    336347        environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio); 
    337          
     348        environment->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);     
     349 
    338350 
    339351        Debug << "========= view cell tree options ================\n"; 
    … …  
    341353        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl; 
    342354        Debug << "max memory: " << mMaxMemory << endl; 
     355        Debug << "refining view cells: " << mRefineViewCells << endl; 
    343356 
    344357        MergeCandidate::sRenderCostWeight = mRenderCostWeight; 
    … …  
    504517        cout << "actual merge starts now ... " << endl; 
    505518         
    506         //ResetMergeQueue(); 
    507519 
    508520        //-- use priority queue to merge leaf pairs 
    … …  
    535547                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells); 
    536548                 
    537                         // recompute priorities => reset render cost 
    538                     ResetMergeQueue(); 
     549                        // refines the view cells 
     550                        // then priorities are recomputed 
     551                        // and the candidates are put back into merge queue 
     552                        if (mRefineViewCells) 
     553                                RefineViewCells(rays, objects); 
     554                        else 
     555                                ResetMergeQueue(); 
    539556 
    540557                         
    … …  
    645662 
    646663        UpdateActiveViewCells(activeViewCells); 
    647         ResetMergeQueue(); 
     664 
     665        // refine view cells and reset costs 
     666        if (mRefineViewCells) 
     667                RefineViewCells(rays, objects); 
     668        else 
     669                ResetMergeQueue(); 
    648670 
    649671        // create a root node if the merge was not done till root level, 
    … …  
    652674        { 
    653675                Debug << "creating root of view cell hierarchy for " << (int)activeViewCells.size() << " view cells" << endl; 
    654                 for (int i = 0;  i < activeViewCells.size(); ++ i){ 
    655                         Debug << "here233 " << activeViewCells[i]->GetParent() << endl; 
    656                         Debug << "here233 " << activeViewCells[i] << endl; 
     676                /*for (int i = 0;  i < activeViewCells.size(); ++ i){ 
     677                        Debug << "parent " << activeViewCells[i]->GetParent() << endl; 
     678                        Debug << "viewcell " << activeViewCells[i] << endl;*/ 
    657679                } 
    658680                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells); 
    … …  
    845867 
    846868// TODO: should be done in view cells manager 
    847 ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const 
     869ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l,  
     870                                                                                                ViewCell *r,  
     871                                                                                                int &pvsDiff) //const 
    848872{ 
    849873        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r); 
    … …  
    876900 
    877901 
    878  
    879 int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects) 
     902int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,  
     903                                                                  const ObjectContainer &objects) 
    880904{ 
    881905        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl; 
    882          
     906 
     907        // intermediate buffer for shuffled view cells 
     908        vector<MergeCandidate> buf; 
     909        buf.reserve(mMergeQueue.size()); 
     910                         
    883911        // Use priority queue of remaining leaf pairs  
    884912        // The candidates either share the same view cells or 
    … …  
    888916        // leaf is made part of the other view cell. It is tested if the 
    889917        // remaining view cells are "better" than the old ones. 
    890         // 
    891         // repeat the merging test numPasses times. For example, it could be 
    892         // that a shuffle only makes sense if another pair was shuffled before. 
    893         // Therefore we keep two queues and shift the merge candidates between 
    894         // those two queues until numPasses is reached 
    895          
    896         queue<MergeCandidate> queue1; 
    897         queue<MergeCandidate> queue2; 
    898  
    899         queue<MergeCandidate> *shuffleQueue = &queue1; 
    900         queue<MergeCandidate> *backQueue = &queue2; 
    901  
    902         while (!mMergeQueue.empty()) 
    903         { 
    904                 MergeCandidate mc = mMergeQueue.top(); 
    905                 shuffleQueue->push(mc); 
    906                 mMergeQueue.pop(); 
    907         } 
    908  
    909         const int numPasses = 5; 
     918         
     919        const int numPasses = 3; 
    910920        int pass = 0; 
    911921        int passShuffled = 0; 
    … …  
    915925        ViewCell::NewMail(); 
    916926         
    917         do 
    918         { 
    919                 passShuffled = 0; 
    920                 while (!shuffleQueue->empty()) 
    921                 { 
    922                         MergeCandidate mc = shuffleQueue->front(); 
    923                         shuffleQueue->pop(); 
    924  
    925                         // both view cells equal or already shuffled 
    926                         if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||  
    927                                 (GetSize(mc.GetLeftViewCell()) == 1) ||  
    928                                 (GetSize(mc.GetRightViewCell()) == 1)) 
    929                         {                        
    930                                 continue; 
     927        while (!mMergeQueue.empty()) 
     928        { 
     929                MergeCandidate mc = mMergeQueue.top(); 
     930                mMergeQueue.pop(); 
     931 
     932                // both view cells equal or already shuffled 
     933                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) || 
     934                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf()) 
     935                {                        
     936                        continue; 
     937                } 
     938 
     939                // candidate for shuffling 
     940                const bool wasShuffled = ShuffleLeaves(mc); 
     941                 
     942                // shuffled or put into other queue for further refine 
     943                if (wasShuffled) 
     944                { 
     945                        ++ passShuffled; 
     946 
     947                        if (!mc.GetLeftViewCell()->Mailed()) 
     948                        { 
     949                                mc.GetLeftViewCell()->Mail(); 
     950                                ++ shuffledViewCells; 
    931951                        } 
    932  
    933                         // candidate for shuffling 
    934                         const bool wasShuffled =  
    935                                 ShuffleLeaves(mc.GetLeftViewCell(), mc.GetRightViewCell()); 
    936                  
    937                         // shuffled or put into other queue for further refine 
    938                         if (wasShuffled) 
     952                        if (!mc.GetRightViewCell()->Mailed()) 
    939953                        { 
    940                                 ++ passShuffled; 
    941  
    942                                 if (!mc.GetLeftViewCell()->Mailed()) 
    943                                 { 
    944                                         mc.GetLeftViewCell()->Mail(); 
    945                                         ++ shuffledViewCells; 
    946                                 } 
    947                                 if (!mc.GetRightViewCell()->Mailed()) 
    948                                 { 
    949                                         mc.GetRightViewCell()->Mail(); 
    950                                         ++ shuffledViewCells; 
    951                                 } 
     954                                mc.GetRightViewCell()->Mail(); 
     955                                ++ shuffledViewCells; 
    952956                        } 
    953                         else 
    954                         { 
    955                                 backQueue->push(mc); 
    956                         } 
    957                 } 
    958  
    959                 // now the back queue is the current shuffle queue 
    960                 swap(shuffleQueue, backQueue); 
    961                 shuffled += passShuffled; 
    962                 Debug << "shuffled in pass: " << passShuffled << endl; 
    963         } 
    964         while (((++ pass) < numPasses) && passShuffled); 
    965  
    966         while (!shuffleQueue->empty()) 
    967         { 
    968                 shuffleQueue->pop(); 
    969         } 
     957                } 
     958 
     959                // put back into intermediate vector 
     960                buf.push_back(mc); 
     961        } 
     962 
     963 
     964        //-- in the end, the candidates must be in the mergequeue again 
     965        //   with the correct cost 
     966 
     967        cout << "reset merge queue ... "; 
     968         
     969         
     970        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end(); 
     971         
     972        for (bit = buf.begin(); bit != bit_end; ++ bit) 
     973        {     
     974                MergeCandidate mc = *bit; 
     975                // recalculate cost 
     976                if (ValidateMergeCandidate(mc)) 
     977                { 
     978                        EvalMergeCost(mc); 
     979                        mMergeQueue.push(mc);    
     980                } 
     981        } 
     982 
     983        cout << "finished" << endl; 
    970984 
    971985        return shuffledViewCells; 
    … …  
    10031017 
    10041018float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,  
    1005                                                                          ViewCell *vc1,  
    1006                                                                          ViewCell *vc2) const 
     1019                                                                         ViewCellInterior *vc1,  
     1020                                                                         ViewCellInterior *vc2) const 
    10071021{ 
    10081022        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs); 
    … …  
    10611075 
    10621076void ViewCellsTree::ShuffleLeaf(ViewCell *leaf, 
    1063                                                                 ViewCell *vc1,  
    1064                                                                 ViewCell *vc2) const 
     1077                                                                ViewCellInterior *vc1,  
     1078                                                                ViewCellInterior *vc2) const 
    10651079{ 
    10661080        // compute new pvs and area 
     1081        // TODO change 
    10671082        vc1->GetPvs().SubtractPvs(leaf->GetPvs()); 
    10681083        vc2->GetPvs().AddPvs(leaf->GetPvs()); 
    … …  
    10791094        } 
    10801095 
    1081         // TODO 
    1082 #if VC_HISTORY 
    1083         /// add to second view cell 
    1084         vc2->mLeaves.push_back(leaf); 
    1085  
    1086         // erase leaf from old view cell 
    1087         vector<BspLeaf *>::iterator it = vc1->mLeaves.begin(); 
    1088  
    1089         for (; *it != leaf; ++ it); 
    1090         vc1->mLeaves.erase(it); 
    1091  
    1092         /*vc1->GetPvs().mEntries.clear(); 
    1093         for (; it != vc1->mLeaves.end(); ++ it) 
    1094         { 
    1095                 if (*it == leaf) 
    1096                         vc1->mLeaves.erase(it); 
    1097                 else 
    1098                         vc1->GetPvs().AddPvs(*(*it)->mPvs); 
    1099         }*/ 
    1100  
    1101         leaf->SetViewCell(vc2); // finally change view cell 
    1102 #endif 
    1103 } 
    1104  
    1105  
    1106 bool ViewCellsTree::ShuffleLeaves(ViewCell *l, ViewCell *r) const 
     1096         
     1097        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent()); 
     1098 
     1099        p->RemoveChildLink(leaf); 
     1100        vc2->SetupChildLink(leaf); 
     1101} 
     1102 
     1103 
     1104bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const 
    11071105{ 
    11081106        float cost1, cost2; 
    11091107 
     1108        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell()); 
     1109        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell()); 
     1110 
     1111        ViewCell *leaf1 = mc.GetInitialLeftViewCell(); 
     1112        ViewCell *leaf2 = mc.GetInitialRightViewCell(); 
     1113 
    11101114        //-- first test if shuffling would decrease cost 
    1111         cost1 = GetCostHeuristics(l); 
    1112         cost2 = GetCostHeuristics(r); 
     1115        cost1 = GetCostHeuristics(vc1); 
     1116        cost2 = GetCostHeuristics(vc2); 
    11131117 
    11141118        const float oldCost = cost1 + cost2; 
    … …  
    11171121        float shuffledCost2 = Limits::Infinity; 
    11181122 
    1119         // the view cell should not be empty after the shuffle 
    1120 #if VC_HISTORY 
    1121         shuffledCost1 = EvalShuffleCost(l, vc1, vc2); 
    1122         /shuffledCost2 = EvalShuffleCost(r, vc2, vc1); 
     1123        if (leaf1) 
     1124                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);        
     1125        if (leaf2) 
     1126                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1); 
    11231127 
    11241128        // if cost of shuffle is less than old cost => shuffle 
    … …  
    11261130                return false; 
    11271131         
    1128          
    11291132        if (shuffledCost1 < shuffledCost2) 
    11301133        { 
    1131                 ShuffleLeaf(leaf1, vc1, vc2); 
    1132                 leaf1->Mail(); 
     1134                if (leaf1) 
     1135                        ShuffleLeaf(leaf1, vc1, vc2); 
     1136                mc.mInitialLeftViewCell = NULL; 
    11331137        } 
    11341138        else 
    11351139        { 
    1136                 ShuffleLeaf(leaf2, vc2, vc1); 
    1137                 leaf2->Mail(); 
    1138         } 
    1139 #endif 
     1140                if (leaf2) 
     1141                        ShuffleLeaf(leaf2, vc2, vc1); 
     1142                mc.mInitialRightViewCell = NULL; 
     1143        } 
     1144 
    11401145        return true; 
    11411146} 
    … …  
    15291534mDeviationIncr(0), 
    15301535mLeftViewCell(l), 
    1531 mRightViewCell(r) 
     1536mRightViewCell(r), 
     1537mInitialLeftViewCell(l), 
     1538mInitialRightViewCell(r) 
    15321539{ 
    15331540        //EvalMergeCost(); 

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

    r584 r586  
    217217        */ 
    218218        void SetupChildLink(ViewCell *l); 
     219        void RemoveChildLink(ViewCell *l); 
    219220        bool IsLeaf() const; 
    220221 
    … …  
    362363                to view cell 2. 
    363364        */ 
    364         void ShuffleLeaf(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const;    
     365        void ShuffleLeaf(ViewCell *leaf, ViewCellInterior *vc1, ViewCellInterior *vc2) const;    
    365366                 
    366367        /** Shuffles the leaves, i.e., tests if exchanging 
    367368                the leaves helps in improving the view cells. 
    368369        */ 
    369         bool ShuffleLeaves(ViewCell *l, ViewCell *r) const; 
     370        bool ShuffleLeaves(MergeCandidate &mc) const; 
    370371 
    371372        /** Calculates cost for merge of view cell 1 and 2. 
    372373        */ 
    373         float EvalShuffleCost(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const; 
     374        float EvalShuffleCost(ViewCell *leaf,  
     375                                                  ViewCellInterior *vc1,  
     376                                                  ViewCellInterior *vc2) const; 
    374377 
    375378        /** Exports a snapshot of the merged view cells to disc. 
    … …  
    411414        ViewCellContainer mMergedViewCells; 
    412415         
     416 
     417        bool mRefineViewCells; 
    413418 
    414419        /// weights between variance and render cost increase (must be between zero and one) 

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

    r585 r586  
    5757         
    5858        environment->GetIntValue("ViewCells.active", mNumMergedViewCells); 
     59        environment->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells); 
    5960 
    6061        mMinPvsSize = emptyViewCells ? 1 : 0; 
    … …  
    23642365 
    23652366        //-- refines the merged view cells 
    2366         RefineViewCells(postProcessRays, objects); 
    2367  
    2368         int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot()); 
    2369         Debug << "number of entries before compress: " << pvsEntries << endl; 
    2370  
    2371         mViewCellsTree->CompressViewCellsPvs(); 
    2372  
    2373         pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot()); 
    2374         Debug << "number of entries after compress: " << pvsEntries << endl; 
     2367        if (0) 
     2368                RefineViewCells(postProcessRays, objects); 
     2369 
     2370        if (mCompressViewCells) 
     2371        { 
     2372                int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot()); 
     2373                Debug << "number of entries before compress: " << pvsEntries << endl; 
     2374 
     2375                mViewCellsTree->CompressViewCellsPvs(); 
     2376 
     2377                pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot()); 
     2378                Debug << "number of entries after compress: " << pvsEntries << endl; 
     2379        } 
    23752380 
    23762381        if (1) 
    … …  
    23922397 
    23932398        //-- export shuffled view cells 
    2394         if (1) 
     2399        if (0) 
    23952400        { 
    23962401                cout << "exporting shuffled view cells ... "; 
    … …  
    24562461 
    24572462        // collapse sibling leaves that share the same view cell 
    2458         mVspBspTree->CollapseTree(); 
     2463        if (0) 
     2464                mVspBspTree->CollapseTree(); 
     2465 
    24592466        // recompute view cell list and statistics 
    24602467        ResetViewCells(); 
    … …  
    27322739 
    27332740 
    2734                 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
     2741                Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) 
    27352742                          << ", piercing rays=" << (int)vcRays.size() << endl; 
    27362743                        //  << ", leaves=" << (int)vc->mLeaves.size() << endl; 

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

    r582 r586  
    436436        int mNumMergedViewCells; 
    437437 
     438        bool mCompressViewCells; 
     439 
    438440        ViewCellsStatistics mViewCellsStats; 
    439441        /// the scene bounding box 
Note: See TracChangeset for help on using the changeset viewer.