Changeset 478 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
- Timestamp:
- 12/22/05 18:32:39 (19 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
r475 r478 1 #include <stack> 2 #include <time.h> 3 #include <iomanip> 4 1 5 #include "Plane3.h" 2 6 #include "VspBspTree.h" … … 8 12 #include "Ray.h" 9 13 #include "AxisAlignedBox3.h" 10 #include <stack>11 #include <time.h>12 #include <iomanip>13 14 #include "Exporter.h" 14 15 #include "Plane3.h" 15 16 #include "ViewCellBsp.h" 17 #include "ViewCellsManager.h" 18 16 19 17 20 //-- static members … … 30 33 int VspBspTree::sFrontAndBackId = 0; 31 34 35 float BspMergeCandidate::sOverallCost = Limits::Small; 32 36 33 37 /****************************************************************/ … … 38 42 mRoot(NULL), 39 43 mPvsUseArea(true), 40 mCostNormalizer(Limits::Small) 44 mCostNormalizer(Limits::Small), 45 mViewCellsManager(NULL), 46 mStoreRays(true) 41 47 { 42 48 mRootCell = new BspViewCell(); … … 75 81 environment->GetIntValue("VspBspTree.maxTests", mMaxTests); 76 82 77 // maximum number of view cells 78 environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 79 80 //-- 83 // maximum and minimum number of view cells 84 environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells); 85 environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells); 86 environment->GetIntValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 87 88 89 //-- debug output 81 90 Debug << "******* VSP BSP options ******** " << endl; 82 91 Debug << "max depth: " << mTermMaxDepth << endl; … … 313 322 long startTime = GetTime(); 314 323 315 while (!tStack.empty()) 324 while (!tStack.empty()) 316 325 { 317 326 tData = tStack.top(); 318 327 319 328 tStack.pop(); 329 320 330 // subdivide leaf node 321 331 BspNode *r = Subdivide(tStack, tData); … … 331 341 } 332 342 333 bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data, 334 const int numLeaves) const 343 bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const 335 344 { 336 345 return … … 338 347 (data.mPvs <= mTermMinPvs) || 339 348 (data.mArea <= mTermMinArea) || 340 ( (mStat.nodes / 2 + 1)>= mMaxViewCells) ||349 (mStat.nodes / 2 + 1 >= mMaxViewCells) || 341 350 // (data.GetAvgRayContribution() >= mTermMaxRayContribution) || 342 351 (data.mDepth >= mTermMaxDepth)); … … 348 357 BspNode *newNode = tData.mNode; 349 358 350 if (!TerminationCriteriaMet(tData , (int)tStack.size()))359 if (!TerminationCriteriaMet(tData)) 351 360 { 352 361 PolygonContainer coincident; … … 370 379 } 371 380 372 //-- terminate traversal 381 //-- terminate traversal and create new view cell 373 382 if (newNode->IsLeaf()) 374 383 { … … 378 387 BspViewCell *viewCell = new BspViewCell(); 379 388 leaf->SetViewCell(viewCell); 389 390 if (mStoreRays) 391 { 392 RayInfoContainer::const_iterator it, it_end = tData.mRays->end(); 393 for (it = tData.mRays->begin(); it != it_end; ++ it) 394 leaf->mVssRays.push_back((*it).mRay); 395 } 396 380 397 viewCell->mLeaves.push_back(leaf); 398 viewCell->SetArea(tData.mArea); 381 399 382 400 //-- update pvs … … 392 410 393 411 //-- cleanup 394 DEL_PTR(tData.mPolygons); 395 DEL_PTR(tData.mRays); 396 DEL_PTR(tData.mGeometry); 412 tData.Clear(); 397 413 398 414 return newNode; … … 1872 1888 return hits; 1873 1889 } 1890 1891 int VspBspTree::MergeLeaves() 1892 { 1893 vector<BspLeaf *> leaves; 1894 priority_queue<BspMergeCandidate> mergeQueue; 1895 1896 // collect the leaves, e.g., the "voxels" that will build the view cells 1897 CollectLeaves(leaves); 1898 1899 int vcSize = (int)leaves.size(); 1900 int savedVcSize = vcSize; 1901 1902 BspLeaf::NewMail(); 1903 1904 vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 1905 1906 // find merge candidates and push them into queue 1907 for (it = leaves.begin(); it != it_end; ++ it) 1908 { 1909 BspLeaf *leaf = *it; 1910 1911 // no leaf is part of two merge candidates 1912 if (!leaf->Mailed()) 1913 { 1914 leaf->Mail(); 1915 1916 vector<BspLeaf *> neighbors; 1917 FindNeighbors(leaf, neighbors, true); 1918 1919 vector<BspLeaf *>::const_iterator nit, 1920 nit_end = neighbors.end(); 1921 1922 for (nit = neighbors.begin(); nit != nit_end; ++ nit) 1923 { 1924 BspMergeCandidate mc = BspMergeCandidate(leaf, *nit); 1925 mergeQueue.push(mc); 1926 1927 BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost(); 1928 BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost(); 1929 } 1930 } 1931 } 1932 1933 int merged = 0; 1934 1935 Debug << "here234: " << mMergeMaxCostRatio << endl; 1936 1937 // use priority queue to merge leaves 1938 while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) )//&& 1939 //(mergeQueue.top().GetMergeCost() < 1940 //mMergeMaxCostRatio / BspMergeCandidate::sOverallCost)) 1941 { 1942 Debug << "mergecost: " << mergeQueue.top().GetMergeCost() << " " << mMergeMaxCostRatio << endl; 1943 BspMergeCandidate mc = mergeQueue.top(); 1944 mergeQueue.pop(); 1945 1946 // both view cells equal! 1947 if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) 1948 continue; 1949 1950 if (mc.Valid()) 1951 { 1952 ViewCell::NewMail(); 1953 MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2()); 1954 1955 ++ merged; 1956 -- vcSize; 1957 // increase absolute merge cost 1958 BspMergeCandidate::sOverallCost += mc.GetMergeCost(); 1959 } 1960 // merge candidate not valid, because one of the leaves was already 1961 // merged with another one 1962 else 1963 { 1964 // validate and reinsert into queue 1965 mc.SetValid(); 1966 mergeQueue.push(mc); 1967 //Debug << "validate " << mc.GetMergeCost() << endl; 1968 } 1969 } 1970 1971 // collapse tree according to view cell partition 1972 //CollapseTree(mRoot); 1973 1974 // revalidate leaves 1975 //ValidateViewCellLeaves(); 1976 1977 //Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl; 1978 1979 //TODO: should return sample contributions 1980 return merged; 1981 } 1982 1983 1984 bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) 1985 { 1986 //-- change pointer to view cells of all leaves associated 1987 //-- with the previous view cells 1988 BspViewCell *fVc = l1->GetViewCell(); 1989 BspViewCell *bVc = l2->GetViewCell(); 1990 1991 BspViewCell *vc = dynamic_cast<BspViewCell *>( 1992 mViewCellsManager->MergeViewCells(*fVc, *bVc)); 1993 1994 // if merge was unsuccessful 1995 if (!vc) return false; 1996 1997 // set new size of view cell 1998 vc->SetArea(fVc->GetVolume() + bVc->GetVolume()); 1999 2000 vector<BspLeaf *> fLeaves = fVc->mLeaves; 2001 vector<BspLeaf *> bLeaves = bVc->mLeaves; 2002 2003 vector<BspLeaf *>::const_iterator it; 2004 2005 //-- change view cells of all the other leaves the view cell belongs to 2006 for (it = fLeaves.begin(); it != fLeaves.end(); ++ it) 2007 { 2008 (*it)->SetViewCell(vc); 2009 vc->mLeaves.push_back(*it); 2010 } 2011 2012 for (it = bLeaves.begin(); it != bLeaves.end(); ++ it) 2013 { 2014 (*it)->SetViewCell(vc); 2015 vc->mLeaves.push_back(*it); 2016 } 2017 2018 vc->Mail(); 2019 2020 // clean up old view cells 2021 DEL_PTR(fVc); 2022 DEL_PTR(bVc); 2023 2024 return true; 2025 } 2026 2027 2028 void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm) 2029 { 2030 mViewCellsManager = vcm; 2031 } 2032 2033 /************************************************************************/ 2034 /* BspMergeCandidate implementation */ 2035 /************************************************************************/ 2036 2037 2038 BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2): 2039 mMergeCost(0), 2040 mLeaf1(l1), 2041 mLeaf2(l2), 2042 mLeaf1Id(l1->GetViewCell()->mMailbox), 2043 mLeaf2Id(l2->GetViewCell()->mMailbox) 2044 { 2045 EvalMergeCost(); 2046 } 2047 2048 float BspMergeCandidate::GetLeaf1Cost() const 2049 { 2050 BspViewCell *vc = mLeaf1->GetViewCell(); 2051 return vc->GetPvs().GetSize() * vc->GetArea(); 2052 } 2053 2054 float BspMergeCandidate::GetLeaf2Cost() const 2055 { 2056 BspViewCell *vc = mLeaf2->GetViewCell(); 2057 return vc->GetPvs().GetSize() * vc->GetVolume(); 2058 } 2059 2060 void BspMergeCandidate::EvalMergeCost() 2061 { 2062 //-- compute pvs difference 2063 BspViewCell *vc1 = mLeaf1->GetViewCell(); 2064 BspViewCell *vc2 = mLeaf2->GetViewCell(); 2065 2066 const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs()); 2067 const int vcPvs = diff1 + vc1->GetPvs().GetSize(); 2068 2069 //-- compute ratio of old cost 2070 //-- (added size of left and right view cell times pvs size) 2071 //-- to new rendering cost (size of merged view cell times pvs size) 2072 const float oldCost = GetLeaf1Cost() + GetLeaf2Cost(); 2073 2074 const float newCost = 2075 (float)vcPvs * (vc1->GetArea() + vc2->GetArea()); 2076 2077 mMergeCost = newCost - oldCost; 2078 2079 // if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large 2080 // mMergeCost += 1.0; 2081 } 2082 2083 void BspMergeCandidate::SetLeaf1(BspLeaf *l) 2084 { 2085 mLeaf1 = l; 2086 } 2087 2088 void BspMergeCandidate::SetLeaf2(BspLeaf *l) 2089 { 2090 mLeaf2 = l; 2091 } 2092 2093 BspLeaf *BspMergeCandidate::GetLeaf1() 2094 { 2095 return mLeaf1; 2096 } 2097 2098 BspLeaf *BspMergeCandidate::GetLeaf2() 2099 { 2100 return mLeaf2; 2101 } 2102 2103 bool BspMergeCandidate::Valid() const 2104 { 2105 return 2106 (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) && 2107 (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id); 2108 } 2109 2110 float BspMergeCandidate::GetMergeCost() const 2111 { 2112 return mMergeCost; 2113 } 2114 2115 void BspMergeCandidate::SetValid() 2116 { 2117 mLeaf1Id = mLeaf1->GetViewCell()->mMailbox; 2118 mLeaf2Id = mLeaf2->GetViewCell()->mMailbox; 2119 2120 EvalMergeCost(); 2121 }
Note: See TracChangeset
for help on using the changeset viewer.