![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
Changeset 441 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
- Timestamp:
- 12/01/05 18:50:06 (19 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
r440 r441 263 263 /****************************************************************/ 264 264 265 BspTree::BspTree(BspViewCell *viewCell): 266 mRootCell(viewCell), 265 BspTree::BspTree(): 267 266 mRoot(NULL), 268 267 mStoreLeavesWithRays(false), 269 mPvsUse Area(true),268 mPvsUseLen(false), 270 269 mGenerateViewCells(true) 271 270 { 272 271 Randomize(); // initialise random generator for heuristics 272 273 // the view cell corresponding to unbounded space 274 mRootCell = new BspViewCell(); 273 275 274 276 //-- termination criteria for autopartition … … 307 309 environment->GetIntValue("BspTree.splitPlaneStrategy", mSplitPlaneStrategy); 308 310 environment->GetFloatValue("BspTree.AxisAligned.splitBorder", mSplitBorder); 311 environment->GetIntValue("BspTree.maxTests", mMaxTests); 309 312 310 313 environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance); 311 314 Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance; 312 315 313 // post processing stuff314 environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);315 environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);316 environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);317 316 318 317 Debug << "BSP max depth: " << mTermMaxDepth << endl; … … 410 409 { 411 410 DEL_PTR(mRoot); 411 DEL_PTR(mRootCell); 412 } 413 414 BspViewCell *BspTree::GetRootCell() const 415 { 416 return mRootCell; 412 417 } 413 418 … … 433 438 mRoot = new BspLeaf(); 434 439 435 tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0,436 mBox.SurfaceArea(), new BspNodeGeometry()));440 tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, 441 new BoundedRayContainer(), 0)); 437 442 438 443 while (!tStack.empty()) … … 470 475 mRootCell, 471 476 tData.mRays, 472 tData.mPvs, 473 mBox.SurfaceArea(), 474 new BspNodeGeometry()); 477 tData.mPvs); 475 478 476 479 BspTraversalData backData(interior->GetBack(), … … 479 482 mRootCell, 480 483 tData.mRays, 481 tData.mPvs, 482 mBox.SurfaceArea(), 483 new BspNodeGeometry()); 484 tData.mPvs); 484 485 485 486 if (!mGenerateViewCells) … … 735 736 736 737 BspTraversalData tData(mRoot, polys, 0, mRootCell, rays, 737 ComputePvsSize(*rays) , cell->GetArea(), cell);738 ComputePvsSize(*rays)); 738 739 739 740 tStack.push(tData); … … 755 756 } 756 757 758 Debug << "here2" << endl; 757 759 cout << "finished\n"; 758 760 … … 766 768 ((int)data.mRays->size() <= mTermMinRays) || 767 769 (data.mPvs <= mTermMinPvs) || 768 (data.mArea <= mTermMinArea) ||769 770 (data.mDepth >= mTermMaxDepth) || 770 771 (data.GetAvgRayContribution() < mTermMaxRayContribution)); … … 815 816 DEL_PTR(tData.mPolygons); 816 817 DEL_PTR(tData.mRays); 817 DEL_PTR(tData.mGeometry); 818 818 819 819 return leaf; 820 820 } … … 824 824 825 825 BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 826 new BoundedRayContainer(), 0 , 0, new BspNodeGeometry());826 new BoundedRayContainer(), 0); 827 827 BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 828 new BoundedRayContainer(), 0 , 0, new BspNodeGeometry());828 new BoundedRayContainer(), 0); 829 829 830 830 // create new interior node and two leaf nodes … … 860 860 DEL_PTR(tData.mPolygons); 861 861 DEL_PTR(tData.mRays); 862 DEL_PTR(tData.mGeometry); 863 862 864 863 return interior; 865 864 } … … 901 900 902 901 BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 902 903 Debug << "*********************" << endl; 904 long startTime = GetTime(); 905 903 906 // select subdivision plane 904 907 BspInterior *interior = 905 908 new BspInterior(SelectPlane(leaf, tData)); 906 909 Debug << "time used for split plane selection: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 907 910 #ifdef _DEBUG 908 911 Debug << interior << endl; 909 912 #endif 910 913 914 915 Debug << "number of rays: " << tData.mRays->size() << endl; 916 Debug << "number of polys: " << tData.mPolygons->size() << endl; 917 918 startTime = GetTime(); 919 911 920 // subdivide rays into front and back rays 912 921 SplitRays(interior->mPlane, *tData.mRays, *frontData.mRays, *backData.mRays); 913 922 923 Debug << "time used for rays splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 924 925 startTime = GetTime(); 914 926 // subdivide polygons with plane 915 927 mStat.splits += interior->SplitPolygons(*tData.mPolygons, … … 918 930 coincident); 919 931 932 Debug << "time used for polygon splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 933 920 934 // compute pvs 921 935 frontData.mPvs = ComputePvsSize(*frontData.mRays); 922 936 backData.mPvs = ComputePvsSize(*backData.mRays); 923 924 // split geometry and compute area925 if (1)926 {927 tData.mGeometry->SplitGeometry(*frontData.mGeometry,928 *backData.mGeometry,929 *this,930 interior->mPlane);931 932 933 frontData.mArea = frontData.mGeometry->GetArea();934 backData.mArea = backData.mGeometry->GetArea();935 }936 937 937 938 // compute accumulated ray length … … 1308 1309 const int frontAndBackId = ViewCell::sMailId; 1309 1310 1310 PolygonContainer::const_iterator it, it_end = polys.end(); 1311 1312 for (it = polys.begin(); it != it_end; ++ it) 1313 { 1314 const int classification = (*it)->ClassifyPlane(candidatePlane); 1311 bool useRand;; 1312 int limit; 1313 1314 // choose test polyongs randomly if over threshold 1315 if ((int)polys.size() > mMaxTests) 1316 { 1317 useRand = true; 1318 limit = mMaxTests; 1319 } 1320 else 1321 { 1322 useRand = false; 1323 limit = (int)polys.size(); 1324 } 1325 1326 1327 for (int i = 0; i < limit; ++ i) 1328 { 1329 const int testIdx = useRand ? Random(limit) : i; 1330 1331 Polygon3 *poly = polys[testIdx]; 1332 1333 const int classification = poly->ClassifyPlane(candidatePlane); 1315 1334 1316 1335 if (mSplitPlaneStrategy & BALANCED_POLYS) … … 1323 1342 { 1324 1343 if (classification == Polygon3::COINCIDENT) 1325 sumPolyArea += (*it)->GetArea();1344 sumPolyArea += poly->GetArea(); 1326 1345 //totalArea += area; 1327 1346 } … … 1329 1348 if (mSplitPlaneStrategy & BLOCKED_RAYS) 1330 1349 { 1331 const float blockedRays = (float) (*it)->mPiercingRays.size();1350 const float blockedRays = (float)poly->mPiercingRays.size(); 1332 1351 1333 1352 if (classification == Polygon3::COINCIDENT) … … 1340 1359 if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS) 1341 1360 { 1342 MeshInstance *viewCell = (*it)->mParent;1361 MeshInstance *viewCell = poly->mParent; 1343 1362 1344 1363 // assure that we only count a view cell … … 1434 1453 float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 1435 1454 const BoundedRayContainer &rays, 1436 const int pvs, 1437 const float area, 1438 const BspNodeGeometry &cell) const 1455 const int pvs) const 1439 1456 { 1440 1457 float val = 0; … … 1442 1459 float sumBalancedRays = 0; 1443 1460 float sumRaySplits = 0; 1444 1445 int backId = 0;1446 int frontId = 0;1447 int frontAndBackId = 0;1448 1461 1449 1462 int frontPvs = 0; … … 1451 1464 1452 1465 // probability that view point lies in child 1453 float pOverall = 0;1454 float pFront = 0 ;1455 float pBack = 0 ;1466 float pOverall = 1; 1467 float pFront = 0.5; 1468 float pBack = 0.5; 1456 1469 1457 1470 if (mSplitPlaneStrategy & PVS) … … 1459 1472 // create unique ids for pvs heuristics 1460 1473 GenerateUniqueIdsForPvs(); 1461 1462 if (mPvsUseArea) // use front and back cell areas to approximate volume1463 {1464 // construct child geometry with regard to the candidate split plane1465 BspNodeGeometry frontCell;1466 BspNodeGeometry backCell;1467 1468 cell.SplitGeometry(frontCell, backCell, *this, candidatePlane);1469 1470 pFront = frontCell.GetArea();1471 pBack = backCell.GetArea();1472 1473 pOverall = area;1474 }1475 1474 } 1476 1475 1477 BoundedRayContainer::const_iterator rit, rit_end = rays.end(); 1478 1479 for (rit = rays.begin(); rit != rays.end(); ++ rit) 1480 { 1481 Ray *ray = (*rit)->mRay; 1482 const float minT = (*rit)->mMinT; 1483 const float maxT = (*rit)->mMaxT; 1476 bool useRand;; 1477 int limit; 1478 1479 // choose test polyongs randomly if over threshold 1480 if ((int)rays.size() > mMaxTests) 1481 { 1482 useRand = true; 1483 limit = mMaxTests; 1484 } 1485 else 1486 { 1487 useRand = false; 1488 limit = (int)rays.size(); 1489 } 1490 1491 for (int i = 0; i < limit; ++ i) 1492 { 1493 const int testIdx = useRand ? Random(limit) : i; 1494 1495 BoundedRay *bRay = rays[testIdx]; 1496 1497 Ray *ray = bRay->mRay; 1498 const float minT = bRay->mMinT; 1499 const float maxT = bRay->mMaxT; 1484 1500 1485 1501 Vector3 entP, extP; … … 1511 1527 AddObjToPvs(ray->sourceObject.mObject, cf, frontPvs, backPvs); 1512 1528 1513 if (!mPvsUseArea) // use front and back cell areas to approximate volume 1514 { 1515 float len = Distance(entP, extP); 1516 pOverall += len; 1517 1518 // use length of rays to approximate volume 1519 switch (cf) 1529 float len = 1; 1530 if (0){ 1531 if (mPvsUseLen) 1532 len = SqrDistance(entP, extP); 1533 1534 // use length of rays to approximate volume 1535 if (Ray::BACK && Ray::COINCIDENT) 1536 pBack += len; 1537 if (Ray::FRONT && Ray::COINCIDENT) 1538 pFront += len; 1539 if (Ray::FRONT_BACK || Ray::BACK_FRONT) 1540 { 1541 if (mPvsUseLen) 1520 1542 { 1521 case Ray::COINCIDENT: 1522 pBack += len; 1523 pFront += len; 1524 break; 1525 case Ray::BACK: 1526 pBack += len; 1527 break; 1528 case Ray::FRONT: 1529 pFront += len; 1530 break; 1531 case Ray::FRONT_BACK: 1532 { 1533 // find intersection of ray segment with plane 1534 const Vector3 extp = ray->Extrap(maxT); 1535 const float t = candidatePlane.FindT(ray->GetLoc(), extp); 1536 1537 const float newT = t * maxT; 1538 float newLen = Distance(ray->Extrap(newT), extp); 1539 1540 pFront += len - newLen; 1541 pBack += newLen; 1542 } 1543 break; 1544 case Ray::BACK_FRONT: 1545 { 1546 // find intersection of ray segment with plane 1547 const Vector3 extp = ray->Extrap(maxT); 1548 const float t = candidatePlane.FindT(ray->GetLoc(), extp); 1549 1550 const float newT = t * maxT; 1551 float newLen = Distance(ray->Extrap(newT), extp); 1552 1553 pFront += len; 1554 pBack += len - newLen; 1555 } 1556 break; 1557 default: 1558 Debug << "Should not come here 2" << endl; 1559 break; 1543 const Vector3 extp = ray->Extrap(maxT); 1544 const float t = candidatePlane.FindT(ray->GetLoc(), extp); 1545 1546 const float newT = t * maxT; 1547 const float newLen = SqrDistance(ray->Extrap(newT), extp); 1548 1549 if (Ray::FRONT_BACK) 1550 { 1551 pFront += len - newLen; 1552 pBack += newLen; 1553 } 1554 else 1555 { 1556 pBack += len - newLen; 1557 pFront += newLen; 1558 } 1560 1559 } 1561 } 1560 else 1561 { 1562 ++ pFront; 1563 ++ pBack; 1564 } 1565 }} 1562 1566 } 1563 1567 } … … 1572 1576 1573 1577 float denom = pOverall * (float)pvs * 2.0f + Limits::Small; 1574 if ((mSplitPlaneStrategy & PVS) && area && pvs) 1578 1579 if (mSplitPlaneStrategy & PVS) 1575 1580 { 1576 1581 val += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / denom; 1577 1582 1578 1583 // give penalty to unbalanced split 1579 if ( 0)1584 if (1) 1580 1585 if (((pFront * 0.2 + Limits::Small) > pBack) || (pFront < (pBack * 0.2 + Limits::Small))) 1581 1586 val += 0.5; 1582 1587 } 1583 1588 1589 1584 1590 #ifdef _DEBUG 1585 1591 Debug << "totalpvs: " << pvs << " ptotal: " << pOverall … … 1664 1670 (mSplitPlaneStrategy & PVS)) 1665 1671 { 1666 val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs, 1667 data.mArea, *data.mGeometry); 1672 val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs); 1668 1673 } 1669 1674 … … 1736 1741 ++ mStat.maxRayContribNodes; 1737 1742 1738 if (data.mGeometry->GetArea() <= mTermMinArea)1739 ++ mStat.minAreaNodes;1743 //if (data.mGeometry->GetArea() <= mTermMinArea) 1744 // ++ mStat.minAreaNodes; 1740 1745 1741 1746 #ifdef _DEBUG … … 1950 1955 } 1951 1956 } 1952 1953 bool BspTree::MergeViewCells(BspLeaf *front, BspLeaf *back) const1954 {1955 BspViewCell *viewCell =1956 NULL;//todo dynamic_cast<BspViewCell *>(ViewCell::Merge(*front->mViewCell, *back->mViewCell));1957 1958 if (!viewCell)1959 return false;1960 1961 // change view cells of all leaves associated with the1962 // previous view cells1963 1964 BspViewCell *fVc = front->mViewCell;1965 BspViewCell *bVc = back->mViewCell;1966 1967 vector<BspLeaf *> fLeaves = fVc->mBspLeaves;1968 vector<BspLeaf *> bLeaves = bVc->mBspLeaves;1969 1970 vector<BspLeaf *>::const_iterator it;1971 1972 for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)1973 {1974 (*it)->SetViewCell(viewCell);1975 viewCell->mBspLeaves.push_back(*it);1976 }1977 for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)1978 {1979 (*it)->SetViewCell(viewCell);1980 viewCell->mBspLeaves.push_back(*it);1981 }1982 1983 DEL_PTR(fVc);1984 DEL_PTR(bVc);1985 1986 return true;1987 }1988 1989 bool BspTree::ShouldMerge(BspLeaf *front, BspLeaf *back) const1990 {1991 ViewCell *fvc = front->mViewCell;1992 ViewCell *bvc = back->mViewCell;1993 1994 if ((fvc == mRootCell) || (bvc == mRootCell) || (fvc == bvc))1995 return false;1996 1997 int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());1998 1999 if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)2000 {2001 if ((fvc->GetPvs().GetSize() < mMinPvs) ||2002 (bvc->GetPvs().GetSize() < mMinPvs) ||2003 ((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))2004 {2005 return true;2006 }2007 }2008 2009 return false;2010 }2011 2012 1957 2013 1958 BspTreeStatistics &BspTree::GetStat() … … 2457 2402 if (frontPoly->Valid()) 2458 2403 front.mPolys.push_back(frontPoly); 2404 else 2405 DEL_PTR(frontPoly); 2406 2459 2407 if (backPoly->Valid()) 2460 2408 back.mPolys.push_back(backPoly); 2409 else 2410 DEL_PTR(backPoly); 2461 2411 } 2462 2412 … … 2510 2460 2511 2461 planePoly->Split(plane, *frontPoly, *backPoly); 2462 2463 // don't need anymore 2512 2464 DEL_PTR(planePoly); 2513 2465 DEL_PTR(frontPoly); 2466 2467 // back polygon is belonging to geometry 2514 2468 if (backPoly->Valid()) 2515 2469 planePoly = backPoly;
Note: See TracChangeset
for help on using the changeset viewer.
