![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
Changeset 612 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
- Timestamp:
- 02/12/06 21:45:02 (18 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
r611 r612 124 124 mSubdivisionStats.open("subdivisionStats.log"); 125 125 126 environment->GetBoolValue("VspBspTree.useCostHeuristics", mUseCostHeuristics); 127 126 128 127 129 //-- debug output … … 393 395 394 396 395 // return memory usage in MB397 // TODO: return memory usage in MB 396 398 float VspBspTree::GetMemUsage(/*const VspBspTraversalQueue &tstack*/) const 397 399 { … … 454 456 455 457 long startTime = GetTime(); 458 int nLeaves = 0; 459 int nViewCells = 0; 456 460 457 461 // used for intermediate time measurements and progress … … 460 464 mOutOfMemory = false; 461 465 462 int nleaves = 500;463 466 mCreatedViewCells = 0; 467 464 468 while (!tQueue.empty()) 465 469 { … … 485 489 << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 486 490 487 if (mBspStats.Leaves() >= nleaves)488 { 489 n leaves += 500;490 491 if (mBspStats.Leaves() == nLeaves) 492 { 493 nLeaves += 500; 494 491 495 cout << "leaves=" << mBspStats.Leaves() << endl; 492 496 Debug << "needed " 493 497 << TimeDiff(interTime, GetTime())*1e-3 494 << " secs to create 500 leaves" << endl;498 << " secs to create 500 view cells" << endl; 495 499 interTime = GetTime(); 500 } 501 502 if (mCreatedViewCells == nViewCells) 503 { 504 nViewCells += 500; 505 506 cout << "generated " << mCreatedViewCells << " viewcells" << endl; 496 507 } 497 508 } … … 530 541 VspBspTraversalData tFrontData; 531 542 VspBspTraversalData tBackData; 543 532 544 #if OCTREE_HACK 533 545 //Debug << "new axis:" << (tData.mAxis + 1) % 3 << endl; 534 535 546 tFrontData.mAxis = (tData.mAxis + 1) % 3; 536 547 tBackData.mAxis = (tData.mAxis + 1) % 3; … … 593 604 leaf->mVssRays.push_back((*it).mRay); 594 605 } 606 595 607 // should I check here? 596 608 if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize())) … … 634 646 int maxCostMisses = tData.mMaxCostMisses; 635 647 648 int splitAxis; 649 636 650 const bool success = 637 SelectPlane(splitPlane, leaf, tData, frontData, backData );651 SelectPlane(splitPlane, leaf, tData, frontData, backData, splitAxis); 638 652 639 653 if (!success) … … 648 662 } 649 663 } 664 665 //! error also computed if cost ratio is missed 666 if (splitAxis < 3) 667 ++ mBspStats.splits[splitAxis]; 668 else 669 ++ mBspStats.polySplits; 650 670 651 671 mBspStats.nodes += 2; … … 792 812 // creates a sorted split candidates array 793 813 if (mSplitCandidates->capacity() > 500000 && 794 requestedSize < (int)(mSplitCandidates->capacity() /10) )814 requestedSize < (int)(mSplitCandidates->capacity() / 10) ) 795 815 { 796 816 delete mSplitCandidates; … … 801 821 802 822 // insert all queries 803 for (RayInfoContainer::const_iterator ri = rays.begin();ri < rays.end(); ++ ri)804 { 805 bool positive = (*ri).mRay->HasPosDir(axis);823 for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri) 824 { 825 const bool positive = (*ri).mRay->HasPosDir(axis); 806 826 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 807 827 (*ri).ExtrapOrigin(axis), (*ri).mRay)); … … 821 841 float &position) 822 842 { 823 int raysBack;824 int raysFront;825 int pvsBack;826 int pvsFront;827 828 843 SortSplitCandidates(rays, axis); 829 844 … … 832 847 // C = ct_div_ci + (ql*rl + qr*rr)/queries 833 848 834 int rl = 0, rr = (int)rays.size(); 835 int pl = 0, pr = pvsSize; 849 int pvsl = 0, pvsr = pvsSize; 850 851 int pvsBack = pvsl; 852 int pvsFront = pvsr; 836 853 837 854 float minBox = box.Min(axis); … … 839 856 float sizeBox = maxBox - minBox; 840 857 841 float minBand = minBox + 0.1f *(maxBox - minBox);842 float maxBand = minBox + 0.9f *(maxBox - minBox);843 844 float sum = rr*sizeBox;858 float minBand = minBox + 0.1f * (maxBox - minBox); 859 float maxBand = minBox + 0.9f * (maxBox - minBox); 860 861 float sum = (float)pvsSize * sizeBox; 845 862 float minSum = 1e20f; 846 863 847 864 Intersectable::NewMail(); 848 865 849 // set all object as belonging to the fron pvs 850 for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri) 851 { 852 if ((*ri).mRay->IsActive()) 853 { 854 Intersectable *object = (*ri).mRay->mTerminationObject; 855 856 if (object) 857 { 858 if (!object->Mailed()) 859 { 860 object->Mail(); 861 object->mCounter = 1; 862 } 863 else 864 ++ object->mCounter; 866 RayInfoContainer::const_iterator ri, ri_end = rays.end(); 867 868 // set all object as belonging to the front pvs 869 for(ri = rays.begin(); ri != ri_end; ++ ri) 870 { 871 Intersectable *oObject = (*ri).mRay->mOriginObject; 872 Intersectable *tObject = (*ri).mRay->mTerminationObject; 873 874 if (oObject) 875 { 876 if (!oObject->Mailed()) 877 { 878 oObject->Mail(); 879 oObject->mCounter = 1; 880 } 881 else 882 { 883 ++ oObject->mCounter; 884 } 885 } 886 if (tObject) 887 { 888 if (!tObject->Mailed()) 889 { 890 tObject->Mail(); 891 tObject->mCounter = 1; 892 } 893 else 894 { 895 ++ tObject->mCounter; 865 896 } 866 897 } … … 869 900 Intersectable::NewMail(); 870 901 871 for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin(); 872 ci < mSplitCandidates->end(); ++ ci) 902 vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end(); 903 904 for (ci = mSplitCandidates->begin(); ci < ci_end; ++ ci) 873 905 { 874 906 VssRay *ray; 907 ray = (*ci).ray; 908 909 Intersectable *oObject = ray->mOriginObject; 910 Intersectable *tObject = ray->mTerminationObject; 911 875 912 876 913 switch ((*ci).type) … … 878 915 case SortableEntry::ERayMin: 879 916 { 880 ++ rl; 881 ray = (VssRay *) (*ci).ray; 882 883 Intersectable *object = ray->mTerminationObject; 884 885 if (object && !object->Mailed()) 917 if (oObject && !oObject->Mailed()) 886 918 { 887 object->Mail(); 888 ++ pl; 919 oObject->Mail(); 920 ++ pvsl; 921 } 922 if (tObject && !tObject->Mailed()) 923 { 924 tObject->Mail(); 925 ++ pvsl; 889 926 } 890 927 break; … … 892 929 case SortableEntry::ERayMax: 893 930 { 894 -- rr; 895 ray = (VssRay *) (*ci).ray; 896 897 Intersectable *object = ray->mTerminationObject; 898 899 if (object) 931 if (oObject) 900 932 { 901 if (-- object->mCounter == 0) 902 -- pr; 933 if (-- oObject->mCounter == 0) 934 -- pvsr; 935 } 936 937 if (tObject) 938 { 939 if (-- tObject->mCounter == 0) 940 -- pvsr; 903 941 } 904 942 … … 910 948 if ((*ci).value > minBand && (*ci).value < maxBand) 911 949 { 912 sum = p l*((*ci).value - minBox) + pr*(maxBox - (*ci).value);950 sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value); 913 951 914 952 // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; … … 920 958 position = (*ci).value; 921 959 922 raysBack = rl; 923 raysFront = rr; 924 925 pvsBack = pl; 926 pvsFront = pr; 927 928 } 929 } 930 } 931 932 float oldCost = (float)pvsSize; 933 float newCost = mCtDivCi + minSum / sizeBox; 934 float ratio = newCost / oldCost; 960 pvsBack = pvsl; 961 pvsFront = pvsr; 962 } 963 } 964 } 965 966 // -- compute cost 967 968 const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 969 const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 970 971 const float pOverall = sizeBox; 972 973 const float pBack = position - minBox; 974 const float pFront = maxBox - position; 975 976 const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit); 977 const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 978 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 979 980 const float oldRenderCost = penaltyOld * pOverall; 981 const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack; 982 983 float ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small); 935 984 936 985 //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) … … 950 999 const bool useKdSplit) 951 1000 { 952 const bool useCostHeuristics = false;953 954 //-- regular split955 1001 float nPosition[3]; 956 1002 float nCostRatio[3]; … … 960 1006 BspNodeGeometry *nFrontGeom[3]; 961 1007 BspNodeGeometry *nBackGeom[3]; 1008 1009 for (int i = 0; i < 3; ++ i) 1010 { 1011 nFrontGeom[i] = NULL; 1012 nBackGeom[i] = NULL; 1013 } 962 1014 963 1015 int bestAxis = -1; … … 990 1042 for (axis = 0; axis < 3; ++ axis) 991 1043 { 992 nFrontGeom[axis] = new BspNodeGeometry();993 nBackGeom[axis] = new BspNodeGeometry();994 995 1044 if (!mOnlyDrivingAxis || (axis == sAxis)) 996 1045 { 997 if (!useCostHeuristics) 998 { 1046 if (!mUseCostHeuristics) 1047 { 1048 nFrontGeom[axis] = new BspNodeGeometry(); 1049 nBackGeom[axis] = new BspNodeGeometry(); 1050 999 1051 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f; 1000 1052 Vector3 normal(0,0,0); normal[axis] = 1.0f; … … 1042 1094 bestAxis = axis; 1043 1095 } 1044 1045 1096 else if (nCostRatio[axis] < nCostRatio[bestAxis]) 1046 1097 { … … 1061 1112 1062 1113 // and delete other geometry 1063 delete nFrontGeom[(bestAxis + 1) % 3];1064 delete nBackGeom[(bestAxis + 2) % 3];1114 DEL_PTR(nFrontGeom[(bestAxis + 1) % 3]); 1115 DEL_PTR(nBackGeom[(bestAxis + 2) % 3]); 1065 1116 1066 1117 //-- split plane … … 1076 1127 VspBspTraversalData &data, 1077 1128 VspBspTraversalData &frontData, 1078 VspBspTraversalData &backData) 1129 VspBspTraversalData &backData, 1130 int &splitAxis) 1079 1131 { 1080 1132 // simplest strategy: just take next polygon … … 1150 1202 float pFront, pBack; 1151 1203 1152 candidateCost = SelectAxisAlignedPlane(plane, data, axis, 1153 &fGeom, &bGeom, 1154 pFront, pBack, 1204 candidateCost = SelectAxisAlignedPlane(plane, 1205 data, 1206 axis, 1207 &fGeom, 1208 &bGeom, 1209 pFront, 1210 pBack, 1155 1211 data.mIsKdNode); 1156 1212 1157 bool isAxisAlignedSplit = false;1213 splitAxis = 3; 1158 1214 1159 1215 if (candidateCost < lowestCost) … … 1161 1217 bestPlane = plane; 1162 1218 lowestCost = candidateCost; 1163 1219 splitAxis = axis; 1164 1220 // assign already computed values 1165 1221 // we can do this because we always save the 1166 1222 // computed values from the axis aligned splits 1167 frontData.mGeometry = fGeom; 1168 backData.mGeometry = bGeom; 1169 1170 frontData.mProbability = pFront; 1171 backData.mProbability = pBack; 1172 1173 //! error also computed if cost ratio is missed 1174 ++ mBspStats.splits[axis]; 1175 isAxisAlignedSplit = true; 1223 if (fGeom && bGeom) 1224 { 1225 frontData.mGeometry = fGeom; 1226 backData.mGeometry = bGeom; 1227 1228 frontData.mProbability = pFront; 1229 backData.mProbability = pBack; 1230 } 1176 1231 } 1177 1232 else … … 1181 1236 } 1182 1237 1183 frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit); 1238 frontData.mIsKdNode = backData.mIsKdNode = 1239 (data.mIsKdNode && splitAxis < 3); 1184 1240 1185 1241 #ifdef _DEBUG … … 1401 1457 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 1402 1458 1403 const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;1459 const float oldRenderCost = pOverall * penaltyOld; 1404 1460 const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack; 1405 1461 … … 1420 1476 fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost); 1421 1477 1422 const float oldDeviation = penaltyOld + Limits::Small;1478 const float oldDeviation = penaltyOld; 1423 1479 1424 1480 newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation; … … 1426 1482 } 1427 1483 1428 cost += mPvsFactor * newCost / oldCost;1484 cost += mPvsFactor * newCost / (oldCost + Limits::Small); 1429 1485 1430 1486 } … … 1656 1712 mBspStats.accumDepth += data.mDepth; 1657 1713 1714 ++ mCreatedViewCells; 1658 1715 #ifdef _DEBUG 1659 1716 Debug << "BSP stats: " … … 1666 1723 #endif 1667 1724 } 1725 1668 1726 1669 1727 int VspBspTree::CastRay(Ray &ray)
Note: See TracChangeset
for help on using the changeset viewer.
