Index: GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp	(revision 1314)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp	(revision 1323)
@@ -580,5 +580,5 @@
 
 	const float oldProp = EvalViewCellsVolume(tData.mNode->mObjects);
-	//const float oldProp2 = tData.mProbability; Debug << "here65 " << oldProp - oldProp2 << endl;
+	//const float oldProp2 = tData.mProbability;
 
 	const float oldRenderCost = oldProp * (float)tData.mNode->mObjects.size();
@@ -591,43 +591,113 @@
 
 
-float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
-										   const int axis,
-										   ObjectContainer &objectsFront,
-										   ObjectContainer &objectsBack)
-{
-	// prepare the heuristics by setting mailboxes and counters.
-	const float totalVol = PrepareHeuristics(tData, axis);
-
+float BvHierarchy::EvalSah(const BvhTraversalData &tData,
+						   const int axis,
+						   ObjectContainer &objectsFront,
+						   ObjectContainer &objectsBack)
+{
+	SortSubdivisionCandidates(tData, axis);
+  
 	// go through the lists, count the number of objects left and right
-	// and evaluate the cost funcion
-
-	// local helper variables
-	float volLeft = 0;
-	float volRight = totalVol;
-
-	int nObjectsLeft = 0;
-
-	const int nTotalObjects = (int)tData.mNode->mObjects.size();
-	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+	// and evaluate the following cost funcion:
+	// C = ct_div_ci  + (ol + or)/queries
+	int objectsLeft = 0, objectsRight = (int)tData.mNode->mObjects.size();
+  
+	AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
+
+	float minBox = box.Min(axis);
+	float maxBox = box.Max(axis);
+	float boxArea = box.SurfaceArea();
+
+	float minSum = 1e20f;
+  
+	vector<float> bordersRight;
+	bordersRight.resize(mSubdivisionCandidates->size());
+
+	float minBorder = maxBox;
+	float maxBorder = minBox;
 
 	vector<SortableEntry>::const_iterator currentPos =
 		mSubdivisionCandidates->begin();
 
-	/////////////////////////////////
-	// the parameters for the current optimum
-
-	float volBack = volLeft;
-	float volFront = volRight;
-	float newRenderCost = nTotalObjects * totalVol;
-
-#ifdef _DEBUG
-	const int leaves = mBvhStats.Leaves();
-	const bool printStats = ((axis == 0) && (leaves > 0) && (leaves < 90));
-	
-	ofstream sumStats;
-	ofstream vollStats;
-	ofstream volrStats;
-
-	if (printStats)
+	vector<SortableEntry>::reverse_iterator rcit = 
+		mSubdivisionCandidates->rbegin(), rcit_end = mSubdivisionCandidates->rend();
+		
+	vector<float>::reverse_iterator rbit = bordersRight.rbegin();
+	
+	for (; rcit != rcit_end; ++ rcit, ++ rbit) 
+	{
+		Intersectable *obj = (*rcit).mObject;
+		const AxisAlignedBox3 box = obj->GetBox();
+
+		if (box.Min() < minBorder)
+			minBorder = box.Min(axis);
+		
+		(*rbit) = minBorder;
+	}
+
+	vector<float>::const_iterator bit = bordersRight.begin();
+
+	vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit) 
+	{
+		Intersectable *obj = (*cit).mObject;
+
+		++ objectsLeft;
+		-- objectsRight;
+
+		AxisAlignedBox3 lbox = box;
+		AxisAlignedBox3 rbox = box;
+	
+		const AxisAlignedBox3 obox = obj->GetBox();
+
+		if (obox.Max(axis) > maxBorder)
+			maxBorder = obox.Max(axis);
+
+        lbox.SetMax(axis, maxBorder);
+		rbox.SetMin(axis, *bit);
+	
+		const float sum = objectsLeft * lbox.SurfaceArea() + objectsRight * rbox.SurfaceArea();
+      
+	    // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
+	    // cout<<"cost= "<<sum<<endl;
+      
+		if (sum < minSum) 
+		{
+			minSum = sum;	
+			// objects belongs to left side now
+			for (; currentPos != (cit + 1); ++ currentPos);
+		}
+	}
+
+	//-- assign object to front and back volume
+
+	// belongs to back bv
+	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
+		objectsBack.push_back((*cit).mObject);
+	
+	// belongs to front bv
+	for (cit = currentPos; cit != cit_end; ++ cit)
+		objectsFront.push_back((*cit).mObject);
+
+	float oldCost = (float)tData.mNode->mObjects.size();
+	float newCost = minSum / boxArea;
+	float ratio = newCost / oldCost;
+  
+#if 0
+  cout<<"===================="<<endl;
+  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
+      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
+#endif
+  return ratio;
+}
+
+
+static bool PrepareOutput(const int axis,
+						  const int leaves,
+						  ofstream &sumStats, 
+						  ofstream &vollStats, 
+						  ofstream &volrStats)
+{
+	if ((axis == 0) && (leaves > 0) && (leaves < 90))
 	{
 		char str[64]; 	
@@ -639,4 +709,71 @@
 		volrStats.open(str);
 	}
+
+	return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
+}
+
+
+static void PrintHeuristics(const int objectsRight,
+							const float sum,
+							const float volLeft,
+							const float volRight,
+							const float viewSpaceVol,
+							ofstream &sumStats, 
+							ofstream &vollStats, 
+							ofstream &volrStats)
+{
+	sumStats
+		<< "#Position\n" << objectsRight << endl
+		<< "#Sum\n" << sum / viewSpaceVol << endl
+		<< "#Vol\n" << (volLeft +  volRight) / viewSpaceVol << endl;
+
+	vollStats
+		<< "#Position\n" << objectsRight << endl
+		<< "#Vol\n" << volLeft / viewSpaceVol << endl;
+
+	volrStats
+		<< "#Position\n" << objectsRight << endl
+		<< "#Vol\n" << volRight / viewSpaceVol << endl;
+}
+
+
+float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
+										   const int axis,
+										   ObjectContainer &objectsFront,
+										   ObjectContainer &objectsBack)
+{
+	// prepare the heuristics by setting mailboxes and counters.
+	const float totalVol = PrepareHeuristics(tData, axis);
+
+	// go through the lists, count the number of objects left and right
+	// and evaluate the cost funcion
+
+	// local helper variables
+	float volLeft = 0;
+	float volRight = totalVol;
+
+	int nObjectsLeft = 0;
+
+	const int nTotalObjects = (int)tData.mNode->mObjects.size();
+	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+
+	vector<SortableEntry>::const_iterator currentPos =
+		mSubdivisionCandidates->begin();
+
+	/////////////////////////////////
+	// the parameters for the current optimum
+
+	float volBack = volLeft;
+	float volFront = volRight;
+	float newRenderCost = nTotalObjects * totalVol;
+
+#ifdef _DEBUG
+	ofstream sumStats;
+	ofstream vollStats;
+	ofstream volrStats;
+
+	const bool printStats =
+		PrepareOutput(axis, mBvhStats.Leaves(), sumStats, vollStats, volrStats);
+	
 #endif
 
@@ -666,20 +803,7 @@
 
 #ifdef _DEBUG
-		
 		if (printStats)
-		{
-			sumStats
-				<< "#Position\n" << nObjectsRight << endl
-				<< "#Sum\n" << sum / viewSpaceVol << endl
-				<< "#Vol\n" << (volLeft +  volRight) / viewSpaceVol << endl;
-
-			vollStats
-				<< "#Position\n" << nObjectsRight << endl
-				<< "#Vol\n" << volLeft / viewSpaceVol << endl;
-
-			volrStats
-				<< "#Position\n" << nObjectsRight << endl
-				<< "#Vol\n" << volRight / viewSpaceVol << endl;
-		}
+			PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
+							sumStats, vollStats, volrStats);
 #endif
 
