Index: /GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h	(revision 1314)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h	(revision 1357)
@@ -256,5 +256,5 @@
 
 protected:
-
+	/// bounding box for this interior node: should we really store this?
 	AxisAlignedBox3 mBoundingBox;
 
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp	(revision 1345)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp	(revision 1357)
@@ -24,7 +24,5 @@
 #define USE_FIXEDPOINT_T 0
 
-static float debugVol = 0;
-
-int BvhNode::sMailId = 10000;//2147483647;
+int BvhNode::sMailId = 10000; //2147483647;
 int BvhNode::sReservedMailboxes = 1;
 
@@ -32,4 +30,5 @@
 
 
+/// sorting operator
 inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
 {
@@ -171,5 +170,5 @@
 {
 	ReadEnvironment();
-	mSubdivisionCandidates = new vector<SortableEntry>;
+	mSubdivisionCandidates = new SortableEntryContainer;
 }
 
@@ -228,7 +227,9 @@
 		"BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
 	
-
+	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useGlobalSort", mUseGlobalSorting);
+
+
+	///////////////////
 	//-- debug output
-
 	Debug << "******* Bvh hierarchy options ******** " << endl;
     Debug << "max depth: " << mTermMaxDepth << endl;
@@ -245,12 +246,12 @@
 	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
 	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
-	
 	Debug << "split borders: " << mSplitBorder << endl;
 	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
+	Debug << "use global sort: " << mUseGlobalSorting << endl;
 	Debug << endl;
 }
 
 
