Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 440)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 441)
@@ -263,12 +263,14 @@
 /****************************************************************/
 
-BspTree::BspTree(BspViewCell *viewCell): 
-mRootCell(viewCell), 
+BspTree::BspTree():  
 mRoot(NULL), 
 mStoreLeavesWithRays(false),
-mPvsUseArea(true),
+mPvsUseLen(false),
 mGenerateViewCells(true)
 {
 	Randomize(); // initialise random generator for heuristics
+
+	// the view cell corresponding to unbounded space
+	mRootCell = new BspViewCell();
 
 	//-- termination criteria for autopartition
@@ -307,12 +309,9 @@
 	environment->GetIntValue("BspTree.splitPlaneStrategy", mSplitPlaneStrategy);
 	environment->GetFloatValue("BspTree.AxisAligned.splitBorder", mSplitBorder);
+	environment->GetIntValue("BspTree.maxTests", mMaxTests);
 
 	environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
 	Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
 
-	// post processing stuff
-	environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);
-	environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);
-	environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);
 
     Debug << "BSP max depth: " << mTermMaxDepth << endl;
@@ -410,4 +409,10 @@
 {
 	DEL_PTR(mRoot);
+	DEL_PTR(mRootCell);
+}
+
+BspViewCell *BspTree::GetRootCell() const
+{
+	return mRootCell;
 }
 
@@ -433,6 +438,6 @@
 		mRoot = new BspLeaf();
 
-	tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0, 
-								 mBox.SurfaceArea(), new BspNodeGeometry()));
+	tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, 
+		new BoundedRayContainer(), 0));
 
 	while (!tStack.empty())
@@ -470,7 +475,5 @@
 										   mRootCell,	
 										   tData.mRays,
-										   tData.mPvs,
-										   mBox.SurfaceArea(),
-										   new BspNodeGeometry());
+										   tData.mPvs);
 
 				BspTraversalData backData(interior->GetBack(), 
@@ -479,7 +482,5 @@
 										  mRootCell,	
 										  tData.mRays,
-										  tData.mPvs,
-										  mBox.SurfaceArea(),
-										  new BspNodeGeometry());
+										  tData.mPvs);
 
 				if (!mGenerateViewCells)
@@ -735,5 +736,5 @@
 
 	BspTraversalData tData(mRoot, polys, 0, mRootCell, rays, 
-						   ComputePvsSize(*rays), cell->GetArea(), cell);
+						   ComputePvsSize(*rays));
 
 	tStack.push(tData);
@@ -755,4 +756,5 @@
 	}
 
+	Debug << "here2" << endl;
 	cout << "finished\n";
 
@@ -766,5 +768,4 @@
 		 ((int)data.mRays->size() <= mTermMinRays) ||
 		 (data.mPvs <= mTermMinPvs) ||
-		 (data.mArea <= mTermMinArea) ||
 		 (data.mDepth >= mTermMaxDepth) ||
 		 (data.GetAvgRayContribution() < mTermMaxRayContribution));
@@ -815,6 +816,5 @@
 		DEL_PTR(tData.mPolygons);
 		DEL_PTR(tData.mRays);
-		DEL_PTR(tData.mGeometry);
-		
+			
 		return leaf;
 	}
@@ -824,7 +824,7 @@
 	
 	BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 
-								new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
+								new BoundedRayContainer(), 0);
 	BspTraversalData tBackData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell, 
-							   new BoundedRayContainer(), 0, 0, new BspNodeGeometry());
+							   new BoundedRayContainer(), 0);
 
 	// create new interior node and two leaf nodes
@@ -860,6 +860,5 @@
 	DEL_PTR(tData.mPolygons);
 	DEL_PTR(tData.mRays);
-	DEL_PTR(tData.mGeometry);		
-
+	
 	return interior;
 }
@@ -901,15 +900,28 @@
 	
 	BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+
+	Debug << "*********************" << endl;
+	long startTime = GetTime();
+	
 	// select subdivision plane
 	BspInterior *interior = 
 		new BspInterior(SelectPlane(leaf, tData)); 
