Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp	(revision 1047)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp	(revision 1072)
@@ -1230,4 +1230,5 @@
 			++ contributingSamples;
 		
+		// note: vss rays are never deleted
 		if (0) leaf->mVssRays.push_back(new VssRay(*ray));
 	}
@@ -1610,7 +1611,9 @@
 					bestAxis = axis;
 				}
-				else if (nCostRatio[axis] < nCostRatio[bestAxis])
+				/*else if (nCostRatio[axis] < nCostRatio[bestAxis])
+				{
 					Debug << "taking split along longest axis (" << bestAxis << ") instead of  (" << axis << ")" << endl;
-				
+				}*/
+
 			}
 			else
@@ -1629,4 +1632,5 @@
 
 	//-- assign values
+
 	axis = bestAxis;
 	pFront = nProbFront[bestAxis];
@@ -1646,5 +1650,5 @@
 
 	//Debug << "best axis: " << bestAxis << " pos " << nPosition[bestAxis] << endl;
-	//Debug << "!!!!!!!!!!!!!!" << endl;
+
 	return nCostRatio[bestAxis];
 }
@@ -1659,7 +1663,8 @@
 {
 	// HACK matt: subdivide regularily to certain depth
-	if (data.mDepth < 0)  	
-	{
-		cout << "d: " << data.mDepth << endl;
+	if (data.mDepth < 0)  	// question matt: why depth < 0 ?
+	{
+		cout << "depth: " << data.mDepth << endl;
+
 		// return axis aligned split
 		AxisAlignedBox3 box;
@@ -1675,4 +1680,5 @@
 		bestPlane = Plane3(norm, position);
 		splitAxis = axis;
+
 		return true;
 	}
@@ -2509,5 +2515,6 @@
 
 
-void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
+void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, 
+								  bool onlyValid) const
 {
 	ViewCell::NewMail();
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp	(revision 1052)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp	(revision 1072)
@@ -777,4 +777,5 @@
 			++ contributingSamples;
 		
+		// warning: rays get never deleted!
 		if (0) leaf->mVssRays.push_back(new VssRay(*ray));
 	}
@@ -803,7 +804,7 @@
 	float pos;
 
-	// float values => don't compare with exact values
 	if (0)
 	{
+		// float values => don't compare with exact values
 		minBand += Limits::Small;
 		maxBand -= Limits::Small;
@@ -816,13 +817,12 @@
 				
 		pos = (*ri).ExtrapOrigin(axis);
-		// clamp to min / max band
-		if (0) ClipValue(pos, minBand, maxBand);
 		
+		if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band
 		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
 									pos, (*ri).mRay));
 
 		pos = (*ri).ExtrapTermination(axis);
-		// clamp to min / max band
-		if (0) ClipValue(pos, minBand, maxBand);
+
+		if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band
 
 		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
@@ -831,4 +831,78 @@
 
 	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
