Changeset 1084 for GTP/trunk/Lib/Vis/Preprocessing
- Timestamp:
- 07/06/06 08:55:06 (18 years ago)
- Location:
- GTP/trunk/Lib/Vis/Preprocessing/src
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h
r1027 r1084 882 882 int &objectsFront) const; 883 883 884 /** Sorts split candidates for surface area heuristics foraxis aligned splits.884 /** Sorts split candidates for cost heuristics using axis aligned splits. 885 885 @param polys the input for choosing split candidates 886 886 @param axis the current split axis -
GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h
r1027 r1084 559 559 const bool useKdSplit); 560 560 561 /** Sorts split candidates for surface area heuristics foraxis aligned splits.561 /** Sorts split candidates for cost heuristics using axis aligned splits. 562 562 @param polys the input for choosing split candidates 563 563 @param axis the current split axis -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp
r1077 r1084 399 399 Debug << "maxband: " << mMaxBand << endl; 400 400 Debug << "pvs count method: " << mPvsCountMethod << endl; 401 401 402 402 403 403 mSplitCandidates = new vector<SortableEntry>; … … 805 805 float pos; 806 806 807 // insert all queries807 //-- insert all queries 808 808 for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri) 809 809 { … … 2559 2559 Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand); 2560 2560 2561 mSplitBorder = 0.1f; 2562 2561 2563 2562 2564 //-- debug output … … 2740 2742 2741 2743 void OspTree::EvalSplitCandidate(OspTraversalData &tData, 2742 OspSplitCandidate &split Data)2744 OspSplitCandidate &splitCandidate) 2743 2745 { 2744 2746 float frontProb; … … 2748 2750 2749 2751 // 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); 2754 2754 2755 2755 //TODO … … 2758 2758 splitData.mParentData = tData; 2759 2759 splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; 2760 #endif2761 2760 } 2762 2761 … … 2842 2841 2843 2842 2844 /* 2845 float OspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays, 2843 float OspTree::EvalLocalCostHeuristics(KdLeaf *node, 2846 2844 const AxisAlignedBox3 &box, 2847 int pvsSize,2848 2845 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 2851 2860 const float minBox = box.Min(axis); 2852 2861 const float maxBox = box.Max(axis); 2853 2862 2854 2863 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 2882 2866 // if no good split can be found, take mid split 2883 2867 position = minBox + 0.5f * sizeBox; … … 2886 2870 float ratio = 99999999.0f; 2887 2871 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; 2892 2882 2893 2883 vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end(); … … 2946 2936 return ratio; 2947 2937 } 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 2939 void 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()); 3047 2971 } 3048 2972 … … 3075 2999 3076 3000 3077 int OspTree::PrepareHeuristics(const RayInfoContainer &rays)3001 int OspTree::PrepareHeuristics(const ObjectContainer &objects) 3078 3002 { 3079 3003 Intersectable::NewMail(); 3080 KdNode::NewMail();3004 ViewCell::NewMail(); 3081 3005 3082 3006 int pvsSize = 0; 3083 3007 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); 3103 3016 } 3104 3017 … … 3156 3069 } 3157 3070 } 3071 } 3072 3073 3074 float 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]; 3158 3146 } 3159 3147 -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
r1077 r1084 871 871 The split candidates are generated on possible visibility 872 872 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. 874 874 875 875 @param polys the input for choosing split candidates … … 882 882 float maxBand); 883 883 884 /** Computes pvs increase with respect to the previous pvs for SAH.884 /** Computes pvs increase with respect to the previous pvs for heuristics. 885 885 */ 886 886 int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes); … … 910 910 void AddContriToPvs(KdLeaf *leaf, int &pvs) const; 911 911 912 /** Prepares objects for SAH.912 /** Prepares objects for the heuristics. 913 913 @returns pvs size of the ray container 914 914 */ … … 1438 1438 float &pBack); 1439 1439 1440 /** Sorts split candidates for surface area heuristics foraxis aligned splits.1441 @param polys the input for choosing split candidates1440 /** Sorts split candidates for cost heuristics using axis aligned splits. 1441 @param node the current node 1442 1442 @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); 1449 1445 1450 1446 /** Computes best cost for axis aligned planes. 1451 1447 */ 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, 1459 1449 const AxisAlignedBox3 &box, 1460 1450 const int axis, … … 1504 1494 inline bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const; 1505 1495 1496 float SelectSplitPlane(const VspTraversalData &tData, 1497 AxisAlignedPlane &plane, 1498 float &pFront, 1499 float &pBack); 1506 1500 /** Adds ray sample contributions to the PVS. 1507 1501 @param sampleContributions the number contributions of the samples … … 1543 1537 void AddContriToPvs(Intersectable *object, int &pvs) const; 1544 1538 1545 /** Prepares objects for SAH.1546 @returns pvs size of the ray container1547 */ 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); 1549 1543 1550 1544 int PrepareHeuristics(Intersectable *object); … … 1631 1625 int mCreatedViewCells; 1632 1626 1627 float mSplitBorder; 1628 1629 1633 1630 private: 1634 1631
Note: See TracChangeset
for help on using the changeset viewer.