![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
Changeset 562 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
- Timestamp:
- 01/20/06 22:32:51 (18 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
r561 r562 329 329 float minT, maxT; 330 330 331 //static Ray hray; 332 //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT); 333 331 334 // TODO: not very efficient to implictly cast between rays types 332 335 if (mBox.GetRaySegment(*ray, minT, maxT)) … … 393 396 geom); 394 397 398 // first node is kd node 399 tData.mIsKdNode = true; 400 395 401 tStack.push(tData); 396 402 … … 510 516 } 511 517 512 if ( !mViewCellsManager->CheckValidity(viewCell, 0.0, mViewCellsManager->GetMaxPvsRatio()))518 if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize())) 513 519 { 514 520 viewCell->SetValid(false); … … 880 886 box.Initialize(); 881 887 882 //TODO: for kd split geometry already is box 888 //TODO: for kd split geometry already is box => only take minmax vertices 883 889 if (1) 884 890 { … … 997 1003 const int pvsSize = data.mPvs; 998 1004 1005 RayInfoContainer::const_iterator rit, rit_end = data.mRays->end(); 1006 999 1007 // this is the main ray classification loop! 1000 for(RayInfoContainer::iterator ri = data.mRays->begin(); 1001 ri != data.mRays->end(); ++ ri) 1002 { 1003 if (!(*ri).mRay->IsActive()) 1004 continue; 1008 for(rit = data.mRays->begin(); rit != rit_end; ++ rit) 1009 { 1010 //if (!(*rit).mRay->IsActive()) continue; 1005 1011 1006 1012 // determine the side of this ray with respect to the plane 1007 1013 float t; 1008 int side = (*ri).ComputeRayIntersection(axis, position, t);1009 1010 AddObjToPvs((*ri ).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);1011 AddObjToPvs((*ri ).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);1014 const int side = (*rit).ComputeRayIntersection(axis, position, t); 1015 1016 AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal); 1017 AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal); 1012 1018 } 1013 1019 … … 1015 1021 float pOverall; 1016 1022 1017 // -- simplified computation for mid split1018 1019 1023 //-- compute heurstics 1024 // we take simplified computation for mid split 1025 1020 1026 pOverall = data.mProbability; 1021 1027 … … 1046 1052 } 1047 1053 1048 //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl; 1049 //Debug << pFront << " " << pBack << " " << pOverall << endl; 1054 #ifdef _DEBUG 1055 Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl; 1056 Debug << pFront << " " << pBack << " " << pOverall << endl; 1057 #endif 1050 1058 1051 1059 const float newCost = pvsBack * pBack + pvsFront * pFront; 1052 const float oldCost = (float)pvsSize * pOverall ;1060 const float oldCost = (float)pvsSize * pOverall + Limits::Small; 1053 1061 1054 1062 return (mCtDivCi + newCost) / oldCost; … … 1098 1106 for (int i = 0; i < limit; ++ i) 1099 1107 { 1100 //-- assure that no index is taken twice 1108 // the already taken candidates are stored behind maxIdx 1109 // => assure that no index is taken twice 1101 1110 const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx)); 1102 1111 Polygon3 *poly = (*data.mPolygons)[candidateIdx]; … … 1127 1136 &fGeom, &bGeom, 1128 1137 pFront, pBack, 1129 onlyAxisAligned); 1138 data.mIsKdNode); 1139 1140 bool isAxisAlignedSplit = false; 1130 1141 1131 1142 if (candidateCost < lowestCost) … … 1136 1147 // assign already computed values 1137 1148 // we can do this because we always save the 1138 // computed values from the axis aligned splits 1139 1149 // computed values from the axis aligned splits 1140 1150 frontData.mGeometry = fGeom; 1141 1151 backData.mGeometry = bGeom; … … 1146 1156 //! error also computed if cost ratio is missed 1147 1157 ++ mStat.splits[axis]; 1158 isAxisAlignedSplit = true; 1148 1159 } 1149 1160 else … … 1152 1163 DEL_PTR(bGeom); 1153 1164 } 1165 1166 frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit); 1154 1167 1155 1168 #ifdef _DEBUG … … 1295 1308 const int cf = rayInf.ComputeRayIntersection(candidatePlane, t); 1296 1309 1297 if (cf >= 0) 1298 ++ raysFront; 1299 if (cf <= 0) 1300 ++ raysBack; 1310 if (0) 1311 { 1312 if (cf >= 0) 1313 ++ raysFront; 1314 if (cf <= 0) 1315 ++ raysBack; 1316 } 1301 1317 1302 1318 if (mSplitPlaneStrategy & LEAST_RAY_SPLITS) … … 1368 1384 1369 1385 // normalize cost by sum of linear factors 1370 return cost / (float)mCostNormalizer; 1386 if(0) 1387 return cost / (float)mCostNormalizer; 1388 else 1389 return cost; 1371 1390 } 1372 1391 … … 1644 1663 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell(); 1645 1664 1646 if (!mViewCellsManager->CheckValidity(viewCell, 0.0, mViewCellsManager->GetMaxPvsRatio())) 1665 if (!mViewCellsManager->CheckValidity(viewCell, 1666 mViewCellsManager->GetMinPvsSize(), 1667 mViewCellsManager->GetMaxPvsSize())) 1647 1668 { 1648 1669 vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end(); … … 1681 1702 } 1682 1703 } 1704 1705 Debug << "invalid leaves: " << mStat.invalidLeaves << endl; 1683 1706 } 1684 1707 … … 1918 1941 1919 1942 int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 1920 1943 const bool onlyUnmailed) const 1921 1944 { 1922 1945 stack<bspNodePair> nodeStack; … … 1937 1960 nodeStack.push(bspNodePair(mRoot, rgeom)); 1938 1961 1939 Debug << "here77" << endl;1940 1941 1962 while (!nodeStack.empty()) 1942 1963 { 1943 1964 BspNode *node = nodeStack.top().first; 1944 1965 BspNodeGeometry *geom = nodeStack.top().second; 1945 1966 1946 1967 nodeStack.pop(); 1947 1968 1948 1969 if (node->IsLeaf()) 1949 { 1950 Debug << "here22" << endl; 1970 { 1951 1971 // test if this leaf is in valid view space 1952 1972 if (node->TreeValid() && … … 1954 1974 (!onlyUnmailed || !node->Mailed())) 1955 1975 { 1956 Debug << "here" << endl;1957 1976 bool isAdjacent = true; 1958 #if 1 1959 1960 // test all planes of current node if still adjacent 1961 for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i) 1977 1978 if (1) 1962 1979 { 1963 const int cf = 1964 Polygon3::ClassifyPlane(geom->mPolys, 1965 halfSpaces[i], 1966 mEpsilon); 1967 1968 if (cf == Polygon3::BACK_SIDE) 1980 // test all planes of current node if still adjacent 1981 for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i) 1969 1982 { 1970 isAdjacent = false; 1983 const int cf = 1984 Polygon3::ClassifyPlane(geom->mPolys, 1985 halfSpaces[i], 1986 mEpsilon); 1987 1988 if (cf == Polygon3::BACK_SIDE) 1989 { 1990 isAdjacent = false; 1991 } 1971 1992 } 1972 1993 } 1973 #else // TODO: why is this wrong?? 1974 // test all planes of current node if still adjacent 1975 for (int i = 0; (i < (int)nodeGeom.mPolys.size()) && isAdjacent; ++ i) 1994 else 1976 1995 { 1977 Debug << "here33" << endl; 1978 Polygon3 *poly = nodeGeom.mPolys[i]; 1979 1980 const int cf = 1981 Polygon3::ClassifyPlane(geom->mPolys, 1982 poly->GetSupportingPlane(), 1983 mEpsilon); 1984 1985 if (cf == Polygon3::BACK_SIDE) 1996 // TODO: why is this wrong?? 1997 // test all planes of current node if still adjacent 1998 for (int i = 0; (i < (int)nodeGeom.mPolys.size()) && isAdjacent; ++ i) 1986 1999 { 1987 isAdjacent = false; 2000 Polygon3 *poly = nodeGeom.mPolys[i]; 2001 2002 const int cf = 2003 Polygon3::ClassifyPlane(geom->mPolys, 2004 poly->GetSupportingPlane(), 2005 mEpsilon); 2006 2007 if (cf == Polygon3::BACK_SIDE) 2008 { 2009 isAdjacent = false; 2010 } 1988 2011 } 1989 2012 } 1990 #endif1991 Debug << "here2" << endl;1992 2013 // neighbor was found 1993 2014 if (isAdjacent) 2015 { 1994 2016 neighbors.push_back(dynamic_cast<BspLeaf *>(node)); 2017 } 2018 } 2019 } 2020 else 2021 { 2022 BspInterior *interior = dynamic_cast<BspInterior *>(node); 2023 2024 const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys, 2025 interior->GetPlane(), 2026 mEpsilon); 2027 2028 BspNode *front = interior->GetFront(); 2029 BspNode *back = interior->GetBack(); 2030 2031 BspNodeGeometry *fGeom = new BspNodeGeometry(); 2032 BspNodeGeometry *bGeom = new BspNodeGeometry(); 2033 2034 geom->SplitGeometry(*fGeom, 2035 *bGeom, 2036 interior->GetPlane(), 2037 mBox, 2038 mEpsilon); 2039 2040 if (cf == Polygon3::FRONT_SIDE) 2041 { 2042 nodeStack.push(bspNodePair(interior->GetFront(), fGeom)); 2043 DEL_PTR(bGeom); 1995 2044 } 1996 2045 else 1997 2046 { 1998 BspInterior *interior = dynamic_cast<BspInterior *>(node); 1999 2000 const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys, 2001 interior->GetPlane(), 2002 mEpsilon); 2003 2004 BspNode *front = interior->GetFront(); 2005 BspNode *back = interior->GetBack(); 2006 2007 BspNodeGeometry *fGeom = new BspNodeGeometry(); 2008 BspNodeGeometry *bGeom = new BspNodeGeometry(); 2009 2010 geom->SplitGeometry(*fGeom, 2011 *bGeom, 2012 interior->GetPlane(), 2013 mBox, 2014 mEpsilon); 2015 2016 if (cf == Polygon3::FRONT_SIDE) 2047 if (cf == Polygon3::BACK_SIDE) 2017 2048 { 2018 nodeStack.push(bspNodePair(interior->Get Front(), fGeom));2019 DEL_PTR( bGeom);2049 nodeStack.push(bspNodePair(interior->GetBack(), bGeom)); 2050 DEL_PTR(fGeom); 2020 2051 } 2021 2052 else 2022 { 2023 if (cf == Polygon3::BACK_SIDE) 2024 { 2025 nodeStack.push(bspNodePair(interior->GetBack(), bGeom)); 2026 DEL_PTR(fGeom); 2027 } 2028 else 2029 { // random decision 2030 nodeStack.push(bspNodePair(front, fGeom)); 2031 nodeStack.push(bspNodePair(back, bGeom)); 2032 } 2053 { // random decision 2054 nodeStack.push(bspNodePair(front, fGeom)); 2055 nodeStack.push(bspNodePair(back, bGeom)); 2033 2056 } 2034 2057 } 2035 2058 } 2036 2059 2037 2060 DEL_PTR(geom); 2038 2061 } … … 2792 2815 mergeStats.Start(); 2793 2816 // TODO: REMOVE LATER for performance! 2794 const bool showMergeStats = true; 2817 const bool showMergeStats = false; 2818 2795 2819 //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs; 2796 2820 long startTime = GetTime(); … … 2808 2832 mergeStats.nodes = CollectMergeCandidates(leaves); 2809 2833 } 2810 2834 2811 2835 2812 2836 mergeStats.collectTime = TimeDiff(startTime, GetTime()); … … 2814 2838 startTime = GetTime(); 2815 2839 2840 // number of view cells withouth the invalid ones 2816 2841 int nViewCells = mStat.Leaves() - mStat.invalidLeaves; 2817 int pass = 0; 2818 const int nextPass = 200; 2819 2820 cout << "starting merge ... "; 2842 Debug << "number of view cells taken into account: " << nViewCells << endl; 2843 // pass is needed for statistics. the last n passes are 2844 // recorded 2845 const int maxPasses = 1000; 2846 int pass = max(nViewCells - mMergeMinViewCells - maxPasses, 0); 2847 const int nextPass = 50; 2848 2849 cout << "starting merge ... " << endl; 2821 2850 2822 2851 //-- use priority queue to merge leaf pairs … … 2825 2854 mMergeMaxCostRatio * BspMergeCandidate::sOverallCost)) 2826 2855 { 2827 /*Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: " 2856 #ifdef _DEBUG 2857 Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: " 2828 2858 << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 2829 << " max ratio: " << mMergeMaxCostRatio << endl;*/ 2859 << " max ratio: " << mMergeMaxCostRatio << endl; 2860 #endif 2861 2830 2862 BspMergeCandidate mc = mMergeQueue.top(); 2831 2863 mMergeQueue.pop(); … … 2841 2873 2842 2874 MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2()); 2843 2844 2875 2845 2876 // increase absolute merge cost 2846 2877 BspMergeCandidate::sOverallCost += mc.GetMergeCost(); 2847 2878 2879 2880 -- nViewCells; 2881 ++ mergeStats.merged; 2848 2882 2849 2883 if (showMergeStats) … … 2858 2892 mergeStats.accTreeDist += dist; 2859 2893 2860 2861 if (( (mergeStats.merged % nextPass) == 0) || (nViewCells == mMergeMinViewCells))2894 //Debug << "viewcells: " << nViewCells << " mergemin " << mMergeMinViewCells << endl; 2895 if ((mergeStats.merged == pass) || (nViewCells == mMergeMinViewCells)) 2862 2896 { 2897 pass += nextPass; 2863 2898 mStats 2864 2899 << "#Pass\n" << pass ++ << endl 2865 2900 << "#Merged\n" << mergeStats.merged << endl 2866 2901 << "#Viewcells\n" << nViewCells << endl 2867 << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl 2902 << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl 2868 2903 << "#CurrentCost\n" << mergeCost << endl 2869 << "#Rel Cost\n" << mc.GetMergeCost()/ BspMergeCandidate::sOverallCost << endl2904 << "#RelativeCost\n" << mergeCost / BspMergeCandidate::sOverallCost << endl 2870 2905 << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl; 2871 2872 cout << "exporting view cells ... "; 2873 2874 2906 2875 2907 ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 2876 2908 … … 2882 2914 while (!viewCells.empty() && (viewCells.back()->GetId() == -2)) 2883 2915 { 2884 DEL_PTR(viewCells.back());2916 //DEL_PTR(viewCells.back()); 2885 2917 viewCells.pop_back(); 2886 2918 } … … 2897 2929 } 2898 2930 2899 cout << "finished" << endl; 2900 // not part of any leaf 2901 //CLEAR_CONTAINER(mOldViewCells); 2902 mOldViewCells.clear(); 2903 2904 int newVcSize = (int)mNewViewCells.size(); 2905 // add new view cells to container 2931 int newVcSize = 0; 2932 // add new view cells to container only if they don't have been 2933 // merged in the mean time 2906 2934 while (!mNewViewCells.empty()) 2907 2935 { 2908 viewCells.push_back(mNewViewCells.back()); 2936 if (mNewViewCells.back()->GetId() != -2) 2937 { 2938 viewCells.push_back(mNewViewCells.back()); 2939 ++ newVcSize; 2940 } 2941 2909 2942 mNewViewCells.pop_back(); 2910 2943 } 2944 2945 // delete the view cells which were merged 2946 CLEAR_CONTAINER(mOldViewCells); 2911 2947 2912 2948 char s[64]; … … 2916 2952 if (exporter) 2917 2953 { 2954 cout << "exporting " << nViewCells << " merged view cells ... "; 2918 2955 exporter->ExportGeometry(objects); 2919 Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;2956 //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl; 2920 2957 ViewCellContainer::const_iterator it, it_end = viewCells.end(); 2921 2958 2922 // new view cells are on the back2923 2959 int i = 0; 2924 2960 for (it = viewCells.begin(); it != it_end; ++ it) … … 2926 2962 Material m; 2927 2963 // assign special material to new view cells 2928 if (i >= (viewCells.size() - newVcSize)) 2964 // new view cells are on the back of container 2965 if (i ++ >= (viewCells.size() - newVcSize)) 2929 2966 { 2930 2967 //m = RandomMaterial(); 2931 m.mDiffuseColor.r = RandomValue(0.5 , 1.0);2932 m.mDiffuseColor.g = RandomValue(0.5 , 1.0);2933 m.mDiffuseColor.b = RandomValue(0.5 , 1.0);2968 m.mDiffuseColor.r = RandomValue(0.5f, 1.0f); 2969 m.mDiffuseColor.g = RandomValue(0.5f, 1.0f); 2970 m.mDiffuseColor.b = RandomValue(0.5f, 1.0f); 2934 2971 } 2935 2972 else 2936 2973 { 2937 float col = RandomValue(0.1 , 0.4);2974 float col = RandomValue(0.1f, 0.4f); 2938 2975 m.mDiffuseColor.r = col; 2939 2976 m.mDiffuseColor.g = col; … … 2944 2981 mViewCellsManager->ExportVcGeometry(exporter, *it); 2945 2982 } 2983 delete exporter; 2984 cout << "finished" << endl; 2985 } 2946 2986 2947 delete exporter;2948 }2949 cout << "finished " << endl;2950 2951 2987 } 2952 2988 } 2953 2954 -- nViewCells; 2955 ++ mergeStats.merged; 2989 mNewViewCells.clear(); 2956 2990 } 2957 2991 // merge candidate not valid, because one of the leaves was already … … 2964 2998 } 2965 2999 2966 3000 // view cells which were merged and are not part of any leaf 3001 CLEAR_CONTAINER(mOldViewCells); 3002 2967 3003 cout << "finished merge" << endl; 2968 3004 mergeStats.mergeTime = TimeDiff(startTime, GetTime());
Note: See TracChangeset
for help on using the changeset viewer.