-
+	Debug << "time used for split plane selection: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 #ifdef _DEBUG
 	Debug << interior << endl;
 #endif
 	
+
+	Debug << "number of rays: " << tData.mRays->size() << endl;
+	Debug << "number of polys: " << tData.mPolygons->size() << endl;
+
+	startTime = GetTime();
+	
 	// subdivide rays into front and back rays
 	SplitRays(interior->mPlane, *tData.mRays, *frontData.mRays, *backData.mRays);
 	
+	Debug << "time used for rays splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+
+	startTime = GetTime();
 	// subdivide polygons with plane
 	mStat.splits += interior->SplitPolygons(*tData.mPolygons, 
@@ -918,20 +930,9 @@
 											coincident);
 
+	Debug << "time used for polygon splitting: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+
     // compute pvs
 	frontData.mPvs = ComputePvsSize(*frontData.mRays);
 	backData.mPvs = ComputePvsSize(*backData.mRays);
-
-	// split geometry and compute area
-	if (1)
-	{
-		tData.mGeometry->SplitGeometry(*frontData.mGeometry, 
-									   *backData.mGeometry, 
-									   *this, 
-									   interior->mPlane);
-	
-		
-		frontData.mArea = frontData.mGeometry->GetArea();
-		backData.mArea = backData.mGeometry->GetArea();
-	}
 
 	// compute accumulated ray length
@@ -1308,9 +1309,27 @@
 	const int frontAndBackId = ViewCell::sMailId;
 
