Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h	(revision 652)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h	(revision 653)
@@ -171,6 +171,9 @@
 		float mRenderCost;
 
+		VspBspSplitCandidate(): mRenderCost(0) 
+		{};
+
 		VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 
-		mSplitPlane(plane), mParentData(tData)
+		mSplitPlane(plane), mParentData(tData), mRenderCost(0)
 		{}
 
@@ -395,4 +398,7 @@
 								 const VspBspTraversalData &data) const;
 
+	void ConstructWithSplitQueueQueue(const PolygonContainer &polys, RayInfoContainer *rays);
+
+
 	/** Returns view cell corresponding to 
 		the invalid view space. If it does not exist, it is created.
@@ -424,4 +430,7 @@
 	BspNode *Subdivide(VspBspTraversalQueue &tStack, 
 					   VspBspTraversalData &tData);
+
+	BspNode *Subdivide(VspBspSplitQueue &tQueue,
+					   VspBspSplitCandidate &splitCandidate);
 
 	/** Constructs the tree from the given traversal data.
@@ -459,5 +468,5 @@
 							 float &pBack) const;
 
-	/** Subdivide leaf.
+	/** Subdivides leaf.
 		@param leaf the leaf to be subdivided
 		
@@ -473,8 +482,9 @@
 	*/
 
