Changeset 1137 for GTP/trunk/Lib/Vis/Preprocessing/src
- Timestamp:
- 07/17/06 18:17:09 (18 years ago)
- Location:
- GTP/trunk/Lib/Vis/Preprocessing/src
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp
r1106 r1137 1264 1264 mLocalSplitCandidates->reserve(requestedSize); 1265 1265 1266 float pos;1267 1268 // float values => don't compare with exact values1269 1266 if (0) 1270 { 1267 { // float values => don't compare with exact values 1271 1268 minBand += Limits::Small; 1272 1269 maxBand -= Limits::Small; … … 1277 1274 { 1278 1275 const bool positive = (*ri).mRay->HasPosDir(axis); 1279 1280 pos = (*ri).ExtrapOrigin(axis); 1276 float pos = (*ri).ExtrapOrigin(axis); 1277 1281 1278 // clamp to min / max band 1282 1279 if (0) ClipValue(pos, minBand, maxBand); … … 1286 1283 1287 1284 pos = (*ri).ExtrapTermination(axis); 1285 1288 1286 // clamp to min / max band 1289 1287 if (0) ClipValue(pos, minBand, maxBand); -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp
r1135 r1137 934 934 float pos; 935 935 936 RayInfoContainer::const_iterator rit, rit_end = rays.end(); 937 936 938 //-- insert all queries 937 for ( RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)938 { 939 const bool positive = (*ri ).mRay->HasPosDir(axis);939 for (rit = rays.begin(); rit != rit_end; ++ rit) 940 { 941 const bool positive = (*rit).mRay->HasPosDir(axis); 940 942 941 pos = (*ri ).ExtrapOrigin(axis);943 pos = (*rit).ExtrapOrigin(axis); 942 944 943 945 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 944 pos, (*ri ).mRay));945 946 pos = (*ri ).ExtrapTermination(axis);946 pos, (*rit).mRay)); 947 948 pos = (*rit).ExtrapTermination(axis); 947 949 948 950 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 949 pos, (*ri ).mRay));951 pos, (*rit).mRay)); 950 952 } 951 953 … … 1005 1007 1006 1008 //-- the objects belonging to several leaves must be handled seperately 1009 1007 1010 ObjectContainer::const_iterator oit, oit_end = node->mMultipleObjects.end(); 1008 1011 … … 2625 2628 2626 2629 2627 /*****************************************************************/ 2628 /* class OspTree implementation */ 2629 /*****************************************************************/ 2630 void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells) 2631 { 2632 // if no precomputation of view cells 2633 CastLineSegment(ray.mOrigin, ray.mTermination, viewCells); 2634 } 2635 2636 2637 /*******************************************************************/ 2638 /* class OspTree implementation */ 2639 /*******************************************************************/ 2630 2640 2631 2641 … … 3009 3019 3010 3020 const int totalPvs = tData.mNode->mObjects.size(); 3011 3012 3021 3022 int pvsl = 0; 3023 int pvsr = totalPvs; 3024 3013 3025 // if no good split can be found, take mid split 3014 int pvsBack = totalPvs / 2;3026 position = minBox + 0.5f * sizeBox; 3015 3027 3016 3028 // the relative cost ratio … … 3023 3035 float volFront = volr; 3024 3036 3037 int pvsBack = 0; 3038 int pvsFront = 0; 3039 3040 3025 3041 float sum = (float)totalVol * sizeBox; 3026 3042 3027 int currentPvs = 0;3028 3029 3043 Intersectable::NewMail(); 3030 3031 //-- traverse through visibility events 3044 ViewCell::NewMail(); 3045 3046 //-- traverse through events and find best split plane 3032 3047 3033 3048 vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end(); 3034 3049 3035 for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci , ++ currentPvs)3050 for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci) 3036 3051 { 3037 3052 Intersectable *object = (*ci).mObject; 3038 3053 3039 // new object in this node -> add to the pvs 3040 if (!object->Mailed()) 3041 { 3042 object->Mail(); 3043 ++ currentPvs; 3044 } 3045 3046 EvalViewCellVolumeIncr(*ci, voll, volr); 3054 EvalHeuristicsContribution(*ci, voll, volr, pvsl, pvsr); 3047 3055 3048 3056 cout << "incr: " << ci->mObject->mViewCellPvs.GetSize() << " obj id " … … 3053 3061 { 3054 3062 //sum = costl * ((*ci).value - minBox) + costr * (maxBox - (*ci).value); 3055 sum = voll * currentPvs + volr * (totalPvs - currentPvs); 3056 3057 cout << "pos=" << currentPvs << "\t volt=(" << voll << "," 3058 << volr << ")" << "\t volt= " << sum << endl; 3063 sum = voll * pvsBack + volr * pvsFront; 3064 3065 cout << "pos: " << (*ci).mPos 3066 << "\t (pvsl: " << pvsBack << ", pvsr: " << pvsFront << ")" 3067 << "\t (voll: " << voll << ", volr: " << volr << ")" 3068 << "\t sum: " << sum << endl; 3059 3069 3060 3070 if (sum < minSum) … … 3063 3073 3064 3074 minSum = sum; 3065 pvsBack = currentPvs; 3075 3076 pvsBack = pvsl; 3077 pvsFront = pvsr; 3066 3078 3067 3079 volBack = voll; 3068 3080 volFront = volr; 3069 } 3070 } 3071 } 3072 3081 3082 position = (*ci).mPos; 3083 } 3084 } 3085 } 3086 3087 3073 3088 //-- compute cost 3074 3089 … … 3081 3096 3082 3097 const float penaltyOld = (float)totalPvs;//EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit); 3083 const float penaltyFront = (float) totalPvs - pvsBack;//EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);3098 const float penaltyFront = (float)pvsFront;//EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 3084 3099 const float penaltyBack = (float)pvsBack;//EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 3085 3100 … … 3113 3128 KdLeaf *leaf = tData.mNode; 3114 3129 3115 int requestedSize = 2 * (int)rays->size() ;3130 int requestedSize = 2 * (int)rays->size() + 2 * (int)leaf->mObjects.size(); 3116 3131 3117 3132 // creates a sorted split candidates array … … 3127 3142 float pos; 3128 3143 3129 //-- insert all queries 3130 for (RayInfoContainer::const_iterator ri = rays->begin(); ri < rays->end(); ++ ri) 3131 { 3132 const bool positive = (*ri).mRay->HasPosDir(axis); 3133 3134 pos = (*ri).ExtrapOrigin(axis); 3135 3136 3137 //if (mOspTree->GetLeaf() == leaf) 3138 3139 /* mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 3140 pos, (*ri).mRay)); 3141 3142 pos = (*ri).ExtrapTermination(axis); 3143 3144 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 3145 pos, (*ri).mRay));*/ 3144 //-- insert ray queries 3145 //-- we are intersested only in rays which intersect an object that 3146 //-- is part of the kd node because they can induce a change in view cell 3147 //-- volume on the left and the right part. 3148 //-- Note that they cannot induce a change in pvs size!! 3149 3150 RayInfoContainer::const_iterator rit, rit_end = rays->end(); 3151 3152 for (rit = rays->begin(); rit < rit_end; ++ rit) 3153 { 3154 VssRay *ray = (*rit).mRay; 3155 3156 const bool positive = ray->HasPosDir(axis); 3157 3158 // if hitpoint with object is inside this node 3159 if (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf) 3160 { 3161 pos = ray->mOrigin[axis]; 3162 3163 mSplitCandidates->push_back( 3164 SortableEntry(SortableEntry::BOX_INTERSECT, 3165 pos, 3166 ray->mOriginObject, 3167 ray) 3168 ); 3169 } 3170 3171 if (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf) 3172 { 3173 pos = ray->mTermination[axis]; 3174 3175 mSplitCandidates->push_back( 3176 SortableEntry(SortableEntry::BOX_INTERSECT, 3177 pos, 3178 ray->mOriginObject, 3179 ray) 3180 ); 3181 } 3182 } 3183 3184 3185 //-- insert object queries 3186 //-- These queries can induce a change in pvs size. 3187 //-- Note that they cannot induce a change in view cell volume, as 3188 //-- there is no ray associated with these events!! 3189 3190 ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end(); 3191 3192 for (oit = leaf->mObjects.begin(); oit != leaf->mObjects.end(); ++ oit ) 3193 { 3194 Intersectable *object = *oit; 3195 const AxisAlignedBox3 box = object->GetBox(); 3196 3197 mSplitCandidates->push_back( 3198 SortableEntry(SortableEntry::BOX_MIN, 3199 box.Min(axis), 3200 object, 3201 NULL) 3202 ); 3203 3204 3205 mSplitCandidates->push_back( 3206 SortableEntry(SortableEntry::BOX_MAX, 3207 box.Max(axis), 3208 object, 3209 NULL) 3210 ); 3146 3211 } 3147 3212 … … 3150 3215 3151 3216 3152 float OspTree::PrepareHeuristics(Intersectable *object)3153 {3154 if (mUseEqualWeightForHeuristics)3155 {3156 // like sah: each object has weight one for heuristics3157 return 1;3158 }3159 else3160 {3161 // the priotity of the object is the sum of view cells3162 // weighted per their volume3163 float vol = 0;3164 return vol;3165 //return object->mViewCellPvs.GetSize();3166 }3167 }3168 3169 3170 3217 const OspTreeStatistics &OspTree::GetStatistics() const 3171 3218 { … … 3174 3221 3175 3222 3176 float OspTree::PrepareHeuristics(const ObjectContainer &objects) 3223 float OspTree::PrepareHeuristics(const VssRay &ray) 3224 { 3225 float vol = 0; 3226 3227 ViewCellContainer viewCells; 3228 3229 mVspTree->GetViewCells(ray); 3230 3231 ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 3232 3233 for (vit = viewCells.begin(); vit != vit_end; ++ vit) 3234 { 3235 ViewCell *vc = (*vit); 3236 3237 if (!vc->Mailed()) 3238 { 3239 vc->Mail(); 3240 vc->mCounter = 0; 3241 vol += vc->GetVolume(); 3242 } 3243 } 3244 3245 return vol; 3246 } 3247 3248 3249 float OspTree::PrepareHeuristics(const OspTraversalData &tData) 3177 3250 { 3178 3251 Intersectable::NewMail(); … … 3181 3254 float vol = 0; 3182 3255 3183 ObjectContainer::const_iterator oit, oit_end = objects.end(); 3184 3185 //-- set all view cell volume as belonging to front volume 3186 for (oit = objects.begin(); oit != oit_end; ++ oit) 3187 { 3188 Intersectable *obj = *oit; 3189 vol += PrepareHeuristics(obj); 3256 KdLeaf *leaf = tData.mNode; 3257 3258 RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end(); 3259 3260 for (rit = tData.mRays->begin(); rit < rit_end; ++ rit) 3261 { 3262 VssRay *ray = (*rit).mRay; 3263 3264 // if hitpoint with one of the objects is inside this node, we 3265 // evaluate the volume of the view cells seen by this ray 3266 if ((GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf) || 3267 (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf)) 3268 { 3269 vol += PrepareHeuristics(ray); 3270 } 3190 3271 } 3191 3272 … … 3194 3275 3195 3276 3196 void OspTree::EvalViewCellVolumeIncr(const SortableEntry &ci, 3197 float &volLeft, 3198 float &volRight) const 3277 void OspTree::EvalHeuristicsContribution(const SortableEntry &ci, 3278 float &volLeft, 3279 float &volRight, 3280 int &pvsLeft, 3281 int &pvsRight) 3199 3282 { 3200 3283 Intersectable *obj = ci.mObject; 3284 VssRay *ray = ci.mRay; 3201 3285 3202 3286 switch (ci.mType) 3203 3287 { 3288 // add reverse pvs to left side of split plane 3204 3289 case SortableEntry::BOX_MIN: 3205 AddContriToPvs(obj, volLeft);3290 ++ pvsLeft; 3206 3291 break; 3207 3292 3208 3293 case SortableEntry::BOX_MAX: 3209 RemoveContriFromPvs(obj, volRight);3294 -- pvsRight; 3210 3295 break; 3296 3297 // compute volume contribution from view cells 3298 case SortableEntry::BOX_INTERSECT: 3299 EvalVolumeContribution(*ray, volRight, volLeft); 3300 break; 3301 default: 3302 cout << "should not come here" << endl; 3303 break; 3211 3304 } 3212 3305 … … 3215 3308 3216 3309 3310 void OspTree::EvalVolumeContribution(const VssRay &ray, float &volLeft, float &volRight) 3311 { 3312 ViewCellContainer viewCells; 3313 3314 mVspTree->GetViewCells(ray, viewCells); 3315 3316 ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 3317 3318 for (vit = viewCells.begin(); vit != vit_end; ++ vit) 3319 { 3320 // view cells comes to left child node 3321 ViewCell *viewCell = *vit; 3322 3323 if (!viewCell->Mailed()) 3324 { 3325 viewCell->Mail(); 3326 volLeft += viewCell->GetVolume(); 3327 } 3328 3329 // remove from right child node 3330 3331 if (-- viewCell->mCounter == 0) 3332 { 3333 volRight -= viewCell->GetVolume(); 3334 } 3335 } 3336 } 3337 3338 3217 3339 void OspTree::SetViewCellsManager(ViewCellsManager *vcm) 3218 3340 { … … 3224 3346 { 3225 3347 return mBoundingBox; 3226 }3227 3228 3229 void OspTree::RemoveContriFromPvs(Intersectable *object, float &pvs) const3230 {3231 if (mUseEqualWeightForHeuristics)3232 -- pvs;3233 else3234 // the cost of an object is the number of view cells it is part of3235 pvs -= object->mViewCellPvs.GetSize();3236 }3237 3238 3239 void OspTree::AddContriToPvs(Intersectable *object, float &pvs) const3240 {3241 if (mUseEqualWeightForHeuristics)3242 ++ pvs;3243 else3244 // the cost of an object is the number of view cells it is part of3245 pvs += object->mViewCellPvs.GetSize();3246 3348 } 3247 3349 … … 3279 3381 3280 3382 nCostRatio[axis] = 3281 EvalLocalCostHeuristics(tData .mNode,3383 EvalLocalCostHeuristics(tData, 3282 3384 tData.mBoundingBox, 3283 3385 axis, … … 3325 3427 3326 3428 3327 float OspTree::EvalViewCellPvsIncr(Intersectable *object) const3328 {3329 if (mUseEqualWeightForHeuristics)3330 return 1;3331 else3332 return (float)object->mViewCellPvs.GetSize();3333 }3334 3335 3336 3429 float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane, 3337 3430 const OspTraversalData &data) const … … 3357 3450 ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end(); 3358 3451 3452 //TODO §§matt: have to evaluate view cell volume on left and right cell 3359 3453 for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit) 3360 3454 { … … 3362 3456 const AxisAlignedBox3 box = obj->GetBox(); 3363 3457 3364 const float pvsIncr = EvalViewCellPvsIncr(obj);3365 totalPvs += pvsIncr; 3366 cout << "totalpvs " << totalPvs << " incr " << pvsIncr <<endl;3458 ++ totalPvs; 3459 3460 cout << "totalpvs " << totalPvs << endl; 3367 3461 3368 3462 if (box.Max(candidatePlane.mAxis) > candidatePlane.mPosition) 3369 3463 { 3370 pvsFront += pvsIncr; 3371 } 3372 if (box.Min(candidatePlane.mAxis) > candidatePlane.mPosition) 3373 { 3374 pvsBack += pvsIncr; 3375 } 3376 } 3464 ++ pvsFront; 3465 } 3466 if (box.Min(candidatePlane.mAxis) < candidatePlane.mPosition) 3467 { 3468 ++ pvsBack; 3469 } 3470 } 3471 3472 3473 ViewCell::NewMail(); 3474 3475 RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end(); 3476 3477 for (rit = tData.mRays->begin(); rit < rit_end; ++ rit) 3478 { 3479 VssRay *ray = (*rit).mRay; 3480 3481 // if hitpoint with one of the objects is inside this node 3482 if (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf) 3483 { 3484 if (ray->mOrigin[candidatePlane.mAxis] > candidatePlane.mPosition) 3485 { 3486 // add view cells volume to front 3487 mVspTree->GetViewCells(ray, viewCells); 3488 3489 ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 3490 3491 for (vit = viewCells.begin(); vit != vit_end; ++ vit) 3492 { 3493 ViewCell *vc = *vit; 3494 3495 if (!vit->Mailed()) 3496 { 3497 vit->Mail(); 3498 volBack += vc->GetVolume(); 3499 } 3500 } 3501 } 3502 else 3503 {// TODO matt§§ 3504 // add view cells volume to back 3505 if (ray->mOrigin[candidatePlane.mAxis] < candidatePlane.mPosition) 3506 { 3507 // add view cells volume to front 3508 mVspTree->GetViewCells(ray, viewCells); 3509 3510 ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 3511 3512 for (vit = viewCells.begin(); vit != vit_end; ++ vit) 3513 { 3514 ViewCell *vc = *vit; 3515 3516 if (!vit->Mailed()) 3517 { 3518 vit->Mail(); 3519 volBack += vc->GetVolume(); 3520 } 3521 } 3522 } 3523 } 3524 } 3525 } 3526 3377 3527 3378 3528 … … 3776 3926 mVspTree(vspTree), mOspTree(ospTree) 3777 3927 { 3928 // cross references 3778 3929 mVspTree.mOspTree = &ospTree; 3930 mOspTree.mVspTree = &vspTree; 3779 3931 } 3780 3932 -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
r1135 r1137 749 749 void AddViewCellReferences(ViewCell *vc) const; 750 750 751 /** Returns view cells of this ray, either taking precomputed cells 752 or by recomputation. 753 */ 754 void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells); 755 751 756 752 757 /// pointer to the hierarchy of view cells … … 900 905 /** Computes best cost for axis aligned planes. 901 906 */ 902 float EvalLocalCostHeuristics(const VspTraversalData & data,907 float EvalLocalCostHeuristics(const VspTraversalData &tData, 903 908 const AxisAlignedBox3 &box, 904 909 const int axis, … … 1365 1370 struct SortableEntry 1366 1371 { 1372 /** There is a 3th "event" for rays which intersect a 1373 box in the middle. These "events" don't induce a change in 1374 pvs size, but may induce a change in view cell volume. 1375 */ 1367 1376 enum EType 1368 1377 { 1369 ERayMin, 1370 ERayMax 1378 BOX_MIN, 1379 BOX_MAX, 1380 BOX_INTERSECT 1371 1381 }; 1372 1382 … … 1374 1384 //int mPvs; 1375 1385 float mPos; 1376 1386 VssRay *mRay; 1387 1377 1388 Intersectable *mObject; 1378 1389 1379 1390 SortableEntry() {} 1380 1391 1381 SortableEntry(const int type, 1392 SortableEntry(const int type, 1382 1393 //const float pvs, 1383 1394 const float pos, 1384 Intersectable *obj): 1395 Intersectable *obj, 1396 VssRay *ray): 1385 1397 mType(type), 1386 1398 //mPvs(pvs), 1387 1399 mPos(pos), 1388 mObject(obj) 1400 mObject(obj), 1401 mRay(ray) 1389 1402 {} 1390 1403 … … 1417 1430 float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane, 1418 1431 const OspTraversalData &data) const; 1419 1420 float EvalViewCellPvsIncr(Intersectable *object) const;1421 1432 1422 1433 … … 1490 1501 /** Computes best cost for axis aligned planes. 1491 1502 */ 1492 float EvalLocalCostHeuristics(const OspTraversalData & data,1503 float EvalLocalCostHeuristics(const OspTraversalData &tData, 1493 1504 const AxisAlignedBox3 &box, 1494 1505 const int axis, … … 1565 1576 float GetMemUsage() const; 1566 1577 1567 /** Evaluates the influence on the pvs of the visibility event ve.1578 /** Evaluates the influence on the pvs of the event. 1568 1579 @param ve the visibility event 1569 1580 @param pvsLeft updates the left pvs 1570 1581 @param rightPvs updates the right pvs 1571 1582 */ 1572 void Eval ViewCellVolumeIncr(const SortableEntry &ve,1583 void EvalHeuristicsContribution(const SortableEntry &ci, 1573 1584 float &volLeft, 1574 float &volRight) const; 1575 1576 void RemoveContriFromPvs(Intersectable *object, float &pvs) const; 1577 void AddContriToPvs(Intersectable *object, float &pvs) const; 1585 float &volRight, 1586 int &pvsLeft, 1587 int &pvsRight); 1588 1589 /** Evaluate the contributions of view cell volume of the left and the right view cell. 1590 */ 1591 void EvalVolumeContribution(const VssRay &ray, float &volLeft, float &volRight); 1578 1592 1579 1593 /** Prepares objects for the cost heuristics. 1580 1594 @returns pvs size of the node 1581 1595 */ 1582 float PrepareHeuristics(const ObjectContainer &objects); 1583 1584 /** Evaluates contribution for one object 1585 to heuristics preparation. 1586 */ 1587 float PrepareHeuristics(Intersectable *object); 1596 float PrepareHeuristics(const OspTraversalData &tData); 1597 1598 /** Prepares heuristics for a particular ray. 1599 */ 1600 float PrepareHeuristics(const VssRay &ray); 1588 1601 1589 1602 /** Prepares construction for vsp and osp trees. … … 1605 1618 1606 1619 protected: 1620 1621 VspTree *mVspTree; 1607 1622 1608 1623 /// The view cells manager
Note: See TracChangeset
for help on using the changeset viewer.