-void AssociateObjectsWithLeaf(BvhLeaf *leaf)
+static void AssociateObjectsWithLeaf(BvhLeaf *leaf)
 {
 	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
@@ -274,5 +275,6 @@
 	
 
-	//-- the front and back traversal data is filled with the new values
+	///////////////////////////////////////////////////////////////////
+	//-- fill  front and back traversal data with the new values
 
 	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
@@ -328,13 +330,11 @@
 	frontData.mMaxCostMisses = sc.mMaxCostMisses;
 	backData.mMaxCostMisses = sc.mMaxCostMisses;
-		
-	// assign positions of the iterators
-#if 0
-	frontData.mObjectsStart = sc.mFrontObjectsStart;
-	frontData.mObjectsEnd = sc.mFrontObjectsEnd;
-	
-	backData.mObjectsStart = sc.mBackObjectsStart;
-	backData.mObjectsEnd = sc.mBackObjectsEnd;
-#endif
+	
+	// assign the objects in sorted order
+	if (mUseGlobalSorting)
+	{
+		AssignSortedObjects(sc, frontData, backData);
+	}
+	
 	// return the new interior node
 	return node;
@@ -388,6 +388,11 @@
 		tBackData.mNode->SetSubdivisionCandidate(backCandidate);
 
-		Debug << "leaf: " << tFrontData.mNode << " setting f candidate: " << tFrontData.mNode->GetSubdivisionCandidate() << " type: " << tFrontData.mNode->GetSubdivisionCandidate()->Type() << endl;
-		Debug << "leaf: " << tBackData.mNode << " setting b candidate: " << tBackData.mNode->GetSubdivisionCandidate() << " type: " << tBackData.mNode->GetSubdivisionCandidate()->Type() << endl;
+		Debug << "leaf: " << tFrontData.mNode << " setting f candidate: " 
+			  << tFrontData.mNode->GetSubdivisionCandidate() << " type: " 
+			  << tFrontData.mNode->GetSubdivisionCandidate()->Type() << endl;
+
+		Debug << "leaf: " << tBackData.mNode << " setting b candidate: " 
+			  << tBackData.mNode->GetSubdivisionCandidate() << " type: " 
+			  << tBackData.mNode->GetSubdivisionCandidate()->Type() << endl;
 		
 		tQueue.Push(frontCandidate);
@@ -443,5 +448,4 @@
 	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
 	const float oldProp = EvalViewCellsVolume(leaf->mObjects);
-	//const float oldProp2 = splitCandidate.mParentData.mProbability; Debug << "here8 " << (oldProp - oldProp2) / viewSpaceVol << "  " << oldProp  / viewSpaceVol << " " << oldProp2  / viewSpaceVol << endl;
 
 	const float oldRenderCost = oldProp * (float)leaf->mObjects.size() / viewSpaceVol;
@@ -568,7 +572,7 @@
 											ObjectContainer &objectsBack)
 {
-	SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
-	
-	vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+	PrepareLocalSubdivisionCandidates(tData, axis);
+	
+	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
 
 	int i = 0;
@@ -603,5 +607,5 @@
 						   ObjectContainer &objectsBack)
 {
-	SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
+	PrepareLocalSubdivisionCandidates(tData, axis);
   
 	// go through the lists, count the number of objects left and right
@@ -624,8 +628,8 @@
 	float maxBorder = minBox;
 
-	vector<SortableEntry>::const_iterator currentPos =
+	SortableEntryContainer::const_iterator currentPos =
 		mSubdivisionCandidates->begin();
 
-	vector<SortableEntry>::reverse_iterator rcit = 
+	SortableEntryContainer::reverse_iterator rcit = 
 		mSubdivisionCandidates->rbegin(), rcit_end = mSubdivisionCandidates->rend();
 		
@@ -645,5 +649,5 @@
 	vector<float>::const_iterator bit = bordersRight.begin();
 
-	vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
 	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit) 
 	{
@@ -750,24 +754,22 @@
 										   ObjectContainer &objectsBack)
 {
+	////////////////////////////////////////////////////////////////
+	// go through the lists, count the number of objects left and right
+	// and evaluate the cost funcion
+
 	// 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();
+	SortableEntryContainer::const_iterator backObjectsStart = mSubdivisionCandidates->begin();
 
 	/////////////////////////////////
-	// the parameters for the current optimum
+	//-- the parameters for the current optimum
 
 	float volBack = volLeft;
@@ -782,13 +784,11 @@
 	const bool printStats =
 		PrepareOutput(axis, mBvhStats.Leaves(), sumStats, vollStats, volrStats);
-	
 #endif
 
-	/////////////////////////////
-	// the sweep heuristics
-	
+	///////////////////////////////////////////////////
+	//-- the sweep heuristics
 	//-- traverse through events and find best split plane
 
-	vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+	SortableEntryContainer::const_iterator cit, cit_end = cit_end = mSubdivisionCandidates->end();
 
 	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
@@ -802,5 +802,4 @@
 
 		++ nObjectsLeft;
-		
 		const int nObjectsRight = nTotalObjects - nObjectsLeft;
 
@@ -811,6 +810,8 @@
 #ifdef _DEBUG
 		if (printStats)
+		{
 			PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
 							sumStats, vollStats, volrStats);
+		}
 #endif
 
@@ -823,18 +824,23 @@
 
 			// objects belongs to left side now
-			for (; currentPos != (cit + 1); ++ currentPos);
+			for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
 		}
 	}
 
+	////////////////////////////////////////////
 	//-- assign object to front and back volume
 
 	// belongs to back bv
-	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
+	for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
+	{
 		objectsBack.push_back((*cit).mObject);
-	
+	}
 	// belongs to front bv
-	for (cit = currentPos; cit != cit_end; ++ cit)
+	for (cit = backObjectsStart; cit != cit_end; ++ cit)
+	{
 		objectsFront.push_back((*cit).mObject);
-
+	}
+
+	// render cost of the old parent
 	const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
 	// the relative cost ratio