-	BspNode *SubdivideNode(VspBspTraversalData &tData,
-						   VspBspTraversalData &frontData,
-						   VspBspTraversalData &backData,
-						   PolygonContainer &coincident);
+	BspInterior *SubdivideNode(const Plane3 &splitPlane,
+							   VspBspTraversalData &tData,
+							   VspBspTraversalData &frontData,
+                               VspBspTraversalData &backData,
+							   PolygonContainer &coincident);
 
 	/** Extracts the meshes of the objects and adds them to polygons. 
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp	(revision 652)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp	(revision 653)
@@ -353,5 +353,6 @@
 	}
 	
-	Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
+	Debug << "maximal pvs (i.e., pvs still considered as valid) : " 
+		  << mViewCellsManager->GetMaxPvsSize() << endl;
 
 	//-- store rays
@@ -521,4 +522,109 @@
 
 
+
+void VspBspTree::ConstructWithSplitQueueQueue(const PolygonContainer &polys, 
+											  RayInfoContainer *rays)
+{
+	VspBspSplitQueue tQueue;
+
+	mRoot = new BspLeaf();
+
+	// constrruct root node geometry
+	BspNodeGeometry *geom = new BspNodeGeometry();
+	ConstructGeometry(mRoot, *geom);
+
+	const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
+
+	VspBspTraversalData tData(mRoot,
+							  new PolygonContainer(polys),
+							  0,
+							  rays,
+                              ComputePvsSize(*rays),
+							  prop,
+							  geom);
+
+	VspBspSplitCandidate splitCandidate;
+
+
+	EvalSplitCandidate(tData, splitCandidate);
+
+	tQueue.push(splitCandidate);
+
+
+	mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
+	mTotalPvsSize = tData.mPvs;
+	
+	mSubdivisionStats 
+			<< "#ViewCells\n1\n" <<  endl
+			<< "#RenderCostDecrease\n0\n" << endl 
+			<< "#TotalRenderCost\n" << mTotalCost << endl
+			<< "#AvgRenderCost\n" << mTotalPvsSize << endl;
+
+	Debug << "total cost: " << mTotalCost << endl;
+	
+	
+	mBspStats.Start();
+	cout << "Contructing vsp bsp tree ... \n";
+
+	long startTime = GetTime();	
+	int nLeaves = 0;
+	int nViewCells = 0;
+
+	// used for intermediate time measurements and progress
+	long interTime = GetTime();	
+
+	mOutOfMemory = false;
+
+	mCreatedViewCells = 0;
+	
+	while (!tQueue.empty())
+	{
+		splitCandidate = tQueue.top();
+	    tQueue.pop();		
+
+		if (0 && !mOutOfMemory)
+		{
+			float mem = GetMemUsage();
+
+			if (mem > mMaxMemory)
+			{
+				mOutOfMemory = true;
+				Debug << "memory limit reached: " << mem << endl;
+			}
+		}
+
+		// subdivide leaf node
+		BspNode *r = Subdivide(tQueue, splitCandidate);
+
+		if (r == mRoot)
+			Debug << "VSP BSP tree construction time spent at root: "
+				  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+
+		if (mBspStats.Leaves() == nLeaves)
+		{
+			nLeaves += 500;
+
+			cout << "leaves=" << mBspStats.Leaves() << endl;
+			Debug << "needed "
+				  << TimeDiff(interTime, GetTime())*1e-3 
+				  << " secs to create 500 view cells" << endl;
+			interTime = GetTime();
+		}
+
+		if (mCreatedViewCells == nViewCells)
+		{
+			nViewCells += 500;
+
+			cout << "generated " << mCreatedViewCells << " viewcells" << endl;
+		}
+	}
+
+	Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
+	cout << "finished\n";
+
+	mBspStats.Stop();
+}
+
+
 bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
 {
@@ -555,8 +661,38 @@
 		// create new interior node and two leaf nodes
 		// or return leaf as it is (if maxCostRatio missed)
-		newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
-
-		if (!newNode->IsLeaf()) //-- continue subdivision
-		{
+
+		int splitAxis;
+		bool splitFurther = true;
+		int maxCostMisses = tData.mMaxCostMisses;
+		
+		Plane3 splitPlane;
+		BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+
+		if (!SelectPlane(splitPlane, leaf, tData, tFrontData, tBackData, splitAxis))
+		{
+			++ maxCostMisses;
+
+			if (maxCostMisses > mTermMissTolerance)
+			{
+				// terminate branch because of max cost
+				++ mBspStats.maxCostNodes;
+				splitFurther = false;
+			}
+		}
+	
+		if (splitFurther) //-- continue subdivision
+		{
+			newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
+
+			if (splitAxis < 3)
+				++ mBspStats.splits[splitAxis];
+			else
+				++ mBspStats.polySplits;
+
+			tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && splitAxis < 3);
+			// how often was max cost ratio missed in this branch?
+			tFrontData.mMaxCostMisses = maxCostMisses;
+			tBackData.mMaxCostMisses = maxCostMisses;
+
 			if (1)
 			{
@@ -643,4 +779,120 @@
 
 
+BspNode *VspBspTree::Subdivide(VspBspSplitQueue &tQueue,
+							   VspBspSplitCandidate &splitCandidate)
+{
+	VspBspTraversalData &tData = splitCandidate.mParentData;
+
+	BspNode *newNode = tData.mNode;
+
+	if (!mOutOfMemory && !TerminationCriteriaMet(tData))
+	{
+		PolygonContainer coincident;
+
+		VspBspTraversalData tFrontData;
+		VspBspTraversalData tBackData;
+
+#if OCTREE_HACK
+		//Debug << "new axis:" << (tData.mAxis + 1) % 3 << endl;
+		tFrontData.mAxis = (tData.mAxis + 1) % 3;
+		tBackData.mAxis = (tData.mAxis + 1) % 3;
+#endif
+		//-- continue subdivision
+		// create new interior node and two leaf node
+		const Plane3 splitPlane = splitCandidate.mSplitPlane;
+			
+		newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
+
+#if 0 // TODO
+			if (splitAxis < 3)
+				++ mBspStats.splits[splitAxis];
+			else
+				++ mBspStats.polySplits;
+
+			tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && splitAxis < 3);
+			// how often was max cost ratio missed in this branch?
+			tFrontData.mMaxCostMisses = maxCostMisses;
+			tBackData.mMaxCostMisses = maxCostMisses;
+#endif
+		if (1)
+		{
+			float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+			float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+			float cData = (float)tData.mPvs * tData.mProbability;;
+
+			float costDecr = 
+				(cFront + cBack - cData) / mBox.GetVolume();
+
+			mTotalCost += costDecr;
+			mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
+
+			mSubdivisionStats 
+					<< "#ViewCells\n" << mBspStats.Leaves() << endl
+					<< "#RenderCostDecrease\n" << -costDecr << endl 
+					<< "#TotalRenderCost\n" << mTotalCost << endl
+					<< "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
+		}
+
+		//-- push the new split candidates on the stack
+		VspBspSplitCandidate frontCandidate;
+		VspBspSplitCandidate backCandidate;
+
+		EvalSplitCandidate(tData, frontCandidate);
+		EvalSplitCandidate(tData, backCandidate);
+
+		tQueue.push(frontCandidate);
+		tQueue.push(backCandidate);
+
+		// delete old leaf node
+		DEL_PTR(tData.mNode);
+	}
+
+	//-- terminate traversal and create new view cell
+	if (newNode->IsLeaf())
+	{
+		BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+		BspViewCell *viewCell = new BspViewCell();
+		
+		leaf->SetViewCell(viewCell);
+	
+		//-- update pvs
+		int conSamp = 0;
+		float sampCon = 0.0f;
+		AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
+
+		mBspStats.contributingSamples += conSamp;
+		mBspStats.sampleContributions +=(int) sampCon;
+
+		//-- store additional info
+		if (mStoreRays)
+		{
+			RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
+			for (it = tData.mRays->begin(); it != it_end; ++ it)
+			{
+				(*it).mRay->Ref();			
+				leaf->mVssRays.push_back((*it).mRay);
+			}
+		}
+
+		// should I check here?
+		viewCell->mLeaf = leaf;
+
+		if (mUseAreaForPvs)
+			viewCell->SetArea(tData.mProbability);
+		else
+			viewCell->SetVolume(tData.mProbability);
+
+		leaf->mProbability = tData.mProbability;
+
+		EvaluateLeafStats(tData);		
+	}
+
+	//-- cleanup
+	tData.Clear();
+
+	return newNode;
+}
+
+
 void VspBspTree::EvalSplitCandidate(VspBspTraversalData &tData,
 									VspBspSplitCandidate &splitData)
@@ -663,34 +915,12 @@
 
 
-BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
-								   VspBspTraversalData &frontData,
-								   VspBspTraversalData &backData,
-								   PolygonContainer &coincident)
+BspInterior *VspBspTree::SubdivideNode(const Plane3 &splitPlane,
+									   VspBspTraversalData &tData,
+									   VspBspTraversalData &frontData,
+									   VspBspTraversalData &backData,
+									   PolygonContainer &coincident)
 {
 	BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
 	
-	// select subdivision plane
-	Plane3 splitPlane;
-	
-	int splitAxis;
-
-	const bool success = 
-		SelectPlane(splitPlane, leaf, tData, frontData, backData, splitAxis);
-
-
-	int maxCostMisses = tData.mMaxCostMisses;
-
-	if (!success)
-	{
-		++ maxCostMisses;
-
-		if (maxCostMisses > mTermMissTolerance)
-		{
-			// terminate branch because of max cost
-			++ mBspStats.maxCostNodes;
-            return leaf;
-		}
-	}
-
 	//-- the front and back traversal data is filled with the new values
 	frontData.mDepth = tData.mDepth + 1;
@@ -702,5 +932,6 @@
 	backData.mRays = new RayInfoContainer();
 	
-	// subdivide rays
+
+	//-- subdivide rays
 	SplitRays(splitPlane,
 			  *tData.mRays,
@@ -708,8 +939,4 @@
 			  *backData.mRays);
 
-
-	// how often was max cost ratio missed in this branch?
-	frontData.mMaxCostMisses = maxCostMisses;
-	backData.mMaxCostMisses = maxCostMisses;
 
 	// compute pvs
@@ -753,16 +980,10 @@
 
 
-	if (splitAxis < 3)
-		++ mBspStats.splits[splitAxis];
-	else
-		++ mBspStats.polySplits;
+	///////////////////////////////////////
+	// subdivide further
 
 	mBspStats.nodes += 2;
 
-
-
-	///////////////////////////////////////
-	
-	//-- subdivide further
+	
 	BspInterior *interior = new BspInterior(splitPlane);
 
@@ -1221,14 +1442,4 @@
 	}
 
-	// cost ratio miss
-	if (mUsePolygonSplitIfAvailable && !data.mPolygons->empty())
-	{
-		frontData.mIsKdNode = backData.mIsKdNode = false;
-		if (lowestCost > mTermMaxCostRatio)
-			return false;
-
-		return true;
-	}
-
 	//-- evaluate axis aligned splits
 	int axis;
@@ -1236,12 +1447,18 @@
 	float pFront, pBack;
 
-	candidateCost = SelectAxisAlignedPlane(plane, 
-										   data, 
-										   axis,
-										   &fGeom, 
-										   &bGeom, 
-										   pFront, 
-										   pBack,
-										   data.mIsKdNode);	 
+	candidateCost = 99999999.0f;
+
+	// option: axis aligned split only if no polygon available
+	if (!mUsePolygonSplitIfAvailable || data.mPolygons->empty())
+	{
+		candidateCost = SelectAxisAlignedPlane(plane, 
+											   data, 
+											   axis,
+											   &fGeom, 
+											   &bGeom, 
+											   pFront, 
+											   pBack,
+											   data.mIsKdNode);	 
+	}
 
 	splitAxis = 3;
@@ -1252,7 +1469,9 @@
 		lowestCost = candidateCost;
 		splitAxis = axis;
+	
 		// assign already computed values
 		// we can do this because we always save the
 		// computed values from the axis aligned splits		
+
 		if (fGeom && bGeom)
 		{
@@ -1269,7 +1488,5 @@
 		DEL_PTR(bGeom);
 	}
-
-	frontData.mIsKdNode = backData.mIsKdNode = 
-		(data.mIsKdNode && splitAxis < 3);
+	
 
 #ifdef _DEBUG
@@ -1277,5 +1494,4 @@
 #endif
 
-	// cost ratio miss
 	if (lowestCost > mTermMaxCostRatio)
 	{