-	PolygonContainer::const_iterator it, it_end = polys.end();
-
-	for (it = polys.begin(); it != it_end; ++ it)
-	{
-		const int classification = (*it)->ClassifyPlane(candidatePlane);
+	bool useRand;;
+	int limit;
+
+	// choose test polyongs randomly if over threshold
+	if ((int)polys.size() > mMaxTests)
+	{
+		useRand = true;
+		limit = mMaxTests;
+	}
+	else
+	{
+		useRand = false;
+		limit = (int)polys.size();
+	}
+	
+
+	for (int i = 0; i < limit; ++ i)
+	{
+		const int testIdx = useRand ? Random(limit) : i;
+
+		Polygon3 *poly = polys[testIdx];
+
+        const int classification = poly->ClassifyPlane(candidatePlane);
 
 		if (mSplitPlaneStrategy & BALANCED_POLYS)
@@ -1323,5 +1342,5 @@
 		{
 			if (classification == Polygon3::COINCIDENT)
-				sumPolyArea += (*it)->GetArea();
+				sumPolyArea += poly->GetArea();
 			//totalArea += area;
 		}
@@ -1329,5 +1348,5 @@
 		if (mSplitPlaneStrategy & BLOCKED_RAYS)
 		{
-			const float blockedRays = (float)(*it)->mPiercingRays.size();
+			const float blockedRays = (float)poly->mPiercingRays.size();
 		
 			if (classification == Polygon3::COINCIDENT)
@@ -1340,5 +1359,5 @@
 		if (mSplitPlaneStrategy & BALANCED_VIEW_CELLS)
 		{
-			MeshInstance *viewCell = (*it)->mParent;
+			MeshInstance *viewCell = poly->mParent;
 		
 			// assure that we only count a view cell 
@@ -1434,7 +1453,5 @@
 float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
 							  const BoundedRayContainer &rays,
-							  const int pvs,
-							  const float area,
-							  const BspNodeGeometry &cell) const
+							  const int pvs) const
 {
 	float val = 0;
@@ -1442,8 +1459,4 @@
 	float sumBalancedRays = 0;
 	float sumRaySplits = 0;
-	
-	int backId = 0;
-	int frontId = 0;
-	int frontAndBackId = 0;
 
 	int frontPvs = 0;
@@ -1451,7 +1464,7 @@
 
 	// probability that view point lies in child
-	float pOverall = 0;
-	float pFront = 0;
-	float pBack = 0;
+	float pOverall = 1;
+	float pFront = 0.5;
+	float pBack = 0.5;
 
 	if (mSplitPlaneStrategy & PVS)
@@ -1459,27 +1472,30 @@
 		// create unique ids for pvs heuristics
 		GenerateUniqueIdsForPvs();
-
-		if (mPvsUseArea) // use front and back cell areas to approximate volume
-		{	
-			// construct child geometry with regard to the candidate split plane
-			BspNodeGeometry frontCell;
-			BspNodeGeometry backCell;
-
-			cell.SplitGeometry(frontCell, backCell, *this, candidatePlane);
-		
-			pFront = frontCell.GetArea();
-			pBack = backCell.GetArea();
-
-			pOverall = area;
-		}
 	}
 			
-	BoundedRayContainer::const_iterator rit, rit_end = rays.end();
-
-	for (rit = rays.begin(); rit != rays.end(); ++ rit)
-	{
-		Ray *ray = (*rit)->mRay;
-		const float minT = (*rit)->mMinT;
-		const float maxT = (*rit)->mMaxT;
+	bool useRand;;
+	int limit;
+
+	// choose test polyongs randomly if over threshold
+	if ((int)rays.size() > mMaxTests)
+	{
+		useRand = true;
+		limit = mMaxTests;
+	}
+	else
+	{
+		useRand = false;
+		limit = (int)rays.size();
+	}
+
+	for (int i = 0; i < limit; ++ i)
+	{
+		const int testIdx = useRand ? Random(limit) : i;
+	
+		BoundedRay *bRay = rays[testIdx];
+
+		Ray *ray = bRay->mRay;
+		const float minT = bRay->mMinT;
+		const float maxT = bRay->mMaxT;
 
 		Vector3 entP, extP;
@@ -1511,53 +1527,41 @@
 			AddObjToPvs(ray->sourceObject.mObject, cf, frontPvs, backPvs);
 			
-			if (!mPvsUseArea) // use front and back cell areas to approximate volume
-			{	
-				float len = Distance(entP, extP);
-				pOverall += len;
-
-				// use length of rays to approximate volume
-				switch (cf)
+			float len = 1;
+			if (0){
+			if (mPvsUseLen)
+				len = SqrDistance(entP, extP);
+							
+			// use length of rays to approximate volume
+			if (Ray::BACK && Ray::COINCIDENT)
+				pBack += len;
+			if (Ray::FRONT && Ray::COINCIDENT)
+				pFront += len;
+			if (Ray::FRONT_BACK || Ray::BACK_FRONT)
+			{
+				if (mPvsUseLen)
 				{
-					case Ray::COINCIDENT:
-						pBack += len;
-						pFront += len;						
-						break;
-					case Ray::BACK:
-						pBack += len;
-						break;
-					case Ray::FRONT:
-						pFront += len;
-						break;
-					case Ray::FRONT_BACK:
-						{
-							// find intersection of ray segment with plane
-							const Vector3 extp = ray->Extrap(maxT);
-							const float t = candidatePlane.FindT(ray->GetLoc(), extp);
-					
-							const float newT = t * maxT;
-							float newLen = Distance(ray->Extrap(newT), extp);
-
-							pFront += len - newLen;
-							pBack += newLen;
-						}
-						break;
-					case Ray::BACK_FRONT:
-						{
-							// find intersection of ray segment with plane
-							const Vector3 extp = ray->Extrap(maxT);
-							const float t = candidatePlane.FindT(ray->GetLoc(), extp);
-					
-							const float newT = t * maxT;
-							float newLen = Distance(ray->Extrap(newT), extp);
-
-							pFront += len;
-							pBack += len - newLen;
-						}
-						break;
-					default:
-						Debug << "Should not come here 2" << endl;
-						break;
+					const Vector3 extp = ray->Extrap(maxT);
+					const float t = candidatePlane.FindT(ray->GetLoc(), extp);
+				
+					const float newT = t * maxT;
+					const float newLen = SqrDistance(ray->Extrap(newT), extp);
+
+					if (Ray::FRONT_BACK)
+					{
+						pFront += len - newLen;
+						pBack += newLen;
+					}
+					else
+					{
+						pBack += len - newLen;
+						pFront += newLen;
+					}
 				}
-			}
+				else
+				{
+					++ pFront;
+					++ pBack;
+				}
+			}}
 		}
 	}
@@ -1572,14 +1576,16 @@
 
 	float denom = pOverall * (float)pvs * 2.0f + Limits::Small;
-	if ((mSplitPlaneStrategy & PVS) && area && pvs)
+
+	if (mSplitPlaneStrategy & PVS)
 	{
 		val += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / denom;
 
 		// give penalty to unbalanced split
-		if (0)
+		if (1)
 		if (((pFront * 0.2 + Limits::Small) > pBack) || (pFront < (pBack * 0.2 + Limits::Small)))
 			val += 0.5;
 	}
 
+	
 #ifdef _DEBUG
 	Debug << "totalpvs: " << pvs << " ptotal: " << pOverall
@@ -1664,6 +1670,5 @@
 		(mSplitPlaneStrategy & PVS))
 	{
-		val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs, 
-							  data.mArea, *data.mGeometry);
+		val += SplitPlaneCost(candidatePlane, *data.mRays, data.mPvs);
 	}
 