@@ -853,11 +859,27 @@
 
 
-void BvHierarchy::SortSubdivisionCandidates(const ObjectContainer &objects,
-											vector<SortableEntry> **subdivisionCandidates,
-											const int axis)											
+void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
+													const int axis)											
+{
+	//-- insert object queries
+	ObjectContainer *objects;
+
+	if (!mUseGlobalSorting)
+		objects = &tData.mNode->mObjects;
+	else
+		objects = tData.mSortedObjects[axis];
+	
+	CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, mUseGlobalSorting, axis);
+}
+
+
+void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects, 
+												  SortableEntryContainer **subdivisionCandidates, 
+												  const bool sort,
+												  const int axis)
 {
 	(*subdivisionCandidates)->clear();
 
-	// compute requested size
+	// compute requested size and look if subdivision candidate has to be recomputed
 	const int requestedSize = (int)objects.size() * 2;
 	
@@ -866,21 +888,14 @@
 		requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
 	{
-    	delete *subdivisionCandidates;
-   		*subdivisionCandidates = new vector<SortableEntry>;
+    	delete (*subdivisionCandidates);
+   		(*subdivisionCandidates) = new SortableEntryContainer;
 	}
 
 	(*subdivisionCandidates)->reserve(requestedSize);
 
-	//-- insert object queries
-	//-- These queries can induce a change in pvs size.
-	//-- Note that they cannot induce a change in view cell volume, as
-	//-- there is no ray associated with these events!!
-
 	ObjectContainer::const_iterator oit, oit_end = objects.end();
 
 	for (oit = objects.begin(); oit < oit_end; ++ oit)
 	{
-		Intersectable *obj = *oit;
-		
 		Intersectable *object = *oit;
 		const AxisAlignedBox3 &box = object->GetBox();
@@ -890,5 +905,8 @@
 	}
 
-	stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
+	if (sort)
+	{
+		stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
+	}
 }
 
@@ -905,7 +923,7 @@
 	float vol = 0;
 
-	// sort so we can use a sweep from right to left
-	SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
-
+    // sort so we can use a sweep from right to left
+	PrepareLocalSubdivisionCandidates(tData, axis);
+	
 	// collect and mark the view cells as belonging to front pvs
 	ViewCellContainer viewCells;
@@ -939,9 +957,9 @@
 	CollectViewCells(obj, viewCells, useMailboxing);
 
-	/// classify view cells and compute volume contri accordingly
-	/// possible view cell classifications:
-	/// view cell mailed => view cell can be seen from left child node
-	/// view cell counter > 0 view cell can be seen from right child node
-	/// combined: view cell volume belongs to both nodes
+	// classify view cells and compute volume contri accordingly
+	// possible view cell classifications:
+	// view cell mailed => view cell can be seen from left child node
+	// view cell counter > 0 view cell can be seen from right child node
+	// combined: view cell volume belongs to both nodes
 	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
 	
@@ -956,5 +974,4 @@
 		{
 			viewCell->Mail();
-
 			// we now see view cell from both nodes 
 			// => add volume to left node
@@ -964,5 +981,5 @@
 		// last reference into the right node
 		if (-- viewCell->mCounter == 0)
-		{
+		{	
 			// view cell was previously seen from both nodes  =>
 			// remove volume from right node
@@ -1005,5 +1022,6 @@
 	}
 	
-	// -- evaluate split cost for all three axis
+	////////////////////////////////////////////
+	//-- evaluate split cost for all three axis
 	
 	for (int axis = 0; axis < 3; ++ axis)
@@ -1042,4 +1060,5 @@
 	}
 
+	/////////////////////////////////////
 	//-- assign values
 
@@ -1129,9 +1148,11 @@
 	//-- pvs rendering heuristics
 	const float newRenderCost = nObjectsFront * pFront + nObjectsBack * pBack;
-	/*
+
+#ifdef _DEBUG
 	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
 	Debug << "\nbvh render cost\n" 
 		  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << endl
 		  << "new rc: " << newRenderCost / viewSpaceVol << endl;*/
+#endif
 
 	return newRenderCost;
@@ -1448,4 +1469,5 @@
 }
 
