Changeset 580 for trunk/VUT/GtpVisibilityPreprocessor/src
- Timestamp:
- 02/01/06 19:29:59 (18 years ago)
- Location:
- trunk/VUT/GtpVisibilityPreprocessor/src
- Files:
-
- 14 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
r579 r580 1283 1283 "false"); 1284 1284 1285 1286 RegisterOption("ViewCells.PostProcess.maxCostRatio", 1287 optFloat, 1288 "-view_cells_post_process_max_cost_ratio=", 1289 "0.9"); 1290 1291 1292 RegisterOption("ViewCells.PostProcess.renderCostWeight", 1293 optFloat, 1294 "-view_cells_post_process_render_cost_weight", 1295 "0.5"); 1296 1297 1298 RegisterOption("ViewCells.PostProcess.avgCostMaxDeviation", 1299 optFloat, 1300 "-vsp_bsp_avgcost_max_deviations", 1301 "0.5"); 1302 1303 RegisterOption("ViewCells.PostProcess.maxMergesPerPass", 1304 optInt, 1305 "vsp_bsp_term_max_merges_per_pass=", 1306 "500"); 1307 1308 RegisterOption("ViewCells.PostProcess.minViewCells", 1309 optInt, 1310 "vsp_bsp_term_post_process_min_view_cells=", 1311 "1000"); 1312 1313 RegisterOption("ViewCells.PostProcess.useRaysForMerge", 1314 optBool, 1315 "view_cells_post_process_use_rays_for_merge=", 1316 "false"); 1317 1318 RegisterOption("ViewCells.Visualization.exportMergedViewCells", 1319 optBool, 1320 "view_cells_viz_export_merged_viewcells=", 1321 "false"); 1322 1323 1285 1324 /************************************************************************************/ 1286 1325 /* Render simulation related options */ … … 1834 1873 RegisterOption("VspBspTree.Factor.pvs", optFloat, "-vsp_bsp_factor_pvs=", "1.0"); 1835 1874 1836 RegisterOption("VspBspTree.PostProcess.maxCostRatio", 1875 1876 RegisterOption("VspBspTree.Construction.renderCostWeight", 1837 1877 optFloat, 1838 "-vsp_bsp_post_process_max_cost_ratio=", 1839 "0.9"); 1840 1841 RegisterOption("VspBspTree.PostProcess.minViewCells", 1842 optInt, 1843 "vsp_bsp_term_post_process_min_view_cells=", 1844 "1000"); 1845 1846 RegisterOption("VspBspTree.PostProcess.useRaysForMerge", 1847 optBool, 1848 "vsp_bsp_term_post_process_use_rays_for_merge=", 1849 "false"); 1878 "-vsp_bsp_post_process_render_cost_weight", 1879 "0.5"); 1880 1850 1881 1851 1882 RegisterOption("VspBspTree.Construction.randomize", … … 1865 1896 "8.0"); 1866 1897 1867 RegisterOption("VspBspTree.Visualization.exportMergedViewCells", 1868 optBool, 1869 "vsp_bsp_viz_export_merged_viewcells=", 1870 "false"); 1871 1872 RegisterOption("VspBspTree.PostProcess.exportMergeStats", 1873 optBool, 1874 "vsp_bsp_viz_export_merge_stats=", 1875 "false"); 1898 1899 1876 1900 1877 1901 ////////////////////////////////////////////////////////////////////////////////// -
trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp
r556 r580 888 888 leaf->mViewCell = viewCell; 889 889 // push back pointer to this leaf 890 viewCell->mLea ves.push_back(leaf);890 viewCell->mLeaf = leaf; 891 891 vc.push_back(viewCell); 892 892 } else { -
trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp
r574 r580 94 94 ViewCell *vc = *it; 95 95 96 const bool valid = !vc->GetValid();96 const bool valid = vc->GetValid(); 97 97 98 98 -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp
r564 r580 4 4 #include "MeshKdTree.h" 5 5 #include "Triangle3.h" 6 #include "common.h" 7 #include "Environment.h" 8 #include "ViewCellsManager.h" 9 #include "Exporter.h" 10 6 11 #include <time.h> 7 12 #include <iomanip> 13 #include <stack> 14 15 16 17 template <typename T> class myless 18 { 19 public: 20 21 //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const 22 bool operator() (T v1, T v2) const 23 { 24 return (v1->GetTimeStamp() > v2->GetTimeStamp()); 25 } 26 }; 27 28 29 typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > TraversalQueue; 30 31 int ViewCell::sMailId = 21843194198; 32 int ViewCell::sReservedMailboxes = 1; 33 34 //int upperPvsLimit = 120; 35 //int lowerPvsLimit = 5; 36 37 float MergeCandidate::sRenderCostWeight = 0; 38 39 40 // pvs penalty can be different from pvs size 41 inline float EvalPvsPenalty(const int pvs, 42 const int lower, 43 const int upper) 44 { 45 // clamp to minmax values 46 if (pvs < lower) 47 return (float)lower; 48 if (pvs > upper) 49 return (float)upper; 50 51 return (float)pvs; 52 } 53 54 55 int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2) 56 { 57 int pvs = pvs1.GetSize(); 58 59 // compute new pvs size 60 ObjectPvsMap::const_iterator it, it_end = pvs1.mEntries.end(); 61 62 Intersectable::NewMail(); 63 64 for (it = pvs1.mEntries.begin(); it != it_end; ++ it) 65 { 66 (*it).first->Mail(); 67 } 68 69 it_end = pvs2.mEntries.end(); 70 71 for (it = pvs2.mEntries.begin(); it != it_end; ++ it) 72 { 73 Intersectable *obj = (*it).first; 74 if (!obj->Mailed()) 75 ++ pvs; 76 } 77 78 return pvs; 79 } 80 8 81 9 82 ViewCell::ViewCell(): … … 12 85 mArea(-1), 13 86 mVolume(-1), 14 mValid(true) 87 mValid(true), 88 mParent(NULL), 89 mTimeStamp(0) 15 90 { 16 91 } … … 21 96 mArea(-1), 22 97 mVolume(-1), 23 mValid(true) 98 mValid(true), 99 mParent(NULL), 100 mTimeStamp(0) 24 101 { 25 102 } … … 43 120 44 121 45 void ViewCell::AddPassingRay(const Ray &ray, const int contributions)46 {47 mPassingRays.AddRay(ray, contributions);48 }49 50 51 122 float ViewCell::GetVolume() const 52 123 { … … 113 184 114 185 186 /*bool ViewCell::IsLeaf() const 187 { 188 return true; 189 }*/ 190 191 192 void ViewCell::SetParent(ViewCellInterior *parent) 193 { 194 mParent = parent; 195 } 196 197 198 bool ViewCell::IsRoot() const 199 { 200 return !mParent; 201 } 202 203 204 ViewCellInterior *ViewCell::GetParent() const 205 { 206 return mParent; 207 } 208 209 210 void ViewCell::SetTimeStamp(const int timeStamp) 211 { 212 mTimeStamp = timeStamp; 213 } 214 215 216 int ViewCell::GetTimeStamp() const 217 { 218 return mTimeStamp; 219 } 220 221 222 /************************************************************************/ 223 /* class ViewCellInterior implementation */ 224 /************************************************************************/ 225 226 227 ViewCellInterior::ViewCellInterior() 228 { 229 } 230 231 232 ViewCellInterior::~ViewCellInterior() 233 { 234 ViewCellContainer::const_iterator it, it_end = mChildren.end(); 235 236 for (it = mChildren.begin(); it != it_end; ++ it) 237 delete (*it); 238 } 239 240 241 ViewCellInterior::ViewCellInterior(Mesh *mesh): 242 ViewCell(mesh) 243 { 244 } 245 246 247 bool ViewCellInterior::IsLeaf() const 248 { 249 return false; 250 } 251 252 253 void ViewCellInterior::SetupChildLink(ViewCell *l) 254 { 255 mChildren.push_back(l); 256 l->mParent = this; 257 } 258 259 260 115 261 /************************************************************************/ 116 262 /* class ViewCellsStatistics implementation */ 117 263 /************************************************************************/ 118 264 265 266 267 119 268 void ViewCellsStatistics::Print(ostream &app) const 120 269 { … … 145 294 app << "========== End of View Cells Statistics ==========\n"; 146 295 } 296 297 298 /*************************************************************************/ 299 /* class ViewCellsTree implementation */ 300 /*************************************************************************/ 301 302 303 ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm): 304 mRoot(NULL), 305 mUseAreaForPvs(false), 306 mViewCellsManager(vcm) 307 { 308 environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells); 309 310 //-- merge options 311 environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight); 312 environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells); 313 environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio); 314 315 MergeCandidate::sRenderCostWeight = mRenderCostWeight; 316 317 mStats.open("mergeStats.log"); 318 } 319 320 321 int ViewCellsTree::GetSize(ViewCell *vc) const 322 { 323 int vcSize = 0; 324 325 stack<ViewCell *> tstack; 326 327 tstack.push(vc); 328 329 while (!tstack.empty()) 330 { 331 ViewCell *vc = tstack.top(); 332 tstack.pop(); 333 334 if (vc->IsLeaf()) 335 { 336 ++ vcSize; 337 } 338 else 339 { 340 ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc); 341 ViewCellContainer::const_iterator it, it_end = interior->mChildren.end(); 342 for (it = interior->mChildren.begin(); it != it_end; ++ it) 343 tstack.push(*it); 344 345 } 346 } 347 348 return vcSize; 349 } 350 351 352 void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const 353 { 354 stack<ViewCell *> tstack; 355 356 tstack.push(vc); 357 358 while (!tstack.empty()) 359 { 360 ViewCell *vc = tstack.top(); 361 tstack.pop(); 362 363 if (vc->IsLeaf()) 364 { 365 leaves.push_back(vc); 366 } 367 else 368 { 369 ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc); 370 ViewCellContainer::const_iterator it, it_end = interior->mChildren.end(); 371 for (it = interior->mChildren.begin(); it != it_end; ++ it) 372 tstack.push(*it); 373 374 } 375 } 376 } 377 378 379 ViewCellsTree::~ViewCellsTree() 380 { 381 DEL_PTR(mRoot); 382 } 383 384 385 int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays, 386 const ObjectContainer &objects) 387 { 388 // number of view cells equals the number of leaves 389 // (without the invalid ones ) 390 //mNumViewCells = mBspStats.Leaves();//- mBspStats.invalidLeaves; 391 mNumViewCells = (int)mViewCellsManager->GetViewCells().size(); 392 393 float variance = 0; 394 int totalPvs = 0; 395 float totalCost = 0; 396 397 //-- compute statistics values of initial view cells 398 mViewCellsManager->EvaluateRenderStatistics(totalCost, 399 mExpectedCost, 400 mDeviation, 401 variance, 402 totalPvs, 403 mAvgRenderCost); 404 405 406 //-- fill merge queue 407 vector<MergeCandidate> candidates; 408 409 mViewCellsManager->CollectMergeCandidates(rays, candidates); 410 while(!candidates.empty()) 411 { 412 MergeCandidate mc = candidates.back(); 413 candidates.pop_back(); 414 EvalMergeCost(mc); 415 mMergeQueue.push(mc); 416 } 417 418 Debug << "************************* merge ***********************************" << endl; 419 Debug << "deviation: " << mDeviation << endl; 420 Debug << "avg render cost: " << mAvgRenderCost << endl; 421 Debug << "expected cost: " <<mExpectedCost << endl; 422 423 424 ViewCellsManager::PvsStatistics pvsStats; 425 mViewCellsManager->GetPvsStatistics(pvsStats); 426 427 static float expectedValue = pvsStats.avgPvs; 428 429 // the current view cells are kept in this container 430 // we start with the current view cells from the 431 // view cell manager. They will change with 432 // subsequent merges 433 ViewCellContainer &viewCells = mViewCellsManager->GetViewCells(); 434 435 436 ViewCell::NewMail(); 437 438 MergeStatistics mergeStats; 439 mergeStats.Start(); 440 441 long startTime = GetTime(); 442 443 mergeStats.collectTime = TimeDiff(startTime, GetTime()); 444 mergeStats.candidates = (int)mMergeQueue.size(); 445 startTime = GetTime(); 446 447 // frequency stats are updated 448 const int statsOut = 100; 449 450 // passes are needed for statistics, because we don't want to record 451 // every merge 452 int pass = 0; 453 int mergedPerPass = 0; 454 float realExpectedCost = mExpectedCost; 455 float realAvgRenderCost = mAvgRenderCost; 456 int realNumViewCells = mNumViewCells; 457 458 // maximal ratio of old expected render cost to expected render 459 // when the the render queue has to be reset. 460 float avgCostMaxDeviation; 461 int maxMergesPerPass; 462 int numActiveViewCells = 0; 463 464 environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass); 465 environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation); 466 467 cout << "actual merge starts now ... " << endl; 468 469 //ResetMergeQueue(); 470 471 //-- use priority queue to merge leaf pairs 472 473 while (!mMergeQueue.empty() && (realNumViewCells > mMergeMinViewCells) && 474 (mMergeQueue.top().GetRenderCost() < mMergeMaxCostRatio * totalCost)) 475 { 476 //-- reset merge queue if the ratio of current expected cost / real expected cost 477 // too small or after a given number of merges 478 if(0) 479 if ((mergedPerPass > maxMergesPerPass) || 480 (avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost)) 481 { 482 Debug << "************ reset queue *****************\n" 483 << "ratios: " << avgCostMaxDeviation 484 << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost 485 << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl; 486 487 Debug << "Values before reset: " 488 << " erc: " << mExpectedCost 489 << " avgrc: " << mAvgRenderCost 490 << " dev: " << mDeviation << endl; 491 492 // adjust render cost 493 ++ pass; 494 495 mergedPerPass = 0; 496 mExpectedCost = realExpectedCost; 497 mAvgRenderCost = realAvgRenderCost; 498 mNumViewCells = realNumViewCells; 499 500 const int numActiveViewCells = UpdateMergedViewCells(viewCells); 501 502 ResetMergeQueue(); 503 504 505 Debug << "Values after reset: " 506 << " erc: " << mExpectedCost 507 << " avg: " << mAvgRenderCost 508 << " dev: " << mDeviation << endl; 509 510 if (mExportMergedViewCells) 511 { 512 ExportMergedViewCells(viewCells, objects, numActiveViewCells); 513 } 514 } 515 516 #ifdef _DEBUG 517 Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << 518 << " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost << 519 << " max ratio: " << mMergeMaxCostRatio << endl 520 << " expected value: " << realExpectedCost << endl; 521 #endif 522 523 524 MergeCandidate mc = mMergeQueue.top(); 525 mMergeQueue.pop(); 526 527 // both view cells equal! 528 if (mc.mLeftViewCell == mc.mRightViewCell) 529 continue; 530 531 if (mc.IsValid()) 532 { 533 ViewCell::NewMail(); 534 535 -- realNumViewCells; 536 ++ mergeStats.merged; 537 ++ mergedPerPass; 538 539 540 //-- update statistical values 541 542 // total render cost and deviation has changed 543 // real expected cost will be larger than expected cost used for the 544 // cost heuristics, but cannot recompute costs on each increase of the 545 // expected cost 546 547 totalCost += mc.GetRenderCost(); 548 mDeviation += mc.GetDeviationIncr(); 549 550 realExpectedCost = totalCost / (float)realNumViewCells; 551 552 const float currentMergeCost = mc.GetMergeCost(); 553 554 // merge the view cells of leaf1 and leaf2 555 int pvsDiff; 556 ViewCellInterior *mergedVc = 557 MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff); 558 559 totalPvs += pvsDiff; 560 // set timestamp 561 mergedVc->SetTimeStamp(mergeStats.merged); 562 563 realAvgRenderCost = (float)totalPvs / (float)realNumViewCells; 564 #if VC_HISTORY 565 if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell)) 566 ++ mergeStats.siblings; 567 #endif 568 if (((mergeStats.merged % statsOut) == 0) || 569 (realNumViewCells == mMergeMinViewCells)) 570 { 571 cout << "merged " << mergeStats.merged << " view cells" << endl; 572 573 mStats 574 << "#Pass\n" << pass << endl 575 << "#Merged\n" << mergeStats.merged << endl 576 << "#Viewcells\n" << realNumViewCells << endl 577 << "#CurrentCost\n" << currentMergeCost << endl 578 << "#RelativeCost\n" << currentMergeCost / mOverallCost << endl 579 << "#CurrentPvs\n" << mc.GetLeftViewCell()->GetPvs().GetSize() << endl 580 << "#MergedSiblings\n" << mergeStats.siblings << endl 581 << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl 582 << "#UsedExpectedCost\n" << mExpectedCost << endl 583 << "#RealExpectedCost\n" << realExpectedCost << endl 584 << "#RealAvgRenderCost\n" << realAvgRenderCost << endl 585 << "#AvgRenderCost\n" << mAvgRenderCost << endl 586 << "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl 587 << "#Deviation\n" << mDeviation / (float)realNumViewCells << endl 588 << "#TotalDeviation\n" << mDeviation<< endl; 589 } 590 } 591 else 592 { 593 // merge candidate not valid, because one of the leaves was already 594 // merged with another one => validate and reinsert into queue 595 SetMergeCandidateValid(mc); 596 mMergeQueue.push(mc); 597 } 598 } 599 600 // adjust stats and reset queue one final time 601 mExpectedCost = realExpectedCost; 602 mAvgRenderCost = realAvgRenderCost; 603 mNumViewCells = realNumViewCells; 604 605 UpdateMergedViewCells(viewCells); 606 ResetMergeQueue(); 607 608 609 // create a root node if the merge was not done till root level, 610 // else take the single node as new root 611 if ((int)viewCells.size() > 1) 612 { 613 ViewCellInterior *root = new ViewCellInterior(); 614 615 ViewCellContainer::const_iterator it, it_end = viewCells.end(); 616 for (it = viewCells.begin(); it != it_end; ++ it) 617 root->SetupChildLink(*it); 618 619 mRoot = root; 620 } 621 else if ((int)viewCells.size() == 1) 622 { 623 mRoot = viewCells[0]; 624 } 625 626 mergeStats.expectedRenderCost = realExpectedCost; 627 mergeStats.deviation = mDeviation; 628 629 // we want to optimize this heuristics 630 mergeStats.heuristics = 631 mDeviation * (1.0f - mRenderCostWeight) + 632 mExpectedCost * mRenderCostWeight; 633 634 mergeStats.mergeTime = TimeDiff(startTime, GetTime()); 635 mergeStats.Stop(); 636 637 Debug << mergeStats << endl << endl; 638 639 640 //TODO: should return sample contributions? 641 return mergeStats.merged; 642 } 643 644 645 void ViewCellsTree::ResetMergeQueue() 646 { 647 cout << "reset merge queue ... "; 648 649 vector<MergeCandidate> buf; 650 buf.reserve(mMergeQueue.size()); 651 652 653 // store merge candidates in intermediate buffer 654 while (!mMergeQueue.empty()) 655 { 656 MergeCandidate mc = mMergeQueue.top(); 657 mMergeQueue.pop(); 658 659 // recalculate cost 660 SetMergeCandidateValid(mc); 661 buf.push_back(mc); 662 } 663 664 vector<MergeCandidate>::const_iterator bit, bit_end = buf.end(); 665 666 // reinsert back into queue 667 for (bit = buf.begin(); bit != bit_end; ++ bit) 668 { 669 mMergeQueue.push(*bit); 670 } 671 672 cout << "finished" << endl; 673 } 674 675 676 int ViewCellsTree::UpdateMergedViewCells(ViewCellContainer &viewCells) 677 { 678 int numActiveViewCells = 0; 679 680 // find all already merged view cells and remove them from view cells 681 int i = 0; 682 683 while (1) 684 { 685 while (!viewCells.empty() && (!viewCells.back()->GetParent())) 686 { 687 viewCells.pop_back(); 688 } 689 690 // all merged view cells have been found 691 if (i >= viewCells.size()) 692 break; 693 694 // already merged view cell, put it to end of vector 695 if (!viewCells[i]->IsRoot()) 696 swap(viewCells[i], viewCells.back()); 697 698 ++ i; 699 } 700 701 // add new view cells to container only if they don't have been 702 // merged in the mean time 703 while (!mActiveViewCells.empty()) 704 { 705 if (!mActiveViewCells.back()->GetParent()) 706 { 707 viewCells.push_back(mActiveViewCells.back()); 708 ++ numActiveViewCells; 709 } 710 711 mActiveViewCells.pop_back(); 712 } 713 714 // update standard deviation 715 ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 716 717 mDeviation = 0; 718 719 for (vit = viewCells.begin(); vit != vit_end; ++ vit) 720 { 721 int lower = mViewCellsManager->GetMinPvsSize(); 722 int upper = mViewCellsManager->GetMaxPvsSize(); 723 float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper); 724 725 mDeviation += fabs(mAvgRenderCost - penalty); 726 } 727 728 mDeviation /= (float)viewCells.size(); 729 730 // clear the view cells which were merged 731 mInactiveViewCells.clear(); 732 // remove the new view cells 733 mActiveViewCells.clear(); 734 735 return numActiveViewCells; 736 } 737 738 739 void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells, 740 const ObjectContainer &objects, 741 const int numActiveViewCells) 742 { 743 744 745 char s[64]; 746 747 sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size()); 748 Exporter *exporter = Exporter::GetExporter(s); 749 750 if (exporter) 751 { 752 cout << "exporting " << (int)viewCells.size() << " merged view cells ... "; 753 exporter->ExportGeometry(objects); 754 //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl; 755 ViewCellContainer::const_iterator it, it_end = viewCells.end(); 756 757 int i = 0; 758 for (it = viewCells.begin(); it != it_end; ++ it) 759 { 760 Material m; 761 // assign special material to new view cells 762 // new view cells are on the back of container 763 if (i ++ >= (viewCells.size() - numActiveViewCells)) 764 { 765 //m = RandomMaterial(); 766 m.mDiffuseColor.r = RandomValue(0.5f, 1.0f); 767 m.mDiffuseColor.g = RandomValue(0.5f, 1.0f); 768 m.mDiffuseColor.b = RandomValue(0.5f, 1.0f); 769 } 770 else 771 { 772 float col = RandomValue(0.1f, 0.4f); 773 m.mDiffuseColor.r = col; 774 m.mDiffuseColor.g = col; 775 m.mDiffuseColor.b = col; 776 } 777 778 exporter->SetForcedMaterial(m); 779 mViewCellsManager->ExportViewCellGeometry(exporter, *it); 780 } 781 delete exporter; 782 cout << "finished" << endl; 783 } 784 } 785 786 787 // TODO: should be done in view cells manager 788 ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const 789 { 790 ViewCellInterior *vc = mViewCellsManager->MergeViewCells(*l, *r); 791 792 // if merge was unsuccessful 793 if (!vc) return NULL; 794 795 // set new size of view cell 796 if (mUseAreaForPvs) 797 vc->SetArea(l->GetArea() + l->GetArea()); 798 else 799 vc->SetVolume(r->GetVolume() + r->GetVolume()); 800 801 // important so other merge candidates sharing this view cell 802 // are notified that the merge cost must be updated!! 803 vc->Mail(); 804 805 const int pvs1 = l->GetPvs().GetSize(); 806 const int pvs2 = r->GetPvs().GetSize(); 807 808 809 //-- clean up old view cells 810 if (0 && !mExportMergedViewCells) 811 { 812 DEL_PTR(l); 813 DEL_PTR(r); 814 } 815 else 816 { 817 mInactiveViewCells.push_back(l); 818 mInactiveViewCells.push_back(r); 819 820 mActiveViewCells.push_back(vc); 821 } 822 823 pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2; 824 825 return vc; 826 } 827 828 829 830 831 int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects) 832 { 833 Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl; 834 835 // Use priority queue of remaining leaf pairs 836 // The candidates either share the same view cells or 837 // are border leaves which share a boundary. 838 // We test if they can be shuffled, i.e., 839 // either one leaf is made part of one view cell or the other 840 // leaf is made part of the other view cell. It is tested if the 841 // remaining view cells are "better" than the old ones. 842 // 843 // repeat the merging test numPasses times. For example, it could be 844 // that a shuffle only makes sense if another pair was shuffled before. 845 // Therefore we keep two queues and shift the merge candidates between 846 // those two queues until numPasses is reached 847 848 queue<MergeCandidate> queue1; 849 queue<MergeCandidate> queue2; 850 851 queue<MergeCandidate> *shuffleQueue = &queue1; 852 queue<MergeCandidate> *backQueue = &queue2; 853 854 while (!mMergeQueue.empty()) 855 { 856 MergeCandidate mc = mMergeQueue.top(); 857 shuffleQueue->push(mc); 858 mMergeQueue.pop(); 859 } 860 861 const int numPasses = 5; 862 int pass = 0; 863 int passShuffled = 0; 864 int shuffled = 0; 865 int shuffledViewCells = 0; 866 867 ViewCell::NewMail(); 868 869 do 870 { 871 passShuffled = 0; 872 while (!shuffleQueue->empty()) 873 { 874 MergeCandidate mc = shuffleQueue->front(); 875 shuffleQueue->pop(); 876 877 // both view cells equal or already shuffled 878 if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) || 879 (GetSize(mc.GetLeftViewCell()) == 1) || 880 (GetSize(mc.GetRightViewCell()) == 1)) 881 { 882 continue; 883 } 884 885 // candidate for shuffling 886 const bool wasShuffled = 887 ShuffleLeaves(mc.GetLeftViewCell(), mc.GetRightViewCell()); 888 889 // shuffled or put into other queue for further refine 890 if (wasShuffled) 891 { 892 ++ passShuffled; 893 894 if (!mc.GetLeftViewCell()->Mailed()) 895 { 896 mc.GetLeftViewCell()->Mail(); 897 ++ shuffledViewCells; 898 } 899 if (!mc.GetRightViewCell()->Mailed()) 900 { 901 mc.GetRightViewCell()->Mail(); 902 ++ shuffledViewCells; 903 } 904 } 905 else 906 { 907 backQueue->push(mc); 908 } 909 } 910 911 // now the back queue is the current shuffle queue 912 swap(shuffleQueue, backQueue); 913 shuffled += passShuffled; 914 Debug << "shuffled in pass: " << passShuffled << endl; 915 } 916 while (((++ pass) < numPasses) && passShuffled); 917 918 while (!shuffleQueue->empty()) 919 { 920 shuffleQueue->pop(); 921 } 922 923 return shuffledViewCells; 924 } 925 926 927 928 929 inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2) 930 { 931 return pvs1.AddPvs(pvs2); 932 } 933 934 935 // recomputes pvs size minus pvs of leaf l 936 #if 0 937 inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2) 938 { 939 ObjectPvs pvs; 940 vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end(); 941 for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it) 942 if (*it != l) 943 pvs.AddPvs(*(*it)->mPvs); 944 return pvs.GetSize(); 945 } 946 #endif 947 948 949 // computes pvs1 minus pvs2 950 inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2) 951 { 952 return pvs1.SubtractPvs(pvs2); 953 } 954 955 956 float ViewCellsTree::EvalShuffleCost(ViewCell *leaf, 957 ViewCell *vc1, 958 ViewCell *vc2) const 959 { 960 //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs); 961 const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs()); 962 const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs()); 963 964 const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 965 const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 966 967 const float pvsPenalty1 = 968 EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit); 969 970 const float pvsPenalty2 = 971 EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit); 972 973 974 // don't shuffle leaves with pvs > max 975 if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize())) 976 { 977 return 1e20f; 978 } 979 980 float p1, p2; 981 982 if (mUseAreaForPvs) 983 { 984 p1 = vc1->GetArea() - leaf->GetArea(); 985 p2 = vc2->GetArea() + leaf->GetArea(); 986 } 987 else 988 { 989 p1 = vc1->GetVolume() - leaf->GetVolume(); 990 p2 = vc2->GetVolume() + leaf->GetVolume(); 991 } 992 993 const float renderCost1 = pvsPenalty1 * p1; 994 const float renderCost2 = pvsPenalty2 * p2; 995 996 float dev1, dev2; 997 998 if (1) 999 { 1000 dev1 = fabs(mAvgRenderCost - pvsPenalty1); 1001 dev2 = fabs(mAvgRenderCost - pvsPenalty2); 1002 } 1003 else 1004 { 1005 dev1 = fabs(mExpectedCost - renderCost1); 1006 dev2 = fabs(mExpectedCost - renderCost2); 1007 } 1008 1009 return mRenderCostWeight * (renderCost1 + renderCost2) + 1010 (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumViewCells; 1011 } 1012 1013 1014 void ViewCellsTree::ShuffleLeaf(ViewCell *leaf, 1015 ViewCell *vc1, 1016 ViewCell *vc2) const 1017 { 1018 // compute new pvs and area 1019 vc1->GetPvs().SubtractPvs(leaf->GetPvs()); 1020 vc2->GetPvs().AddPvs(leaf->GetPvs()); 1021 1022 if (mUseAreaForPvs) 1023 { 1024 vc1->SetArea(vc1->GetArea() - leaf->GetArea()); 1025 vc2->SetArea(vc2->GetArea() + leaf->GetArea()); 1026 } 1027 else 1028 { 1029 vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume()); 1030 vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume()); 1031 } 1032 1033 // TODO 1034 #if VC_HISTORY 1035 /// add to second view cell 1036 vc2->mLeaves.push_back(leaf); 1037 1038 // erase leaf from old view cell 1039 vector<BspLeaf *>::iterator it = vc1->mLeaves.begin(); 1040 1041 for (; *it != leaf; ++ it); 1042 vc1->mLeaves.erase(it); 1043 1044 /*vc1->GetPvs().mEntries.clear(); 1045 for (; it != vc1->mLeaves.end(); ++ it) 1046 { 1047 if (*it == leaf) 1048 vc1->mLeaves.erase(it); 1049 else 1050 vc1->GetPvs().AddPvs(*(*it)->mPvs); 1051 }*/ 1052 1053 leaf->SetViewCell(vc2); // finally change view cell 1054 #endif 1055 } 1056 1057 1058 bool ViewCellsTree::ShuffleLeaves(ViewCell *l, ViewCell *r) const 1059 { 1060 float cost1, cost2; 1061 1062 //-- first test if shuffling would decrease cost 1063 cost1 = GetCostHeuristics(l); 1064 cost2 = GetCostHeuristics(r); 1065 1066 const float oldCost = cost1 + cost2; 1067 1068 float shuffledCost1 = Limits::Infinity; 1069 float shuffledCost2 = Limits::Infinity; 1070 1071 // the view cell should not be empty after the shuffle 1072 #if VC_HISTORY 1073 shuffledCost1 = EvalShuffleCost(l, vc1, vc2); 1074 /shuffledCost2 = EvalShuffleCost(r, vc2, vc1); 1075 1076 // if cost of shuffle is less than old cost => shuffle 1077 if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2)) 1078 return false; 1079 1080 1081 if (shuffledCost1 < shuffledCost2) 1082 { 1083 ShuffleLeaf(leaf1, vc1, vc2); 1084 leaf1->Mail(); 1085 } 1086 else 1087 { 1088 ShuffleLeaf(leaf2, vc2, vc1); 1089 leaf2->Mail(); 1090 } 1091 #endif 1092 return true; 1093 } 1094 1095 1096 float ViewCellsTree::GetVariance(ViewCell *vc) const 1097 { 1098 const int upper = mViewCellsManager->GetMaxPvsSize(); 1099 const int lower = mViewCellsManager->GetMinPvsSize(); 1100 1101 if (1) 1102 { 1103 const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper); 1104 return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumViewCells; 1105 } 1106 1107 const float leafCost = GetRenderCost(vc); 1108 return (mExpectedCost - leafCost) * (mExpectedCost - leafCost); 1109 } 1110 1111 1112 float ViewCellsTree::GetDeviation(ViewCell *vc) const 1113 { 1114 const int upper = mViewCellsManager->GetMaxPvsSize(); 1115 const int lower = mViewCellsManager->GetMinPvsSize(); 1116 1117 if (1) 1118 { 1119 const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper); 1120 return fabs(mAvgRenderCost - penalty) / (float)mNumViewCells; 1121 } 1122 1123 const float renderCost = GetRenderCost(vc); 1124 return fabs(mExpectedCost - renderCost); 1125 } 1126 1127 1128 1129 float ViewCellsTree::GetRenderCost(ViewCell *vc) const 1130 { 1131 if (mUseAreaForPvs) 1132 return vc->GetPvs().GetSize() * vc->GetArea(); 1133 1134 return vc->GetPvs().GetSize() * vc->GetVolume(); 1135 } 1136 1137 1138 float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const 1139 { 1140 return GetRenderCost(vc) * mRenderCostWeight + 1141 GetDeviation(vc) * (1.0f - mRenderCostWeight); 1142 } 1143 1144 1145 void ViewCellsTree::SetMergeCandidateValid(MergeCandidate &mc) const 1146 { 1147 while (mc.mLeftViewCell->mParent) 1148 { 1149 mc.mLeftViewCell = mc.mLeftViewCell->mParent; 1150 } 1151 1152 while (mc.mRightViewCell->mParent) 1153 { 1154 mc.mRightViewCell = mc.mRightViewCell->mParent; 1155 } 1156 1157 EvalMergeCost(mc); 1158 } 1159 1160 1161 void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const 1162 { 1163 //-- compute pvs difference 1164 const int newPvs = 1165 ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(), 1166 mc.mRightViewCell->GetPvs()); 1167 1168 const float newPenalty = 1169 EvalPvsPenalty(newPvs, 1170 mViewCellsManager->GetMinPvsSize(), 1171 mViewCellsManager->GetMaxPvsSize()); 1172 1173 ViewCell *vc1 = mc.mLeftViewCell; 1174 ViewCell *vc2 = mc.mRightViewCell; 1175 1176 //-- compute ratio of old cost 1177 // (i.e., added size of left and right view cell times pvs size) 1178 // to new rendering cost (i.e, size of merged view cell times pvs size) 1179 const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2); 1180 1181 const float newCost = mUseAreaForPvs ? 1182 (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) : 1183 (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume()); 1184 1185 1186 // strong penalty if pvs size too large 1187 if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize())) 1188 { 1189 mc.mRenderCost = 1e20f; 1190 } 1191 else 1192 { 1193 mc.mRenderCost = (newCost - oldCost) / 1194 mViewCellsManager->GetViewSpaceBox().GetVolume(); 1195 } 1196 1197 1198 //-- merge cost also takes deviation into account 1199 float newDev, oldDev; 1200 1201 if (1) 1202 newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumViewCells; 1203 else 1204 newDev = fabs(mExpectedCost - newCost) / (float)mNumViewCells; 1205 1206 oldDev = GetDeviation(vc1) + GetDeviation(vc2); 1207 1208 // compute deviation increase 1209 mc.mDeviationIncr = newDev - oldDev; 1210 1211 //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl; 1212 //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl; 1213 } 1214 1215 1216 void ViewCellsTree::CompressViewCellsPvs() 1217 { 1218 stack<ViewCell *> tstack; 1219 1220 1221 } 1222 1223 1224 void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells) 1225 { 1226 TraversalQueue tqueue; 1227 1228 while (!tqueue.empty()) 1229 { 1230 ViewCell *vc = tqueue.top(); 1231 1232 tqueue.pop(); 1233 } 1234 } 1235 1236 1237 /**************************************************************************/ 1238 /* MergeCandidate implementation */ 1239 /**************************************************************************/ 1240 1241 1242 MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r): 1243 mRenderCost(0), 1244 mDeviationIncr(0), 1245 mLeftViewCell(l), 1246 mRightViewCell(r) 1247 { 1248 //EvalMergeCost(); 1249 } 1250 1251 1252 void MergeCandidate::SetRightViewCell(ViewCell *v) 1253 { 1254 mRightViewCell = v; 1255 } 1256 1257 1258 void MergeCandidate::SetLeftViewCell(ViewCell *v) 1259 { 1260 mLeftViewCell = v; 1261 } 1262 1263 1264 ViewCell *MergeCandidate::GetRightViewCell() const 1265 { 1266 return mRightViewCell; 1267 } 1268 1269 1270 ViewCell *MergeCandidate::GetLeftViewCell() const 1271 { 1272 return mLeftViewCell; 1273 } 1274 1275 1276 ViewCell *MergeCandidate::GetInitialRightViewCell() const 1277 { 1278 return mInitialRightViewCell; 1279 } 1280 1281 1282 ViewCell *MergeCandidate::GetInitialLeftViewCell() const 1283 { 1284 return mInitialLeftViewCell; 1285 } 1286 1287 1288 bool MergeCandidate::IsValid() const 1289 { 1290 return !(mLeftViewCell->mParent && mRightViewCell->mParent); 1291 } 1292 1293 1294 float MergeCandidate::GetRenderCost() const 1295 { 1296 return mRenderCost; 1297 } 1298 1299 1300 float MergeCandidate::GetDeviationIncr() const 1301 { 1302 return mDeviationIncr; 1303 } 1304 1305 1306 float MergeCandidate::GetMergeCost() const 1307 { 1308 return mRenderCost * sRenderCostWeight + 1309 mDeviationIncr * (1.0f - sRenderCostWeight); 1310 } 1311 1312 1313 /************************************************************************/ 1314 /* MergeStatistics implementation */ 1315 /************************************************************************/ 1316 1317 1318 void MergeStatistics::Print(ostream &app) const 1319 { 1320 app << "===== Merge statistics ===============\n"; 1321 1322 app << setprecision(4); 1323 1324 app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n"; 1325 1326 app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n"; 1327 1328 app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n"; 1329 1330 app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n"; 1331 1332 app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n"; 1333 1334 app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n"; 1335 1336 app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n"; 1337 1338 app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n"; 1339 1340 app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n"; 1341 1342 app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n"; 1343 1344 app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n"; 1345 1346 app << "#DEVIATION ( deviation )\n" << deviation << "\n"; 1347 1348 app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n"; 1349 1350 1351 app << "===== END OF BspTree statistics ==========\n"; 1352 } -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h
r569 r580 16 16 class VspKdLeaf; 17 17 class KdLeaf; 18 class ViewCellInterior; 19 class MergeCandidate; 20 class ViewCellsManager; 18 21 19 22 /** Statistics for a view cell partition. … … 78 81 }; 79 82 83 80 84 /** 81 85 View cell with an optional mesh representation 82 86 */ 87 88 83 89 class ViewCell: public MeshInstance 84 90 { … … 93 99 */ 94 100 virtual ~ViewCell() {} 101 95 102 /** Returns Pvs. 96 103 */ … … 100 107 int Type() const; 101 108 109 void SetParent(ViewCellInterior *parent); 110 102 111 /** Adds a passing ray to the passing ray container. 103 112 */ … … 124 133 virtual void UpdateViewCellsStats(ViewCellsStatistics &vcStat); 125 134 126 /// Ray set description of the rays passing through this node. 127 PassingRaySet mPassingRays; 135 /** if this view cell is the root of a view cell hierarchy 136 */ 137 bool IsRoot() const; 138 139 /** Returns parent view cell. 140 */ 141 ViewCellInterior *GetParent() const; 142 143 144 /** Sets the mesh for this view cell. 145 */ 146 void SetMesh(Mesh *mesh); 147 148 void SetValid(const bool valid); 149 bool GetValid() const; 150 151 152 153 154 /// parent view cell in the view cell hierarchy 155 ViewCellInterior *mParent; 128 156 129 157 /// Rays piercing this view cell. 130 158 RayContainer mPiercingRays; 131 159 132 /** Sets the mesh for this view cell. 133 */ 134 void SetMesh(Mesh *mesh); 135 136 void SetValid(const bool valid); 137 bool GetValid() const; 160 161 /** if this is a view cell correspending to a leaf in a hierarchy. 162 */ 163 virtual bool IsLeaf() const = 0; 138 164 139 165 static bool SmallerPvs(const ViewCell *a, … … 142 168 } 143 169 170 171 void SetTimeStamp(const int timeStamp); 172 int GetTimeStamp() const; 173 static void NewMail(const int reserve = 1) { 174 sMailId += sReservedMailboxes; 175 sReservedMailboxes = reserve; 176 } 177 void Mail() { mMailbox = sMailId; } 178 bool Mailed() const { return mMailbox == sMailId; } 179 180 void Mail(const int mailbox) { mMailbox = sMailId + mailbox; } 181 bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; } 182 183 int IncMail() { return ++mMailbox - sMailId; } 184 185 186 187 // last mail id -> warning not thread safe! 188 // both mailId and mailbox should be unique for each thread!!! 189 static int sMailId; 190 static int sReservedMailboxes; 191 192 144 193 protected: 145 194 … … 150 199 float mArea; 151 200 201 int mTimeStamp; 152 202 153 203 bool mValid; 204 }; 205 206 207 class ViewCellInterior: public ViewCell 208 { 209 public: 210 ViewCellInterior(); 211 ~ViewCellInterior(); 212 213 ViewCellInterior(Mesh *mesh); 214 215 216 /** Sets pointer from parent to child and vice versa. 217 */ 218 void SetupChildLink(ViewCell *l); 219 bool IsLeaf() const; 220 221 ViewCellContainer mChildren; 222 154 223 }; 155 224 … … 158 227 */ 159 228 template<typename T> 160 class HierarchyViewCell: public ViewCell229 class ViewCellLeaf: public ViewCell 161 230 { 162 231 public: 163 HierarchyViewCell<T>(): mLeaves(0) {} 164 HierarchyViewCell<T>(Mesh *mesh): 165 ViewCell(mesh), mLeaves(0) {} 232 233 ViewCellLeaf<T>(): mLeaf(NULL) {} 234 ViewCellLeaf<T>(Mesh *mesh): 235 ViewCell(mesh), mLeaf(NULL) {} 166 236 167 237 void UpdateViewCellsStats(ViewCellsStatistics &vcStat) … … 169 239 ViewCell::UpdateViewCellsStats(vcStat); 170 240 171 if ((int)mLeaves.size() > vcStat.maxLeaves) 172 vcStat.maxLeaves = (int)mLeaves.size(); 173 vcStat.leaves += (int)mLeaves.size(); 174 } 175 176 /// Leaves of the hierarchy which are part of this view cell. 177 std::vector<T> mLeaves; 178 }; 179 180 181 typedef HierarchyViewCell<BspLeaf *> BspViewCell; 182 typedef HierarchyViewCell<KdLeaf *> KdViewCell; 183 typedef HierarchyViewCell<VspKdLeaf *> VspKdViewCell; 184 241 //if ((int)mLeaves.size() > vcStat.maxLeaves) 242 // vcStat.maxLeaves = (int)mLeaves.size(); 243 //vcStat.leaves += (int)mLeaves.size(); 244 } 245 246 bool IsLeaf() const 247 { 248 return true; 249 } 250 251 /// Leaf of some hierarchy which is part of this view cell. 252 T mLeaf; 253 }; 254 255 256 typedef ViewCellLeaf<BspLeaf *> BspViewCell; 257 typedef ViewCellLeaf<KdLeaf *> KdViewCell; 258 typedef ViewCellLeaf<VspKdLeaf *> VspKdViewCell; 259 260 261 262 class ViewCellsTree 263 { 264 public: 265 ViewCellsTree(ViewCellsManager *vcm); 266 ~ViewCellsTree(); 267 268 /** Returns number of leaves this view cell consists of. 269 */ 270 int GetSize(ViewCell *vc) const; 271 272 /** Collects leaves corresponding to a view cell. 273 */ 274 void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const; 275 276 /** Merges view cells according to some cost heuristics. 277 */ 278 int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects); 279 280 /** Refines view cells using shuffling, i.e., border leaves 281 of two view cells are exchanged if the resulting view cells 282 are tested to be "better" than the old ones. 283 @returns number of refined view cells 284 */ 285 int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects); 286 287 /** Compresses the pvs of the view cells. 288 */ 289 void CompressViewCellsPvs(); 290 291 /** Returns optimal set of view cells for a given number of view cells. 292 */ 293 void CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells); 294 295 protected: 296 297 298 ////////////////////////////////////////////////////////////// 299 // merge options // 300 ////////////////////////////////////////////////////////////// 301 302 303 /** Returns cost of this leaf according to current heuristics. 304 */ 305 float GetCostHeuristics(ViewCell *vc) const; 306 307 /** Returns cost of leaf. 308 */ 309 float GetRenderCost(ViewCell *vc) const; 310 311 /** Evaluates the merge cost of this merge candidate pair. 312 */ 313 void EvalMergeCost(MergeCandidate &mc) const; 314 315 /** Variance of leaf. 316 */ 317 float GetVariance(ViewCell *vc) const; 318 319 /** Standard deviation of leaf. 320 */ 321 float GetDeviation(ViewCell *vc) const; 322 323 /** Recalculates this merge candidate and sets valid. 324 */ 325 void SetMergeCandidateValid(MergeCandidate &mc) const; 326 327 /** Merge view cells of leaves l1 and l2. 328 @returns difference in pvs size 329 */ 330 ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff); //const; 331 332 /** Shuffles, i.e. takes border leaf from view cell 1 and adds it 333 to view cell 2. 334 */ 335 void ShuffleLeaf(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const; 336 337 /** Shuffles the leaves, i.e., tests if exchanging 338 the leaves helps in improving the view cells. 339 */ 340 bool ShuffleLeaves(ViewCell *l, ViewCell *r) const; 341 342 /** Calculates cost for merge of view cell 1 and 2. 343 */ 344 float EvalShuffleCost(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const; 345 346 /** Exports a snapshot of the merged view cells to disc. 347 */ 348 void ExportMergedViewCells(ViewCellContainer &viewCells, 349 const ObjectContainer &objects, 350 const int numNewViewCells); 351 352 353 354 /** merge queue must be reset after some time because expected value 355 may not be valid. 356 */ 357 void ResetMergeQueue(); 358 359 /** Updates the current top level of view cells. 360 */ 361 int UpdateMergedViewCells(ViewCellContainer &viewCells); 362 363 364 365 ViewCellsManager *mViewCellsManager; 366 ViewCell *mRoot; 367 368 /// if merge visualization should be shown 369 bool mExportMergedViewCells; 370 371 372 373 ViewCellContainer mInactiveViewCells; 374 ViewCellContainer mActiveViewCells; 375 376 /// weights between variance and render cost increase (must be between zero and one) 377 float mRenderCostWeight; 378 379 /// overall cost used to normalize cost ratio 380 float mOverallCost; 381 float mExpectedCost; 382 float mDeviation; 383 float mAvgRenderCost; 384 385 int mUseAreaForPvs; 386 387 int mNumViewCells; 388 389 /// minimal number of view cells 390 int mMergeMinViewCells; 391 /// maximal cost ratio for the merge 392 float mMergeMaxCostRatio; 393 394 ofstream mStats; 395 396 typedef priority_queue<MergeCandidate> MergeQueue; 397 398 MergeQueue mMergeQueue; 399 400 401 402 }; 403 404 405 /** 406 Candidate for leaf merging based on priority. 407 */ 408 class MergeCandidate 409 { 410 friend class ViewCellsTree; 411 412 public: 413 414 MergeCandidate(ViewCell *l, ViewCell *r); 415 416 /** If this merge pair is still valid. 417 */ 418 bool IsValid() const; 419 420 421 friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb) 422 { 423 return leafb.GetMergeCost() < leafa.GetMergeCost(); 424 } 425 426 void SetLeftViewCell(ViewCell *l); 427 void SetRightViewCell(ViewCell *l); 428 429 ViewCell *GetLeftViewCell() const; 430 ViewCell *GetRightViewCell() const; 431 432 ViewCell *GetInitialLeftViewCell() const; 433 ViewCell *GetInitialRightViewCell() const; 434 435 /** Returns the increase of the standard deviation of this merge candidate. 436 */ 437 float GetDeviationIncr() const; 438 439 /** Merge cost of this candidate pair. 440 */ 441 float GetMergeCost() const; 442 443 /** Render cost of this candidate. 444 */ 445 float GetRenderCost() const; 446 447 static float sRenderCostWeight; 448 449 protected: 450 451 /// render cost increase by this merge 452 float mRenderCost; 453 /// increase / decrease of standard deviation 454 float mDeviationIncr; 455 456 ViewCell *mLeftViewCell; 457 ViewCell *mRightViewCell; 458 459 ViewCell *mInitialLeftViewCell; 460 ViewCell *mInitialRightViewCell; 461 }; 462 463 464 class MergeStatistics: public StatisticsBase 465 { 466 public: 467 468 int merged; 469 int siblings; 470 int candidates; 471 int nodes; 472 473 int accTreeDist; 474 int maxTreeDist; 475 476 Real collectTime; 477 Real mergeTime; 478 479 Real overallCost; 480 481 Real expectedRenderCost; 482 Real deviation; 483 Real heuristics; 484 485 // Constructor 486 MergeStatistics() 487 { 488 Reset(); 489 } 490 491 double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 492 493 void Reset() 494 { 495 nodes = 0; 496 merged = 0; 497 siblings = 0; 498 candidates = 0; 499 500 accTreeDist = 0; 501 maxTreeDist = 0; 502 503 collectTime = 0; 504 mergeTime = 0; 505 overallCost = 0; 506 507 expectedRenderCost = 0; 508 deviation = 0; 509 heuristics = 0; 510 511 } 512 513 void Print(ostream &app) const; 514 515 friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 516 { 517 stat.Print(s); 518 return s; 519 } 520 }; 185 521 186 522 #endif -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
r574 r580 208 208 209 209 210 /****************************************************************** /211 /* class BspTree implementation */212 /****************************************************************** /210 /*********************************************************************/ 211 /* class BspTree implementation */ 212 /*********************************************************************/ 213 213 214 214 BspTree::BspTree(): … … 840 840 841 841 leaf->SetViewCell(viewCell); 842 viewCell->mLea ves.push_back(leaf);842 viewCell->mLeaf = leaf; 843 843 844 844 //-- add pvs … … 2208 2208 void BspTree::ConstructGeometry(BspViewCell *vc, BspNodeGeometry &geom) const 2209 2209 { 2210 vector<BspLeaf *> leaves = vc->mLeaves; 2210 // TODO 2211 /* vector<BspLeaf *> leaves = vc->mLeaves; 2211 2212 2212 2213 vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 2213 2214 2214 2215 for (it = leaves.begin(); it != it_end; ++ it) 2215 ConstructGeometry(*it, geom); 2216 ConstructGeometry(*it, geom);*/ 2216 2217 } 2217 2218 -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp
r579 r580 33 33 mViewSpaceBox.Initialize(); 34 34 ParseEnvironment(); 35 36 mViewCellsTree = new ViewCellsTree(this); 35 37 } 36 38 … … 53 55 54 56 environment->GetBoolValue("ViewCells.exportToFile", mExportViewCells); 57 58 environment->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge); 55 59 56 60 mMinPvsSize = emptyViewCells ? 1 : 0; … … 75 79 { 76 80 DEL_PTR(mRenderer); 77 CLEAR_CONTAINER(mViewCells); 81 //CLEAR_CONTAINER(mViewCells); 82 DEL_PTR(mViewCellsTree); 83 78 84 CLEAR_CONTAINER(mMeshContainer); 79 85 } … … 302 308 float ViewCellsManager::GetViewSpaceVolume() 303 309 { 304 return mViewSpaceBox.GetVolume()*(2.0f*sqr( M_PI));310 return mViewSpaceBox.GetVolume()*(2.0f*sqr((float)M_PI)); 305 311 } 306 312 … … 356 362 357 363 358 void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost, 364 void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost, 359 365 float &expectedRenderCost, 360 float &variance) 366 float &deviation, 367 float &variance, 368 int &totalPvs, 369 float &avgRenderCost) 361 370 { 362 371 ViewCellContainer::const_iterator it, it_end = mViewCells.end(); 363 372 373 364 374 //-- compute expected value 365 375 366 376 totalRenderCost = 0; 377 totalPvs = 0; 367 378 368 379 for (it = mViewCells.begin(); it != it_end; ++ it) 369 380 { 370 381 ViewCell *vc = *it; 371 372 382 totalRenderCost += vc->GetPvs().GetSize() * vc->GetVolume(); 373 } 374 383 totalPvs += (int)vc->GetPvs().GetSize(); 384 } 385 386 // normalize with view space box 387 totalRenderCost /= mViewSpaceBox.GetVolume(); 375 388 expectedRenderCost = totalRenderCost / (float)mViewCells.size(); 376 377 378 //-- compute variance 379 389 avgRenderCost = totalPvs / (float)mViewCells.size(); 390 391 392 //-- compute standard defiation 380 393 variance = 0; 394 deviation = 0; 381 395 382 396 for (it = mViewCells.begin(); it != it_end; ++ it) … … 385 399 386 400 float renderCost = vc->GetPvs().GetSize() * vc->GetVolume(); 387 388 const float var = (expectedRenderCost - renderCost) * (expectedRenderCost - renderCost); 389 390 variance += var; 391 } 392 401 float dev; 402 403 if (1) 404 dev = fabs(avgRenderCost - (float)vc->GetPvs().GetSize()); 405 else 406 dev = fabs(expectedRenderCost - renderCost); 407 408 deviation += dev; 409 variance += dev * dev; 410 } 411 393 412 variance /= (float)mViewCells.size(); 413 deviation /= (float)mViewCells.size(); 394 414 } 395 415 … … 493 513 494 514 495 ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const496 { 497 // generate mergedview cell498 ViewCell *vc =GenerateViewCell();515 ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell &left, ViewCell &right) const 516 { 517 // generate parent view cell 518 ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell(); 499 519 500 520 // merge pvs 501 vc->GetPvs().Merge( front.GetPvs(), back.GetPvs());521 vc->GetPvs().Merge(left.GetPvs(), right.GetPvs()); 502 522 503 523 //-- merge ray sets 504 524 if (0) 505 525 { 506 stable_sort( front.mPiercingRays.begin(), front.mPiercingRays.end());507 stable_sort( back.mPiercingRays.begin(), back.mPiercingRays.end());508 509 std::merge( front.mPiercingRays.begin(), front.mPiercingRays.end(),510 back.mPiercingRays.begin(), back.mPiercingRays.end(),526 stable_sort(left.mPiercingRays.begin(), left.mPiercingRays.end()); 527 stable_sort(right.mPiercingRays.begin(), right.mPiercingRays.end()); 528 529 std::merge(left.mPiercingRays.begin(), left.mPiercingRays.end(), 530 right.mPiercingRays.begin(), right.mPiercingRays.end(), 511 531 vc->mPiercingRays.begin()); 512 532 } 513 533 534 535 vc->SetupChildLink(&left); 536 vc->SetupChildLink(&right); 537 538 514 539 return vc; 515 540 } … … 522 547 523 548 524 ViewCell *ViewCellsManager::GenerateViewCell(Mesh *mesh) const525 { 526 return new ViewCell(mesh);549 ViewCellsTree *ViewCellsManager::GetViewCellsTree() 550 { 551 return mViewCellsTree; 527 552 } 528 553 … … 814 839 { 815 840 ExportColor(exporter, *it); 816 ExportV cGeometry(exporter, *it);841 ExportViewCellGeometry(exporter, *it); 817 842 } 818 843 } … … 1186 1211 1187 1212 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 1188 << ", piercing rays=" << (int)vcRays.size() 1189 << ", leaves=" << (int)vc->mLeaves.size() << endl;1213 << ", piercing rays=" << (int)vcRays.size() << endl; 1214 // << ", leaves=" << (int)vc->mLeaves.size() << endl; 1190 1215 1191 1216 1192 1217 // export rays piercing this view cell 1193 #if 01194 1218 exporter->ExportRays(vcRays, RgbColor(0, 1, 0)); 1195 #else 1196 vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end(); 1197 for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit) 1198 exporter->ExportRays((*lit)->mVssRays); 1199 #endif 1219 1200 1220 m.mDiffuseColor = RgbColor(1, 0, 0); 1201 1221 exporter->SetForcedMaterial(m); … … 1249 1269 { 1250 1270 BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit); 1251 ray->intersections.push_back(BspIntersection(0, vc->mLea ves[0]));1271 ray->intersections.push_back(BspIntersection(0, vc->mLeaf)); 1252 1272 } 1253 1273 … … 1278 1298 case 2: // merges 1279 1299 { 1280 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc); 1281 1282 importance = (float)bspVc->mLeaves.size() / 1300 importance = (float)mViewCellsTree->GetSize(vc) / 1283 1301 (float)mViewCellsStats.maxLeaves; 1284 1302 } … … 1301 1319 } 1302 1320 1303 void BspViewCellsManager::ExportV cGeometry(Exporter *exporter,1321 void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 1304 1322 ViewCell *vc) const 1305 1323 { … … 1332 1350 return mBspTree->GetViewCell(point); 1333 1351 } 1352 1353 1354 void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates) 1355 { 1356 // TODO 1357 } 1358 1334 1359 1335 1360 /**********************************************************************/ … … 1585 1610 } 1586 1611 1587 1588 void KdViewCellsManager::ExportVcGeometry(Exporter *exporter, 1589 ViewCell *vc) const 1590 { 1591 KdViewCell *kdVc = dynamic_cast<KdViewCell *>(vc); 1592 vector<KdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end(); 1593 1594 for (it = kdVc->mLeaves.begin(); it != it_end; ++ it) 1595 exporter->ExportBox(mKdTree->GetBox(*it)); 1612 ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const 1613 { 1614 return new KdViewCell(mesh); 1615 } 1616 1617 1618 void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 1619 ViewCell *vc) const 1620 { 1621 ViewCellContainer leaves; 1622 1623 mViewCellsTree->CollectLeaves(vc, leaves); 1624 ViewCellContainer::const_iterator it, it_end = leaves.end(); 1625 1626 for (it = leaves.begin(); it != it_end; ++ it) 1627 { 1628 KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it); 1629 1630 exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaf)); 1631 } 1596 1632 } 1597 1633 … … 1625 1661 // TODO 1626 1662 } 1663 1664 1665 1666 void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 1667 vector<MergeCandidate> &candidates) 1668 { 1669 // TODO 1670 } 1671 1627 1672 1628 1673 /**********************************************************************/ … … 1798 1843 exporter->SetWireframe(); 1799 1844 1800 ExportV cGeometry(exporter, vc);1845 ExportViewCellGeometry(exporter, vc); 1801 1846 1802 1847 //-- export stored rays 1848 1803 1849 if (mExportRays) 1804 1850 { 1805 vector<VspKdLeaf *>::const_iterator it, 1806 it_end = vc->mLeaves.end(); 1807 1808 for (it = vc->mLeaves.begin(); it != it_end; ++ it) 1851 ViewCellContainer leaves; 1852 mViewCellsTree->CollectLeaves(vc, leaves); 1853 1854 ViewCellContainer::const_iterator it, 1855 it_end = leaves.end(); 1856 1857 for (it = leaves.begin(); it != it_end; ++ it) 1809 1858 { 1810 VspKdLeaf *leaf = *it; 1859 VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it); 1860 VspKdLeaf *leaf = vspKdVc->mLeaf; 1811 1861 AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf); 1812 1862 … … 1834 1884 } 1835 1885 } 1836 1886 1837 1887 //-- output PVS of view cell 1838 1888 m.mDiffuseColor = RgbColor(1, 0, 0); … … 1927 1977 } 1928 1978 break; 1929 case 2: // merges 1930 { 1931 VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(vc); 1932 1933 importance = (float)vspKdVc->mLeaves.size() / 1979 case 2: // merged leaves 1980 { 1981 int lSize = mViewCellsTree->GetSize(vc); 1982 importance = (float)lSize / 1934 1983 (float)mViewCellsStats.maxLeaves; 1935 1984 } … … 1954 2003 1955 2004 1956 void VspKdViewCellsManager::ExportV cGeometry(Exporter *exporter,2005 void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 1957 2006 ViewCell *vc) const 1958 2007 { 1959 2008 VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc); 1960 vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();1961 2009 1962 2010 Mesh m; 1963 for (it = kdVc->mLeaves.begin(); it != it_end; ++ it) 1964 { 1965 mVspKdTree->GetBBox(*it).AddBoxToMesh(&m); 2011 2012 ViewCellContainer leaves; 2013 mViewCellsTree->CollectLeaves(vc, leaves); 2014 2015 ViewCellContainer::const_iterator it, it_end = leaves.end(); 2016 2017 for (it = leaves.begin(); it != it_end; ++ it) 2018 { 2019 VspKdLeaf *l = dynamic_cast<VspKdViewCell *>(*it)->mLeaf; 2020 mVspKdTree->GetBBox(l).AddBoxToMesh(&m); 1966 2021 } 1967 2022 … … 1975 2030 } 1976 2031 2032 2033 void VspKdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates) 2034 { 2035 // TODO 2036 } 1977 2037 1978 2038 … … 2131 2191 long startTime = GetTime(); 2132 2192 2193 2133 2194 // TODO: should be done BEFORE the ray casting 2134 merged = mV spBspTree->MergeViewCells(rays, objects);2195 merged = mViewCellsTree->ConstructMergeTree(rays, objects); 2135 2196 2136 2197 //-- stats and visualizations … … 2194 2255 2195 2256 // refining the merged view cells 2196 const int refined = mV spBspTree->RefineViewCells(rays, objects);2257 const int refined = mViewCellsTree->RefineViewCells(rays, objects); 2197 2258 2198 2259 //-- stats and visualizations … … 2234 2295 mViewCellsStats.Reset(); 2235 2296 EvaluateViewCellsStats(); 2297 2236 2298 // has to be recomputed 2237 2299 mTotalAreaValid = false; … … 2254 2316 //-- merge the individual view cells 2255 2317 MergeViewCells(postProcessRays, objects); 2318 2256 2319 //-- refines the merged view cells 2257 2320 RefineViewCells(postProcessRays, objects); 2321 2322 if (1) 2323 { 2324 float totalCost, erc, var, dev, avg; 2325 int totalpvs; 2326 2327 mViewCellsStats.Reset(); 2328 2329 EvaluateRenderStatistics(totalCost, erc, dev, var, totalpvs, avg); 2330 2331 Debug << "statistics after merge " 2332 << " erc: " << erc 2333 << " dev: " << dev 2334 << " totalpvs: " << totalpvs 2335 << " avg: " << avg << endl; 2336 } 2337 2258 2338 2259 2339 //-- export shuffled view cells … … 2293 2373 vm.mDiffuseColor.b -= 0.45f; 2294 2374 2295 vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end(); 2296 2297 for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit) 2375 2376 ViewCellContainer leaves; 2377 mViewCellsTree->CollectLeaves(vc, leaves); 2378 2379 ViewCellContainer::const_iterator lit, lit_end = leaves.end(); 2380 2381 for (lit = leaves.begin(); lit != lit_end; ++ lit) 2298 2382 { 2299 BspLeaf *leaf = *lit;2383 BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf; 2300 2384 2301 2385 if (leaf->Mailed()) … … 2391 2475 if (1) // export view cells 2392 2476 { 2393 cout << "exporting view cells after post process ... ";2394 2477 Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d"); 2395 2478 2396 2479 if (exporter) 2397 2480 { 2481 cout << "exporting view cells after post process ... "; 2482 2398 2483 if (1) 2399 2484 { … … 2416 2501 ExportViewCellsForViz(exporter); 2417 2502 delete exporter; 2503 cout << "finished" << endl; 2418 2504 } 2419 2505 } … … 2446 2532 BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit); 2447 2533 2448 vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end(); 2449 2450 for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit) 2534 ViewCellContainer leaves; 2535 mViewCellsTree->CollectLeaves(vc, leaves); 2536 2537 ViewCellContainer::const_iterator lit, lit_end = leaves.end(); 2538 2539 for (lit = leaves.begin(); lit != lit_end; ++ lit) 2451 2540 { 2452 BspLeaf *leaf = *lit;2541 BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf; 2453 2542 2454 2543 Material m; … … 2573 2662 { 2574 2663 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(ray->mViewCells[j]); 2575 BspLeaf *leaf = bspVc->mLea ves[0];2664 BspLeaf *leaf = bspVc->mLeaf; 2576 2665 if (vc == bspVc) 2577 2666 vcRays.push_back(ray); … … 2589 2678 exporter->SetForcedMaterial(m); 2590 2679 2591 ExportV cGeometry(exporter, vc);2680 ExportViewCellGeometry(exporter, vc); 2592 2681 2593 2682 2594 2683 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 2595 << ", piercing rays=" << (int)vcRays.size() 2596 << ", leaves=" << (int)vc->mLeaves.size() << endl;2684 << ", piercing rays=" << (int)vcRays.size() << endl; 2685 // << ", leaves=" << (int)vc->mLeaves.size() << endl; 2597 2686 2598 2687 … … 2604 2693 else 2605 2694 { 2606 vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end(); 2607 2608 for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit) 2609 exporter->ExportRays((*lit)->mVssRays); 2695 2696 ViewCellContainer leaves; 2697 mViewCellsTree->CollectLeaves(vc, leaves); 2698 2699 ViewCellContainer::const_iterator lit, lit_end = leaves.end(); 2700 2701 for (lit = leaves.begin(); lit != lit_end; ++ lit) 2702 { 2703 BspLeaf *l = dynamic_cast<BspViewCell *>(*lit)->mLeaf; 2704 exporter->ExportRays(l->mVssRays); 2705 } 2610 2706 } 2611 2707 … … 2686 2782 case 2: // merges 2687 2783 { 2688 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc); 2689 2690 importance = (float)bspVc->mLeaves.size() / 2691 (float)mViewCellsStats.maxLeaves; 2784 int lSize = mViewCellsTree->GetSize(vc); 2785 2786 importance = (float)lSize / (float)mViewCellsStats.maxLeaves; 2692 2787 } 2693 2788 break; … … 2713 2808 2714 2809 2715 void VspBspViewCellsManager::ExportV cGeometry(Exporter *exporter,2810 void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 2716 2811 ViewCell *vc) const 2717 2812 { … … 2731 2826 int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const 2732 2827 { 2733 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc); 2828 ViewCellContainer leaves; 2829 mViewCellsTree->CollectLeaves(vc, leaves); 2830 2734 2831 2735 2832 int maxDist = 0; 2833 2736 2834 // compute max height difference 2737 for (int i = 0; i < (int) bspVc->mLeaves.size(); ++ i)2738 for (int j = 0; j < (int) bspVc->mLeaves.size(); ++ j)2739 { 2740 BspLeaf *leaf = bspVc->mLeaves[i];2835 for (int i = 0; i < (int)leaves.size(); ++ i) 2836 for (int j = 0; j < (int)leaves.size(); ++ j) 2837 { 2838 BspLeaf *leaf = dynamic_cast<BspViewCell *>(leaves[i])->mLeaf; 2741 2839 2742 2840 if (i != j) 2743 2841 { 2744 BspLeaf *leaf2 = bspVc->mLeaves[j];2842 BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaf; 2745 2843 int dist = mVspBspTree->TreeDistance(leaf, leaf2); 2746 2844 if (dist > maxDist) … … 2748 2846 } 2749 2847 } 2848 2750 2849 return maxDist; 2751 2850 } … … 2871 2970 CreateMesh(vc); 2872 2971 2873 vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();2874 2875 2972 float area = 0; 2876 2973 float volume = 0; 2877 2974 2878 for (it = vc->mLeaves.begin(); it != it_end; ++ it) 2975 ViewCellContainer leaves; 2976 mViewCellsTree->CollectLeaves(vc, leaves); 2977 2978 ViewCellContainer::const_iterator it, it_end = leaves.end(); 2979 2980 for (it = leaves.begin(); it != it_end; ++ it) 2879 2981 { 2880 2982 BspNodeGeometry geom; 2881 BspLeaf *leaf = *it;2983 BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf; 2882 2984 mVspBspTree->ConstructGeometry(leaf, geom); 2883 2985 … … 2898 3000 2899 3001 2900 //////////////////////////////////77 3002 3003 void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 3004 vector<MergeCandidate> &candidates) 3005 { 3006 cout << "collecting merge candidates ... " << endl; 3007 3008 if (mUseRaysForMerge) 3009 { 3010 mVspBspTree->CollectMergeCandidates(rays, candidates); 3011 } 3012 else 3013 { 3014 vector<BspLeaf *> leaves; 3015 mVspBspTree->CollectLeaves(leaves); 3016 mVspBspTree->CollectMergeCandidates(leaves, candidates); 3017 } 3018 3019 cout << "fininshed collecting candidates" << endl; 3020 } 3021 3022 3023 3024 ////////////////////////////////// 2901 3025 ViewCellsManager *ViewCellsManagerFactory::Create(const string mName) 2902 3026 { … … 2904 3028 return NULL;// new VspBspViewCellsManager(); 2905 3029 } 3030 -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h
r579 r580 27 27 class Beam; 28 28 class Preprocessor; 29 class ViewCellsTree; 30 class MergeCandidate; 29 31 30 32 struct BspRay; … … 133 135 @returns new view cell based on the merging. 134 136 */ 135 ViewCell *MergeViewCells(ViewCell &front, ViewCell &back) const;137 ViewCellInterior *MergeViewCells(ViewCell &front, ViewCell &back) const; 136 138 137 139 /** Generates view cell of type specified by this manager 138 140 */ 139 virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const ;141 virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const = 0; 140 142 141 143 /** Adds a new view cell to the list of predefined view cells. … … 206 208 virtual float GetRendercost(ViewCell *viewCell, float objRendercost) const = 0; 207 209 208 /** Returns vector of loaded / generated view cells.210 /** Returns container of loaded / generated view cells. 209 211 */ 210 212 ViewCellContainer &GetViewCells(); … … 311 313 /** Exports view cell geometry. 312 314 */ 313 virtual void ExportV cGeometry(Exporter *exporter, ViewCell *vc) const = 0;315 virtual void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const = 0; 314 316 315 317 virtual void FinalizeViewCells(const bool createMesh); … … 325 327 /** Evaluates statistics values on view cells. 326 328 */ 327 void EvaluateRenderStatistics(float &totalRenderCost, 328 float &expectedRenderCost, 329 float &variance); 329 void EvaluateRenderStatistics(float &totalRenderCost, 330 float &expectedRenderCost, 331 float &deviation, 332 float &variance, 333 int &totalPvs, 334 float &avgRenderCost); 335 336 337 /** Returns hierarchy of the view cells. 338 */ 339 ViewCellsTree *GetViewCellsTree(); 340 341 virtual void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates) = 0; 342 330 343 331 344 protected: … … 392 405 /// Loaded view cells 393 406 ViewCellContainer mViewCells; 407 408 ViewCellsTree *mViewCellsTree; 394 409 395 410 /// maximum number of samples taken for construction of the view cells … … 417 432 bool mOnlyValidViewCells; 418 433 434 /// if rays should be used to collect merge candidates 435 bool mUseRaysForMerge; 436 437 419 438 //-- visualization options 420 439 … … 472 491 void CreateMesh(ViewCell *vc); 473 492 474 void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const; 493 void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const; 494 495 void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates); 475 496 476 497 protected: … … 529 550 bool ViewCellsConstructed() const; 530 551 552 ViewCell *GenerateViewCell(Mesh *mesh) const; 531 553 532 554 /** Prints out statistics of this approach. … … 540 562 void CreateMesh(ViewCell *vc); 541 563 542 void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const; 564 void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const; 565 566 void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates); 543 567 544 568 protected: 545 569 570 /** Collects view cells from a hierarchy. 571 */ 546 572 void CollectViewCells(); 573 547 574 KdNode *GetNodeForPvs(KdLeaf *leaf); 548 575 … … 598 625 void CreateMesh(ViewCell *vc); 599 626 600 void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const; 627 void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const; 628 629 void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates); 601 630 602 631 protected: … … 664 693 int CastBeam(Beam &beam); 665 694 666 void ExportV cGeometry(Exporter *exporter, ViewCell *vc) const;695 void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const; 667 696 668 697 //float GetVolume(ViewCell *viewCell) const; 669 698 670 699 void Finalize(ViewCell *viewCell, const bool createMesh); 700 701 void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates); 671 702 672 703 protected: -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsParser.cpp
r577 r580 356 356 { 357 357 // TODO: get view cell with specified id 358 ViewCell dummyVc;358 BspViewCell dummyVc; 359 359 dummyVc.SetId(viewCellId); 360 360 … … 363 363 364 364 BspViewCell *viewCell = dynamic_cast<BspViewCell *>(*vit); 365 365 366 if (viewCell->GetId() == viewCellId) 366 367 { -
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
r579 r580 25 25 const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0}; 26 26 /** Evaluates split plane classification with respect to the plane's 27 contribution for balanced rays.27 contribution for balanced rays. 28 28 */ 29 29 const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0}; 30 30 31 ViewCellsManager *BspMergeCandidate::sViewCellsManager = NULL;32 //int BspMergeCandidate::sMaxPvsSize = 0;33 //int BspMergeCandidate::sMinPvsSize = 0;34 31 35 32 int VspBspTree::sFrontId = 0; … … 37 34 int VspBspTree::sFrontAndBackId = 0; 38 35 39 float BspMergeCandidate::sOverallCost = 0;40 float BspMergeCandidate::sExpectedCost = 0;41 float BspMergeCandidate::sVariance = 0;42 float BspMergeCandidate::sRenderCostWeight = 0.5f;43 bool BspMergeCandidate::sUseArea = false;44 int BspMergeCandidate::sNumViewCells = 0;45 46 //int upperPvsLimit = 120;47 //int lowerPvsLimit = 5;48 36 49 37 … … 64 52 65 53 66 // penalty for pvs durint merge67 inline float EvalPvsPenaltyForMerge(const int pvs,68 const int lower,69 const int upper)70 {71 // clamp to minmax values72 if (pvs < lower)73 return (float)lower;74 if (pvs > upper)75 return (float)upper;76 77 return (float)pvs;78 }79 54 80 55 … … 90 65 mViewCellsManager(NULL), 91 66 mOutOfBoundsCell(NULL), 92 mStoreRays(false) 67 mStoreRays(false), 68 mRenderCostWeight(0.5) 93 69 { 94 70 bool randomize = false; … … 126 102 // if only the driving axis is used for axis aligned split 127 103 environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis); 128 129 //-- merge options 130 environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells); 131 environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 132 environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge); 133 134 104 135 105 //-- termination criteria for axis aligned split 136 106 environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution", … … 142 112 environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory); 143 113 144 environment->GetBoolValue("VspBspTree.Visualization.exportMergedViewCells", mExportMergedViewCells); 145 environment->GetBoolValue("VspBspTree.PostProcess.exportMergeStats", mExportMergeStats); 146 147 148 mStats.open("bspStats.log"); 114 environment->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight); 115 116 117 149 118 150 119 //-- debug output 120 151 121 Debug << "******* VSP BSP options ******** " << endl; 152 122 Debug << "max depth: " << mTermMaxDepth << endl; … … 162 132 Debug << "max plane candidates: " << mMaxRayCandidates << endl; 163 133 Debug << "randomize: " << randomize << endl; 164 Debug << "minimum view cells: " << mMergeMinViewCells << endl;134 // Debug << "minimum view cells: " << mMergeMinViewCells << endl; 165 135 Debug << "using area for pvs: " << mUseAreaForPvs << endl; 136 Debug << "render cost weight: " << mRenderCostWeight << endl; 166 137 Debug << "Split plane strategy: "; 167 138 … … 195 166 Debug << endl; 196 167 } 168 197 169 198 170 BspViewCell *VspBspTree::GetOutOfBoundsCell() … … 249 221 return (int)mesh->mFaces.size(); 250 222 } 223 251 224 252 225 int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells, … … 273 246 return polysSize; 274 247 } 248 275 249 276 250 int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects, … … 310 284 } 311 285 286 312 287 void VspBspTree::Construct(const VssRayContainer &sampleRays, 313 288 AxisAlignedBox3 *forcedBoundingBox) … … 366 341 367 342 Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl; 343 368 344 //-- store rays 369 345 for (rit = sampleRays.begin(); rit != rit_end; ++ rit) … … 572 548 } 573 549 574 viewCell->mLea ves.push_back(leaf);550 viewCell->mLeaf = leaf; 575 551 576 552 if (mUseAreaForPvs) … … 589 565 return newNode; 590 566 } 591 592 593 567 594 568 … … 752 726 } 753 727 728 754 729 void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis) 755 730 { … … 780 755 stable_sort(mSplitCandidates->begin(), mSplitCandidates->end()); 781 756 } 757 782 758 783 759 float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays, … … 1035 1011 1036 1012 1013 bool VspBspTree::SelectPlane(Plane3 &bestPlane, 1014 BspLeaf *leaf, 1015 VspBspTraversalData &data, 1016 VspBspTraversalData &frontData, 1017 VspBspTraversalData &backData) 1018 { 1019 // simplest strategy: just take next polygon 1020 if (mSplitPlaneStrategy & RANDOM_POLYGON) 1021 { 1022 if (!data.mPolygons->empty()) 1023 { 1024 const int randIdx = 1025 (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1)); 1026 Polygon3 *nextPoly = (*data.mPolygons)[randIdx]; 1027 1028 bestPlane = nextPoly->GetSupportingPlane(); 1029 return true; 1030 } 1031 } 1032 1033 //-- use heuristics to find appropriate plane 1034 1035 // intermediate plane 1036 Plane3 plane; 1037 float lowestCost = MAX_FLOAT; 1038 1039 // decides if the first few splits should be only axisAligned 1040 const bool onlyAxisAligned = 1041 (mSplitPlaneStrategy & AXIS_ALIGNED) && 1042 ((int)data.mRays->size() > mTermMinRaysForAxisAligned) && 1043 ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned); 1044 1045 const int limit = onlyAxisAligned ? 0 : 1046 Min((int)data.mPolygons->size(), mMaxPolyCandidates); 1047 1048 float candidateCost; 1049 1050 int maxIdx = (int)data.mPolygons->size(); 1051 1052 for (int i = 0; i < limit; ++ i) 1053 { 1054 // the already taken candidates are stored behind maxIdx 1055 // => assure that no index is taken twice 1056 const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx)); 1057 Polygon3 *poly = (*data.mPolygons)[candidateIdx]; 1058 1059 // swap candidate to the end to avoid testing same plane 1060 std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]); 1061 //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)]; 1062 1063 // evaluate current candidate 1064 BspNodeGeometry fGeom, bGeom; 1065 float fArea, bArea; 1066 plane = poly->GetSupportingPlane(); 1067 candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea); 1068 1069 if (candidateCost < lowestCost) 1070 { 1071 bestPlane = plane; 1072 lowestCost = candidateCost; 1073 } 1074 } 1075 1076 //-- evaluate axis aligned splits 1077 int axis; 1078 BspNodeGeometry *fGeom, *bGeom; 1079 float pFront, pBack; 1080 1081 candidateCost = SelectAxisAlignedPlane(plane, data, axis, 1082 &fGeom, &bGeom, 1083 pFront, pBack, 1084 data.mIsKdNode); 1085 1086 bool isAxisAlignedSplit = false; 1087 1088 if (candidateCost < lowestCost) 1089 { 1090 bestPlane = plane; 1091 lowestCost = candidateCost; 1092 1093 // assign already computed values 1094 // we can do this because we always save the 1095 // computed values from the axis aligned splits 1096 frontData.mGeometry = fGeom; 1097 backData.mGeometry = bGeom; 1098 1099 frontData.mProbability = pFront; 1100 backData.mProbability = pBack; 1101 1102 //! error also computed if cost ratio is missed 1103 ++ mBspStats.splits[axis]; 1104 isAxisAlignedSplit = true; 1105 } 1106 else 1107 { 1108 DEL_PTR(fGeom); 1109 DEL_PTR(bGeom); 1110 } 1111 1112 frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit); 1113 1114 #ifdef _DEBUG 1115 Debug << "plane lowest cost: " << lowestCost << endl; 1116 #endif 1117 1118 // cost ratio miss 1119 if (lowestCost > mTermMaxCostRatio) 1120 return false; 1121 1122 return true; 1123 } 1124 1125 1126 Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const 1127 { 1128 const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 1129 1130 const Vector3 minPt = rays[candidateIdx].ExtrapOrigin(); 1131 const Vector3 maxPt = rays[candidateIdx].ExtrapTermination(); 1132 1133 const Vector3 pt = (maxPt + minPt) * 0.5; 1134 const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir()); 1135 1136 return Plane3(normal, pt); 1137 } 1138 1139 1140 Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const 1141 { 1142 Vector3 pt[3]; 1143 1144 int idx[3]; 1145 int cmaxT = 0; 1146 int cminT = 0; 1147 bool chooseMin = false; 1148 1149 for (int j = 0; j < 3; ++ j) 1150 { 1151 idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1)); 1152 1153 if (idx[j] >= (int)rays.size()) 1154 { 1155 idx[j] -= (int)rays.size(); 1156 1157 chooseMin = (cminT < 2); 1158 } 1159 else 1160 chooseMin = (cmaxT < 2); 1161 1162 RayInfo rayInf = rays[idx[j]]; 1163 pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination(); 1164 } 1165 1166 return Plane3(pt[0], pt[1], pt[2]); 1167 } 1168 1169 1170 Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const 1171 { 1172 Vector3 pt[3]; 1173 1174 int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 1175 int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 1176 1177 // check if rays different 1178 if (idx1 == idx2) 1179 idx2 = (idx2 + 1) % (int)rays.size(); 1180 1181 const RayInfo ray1 = rays[idx1]; 1182 const RayInfo ray2 = rays[idx2]; 1183 1184 // normal vector of the plane parallel to both lines 1185 const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir())); 1186 1187 // vector from line 1 to line 2 1188 const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin(); 1189 1190 // project vector on normal to get distance 1191 const float dist = DotProd(vd, norm); 1192 1193 // point on plane lies halfway between the two planes 1194 const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5; 1195 1196 return Plane3(norm, planePt); 1197 } 1198 1199 1200 inline void VspBspTree::GenerateUniqueIdsForPvs() 1201 { 1202 Intersectable::NewMail(); sBackId = Intersectable::sMailId; 1203 Intersectable::NewMail(); sFrontId = Intersectable::sMailId; 1204 Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId; 1205 } 1206 1207 1208 float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane, 1209 const VspBspTraversalData &data, 1210 BspNodeGeometry &geomFront, 1211 BspNodeGeometry &geomBack, 1212 float &pFront, 1213 float &pBack) const 1214 { 1215 float cost = 0; 1216 1217 float sumBalancedRays = 0; 1218 float sumRaySplits = 0; 1219 1220 int pvsFront = 0; 1221 int pvsBack = 0; 1222 1223 // probability that view point lies in back / front node 1224 float pOverall = 0; 1225 pFront = 0; 1226 pBack = 0; 1227 1228 int raysFront = 0; 1229 int raysBack = 0; 1230 int totalPvs = 0; 1231 1232 int limit; 1233 bool useRand; 1234 1235 // choose test rays randomly if too much 1236 if ((int)data.mRays->size() > mMaxTests) 1237 { 1238 useRand = true; 1239 limit = mMaxTests; 1240 } 1241 else 1242 { 1243 useRand = false; 1244 limit = (int)data.mRays->size(); 1245 } 1246 1247 for (int i = 0; i < limit; ++ i) 1248 { 1249 const int testIdx = useRand ? 1250 (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i; 1251 RayInfo rayInf = (*data.mRays)[testIdx]; 1252 1253 float t; 1254 VssRay *ray = rayInf.mRay; 1255 const int cf = rayInf.ComputeRayIntersection(candidatePlane, t); 1256 1257 if (0) 1258 { 1259 if (cf >= 0) 1260 ++ raysFront; 1261 if (cf <= 0) 1262 ++ raysBack; 1263 } 1264 1265 if (mSplitPlaneStrategy & LEAST_RAY_SPLITS) 1266 { 1267 sumBalancedRays += cf; 1268 } 1269 1270 if (mSplitPlaneStrategy & BALANCED_RAYS) 1271 { 1272 if (cf == 0) 1273 ++ sumRaySplits; 1274 } 1275 1276 if (mSplitPlaneStrategy & PVS) 1277 { 1278 // find front and back pvs for origing and termination object 1279 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs); 1280 AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs); 1281 } 1282 } 1283 1284 const float raysSize = (float)data.mRays->size() + Limits::Small; 1285 1286 if (mSplitPlaneStrategy & PVS) 1287 { 1288 // create unique ids for pvs heuristics 1289 GenerateUniqueIdsForPvs(); 1290 1291 // construct child geometry with regard to the candidate split plane 1292 data.mGeometry->SplitGeometry(geomFront, 1293 geomBack, 1294 candidatePlane, 1295 mBox, 1296 mEpsilon); 1297 1298 pOverall = data.mProbability; 1299 1300 if (!mUseAreaForPvs) // use front and back cell areas to approximate volume 1301 { 1302 pFront = geomFront.GetVolume(); 1303 pBack = pOverall - geomFront.GetVolume(); 1304 } 1305 else 1306 { 1307 pFront = geomFront.GetArea(); 1308 pBack = geomBack.GetArea(); 1309 } 1310 } 1311 1312 1313 if (mSplitPlaneStrategy & LEAST_RAY_SPLITS) 1314 cost += mLeastRaySplitsFactor * sumRaySplits / raysSize; 1315 1316 if (mSplitPlaneStrategy & BALANCED_RAYS) 1317 cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize; 1318 1319 // -- pvs rendering heuristics 1320 if (mSplitPlaneStrategy & PVS) 1321 { 1322 const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 1323 const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 1324 1325 // only render cost heuristics or combined with standard deviation 1326 if (1) 1327 { 1328 const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit); 1329 const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 1330 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 1331 1332 const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small; 1333 const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack; 1334 1335 float oldCost, newCost; 1336 1337 if (1) 1338 { 1339 oldCost = oldRenderCost; 1340 newCost = newRenderCost; 1341 } 1342 else 1343 { 1344 // standard deviation is difference of back and front pvs 1345 const float expectedCost = 0.5f * (penaltyFront + penaltyBack); 1346 1347 const float newDeviation = 0.5f * 1348 fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost); 1349 1350 const float oldDeviation = penaltyOld + Limits::Small; 1351 1352 newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation; 1353 oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation; 1354 } 1355 1356 cost += mPvsFactor * newCost / oldCost; 1357 } 1358 else 1359 { 1360 //-- compute weighted sum of expected render cost and standard deviation 1361 1362 //-- first compute expected render cost 1363 const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit); 1364 const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 1365 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 1366 1367 const float renderCostFront = penaltyFront * pFront; 1368 const float renderCostBack = penaltyBack * pBack; 1369 1370 const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small; 1371 const float newRenderCost = renderCostFront + renderCostBack; 1372 1373 1374 //-- compute standard deviation 1375 const float expectedCost = 0.5f * (renderCostBack + renderCostFront); 1376 1377 const float devFront = fabs(renderCostFront - expectedCost); 1378 1379 const float devBack = fabs(renderCostBack - expectedCost); 1380 1381 const float newDev = 0.5f * (devFront + devBack); 1382 const float oldDev = oldRenderCost * oldRenderCost; 1383 1384 const float newCost = newRenderCost * mRenderCostWeight + newDev * (1.0f - mRenderCostWeight); 1385 const float oldCost = oldRenderCost * mRenderCostWeight + oldDev * (1.0f - mRenderCostWeight); 1386 1387 cost += mPvsFactor * newCost / oldCost; 1388 1389 // also try to equalize render differences between front and back pvs 1390 //const float oldCost = pOverall + Limits::Small; 1391 //float newCost = (float)abs(pvsFront - pvsBack); 1392 1393 } 1394 } 1395 1396 #ifdef _DEBUG 1397 Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall 1398 << " frontpvs: " << pvsFront << " pFront: " << pFront 1399 << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl; 1400 #endif 1401 1402 // normalize cost by sum of linear factors 1403 if(0) 1404 return cost / (float)mCostNormalizer; 1405 else 1406 return cost; 1407 } 1408 1409 1037 1410 float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data, 1038 1411 const AxisAlignedBox3 &box, … … 1110 1483 1111 1484 return (mCtDivCi + newCost) / oldCost; 1112 }1113 1114 1115 1116 bool VspBspTree::SelectPlane(Plane3 &bestPlane,1117 BspLeaf *leaf,1118 VspBspTraversalData &data,1119 VspBspTraversalData &frontData,1120 VspBspTraversalData &backData)1121 {1122 // simplest strategy: just take next polygon1123 if (mSplitPlaneStrategy & RANDOM_POLYGON)1124 {1125 if (!data.mPolygons->empty())1126 {1127 const int randIdx =1128 (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));1129 Polygon3 *nextPoly = (*data.mPolygons)[randIdx];1130 1131 bestPlane = nextPoly->GetSupportingPlane();1132 return true;1133 }1134 }1135 1136 //-- use heuristics to find appropriate plane1137 1138 // intermediate plane1139 Plane3 plane;1140 float lowestCost = MAX_FLOAT;1141 1142 // decides if the first few splits should be only axisAligned1143 const bool onlyAxisAligned =1144 (mSplitPlaneStrategy & AXIS_ALIGNED) &&1145 ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&1146 ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);1147 1148 const int limit = onlyAxisAligned ? 0 :1149 Min((int)data.mPolygons->size(), mMaxPolyCandidates);1150 1151 float candidateCost;1152 1153 int maxIdx = (int)data.mPolygons->size();1154 1155 for (int i = 0; i < limit; ++ i)1156 {1157 // the already taken candidates are stored behind maxIdx1158 // => assure that no index is taken twice1159 const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));1160 Polygon3 *poly = (*data.mPolygons)[candidateIdx];1161 1162 // swap candidate to the end to avoid testing same plane1163 std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);1164 //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];1165 1166 // evaluate current candidate1167 BspNodeGeometry fGeom, bGeom;1168 float fArea, bArea;1169 plane = poly->GetSupportingPlane();1170 candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);1171 1172 if (candidateCost < lowestCost)1173 {1174 bestPlane = plane;1175 lowestCost = candidateCost;1176 }1177 }1178 1179 //-- evaluate axis aligned splits1180 int axis;1181 BspNodeGeometry *fGeom, *bGeom;1182 float pFront, pBack;1183 1184 candidateCost = SelectAxisAlignedPlane(plane, data, axis,1185 &fGeom, &bGeom,1186 pFront, pBack,1187 data.mIsKdNode);1188 1189 bool isAxisAlignedSplit = false;1190 1191 if (candidateCost < lowestCost)1192 {1193 bestPlane = plane;1194 lowestCost = candidateCost;1195 1196 // assign already computed values1197 // we can do this because we always save the1198 // computed values from the axis aligned splits1199 frontData.mGeometry = fGeom;1200 backData.mGeometry = bGeom;1201 1202 frontData.mProbability = pFront;1203 backData.mProbability = pBack;1204 1205 //! error also computed if cost ratio is missed1206 ++ mBspStats.splits[axis];1207 isAxisAlignedSplit = true;1208 }1209 else1210 {1211 DEL_PTR(fGeom);1212 DEL_PTR(bGeom);1213 }1214 1215 frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);1216 1217 #ifdef _DEBUG1218 Debug << "plane lowest cost: " << lowestCost << endl;1219 #endif1220 1221 // cost ratio miss1222 if (lowestCost > mTermMaxCostRatio)1223 return false;1224 1225 return true;1226 }1227 1228 1229 Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const1230 {1231 const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));1232 1233 const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();1234 const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();1235 1236 const Vector3 pt = (maxPt + minPt) * 0.5;1237 const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());1238 1239 return Plane3(normal, pt);1240 }1241 1242 1243 Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const1244 {1245 Vector3 pt[3];1246 1247 int idx[3];1248 int cmaxT = 0;1249 int cminT = 0;1250 bool chooseMin = false;1251 1252 for (int j = 0; j < 3; ++ j)1253 {1254 idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));1255 1256 if (idx[j] >= (int)rays.size())1257 {1258 idx[j] -= (int)rays.size();1259 1260 chooseMin = (cminT < 2);1261 }1262 else1263 chooseMin = (cmaxT < 2);1264 1265 RayInfo rayInf = rays[idx[j]];1266 pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();1267 }1268 1269 return Plane3(pt[0], pt[1], pt[2]);1270 }1271 1272 Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const1273 {1274 Vector3 pt[3];1275 1276 int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));1277 int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));1278 1279 // check if rays different1280 if (idx1 == idx2)1281 idx2 = (idx2 + 1) % (int)rays.size();1282 1283 const RayInfo ray1 = rays[idx1];1284 const RayInfo ray2 = rays[idx2];1285 1286 // normal vector of the plane parallel to both lines1287 const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));1288 1289 // vector from line 1 to line 21290 const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();1291 1292 // project vector on normal to get distance1293 const float dist = DotProd(vd, norm);1294 1295 // point on plane lies halfway between the two planes1296 const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;1297 1298 return Plane3(norm, planePt);1299 }1300 1301 1302 inline void VspBspTree::GenerateUniqueIdsForPvs()1303 {1304 Intersectable::NewMail(); sBackId = ViewCell::sMailId;1305 Intersectable::NewMail(); sFrontId = ViewCell::sMailId;1306 Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;1307 }1308 1309 1310 float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,1311 const VspBspTraversalData &data,1312 BspNodeGeometry &geomFront,1313 BspNodeGeometry &geomBack,1314 float &pFront,1315 float &pBack) const1316 {1317 float cost = 0;1318 1319 float sumBalancedRays = 0;1320 float sumRaySplits = 0;1321 1322 int pvsFront = 0;1323 int pvsBack = 0;1324 1325 // probability that view point lies in back / front node1326 float pOverall = 0;1327 pFront = 0;1328 pBack = 0;1329 1330 int raysFront = 0;1331 int raysBack = 0;1332 int totalPvs = 0;1333 1334 int limit;1335 bool useRand;1336 1337 // choose test rays randomly if too much1338 if ((int)data.mRays->size() > mMaxTests)1339 {1340 useRand = true;1341 limit = mMaxTests;1342 }1343 else1344 {1345 useRand = false;1346 limit = (int)data.mRays->size();1347 }1348 1349 for (int i = 0; i < limit; ++ i)1350 {1351 const int testIdx = useRand ?1352 (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;1353 RayInfo rayInf = (*data.mRays)[testIdx];1354 1355 float t;1356 VssRay *ray = rayInf.mRay;1357 const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);1358 1359 if (0)1360 {1361 if (cf >= 0)1362 ++ raysFront;1363 if (cf <= 0)1364 ++ raysBack;1365 }1366 1367 if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)1368 {1369 sumBalancedRays += cf;1370 }1371 1372 if (mSplitPlaneStrategy & BALANCED_RAYS)1373 {1374 if (cf == 0)1375 ++ sumRaySplits;1376 }1377 1378 if (mSplitPlaneStrategy & PVS)1379 {1380 // find front and back pvs for origing and termination object1381 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);1382 AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);1383 }1384 }1385 1386 const float raysSize = (float)data.mRays->size() + Limits::Small;1387 1388 if (mSplitPlaneStrategy & PVS)1389 {1390 // create unique ids for pvs heuristics1391 GenerateUniqueIdsForPvs();1392 1393 // construct child geometry with regard to the candidate split plane1394 data.mGeometry->SplitGeometry(geomFront,1395 geomBack,1396 candidatePlane,1397 mBox,1398 mEpsilon);1399 1400 pOverall = data.mProbability;1401 1402 if (!mUseAreaForPvs) // use front and back cell areas to approximate volume1403 {1404 pFront = geomFront.GetVolume();1405 pBack = pOverall - geomFront.GetVolume();1406 }1407 else1408 {1409 pFront = geomFront.GetArea();1410 pBack = geomBack.GetArea();1411 }1412 }1413 1414 1415 if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)1416 cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;1417 1418 if (mSplitPlaneStrategy & BALANCED_RAYS)1419 cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;1420 1421 // pvs criterium1422 if (mSplitPlaneStrategy & PVS)1423 {1424 if (1)1425 {1426 const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();1427 const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();1428 1429 const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);1430 1431 const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);1432 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);1433 1434 const float oldCost = pOverall * (float)penaltyOld + Limits::Small;1435 cost += mPvsFactor * (penaltyFront * pFront + penaltyBack * pBack) / oldCost;1436 1437 }1438 else1439 {1440 // try to equalize render differences1441 //const float oldCost = pOverall * (float)totalPvs + Limits::Small;1442 //float newCost = fabs(pvsFront * pFront - pvsBack * pBack);1443 const float oldCost = pOverall + Limits::Small;1444 float newCost = (float)abs(pvsFront - pvsBack);1445 1446 cost += mPvsFactor * newCost / oldCost;1447 }1448 }1449 1450 #ifdef _DEBUG1451 Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall1452 << " frontpvs: " << pvsFront << " pFront: " << pFront1453 << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;1454 #endif1455 1456 // normalize cost by sum of linear factors1457 if(0)1458 return cost / (float)mCostNormalizer;1459 else1460 return cost;1461 1485 } 1462 1486 … … 1731 1755 { 1732 1756 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell(); 1733 1734 vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end(); 1735 for (it = viewCell->mLeaves.begin();it != it_end; ++ it) 1757 1758 ViewCellContainer leaves; 1759 mViewCellsManager->GetViewCellsTree()->CollectLeaves(viewCell, leaves); 1760 1761 ViewCellContainer::const_iterator it, it_end = leaves.end(); 1762 1763 for (it = leaves.begin(); it != it_end; ++ it) 1736 1764 { 1737 BspLeaf *l = *it;1765 BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf; 1738 1766 l->SetViewCell(GetOrCreateOutOfBoundsCell()); 1739 1767 ++ mBspStats.invalidLeaves; … … 2024 2052 BspNodeGeometry &vcGeom) const 2025 2053 { 2026 vector<BspLeaf *> leaves = vc->mLeaves; 2027 vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 2054 ViewCellContainer leaves; 2055 mViewCellsManager->GetViewCellsTree()->CollectLeaves(vc, leaves); 2056 2057 ViewCellContainer::const_iterator it, it_end = leaves.end(); 2028 2058 2029 2059 for (it = leaves.begin(); it != it_end; ++ it) 2030 ConstructGeometry(*it, vcGeom); 2060 { 2061 BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf; 2062 ConstructGeometry(l, vcGeom); 2063 } 2031 2064 } 2032 2065 … … 2456 2489 } 2457 2490 2491 2458 2492 BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed) 2459 2493 { … … 2499 2533 { 2500 2534 int collapsed = 0; 2501 2535 //TODO 2536 #if VC_HISTORY 2502 2537 (void)CollapseTree(mRoot, collapsed); 2503 2538 2504 2539 // revalidate leaves 2505 2540 RepairViewCellsLeafLists(); 2506 2541 #endif 2507 2542 return collapsed; 2508 2543 } … … 2527 2562 2528 2563 BspViewCell *viewCell = leaf->GetViewCell(); 2529 2564 // TODO 2565 #if VC_HISTORY 2530 2566 if (!viewCell->Mailed()) 2531 2567 { … … 2533 2569 viewCell->Mail(); 2534 2570 } 2535 2571 2536 2572 viewCell->mLeaves.push_back(leaf); 2573 // TODO 2574 #endif 2537 2575 } 2538 2576 else … … 2631 2669 2632 2670 2633 bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) //const2634 {2635 //-- change pointer to view cells of all leaves associated2636 //-- with the previous view cells2637 BspViewCell *fVc = l1->GetViewCell();2638 BspViewCell *bVc = l2->GetViewCell();2639 2640 BspViewCell *vc = dynamic_cast<BspViewCell *>(2641 mViewCellsManager->MergeViewCells(*fVc, *bVc));2642 2643 // if merge was unsuccessful2644 if (!vc) return false;2645 2646 // set new size of view cell2647 if (mUseAreaForPvs)2648 vc->SetArea(fVc->GetArea() + bVc->GetArea());2649 else2650 vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());2651 2652 vector<BspLeaf *> fLeaves = fVc->mLeaves;2653 vector<BspLeaf *> bLeaves = bVc->mLeaves;2654 2655 vector<BspLeaf *>::const_iterator it;2656 2657 //-- change view cells of all the other leaves the view cell belongs to2658 for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)2659 {2660 (*it)->SetViewCell(vc);2661 vc->mLeaves.push_back(*it);2662 }2663 2664 for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)2665 {2666 (*it)->SetViewCell(vc);2667 vc->mLeaves.push_back(*it);2668 }2669 2670 // important so other merge candidates sharing this view cell2671 // are notified that the merge cost must be updated!!2672 vc->Mail();2673 2674 //-- clean up old view cells2675 if (mExportMergedViewCells)2676 {2677 DEL_PTR(fVc);2678 DEL_PTR(bVc);2679 }2680 else2681 {2682 // old view cells container needed for visualization2683 //fVc->mMailbox = -1;2684 //bVc->mMailbox = -1;2685 fVc->SetId(-2);2686 bVc->SetId(-2);2687 2688 mOldViewCells.push_back(fVc);2689 mOldViewCells.push_back(bVc);2690 2691 mNewViewCells.push_back(vc);2692 }2693 2694 return true;2695 }2696 2697 2698 2671 void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm) 2699 2672 { … … 2702 2675 2703 2676 2704 int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves) 2677 int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves, 2678 vector<MergeCandidate> &candidates) 2705 2679 { 2706 2680 BspLeaf::NewMail(); … … 2708 2682 vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 2709 2683 2710 int candidates = 0;2684 int numCandidates = 0; 2711 2685 2712 2686 // find merge candidates and push them into queue … … 2714 2688 { 2715 2689 BspLeaf *leaf = *it; 2716 2717 /// create leaf pvs (needed for post processing)2718 leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());2719 2720 //const float rc = leaf->mProbability * (float)leaf->mPvs->GetSize();2721 //BspMergeCandidate::sOverallCost += rc;2722 2690 2723 2691 // the same leaves must not be part of two merge candidates … … 2733 2701 if ((*nit)->GetViewCell() != leaf->GetViewCell()) 2734 2702 { 2735 BspMergeCandidate mc(leaf, *nit); 2736 mc.EvalMergeCost(); 2737 2738 mMergeQueue.push(mc); 2739 ++ candidates; 2740 if ((candidates % 1000) == 0) 2703 MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell()); 2704 candidates.push_back(mc); 2705 2706 ++ numCandidates; 2707 if ((numCandidates % 1000) == 0) 2741 2708 { 2742 cout << "collected " << candidates << " merge candidates" << endl;2709 cout << "collected " << numCandidates << " merge candidates" << endl; 2743 2710 } 2744 2711 } … … 2746 2713 } 2747 2714 2748 Debug << "mergequeue: " << (int)mMergeQueue.size() << endl; 2749 Debug << "leaves in queue: " << candidates << endl; 2750 Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl; 2751 2715 Debug << "merge queue: " << (int)candidates.size() << endl; 2716 Debug << "leaves in queue: " << numCandidates << endl; 2717 2752 2718 2753 2719 return (int)leaves.size(); … … 2755 2721 2756 2722 2757 int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays) 2723 int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays, 2724 vector<MergeCandidate> &candidates) 2758 2725 { 2759 2726 ViewCell::NewMail(); … … 2775 2742 if (ray->mViewCells.size() < 2) 2776 2743 continue; 2777 2744 //TODO viewcellhierarchy 2778 2745 iit = ray->mViewCells.begin(); 2779 2746 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++)); 2780 BspLeaf *leaf = bspVc->mLeaves[0]; 2781 2782 // create leaf pvs (needed for post processing) 2783 if (!leaf->mPvs) 2784 { 2785 leaf->mPvs = 2786 new ObjectPvs(leaf->GetViewCell()->GetPvs()); 2787 2788 //BspMergeCandidate::sOverallCost += 2789 // leaf->mProbability * leaf->mPvs->GetSize(); 2790 2791 ++ numLeaves; 2792 } 2747 BspLeaf *leaf = bspVc->mLeaf; 2793 2748 2794 2749 // traverse intersections … … 2799 2754 BspLeaf *prevLeaf = leaf; 2800 2755 bspVc = dynamic_cast<BspViewCell *>(*iit); 2801 leaf = bspVc->mLea ves[0];2756 leaf = bspVc->mLeaf; 2802 2757 2803 2758 // view space not valid or same view cell … … 2806 2761 continue; 2807 2762 2808 // create leaf pvs (needed for post processing) 2809 if (!leaf->mPvs) 2810 { 2811 leaf->mPvs = 2812 new ObjectPvs(leaf->GetViewCell()->GetPvs()); 2813 2814 //BspMergeCandidate::sOverallCost += 2815 // leaf->mProbability * leaf->mPvs->GetSize(); 2816 2817 ++ numLeaves; 2818 } 2819 2820 vector<BspLeaf *> &neighbors = neighborMap[leaf]; 2763 vector<BspLeaf *> &neighbors = neighborMap[leaf]; 2821 2764 2822 2765 bool found = false; … … 2843 2786 prevLeaf->Mail(); 2844 2787 2845 BspMergeCandidate mc(leaf, prevLeaf); 2846 mc.EvalMergeCost(); 2847 2848 mMergeQueue.push(mc); 2849 2850 if (((int)mMergeQueue.size() % 1000) == 0) 2788 MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell()); 2789 2790 candidates.push_back(mc); 2791 2792 if (((int)candidates.size() % 1000) == 0) 2851 2793 { 2852 cout << "collected " << (int) mMergeQueue.size() << " merge candidates" << endl;2794 cout << "collected " << (int)candidates.size() << " merge candidates" << endl; 2853 2795 } 2854 2796 } … … 2857 2799 2858 2800 Debug << "neighbormap size: " << (int)neighborMap.size() << endl; 2859 Debug << "merge queue: " << (int)mMergeQueue.size() << endl;2801 Debug << "merge queue: " << (int)candidates.size() << endl; 2860 2802 Debug << "leaves in queue: " << numLeaves << endl; 2861 Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl; 2803 2862 2804 2863 2805 //-- collect the leaves which haven't been found by ray casting … … 2868 2810 CollectLeaves(leaves, true); 2869 2811 Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl; 2870 CollectMergeCandidates(leaves );2812 CollectMergeCandidates(leaves, candidates); 2871 2813 } 2872 2814 … … 2875 2817 2876 2818 2877 void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,2878 const VssRayContainer &rays)2879 {2880 VssRayContainer::const_iterator it, it_end = rays.end();2881 2882 for (it = rays.begin(); it != rays.end(); ++ it)2883 {2884 VssRay *vssRay = *it;2885 BspRay *ray = new BspRay(vssRay);2886 2887 ViewCellContainer viewCells;2888 2889 Ray hray(*vssRay);2890 float tmin = 0, tmax = 1.0;2891 // matt TODO: remove this!!2892 //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);2893 if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))2894 continue;2895 2896 Vector3 origin = hray.Extrap(tmin);2897 Vector3 termination = hray.Extrap(tmax);2898 2899 // cast line segment to get intersections with bsp leaves2900 CastLineSegment(origin, termination, viewCells);2901 2902 ViewCellContainer::const_iterator vit, vit_end = viewCells.end();2903 for (vit = viewCells.begin(); vit != vit_end; ++ vit)2904 {2905 BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);2906 vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();2907 //NOTE: not sorted!2908 for (it = vc->mLeaves.begin(); it != it_end; ++ it)2909 {2910 ray->intersections.push_back(BspIntersection(0, *it));2911 }2912 }2913 2914 bspRays.push_back(ray);2915 }2916 }2917 2918 2919 #if 12920 int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)2921 {2922 BspMergeCandidate::sViewCellsManager = mViewCellsManager;2923 BspMergeCandidate::sUseArea = mUseAreaForPvs;2924 2925 2926 //-- compute statistics values of initial view cells2927 mViewCellsManager->EvaluateRenderStatistics(BspMergeCandidate::sOverallCost,2928 BspMergeCandidate::sExpectedCost,2929 BspMergeCandidate::sVariance);2930 2931 2932 //BspMergeCandidate::sExpectedCost =2933 // BspMergeCandidate::sOverallCost / BspMergeCandidate::sNumViewCells;2934 2935 2936 ViewCellsManager::PvsStatistics pvsStats;2937 mViewCellsManager->GetPvsStatistics(pvsStats);2938 2939 static float expectedValue = pvsStats.avgPvs;2940 2941 // the current view cells are kept in this container2942 ViewCellContainer viewCells;2943 if (mExportMergedViewCells)2944 {2945 ViewCell::NewMail();2946 CollectViewCells(mRoot, true, viewCells, true);2947 }2948 2949 2950 ViewCell::NewMail();2951 2952 MergeStatistics mergeStats;2953 mergeStats.Start();2954 2955 long startTime = GetTime();2956 2957 cout << "collecting merge candidates ... " << endl;2958 2959 if (mUseRaysForMerge)2960 {2961 mergeStats.nodes = CollectMergeCandidates(rays);2962 }2963 else2964 {2965 vector<BspLeaf *> leaves;2966 CollectLeaves(leaves);2967 mergeStats.nodes = CollectMergeCandidates(leaves);2968 }2969 2970 cout << "fininshed collecting candidates" << endl;2971 2972 mergeStats.collectTime = TimeDiff(startTime, GetTime());2973 mergeStats.candidates = (int)mMergeQueue.size();2974 startTime = GetTime();2975 2976 // frequency stats are updated2977 const int statsOut = 100;2978 2979 // number of view cells withouth the invalid ones2980 BspMergeCandidate::sNumViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;2981 2982 // passes are needed for statistics, because we don't want to record2983 // every merge2984 const int maxMergesPerPass = 100;2985 int pass = 0;2986 2987 // maximal ratio of old expected render cost to expected render2988 // when the the render queue has to be reset.2989 const float ercMaxRatio = 0.7f;2990 2991 cout << "actual merge starts now ... " << endl;2992 2993 2994 2995 //-- use priority queue to merge leaf pairs2996 2997 2998 while (!mMergeQueue.empty() &&2999 (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&3000 (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))3001 {3002 3003 int mergedPerPass = 0;3004 const float oldExpectedCost = BspMergeCandidate::sExpectedCost;3005 3006 //#ifdef _DEBUG3007 Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "3008 << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost3009 << " max ratio: " << mMergeMaxCostRatio << endl3010 << " expected value: " << oldExpectedCost << endl;3011 //#endif3012 3013 while (!mMergeQueue.empty() &&3014 (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&3015 (ercMaxRatio > oldExpectedCost / BspMergeCandidate::sExpectedCost) &&3016 (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost) &&3017 (maxMergesPerPass < mergedPerPass));3018 {3019 Debug << "erc max ratio" << ercMaxRatio << endl;3020 3021 BspMergeCandidate mc = mMergeQueue.top();3022 mMergeQueue.pop();3023 3024 // both view cells equal!3025 if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())3026 continue;3027 3028 if (mc.Valid())3029 {3030 ViewCell::NewMail();3031 const float currentMergeCost = mc.GetMergeCost();3032 3033 MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());3034 3035 -- BspMergeCandidate::sNumViewCells;3036 ++ mergeStats.merged;3037 ++ mergedPerPass;3038 3039 // increase absolute merge cost3040 BspMergeCandidate::sOverallCost += mc.GetRenderCost();3041 BspMergeCandidate::sVariance = mc.GetVarianceIncr();3042 3043 BspMergeCandidate::sExpectedCost =3044 BspMergeCandidate::sOverallCost / (float)BspMergeCandidate::sNumViewCells;3045 3046 // stats3047 if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))3048 ++ mergeStats.siblings;3049 3050 if (0)3051 {3052 const int dist =3053 TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());3054 if (dist > mergeStats.maxTreeDist)3055 mergeStats.maxTreeDist = dist;3056 mergeStats.accTreeDist += dist;3057 }3058 3059 if ((mergeStats.merged % statsOut) == 0)3060 {3061 cout << "merged " << mergeStats.merged << " view cells" << endl;3062 3063 mStats3064 << "#Pass\n" << pass << endl3065 << "#Merged\n" << mergeStats.merged << endl3066 << "#Viewcells\n" << BspMergeCandidate::sNumViewCells << endl3067 << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl3068 << "#CurrentCost\n" << currentMergeCost << endl3069 << "#RelativeCost\n" << currentMergeCost / BspMergeCandidate::sOverallCost << endl3070 << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl3071 << "#MergedSiblings\n" << mergeStats.siblings << endl3072 << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl3073 << "#ExpectedCost\n" << BspMergeCandidate::sExpectedCost << endl3074 << "#RatioExpectedCost\n" << oldExpectedCost / BspMergeCandidate::sExpectedCost << endl3075 << "#variance\n" << BspMergeCandidate::sVariance << endl;3076 3077 if (mExportMergedViewCells)3078 ExportMergedViewCells(viewCells, objects, BspMergeCandidate::sNumViewCells);3079 }3080 }3081 else3082 {3083 3084 // merge candidate not valid, because one of the leaves was already3085 // merged with another one => validate and reinsert into queue3086 mc.SetValid();3087 mMergeQueue.push(mc);3088 }3089 }3090 3091 3092 ++ pass;3093 }3094 3095 mergeStats.overallCost = BspMergeCandidate::sOverallCost;3096 3097 mergeStats.mergeTime = TimeDiff(startTime, GetTime());3098 mergeStats.Stop();3099 3100 Debug << mergeStats << endl << endl;3101 3102 // delete the view cells which were already merged3103 CLEAR_CONTAINER(mOldViewCells);3104 3105 3106 //TODO: should return sample contributions?3107 return mergeStats.merged;3108 }3109 3110 #else3111 3112 int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)3113 {3114 BspMergeCandidate::sViewCellsManager = mViewCellsManager;3115 BspMergeCandidate::sUseArea = mUseAreaForPvs;3116 3117 ViewCellsManager::PvsStatistics pvsStats;3118 mViewCellsManager->GetPvsStatistics(pvsStats);3119 3120 static float expectedValue = pvsStats.avgPvs;3121 // the current view cells are kept in this container3122 ViewCellContainer viewCells;3123 if (mExportMergedViewCells)3124 {3125 ViewCell::NewMail();3126 CollectViewCells(mRoot, true, viewCells, true);3127 }3128 ViewCell::NewMail();3129 3130 MergeStatistics mergeStats;3131 mergeStats.Start();3132 3133 //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mBspStats.maxPvs;3134 long startTime = GetTime();3135 3136 cout << "collecting merge candidates ... " << endl;3137 3138 if (mUseRaysForMerge)3139 {3140 mergeStats.nodes = CollectMergeCandidates(rays);3141 }3142 else3143 {3144 vector<BspLeaf *> leaves;3145 CollectLeaves(leaves);3146 mergeStats.nodes = CollectMergeCandidates(leaves);3147 }3148 3149 cout << "fininshed collecting candidates" << endl;3150 3151 mergeStats.collectTime = TimeDiff(startTime, GetTime());3152 mergeStats.candidates = (int)mMergeQueue.size();3153 startTime = GetTime();3154 3155 3156 // number of view cells withouth the invalid ones3157 int nViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;3158 BspMergeCandidate::sExpectedCost = BspMergeCandidate::sOverallCost / (float)nViewCells;3159 3160 // passes are needed for statistics, because we don't want to record3161 // every merge3162 const int mergesPerPass = 100;3163 3164 int nextPass = 0;3165 int pass = 0;3166 3167 3168 Debug << "stats: " << nextStats << " " << statsIncr << endl;3169 cout << "actual merge starts now ... " << endl;3170 3171 //-- use priority queue to merge leaf pairs3172 while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&3173 (mMergeQueue.top().GetMergeCost() <3174 mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))3175 {3176 #ifdef _DEBUG3177 Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "3178 << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost3179 << " max ratio: " << mMergeMaxCostRatio << endl;3180 #endif3181 3182 BspMergeCandidate mc = mMergeQueue.top();3183 mMergeQueue.pop();3184 3185 3186 // both view cells equal!3187 if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())3188 continue;3189 3190 if (mc.Valid())3191 {3192 ViewCell::NewMail();3193 const float mergeCost = mc.GetMergeCost();3194 3195 MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());3196 3197 // increase absolute merge cost3198 BspMergeCandidate::sOverallCost += mc.GetMergeCost();3199 3200 3201 -- nViewCells;3202 ++ mergeStats.merged;3203 3204 if ((mergeStats.merged % 500) == 0)3205 cout << "merged " << mergeStats.merged << " view cells" << endl;3206 3207 // stats and visualizations3208 if (mExportMergeStats)3209 {3210 if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))3211 ++ mergeStats.siblings;3212 3213 if (0)3214 const int dist =3215 TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());3216 if (dist > mergeStats.maxTreeDist)3217 mergeStats.maxTreeDist = dist;3218 mergeStats.accTreeDist += dist;3219 3220 if ((mergeStats.merged == nextPass) || (nViewCells == mMergeMinViewCells))3221 {3222 nextPass += mergesPerPass;3223 3224 mStats3225 << "#Pass\n" << pass ++ << endl3226 << "#Merged\n" << mergeStats.merged << endl3227 << "#Viewcells\n" << nViewCells << endl3228 << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl3229 << "#CurrentCost\n" << mergeCost << endl3230 << "#RelativeCost\n" << mergeCost / BspMergeCandidate::sOverallCost << endl3231 << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl3232 << "#MergedSiblings\n" << mergeStats.siblings << endl3233 << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl;3234 3235 if (mExportMergedViewCells)3236 ExportMergedViewCells(viewCells, objects, nViewCells);3237 }3238 }3239 }3240 // merge candidate not valid, because one of the leaves was already3241 // merged with another one => validate and reinsert into queue3242 else3243 {3244 mc.SetValid();3245 mMergeQueue.push(mc);3246 }3247 }3248 3249 mergeStats.overallCost = BspMergeCandidate::sOverallCost;3250 3251 mergeStats.mergeTime = TimeDiff(startTime, GetTime());3252 mergeStats.Stop();3253 3254 Debug << mergeStats << endl << endl;3255 3256 // delete the view cells which were already merged3257 CLEAR_CONTAINER(mOldViewCells);3258 3259 3260 //TODO: should return sample contributions?3261 return mergeStats.merged;3262 }3263 #endif3264 2819 3265 2820 … … 3297 2852 3298 2853 3299 void VspBspTree::ExportMergedViewCells(ViewCellContainer &viewCells,3300 const ObjectContainer &objects,3301 const int nViewCells)3302 {3303 ViewCellContainer::const_iterator vit, vit_end = viewCells.end();3304 3305 // find all already merged view cells and remove them from view cells3306 int i = 0;3307 3308 while (1)3309 {3310 //while (!viewCells.empty() && (viewCells.back()->mMailbox == -1))3311 while (!viewCells.empty() && (viewCells.back()->GetId() == -2))3312 {3313 //DEL_PTR(viewCells.back());3314 viewCells.pop_back();3315 }3316 // all merged view cells have been found3317 if (i >= viewCells.size())3318 break;3319 3320 // already merged view cell, put it to end of vector3321 //if (viewCells[i]->mMailbox == -1)3322 if (viewCells[i]->GetId() == -2)3323 swap(viewCells[i], viewCells.back());3324 3325 ++ i;3326 }3327 3328 int newVcSize = 0;3329 // add new view cells to container only if they don't have been3330 // merged in the mean time3331 while (!mNewViewCells.empty())3332 {3333 if (mNewViewCells.back()->GetId() != -2)3334 {3335 viewCells.push_back(mNewViewCells.back());3336 ++ newVcSize;3337 }3338 3339 mNewViewCells.pop_back();3340 }3341 3342 char s[64];3343 sprintf(s, "merged_viewcells%07d.x3d", nViewCells);3344 Exporter *exporter = Exporter::GetExporter(s);3345 3346 if (exporter)3347 {3348 cout << "exporting " << nViewCells << " merged view cells ... ";3349 exporter->ExportGeometry(objects);3350 //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;3351 ViewCellContainer::const_iterator it, it_end = viewCells.end();3352 3353 int i = 0;3354 for (it = viewCells.begin(); it != it_end; ++ it)3355 {3356 Material m;3357 // assign special material to new view cells3358 // new view cells are on the back of container3359 if (i ++ >= (viewCells.size() - newVcSize))3360 {3361 //m = RandomMaterial();3362 m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);3363 m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);3364 m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);3365 }3366 else3367 {3368 float col = RandomValue(0.1f, 0.4f);3369 m.mDiffuseColor.r = col;3370 m.mDiffuseColor.g = col;3371 m.mDiffuseColor.b = col;3372 }3373 3374 exporter->SetForcedMaterial(m);3375 mViewCellsManager->ExportVcGeometry(exporter, *it);3376 }3377 delete exporter;3378 cout << "finished" << endl;3379 }3380 3381 // delete the view cells which were merged3382 CLEAR_CONTAINER(mOldViewCells);3383 // remove the new view cells3384 mNewViewCells.clear();3385 }3386 3387 3388 int VspBspTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)3389 {3390 Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;3391 3392 BspLeaf::NewMail();3393 3394 // Use priority queue of remaining leaf pairs3395 // The candidates either share the same view cells or3396 // are border leaves which share a boundary.3397 // We test if they can be shuffled, i.e.,3398 // either one leaf is made part of one view cell or the other3399 // leaf is made part of the other view cell. It is tested if the3400 // remaining view cells are "better" than the old ones.3401 //3402 // repeat the merging test numPasses times. For example, it could be3403 // that a shuffle only makes sense if another pair was shuffled before.3404 // Therefore we keep two queues and shift the merge candidates between3405 // those two queues until numPasses is reached3406 3407 queue<BspMergeCandidate> queue1;3408 queue<BspMergeCandidate> queue2;3409 3410 queue<BspMergeCandidate> *shuffleQueue = &queue1;3411 queue<BspMergeCandidate> *backQueue = &queue2;3412 3413 while (!mMergeQueue.empty())3414 {3415 BspMergeCandidate mc = mMergeQueue.top();3416 shuffleQueue->push(mc);3417 mMergeQueue.pop();3418 }3419 3420 const int numPasses = 5;3421 int pass = 0;3422 int passShuffled = 0;3423 int shuffled = 0;3424 3425 BspLeaf::NewMail();3426 3427 do3428 {3429 passShuffled = 0;3430 while (!shuffleQueue->empty())3431 {3432 BspMergeCandidate mc = shuffleQueue->front();3433 shuffleQueue->pop();3434 3435 // both view cells equal or already shuffled3436 if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()))// ||3437 // (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))3438 continue;3439 3440 // candidate for shuffling3441 const bool wasShuffled =3442 ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());3443 3444 if (wasShuffled)3445 ++ passShuffled;3446 else3447 backQueue->push(mc);3448 }3449 3450 // now the back queue is the current shuffle queue3451 swap(shuffleQueue, backQueue);3452 shuffled += passShuffled;3453 Debug << "shuffled in pass: " << passShuffled << endl;3454 }3455 while (((++ pass) < numPasses) && passShuffled);3456 3457 while (!shuffleQueue->empty())3458 {3459 shuffleQueue->pop();3460 }3461 3462 return shuffled;3463 }3464 3465 3466 inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)3467 {3468 return pvs1.AddPvs(pvs2);3469 }3470 3471 3472 // recomputes pvs size minus pvs of leaf l3473 #if 03474 inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)3475 {3476 ObjectPvs pvs;3477 vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();3478 for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)3479 if (*it != l)3480 pvs.AddPvs(*(*it)->mPvs);3481 return pvs.GetSize();3482 }3483 #endif3484 3485 // computes pvs1 minus pvs23486 inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)3487 {3488 return pvs1.SubtractPvs(pvs2);3489 }3490 3491 3492 float VspBspTree::GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const3493 {3494 //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);3495 const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);3496 const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);3497 3498 // don't shuffle leaves with pvs > max3499 if (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize())3500 return 1e15f;3501 3502 #if 13503 float p1, p2;3504 3505 if (mUseAreaForPvs)3506 {3507 p1 = vc1->GetArea() - leaf->mProbability;3508 p2 = vc2->GetArea() + leaf->mProbability;3509 }3510 else3511 {3512 p1 = vc1->GetVolume() - leaf->mProbability;3513 p2 = vc2->GetVolume() + leaf->mProbability;3514 }3515 3516 const float cost1 = pvs1 * p1;3517 const float cost2 = pvs2 * p2;3518 #else3519 const float cost1 = pvs1;3520 const float cost2 = pvs2;3521 #endif3522 3523 return cost1 + cost2;3524 }3525 3526 3527 void VspBspTree::ShuffleLeaf(BspLeaf *leaf,3528 BspViewCell *vc1,3529 BspViewCell *vc2) const3530 {3531 // compute new pvs and area3532 vc1->GetPvs().SubtractPvs(*leaf->mPvs);3533 vc2->GetPvs().AddPvs(*leaf->mPvs);3534 3535 if (mUseAreaForPvs)3536 {3537 vc1->SetArea(vc1->GetArea() - leaf->mProbability);3538 vc2->SetArea(vc2->GetArea() + leaf->mProbability);3539 }3540 else3541 {3542 vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);3543 vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);3544 }3545 3546 /// add to second view cell3547 vc2->mLeaves.push_back(leaf);3548 3549 // erase leaf from old view cell3550 vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();3551 3552 for (; *it != leaf; ++ it);3553 vc1->mLeaves.erase(it);3554 3555 /*vc1->GetPvs().mEntries.clear();3556 for (; it != vc1->mLeaves.end(); ++ it)3557 {3558 if (*it == leaf)3559 vc1->mLeaves.erase(it);3560 else3561 vc1->GetPvs().AddPvs(*(*it)->mPvs);3562 }*/3563 3564 leaf->SetViewCell(vc2); // finally change view cell3565 }3566 3567 3568 bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const3569 {3570 BspViewCell *vc1 = leaf1->GetViewCell();3571 BspViewCell *vc2 = leaf2->GetViewCell();3572 3573 float cost1, cost2;3574 3575 #if 13576 if (mUseAreaForPvs)3577 {3578 cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();3579 cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();3580 }3581 else3582 {3583 cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();3584 cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();3585 }3586 #else3587 cost1 = vc1->GetPvs().GetSize();3588 cost2 = vc2->GetPvs().GetSize();3589 #endif3590 3591 const float oldCost = cost1 + cost2;3592 3593 float shuffledCost1 = Limits::Infinity;3594 float shuffledCost2 = Limits::Infinity;3595 3596 // the view cell should not be empty after the shuffle3597 if (vc1->mLeaves.size() > 1)3598 shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);3599 if (vc2->mLeaves.size() > 1)3600 shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);3601 3602 // shuffling unsuccessful3603 if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))3604 return false;3605 3606 if (shuffledCost1 < shuffledCost2)3607 {3608 ShuffleLeaf(leaf1, vc1, vc2);3609 leaf1->Mail();3610 }3611 else3612 {3613 ShuffleLeaf(leaf2, vc2, vc1);3614 leaf2->Mail();3615 }3616 3617 return true;3618 }3619 3620 3621 2854 bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const 3622 2855 { … … 3713 2946 } 3714 2947 } 3715 3716 3717 /**************************************************************************/3718 /* BspMergeCandidate implementation */3719 /**************************************************************************/3720 3721 3722 BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):3723 mRenderCost(0),3724 mVarianceIncr(0),3725 mLeaf1(l1),3726 mLeaf2(l2),3727 mLeaf1Id(l1->GetViewCell()->mMailbox),3728 mLeaf2Id(l2->GetViewCell()->mMailbox)3729 {3730 //EvalMergeCost();3731 }3732 3733 3734 float BspMergeCandidate::GetRenderCost(ViewCell *vc) const3735 {3736 if (sUseArea)3737 return vc->GetPvs().GetSize() * vc->GetArea();3738 3739 return vc->GetPvs().GetSize() * vc->GetVolume();3740 }3741 3742 3743 float BspMergeCandidate::GetLeaf1Cost() const3744 {3745 BspViewCell *vc = mLeaf1->GetViewCell();3746 3747 return GetRenderCost(vc);3748 }3749 3750 3751 float BspMergeCandidate::GetLeaf2Cost() const3752 {3753 BspViewCell *vc = mLeaf2->GetViewCell();3754 3755 return GetRenderCost(vc);3756 }3757 3758 3759 int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)3760 {3761 int pvs = pvs1.GetSize();3762 3763 // compute new pvs size3764 ObjectPvsMap::const_iterator it, it_end = pvs1.mEntries.end();3765 3766 Intersectable::NewMail();3767 3768 for (it = pvs1.mEntries.begin(); it != it_end; ++ it)3769 {3770 (*it).first->Mail();3771 }3772 3773 it_end = pvs2.mEntries.end();3774 3775 for (it = pvs2.mEntries.begin(); it != it_end; ++ it)3776 {3777 Intersectable *obj = (*it).first;3778 if (!obj->Mailed())3779 ++ pvs;3780 }3781 3782 return pvs;3783 }3784 3785 3786 3787 void BspMergeCandidate::EvalMergeCost()3788 {3789 //-- compute pvs difference3790 BspViewCell *vc1 = mLeaf1->GetViewCell();3791 BspViewCell *vc2 = mLeaf2->GetViewCell();3792 3793 const int newPvs = ComputeMergedPvsSize(vc1->GetPvs(), vc2->GetPvs());3794 const float newPenalty =3795 EvalPvsPenalty(newPvs,3796 sViewCellsManager->GetMinPvsSize(),3797 sViewCellsManager->GetMaxPvsSize());3798 3799 //-- compute ratio of old cost3800 // (i.e., added size of left and right view cell times pvs size)3801 // to new rendering cost (i.e, size of merged view cell times pvs size)3802 const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();3803 3804 const float newCost = sUseArea ?3805 (float)newPvs * (vc1->GetArea() + vc2->GetArea()) :3806 (float)newPvs * (vc1->GetVolume() + vc2->GetVolume());3807 3808 3809 if (newPvs > sViewCellsManager->GetMaxPvsSize()) // strong penalty if pvs size too large3810 {3811 mRenderCost = 1e15;3812 }3813 else3814 {3815 mRenderCost = newCost - oldCost;3816 }3817 3818 // merge cost also takes variance into account3819 3820 const float oldVar1 = GetLeaf1Variance();3821 const float oldVar2 = GetLeaf2Variance();3822 3823 const float newVar = (sExpectedCost - mRenderCost) * (sExpectedCost - mRenderCost);3824 3825 mVarianceIncr = (newVar - oldVar1 - oldVar2) / sNumViewCells;3826 //mMergeCost = mRenderCost + fabs(newPenalty - BspMergeCandidate::sExpectedCost) ;3827 }3828 3829 3830 void BspMergeCandidate::SetLeaf1(BspLeaf *l)3831 {3832 mLeaf1 = l;3833 }3834 3835 3836 void BspMergeCandidate::SetLeaf2(BspLeaf *l)3837 {3838 mLeaf2 = l;3839 }3840 3841 3842 BspLeaf *BspMergeCandidate::GetLeaf1() const3843 {3844 return mLeaf1;3845 }3846 3847 3848 BspLeaf *BspMergeCandidate::GetLeaf2() const3849 {3850 return mLeaf2;3851 }3852 3853 3854 bool BspMergeCandidate::Valid() const3855 {3856 return3857 (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&3858 (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);3859 }3860 3861 3862 float BspMergeCandidate::GetMergeCost() const3863 {3864 return mRenderCost * sRenderCostWeight + mVarianceIncr * (1.0f - sRenderCostWeight);3865 }3866 3867 3868 float BspMergeCandidate::GetRenderCost() const3869 {3870 return mRenderCost;3871 }3872 3873 3874 float BspMergeCandidate::GetVarianceIncr() const3875 {3876 return mVarianceIncr;3877 }3878 3879 float BspMergeCandidate::GetLeaf1Variance() const3880 {3881 const float leafCost = GetLeaf1Cost();3882 3883 return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);3884 }3885 3886 3887 float BspMergeCandidate::GetLeaf2Variance() const3888 {3889 const float leafCost = GetLeaf2Cost();3890 3891 return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);3892 }3893 3894 3895 void BspMergeCandidate::SetValid()3896 {3897 mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;3898 mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;3899 3900 EvalMergeCost();3901 }3902 3903 3904 /************************************************************************/3905 /* MergeStatistics implementation */3906 /************************************************************************/3907 3908 3909 void MergeStatistics::Print(ostream &app) const3910 {3911 app << "===== Merge statistics ===============\n";3912 3913 app << setprecision(4);3914 3915 app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";3916 3917 app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";3918 3919 app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";3920 3921 app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";3922 3923 app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";3924 3925 app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";3926 3927 app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";3928 3929 app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";3930 3931 app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";3932 3933 app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";3934 3935 app << "===== END OF BspTree statistics ==========\n";3936 } -
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h
r579 r580 21 21 class ViewCellsStatistics; 22 22 class ViewCellsManager; 23 class BspMergeCandidate;23 class MergeCandidate; 24 24 class Beam; 25 25 … … 252 252 int TreeDistance(BspNode *n1, BspNode *n2) const; 253 253 254 /** Merges view cells according to some cost heuristics.255 */256 int MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects);257 258 /** Refines view cells using shuffling, i.e., border leaves259 of two view cells are exchanged if the resulting view cells260 are tested to be "better" than the old ones.261 @returns number of refined view cells262 */263 int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);264 265 254 /** Collapses the tree with respect to the view cell partition. 266 255 @returns number of collapsed nodes … … 272 261 ViewCell *GetViewCell(const Vector3 &point); 273 262 274 /** Constructs bsp rays for post processing and visualization.275 */276 void ConstructBspRays(vector<BspRay *> &bspRays,277 const VssRayContainer &rays);278 279 /** Merge view cells of leaves l1 and l2.280 */281 bool MergeViewCells(BspLeaf *l1, BspLeaf *l2); //const;282 263 283 264 /** Returns true if this view point is in a valid view space, … … 369 350 BspNode *CollapseTree(BspNode *node, int &collapsed); 370 351 371 /** Shuffles the leaves, i.e., tests if exchanging372 the leaves helps in improving the view cells.373 */374 bool ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const;375 376 352 /** Helper function revalidating the view cell leaf list after merge. 377 353 */ … … 573 549 574 550 575 /** Collects candidates for the merge in the merge queue. 576 @param leaves the leaves to be merged 577 @returns number of leaves in queue 578 */ 579 int CollectMergeCandidates(const vector<BspLeaf *> leaves); 580 /** Collects candidates for the merge in the merge queue. 581 @returns number of leaves in queue 582 */ 583 int CollectMergeCandidates(const VssRayContainer &rays); 584 551 552 553 554 585 555 /** Take 3 ray endpoints, where two are minimum and one a maximum 586 556 point or the other way round. … … 599 569 Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const; 600 570 601 /** Shuffles, i.e. takes border leaf from view cell 1 and adds it 602 to view cell 2. 603 */ 604 void ShuffleLeaf(BspLeaf *leaf, 605 BspViewCell *vc1, 606 BspViewCell *vc2) const; 607 571 /** Collects candidates for merging. 572 @param leaves the leaves to be merged 573 @returns number of leaves in queue 574 */ 575 int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates); 576 577 /** Collects candidates for the merge in the merge queue. 578 @returns number of leaves in queue 579 */ 580 int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates); 581 582 608 583 609 584 /** Propagates valid flag up the tree. … … 620 595 float GetMemUsage() const; 621 596 622 /** Calculates cost for merge of view cell 1 and 2. 623 */ 624 float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const; 625 626 void ExportMergedViewCells(ViewCellContainer &viewCells, 627 const ObjectContainer &objects, 628 const int nViewCells); 597 629 598 630 599 /// Pointer to the root of the tree … … 658 627 float mTermMinAccRayLength; 659 628 660 ofstream mStats;629 661 630 662 631 //-- termination criteria for axis aligned split … … 701 670 /// maximal number of view cells 702 671 int mMaxViewCells; 703 /// minimal number of view cells 704 int mMergeMinViewCells; 705 /// maximal cost ratio for the merge 706 float mMergeMaxCostRatio; 672 707 673 708 674 // if rays should be stored in leaves … … 716 682 vector<SortableEntry> *mSplitCandidates; 717 683 718 719 typedef priority_queue<BspMergeCandidate> MergeQueue; 720 721 MergeQueue mMergeQueue; 722 723 /// if rays should be used to collect merge candidates 724 bool mUseRaysForMerge; 725 684 685 float mRenderCostWeight; 726 686 /// View cell corresponding to the space outside the valid view space 727 687 BspViewCell *mOutOfBoundsCell; 728 729 int mCurrentViewCellsId;730 688 731 689 /// maximal tree memory … … 733 691 /// the tree is out of memory 734 692 bool mOutOfMemory; 735 /// if merge visualization should be shown 736 bool mExportMergedViewCells; 737 /// if merge statistics should be exported 738 bool mExportMergeStats; 739 693 694 740 695 private: 741 742 ViewCellContainer mOldViewCells; 743 ViewCellContainer mNewViewCells; 696 744 697 745 698 static const float sLeastRaySplitsTable[5]; … … 758 711 }; 759 712 760 /** 761 Candidate for leaf merging based on priority. 762 */ 763 class BspMergeCandidate 764 { 765 friend class VspBspTree; 766 767 public: 768 769 BspMergeCandidate(BspLeaf *l1, BspLeaf *l2); 770 771 /** If this merge pair is still valid. 772 */ 773 bool Valid() const; 774 775 /** Sets this merge candidate to be valid. 776 */ 777 void SetValid(); 778 779 friend bool operator<(const BspMergeCandidate &leafa, const BspMergeCandidate &leafb) 780 { 781 return leafb.GetMergeCost() < leafa.GetMergeCost(); 782 } 783 784 void SetLeaf1(BspLeaf *l); 785 void SetLeaf2(BspLeaf *l); 786 787 BspLeaf *GetLeaf1() const; 788 BspLeaf *GetLeaf2() const; 789 790 /** Merge cost of this candidate pair. 791 */ 792 float GetMergeCost() const; 793 794 /** Render cost of this candidate. 795 */ 796 float GetRenderCost() const; 797 798 /** returns increase in variance of this view cell. 799 */ 800 float GetVarianceIncr() const; 801 802 /** Returns cost of leaf 1. 803 */ 804 float GetLeaf1Cost() const; 805 806 /** Returns cost of leaf 2. 807 */ 808 float GetLeaf2Cost() const; 809 810 /** Variance of leaf1 811 */ 812 float GetLeaf1Variance() const; 813 814 /** Variance of leaf2 815 */ 816 float GetLeaf2Variance() const; 817 818 /// overall cost used to normalize cost ratio 819 static float sOverallCost; 820 static float sExpectedCost; 821 static float sVariance; 822 823 static int sNumViewCells; 824 825 // weights between variance and render cost increase (must between zero and one) 826 static float sRenderCostWeight; 827 828 /// if area or volume should be used for the merge heuristics 829 static bool sUseArea; 830 831 /// pointer to view cells manager 832 static ViewCellsManager *sViewCellsManager; 833 834 protected: 835 836 837 /** Evaluates the merge costs of the leaves. 838 */ 839 void EvalMergeCost(); 840 841 /** render cost of a view cell. 842 */ 843 float GetRenderCost(ViewCell *vc) const; 844 845 int mLeaf1Id; 846 int mLeaf2Id; 847 848 /// render cost increase by this merge 849 float mRenderCost; 850 /// increase / decrease of variance 851 float mVarianceIncr; 852 853 BspLeaf *mLeaf1; 854 BspLeaf *mLeaf2; 855 }; 856 857 858 class MergeStatistics: public StatisticsBase 859 { 860 public: 861 862 int merged; 863 int siblings; 864 int candidates; 865 int nodes; 866 867 int accTreeDist; 868 int maxTreeDist; 869 870 Real collectTime; 871 Real mergeTime; 872 873 Real overallCost; 874 875 // Constructor 876 MergeStatistics() 877 { 878 Reset(); 879 } 880 881 double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 882 883 void Reset() 884 { 885 nodes = 0; 886 merged = 0; 887 siblings = 0; 888 candidates = 0; 889 890 accTreeDist = 0; 891 maxTreeDist = 0; 892 893 collectTime = 0; 894 mergeTime = 0; 895 overallCost = 0; 896 } 897 898 void Print(ostream &app) const; 899 900 friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 901 { 902 stat.Print(s); 903 return s; 904 } 905 }; 713 714 906 715 907 716 #endif -
trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
r556 r580 30 30 // Static variables 31 31 int VspKdLeaf::sMailId = 0; 32 int MergeCandidate::sMaxPvsSize = 150;33 float MergeCandidate::sOverallCost = Limits::Small;32 int VspKdMergeCandidate::sMaxPvsSize = 150; 33 float VspKdMergeCandidate::sOverallCost = Limits::Small; 34 34 #define USE_FIXEDPOINT_T 0 35 35 … … 430 430 environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 431 431 environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize", 432 MergeCandidate::sMaxPvsSize);432 VspKdMergeCandidate::sMaxPvsSize); 433 433 434 434 environment->GetBoolValue("VspKdTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis); … … 2173 2173 vc->SetArea(GetBBox(leaf).SurfaceArea()); 2174 2174 2175 vc->mLea ves.push_back(leaf);2175 vc->mLeaf = leaf; 2176 2176 2177 2177 for (it = leaf->GetRays().begin(); it != it_end; ++ it) … … 2200 2200 // if merge was unsuccessful 2201 2201 if (!vc) return false; 2202 2202 // TODO 2203 #if VC_HISTORY 2203 2204 // set new size of view cell 2204 2205 vc->SetVolume(fVc->GetVolume() + bVc->GetVolume()); … … 2223 2224 vc->mLeaves.push_back(*it); 2224 2225 } 2225 2226 #endif 2226 2227 vc->Mail(); 2227 2228 … … 2235 2236 void VspKdTree::CollectMergeCandidates() 2236 2237 { 2237 MergeCandidate::sOverallCost = 0;2238 VspKdMergeCandidate::sOverallCost = 0; 2238 2239 vector<VspKdLeaf *> leaves; 2239 2240 … … 2256 2257 // no leaf is part of two merge candidates 2257 2258 leaf->Mail(); 2258 MergeCandidate::sOverallCost +=2259 VspKdMergeCandidate::sOverallCost += 2259 2260 vc->GetVolume() * vc->GetPvs().GetSize(); 2260 2261 vector<VspKdLeaf *> neighbors; … … 2266 2267 for (nit = neighbors.begin(); nit != nit_end; ++ nit) 2267 2268 { 2268 mMergeQueue.push( MergeCandidate(leaf, *nit));2269 mMergeQueue.push(VspKdMergeCandidate(leaf, *nit)); 2269 2270 } 2270 2271 } … … 2273 2274 void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays) 2274 2275 { 2275 MergeCandidate::sOverallCost = 0;2276 VspKdMergeCandidate::sOverallCost = 0; 2276 2277 2277 2278 vector<VspKdIntersection>::const_iterator iit; … … 2299 2300 leaf->Mail 2300 2301 // TODO: how to sort out doubles? 2301 MergeCandidate mc =MergeCandidate(leaf, previousLeaf);2302 VspKdMergeCandidate mc = VspKdMergeCandidate(leaf, previousLeaf); 2302 2303 mMergeQueue.push(mc); 2303 2304 2304 MergeCandidate::sOverallCost += mc.GetLeaf1Cost();2305 MergeCandidate::sOverallCost += mc.GetLeaf2Cost();2305 VspKdMergeCandidate::sOverallCost += mc.GetLeaf1Cost(); 2306 VspKdMergeCandidate::sOverallCost += mc.GetLeaf2Cost(); 2306 2307 2307 2308 previousLeaf = leaf; … … 2321 2322 while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) && 2322 2323 (mMergeQueue.top().GetMergeCost() < 2323 mMergeMaxCostRatio * MergeCandidate::sOverallCost))2324 mMergeMaxCostRatio * VspKdMergeCandidate::sOverallCost)) 2324 2325 { 2325 2326 //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / 2326 // MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;2327 MergeCandidate mc = mMergeQueue.top();2327 //VspKdMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 2328 VspKdMergeCandidate mc = mMergeQueue.top(); 2328 2329 mMergeQueue.pop(); 2329 2330 … … 2340 2341 -- vcSize; 2341 2342 // increase absolute merge cost 2342 MergeCandidate::sOverallCost += mc.GetMergeCost();2343 VspKdMergeCandidate::sOverallCost += mc.GetMergeCost(); 2343 2344 } 2344 2345 // merge candidate not valid, because one of the leaves was already … … 2378 2379 2379 2380 VspKdViewCell *viewCell = leaf->GetViewCell(); 2380 2381 #if VC_HISTORY 2381 2382 if (!viewCell->Mailed()) 2382 2383 { … … 2386 2387 2387 2388 viewCell->mLeaves.push_back(leaf); 2389 #endif 2388 2390 } 2389 2391 else … … 2468 2470 while (!mMergeQueue.empty()) 2469 2471 { 2470 MergeCandidate mc = mMergeQueue.top();2472 VspKdMergeCandidate mc = mMergeQueue.top(); 2471 2473 mMergeQueue.pop(); 2472 2474 … … 2501 2503 2502 2504 2503 float GetShuffledVcCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2)2505 float EvalShuffleCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2) 2504 2506 { 2505 2507 const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs); … … 2521 2523 { 2522 2524 // compute new pvs and area 2525 // TODO 2526 #if VC_HISTORY 2523 2527 vc1->GetPvs().SubtractPvs(*leaf->mPvs); 2524 2528 vc2->GetPvs().AddPvs(*leaf->mPvs); … … 2537 2541 2538 2542 leaf->SetViewCell(vc2); // finally change view cell 2543 #endif 2539 2544 } 2540 2545 … … 2554 2559 2555 2560 // the view cell should not be empty after the shuffle 2556 if (vc1->mLeaves.size() > 1) 2557 shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2); 2561 //todo 2562 /* if (vc1->mLeaves.size() > 1) 2563 shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2); 2558 2564 if (vc2->mLeaves.size() > 1) 2559 shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);2560 2561 // shuffling unsuccessful2565 shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1); 2566 2567 */ // shuffling unsuccessful 2562 2568 if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2)) 2563 2569 return false; … … 2581 2587 2582 2588 /*********************************************************************/ 2583 /* MergeCandidate implementation */2589 /* VspKdMergeCandidate implementation */ 2584 2590 /*********************************************************************/ 2585 2591 2586 2592 2587 MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):2593 VspKdMergeCandidate::VspKdMergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2): 2588 2594 mMergeCost(0), 2589 2595 mLeaf1(l1), … … 2595 2601 } 2596 2602 2597 float MergeCandidate::GetLeaf1Cost() const2603 float VspKdMergeCandidate::GetLeaf1Cost() const 2598 2604 { 2599 2605 VspKdViewCell *vc = mLeaf1->GetViewCell(); … … 2601 2607 } 2602 2608 2603 float MergeCandidate::GetLeaf2Cost() const2609 float VspKdMergeCandidate::GetLeaf2Cost() const 2604 2610 { 2605 2611 VspKdViewCell *vc = mLeaf2->GetViewCell(); … … 2607 2613 } 2608 2614 2609 void MergeCandidate::EvalMergeCost()2615 void VspKdMergeCandidate::EvalMergeCost() 2610 2616 { 2611 2617 //-- compute pvs difference … … 2630 2636 } 2631 2637 2632 void MergeCandidate::SetLeaf1(VspKdLeaf *l)2638 void VspKdMergeCandidate::SetLeaf1(VspKdLeaf *l) 2633 2639 { 2634 2640 mLeaf1 = l; 2635 2641 } 2636 2642 2637 void MergeCandidate::SetLeaf2(VspKdLeaf *l)2643 void VspKdMergeCandidate::SetLeaf2(VspKdLeaf *l) 2638 2644 { 2639 2645 mLeaf2 = l; … … 2641 2647 2642 2648 2643 VspKdLeaf * MergeCandidate::GetLeaf1()2649 VspKdLeaf *VspKdMergeCandidate::GetLeaf1() 2644 2650 { 2645 2651 return mLeaf1; … … 2647 2653 2648 2654 2649 VspKdLeaf * MergeCandidate::GetLeaf2()2655 VspKdLeaf *VspKdMergeCandidate::GetLeaf2() 2650 2656 { 2651 2657 return mLeaf2; … … 2653 2659 2654 2660 2655 bool MergeCandidate::Valid() const2661 bool VspKdMergeCandidate::Valid() const 2656 2662 { 2657 2663 return … … 2661 2667 2662 2668 2663 float MergeCandidate::GetMergeCost() const2669 float VspKdMergeCandidate::GetMergeCost() const 2664 2670 { 2665 2671 return mMergeCost; … … 2667 2673 2668 2674 2669 void MergeCandidate::SetValid()2675 void VspKdMergeCandidate::SetValid() 2670 2676 { 2671 2677 mLeaf1Id = mLeaf1->GetViewCell()->mMailbox; -
trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h
r517 r580 43 43 Candidate for leaf merging based on priority. 44 44 */ 45 class MergeCandidate45 class VspKdMergeCandidate 46 46 { 47 47 public: 48 48 49 MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2);49 VspKdMergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2); 50 50 51 51 /** Computes PVS difference between the leaves. … … 61 61 void SetValid(); 62 62 63 friend bool operator<(const MergeCandidate &leafa, constMergeCandidate &leafb)63 friend bool operator<(const VspKdMergeCandidate &leafa, const VspKdMergeCandidate &leafb) 64 64 { 65 65 return leafb.GetMergeCost() < leafa.GetMergeCost(); … … 850 850 ViewCellsManager *mViewCellsManager; 851 851 852 priority_queue< MergeCandidate> mMergeQueue;852 priority_queue<VspKdMergeCandidate> mMergeQueue; 853 853 854 854 -
trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp
r564 r580 850 850 { 851 851 ViewCell *vc = dynamic_cast<BspLeaf *>(node)->GetViewCell(); 852 852 #if 0 853 853 // set the mesh material according to the ray density 854 854 if (vc->mPassingRays.mRays) … … 860 860 mForcedMaterial.mDiffuseColor.g = 1.0f - mForcedMaterial.mDiffuseColor.r; 861 861 ExportViewCell(vc); 862 862 863 } 863 } else 864 #endif 865 } 866 else 864 867 { 865 868 BspInterior *interior = (BspInterior *)node;
Note: See TracChangeset
for help on using the changeset viewer.