@@ -705,6 +829,4 @@
 	for (cit = currentPos; cit != cit_end; ++ cit)
 		objectsFront.push_back((*cit).mObject);
-
-	tData.mNode->mObjects.end();
 
 	const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
@@ -775,16 +897,15 @@
 float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData, const int axis)
 {	
-	//-- sort so we can use a sweep from right to left
+	BvhLeaf *leaf = tData.mNode;
+	float vol = 0;
+
+	// sort so we can use a sweep from right to left
 	SortSubdivisionCandidates(tData, axis);
-
-	float vol = 0;
-	BvhLeaf *leaf = tData.mNode;
 
 	// collect and mark the view cells as belonging to front pvs
 	ViewCellContainer viewCells;
 	CollectViewCells(tData.mNode->mObjects, viewCells, true);
-
-    ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-
+			
+	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
 	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
 	{
@@ -792,9 +913,9 @@
 	}
 
+	// mail the objects on the left side
+	Intersectable::NewMail();
 	// mail view cells on the left side
 	ViewCell::NewMail();
-	// mail the objects on the left side
-	Intersectable::NewMail();
-
+	
 	return vol;
 }
@@ -808,10 +929,8 @@
 	// collect all view cells associated with this objects 
 	// (also multiple times, if they are pierced by several rays)
-
 	ViewCellContainer viewCells;
-	
 	const bool useMailboxing = false;
+
 	CollectViewCells(obj, viewCells, useMailboxing);
-
 
 	/// classify view cells and compute volume contri accordingly