+}
+
+
+int VspTree::GetPvsContribution(Intersectable *object) const
+{
+    int pvsContri = 0;
+
+	KdPvsMap::const_iterator kit, kit_end = object->mKdPvs.mEntries.end();
+
+	Intersectable::NewMail();
+
+	// Search kd leaves this object is attached to
+	for (kit = object->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+	{
+		KdNode *l = (*kit).first;
+
+		// new object found during sweep 
+		// => increase pvs contribution of this kd node
+		if (!l->Mailed())
+		{
+			l->Mail();
+			++ pvsContri;
+		}
+	}
+
+	return pvsContri;
+}
+
+
+void VspTree::PrepareHeuristics(const RayInfoContainer &rays)
+{	
+	ObjectContainer objects;
+
+	// Collect all pvs that can be seen from the view cell
+	CollectPvs(rays, objects);
+
+	// adjust kd node info table
+	// for each object the entry must be updated 
+	// which belongs to the same kd nodes
+	ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+	for (oit = objects.begin(); oit != oit_end; ++ oit)
+	{
+		Intersectable *obj = *oit;
+		// TODO
+		//UpdateKdNodeInfo(obj);
+	}
+}
+
+
+int VspTree::GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes)
+{
+	// TODO:
+	// use kd info table to apply set theory in order to
+	// sort out dublicate pvs entries due to objects which
+	// belong to more than one kd leaves.
+#if TODO
+	KdPvsMap::const_iterator kit, kit_end = obj->mKdPvs.mEntries.end();
+
+	// Search kd leaves this object is attached to
+	for (kit = obj->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+	{
+		KdNode *l = (*kit).first;
+
+		// new object found during sweep 
+		// => increase pvs contribution of this kd node
+		if (!l->Mailed())
+		{
+			l->Mail();
+			++ pvsContr;
+		}
+	}
+#endif
+	return 0;
 }
 
@@ -875,5 +949,6 @@
    	RayInfoContainer::const_iterator ri, ri_end = rays.end();
 
-	// set all object as belonging to the front pvs
+	//-- set all object as belonging to the front pvs
+
 	for(ri = rays.begin(); ri != ri_end; ++ ri)
 	{
@@ -1015,4 +1090,325 @@
 
 
+void VspTree::EvalPvsIncr(ObjectMap &multipleObjects,
+						  KdLeaf *leaf, 
+						  const SortableEntry &ci,
+						  int &pvsLeft,
+						  int &pvsRight) const
+{
+	int pvsSize = 0;
+
+	if (ci.type == SortableEntry::ERayMin)
+	{
+		if (!leaf->Mailed())
+		{
+			leaf->Mail();
+			pvsLeft += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size();
+
+			// add duplicates
+			ObjectMap::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
+
+			for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
+			{
+				const int id = (*oit)->first;
+				Intersectable *object = (*oit)->second;
+
+				if (multipleObjects[id] != object) // object not previously in pvs
+				{
+					multipleObjects[id] = object;
+					++ pvsLeft;
+				}
+
+			}
+		}					
+	}
+	else if (ci.type == SortableEntry::ERayMax)
+	{
+		if (-- leaf->mCounter == 0)
+			pvsRight += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size();
+	}
+}
+
+
+float VspTree::EvalKdCostHeuristics(const RayInfoContainer &rays,
+									const AxisAlignedBox3 &box,
+									const int pvsSize,
+									const int axis,
+									float &position)
+{
+	const float minBox = box.Min(axis);
+	const float maxBox = box.Max(axis);
+
+	const float sizeBox = maxBox - minBox;
+
+	const float minBand = minBox + mMinBand * sizeBox;
+	const float maxBand = minBox + mMaxBand * sizeBox;
+
+	SortSplitCandidates(rays, axis, minBand, maxBand);
+
+	// go through the lists, count the number of objects left and right
+	// and evaluate the following cost funcion:
+	// C = ct_div_ci  + (ql*rl + qr*rr)/queries
+
+	int pvsl = 0;
+	int pvsr = pvsSize;
+
+	int pvsBack = pvsl;
+	int pvsFront = pvsr;
+
+	float sum = (float)pvsSize * sizeBox;
+	float minSum = 1e20f;
+
+	
+	// if no good split can be found, take mid split
+	position = minBox + 0.5f * sizeBox;
+	
+	// the relative cost ratio
+	float ratio = /*Limits::Infinity;*/99999999.0f;
+	bool splitPlaneFound = false;
+
+	Intersectable::NewMail();
+	KdNode::NewMail();
+
+   	RayInfoContainer::const_iterator ri, ri_end = rays.end();
+
+	//-- set all kd nodes as belonging to the front pvs
+
+	for (ri = rays.begin(); ri != ri_end; ++ ri)
+	{
+		Intersectable *oObject = (*ri).mRay->mOriginObject;
+
+		if (oObject)
+		{
+			KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
+		
+			for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+			{
+				KdNode *node = (*kit).first;
+
+				if (!node->Mailed())
+				{
+					node->Mail();
+					//node->mCounter = 1;
+				}
+				else
+				{
+					//++ node->mCounter;
+				}
+			}	
+		}
+
+		Intersectable *tObject = (*ri).mRay->mTerminationObject;
+
+		if (tObject)
+		{
+			KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
+		
+			for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+			{
+				KdNode *node = (*kit).first;
+
+				if (!node->Mailed())
+				{
+					node->Mail();
+					//node->mCounter = 1;
+				}
+				else
+				{
+					//++ node->mCounter;
+				}
+			}	
+		}
+	}
+
+	Intersectable::NewMail();
+
+	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
+
+	ObjectMap multipleObjectsLeft, multipleObjectsRight;
+
+
+	// -- traverse through visibility events
+
+	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
+	{
+		VssRay *ray;
+		ray = (*ci).ray;
+		
+		Intersectable *oObject = ray->mOriginObject;
+		
+		KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
+
+		if (oObject)
+		{	
+			for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+			{
+                KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first);
+
+				EvalPvsIncr(multipleObjectsLeft, node, *ci, pvsl, pvsr);
+			}
+		}
+
+		Intersectable *tObject = ray->mOriginObject;
+
+		if (tObject)
+		{	
+			for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+			{
+				KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first);
+
+				EvalPvsIncr(multipleObjectsRight, node, *ci, pvsl, pvsr);
+			}
+		}
+
+
+		// Note: sufficient to compare size of bounding boxes of front and back side?
+		if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
+		{
+			sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
+
+			//Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
+			//Debug << "cost= " << sum << endl;
+
+			if (sum < minSum)
+			{
+				splitPlaneFound = true;
+
+				minSum = sum;
+				position = (*ci).value;
+				
+				pvsBack = pvsl;
+				pvsFront = pvsr;
+			}
+		}
+	}
+	
+	
+	// -- compute cost
+
+	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+	const float pOverall = sizeBox;
+	const float pBack = position - minBox;
+	const float pFront = maxBox - position;
+
+	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+	
+	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
+	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+	if (splitPlaneFound)
+	{
+		ratio = newRenderCost / oldRenderCost;
+	}
+	//if (axis != 1)
+	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+	 //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
+
+	return ratio;
+}
+
+
+#if TODO
+
+float VspTree::EvalLocalCostHeuristicsNonIncremential(const RayInfoContainer &rays,
+													  const AxisAlignedBox3 &box,
+													  const int pvsSize,
+													  const int axis,
+													  float &position)
+{
+	const float minBox = box.Min(axis);
+	const float maxBox = box.Max(axis);
+
+	const float sizeBox = maxBox - minBox;
+
+	const float minBand = minBox + mMinBand * sizeBox;
+	const float maxBand = minBox + mMaxBand * sizeBox;
+
+	SortSplitCandidates(rays, axis, minBand, maxBand);
+
+	// go through the lists, count the number of objects left and right
+	// and evaluate the following cost funcion:
+	// C = ct_div_ci  + (ql*rl + qr*rr)/queries
+
+	int pvsl = 0;
+	int pvsr = pvsSize;
+
+	int pvsBack = pvsl;
+	int pvsFront = pvsr;
+
+	float sum = (float)pvsSize * sizeBox;
+	float minSum = 1e20f;
+
+	
+	// if no good split can be found, take mid split
+	position = minBox + 0.5f * sizeBox;
+	
+	// the relative cost ratio
+	float ratio = /*Limits::Infinity;*/99999999.0f;
+	bool splitPlaneFound = false;
+
+	Intersectable::NewMail();
+
+   	RayInfoContainer::const_iterator ri, ri_end = rays.end();
+
+	//-- set all object as belonging to the front pvs
+
+	for(ri = rays.begin(); ri != ri_end; ++ ri)
+	{
+		// Note: sufficient to compare size of bounding boxes of front and back side?
+		if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
+		{
+			sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
+
+			//Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
+			//Debug << "cost= " << sum << endl;
+
+			if (sum < minSum)
+			{
+				splitPlaneFound = true;
+
+				minSum = sum;
+				position = (*ci).value;
+				
+				pvsBack = pvsl;
+				pvsFront = pvsr;
+			}
+		}
+	}
+
+	
+	// -- compute cost
+
+	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+	const float pOverall = sizeBox;
+	const float pBack = position - minBox;
+	const float pFront = maxBox - position;
+
+	
+	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+	
+	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
+	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+	if (splitPlaneFound)
+	{
+		ratio = newRenderCost / oldRenderCost;
+	}
+	//if (axis != 1)
+	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+	 //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
+
+	return ratio;
+}
+#endif
+
+
 float VspTree::SelectSplitPlane(const VspTraversalData &tData,
 								AxisAlignedPlane &plane,
@@ -1699,4 +2095,41 @@
 
 
+void VspTree::CollectPvs(const RayInfoContainer &rays, 
+						 ObjectContainer &objects) const
+{
+	RayInfoContainer::const_iterator rit, rit_end = rays.end();
+
+	Intersectable::NewMail();
+
+	for (rit = rays.begin(); rit != rays.end(); ++ rit)
+	{
+		VssRay *ray = (*rit).mRay;
+
+		Intersectable *object;
+		object = ray->mOriginObject;
+
+        if (object)
+		{
+			if (!object->Mailed())
+			{
+				object->Mail();
+				objects.push_back(object);
+			}
+		}
+
+		object = ray->mTerminationObject;
+
+		if (object)
+		{
+			if (!object->Mailed())
+			{
+				object->Mail();
+				objects.push_back(object);
+			}
+		}
+	}
+}
+
+
 int VspTree::ComputePvsSize(const RayInfoContainer &rays) const
 {
@@ -2576,5 +3009,5 @@
 		  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
 		  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
-	  //		  << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
+	  	  << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
 		  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
 		  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
@@ -2586,7 +3019,10 @@
 
 
+
 /*********************************************************************/
 /*                class HierarchyManager implementation              */
 /*********************************************************************/
+
+
 
 HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/Containers.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/Containers.h	(revision 1001)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/Containers.h	(revision 1072)
@@ -4,4 +4,5 @@
 #include <vector>
 #include <queue>
+#include <map>
 
 using namespace std;
@@ -54,4 +55,6 @@
 typedef vector<IndexedBoundingBox> IndexedBoundingBoxContainer;
 
+typedef std::map<int, Intersectable *> ObjectMap;
+
 }
 
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp	(revision 1052)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp	(revision 1072)
@@ -5253,5 +5253,5 @@
 
 			// export rays
-			if (1 && mExportRays)
+			if (0 && mExportRays)
 			{
 				exporter->ExportRays(visRays, RgbColor(0, 1, 0));
@@ -5262,5 +5262,6 @@
 			// HACK: export without clip plane
 			const bool b = mUseClipPlaneForViz;
-			mUseClipPlaneForViz = false;
+			if (0)
+				mUseClipPlaneForViz = false;
 
 			ExportViewCellsForViz(exporter);
@@ -5336,6 +5337,4 @@
 
 				raysOut = min((int)rays.size(), 100);
-
-				Debug  << "here12 " << raysOut << endl;
 
 				// collect intial view cells
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h	(revision 1047)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h	(revision 1072)
@@ -868,5 +868,9 @@
 						   float &pBack);
 
-	/** Sorts split candidates for surface area heuristics for axis aligned splits.
+	/** Sorts split candidates along the specified axis.
+		The split candidates are generated on possible visibility
+		events (i.e., where ray segments intersect the ray boundaries).
+		The sorted candidates are needed to compute the SAH.
+
 		@param polys the input for choosing split candidates
 		@param axis the current split axis
@@ -877,4 +881,16 @@
 							 float minBand, 
 							 float maxBand);
+
+	/** Prepares objects for SAH.
+	*/
+	void PrepareHeuristics(const RayInfoContainer &rays);
+
+	/** Computes pvs increase with respect to the previous pvs for SAH.
+	*/
+	int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes);
+
+	/** Returns absolute pvs contribution of this object.
+	*/
+	int GetPvsContribution(Intersectable *object) const;
 
 	/** Computes best cost for axis aligned planes.
@@ -886,4 +902,16 @@
 								  float &position);
 
+	float EvalKdCostHeuristics(const RayInfoContainer &rays,
+							   const AxisAlignedBox3 &box,
+							   const int pvsSize,
+							   const int axis,
+							   float &position);
+	 void EvalPvsIncr(ObjectMap &multipleObjects,
+					  KdLeaf *leaf, 
+					  const SortableEntry &ci,
+					  int &pvsLeft,
+					  int &pvsRight) const;
+
+
 	/** Subdivides the rays into front and back rays according to the split plane.
 		
@@ -918,4 +946,9 @@
 	*/
 	int ComputePvsSize(const RayInfoContainer &rays) const;
