![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
Changeset 2124 for GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.cpp
- Timestamp:
- 02/19/07 02:51:22 (17 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.cpp
r2094 r2124 7 7 #include "ViewCell.h" 8 8 #include "Beam.h" 9 #include "Exporter.h" 9 10 10 11 … … 59 60 60 61 61 void TraversalInterior::ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild) 62 void TraversalInterior::ReplaceChildLink(TraversalNode *oldChild, 63 TraversalNode *newChild) 62 64 { 63 65 if (mBack == oldChild) … … 71 73 TraversalNode(parent) 72 74 { 73 m Objects.reserve(objects);75 mViewCells.reserve(objects); 74 76 } 75 77 … … 88 90 TraversalTree::TraversalTree() 89 91 { 90 mRoot = new TraversalLeaf(NULL, 0); 92 TraversalLeaf *leaf = new TraversalLeaf(NULL, 0); 93 leaf->mDepth = 0; 94 mRoot = leaf; 91 95 92 96 Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxNodes", mTermMaxNodes); … … 102 106 Environment::GetSingleton()->GetStringValue("TraversalTree.splitMethod", splitType); 103 107 108 splitCandidates = NULL; 104 109 mSplitMethod = SPLIT_SPATIAL_MEDIAN; 110 105 111 if (strcmp(splitType, "spatialMedian") == 0) 106 112 { … … 121 127 else 122 128 { 123 cerr <<"Wrong kd split type "<<splitType<<endl;129 cerr << "Wrong kd split type " << splitType << endl; 124 130 exit(1); 125 131 } 126 127 splitCandidates = NULL; 128 } 129 } 132 } 133 } 134 cout << "Traversal Tree Split method: " << mSplitMethod << endl; 130 135 } 131 136 … … 137 142 138 143 139 bool 140 TraversalTree::Construct() 141 { 142 144 bool TraversalTree::Construct(const ViewCellContainer &viewCells) 145 { 143 146 if (!splitCandidates) 144 147 { … … 149 152 TraversalLeaf *leaf = static_cast<TraversalLeaf *>(mRoot); 150 153 154 leaf->mViewCells = viewCells; 151 155 mStat.nodes = 1; 152 153 156 mBox.Initialize(); 154 157 155 ObjectContainer::const_iterator mi; 156 for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++ mi) 158 ViewCellContainer::const_iterator mi; 159 160 for ( mi = leaf->mViewCells.begin(); mi != leaf->mViewCells.end(); ++ mi) 157 161 { 158 162 mBox.Include((*mi)->GetBox()); … … 163 167 164 168 // remove the allocated array 165 CLEAR_CONTAINER(*splitCandidates); 166 delete splitCandidates; 167 169 if (splitCandidates) 170 { 171 CLEAR_CONTAINER(*splitCandidates); 172 delete splitCandidates; 173 } 174 168 175 return true; 169 176 } … … 182 189 while (!tStack.empty()) 183 190 { 184 // cout<<mStat.Nodes() << " " << mTermMaxNodes << endl;185 191 if (mStat.Nodes() > mTermMaxNodes) 186 192 { … … 226 232 bool TraversalTree::TerminationCriteriaMet(const TraversalLeaf *leaf) 227 233 { 228 const bool criteriaMet = 229 ((int)leaf->mObjects.size() <= mTermMinCost) || 230 (leaf->mDepth >= mTermMaxDepth); 234 const bool criteriaMet = ( 235 ((int)leaf->mViewCells.size() <= mTermMinCost) || 236 (leaf->mDepth >= mTermMaxDepth) 237 || (GetBox(leaf).SurfaceArea() < 0.00001f) 238 ); 231 239 232 240 if (criteriaMet) 233 cerr<< "\n OBJECTS=" << (int)leaf->mObjects.size() << endl; 241 { 242 cerr << "\nOBJECTS=" << (int)leaf->mViewCells.size() << endl; 243 cerr << "\nDEPTH=" << (int)leaf->mDepth << endl; 244 } 234 245 235 246 return criteriaMet; … … 248 259 { 249 260 axis = box.Size().DrivingAxis(); 250 position = (box.Min()[axis] + box.Max()[axis]) *0.5f;261 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f; 251 262 break; 252 263 } … … 254 265 { 255 266 int objectsBack, objectsFront; 256 float costRatio; 257 bool mOnlyDrivingAxis = true; 258 259 if (mOnlyDrivingAxis) 260 { 261 axis = box.Size().DrivingAxis(); 262 costRatio = BestCostRatio(leaf, 263 box, 264 axis, 265 position, 266 objectsBack, 267 objectsFront); 268 } 269 else 270 { 271 costRatio = MAX_FLOAT; 272 273 for (int i=0; i < 3; i++) 267 float costRatio = 99999;//MAX_FLOAT; 268 269 for (int i=0; i < 3; ++ i) 270 { 271 float p; 272 float r = BestCostRatio(leaf, 273 box, 274 i, 275 p, 276 objectsBack, 277 objectsFront); 278 279 if (r < costRatio) 274 280 { 275 float p; 276 float r = BestCostRatio(leaf, 277 box, 278 i, 279 p, 280 objectsBack, 281 objectsFront); 282 283 if (r < costRatio) 284 { 285 costRatio = r; 286 axis = i; 287 position = p; 288 } 281 costRatio = r; 282 axis = i; 283 position = p; 289 284 } 290 285 } … … 292 287 if (costRatio > mMaxCostRatio) 293 288 { 294 //cout<<"Too big cost ratio "<<costRatio<<endl;289 cout << "Too big cost ratio " << costRatio << endl; 295 290 axis = -1; 296 291 } … … 318 313 319 314 if (axis == -1) { 315 cout << "terminate on cost ratio" << endl; 320 316 return leaf; 321 317 } … … 341 337 frontBBox.SetMin(axis, position); 342 338 343 ObjectContainer::const_iterator mi; 344 345 for ( mi = leaf->mObjects.begin(); 346 mi != leaf->mObjects.end(); 347 mi++) 339 ViewCellContainer::const_iterator mi, mi_end = leaf->mViewCells.end(); 340 341 for (mi = leaf->mViewCells.begin(); mi != mi_end; ++ mi) 348 342 { 349 343 // determine the side of this ray with respect to the plane 350 344 AxisAlignedBox3 box = (*mi)->GetBox(); 351 if (box.Max(axis) > position 352 objectsFront++;353 354 if (box.Min(axis) < position 345 if (box.Max(axis) > position) 346 ++ objectsFront; 347 348 if (box.Min(axis) < position) 355 349 ++ objectsBack; 356 350 } 357 358 351 359 352 TraversalLeaf *back = new TraversalLeaf(node, objectsBack); 360 353 TraversalLeaf *front = new TraversalLeaf(node, objectsFront); 361 354 355 back->mDepth = front->mDepth = leaf->mDepth + 1; 362 356 363 357 // replace a link from node's parent … … 370 364 node->SetupChildLinks(back, front); 371 365 372 for (mi = leaf->m Objects.begin(); mi != leaf->mObjects.end(); ++ mi)366 for (mi = leaf->mViewCells.begin(); mi != mi_end; ++ mi) 373 367 { 374 368 // determine the side of this ray with respect to the plane … … 377 371 if (box.Max(axis) >= position ) 378 372 { 379 front->m Objects.push_back(*mi);373 front->mViewCells.push_back(*mi); 380 374 } 381 375 382 376 if (box.Min(axis) < position ) 383 377 { 384 back->m Objects.push_back(*mi);385 } 386 387 mStat.objectRefs -= (int)leaf->m Objects.size();378 back->mViewCells.push_back(*mi); 379 } 380 381 mStat.objectRefs -= (int)leaf->mViewCells.size(); 388 382 mStat.objectRefs += objectsBack + objectsFront; 389 383 } … … 404 398 405 399 app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz)\n"; 406 for (int i=0; i<7; i++) 407 app << splits[i] <<" "; 408 app <<endl; 409 410 app << "#N_RAYREFS ( Number of rayRefs )\n" << 411 rayRefs << "\n"; 412 413 app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" << 414 rayRefs/(double)rays << "\n"; 415 416 app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" << 417 rayRefs/(double)Leaves() << "\n"; 400 401 for (int i = 0; i < 7; ++ i) 402 app << splits[i] << " "; 403 app << endl; 418 404 419 405 app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" << 420 406 maxObjectRefs << "\n"; 421 407 422 app << "#N_ NONEMPTYRAYREFS ( Number of rayRefs in nonEmpty leaves / non emptyleaf )\n" <<423 rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";408 app << "#N_AVGOBJECTREFS ( Avg number of object refs / leaf )\n" << 409 totalObjectRefs / (double)Leaves() << "\n"; 424 410 425 411 app << "#N_LEAFDOMAINREFS ( Number of query domain Refs / leaf )\n" << 426 objectRefs/(double)Leaves() << "\n"; 412 objectRefs / (double)Leaves() << "\n"; 413 414 app << "#N_PEMPTYLEAVES ( Percentage of leaves with zero query domains )\n"<< 415 zeroQueryNodes * 100 / (double)Leaves() << endl; 416 417 app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<< 418 maxDepthNodes * 100 / (double)Leaves() << endl; 419 420 app << "#N_PMINCOSTLEAVES ( Percentage of leaves with minCost )\n"<< 421 minCostNodes * 100 / (double)Leaves() << endl; 427 422 428 423 // app << setprecision(4); 429 430 app << "#N_PEMPTYLEAVES ( Percentage of leaves with zero query domains )\n"<<431 zeroQueryNodes*100/(double)Leaves()<<endl;432 433 app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<434 maxDepthNodes*100/(double)Leaves()<<endl;435 436 app << "#N_PMINCOSTLEAVES ( Percentage of leaves with minCost )\n"<<437 minCostNodes*100/(double)Leaves()<<endl;438 439 app << "#N_ADDED_RAYREFS (Number of dynamically added ray references )\n"<<440 addedRayRefs<<endl;441 442 app << "#N_REMOVED_RAYREFS (Number of dynamically removed ray references )\n"<<443 removedRayRefs<<endl;444 445 // app << setprecision(4);446 447 424 // app << "#N_CTIME ( Construction time [s] )\n" 448 425 // << Time() << " \n"; 449 426 450 app << "===== END OF TraversalTree statistics ==========\n"; 451 427 app << "======= END OF TraversalTree statistics ========\n"; 452 428 } 453 429 … … 455 431 void TraversalTree::EvaluateLeafStats(const TraversalData &data) 456 432 { 457 458 // the node became a leaf -> evaluate stats for leafs 459 TraversalLeaf *leaf = (TraversalLeaf *)data.mNode; 460 461 if (data.mDepth > mTermMaxDepth) 462 mStat.maxDepthNodes++; 463 464 if ( (int)(leaf->mObjects.size()) < mTermMinCost) 465 mStat.minCostNodes++; 466 467 468 if ( (int)(leaf->mObjects.size()) > mStat.maxObjectRefs) 469 mStat.maxObjectRefs = (int)leaf->mObjects.size(); 470 471 } 472 433 // the node became a leaf -> evaluate stats for leafs 434 TraversalLeaf *leaf = (TraversalLeaf *)data.mNode; 435 436 if (data.mDepth > mTermMaxDepth) 437 ++ mStat.maxDepthNodes; 438 439 if ((int)(leaf->mViewCells.size()) < mTermMinCost) 440 ++ mStat.minCostNodes; 441 442 mStat.totalObjectRefs += (int)leaf->mViewCells.size(); 443 444 if ((int)(leaf->mViewCells.size()) > mStat.maxObjectRefs) 445 mStat.maxObjectRefs = (int)leaf->mViewCells.size(); 446 } 473 447 474 448 … … 480 454 //splitCandidates->clear(); 481 455 482 int requestedSize = 2 *(int)node->mObjects.size();456 int requestedSize = 2 * (int)node->mViewCells.size(); 483 457 484 458 // creates a sorted split candidates array 485 459 if (splitCandidates->capacity() > 500000 && 486 requestedSize < (int)(splitCandidates->capacity() /10) )460 requestedSize < (int)(splitCandidates->capacity() / 10) ) 487 461 { 488 462 delete splitCandidates; … … 492 466 splitCandidates->reserve(requestedSize); 493 467 468 494 469 // insert all queries 495 for(ObjectContainer::const_iterator mi = node->mObjects.begin(); 496 mi != node->mObjects.end(); 470 for(ViewCellContainer::const_iterator mi = node->mViewCells.begin(); 471 mi != node->mViewCells.end(); 472 mi++) 473 { 474 AxisAlignedBox3 box = (*mi)->GetBox(); 475 476 splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX, 477 box.Max(axis), 478 *mi) 479 ); 480 } 481 482 // insert all queries 483 for(ViewCellContainer::const_iterator mi = node->mViewCells.begin(); 484 mi != node->mViewCells.end(); 497 485 mi++) 498 486 { … … 503 491 *mi) 504 492 ); 505 506 splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX, 493 /*splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX, 507 494 box.Max(axis), 508 495 *mi) 509 ); 496 );*/ 510 497 } 511 498 … … 550 537 // C = ct_div_ci + (ol + or)/queries 551 538 552 float totalIntersections = 0.0f;553 539 vector<SortableEntry *>::const_iterator ci; 554 540 555 for(ci = splitCandidates->begin(); ci < splitCandidates->end(); ++ ci) 556 if ((*ci)->type == SortableEntry::BOX_MIN) 557 { 558 totalIntersections += (*ci)->intersectable->IntersectionComplexity(); 559 } 560 561 float intersectionsLeft = 0; 562 float intersectionsRight = totalIntersections; 563 564 int objectsLeft = 0, objectsRight = (int)node->mObjects.size(); 541 int objectsLeft = 0, objectsRight = (int)node->mViewCells.size(); 542 543 int dummy1 = objectsLeft, dummy2 = objectsRight; 565 544 566 545 float minBox = box.Min(axis); … … 578 557 { 579 558 case SortableEntry::BOX_MIN: 580 objectsLeft++; 581 intersectionsLeft += (*ci)->intersectable->IntersectionComplexity(); 559 ++ objectsLeft; 582 560 break; 583 561 case SortableEntry::BOX_MAX: 584 objectsRight--; 585 intersectionsRight -= (*ci)->intersectable->IntersectionComplexity(); 562 -- objectsRight; 586 563 break; 587 564 } 588 565 589 if ((*ci)->value > minBand && (*ci)->value <maxBand)566 if ((*ci)->value >= minBand && (*ci)->value <= maxBand) 590 567 { 591 568 AxisAlignedBox3 lbox = box; 592 569 AxisAlignedBox3 rbox = box; 570 593 571 lbox.SetMax(axis, (*ci)->value); 594 572 rbox.SetMin(axis, (*ci)->value); 595 573 596 float sum; 597 598 if (mSahUseFaces) 599 sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea(); 600 else 601 sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea(); 602 603 // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 604 // cout<<"cost= "<<sum<<endl; 574 const float sum = objectsLeft * lbox.SurfaceArea() + objectsRight * rbox.SurfaceArea(); 575 576 // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 577 // cout<<"cost= "<<sum<<endl; 605 578 606 579 #if DEBUG_COST 607 580 if (nodeId < 100) 608 581 { 609 float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();582 float oldCost = (float)node->mViewCells.size(); 610 583 float newCost = mCt_div_ci + sum/boxArea; 611 float ratio = newCost /oldCost;584 float ratio = newCost / oldCost; 612 585 costStream<<(*ci)->value<<" "<<ratio<<endl; 613 586 } … … 625 598 } 626 599 627 const float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size(); 628 const float newCost = mCt_div_ci + minSum/boxArea; 629 const float ratio = newCost/oldCost; 630 600 const float oldCost = (float)node->mViewCells.size(); 601 const float newCost = mCt_div_ci + minSum / boxArea; 602 const float ratio = newCost / oldCost; 603 604 //if (boxArea == 0) 605 // cout << "error: " << boxArea << endl; 606 if (ratio > 2) 607 { 608 cout << "costratio: " << ratio << " oldcost: " << oldCost << " box area: " << boxArea << " new: " << newCost << endl; 609 cout << "obj left: " <<objectsBack<< " obj right: " << objectsFront << endl; 610 cout << "dummy1: " << dummy1 << " dummy2: " << dummy2 << endl; 611 } 631 612 #if 0 632 613 cout<<"===================="<<endl; … … 634 615 <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl; 635 616 #endif 617 636 618 return ratio; 619 } 620 621 622 int TraversalTree::FindViewCellIntersections(const Vector3 &lStart, 623 const Vector3 &lEnd, 624 const ViewCellContainer &viewCells, 625 ViewCellContainer &hitViewCells, 626 const bool useMailboxing) 627 { 628 int hits = 0; 629 ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 630 631 for (vit = viewCells.begin(); vit != vit_end; ++ vit) 632 { 633 ViewCell *viewCell = *vit; 634 // don't have to mail if each view cell belongs to exactly one leaf 635 if (!useMailboxing || !viewCell->Mailed()) 636 { 637 if (useMailboxing) 638 viewCell->Mail(); 639 640 // hack: assume that we use vsp tree, 641 //P so we can just test intersection with bounding boxes 642 if (viewCell->GetBox().Intersects(lStart, lEnd)); 643 { 644 hitViewCells.push_back(viewCell); 645 ++ hits; 646 } 647 } 648 } 649 650 return hits; 637 651 } 638 652 … … 640 654 int TraversalTree::CastLineSegment(const Vector3 &origin, 641 655 const Vector3 &termination, 642 ViewCellContainer &view cells,656 ViewCellContainer &viewCells, 643 657 const bool useMailboxing) 644 658 { … … 709 723 // compute intersection with all objects in this leaf 710 724 TraversalLeaf *leaf = static_cast<TraversalLeaf *>(node); 711 ViewCell *viewCell = NULL; 712 713 #if TODO 714 if (0) 715 viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell()); 716 else 717 viewCell = leaf->mViewCell; 718 #endif 719 // don't have to mail if each view cell belongs to exactly one leaf 720 if (!useMailboxing || !viewCell->Mailed()) 721 { 722 if (useMailboxing) 723 viewCell->Mail(); 724 725 viewcells.push_back(viewCell); 726 ++ hits; 727 } 728 725 726 hits += FindViewCellIntersections(origin, 727 termination, 728 leaf->mViewCells, 729 viewCells, 730 useMailboxing); 731 729 732 // get the next node from the stack 730 733 if (tStack.empty())
Note: See TracChangeset
for help on using the changeset viewer.
