Index: GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp	(revision 1344)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp	(revision 1345)
@@ -262,14 +262,11 @@
 
 
-BvhInterior *BvHierarchy::SubdivideNode(const ObjectContainer &frontObjects,
-										const ObjectContainer &backObjects,
-										const BvhTraversalData &tData,
+BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
 										BvhTraversalData &frontData,
 										BvhTraversalData &backData)
 {
+	const BvhTraversalData &tData = sc.mParentData;
 	BvhLeaf *leaf = tData.mNode;
-	
-	// two new leaves
-    mBvhStats.nodes += 2;
+    mBvhStats.nodes += 2; // we have two new leaves
 
 	// add the new nodes to the tree
@@ -281,17 +278,17 @@
 	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
 
-	frontData.mBoundingBox = ComputeBoundingBox(frontObjects, &tData.mBoundingBox);
-	backData.mBoundingBox = ComputeBoundingBox(backObjects, &tData.mBoundingBox);
-	
-	/////////////
+	frontData.mBoundingBox = ComputeBoundingBox(sc.mFrontObjects, &tData.mBoundingBox);
+	backData.mBoundingBox = ComputeBoundingBox(sc.mBackObjects, &tData.mBoundingBox);
+	
+
+	////////////////////////////////
 	//-- create front and back leaf
 
 	BvhLeaf *back = 
-		new BvhLeaf(backData.mBoundingBox, node, (int)backObjects.size());
+		new BvhLeaf(backData.mBoundingBox, node, (int)sc.mBackObjects.size());
 	BvhLeaf *front = 
-		new BvhLeaf(frontData.mBoundingBox, node, (int)frontObjects.size());
+		new BvhLeaf(frontData.mBoundingBox, node, (int)sc.mFrontObjects.size());
 
 	BvhInterior *parent = leaf->GetParent();
-
 
 	// replace a link from node's parent
@@ -301,5 +298,5 @@
 		node->SetParent(parent);
 	}
-	else // new root
+	else // no parent => this node is the root
 	{
 		mRoot = node;
@@ -311,20 +308,34 @@
 	++ mBvhStats.splits;
 
-
 	////////////////////////////////////
+	//-- fill traversal data
 
 	frontData.mNode = front;
 	backData.mNode = back;
 
-	back->mObjects = backObjects;
-	front->mObjects = frontObjects;
+	back->mObjects = sc.mBackObjects;
+	front->mObjects = sc.mFrontObjects;
 
 	AssociateObjectsWithLeaf(back);
 	AssociateObjectsWithLeaf(front);
    
-	// compute probability, i.e., volume of seen view cells
-	frontData.mProbability = EvalViewCellsVolume(frontObjects);
-	backData.mProbability = EvalViewCellsVolume(backObjects);
-
+	// compute probability of this node being visible, 
+	// i.e., volume of the view cells that can see this node
+	frontData.mProbability = EvalViewCellsVolume(sc.mFrontObjects);
+	backData.mProbability = EvalViewCellsVolume(sc.mBackObjects);
+
+    // how often was max cost ratio missed in this branch?
+	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
+	// return the new interior node
 	return node;
 }
@@ -339,8 +350,9 @@
 	BvhTraversalData &tData = sc->mParentData;
 