@@ -1736,6 +1741,6 @@
 		++ mStat.maxRayContribNodes;
 	
-	if (data.mGeometry->GetArea() <= mTermMinArea) 
-		++ mStat.minAreaNodes;
+	//if (data.mGeometry->GetArea() <= mTermMinArea) 
+	//	++ mStat.minAreaNodes;
 
 #ifdef _DEBUG
@@ -1950,64 +1955,4 @@
 	}
 }
-
-bool BspTree::MergeViewCells(BspLeaf *front, BspLeaf *back) const
-{
-	BspViewCell *viewCell = 
-NULL;//todo		dynamic_cast<BspViewCell *>(ViewCell::Merge(*front->mViewCell, *back->mViewCell));
-	
-	if (!viewCell)
-		return false;
-
-	// change view cells of all leaves associated with the
-	// previous view cells
-
-	BspViewCell *fVc = front->mViewCell;
-	BspViewCell *bVc = back->mViewCell;
-
-	vector<BspLeaf *> fLeaves = fVc->mBspLeaves;
-	vector<BspLeaf *> bLeaves = bVc->mBspLeaves;
-
-	vector<BspLeaf *>::const_iterator it;
-	
-	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
-	{
-		(*it)->SetViewCell(viewCell);
-		viewCell->mBspLeaves.push_back(*it);
-	}
-	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
-	{
-		(*it)->SetViewCell(viewCell);
-		viewCell->mBspLeaves.push_back(*it);
-	}
-	
-	DEL_PTR(fVc);
-	DEL_PTR(bVc);
-
-	return true;
-}
-
-bool BspTree::ShouldMerge(BspLeaf *front, BspLeaf *back) const
-{
-	ViewCell *fvc = front->mViewCell;
-	ViewCell *bvc = back->mViewCell;
-
-	if ((fvc == mRootCell) || (bvc == mRootCell) || (fvc == bvc))
-		return false;
-
-	int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
-
-	if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
-	{
-		if ((fvc->GetPvs().GetSize() < mMinPvs) ||	
-			(bvc->GetPvs().GetSize() < mMinPvs) ||
-			((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
-		{
-			return true;
-		}
-	}
-	
-	return false;
-}
-
 
 BspTreeStatistics &BspTree::GetStat()
@@ -2457,6 +2402,11 @@
 					if (frontPoly->Valid())
 						front.mPolys.push_back(frontPoly);
+					else
+						DEL_PTR(frontPoly);
+
 					if (backPoly->Valid())
 						back.mPolys.push_back(backPoly);
+					else
+						DEL_PTR(backPoly);
 				}
 				
@@ -2510,6 +2460,10 @@
 
 					planePoly->Split(plane, *frontPoly, *backPoly);
+					
+					// don't need anymore
 					DEL_PTR(planePoly);
-
+					DEL_PTR(frontPoly);
+
+					// back polygon is belonging to geometry
 					if (backPoly->Valid())
 						planePoly = backPoly;
