Changeset 472 for trunk/VUT


Ignore:
Timestamp:
12/19/05 18:57:00 (19 years ago)
Author:
mattausch
Message:

added priority queue to vspbsptree

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
8 edited

Legend:

Unmodified
Added
Removed

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

    r469 r472  
    289289                minRays                 500 
    290290                minSize                 0.1 
    291                 maxCostRatio            999.0 
     291                maxCostRatio            0.9 
     292                missTolerance           4 
    292293                maxRayContribution      0.2 
    293294        } 
    … …  
    345346        Termination { 
    346347                # parameters used for autopartition 
    347                 minRays 100 
    348                 minPolygons -1 
    349                 maxDepth 30 
    350                 minPvs 100 
    351                 minArea 0.01 
    352                 maxRayContribution 0.005 
    353                 #maxAccRayLength 100 
     348                minRays                 100 
     349                minPolygons             -1 
     350                maxDepth                30 
     351                minPvs                  100 
     352                minArea                 0.01 
     353                maxRayContribution      0.005 
     354                maxCostRatio            0.9 
     355                missTolerance           4 
     356                #maxAccRayLength        100 
    354357                 
    355358                # used for pvs criterium 

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

    r469 r472  
    139139    return; 
    140140 
    141   numParams = strlen(optParams) + 1; 
     141  numParams = (int)strlen(optParams) + 1; 
    142142  optionalParams = new char[numParams]; 
    143143  strcpy(optionalParams, optParams); 
    … …  
    390390  if (options[i].value != NULL) { 
    391391    // option was explicitly specified 
    392     value = strtod(options[i].value, NULL); 
     392    value = (Real)strtod(options[i].value, NULL); 
    393393  } else { 
    394394    // option was not read, so use the default 
    395     value = strtod(options[i].defaultValue, NULL); 
     395    value = (Real)strtod(options[i].defaultValue, NULL); 
    396396  } 
    397397  return true; 
    … …  
    13151315                 "100"); 
    13161316 
    1317   RegisterOption("BspTree.Termination.AxisAligned.maxCostRatio", 
     1317  RegisterOption("BspTree.Termination.maxCostRatio", 
    13181318                 optFloat, 
    13191319                 "-bsp_term_axis_aligned_max_cost_ratio=", 
    … …  
    15121512                "false"); 
    15131513 
     1514        RegisterOption("VspKdTree.Termination.maxCostRatio", 
     1515                optFloat, 
     1516                "-vsp_kd_term_max_cost_ratio=", 
     1517                "1.5"); 
     1518 
     1519        RegisterOption("VspKdTree.Termination.missTolerance", 
     1520                 optInt, 
     1521                 "-vsp_kd_term_miss_tolerance=", 
     1522                 "4"); 
    15141523 
    15151524        /************************************************************************************/ 
    … …  
    16631672                        "1.5"); 
    16641673 
     1674        RegisterOption("VspBspTree.Termination.maxCostRatio", 
     1675                optFloat, 
     1676                "-vsp_bsp_term_max_cost_ratio=", 
     1677                "1.5"); 
     1678 
     1679        RegisterOption("VspBspTree.Termination.missTolerance", 
     1680                 optInt, 
     1681                 "-vsp_bsp_term_miss_tolerance=", 
     1682                 "4"); 
    16651683 
    16661684        RegisterOption("VspBspTree.Termination.AxisAligned.ct_div_ci", 

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

    r469 r472  
    195195 
    196196        //-- termination criteria for axis aligned split 
    197         environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAaCtDivCi); 
    198         environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", mMaxCostRatio); 
     197        environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi); 
     198        environment->GetFloatValue("BspTree.Termination.maxCostRatio", mMaxCostRatio); 
    199199        environment->GetIntValue("BspTree.Termination.AxisAligned.minPolys",  
    200200                                                         mTermMinPolysForAxisAligned); 
    … …  
    406406void BspTree::InsertPolygons(PolygonContainer *polys) 
    407407{        
    408         std::stack<BspTraversalData> tStack; 
     408        BspTraversalStack tStack; 
    409409 
    410410        // traverse existing tree or create new tree 
    … …  
    710710void BspTree::Construct(PolygonContainer *polys, BoundedRayContainer *rays) 
    711711{ 
    712         std::stack<BspTraversalData> tStack; 
     712        BspTraversalStack tStack; 
    713713 
    714714        mRoot = new BspLeaf(); 
    … …  
    10421042                        rbox.SetMin(axis, (*ci).value); 
    10431043 
    1044                         float sum = objectsLeft * lbox.SurfaceArea() +  
    1045                                                 objectsRight * rbox.SurfaceArea(); 
     1044                        const float sum = objectsLeft * lbox.SurfaceArea() +  
     1045                                                          objectsRight * rbox.SurfaceArea(); 
    10461046       
    10471047                        if (sum < minSum)  
    … …  
    10561056        } 
    10571057   
    1058         float oldCost = (float)polys.size(); 
    1059         float newCost = mAaCtDivCi + minSum / boxArea; 
    1060         float ratio = newCost / oldCost; 
     1058        const float oldCost = (float)polys.size(); 
     1059        const float newCost = mAxisAlignedCtDivCi + minSum / boxArea; 
     1060        const float ratio = newCost / oldCost; 
    10611061 
    10621062 

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

    r469 r472  
    346346         
    347347        typedef std::stack<BspTraversalData> BspTraversalStack; 
     348        //typedef std::priority_queue<BspTraversalData> BspTraversalStack; 
    348349 
    349350        /** Default constructor creating an empty tree. 
    … …  
    353354        ~BspTree(); 
    354355 
    355          
     356        /** Returns detailed statistics of the BSP tree. 
     357        */ 
    356358        const BspTreeStatistics &GetStatistics() const;  
    357359   
    … …  
    797799 
    798800        /// axis aligned split criteria 
    799         float mAaCtDivCi; 
     801        float mAxisAlignedCtDivCi; 
    800802        float mSplitBorder; 
    801803        float mMaxCostRatio; 

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

    r469 r472  
    3737VspBspTree::VspBspTree():  
    3838mRoot(NULL), 
    39 mPvsUseArea(true) 
     39mPvsUseArea(true), 
     40mNumCriteria(0) 
    4041{ 
    4142        mRootCell = new BspViewCell(); 
    … …  
    5051        environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution); 
    5152        environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength); 
     53        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio); 
     54        environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance); 
    5255 
    5356        //-- factors for bsp tree split plane heuristics 
    … …  
    5760 
    5861        //-- termination criteria for axis aligned split 
    59         environment->GetFloatValue("VspBspTree.Termination.AxisAligned.ct_div_ci", mAaCtDivCi); 
    60         environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxCostRatio", mMaxCostRatio); 
     62        environment->GetFloatValue("VspBspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi); 
     63        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio); 
    6164         
    6265        environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",  
    … …  
    6770        environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates); 
    6871        environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy); 
    69         environment->GetFloatValue("VspBspTree.AxisAligned.splitBorder", mSplitBorder); 
     72        environment->GetFloatValue("VspBspTree.AxisAligned.splitBorder", mAxisAlignedSplitBorder); 
    7073 
    7174        environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon); 
    … …  
    8285        if (mSplitPlaneStrategy & RANDOM_POLYGON) 
    8386                Debug << "random polygon "; 
     87 
    8488        if (mSplitPlaneStrategy & AXIS_ALIGNED) 
     89        { 
     90                ++ mNumCriteria; 
    8591                Debug << "axis aligned "; 
     92        } 
    8693        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS) 
     94        { 
     95                ++ mNumCriteria; 
    8796                Debug << "least ray splits "; 
     97        } 
    8898        if (mSplitPlaneStrategy & BALANCED_RAYS) 
     99        { 
     100                ++ mNumCriteria; 
    89101                Debug << "balanced rays "; 
     102        } 
    90103        if (mSplitPlaneStrategy & PVS) 
     104        { 
     105                ++ mNumCriteria; 
    91106                Debug << "pvs"; 
     107        } 
    92108 
    93109        Debug << endl; 
    … …  
    261277void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays) 
    262278{ 
    263         std::stack<VspBspTraversalData> tStack; 
     279        VspBspTraversalStack tStack; 
    264280 
    265281        mRoot = new BspLeaf(); 
    … …  
    338354                EvaluateLeafStats(tData); 
    339355         
    340                 //-- clean up 
    341                  
     356                //-- clean up    
    342357                DEL_PTR(tData.mPolygons); 
    343358                DEL_PTR(tData.mRays); 
    … …  
    361376 
    362377        // create new interior node and two leaf nodes 
    363         BspInterior *interior =  
    364                 SubdivideNode(tData, tFrontData, tBackData, coincident); 
    365  
     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                 
    366385#ifdef _DEBUG    
    367386//      if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2)) 
    … …  
    371390#endif 
    372391 
    373         // push the children on the stack 
    374         tStack.push(tFrontData); 
    375         tStack.push(tBackData); 
     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        } 
    376399 
    377400        // cleanup 
    378         DEL_PTR(tData.mNode);    
    379  
    380401        DEL_PTR(tData.mPolygons); 
    381402        DEL_PTR(tData.mRays); 
    382403        DEL_PTR(tData.mGeometry); 
    383404 
    384         return interior; 
    385 } 
    386  
    387 BspInterior *VspBspTree::SubdivideNode(VspBspTraversalData &tData, 
    388                                                                            VspBspTraversalData &frontData, 
    389                                                                            VspBspTraversalData &backData, 
    390                                                                            PolygonContainer &coincident) 
     405        return newNode; 
     406} 
     407 
     408BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData, 
     409                                                                   VspBspTraversalData &frontData, 
     410                                                                   VspBspTraversalData &backData, 
     411                                                                   PolygonContainer &coincident) 
    391412{ 
    392413        mStat.nodes += 2; 
    … …  
    394415        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 
    395416         
     417        int maxCostMisses = tData.mMaxCostMisses; 
     418 
    396419        // select subdivision plane 
    397         BspInterior *interior = new BspInterior(SelectPlane(leaf, tData));  
     420        Plane3 splitPlane; 
     421        if (!SelectPlane(splitPlane, leaf, tData)) 
     422        { 
     423                ++ maxCostMisses; 
     424 
     425                if (maxCostMisses >= mTermMissTolerance) 
     426            return leaf; 
     427        } 
     428 
     429        // subdivide further 
     430        BspInterior *interior = new BspInterior(splitPlane);  
    398431 
    399432#ifdef _DEBUG 
    … …  
    414447                                                                  coincident); 
    415448 
    416     // compute pvs 
     449     
     450        //-- set left and right traversal data 
     451        frontData.mMaxCostMisses = maxCostMisses; 
     452        backData.mMaxCostMisses = maxCostMisses; 
     453 
     454        // compute pvs 
    417455        frontData.mPvs = ComputePvsSize(*frontData.mRays); 
    418456        backData.mPvs = ComputePvsSize(*backData.mRays); 
    … …  
    426464                                                                           mBox, 
    427465                                                                           mEpsilon); 
    428          
    429                  
    430                 frontData.mArea = frontData.mGeometry->GetArea(); 
    431                 backData.mArea = backData.mGeometry->GetArea(); 
     466                         
     467                // area is normalized with view space area 
     468                frontData.mArea = frontData.mGeometry->GetArea() / mBox.SurfaceArea(); 
     469                backData.mArea = backData.mGeometry->GetArea() / mBox.SurfaceArea(); 
    432470        } 
    433471 
    … …  
    543581        float boxArea = box.SurfaceArea(); 
    544582   
    545         float minBand = minBox + mSplitBorder * (maxBox - minBox); 
    546         float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox); 
     583        float minBand = minBox + mAxisAlignedSplitBorder * (maxBox - minBox); 
     584        float maxBand = minBox + (1.0f - mAxisAlignedSplitBorder) * (maxBox - minBox); 
    547585         
    548586        float minSum = 1e20f; 
    … …  
    584622        } 
    585623   
    586         float oldCost = (float)polys.size(); 
    587         float newCost = mAaCtDivCi + minSum / boxArea; 
    588         float ratio = newCost / oldCost; 
     624        const float oldCost = (float)polys.size(); 
     625        const float newCost = mAxisAlignedCtDivCi + minSum / boxArea; 
     626        const float ratio = newCost / oldCost; 
    589627 
    590628 
    … …  
    615653        { 
    616654                float p = 0; 
    617                 float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront); 
     655                const float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront); 
    618656                 
    619657                if (r < costRatio) 
    … …  
    625663        } 
    626664         
    627         if (costRatio >= mMaxCostRatio) 
     665        if (costRatio >= mTermMaxCostRatio) 
    628666                return false; 
    629667 
    … …  
    634672} 
    635673 
    636 Plane3 VspBspTree::SelectPlane(BspLeaf *leaf, VspBspTraversalData &data) 
     674bool VspBspTree::SelectPlane(Plane3 &plane,  
     675                                                         BspLeaf *leaf,  
     676                                                         VspBspTraversalData &data) 
    637677{ 
    638678        if ((mSplitPlaneStrategy & AXIS_ALIGNED) && 
    639679                ((int)data.mRays->size() > mTermMinRaysForAxisAligned)) 
    640         { 
    641                 Plane3 plane; 
    642                 if (SelectAxisAlignedPlane(plane, *data.mPolygons)) // TODO: should be rays 
    643                         return plane; 
     680        {       // TODO: candidates should be rays 
     681                return SelectAxisAlignedPlane(plane, *data.mPolygons);  
    644682        } 
    645683 
    … …  
    651689                        const int randIdx = Random((int)data.mPolygons->size()); 
    652690                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx]; 
    653                         return nextPoly->GetSupportingPlane(); 
     691 
     692                        plane = nextPoly->GetSupportingPlane(); 
     693                        return true; 
    654694                } 
    655695                else 
    … …  
    665705                        const Vector3 normal = (*data.mRays)[candidateIdx].mRay->GetDir(); 
    666706                         
    667                         return Plane3(normal, pt); 
    668                 } 
    669  
    670                 return Plane3(); 
     707                        plane = Plane3(normal, pt); 
     708                        return true; 
     709                } 
     710 
     711                return false; 
    671712        } 
    672713 
    673714        // use heuristics to find appropriate plane 
    674         return SelectPlaneHeuristics(leaf, data);  
    675 } 
    676  
    677 Plane3 VspBspTree::SelectPlaneHeuristics(BspLeaf *leaf, VspBspTraversalData &data) 
     715        return SelectPlaneHeuristics(plane, leaf, data);  
     716} 
     717 
     718bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane,  
     719                                                                           BspLeaf *leaf,  
     720                                                                           VspBspTraversalData &data) 
    678721{ 
    679722        float lowestCost = MAX_FLOAT; 
    680         Plane3 bestPlane; 
     723        // intermediate plane 
    681724        Plane3 plane; 
    682725 
    683         int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates); 
    684          
     726        const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates); 
    685727        int candidateIdx = limit; 
    686728         
    … …  
    774816        }        
    775817 
     818        // cost ratio miss 
     819        if (lowestCost > mTermMaxCostRatio) 
     820                return false; 
     821 
    776822#ifdef _DEBUG 
    777823        Debug << "plane lowest cost: " << lowestCost << endl; 
    778824#endif 
    779         return bestPlane; 
     825 
     826        return true; 
    780827} 
    781828 
    … …  
    802849                                                                 const VspBspTraversalData &data) 
    803850{ 
    804         float val = 0; 
     851        float cost = 0; 
    805852 
    806853        float sumBalancedRays = 0; 
    … …  
    933980 
    934981        const float raysSize = (float)data.mRays->size() + Limits::Small; 
    935  
     982         
    936983        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS) 
    937                 val += mLeastRaySplitsFactor * sumRaySplits / raysSize; 
     984                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize; 
    938985 
    939986        if (mSplitPlaneStrategy & BALANCED_RAYS) 
    940                 val += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize; 
    941  
    942         const float denom = pOverall * (float)data.mPvs * 2.0f + Limits::Small; 
    943  
     987                cost += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize; 
     988         
     989        // pvs criterium 
    944990        if (mSplitPlaneStrategy & PVS) 
    945991        { 
    946                 val += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / denom; 
     992                const float oldCost = pOverall * (float)data.mPvs + Limits::Small; 
     993 
     994                cost += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / oldCost; 
    947995 
    948996                // give penalty to unbalanced split 
    … …  
    950998                if (((pFront * 0.2 + Limits::Small) > pBack) ||  
    951999                        (pFront < (pBack * 0.2 + Limits::Small))) 
    952                         val += 0.5; 
     1000                        cost += 0.5; 
    9531001        } 
    9541002 
    … …  
    9581006//                << " backpvs: " << backPvs << " pBack: " << pBack << endl << endl; 
    9591007#endif 
    960         return val; 
     1008 
     1009        // normalize by number of criteria 
     1010        return cost / (float)(mNumCriteria + Limits::Small); 
    9611011} 
    9621012 

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

    r469 r472  
    1010#include "RayInfo.h" 
    1111#include "ViewCellBsp.h" 
    12 #include "ViewCell.h" 
    1312 
    1413class ViewCell; 
    … …  
    5150                /// current depth 
    5251                int mDepth; 
    53                  
    5452                /// rays piercing this node 
    5553                RayInfoContainer *mRays; 
    … …  
    5856                /// geometry of node as induced by planes 
    5957                BspNodeGeometry *mGeometry; 
    60                  
    6158                /// pvs size 
    6259                int mPvs; 
    63                  
     60                /// how often this branch has missed the max-cost ratio 
     61                int mMaxCostMisses; 
    6462                /** Returns average ray contribution. 
    6563                */ 
    … …  
    7775                mPvs(0), 
    7876                mArea(0.0), 
    79                 mGeometry(NULL) 
     77                mGeometry(NULL), 
     78                mMaxCostMisses(0) 
    8079                {} 
    8180                 
    … …  
    9392                mPvs(pvs), 
    9493                mArea(area), 
    95                 mGeometry(geom) 
     94                mGeometry(geom), 
     95                mMaxCostMisses(0) 
    9696                {} 
    9797 
    … …  
    106106                mPvs(0), 
    107107                mArea(0), 
    108                 mGeometry(geom) 
     108                mGeometry(geom), 
     109                mMaxCostMisses(0) 
    109110                {} 
     111 
     112                friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b) 
     113                { 
     114#if 0 
     115                        return a.mPvs * a.mArea < b.mPvs * b.mArea; 
     116#endif 
     117#if 1 
     118                        return a.mPvs * (int)a.mRays->size() < b.mPvs * (int)b.mRays->size(); 
     119#endif 
     120#if 0 
     121                        return a.mPvs < b.mPvs; 
     122#endif 
     123#if 0 
     124                        return  
     125                                a.mPvs / (float)(a.mRays->size() + Limits::Small()) 
     126                                > 
     127                                b.mPvs / (float)(b.mRays->size() + Limits::Small()); 
     128#endif 
     129#if 0 
     130                        return a.mPvs * (int)a.mRays->size() <  b.mPvs * (int)b.mRays->size(); 
     131#endif 
     132                } 
    110133    }; 
    111134         
    112         typedef std::stack<VspBspTraversalData> VspBspTraversalStack; 
     135        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalStack; 
     136        //typedef std::stack<VspBspTraversalData> VspBspTraversalStack; 
    113137 
    114138        /** Default constructor creating an empty tree. 
    … …  
    257281 
    258282        /** Selects the best possible splitting plane.  
     283                @param plane returns the split plane 
    259284                @param leaf the leaf to be split 
    260285                @param polys the polygon list on which the split decition is based 
    261286                @param rays ray container on which selection may be based 
    262287                @note the polygons can be reordered in the process 
    263                 @returns the split plane 
    264         */ 
    265         Plane3 SelectPlane(BspLeaf *leaf,  
    266                                            VspBspTraversalData &data); 
    267  
     288                @returns true if the cost of the split is under maxCostRatio 
     289 
     290        */ 
     291        bool SelectPlane(Plane3 &plane,  
     292                                         BspLeaf *leaf,  
     293                                         VspBspTraversalData &data); 
    268294         
    269295        /** Strategies where the effect of the split plane is tested 
    … …  
    274300        float SplitPlaneCost(const Plane3 &candidatePlane,  
    275301                                                 const VspBspTraversalData &data); 
    276  
    277302 
    278303 
    … …  
    291316        */ 
    292317 
    293         BspInterior *SubdivideNode(VspBspTraversalData &tData, 
    294                                                            VspBspTraversalData &frontData, 
    295                                                            VspBspTraversalData &backData, 
    296                                                            PolygonContainer &coincident); 
     318        BspNode *SubdivideNode(VspBspTraversalData &tData, 
     319                                                   VspBspTraversalData &frontData, 
     320                                                   VspBspTraversalData &backData, 
     321                                                   PolygonContainer &coincident); 
    297322 
    298323        /** Selects the split plane in order to construct a tree with 
    299324                certain characteristics (e.g., balanced tree, least splits,  
    300325                2.5d aligned) 
     326                @param bestPlane returns the split plane 
    301327                @param polygons container of polygons 
    302328                @param rays bundle of rays on which the split can be based 
    303         */ 
    304         Plane3 SelectPlaneHeuristics(BspLeaf *leaf, 
    305                                                                  VspBspTraversalData &data); 
     329 
     330                @returns true if the overall cost is under maxCostRatio 
     331        */ 
     332        bool SelectPlaneHeuristics(Plane3 &bestPlane,  
     333                                                           BspLeaf *leaf,  
     334                                                           VspBspTraversalData &data); 
    306335 
    307336        /** Extracts the meshes of the objects and adds them to polygons.  
    … …  
    476505        float mTermMinAccRayLength; 
    477506 
    478  
    479507        /// strategy to get the best split plane 
    480508        int mSplitPlaneStrategy; 
    … …  
    487515 
    488516        //-- axis aligned split criteria 
    489         float mAaCtDivCi; 
    490         float mSplitBorder; 
    491         float mMaxCostRatio; 
     517        float mAxisAlignedCtDivCi; 
     518        /// spezifies the split border of the axis aligned split 
     519        float mAxisAlignedSplitBorder; 
     520 
     521        /// maximal acceptable cost ratio 
     522        float mTermMaxCostRatio; 
     523        /// tolerance value indicating how often the max cost ratio can be failed 
     524        int mTermMissTolerance; 
    492525 
    493526        //-- factors guiding the split plane heuristics 
    … …  
    498531        /// if area or accumulated ray lenght should be used for PVS heuristics 
    499532        bool mPvsUseArea; 
    500  
     533        /// tolerance for polygon split 
    501534        float mEpsilon; 
    502  
     535        /// maximal number of test rays used to evaluate candidate split plane 
    503536        int mMaxTests; 
     537        /// number of different bsp split plane criteria 
     538        int mNumCriteria; 
    504539 
    505540private: 

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

    r471 r472  
    3131int VspKdLeaf::sMailId = 0; 
    3232int MergeCandidate::sMaxPvsSize = 150; 
    33  
    34  
     33float MergeCandidate::sOverallCost = Limits::Small; 
    3534#define USE_FIXEDPOINT_T 0 
    3635 
    … …  
    184183 
    185184 
    186 VspKdLeaf::VspKdLeaf(VspKdInterior *p,  const int nRays): 
    187 VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL) 
     185VspKdLeaf::VspKdLeaf(VspKdInterior *p,  
     186                                         const int nRays,  
     187                                         const int maxCostMisses): 
     188VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL), 
     189mMaxCostMisses(maxCostMisses) 
    188190{ 
    189191        mRays.reserve(nRays); 
    … …  
    193195{ 
    194196} 
     197 
     198 
     199int VspKdLeaf::GetMaxCostMisses() 
     200{ 
     201        return mMaxCostMisses; 
     202} 
     203 
    195204 
    196205int VspKdLeaf::Type() const 
    … …  
    343352        environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize); 
    344353 
     354        environment->GetIntValue("VspKdTree.Termination.missTolerance", mTermMissTolerance); 
     355 
    345356        mTermMinSize = sqr(mTermMinSize); 
    346357 
    … …  
    356367        //environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 
    357368 
    358         environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMinViewCells); 
    359         environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMaxCostRatio); 
     369        environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMergeMinViewCells); 
     370        environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 
    360371        environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize", 
    361372                                                         MergeCandidate::sMaxPvsSize); 
    … …  
    615626                tStack.pop(); 
    616627 
    617                 VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode, 
    618                                                                                         data.mBox, backBox,     frontBox); 
     628                VspKdNode *node = SubdivideNode(dynamic_cast<VspKdLeaf *>(data.mNode), 
     629                                                                                data.mBox, backBox,     frontBox); 
    619630                if (result == NULL) 
    620631                        result = node; 
    … …  
    663674        else if (splitType == ESplitHeuristic) 
    664675        { 
    665                         costRatio = BestCostRatioHeuristic(leaf, 
    666                                                                                            axis, 
    667                                                                                            position, 
    668                                                                                            raysBack, 
    669                                                                                            raysFront, 
    670                                                                                            pvsBack, 
    671                                                                                            pvsFront); 
     676                costRatio = BestCostRatioHeuristic(leaf, 
     677                                                                                   axis, 
     678                                                                                   position, 
     679                                                                                   raysBack, 
     680                                                                                   raysFront, 
     681                                                                                   pvsBack, 
     682                                                                                   pvsFront); 
    672683        } 
    673684        else 
    … …  
    10221033 
    10231034VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf, 
    1024                                                                                 const AxisAlignedBox3 &box, 
    1025                                                                                 AxisAlignedBox3 &backBBox, 
    1026                                                                                 AxisAlignedBox3 &frontBBox) 
     1035                                                                        const AxisAlignedBox3 &box, 
     1036                                                                        AxisAlignedBox3 &backBBox, 
     1037                                                                        AxisAlignedBox3 &frontBBox) 
    10271038{ 
    10281039        if (TerminationCriteriaMet(leaf, box)) 
    … …  
    10501061        //Debug << "rays back=" << raysBack << " rays front=" << raysFront << " pvs back=" << pvsBack << " pvs front=" <<       pvsFront << endl; 
    10511062 
     1063        int maxCostMisses = leaf->GetMaxCostMisses(); 
     1064 
    10521065        if (axis == -1) 
    10531066        { 
    1054                 return leaf; 
     1067                ++ maxCostMisses; 
     1068 
     1069                if (maxCostMisses >= mTermMissTolerance) 
     1070                        return leaf; 
    10551071        } 
    10561072 
    … …  
    10681084        frontBBox = box; 
    10691085 
    1070         VspKdLeaf *back = new VspKdLeaf(node, raysBack); 
     1086        VspKdLeaf *back = new VspKdLeaf(node, raysBack, maxCostMisses); 
    10711087        back->SetPvsSize(pvsBack); 
    1072         VspKdLeaf *front = new VspKdLeaf(node, raysFront); 
     1088        VspKdLeaf *front = new VspKdLeaf(node, raysFront, maxCostMisses); 
    10731089        front->SetPvsSize(pvsFront); 
    10741090 
    … …  
    14881504                else 
    14891505                { 
    1490                         tstack.push(((VspKdInterior *)node)->GetFront()); 
    1491                         tstack.push(((VspKdInterior *)node)->GetBack()); 
     1506                        tstack.push(dynamic_cast<VspKdInterior *>(node)->GetFront()); 
     1507                        tstack.push(dynamic_cast<VspKdInterior *>(node)->GetBack()); 
    14921508                } 
    14931509        } 
    … …  
    14991515 
    15001516        if (newLeaf->mParent) 
     1517        { 
    15011518                newLeaf->mParent->ReplaceChildLink(sroot, newLeaf); 
    1502  
     1519        } 
    15031520        tstack.push(sroot); 
    15041521 
    … …  
    20782095bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2) 
    20792096{ 
    2080         //-- change pointer to view cells of all leaves associated with the previous view cells 
     2097        //-- change pointer to view cells of all leaves associated  
     2098        //-- with the previous view cells 
    20812099        VspKdViewCell *fVc = l1->GetViewCell(); 
    20822100        VspKdViewCell *bVc = l2->GetViewCell(); 
    … …  
    21562174 
    21572175                        for (nit = neighbors.begin(); nit != nit_end; ++ nit) 
    2158                                 mergeQueue.push(MergeCandidate(leaf, *nit)); 
     2176                        { 
     2177                                MergeCandidate mc = MergeCandidate(leaf, *nit); 
     2178                                mergeQueue.push(mc); 
     2179 
     2180                                MergeCandidate::sOverallCost += mc.GetLeaf1Cost(); 
     2181                                MergeCandidate::sOverallCost += mc.GetLeaf2Cost(); 
     2182                        } 
    21592183                } 
    21602184        } 
    … …  
    21662190        // use priority queue to merge leaves 
    21672191        while (!mergeQueue.empty() && 
    2168                    (vcSize > mMinViewCells))// && 
    2169                    //(mergeQueue.top().GetMergeCost() < mMaxCostRatio)) 
     2192                   (vcSize > mMergeMinViewCells) && 
     2193                   (mergeQueue.top().GetMergeCost() <  
     2194                    mMergeMaxCostRatio / MergeCandidate::sOverallCost)) 
    21702195        { 
    21712196                //Debug << mergeQueue.top().GetMergeCost() << " " << mMaxCostRatio << endl; 
    … …  
    21842209                        ++ merged; 
    21852210                        -- vcSize; 
     2211                        // increase absolute merge cost 
     2212                        MergeCandidate::sOverallCost += mc.GetMergeCost(); 
    21862213                } 
    21872214                // merge candidate not valid, because one of the leaves was already 
    … …  
    22302257                        if (!viewCell->Mailed()) 
    22312258                        { 
    2232                                 Debug << "jhere2" << endl; 
    22332259                                viewCell->mLeaves.clear(); 
    22342260                                viewCell->Mail(); 
    … …  
    22522278                return node; 
    22532279 
    2254         Debug << "here554444" << endl; 
    22552280        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
    22562281 
    … …  
    23002325} 
    23012326 
     2327float MergeCandidate::GetLeaf1Cost() const 
     2328{ 
     2329        VspKdViewCell *vc = mLeaf1->GetViewCell(); 
     2330        return vc->GetPvs().GetSize() * vc->GetVolume(); 
     2331} 
     2332 
     2333float MergeCandidate::GetLeaf2Cost() const 
     2334{ 
     2335        VspKdViewCell *vc = mLeaf2->GetViewCell(); 
     2336        return vc->GetPvs().GetSize() * vc->GetVolume(); 
     2337} 
    23022338 
    23032339void MergeCandidate::EvalMergeCost() 
    … …  
    23132349        //-- (added size of left and right view cell times pvs size) 
    23142350        //-- to new rendering cost (size of merged view cell times pvs size) 
    2315         const float oldCost = 
    2316                 (float)vc1->GetPvs().GetSize() * vc1->GetVolume() + 
    2317                 (float)vc2->GetPvs().GetSize() * vc2->GetVolume(); 
    2318  
     2351        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost(); 
     2352         
    23192353        const float newCost = 
    23202354                (float)vcPvs * (vc1->GetVolume() + vc2->GetVolume()); 

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

    r469 r472  
    7676        float GetMergeCost() const; 
    7777 
     78        /** Returns cost of leaf 1. 
     79        */ 
     80        float GetLeaf1Cost() const; 
     81        /** Returns cost of leaf 2. 
     82        */ 
     83        float GetLeaf2Cost() const; 
     84 
    7885        /// maximal pvs size 
    7986        static int sMaxPvsSize; 
     87        /// overall cost used to normalize cost ratio 
     88        static float sOverallCost; 
    8089 
    8190protected: 
    … …  
    305314                @param p the parent node 
    306315                @param nRays preallocates memory to store this number of rays 
    307         */ 
    308         VspKdLeaf(VspKdInterior *p,     const int nRays); 
     316                @parma maxMisses how many times the max cost ratio was missed on the path to the leaf 
     317        */ 
     318        VspKdLeaf(VspKdInterior *p,     const int nRays, const int maxCostMisses = 0); 
    309319         
    310320        virtual ~VspKdLeaf(); 
    … …  
    365375        VspKdViewCell *GetViewCell(); 
    366376 
     377        /** Returns number of times the max cost ratio was missed until 
     378                this leaf. 
     379        */ 
     380        int GetMaxCostMisses(); 
     381 
     382 
    367383        //////////////////////////////////////////// 
    368384         
    … …  
    371387        static int sMailId; 
    372388 
    373  
     389         
    374390protected: 
    375391 
    … …  
    381397        int mMailbox; 
    382398   
     399        /// rays intersecting this leaf. 
    383400        RayInfoContainer mRays; 
    384          
    385401        /// true if mPvsSize is valid => PVS does not have to be updated 
    386402        bool mValidPvs; 
    387  
    388403        /// the view cell associated with this leaf 
    389404        VspKdViewCell *mViewCell; 
     405        /// number of times the max cost ratio was missed on the way to the leaf. 
     406        int mMaxCostMisses; 
    390407 
    391408private: 
    … …  
    453470                //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {} 
    454471     
    455                 friend bool operator<(const TraversalData &a, const TraversalData &b)  
     472        friend bool operator<(const TraversalData &a, const TraversalData &b)  
    456473                { 
    457474                        // return a.node->queries.size() < b.node->queries.size(); 
    … …  
    743760        ViewCellsManager *mViewCellsManager; 
    744761 
    745         /// maximal cost ratio of a merge 
    746         float mMaxCostRatio; 
    747  
    748762        ///////////////////////////// 
    749763        // Construction parameters 
    … …  
    751765        /// max depth of the tree 
    752766        int mTermMaxDepth; 
    753  
    754767        /// minimal ratio of the volume of the cell and the query volume 
    755768        float mTermMinSize; 
    756  
    757769        /// minimal pvs per node to still get subdivided 
    758770        int mTermMinPvs; 
    759  
    760771        /// minimal ray number per node to still get subdivided 
    761772        int mTermMinRays; 
    762          
    763         /// maximal cost ration to subdivide a node 
     773        /// maximal acceptable cost ratio to continue subdivision 
    764774        float mTermMaxCostRatio; 
    765          
    766775        /// maximal contribution per ray to subdivide the node 
    767776        float mTermMaxRayContribution; 
     777        /// tolerance value indicating how often the max cost ratio can be failed 
     778        int mTermMissTolerance; 
     779 
     780        /// maximal numbers of view cells 
     781        int mMaxViewCells; 
     782 
     783        /// maximal cost ratio of a merge 
     784        float mMergeMaxCostRatio; 
     785         
     786        /// minimal number of view cells 
     787        int mMergeMinViewCells; 
    768788 
    769789        /// if only the "driving axis", i.e., the axis with the biggest extent 
    … …  
    771791        bool mOnlyDrivingAxis; 
    772792 
    773         /// maximal numbers of view cells 
    774         int mMaxViewCells; 
    775  
    776         /// minimal number of view cells 
    777         int mMinViewCells; 
    778  
    779793        ///////////////////////////// 
    780794        VspKdStatistics mStat;   
Note: See TracChangeset for help on using the changeset viewer.