Changeset 480 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
- Timestamp:
- 12/23/05 21:35:53 (19 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
r479 r480 84 84 environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells); 85 85 environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells); 86 environment->Get IntValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);86 environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 87 87 88 88 … … 125 125 Debug << "pvs"; 126 126 } 127 128 mSplitCandidates = new vector<SortableEntry>; 127 129 128 130 Debug << endl; … … 140 142 DEL_PTR(mRoot); 141 143 DEL_PTR(mRootCell); 144 DEL_PTR(mSplitCandidates); 142 145 } 143 146 … … 236 239 long startTime = GetTime(); 237 240 238 cout << "Extracting polygons from rays ... ";241 cout << "Extracting polygons from rays ... "; 239 242 240 243 Intersectable::NewMail(); … … 430 433 ++ maxCostMisses; 431 434 432 if (maxCostMisses > =mTermMissTolerance)435 if (maxCostMisses > mTermMissTolerance) 433 436 { 434 437 // terminate branch because of max cost … … 555 558 } 556 559 557 void VspBspTree::SortSplitCandidates(const PolygonContainer &polys, 558 const int axis, 559 vector<SortableEntry> &splitCandidates) const 560 { 561 splitCandidates.clear(); 562 563 const int requestedSize = 2 * (int)polys.size(); 564 565 // creates a sorted split candidates array 566 splitCandidates.reserve(requestedSize); 567 568 PolygonContainer::const_iterator it, it_end = polys.end(); 569 570 AxisAlignedBox3 box; 571 572 // insert all queries 573 for(it = polys.begin(); it != it_end; ++ it) 574 { 575 box.Initialize(); 576 box.Include(*(*it)); 577 578 splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it)); 579 splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it)); 580 } 581 582 stable_sort(splitCandidates.begin(), splitCandidates.end()); 583 } 584 585 586 float VspBspTree::BestCostRatio(const PolygonContainer &polys, 587 const AxisAlignedBox3 &box, 588 const int axis, 589 float &position, 590 int &objectsBack, 591 int &objectsFront) const 592 { 593 vector<SortableEntry> splitCandidates; 594 595 SortSplitCandidates(polys, axis, splitCandidates); 596 560 void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis) 561 { 562 mSplitCandidates->clear(); 563 564 int requestedSize = 2 * (int)(rays.size()); 565 // creates a sorted split candidates array 566 if (mSplitCandidates->capacity() > 500000 && 567 requestedSize < (int)(mSplitCandidates->capacity()/10) ) 568 { 569 DEL_PTR(mSplitCandidates); 570 mSplitCandidates = new vector<SortableEntry>; 571 } 572 573 mSplitCandidates->reserve(requestedSize); 574 575 // insert all queries 576 for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri) 577 { 578 bool positive = (*ri).mRay->HasPosDir(axis); 579 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 580 (*ri).ExtrapOrigin(axis), (void *)&*ri)); 581 582 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 583 (*ri).ExtrapTermination(axis), (void *)&*ri)); 584 } 585 586 stable_sort(mSplitCandidates->begin(), mSplitCandidates->end()); 587 } 588 589 float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays, 590 const AxisAlignedBox3 &box, 591 const int pvsSize, 592 int &axis, 593 float &position) 594 { 595 // AxisAlignedBox3 dirBox = GetDirBBox(node); 596 int raysBack; 597 int raysFront; 598 int pvsBack; 599 int pvsFront; 600 601 axis = box.Size().DrivingAxis(); 602 603 SortSplitCandidates(rays, axis); 604 597 605 // go through the lists, count the number of objects left and right 598 606 // and evaluate the following cost funcion: 599 // C = ct_div_ci + (ol + or)/queries 600 601 int objectsLeft = 0, objectsRight = (int)polys.size(); 602 607 // C = ct_div_ci + (ql*rl + qr*rr)/queries 608 609 int rl = 0, rr = (int)rays.size(); 610 int pl = 0, pr = pvsSize; 611 603 612 float minBox = box.Min(axis); 604 613 float maxBox = box.Max(axis); 605 float boxArea = box.SurfaceArea(); 606 607 float minBand = minBox + mAxisAlignedSplitBorder * (maxBox - minBox); 608 float maxBand = minBox + (1.0f - mAxisAlignedSplitBorder) * (maxBox - minBox); 609 614 float sizeBox = maxBox - minBox; 615 616 float minBand = minBox + 0.1f*(maxBox - minBox); 617 float maxBand = minBox + 0.9f*(maxBox - minBox); 618 619 float sum = rr*sizeBox; 610 620 float minSum = 1e20f; 611 vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end(); 612 613 for(ci = splitCandidates.begin(); ci != ci_end; ++ ci) 614 { 615 switch ((*ci).type) 616 { 617 case SortableEntry::POLY_MIN: 618 ++ objectsLeft; 619 break; 620 case SortableEntry::POLY_MAX: 621 -- objectsRight; 622 break; 623 default: 624 break; 625 } 626 627 if ((*ci).value > minBand && (*ci).value < maxBand) 628 { 629 AxisAlignedBox3 lbox = box; 630 AxisAlignedBox3 rbox = box; 631 lbox.SetMax(axis, (*ci).value); 632 rbox.SetMin(axis, (*ci).value); 633 634 float sum = objectsLeft * lbox.SurfaceArea() + 635 objectsRight * rbox.SurfaceArea(); 636 637 if (sum < minSum) 621 622 Intersectable::NewMail(); 623 624 // set all object as belonging to the fron pvs 625 for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri) 626 { 627 if ((*ri).mRay->IsActive()) 628 { 629 Intersectable *object = (*ri).mRay->mTerminationObject; 630 631 if (object) 632 if (!object->Mailed()) 633 { 634 object->Mail(); 635 object->mCounter = 1; 636 } 637 else 638 ++ object->mCounter; 639 } 640 } 641 642 Intersectable::NewMail(); 643 644 for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin(); 645 ci < mSplitCandidates->end(); ++ ci) 646 { 647 VssRay *ray; 648 649 switch ((*ci).type) 650 { 651 case SortableEntry::ERayMin: 652 { 653 ++ rl; 654 ray = (VssRay *) (*ci).data; 655 Intersectable *object = ray->mTerminationObject; 656 if (object && !object->Mailed()) 657 { 658 object->Mail(); 659 ++ pl; 660 } 661 break; 662 } 663 case SortableEntry::ERayMax: 664 { 665 -- rr; 666 667 ray = (VssRay *) (*ci).data; 668 Intersectable *object = ray->mTerminationObject; 669 670 if (object) 671 { 672 if (-- object->mCounter == 0) 673 -- pr; 674 } 675 676 break; 677 } 678 } 679 680 // Note: sufficient to compare size of bounding boxes of front and back side? 681 if ((*ci).value > minBand && (*ci).value < maxBand) 682 { 683 sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value); 684 685 // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 686 // cout<<"cost= "<<sum<<endl; 687 688 if (sum < minSum) 638 689 { 639 690 minSum = sum; 640 691 position = (*ci).value; 641 692 642 objectsBack = objectsLeft; 643 objectsFront = objectsRight; 693 raysBack = rl; 694 raysFront = rr; 695 696 pvsBack = pl; 697 pvsFront = pr; 698 644 699 } 645 700 } 646 701 } 647 648 const float oldCost = (float)polys.size(); 649 const float newCost = mAxisAlignedCtDivCi + minSum / boxArea; 650 const float ratio = newCost / oldCost; 651 652 653 #if 0 654 Debug << "====================" << endl; 655 Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox) 656 << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl; 657 #endif 658 return ratio; 659 } 660 661 bool VspBspTree::SelectAxisAlignedPlane(Plane3 &plane, 662 const PolygonContainer &polys) const 702 703 float oldCost = (float)pvsSize; 704 float newCost = mCtDivCi + minSum / sizeBox; 705 float ratio = newCost / oldCost; 706 707 //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) 708 // <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl; 709 710 return ratio; 711 } 712 713 714 float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane, 715 const VspBspTraversalData &tData) 663 716 { 664 717 AxisAlignedBox3 box; … … 666 719 667 720 // create bounding box of region 668 Polygon3::IncludeInBox(polys, box); 669 670 int objectsBack = 0, objectsFront = 0; 721 RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end(); 722 723 for(ri = tData.mRays->begin(); ri < ri_end; ++ ri) 724 box.Include((*ri).ExtrapTermination()); 725 671 726 int axis = 0; 672 float costRatio = MAX_FLOAT; 673 Vector3 position; 674 675 //-- area subdivision 676 for (int i = 0; i < 3; ++ i) 677 { 678 float p = 0; 679 const float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront); 727 const bool useCostHeuristics = false; 728 729 if (useCostHeuristics) 730 { 731 float position; 732 733 const float ratio = 734 BestCostRatioHeuristics(*tData.mRays, 735 box, 736 tData.mPvs, 737 axis, 738 position); 739 740 Vector3 normal(0,0,0); normal[axis] = 1; 741 plane = Plane3(normal, position); 742 743 return ratio; 744 } 745 746 //-- regular split 747 float nPosition[3]; 748 float nCostRatio[3]; 749 int bestAxis = -1; 750 751 bool mOnlyDrivingAxis = false; 752 753 const int sAxis = box.Size().DrivingAxis(); 680 754 681 if (r < costRatio) 682 { 683 costRatio = r; 684 axis = i; 685 position = p; 686 } 687 } 688 689 if (costRatio >= mTermMaxCostRatio) 690 return false; 691 692 Vector3 norm(0,0,0); norm[axis] = 1.0f; 693 plane = Plane3(norm, position); 694 695 return true; 696 } 755 for (axis = 0; axis < 3; ++ axis) 756 { 757 if (!mOnlyDrivingAxis || axis == sAxis) 758 { 759 if (!useCostHeuristics) 760 { 761 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f; 762 Vector3 normal(0,0,0); normal[axis] = 1; 763 764 nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), tData); 765 } 766 767 if (bestAxis == -1) 768 { 769 bestAxis = axis; 770 } 771 772 else if (nCostRatio[axis] < nCostRatio[bestAxis]) 773 { 774 /*Debug << "pvs front " << nPvsBack[axis] 775 << " pvs back " << nPvsFront[axis] 776 << " overall pvs " << leaf->GetPvsSize() << endl;*/ 777 bestAxis = axis; 778 } 779 780 } 781 } 782 783 //-- assign best axis 784 Vector3 normal(0,0,0); normal[bestAxis] = 1; 785 plane = Plane3(normal, nPosition[bestAxis]); 786 787 return nCostRatio[bestAxis]; 788 } 789 697 790 698 791 bool VspBspTree::SelectPlane(Plane3 &plane, … … 700 793 VspBspTraversalData &data) 701 794 { 702 if ((mSplitPlaneStrategy & AXIS_ALIGNED) &&703 ((int)data.mRays->size() > mTermMinRaysForAxisAligned))704 { // TODO: candidates should be rays705 return SelectAxisAlignedPlane(plane, *data.mPolygons);706 }707 708 795 // simplest strategy: just take next polygon 709 796 if (mSplitPlaneStrategy & RANDOM_POLYGON) … … 740 827 } 741 828 829 742 830 Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const 743 831 { … … 752 840 return Plane3(normal, pt); 753 841 } 842 754 843 755 844 Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const … … 822 911 int maxIdx = (int)data.mPolygons->size(); 823 912 913 float candidateCost; 914 824 915 for (int i = 0; i < limit; ++ i) 825 916 { … … 836 927 837 928 // evaluate current candidate 838 const float candidateCost = 839 SplitPlaneCost(poly->GetSupportingPlane(), data); 929 candidateCost = SplitPlaneCost(poly->GetSupportingPlane(), data); 840 930 841 931 if (candidateCost < lowestCost) … … 846 936 } 847 937 938 #if 0 848 939 //-- choose candidate planes extracted from rays 849 940 //-- different methods are available … … 851 942 { 852 943 plane = ChooseCandidatePlane3(*data.mRays); 853 c onst float candidateCost = SplitPlaneCost(plane, data);944 candidateCost = SplitPlaneCost(plane, data); 854 945 855 946 if (candidateCost < lowestCost) … … 858 949 lowestCost = candidateCost; 859 950 } 951 } 952 #endif 953 954 // axis aligned splits 955 candidateCost = SelectAxisAlignedPlane(plane, data); 956 957 if (candidateCost < lowestCost) 958 { 959 bestPlane = plane; 960 lowestCost = candidateCost; 860 961 } 861 962 … … 880 981 881 982 float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane, 882 const VspBspTraversalData &data) 983 const VspBspTraversalData &data) const 883 984 { 884 985 float cost = 0; … … 1957 2058 int merged = 0; 1958 2059 1959 Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 1960 Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl; 1961 1962 // use priority queue to merge leaves 2060 //-- use priority queue to merge leaf pairs 1963 2061 while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) && 1964 2062 (mergeQueue.top().GetMergeCost() < 1965 2063 mMergeMaxCostRatio * BspMergeCandidate::sOverallCost)) 1966 2064 { 1967 Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;2065 //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 1968 2066 BspMergeCandidate mc = mergeQueue.top(); 1969 2067 mergeQueue.pop();
Note: See TracChangeset
for help on using the changeset viewer.