-	BvhNode *newNode = tData.mNode;
+	BvhNode *currentNode = tData.mNode;
 
 	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
 	{	
+		//////////////////////////////////////////
 		//-- continue subdivision
 
@@ -349,16 +361,9 @@
 			
 		// create new interior node and two leaf node
-		newNode = SubdivideNode(sc->mFrontObjects,
-								sc->mBackObjects,
-								tData, 
-								tFrontData, 
-								tBackData);
-	
-		const int maxCostMisses = sc->mMaxCostMisses;
-
-        // how often was max cost ratio missed in this branch?
-		tFrontData.mMaxCostMisses = maxCostMisses;
-		tBackData.mMaxCostMisses = maxCostMisses;
-		
+		currentNode = SubdivideNode(
+			*sc, 
+			tFrontData, 
+			tBackData);
+	
 		// decrease the weighted average cost of the subdivisoin
 		mTotalCost -= sc->GetRenderCostDecrease();
@@ -367,4 +372,6 @@
 		if (1) PrintSubdivisionStats(*sc);
 
+
+		/////////////////////////////////////////
 		//-- push the new split candidates on the queue
 		
@@ -386,15 +393,13 @@
 		tQueue.Push(frontCandidate);
 		tQueue.Push(backCandidate);
-
-		// delete old leaf node
-		//DEL_PTR(tData.mNode);
-	}
-
-	//-- terminate traversal
-
-    if (newNode->IsLeaf())
-	{
+	}
+
+	/////////////////////////////////
+	//-- node is a leaf => terminate traversal
+
+	if (currentNode->IsLeaf())
+	{
+		//////////////////////////////////////
 		//-- store additional info
-		
 		EvaluateLeafStats(tData);
         
@@ -402,16 +407,18 @@
 		if (mStoreRays)
 		{
-			BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(newNode);
+			BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(currentNode);
 			CollectRays(leaf->mObjects, leaf->mVssRays);
 		}
 		
-		// detach subdivision candidate: this leaf is no candidate for
-		// splitting anymore
+		//////////////////////////////////////
+		
+		// this leaf is no candidate for splitting anymore
+		// => detach subdivision candidate
 		tData.mNode->SetSubdivisionCandidate(NULL); 
-		// detach node so it won't get deleted
+		// detach node so we don't delete it with the traversal data
 		tData.mNode = NULL;
 	}
 	
-	return newNode;
+	return currentNode;
 }
 