+
 void BvHierarchy::CreateRoot(const ObjectContainer &objects)
 {
@@ -1454,5 +1476,4 @@
 	BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
 	bvhleaf->mObjects = objects;
-
 	mRoot = bvhleaf;
 
@@ -1465,15 +1486,10 @@
 													   const ObjectContainer &objects)
 {
+	///////////////////////////////////////////////////////////////
+	// note matt: we assume that we have objects sorted by their id
+
 	mBvhStats.Reset();
 	mBvhStats.Start();
 	mBvhStats.nodes = 1;
-
-	for (int i = 0; i < 3; ++ i)
-	{
-		mGlobalSubdivisionCandidates[i] = new vector<SortableEntry>();
-		SortSubdivisionCandidates(objects, &mGlobalSubdivisionCandidates[i], i);
-	}
-
-	// note matt: we assume that we have objects sorted by their id
 
 	// store pointer to this tree
@@ -1502,5 +1518,14 @@
 	BvhTraversalData oData(bvhleaf, 0, mBoundingBox, prop);
 
+	// create sorted object lists for the first data
+	if (mUseGlobalSorting)
+	{
+		CreateInitialSortedObjectList(oData);
+	}
+	
+
+	////////////////////////////////////////////////////
 	//-- add first candidate for object space partition	
+
 	BvhSubdivisionCandidate *oSubdivisionCandidate = 
 		new BvhSubdivisionCandidate(oData);
@@ -1530,4 +1555,65 @@
 
 
+void BvHierarchy::CreateInitialSortedObjectList(BvhTraversalData &tData)
+{
+	SortableEntryContainer *sortedObjects = new SortableEntryContainer();
+
+	// we sort the objects as a preprocess so they don't have
+	// to be sorted for each split
+	for (int i = 0; i < 3; ++ i)
+	{
+		CreateLocalSubdivisionCandidates(tData.mNode->mObjects, &sortedObjects, true, i);
+			
+		tData.mSortedObjects[i] = new ObjectContainer();
+		tData.mSortedObjects[i]->reserve((int)sortedObjects->size());
+
+		SortableEntryContainer::const_iterator oit, oit_end = sortedObjects->end();
+		for (oit = sortedObjects->begin(); oit != oit_end; ++ oit)
+		{
+			tData.mSortedObjects[i]->push_back((*oit).mObject);
+		}
+	}
+
+	delete sortedObjects;
+}
+
+
+void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
+									  BvhTraversalData &frontData,
+									  BvhTraversalData &backData)
+{
+	Intersectable::NewMail();
+
+	// we sorted the objects as a preprocess so they don't have
+	// to be sorted for each split
+	ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();
+
+	for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
+	{
+		(*fit)->Mail();
+	}
+
+	for (int i = 0; i < 3; ++ i)
+	{
+		frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
+		backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
+
+		ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mNode->mObjects.end();
+
+		for (oit = sc.mParentData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
+		{
+			if ((*oit)->Mailed())
+			{
+				frontData.mSortedObjects[i]->push_back(*oit);
+			}
+			else
+			{
+				backData.mSortedObjects[i]->push_back(*oit);
+			}
+		}
+	}
+}
+
+
 void BvhStatistics::Print(ostream &app) const
 {
Index: /GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h
===================================================================
--- /GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h	(revision 1345)
+++ /GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h	(revision 1357)
@@ -35,5 +35,4 @@
 class VspTree;
 class ViewCellsContainer;
-//class BvhSubdivisionCandidate;
 
 
@@ -149,8 +148,10 @@
 	/** The bounding box specifies the node extent.
 	*/
+	inline 
 	AxisAlignedBox3 GetBoundingBox() const
 	{ return mBoundingBox; }
 
 
+	inline 
 	void SetBoundingBox(const AxisAlignedBox3 &boundingBox) 
 	{ mBoundingBox = boundingBox; }
@@ -298,7 +299,7 @@
 		mMaxCostMisses(0), 
 		mAxis(0)
-		//mObjectsStart(0),
-		//mObjectsEnd(0)
-		{}
+		{
+			mSortedObjects[0] = mSortedObjects[1] = mSortedObjects[2] = NULL;
+		}
 		
 		BvhTraversalData(BvhLeaf *node, 
@@ -312,12 +313,16 @@
 		mMaxCostMisses(0),
 		mAxis(0)
-		//mObjectsStart(0)
-		//mObjectsEnd(0)
-		{}
-
-		/// deletes contents and sets them to NULL
+		{
+			mSortedObjects[0] = mSortedObjects[1] = mSortedObjects[2] = NULL;
+		}
+
+		/** Deletes contents and sets them to NULL.
+		*/
 		void Clear()
 		{
 			DEL_PTR(mNode);
+			/*DEL_PTR(mSortedObjects[0]);
+			DEL_PTR(mSortedObjects[1]);
+			DEL_PTR(mSortedObjects[2]);*/
 		}
 
@@ -334,11 +339,10 @@
 		/// current axis
 		int mAxis;
-		/// start of objects
-		SortableEntryContainer::const_iterator mObjectsStart;
-		/// end of objects
-		SortableEntryContainer::const_iterator mObjectsEnd;
+		/// the sorted objects for the three dimensions
+		ObjectContainer *mSortedObjects[3];		
     };
 
-	/** Candidate for a view space split.
+
+	/** Candidate for a object space split.
 	*/
 	class BvhSubdivisionCandidate: public SubdivisionCandidate
@@ -618,14 +622,26 @@
 
 	
-	/** Sorts split candidates for cost heuristics using axis aligned splits.
+	/** Prepare split candidates for cost heuristics using axis aligned splits.
 		@param node the current node
 		@param axis the current split axis
 	*/
-	static void SortSubdivisionCandidates(
-		const ObjectContainer &objects,
-		vector<SortableEntry> **subdivisionCandidates,
+	void PrepareLocalSubdivisionCandidates(
+		const BvhTraversalData &tData,
 		const int axis);
 
-	/** Computes best cost for axis aligned planes.
+	static void CreateLocalSubdivisionCandidates(
+		const ObjectContainer &objects, 
+		SortableEntryContainer **subdivisionCandidates,
+		const bool sort,
+		const int axis);
+
+	/** Computes object partition with the best cost according to the heurisics.
+		@param tData the traversal data
+		@param axis the split axis
+		@param objectsFront the objects in the front child bv
+		@param objectsBack the objects in the back child bv
+		@param backObjectsStart the iterator marking the position where the back objects begin
+
+		@returns relative cost (relative to parent cost)
 	*/
 	float EvalLocalCostHeuristics(
@@ -633,5 +649,5 @@
 		const int axis,
 		ObjectContainer &objectsFront,
-		ObjectContainer &objectsFBack);
+		ObjectContainer &objectsBack);
 
 	/** Evaluates the contribution to the front and back volume
@@ -708,4 +724,11 @@
 	float EvalViewCellsVolume(const ObjectContainer &objects) const;
 
+	void CreateInitialSortedObjectList(BvhTraversalData &tData);
+
+	void AssignSortedObjects(
+		const BvhSubdivisionCandidate &sc,
+		BvhTraversalData &frontData,
+		BvhTraversalData &backData);
+
 
 protected:
@@ -735,5 +758,6 @@
 
 
-	//-- local termination
+	////////////////////////////////
+	//-- local termination criteria
 
 	/// maximal possible depth
@@ -751,5 +775,6 @@
 
 
-	//-- global criteria
+	////////////////////////////////////
+	//-- global termination criteria
 
 	float mTermMinGlobalCostRatio;
@@ -765,4 +790,5 @@
 
 
+	////////////////////////////////////////
 	//-- split heuristics based parameters
 	
@@ -772,14 +798,9 @@
 	/// if only driving axis should be used for split
 	bool mOnlyDrivingAxis;
-	
 	/// current time stamp (used for keeping split history)
 	int mTimeStamp;
 	// if rays should be stored in leaves
 	bool mStoreRays;
-
-	/// epsilon for geometric comparisons
-	float mEpsilon;
-
-	/// subdivision stats output file
+	// subdivision stats output file
 	ofstream  mSubdivisionStats;
 	/// keeps track of cost during subdivision
@@ -789,14 +810,12 @@
 	/// number of currenly generated view cells
 	int mCreatedLeaves;
-
 	/// represents min and max band for sweep
 	float mSplitBorder;
-
 	/// weight between render cost decrease and node render cost
 	float mRenderCostDecreaseWeight;
-
 	/// stores the kd node intersectables used for pvs
 	BvhIntersectableMap mBvhIntersectables;
 
+	bool mUseGlobalSorting;
 };
 
