Changeset 1084 for GTP/trunk/Lib/Vis


Ignore:
Timestamp:
07/06/06 08:55:06 (18 years ago)
Author:
mattausch
Message:
 
Location:
GTP/trunk/Lib/Vis/Preprocessing/src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h

    r1027 r1084  
    882882                                                int &objectsFront) const; 
    883883         
    884         /** Sorts split candidates for surface area heuristics for axis aligned splits. 
     884        /** Sorts split candidates for cost heuristics using axis aligned splits. 
    885885                @param polys the input for choosing split candidates 
    886886                @param axis the current split axis 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h

    r1027 r1084  
    559559                                                                 const bool useKdSplit); 
    560560 
    561         /** Sorts split candidates for surface area heuristics for axis aligned splits. 
     561        /** Sorts split candidates for cost heuristics using axis aligned splits. 
    562562                @param polys the input for choosing split candidates 
    563563                @param axis the current split axis 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

    r1077 r1084  
    399399        Debug << "maxband: " << mMaxBand << endl; 
    400400        Debug << "pvs count method: " << mPvsCountMethod << endl; 
    401          
     401 
    402402 
    403403        mSplitCandidates = new vector<SortableEntry>; 
     
    805805        float pos; 
    806806 
    807         // insert all queries 
     807        //-- insert all queries 
    808808        for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri) 
    809809        { 
     
    25592559        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand); 
    25602560         
     2561        mSplitBorder = 0.1f; 
     2562 
    25612563 
    25622564        //-- debug output 
     
    27402742 
    27412743void OspTree::EvalSplitCandidate(OspTraversalData &tData, 
    2742                                                                  OspSplitCandidate &splitData) 
     2744                                                                 OspSplitCandidate &splitCandidate) 
    27432745{ 
    27442746        float frontProb; 
     
    27482750 
    27492751        // compute locally best split plane 
    2750         const bool success = false; 
    2751 #if TODO 
    2752         SelectPlane(tData, splitData.mSplitPlane, 
    2753                                 frontData.mProbability, backData.mProbability); 
     2752        const bool success =  
     2753                SelectSplitPlane(tData, splitCandidate.mSplitPlane,     frontProb, backProb); 
    27542754 
    27552755        //TODO 
     
    27582758        splitData.mParentData = tData; 
    27592759        splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; 
    2760 #endif 
    27612760} 
    27622761 
     
    28422841 
    28432842 
    2844 /* 
    2845 float OspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays, 
     2843float OspTree::EvalLocalCostHeuristics(KdLeaf *node, 
    28462844                                                                           const AxisAlignedBox3 &box, 
    2847                                                                            int pvsSize, 
    28482845                                                                           const int axis, 
    2849                                                                            float &position) 
    2850 { 
     2846                                                                           float &position, 
     2847                                                                           int &objectsBack, 
     2848                                                                           int &objectsFront) 
     2849{ 
     2850         
     2851        SortSplitCandidates(node, axis); 
     2852   
     2853        // go through the lists, count the number of objects left and right 
     2854        // and evaluate the following cost funcion: 
     2855        // C = ct_div_ci  + (ol + or)/queries 
     2856         
     2857        int pvsSize = PrepareHeuristics(node->mObjects);; 
     2858        int pvsl = 0, pvsr = pvsSize; 
     2859   
    28512860        const float minBox = box.Min(axis); 
    28522861        const float maxBox = box.Max(axis); 
    28532862 
    28542863        const float sizeBox = maxBox - minBox; 
    2855  
    2856         const float minBand = minBox + mMinBand * sizeBox; 
    2857         const float maxBand = minBox + mMaxBand * sizeBox; 
    2858  
    2859         SortSplitCandidates(rays, axis, minBand, maxBand); 
    2860  
    2861         // prepare the sweep  
    2862         // (note: returns pvs size, so there would be no need  
    2863         // to give pvs size as argument) 
    2864         pvsSize = PrepareHeuristics(rays); 
    2865  
    2866         Debug << "here45 pvs: " << pvsSize << endl; 
    2867  
    2868         // go through the lists, count the number of objects left and right 
    2869         // and evaluate the following cost funcion: 
    2870         // C = ct_div_ci  + (ql*rl + qr*rr)/queries 
    2871  
    2872         int pvsl = 0; 
    2873         int pvsr = pvsSize; 
    2874  
    2875         int pvsBack = pvsl; 
    2876         int pvsFront = pvsr; 
    2877  
    2878         float sum = (float)pvsSize * sizeBox; 
    2879         float minSum = 1e20f; 
    2880  
    2881          
     2864         
     2865                         
    28822866        // if no good split can be found, take mid split 
    28832867        position = minBox + 0.5f * sizeBox; 
     
    28862870        float ratio = 99999999.0f; 
    28872871        bool splitPlaneFound = false; 
    2888  
    2889         Intersectable::NewMail(); 
    2890         KdLeaf::NewMail(); 
    2891  
     2872   
     2873        float minBand = minBox + mSplitBorder * (maxBox - minBox); 
     2874        float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox); 
     2875 
     2876    float minSum = 1e20f; 
     2877 
     2878        int pvsBack = pvsl; 
     2879        int pvsFront = pvsr; 
     2880 
     2881        float sum = (float)pvsSize * sizeBox; 
    28922882 
    28932883        vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end(); 
     
    29462936        return ratio; 
    29472937} 
    2948 */ 
    2949  
    2950 float OspTree::EvalLocalCostHeuristics(BspLeaf *node, 
    2951                                                                            const AxisAlignedBox3 &box, 
    2952                                                                            const int axis, 
    2953                                                                            float &position, 
    2954                                                                            int &objectsBack, 
    2955                                                                            int &objectsFront) 
    2956 { 
    2957          
    2958         /*SortSplitCandidates(node, axis); 
    2959    
    2960         // go through the lists, count the number of objects left and right 
    2961         // and evaluate the following cost funcion: 
    2962         // C = ct_div_ci  + (ol + or)/queries 
    2963  
    2964         float totalIntersections = 0.0f; 
    2965          
    2966         vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end(); 
    2967  
    2968         for(ci = splitCandidates->begin(); ci != ci_end; ++ ci) 
    2969         { 
    2970                  if ((*ci).type == SortableEntry::BOX_MIN)  
    2971                  { 
    2972                          totalIntersections += (*ci).intersectable->IntersectionComplexity(); 
    2973                  } 
    2974         } 
    2975          
    2976         float intersectionsLeft = 0; 
    2977         float intersectionsRight = totalIntersections; 
    2978  
    2979          
    2980         int objectsLeft = 0, objectsRight = (int)node->mObjects.size(); 
    2981    
    2982         float minBox = box.Min(axis); 
    2983         float maxBox = box.Max(axis); 
    2984          
    2985         float boxArea = box.SurfaceArea(); 
    2986    
    2987         float minBand = minBox + mSplitBorder*(maxBox - minBox); 
    2988         float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox); 
    2989  
    2990     float minSum = 1e20f; 
    2991    
    2992         for(ci = splitCandidates->begin(); ci != ci_end; ++ ci) 
    2993         { 
    2994                 EvalPvsIncr(ci, pvsl, pvsr); 
    2995  
    2996                 if ((*ci).value > minBand && (*ci).value < maxBand)  
    2997                 { 
    2998                         AxisAlignedBox3 lbox = box; 
    2999                         AxisAlignedBox3 rbox = box; 
    3000                          
    3001                         lbox.SetMax(axis, (*ci).value); 
    3002                         rbox.SetMin(axis, (*ci).value); 
    3003  
    3004                         float sum; 
    3005                          
    3006                         if (mSahUseFaces) 
    3007                                 sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea(); 
    3008                         else 
    3009                                 sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea(); 
    3010        
    3011                         //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 
    3012                         //      cout<<"cost= "<<sum<<endl; 
    3013        
    3014                         if (sum < minSum)  
    3015                         { 
    3016                                 minSum = sum; 
    3017                                 position = (*ci).value; 
    3018  
    3019                                 objectsBack = objectsLeft; 
    3020                                 objectsFront = objectsRight; 
    3021                         } 
    3022                 } 
    3023         } 
    3024    
    3025         float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size(); 
    3026         float newCost = mCt_div_ci + minSum/boxArea; 
    3027         float ratio = newCost/oldCost; 
    3028    
    3029 #if 0 
    3030         cout<<"===================="<<endl; 
    3031         cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox) 
    3032                 <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl; 
    3033 #endif 
    3034          
    3035         return ratio; 
    3036         */ 
    3037         return 0; 
    3038 } 
    3039  
    3040  
    3041 void OspTree::SortSplitCandidates(const RayInfoContainer &rays, 
    3042                                                                   const int axis,  
    3043                                                                   float minBand,  
    3044                                                                   float maxBand) 
    3045 { 
    3046         // TODO 
     2938 
     2939void OspTree::SortSplitCandidates(KdLeaf *node, const int axis) 
     2940{ 
     2941        mSplitCandidates->clear(); 
     2942 
     2943        int requestedSize = 2*(int)node->mObjects.size(); 
     2944         
     2945        // creates a sorted split candidates array 
     2946        if (mSplitCandidates->capacity() > 500000 && 
     2947                requestedSize < (int)(mSplitCandidates->capacity()/10))  
     2948        { 
     2949                delete mSplitCandidates; 
     2950                mSplitCandidates = new vector<SortableEntry>; 
     2951        } 
     2952 
     2953        mSplitCandidates->reserve(requestedSize); 
     2954         
     2955        ObjectContainer::const_iterator mi, mi_end = node->mObjects.end(); 
     2956 
     2957        // insert all queries  
     2958        for(mi = node->mObjects.begin(); mi != mi_end; ++ mi)  
     2959        { 
     2960                AxisAlignedBox3 box = (*mi)->GetBox(); 
     2961 
     2962                mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MIN, 
     2963                                        box.Min(axis), *mi)); 
     2964 
     2965 
     2966                mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MAX, 
     2967                                        box.Max(axis), *mi)); 
     2968        } 
     2969 
     2970        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end()); 
    30472971} 
    30482972 
     
    30752999 
    30763000 
    3077 int OspTree::PrepareHeuristics(const RayInfoContainer &rays) 
     3001int OspTree::PrepareHeuristics(const ObjectContainer &objects) 
    30783002{        
    30793003        Intersectable::NewMail(); 
    3080         KdNode::NewMail(); 
     3004        ViewCell::NewMail(); 
    30813005 
    30823006        int pvsSize = 0; 
    30833007 
    3084         RayInfoContainer::const_iterator ri, ri_end = rays.end(); 
    3085  
    3086         //-- set all kd nodes as belonging to the front pvs 
    3087  
    3088         for (ri = rays.begin(); ri != ri_end; ++ ri) 
    3089         { 
    3090                 Intersectable *oObject = (*ri).mRay->mOriginObject; 
    3091  
    3092                 if (oObject) 
    3093                 { 
    3094                         pvsSize += PrepareHeuristics(oObject);           
    3095                 } 
    3096  
    3097                 Intersectable *tObject = (*ri).mRay->mTerminationObject; 
    3098  
    3099                 if (tObject) 
    3100                 { 
    3101                         pvsSize += PrepareHeuristics(tObject);   
    3102                 } 
     3008        ObjectContainer::const_iterator oit, oit_end = objects.end(); 
     3009 
     3010        //-- set all pvs as belonging to the front pvs 
     3011        for (oit = objects.begin(); oit != oit_end; ++ oit) 
     3012        { 
     3013                Intersectable *obj = *oit; 
     3014 
     3015                pvsSize += PrepareHeuristics(obj);               
    31033016        } 
    31043017 
     
    31563069                } 
    31573070        } 
     3071} 
     3072 
     3073 
     3074float OspTree::SelectSplitPlane(const VspTraversalData &tData, 
     3075                                                                AxisAlignedPlane &plane, 
     3076                                                                float &pFront, 
     3077                                                                float &pBack) 
     3078{ 
     3079        float nPosition[3]; 
     3080        float nCostRatio[3]; 
     3081        float nProbFront[3]; 
     3082        float nProbBack[3]; 
     3083 
     3084        // create bounding box of node geometry 
     3085        AxisAlignedBox3 box = tData.mBoundingBox; 
     3086                 
     3087        int sAxis = 0; 
     3088        int bestAxis = -1; 
     3089 
     3090        if (mOnlyDrivingAxis) 
     3091        { 
     3092                sAxis = box.Size().DrivingAxis(); 
     3093        } 
     3094 
     3095        //sAxis = 2; 
     3096        for (int axis = 0; axis < 3; ++ axis) 
     3097        { 
     3098                if (!mOnlyDrivingAxis || (axis == sAxis)) 
     3099                { 
     3100                        //-- place split plane using heuristics 
     3101 
     3102                        if (mUseCostHeuristics) 
     3103                        { 
     3104                                nCostRatio[axis] = 
     3105                                        EvalLocalCostHeuristics(*tData.mRays, 
     3106                                                                                        box, 
     3107                                                                                        tData.mPvs, 
     3108                                                                                        axis, 
     3109                                                                                        nPosition[axis]);                        
     3110                        } 
     3111                        else //-- split plane position is spatial median 
     3112                        { 
     3113                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f; 
     3114 
     3115                                nCostRatio[axis] = EvalLocalSplitCost(tData, 
     3116                                                                                                          box, 
     3117                                                                                                          axis, 
     3118                                                                                                          nPosition[axis], 
     3119                                                                                                          nProbFront[axis],  
     3120                                                                                                          nProbBack[axis]); 
     3121                        } 
     3122                                                 
     3123                        if (bestAxis == -1) 
     3124                        { 
     3125                                bestAxis = axis; 
     3126                        } 
     3127                        else if (nCostRatio[axis] < nCostRatio[bestAxis]) 
     3128                        { 
     3129                                bestAxis = axis; 
     3130                        }  
     3131                } 
     3132        } 
     3133 
     3134 
     3135        //-- assign values 
     3136         
     3137        plane.mAxis = bestAxis; 
     3138        // split plane position 
     3139    plane.mPosition = nPosition[bestAxis]; 
     3140 
     3141        pFront = nProbFront[bestAxis]; 
     3142        pBack = nProbBack[bestAxis]; 
     3143 
     3144        //Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl; 
     3145        return nCostRatio[bestAxis]; 
    31583146} 
    31593147 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h

    r1077 r1084  
    871871                The split candidates are generated on possible visibility 
    872872                events (i.e., where ray segments intersect the ray boundaries). 
    873                 The sorted candidates are needed to compute the SAH. 
     873                The sorted candidates are needed to compute the heuristics. 
    874874 
    875875                @param polys the input for choosing split candidates 
     
    882882                                                         float maxBand); 
    883883 
    884         /** Computes pvs increase with respect to the previous pvs for SAH. 
     884        /** Computes pvs increase with respect to the previous pvs for heuristics. 
    885885        */ 
    886886        int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes); 
     
    910910        void AddContriToPvs(KdLeaf *leaf, int &pvs) const; 
    911911 
    912         /** Prepares objects for SAH. 
     912        /** Prepares objects for the heuristics. 
    913913                @returns pvs size of the ray container 
    914914        */ 
     
    14381438                                          float &pBack); 
    14391439 
    1440         /** Sorts split candidates for surface area heuristics for axis aligned splits. 
    1441                 @param polys the input for choosing split candidates 
     1440        /** Sorts split candidates for cost heuristics using axis aligned splits. 
     1441                @param node the current node 
    14421442                @param axis the current split axis 
    1443                 @param splitCandidates returns sorted list of split candidates 
    1444         */ 
    1445         void SortSplitCandidates(const RayInfoContainer &rays,  
    1446                                                          const int axis,  
    1447                                                          float minBand,  
    1448                                                          float maxBand); 
     1443        */ 
     1444        void SortSplitCandidates(KdLeaf *node, const int axis); 
    14491445 
    14501446        /** Computes best cost for axis aligned planes. 
    14511447        */ 
    1452 /*      float EvalLocalCostHeuristics(const RayInfoContainer &rays, 
    1453                                                                   const AxisAlignedBox3 &box, 
    1454                                                                   const int pvsSize, 
    1455                                                                   const int axis, 
    1456                                                                   float &position); 
    1457 */ 
    1458         float EvalLocalCostHeuristics(BspLeaf *node, 
     1448        float EvalLocalCostHeuristics(KdLeaf *node, 
    14591449                const AxisAlignedBox3 &box, 
    14601450                const int axis, 
     
    15041494        inline bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const; 
    15051495 
     1496        float SelectSplitPlane(const VspTraversalData &tData, 
     1497                                                                AxisAlignedPlane &plane, 
     1498                                                                float &pFront, 
     1499                                                                float &pBack); 
    15061500        /** Adds ray sample contributions to the PVS. 
    15071501                @param sampleContributions the number contributions of the samples 
     
    15431537        void AddContriToPvs(Intersectable *object, int &pvs) const; 
    15441538 
    1545         /** Prepares objects for SAH. 
    1546                 @returns pvs size of the ray container 
    1547         */ 
    1548         int PrepareHeuristics(const RayInfoContainer &rays); 
     1539        /** Prepares objects for the cost heuristics. 
     1540                @returns pvs size of the node 
     1541        */ 
     1542        int PrepareHeuristics(const ObjectContainer &objects); 
    15491543 
    15501544        int PrepareHeuristics(Intersectable *object); 
     
    16311625        int mCreatedViewCells; 
    16321626 
     1627        float mSplitBorder; 
     1628 
     1629 
    16331630private: 
    16341631 
Note: See TracChangeset for help on using the changeset viewer.