Ignore:
Timestamp:
12/23/05 21:35:53 (19 years ago)
Author:
mattausch
Message:

axis aligned split for vsp bsp view cells

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
12 edited

Legend:

Unmodified
Added
Removed

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

    r479 r480  
    177177Simulation { 
    178178        objRenderCost 1.0 
    179         vcOverhead 2.0 
     179        vcOverhead 1.0 
    180180        # always between 0 and 1 
    181         moveSpeed 0.00002 
     181        moveSpeed 0.0001 
    182182} 
    183183 
    … …  
    223223VspBspTree { 
    224224        Construction { 
    225                 samples 100000 
     225                samples 500000 
    226226                epsilon 0.005 
    227227        } 
    … …  
    241241         
    242242        # maximal tested rays for split cost heuristics 
    243         maxTests 500 
     243        maxTests 2000 
    244244         
    245245        # factors for evaluating split plane costs 
    … …  
    258258                minArea                 0.0001 
    259259                maxRayContribution      0.005 
    260                 maxCostRatio            0.9 
     260                maxCostRatio            0.8 
    261261                missTolerance           2 
    262262                #maxAccRayLength        100 
    263263                 
    264                 maxViewCells            1000 
     264                maxViewCells            5000 
    265265                 
    266266                # used for pvs criterium 
    … …  
    289289         
    290290        PostProcess { 
    291                 maxCostRatio 0.05 
     291                maxCostRatio 0.005 
    292292                minViewCells 700 
    293293                maxPvsSize   500 

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

    r478 r480  
    14901490                        optFloat, 
    14911491                        "-vsp_kd_post_process_max_cost_ratio=", 
    1492                         "1.5"); 
     1492                        "0.9"); 
    14931493 
    14941494        RegisterOption("VspKdTree.PostProcess.minViewCells",  
    … …  
    17581758                        optFloat, 
    17591759                        "-vsp_bsp_post_process_max_cost_ratio=", 
    1760                         "1.5"); 
     1760                        "0.9"); 
    17611761 
    17621762        RegisterOption("VspBspTree.PostProcess.minViewCells",  

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

    r478 r480  
    236236        mViewCellsManager->SetPostProcessSamples(postProcessSamples); 
    237237        mViewCellsManager->SetVisualizationSamples(visSamples); 
     238        mViewCellsManager->SetRenderer(mRenderSimulator); 
    238239 
    239240        //Debug << "Visualization samples: " << mViewCellsManager->GetVisualizationSamples() << endl; 

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

    r479 r480  
    8383                // and the probability that a view cell border is crossed 
    8484                loadPvsOverhead += GetCrossVcProbability() * mVcOverhead; 
    85  
     85                //Debug << "vccost: " << vcCost << " p in vc " << pInVc << " cross vc " << GetCrossVcProbability() << endl; 
    8686                //-- update statistics 
    8787                renderTime += vcCost; 

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

    r479 r480  
    976976                                                                  vector<SortableEntry> &splitCandidates) const 
    977977{ 
    978   splitCandidates.clear(); 
    979    
    980   int requestedSize = 2 * (int)polys.size(); 
    981   // creates a sorted split candidates array   
    982   splitCandidates.reserve(requestedSize); 
    983    
    984   PolygonContainer::const_iterator it, it_end = polys.end(); 
    985  
    986   AxisAlignedBox3 box; 
    987  
    988   // insert all queries  
    989   for(it = polys.begin(); it != it_end; ++ it) 
    990   { 
    991           box.Initialize(); 
    992           box.Include(*(*it)); 
    993            
    994           splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it)); 
    995       splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it)); 
    996   } 
    997    
    998   stable_sort(splitCandidates.begin(), splitCandidates.end()); 
     978        splitCandidates.clear(); 
     979 
     980        int requestedSize = 2 * (int)polys.size(); 
     981        // creates a sorted split candidates array   
     982        splitCandidates.reserve(requestedSize); 
     983 
     984        PolygonContainer::const_iterator it, it_end = polys.end(); 
     985 
     986        AxisAlignedBox3 box; 
     987 
     988        // insert all queries  
     989        for(it = polys.begin(); it != it_end; ++ it) 
     990        { 
     991                box.Initialize(); 
     992                box.Include(*(*it)); 
     993                 
     994                splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it)); 
     995                splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it)); 
     996        } 
     997 
     998        stable_sort(splitCandidates.begin(), splitCandidates.end()); 
    999999} 
    10001000 
    … …  
    26122612        return planePoly; 
    26132613} 
     2614 
     2615void BspNodeGeometry::ComputeBoundingBox(AxisAlignedBox3 &box) 
     2616{ 
     2617        Polygon3::IncludeInBox(mPolys, box); 
     2618} 

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

    r479 r480  
    2828        ~BspNodeGeometry(); 
    2929 
     30        /** Returns accumulated area of all polygons. 
     31        */ 
    3032        float GetArea() const; 
    3133         
    … …  
    3941                                           const float epsilon) const; 
    4042 
     43        /** Computes bounding box of the node. 
     44        */ 
     45        void ComputeBoundingBox(AxisAlignedBox3 &box); 
     46        /** Splits the polygon and returns the part of the polygon inside of the node geometry. 
     47        */ 
    4148        Polygon3 *SplitPolygon(Polygon3 *poly, const float epsilon) const; 
    4249 

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

    r479 r480  
    1414 
    1515ViewCellsManager::ViewCellsManager(): 
    16 mRenderSimulator(NULL), 
     16mRenderer(NULL), 
    1717mConstructionSamples(0), 
    1818mPostProcessSamples(0), 
    … …  
    2929ViewCellsManager::ViewCellsManager(int constructionSamples): 
    3030mConstructionSamples(constructionSamples), 
    31 mRenderSimulator(NULL), 
     31mRenderer(NULL), 
    3232mPostProcessSamples(0), 
    3333mVisualizationSamples(0) 
    … …  
    4141ViewCellsManager::~ViewCellsManager() 
    4242{ 
    43         DEL_PTR(mRenderSimulator); 
     43        DEL_PTR(mRenderer); 
    4444 
    4545        CLEAR_CONTAINER(mViewCells); 
    … …  
    176176} 
    177177 
     178void ViewCellsManager::SetRenderer(Renderer *renderer) 
     179{ 
     180        mRenderer = renderer; 
     181} 
    178182 
    179183ViewCell *ViewCellsManager::GenerateViewCell(Mesh *mesh) const 
    … …  
    236240} 
    237241 
    238 void 
    239 ViewCellsManager::PrintPvsStatistics(ostream &s) 
     242void ViewCellsManager::PrintPvsStatistics(ostream &s) 
    240243{ 
    241244  s<<"############# Viewcell PVS STAT ##################\n"; 
    … …  
    252255} 
    253256 
     257void ViewCellsManager::ResetViewCells() 
     258{ 
     259        mViewCells.clear(); 
     260        CollectViewCells(); 
     261        mViewCellsStats.Reset(); 
     262        EvaluateViewCellsStats(); 
     263 
     264        mTotalAreaValid = false; 
     265} 
     266 
    254267void ViewCellsManager::ComputeSampleContributions(VssRay &ray) 
    255268{ 
    … …  
    313326 
    314327        for (it = mViewCells.begin(); it != it_end; ++ it) 
     328        { 
     329                //Debug << "area: " << GetArea(*it); 
    315330        mTotalArea += GetArea(*it); 
    316          
     331        } 
     332 
    317333        mTotalAreaValid = true; 
    318334 
    … …  
    343359} 
    344360 
     361 
    345362ViewCell *BspViewCellsManager::GenerateViewCell(Mesh *mesh) const 
    346363{ 
    347364        return new BspViewCell(mesh); 
    348365} 
     366 
    349367 
    350368int BspViewCellsManager::Construct(const ObjectContainer &objects,  
    … …  
    388406        } 
    389407 
    390         EvaluateViewCellsStats(); 
    391  
    392408        // destroy rays created only for construction 
    393409        CLEAR_CONTAINER(constructionRays); 
    … …  
    395411        Debug << mBspTree->GetStatistics() << endl; 
    396412         
     413        EvaluateViewCellsStats(); 
     414        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl; 
     415 
    397416        // recast rest of the rays 
    398417        ComputeSampleContributions(savedRays); 
    … …  
    401420} 
    402421 
     422void BspViewCellsManager::CollectViewCells() 
     423{ 
     424        mBspTree->CollectViewCells(mViewCells); 
     425} 
    403426 
    404427float BspViewCellsManager::GetProbability(ViewCell *viewCell) 
    … …  
    449472        int pvsSize = 0; 
    450473 
     474        EvaluateViewCellsStats(); 
    451475        Debug << "original view cell partition:\n" << mViewCellsStats << endl; 
    452                  
     476 
     477        mRenderer->RenderScene(); 
     478        SimulationStatistics ss; 
     479        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss); 
     480 
     481    Debug << ss << endl; 
     482 
    453483        if (1) // export view cells 
    454484        { 
    … …  
    529559         
    530560        // reset view cells and stats 
    531         mViewCells.clear(); 
    532         mTotalAreaValid = false; 
    533         mBspTree->CollectViewCells(mViewCells); 
    534         mViewCellsStats.Reset(); 
    535         EvaluateViewCellsStats(); 
     561        ResetViewCells(); 
    536562 
    537563        return merged; 
    … …  
    876902} 
    877903 
     904void KdViewCellsManager::CollectViewCells() 
     905{ 
     906        //mKdTree->CollectViewCells(mViewCells); TODO 
     907} 
    878908 
    879909int KdViewCellsManager::Construct(const ObjectContainer &objects,  
    … …  
    887917        mKdTree->Construct(); 
    888918 
     919        mTotalAreaValid = false; 
    889920        // create the view cells 
    890921        mKdTree->CreateAndCollectViewCells(mViewCells); 
     922         
     923        // cast rays 
     924        ComputeSampleContributions(rays); 
     925 
    891926        EvaluateViewCellsStats(); 
     927        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl; 
    892928 
    893929        return 0; 
    … …  
    11191155{ 
    11201156        // volume or area substitutes for view point probability 
    1121         AxisAlignedBox3 box = mVspKdTree->GetBBox(mVspKdTree->GetRoot()); 
    1122  
    1123         return GetArea(viewCell) / box.SurfaceArea(); 
    1124         //return GetArea(viewCell) / GetAccVcArea(); 
     1157#if 0 
     1158        return GetArea(viewCell) / GetSceneBbox().SurfaceArea(); 
     1159#else 
     1160        return GetArea(viewCell) / GetAccVcArea(); 
     1161#endif 
    11251162} 
    11261163 
    … …  
    11311168} 
    11321169 
     1170void VspKdViewCellsManager::CollectViewCells() 
     1171{ 
     1172        mVspKdTree->CollectViewCells(mViewCells); 
     1173} 
    11331174 
    11341175int VspKdViewCellsManager::Construct(const ObjectContainer &objects,  
    … …  
    11491190 
    11501191        mVspKdTree->Construct(constructionRays, sceneBbox); 
    1151         mVspKdTree->CollectViewCells(mViewCells); 
    1152         EvaluateViewCellsStats(); 
    1153  
    11541192        Debug << mVspKdTree->GetStatistics() << endl; 
     1193 
     1194        ResetViewCells(); 
     1195        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl; 
    11551196 
    11561197        // finally merge kd leaf building blocks to view cells 
    … …  
    13521393 
    13531394 
     1395void VspBspViewCellsManager::CollectViewCells() 
     1396{ 
     1397        mVspBspTree->CollectViewCells(mViewCells); 
     1398} 
     1399 
     1400 
    13541401float VspBspViewCellsManager::GetRendercost(ViewCell *viewCell,  
    13551402                                                                                        float objRendercost) const 
    … …  
    13921439         
    13931440        mVspBspTree->Construct(constructionRays); 
    1394         mVspBspTree->CollectViewCells(mViewCells); 
    1395         EvaluateViewCellsStats(); 
    1396  
    13971441        Debug << mVspBspTree->GetStatistics() << endl; 
    1398          
     1442 
     1443        ResetViewCells(); 
     1444 
     1445        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl; 
    13991446        // recast rest of rays 
    14001447        ComputeSampleContributions(savedRays); 
    … …  
    14471494        int pvsSize = 0; 
    14481495 
     1496        EvaluateViewCellsStats(); 
    14491497        Debug << "original view cell partition:\n" << mViewCellsStats << endl; 
    1450                  
     1498 
     1499        mRenderer->RenderScene(); 
     1500        SimulationStatistics ss; 
     1501        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss); 
     1502    Debug << ss << endl; 
     1503 
    14511504        if (1) // export view cells 
    14521505        { 
    … …  
    15321585         
    15331586        // reset view cells and stats 
    1534         mViewCells.clear(); 
    1535         mTotalAreaValid = false; 
    1536         mVspBspTree->CollectViewCells(mViewCells); 
    1537         mViewCellsStats.Reset(); 
    1538         EvaluateViewCellsStats(); 
     1587        ResetViewCells(); 
    15391588 
    15401589        return merged; 

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

    r479 r480  
    1010class Intersectable; 
    1111class RenderSimulator; 
     12class Renderer; 
    1213class Mesh; 
    1314struct Triangle3; 
    … …  
    192193                                        VssRayContainer &savedRays) const; 
    193194 
    194   /** Returns accumulated area of all view cells. 
    195   */ 
    196   float GetAccVcArea(); 
    197  
    198   /** Returns area of one view cell. 
    199   */ 
    200   virtual float GetArea(ViewCell *viewCell) const; 
    201  
    202   /** Returns volume of view cells. 
    203   */ 
    204   virtual float GetVolume(ViewCell *viewCell) const; 
    205  
    206   virtual AxisAlignedBox3 GetSceneBbox() const = 0; 
    207  
     195        /** Returns accumulated area of all view cells. 
     196        */ 
     197        float GetAccVcArea(); 
     198 
     199        /** Returns area of one view cell. 
     200        */ 
     201        virtual float GetArea(ViewCell *viewCell) const; 
     202 
     203        /** Returns volume of view cells. 
     204        */ 
     205        virtual float GetVolume(ViewCell *viewCell) const; 
     206 
     207        virtual AxisAlignedBox3 GetSceneBbox() const = 0; 
     208 
     209        /** Sets the current renderer mainly for view cells statistics. 
     210        */ 
     211        void SetRenderer(Renderer *renderer); 
     212 
     213         
    208214protected: 
     215 
     216        /** Recollects view cells and resets statistics. 
     217        */ 
     218        void ResetViewCells(); 
     219        /** Collects the view cells in the view cell container. 
     220        */ 
     221        virtual void CollectViewCells() = 0; 
     222 
    209223        /** Evaluates view cells statistics and stores it in 
    210224                mViewCellsStatistics. 
    … …  
    215229        ViewCell *mUnbounded; 
    216230 
    217         /// Simulates rendering 
    218         RenderSimulator *mRenderSimulator; 
     231        /// Renders the view cells. 
     232        Renderer *mRenderer; 
    219233 
    220234        /// Loaded view cells 
    … …  
    281295protected: 
    282296 
     297        void CollectViewCells(); 
     298 
    283299        /** Merges view cells front and back leaf view cell. 
    284300        */ 
    … …  
    348364protected: 
    349365 
    350          KdNode *GetNodeForPvs(KdLeaf *leaf); 
    351  
    352  
    353          /// the BSP tree. 
    354          KdTree *mKdTree; 
    355  
    356          /// depth of the KD tree nodes with represent the view cells 
    357          int mKdPvsDepth; 
     366        void CollectViewCells(); 
     367        KdNode *GetNodeForPvs(KdLeaf *leaf); 
     368 
     369 
     370        /// the BSP tree. 
     371        KdTree *mKdTree; 
     372 
     373        /// depth of the KD tree nodes with represent the view cells 
     374        int mKdPvsDepth; 
    358375}; 
    359376 
    … …  
    400417protected: 
    401418 
     419        void CollectViewCells(); 
     420 
    402421        /// the BSP tree. 
    403422        VspKdTree *mVspKdTree; 
    … …  
    459478        bool ShouldMerge(BspLeaf *front, BspLeaf *back) const; 
    460479 
     480        void CollectViewCells(); 
     481 
    461482        /// the view space partition BSP tree. 
    462483        VspBspTree *mVspBspTree; 

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

    r479 r480  
    8484        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells); 
    8585        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells); 
    86         environment->GetIntValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 
     86        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 
    8787 
    8888 
    … …  
    125125                Debug << "pvs"; 
    126126        } 
     127         
     128        mSplitCandidates = new vector<SortableEntry>; 
    127129 
    128130        Debug << endl; 
    … …  
    140142        DEL_PTR(mRoot); 
    141143        DEL_PTR(mRootCell); 
     144        DEL_PTR(mSplitCandidates); 
    142145} 
    143146 
    … …  
    236239        long startTime = GetTime(); 
    237240 
    238         cout << "Extracting polygons from rays ..."; 
     241        cout << "Extracting polygons from rays ... "; 
    239242 
    240243        Intersectable::NewMail(); 
    … …  
    430433                ++ maxCostMisses; 
    431434 
    432                 if (maxCostMisses >= mTermMissTolerance) 
     435                if (maxCostMisses > mTermMissTolerance) 
    433436                { 
    434437                        // terminate branch because of max cost 
    … …  
    555558} 
    556559 
    557 void VspBspTree::SortSplitCandidates(const PolygonContainer &polys,  
    558                                                                          const int axis,  
    559                                                                          vector<SortableEntry> &splitCandidates) const 
    560 { 
    561         splitCandidates.clear(); 
    562    
    563         const int requestedSize = 2 * (int)polys.size(); 
    564          
    565         // creates a sorted split candidates array   
    566         splitCandidates.reserve(requestedSize); 
    567    
    568         PolygonContainer::const_iterator it, it_end = polys.end(); 
    569  
    570         AxisAlignedBox3 box; 
    571  
    572         // insert all queries  
    573         for(it = polys.begin(); it != it_end; ++ it) 
    574         { 
    575                 box.Initialize(); 
    576                 box.Include(*(*it)); 
    577            
    578                 splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it)); 
    579                 splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it)); 
    580         } 
    581    
    582         stable_sort(splitCandidates.begin(), splitCandidates.end()); 
    583 } 
    584  
    585  
    586 float VspBspTree::BestCostRatio(const PolygonContainer &polys, 
    587                                                                 const AxisAlignedBox3 &box, 
    588                                                                 const int axis, 
    589                                                                 float &position, 
    590                                                                 int &objectsBack, 
    591                                 int &objectsFront) const 
    592 { 
    593         vector<SortableEntry> splitCandidates; 
    594  
    595         SortSplitCandidates(polys, axis, splitCandidates); 
    596          
     560void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis) 
     561{ 
     562        mSplitCandidates->clear(); 
     563 
     564        int requestedSize = 2 * (int)(rays.size()); 
     565        // creates a sorted split candidates array 
     566        if (mSplitCandidates->capacity() > 500000 && 
     567                requestedSize < (int)(mSplitCandidates->capacity()/10) ) 
     568        { 
     569        DEL_PTR(mSplitCandidates); 
     570                mSplitCandidates = new vector<SortableEntry>; 
     571        } 
     572 
     573        mSplitCandidates->reserve(requestedSize); 
     574 
     575        // insert all queries 
     576        for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri) 
     577        { 
     578                bool positive = (*ri).mRay->HasPosDir(axis); 
     579                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
     580                                                                                                  (*ri).ExtrapOrigin(axis), (void *)&*ri)); 
     581 
     582                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
     583                                                                                                  (*ri).ExtrapTermination(axis), (void *)&*ri)); 
     584        } 
     585 
     586        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end()); 
     587} 
     588 
     589float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays, 
     590                                                                                  const AxisAlignedBox3 &box, 
     591                                                                                  const int pvsSize, 
     592                                                                                  int &axis, 
     593                                          float &position) 
     594{ 
     595        //      AxisAlignedBox3 dirBox = GetDirBBox(node); 
     596        int raysBack; 
     597        int raysFront; 
     598        int pvsBack; 
     599        int pvsFront; 
     600 
     601        axis = box.Size().DrivingAxis(); 
     602 
     603        SortSplitCandidates(rays, axis); 
     604 
    597605        // go through the lists, count the number of objects left and right 
    598606        // and evaluate the following cost funcion: 
    599         // C = ct_div_ci  + (ol + or)/queries 
    600          
    601         int objectsLeft = 0, objectsRight = (int)polys.size(); 
    602          
     607        // C = ct_div_ci  + (ql*rl + qr*rr)/queries 
     608 
     609        int rl = 0, rr = (int)rays.size(); 
     610        int pl = 0, pr = pvsSize; 
     611 
    603612        float minBox = box.Min(axis); 
    604613        float maxBox = box.Max(axis); 
    605         float boxArea = box.SurfaceArea(); 
    606    
    607         float minBand = minBox + mAxisAlignedSplitBorder * (maxBox - minBox); 
    608         float maxBand = minBox + (1.0f - mAxisAlignedSplitBorder) * (maxBox - minBox); 
    609          
     614        float sizeBox = maxBox - minBox; 
     615 
     616        float minBand = minBox + 0.1f*(maxBox - minBox); 
     617        float maxBand = minBox + 0.9f*(maxBox - minBox); 
     618 
     619        float sum = rr*sizeBox; 
    610620        float minSum = 1e20f; 
    611         vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end(); 
    612  
    613         for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)  
    614         { 
    615                 switch ((*ci).type)  
    616                 { 
    617                         case SortableEntry::POLY_MIN: 
    618                                 ++ objectsLeft; 
    619                                 break; 
    620                         case SortableEntry::POLY_MAX: 
    621                             -- objectsRight; 
    622                                 break; 
    623                         default: 
    624                                 break; 
    625                 } 
    626                  
    627                 if ((*ci).value > minBand && (*ci).value < maxBand)  
    628                 { 
    629                         AxisAlignedBox3 lbox = box; 
    630                         AxisAlignedBox3 rbox = box; 
    631                         lbox.SetMax(axis, (*ci).value); 
    632                         rbox.SetMin(axis, (*ci).value); 
    633  
    634                         float sum = objectsLeft * lbox.SurfaceArea() +  
    635                                                 objectsRight * rbox.SurfaceArea(); 
    636        
    637                         if (sum < minSum)  
     621 
     622        Intersectable::NewMail(); 
     623 
     624        // set all object as belonging to the fron pvs 
     625        for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri) 
     626        { 
     627                if ((*ri).mRay->IsActive()) 
     628                { 
     629                        Intersectable *object = (*ri).mRay->mTerminationObject; 
     630 
     631                        if (object) 
     632                                if (!object->Mailed()) 
     633                                { 
     634                                        object->Mail(); 
     635                                        object->mCounter = 1; 
     636                                } 
     637                                else 
     638                                        ++ object->mCounter; 
     639                } 
     640        } 
     641 
     642        Intersectable::NewMail(); 
     643 
     644        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin(); 
     645                ci < mSplitCandidates->end(); ++ ci) 
     646        { 
     647                VssRay *ray; 
     648 
     649                switch ((*ci).type) 
     650                { 
     651                        case SortableEntry::ERayMin: 
     652                                { 
     653                                        ++ rl; 
     654                                        ray = (VssRay *) (*ci).data; 
     655                                        Intersectable *object = ray->mTerminationObject; 
     656                                        if (object && !object->Mailed()) 
     657                                        { 
     658                                                object->Mail(); 
     659                                                ++ pl; 
     660                                        } 
     661                                        break; 
     662                                } 
     663                        case SortableEntry::ERayMax: 
     664                                { 
     665                                        -- rr; 
     666 
     667                                        ray = (VssRay *) (*ci).data; 
     668                                        Intersectable *object = ray->mTerminationObject; 
     669 
     670                                        if (object) 
     671                                        { 
     672                                                if (-- object->mCounter == 0) 
     673                                                -- pr; 
     674                                        } 
     675 
     676                                        break; 
     677                                } 
     678                } 
     679 
     680                // Note: sufficient to compare size of bounding boxes of front and back side? 
     681                if ((*ci).value > minBand && (*ci).value < maxBand) 
     682                { 
     683                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value); 
     684 
     685                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 
     686                        // cout<<"cost= "<<sum<<endl; 
     687 
     688                        if (sum < minSum) 
    638689                        { 
    639690                                minSum = sum; 
    640691                                position = (*ci).value; 
    641692 
    642                                 objectsBack = objectsLeft; 
    643                                 objectsFront = objectsRight; 
     693                                raysBack = rl; 
     694                                raysFront = rr; 
     695 
     696                                pvsBack = pl; 
     697                                pvsFront = pr; 
     698 
    644699                        } 
    645700                } 
    646701        } 
    647    
    648         const float oldCost = (float)polys.size(); 
    649         const float newCost = mAxisAlignedCtDivCi + minSum / boxArea; 
    650         const float ratio = newCost / oldCost; 
    651  
    652  
    653 #if 0 
    654   Debug << "====================" << endl; 
    655   Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox) 
    656       << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl; 
    657 #endif 
    658   return ratio; 
    659 } 
    660  
    661 bool VspBspTree::SelectAxisAlignedPlane(Plane3 &plane, 
    662                                         const PolygonContainer &polys) const 
     702 
     703        float oldCost = (float)pvsSize; 
     704        float newCost = mCtDivCi + minSum / sizeBox; 
     705        float ratio = newCost / oldCost; 
     706 
     707        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) 
     708        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl; 
     709 
     710        return ratio; 
     711} 
     712 
     713 
     714float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,  
     715                                                                                 const VspBspTraversalData &tData) 
    663716{ 
    664717        AxisAlignedBox3 box; 
    … …  
    666719         
    667720        // create bounding box of region 
    668         Polygon3::IncludeInBox(polys, box); 
    669          
    670         int objectsBack = 0, objectsFront = 0; 
     721        RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end(); 
     722 
     723        for(ri = tData.mRays->begin(); ri < ri_end; ++ ri) 
     724                box.Include((*ri).ExtrapTermination()); 
     725 
    671726        int axis = 0; 
    672         float costRatio = MAX_FLOAT; 
    673         Vector3 position; 
    674  
    675         //-- area subdivision 
    676         for (int i = 0; i < 3; ++ i)  
    677         { 
    678                 float p = 0; 
    679                 const float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront); 
     727        const bool useCostHeuristics = false; 
     728 
     729        if (useCostHeuristics) 
     730        { 
     731                float position; 
     732 
     733                const float ratio =  
     734                        BestCostRatioHeuristics(*tData.mRays, 
     735                                                                    box, 
     736                                                                        tData.mPvs, 
     737                                                                        axis, 
     738                                                                        position); 
     739 
     740                Vector3 normal(0,0,0); normal[axis] = 1; 
     741                plane = Plane3(normal, position); 
     742 
     743                return ratio; 
     744        } 
     745 
     746        //-- regular split 
     747        float nPosition[3]; 
     748        float nCostRatio[3]; 
     749        int bestAxis = -1; 
     750 
     751        bool mOnlyDrivingAxis = false; 
     752 
     753        const int sAxis = box.Size().DrivingAxis(); 
    680754                 
    681                 if (r < costRatio) 
    682                 { 
    683                         costRatio = r; 
    684                         axis = i; 
    685                         position = p; 
    686                 } 
    687         } 
    688          
    689         if (costRatio >= mTermMaxCostRatio) 
    690                 return false; 
    691  
    692         Vector3 norm(0,0,0); norm[axis] = 1.0f; 
    693         plane = Plane3(norm, position); 
    694  
    695         return true; 
    696 } 
     755        for (axis = 0; axis < 3; ++ axis) 
     756        { 
     757                if (!mOnlyDrivingAxis || axis == sAxis) 
     758                { 
     759                        if (!useCostHeuristics) 
     760                        { 
     761                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f; 
     762                                Vector3 normal(0,0,0); normal[axis] = 1; 
     763 
     764                                nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), tData); 
     765                        } 
     766                         
     767                        if (bestAxis == -1) 
     768                        { 
     769                                bestAxis = axis; 
     770                        } 
     771 
     772                        else if (nCostRatio[axis] < nCostRatio[bestAxis]) 
     773                        { 
     774                                /*Debug << "pvs front " << nPvsBack[axis] 
     775                                          << " pvs back " << nPvsFront[axis] 
     776                                          << " overall pvs " << leaf->GetPvsSize() << endl;*/ 
     777                                bestAxis = axis; 
     778                        } 
     779 
     780                } 
     781        } 
     782 
     783        //-- assign best axis 
     784        Vector3 normal(0,0,0); normal[bestAxis] = 1; 
     785        plane = Plane3(normal, nPosition[bestAxis]); 
     786 
     787        return nCostRatio[bestAxis]; 
     788} 
     789 
    697790 
    698791bool VspBspTree::SelectPlane(Plane3 &plane,  
    … …  
    700793                                                         VspBspTraversalData &data) 
    701794{ 
    702         if ((mSplitPlaneStrategy & AXIS_ALIGNED) && 
    703                 ((int)data.mRays->size() > mTermMinRaysForAxisAligned)) 
    704         {       // TODO: candidates should be rays 
    705                 return SelectAxisAlignedPlane(plane, *data.mPolygons);  
    706         } 
    707  
    708795        // simplest strategy: just take next polygon 
    709796        if (mSplitPlaneStrategy & RANDOM_POLYGON) 
    … …  
    740827} 
    741828 
     829 
    742830Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const 
    743831{        
    … …  
    752840        return Plane3(normal, pt); 
    753841} 
     842 
    754843 
    755844Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const 
    … …  
    822911        int maxIdx = (int)data.mPolygons->size(); 
    823912         
     913        float candidateCost; 
     914 
    824915        for (int i = 0; i < limit; ++ i) 
    825916        { 
    … …  
    836927 
    837928                // evaluate current candidate 
    838                 const float candidateCost =  
    839                         SplitPlaneCost(poly->GetSupportingPlane(), data); 
     929                candidateCost = SplitPlaneCost(poly->GetSupportingPlane(), data); 
    840930 
    841931                if (candidateCost < lowestCost) 
    … …  
    846936        } 
    847937         
     938#if 0 
    848939        //-- choose candidate planes extracted from rays 
    849940        //-- different methods are available 
    … …  
    851942        { 
    852943                plane = ChooseCandidatePlane3(*data.mRays); 
    853                 const float candidateCost = SplitPlaneCost(plane, data); 
     944                candidateCost = SplitPlaneCost(plane, data); 
    854945 
    855946                if (candidateCost < lowestCost) 
    … …  
    858949                        lowestCost = candidateCost; 
    859950                } 
     951        } 
     952#endif 
     953 
     954        // axis aligned splits 
     955        candidateCost = SelectAxisAlignedPlane(plane, data);  
     956 
     957        if (candidateCost < lowestCost) 
     958        { 
     959                bestPlane = plane;       
     960                lowestCost = candidateCost; 
    860961        } 
    861962 
    … …  
    880981 
    881982float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane,  
    882                                                                  const VspBspTraversalData &data) 
     983                                                                 const VspBspTraversalData &data) const 
    883984{ 
    884985        float cost = 0; 
    … …  
    19572058        int merged = 0; 
    19582059 
    1959         Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 
    1960         Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl; 
    1961  
    1962         // use priority queue to merge leaves 
     2060        //-- use priority queue to merge leaf pairs 
    19632061        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) && 
    19642062                   (mergeQueue.top().GetMergeCost() <  
    19652063                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost)) 
    19662064        { 
    1967                 Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 
     2065                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 
    19682066                BspMergeCandidate mc = mergeQueue.top(); 
    19692067                mergeQueue.pop(); 

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

    r479 r480  
    263263        struct SortableEntry 
    264264        { 
    265                 enum {POLY_MIN, POLY_MAX}; 
    266      
     265                enum EType  
     266                { 
     267                        ERayMin, 
     268                        ERayMax 
     269                }; 
     270 
    267271                int type; 
    268272                float value; 
    269                 Polygon3 *poly; 
     273                void *data; 
     274   
    270275                SortableEntry() {} 
    271                 SortableEntry(const int t, const float v, Polygon3 *poly):  
    272                 type(t), value(v), poly(poly) {} 
    273                  
    274                 bool operator<(const SortableEntry &b) const  
     276                SortableEntry(const int t, const float v, void *d):type(t), 
     277                                          value(v), data(d)  
    275278                { 
    276                         return value < b.value; 
    277                 }   
     279                } 
     280                 
     281                friend bool operator<(const SortableEntry &a, const SortableEntry &b)  
     282                { 
     283                        return a.value < b.value; 
     284                } 
    278285        }; 
    279286 
    … …  
    315322        */ 
    316323        float SplitPlaneCost(const Plane3 &candidatePlane,  
    317                                                  const VspBspTraversalData &data); 
     324                                                 const VspBspTraversalData &data) const; 
    318325 
    319326 
    … …  
    375382        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent); 
    376383 
    377         /** Computes best cost ratio for the suface area heuristics for axis aligned 
    378                 splits. This heuristics minimizes the cost for ray traversal. 
    379                 @param polys the polygons guiding the ratio computation 
    380                 @param box the bounding box of the leaf 
    381                 @param axis the current split axis 
    382                 @param position returns the split position 
    383                 @param objectsBack the number of objects in the back of the split plane 
    384                 @param objectsFront the number of objects in the front of the split plane 
    385         */ 
    386         float BestCostRatio(const PolygonContainer &polys, 
    387                                                 const AxisAlignedBox3 &box, 
    388                                                 const int axis, 
    389                                                 float &position, 
    390                                                 int &objectsBack, 
    391                                                 int &objectsFront) const; 
    392          
     384        /** Selects a plane axis aligned. 
     385        */ 
     386        float SelectAxisAlignedPlane(Plane3 &plane,  
     387                                                                 const VspBspTraversalData &tData); 
     388 
    393389        /** Sorts split candidates for surface area heuristics for axis aligned splits. 
    394390                @param polys the input for choosing split candidates 
    … …  
    396392                @param splitCandidates returns sorted list of split candidates 
    397393        */ 
    398         void SortSplitCandidates(const PolygonContainer &polys,  
    399                                                          const int axis,  
    400                                                          vector<SortableEntry> &splitCandidates) const; 
     394        void SortSplitCandidates(const RayInfoContainer &rays, const int axis); 
     395 
     396        /** Computes best cost for axis aligned planes. 
     397        */ 
     398        float BestCostRatioHeuristics(const RayInfoContainer &rays, 
     399                                                                  const AxisAlignedBox3 &box, 
     400                                                                  const int pvsSize, 
     401                                                                  int &axis, 
     402                                                                  float &position); 
    401403 
    402404        /** Selects an axis aligned split plane. 
    … …  
    569571        int mMergeMinViewCells; 
    570572        /// maximal cost ratio for the merge 
    571         int mMergeMaxCostRatio; 
     573        float mMergeMaxCostRatio; 
    572574 
    573575        ViewCellsManager *mViewCellsManager; 
    … …  
    575577        // if rays should be stored in leaves 
    576578        bool mStoreRays; 
     579 
     580        vector<SortableEntry> *mSplitCandidates; 
    577581 
    578582private: 

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

    r479 r480  
    8080 
    8181VspKdNode::~VspKdNode() 
    82 {}; 
     82{ 
     83}; 
    8384 
    8485inline VspKdInterior *VspKdNode::GetParent() const 
    … …  
    658659                                                   int &pvsFront) 
    659660{ 
    660         int minDirDepth = 6; 
    661661        int axis = 0; 
    662662        float costRatio = 0; 
    … …  
    665665        { 
    666666                costRatio = BestCostRatioRegular(leaf, 
     667                                                                                 box, 
    667668                                                                                 axis, 
    668669                                                                                 position, 
    … …  
    675676        { 
    676677                costRatio = BestCostRatioHeuristic(leaf, 
     678                                                                                   box, 
    677679                                                                                   axis, 
    678680                                                                                   position, 
    … …  
    706708 
    707709float VspKdTree::EvalCostRatio(VspKdLeaf *leaf, 
     710                                                           const AxisAlignedBox3 &box, 
    708711                                                           const int axis, 
    709712                                                           const float position, 
    … …  
    725728        int pvsSize = leaf->GetPvsSize(); 
    726729 
    727         Intersectable::NewMail(3); 
    728  
    729730        // this is the main ray classification loop! 
    730           for(RayInfoContainer::iterator ri = leaf->mRays.begin(); 
     731        for(RayInfoContainer::iterator ri = leaf->mRays.begin(); 
    731732                        ri != leaf->mRays.end(); ++ ri) 
    732                 { 
    733  if (!(*ri).mRay->IsActive()) 
    734                                                                 continue; 
    735  
    736                                                                 // determine the side of this ray with respect to the plane 
    737                                                                 float t; 
    738                                                                 int side = (*ri).ComputeRayIntersection(axis, position, t); 
    739                 //                              (*ri).mRay->mSide = side; 
    740  
     733        { 
     734                if (!(*ri).mRay->IsActive()) 
     735                        continue; 
     736 
     737                // determine the side of this ray with respect to the plane 
     738                float t; 
     739                int side = (*ri).ComputeRayIntersection(axis, position, t); 
     740                         
    741741                if (side <= 0) 
    742742                        ++ raysBack; 
    … …  
    757757        else 
    758758        { 
    759                 AxisAlignedBox3 box = GetBBox(leaf); 
    760  
     759#if 0 
    761760                float minBox = box.Min(axis); 
    762761                float maxBox = box.Max(axis); 
     762 
    763763                float sizeBox = maxBox - minBox; 
     764#else 
     765 
     766                float minBox = AxisAlignedBox3(box.Min(), position).SurfaceArea(); 
     767                float maxBox = AxisAlignedBox3(position, box.Max()).SurfaceArea(); 
     768 
     769                float sizeBox = box.SurfaceArea(); 
     770#endif 
    764771 
    765772                // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position); 
    … …  
    777784 
    778785float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf, 
     786                                                                          const AxisAlignedBox3 &box, 
    779787                                                                          int &axis, 
    780788                                                                          float &position, 
    … …  
    791799        int bestAxis = -1; 
    792800 
    793         AxisAlignedBox3 sBox = GetBBox(leaf); 
    794  
    795         const int sAxis = sBox.Size().DrivingAxis(); 
     801        //AxisAlignedBox3 sBox = GetBBox(leaf); 
     802 
     803        const int sAxis = box.Size().DrivingAxis(); 
    796804 
    797805        for (axis = 0; axis < 3; ++ axis) 
    … …  
    800808                { 
    801809 
    802                         nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis]) * 0.5f; 
     810                        nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f; 
    803811 
    804812                        nCostRatio[axis] = EvalCostRatio(leaf, 
     813                                                                                         box, 
    805814                                                                                         axis, 
    806815                                                                                         nPosition[axis], 
    … …  
    838847 
    839848float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf, 
     849                                                                                const AxisAlignedBox3 &box, 
    840850                                                                                int &axis, 
    841851                                                                                float &position, 
    … …  
    845855                                                                                int &pvsFront) 
    846856{ 
    847         AxisAlignedBox3 box = GetBBox(leaf); 
     857        //AxisAlignedBox3 box = GetBBox(leaf); 
    848858        //      AxisAlignedBox3 dirBox = GetDirBBox(node); 
    849859 
    … …  
    10651075        if (axis == -1) 
    10661076        { 
     1077                // cost ratio missed 
    10671078                ++ maxCostMisses; 
    1068  
    1069                 if (maxCostMisses >= mTermMissTolerance) 
     1079                if (maxCostMisses > mTermMissTolerance) 
    10701080                        return leaf; 
    10711081        } 
    … …  
    21712181 
    21722182        // collapse siblings belonging to the same view cell 
    2173         CollapseTree(mRoot); 
     2183        //CollapseTree(mRoot); 
    21742184        // revalidate leaves 
    2175         RepairVcLeafLists(); 
     2185        //RepairVcLeafLists(); 
    21762186 
    21772187        //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl; 

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

    r479 r480  
    629629   
    630630        float BestCostRatioHeuristic(VspKdLeaf *node, 
     631                                                                 const AxisAlignedBox3 &box, 
    631632                                                                 int &axis, 
    632633                                                                 float &position, 
    … …  
    636637                                                                 int &pvsFront); 
    637638 
    638         float BestCostRatioRegular(VspKdLeaf *node,  
     639        float BestCostRatioRegular(VspKdLeaf *node, 
     640                                                           const AxisAlignedBox3 &box, 
    639641                                                           int &axis, 
    640642                                                           float &position, 
    … …  
    645647         
    646648        float EvalCostRatio(VspKdLeaf *node, 
     649                                                const AxisAlignedBox3 &box, 
    647650                                                const int axis, 
    648651                                                const float position, 
Note: See TracChangeset for help on using the changeset viewer.