+	
+	/** Collects pvs from rays.
+	*/
+	void CollectPvs(const RayInfoContainer &rays,
+					ObjectContainer &objects) const;
 
 	/** Returns true if tree can be terminated.
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.h	(revision 1002)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.h	(revision 1072)
@@ -188,5 +188,9 @@
   /** pointers to occluders contained in this node */
   ObjectContainer mObjects;
-  
+
+  /** Objects that are part of several leaves.
+  */
+  ObjectMap mMultipleObjects;
+
   /** Ray set description of the rays passing through this node */
   PassingRaySet mPassingRays;
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/Intersectable.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/Intersectable.h	(revision 1020)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/Intersectable.h	(revision 1072)
@@ -8,4 +8,5 @@
 
 struct VssRayContainer;
+class KdLeaf;
 
 class Intersectable {
@@ -17,13 +18,16 @@
   int mMailbox;
   
-  // unique object Id
+  /// unique object Id
   int mId;
   
-  // universal counter
+  /// universal counter
   int mCounter;
 	
-  // object based pvs
+  /// object based pvs
   KdPvs mKdPvs;
   
+  /// kd leaves that this intersectable belongs to
+  std::vector<KdLeaf *> mKdLeaves;
+
   enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEW_CELL, OGRE_MESH_INSTANCE };
   