@@ -561,5 +568,5 @@
 											ObjectContainer &objectsBack)
 {
-	SortSubdivisionCandidates(tData, axis);
+	SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
 	
 	vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
@@ -596,5 +603,5 @@
 						   ObjectContainer &objectsBack)
 {
-	SortSubdivisionCandidates(tData, axis);
+	SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
   
 	// go through the lists, count the number of objects left and right
@@ -846,24 +853,22 @@
 
 
-void BvHierarchy::SortSubdivisionCandidates(const BvhTraversalData &tData,
+void BvHierarchy::SortSubdivisionCandidates(const ObjectContainer &objects,
+											vector<SortableEntry> **subdivisionCandidates,
 											const int axis)											
 {
-	mSubdivisionCandidates->clear();
-
-	//RayInfoContainer *rays = tData.mRays;
-	BvhLeaf *leaf = tData.mNode;
+	(*subdivisionCandidates)->clear();
 
 	// compute requested size
-	const int requestedSize = (int)leaf->mObjects.size() * 2;
+	const int requestedSize = (int)objects.size() * 2;
 	
 	// creates a sorted split candidates array
-	if (mSubdivisionCandidates->capacity() > 500000 &&
-		requestedSize < (int)(mSubdivisionCandidates->capacity() / 10) )
-	{
-    	delete mSubdivisionCandidates;
-   		mSubdivisionCandidates = new vector<SortableEntry>;
-	}
-
-	mSubdivisionCandidates->reserve(requestedSize);
+	if ((*subdivisionCandidates)->capacity() > 500000 &&
+		requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
+	{
+    	delete *subdivisionCandidates;
+   		*subdivisionCandidates = new vector<SortableEntry>;
+	}
+
+	(*subdivisionCandidates)->reserve(requestedSize);
 
 	//-- insert object queries
@@ -872,7 +877,7 @@
 	//-- there is no ray associated with these events!!
 
-	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
-
-	for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
+	ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+	for (oit = objects.begin(); oit < oit_end; ++ oit)
 	{
 		Intersectable *obj = *oit;
@@ -882,8 +887,8 @@
 		const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;
 
-		mSubdivisionCandidates->push_back(SortableEntry(object, midPt));
-	}
-
-	stable_sort(mSubdivisionCandidates->begin(), mSubdivisionCandidates->end());
+		(*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
+	}
+
+	stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
 }
 
@@ -901,5 +906,5 @@
 
 	// sort so we can use a sweep from right to left
-	SortSubdivisionCandidates(tData, axis);
+	SortSubdivisionCandidates(tData.mNode->mObjects, &mSubdivisionCandidates, axis);
 
 	// collect and mark the view cells as belonging to front pvs
@@ -1464,4 +1469,10 @@
 	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
 
Index: GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h	(revision 1323)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h	(revision 1345)
@@ -283,4 +283,7 @@
 public:
 	
+	struct SortableEntry;
+	typedef vector<SortableEntry> SortableEntryContainer;
+
 	/** Additional data which is passed down the BSP tree during traversal.
 	*/
@@ -294,6 +297,7 @@
 		mProbability(0.0),
 		mMaxCostMisses(0), 
-		mPriority(0),
 		mAxis(0)
+		//mObjectsStart(0),
+		//mObjectsEnd(0)
 		{}
 		
@@ -307,15 +311,8 @@
 		mProbability(v),
 		mMaxCostMisses(0),
-		mPriority(0),
 		mAxis(0)
+		//mObjectsStart(0)
+		//mObjectsEnd(0)
 		{}
-
-
-		/** Returns cost of the traversal data.
-		*/
-		float GetCost() const
-		{
-			return mPriority;
-		}
 
 		/// deletes contents and sets them to NULL
@@ -337,12 +334,8 @@
 		/// current axis
 		int mAxis;
-		/// current priority
-		float mPriority;
-
-
-		friend bool operator<(const BvhTraversalData &a, const BvhTraversalData &b)
-		{
-			return a.GetCost() < b.GetCost();
-		}
+		/// start of objects
+		SortableEntryContainer::const_iterator mObjectsStart;
+		/// end of objects
+		SortableEntryContainer::const_iterator mObjectsEnd;
     };
 
@@ -544,5 +537,5 @@
 		}
 	};
- 
+
 	/** Evaluate balanced object partition.
 	*/
@@ -586,20 +579,13 @@
 	
 	/** Subdivides leaf.
-		@param leaf the leaf to be subdivided
+		@param sc the subdivisionCandidate holding all necessary data for subdivision		
 		
-		@param polys the polygons to be split
-		@param frontPolys returns the polygons in front of the split plane
-		@param backPolys returns the polygons in the back of the split plane
-		
-		@param rays the polygons to be filtered
-		@param frontRays returns the polygons in front of the split plane
-		@param backRays returns the polygons in the back of the split plane
-
-		@returns the root of the subdivision
+		@param frontData returns the traversal data for the front node
+		@param backData returns the traversal data for the back node
+
+		@returns the new interior node = the of the subdivision
 	*/
 	BvhInterior *SubdivideNode(
-		const ObjectContainer &frontObjects,
-		const ObjectContainer &backObjects,
-		const BvhTraversalData &tData,
+		const BvhSubdivisionCandidate &sc,
 		BvhTraversalData &frontData,
 		BvhTraversalData &backData);
@@ -636,6 +622,7 @@
 		@param axis the current split axis
 	*/
-	void SortSubdivisionCandidates(
-		const BvhTraversalData &data,
+	static void SortSubdivisionCandidates(
+		const ObjectContainer &objects,
+		vector<SortableEntry> **subdivisionCandidates,
 		const int axis);
 
@@ -724,4 +711,7 @@
 protected:
 	
+	/// pre-sorted subdivision candidtes for all three directions.
+	vector<SortableEntry> *mGlobalSubdivisionCandidates[3];
+
 	/// pointer to the hierarchy of view cells
 	ViewCellsTree *mViewCellsTree;
