Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/SceneEntity.h
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/SceneEntity.h	(revision 2795)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/SceneEntity.h	(revision 2802)
@@ -13,5 +13,5 @@
 class Geometry;
 class RenderState;
-
+struct RenderQueueBucket;
 
 /** Class representing a scene entity.
@@ -20,4 +20,6 @@
 class SceneEntity
 {
+	friend class RenderQueue;
+
 public:
 	/** Creates a scene entity.
@@ -52,4 +54,5 @@
 
 	inline Material *GetMaterial() const  { return mMaterial; }
+	inline Matrix4x4 *GetTransformation() const  { return mTransform; }
 
 protected:
@@ -61,4 +64,6 @@
 	
 	int mLastRendered;
+	/// pointer to the renderqueue bucket this entity belongs to
+	RenderQueueBucket *mRenderQueueBucket;
 };
 
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Timer/PerfTimer.h
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Timer/PerfTimer.h	(revision 2801)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Timer/PerfTimer.h	(revision 2802)
@@ -22,5 +22,5 @@
 #define _PERFTIMER_H
 
-// RDTSC timer does not work with modern CPUs
+// note: RDTSC timer does not work with modern CPUs
 #define NO_RDTSC_TIMER
 
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderTraverser.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderTraverser.cpp	(revision 2801)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderTraverser.cpp	(revision 2802)
@@ -168,16 +168,6 @@
 	glDisableClientState(GL_VERTEX_ARRAY);
 	glDisableClientState(GL_NORMAL_ARRAY);
-	
-
-#ifdef PRINT_VERBOSE_BENCHMARKS
-
-	Debug << "traversal type: " << GetType() << endl;
-	if (mUseRenderQueue) Debug << "rq sort: " << 1e3f * mRenderQueue.sortTimer.TotalTime() << " ms" << endl;
-	
-	Debug << "wait time: " << 1e3f * waitTimer.TotalTime() << " ms" << endl;
-	Debug << "query time: " << 1e3f * queryTimer.TotalTime() << " ms" << endl;
-	Debug << "rest time: " << 1e3f * restTimer.TotalTime() << " ms" << endl;
-
-#endif
+
+	//cout << "rq overhead: " << 1e3f * mRenderQueue->rTimer.TotalTime() << " ms" << endl;
 }
 
@@ -243,12 +233,8 @@
 OcclusionQuery *RenderTraverser::IssueOcclusionQuery(BvhNode *node)
 {
-	queryTimer.Entry();
-
 	OcclusionQuery *query = mQueryHandler.RequestQuery();
 	query->AddNode(node);
 
 	IssueOcclusionQuery(*query);
-
-	queryTimer.Exit();
 
 	return query;
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.cpp	(revision 2800)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.cpp	(revision 2802)
@@ -154,5 +154,5 @@
 	}
 
-	//cout << "scene box: " << mBox << endl;
+	cout << "scene box: " << mBox << endl;
 }
 
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.h
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.h	(revision 2782)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.h	(revision 2802)
@@ -341,6 +341,7 @@
 	Vector3 mmin(MAXFLOAT);
 	Vector3 mmax(-MAXFLOAT);
-
+	
 	AxisAlignedBox3 ret(mmin, mmax);
+	
 	ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMin.z));
 	ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMax.z));
@@ -351,4 +352,5 @@
 	ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMin.z));
 	ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMax.z));
+	
 	return ret;
 }
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderQueue.h
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderQueue.h	(revision 2801)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderQueue.h	(revision 2802)
@@ -10,8 +10,30 @@
 
 class RenderState;
+class Camera;
 
 
-/** This class implements a render queue that sorts entities according to
-	their materials.
+/** Defines a bucket for scene entities that have the same properties.
+*/
+struct RenderQueueBucket
+{
+	/** should be full texture format, but we as use the same format for all textures
+	    they differ only in size, and we implicitly assume that textures with the same 
+	    size have exactly the same format
+	*/
+	int mTextureSize;
+	bool mAlphaTestEnabled;
+
+	/// minimal distance to the camera
+	float mMinDistance;
+
+	SceneEntityContainer mEntities;
+};
+
+
+/** This class implements a render queue that sorts renderable geometry in order
+	to minimize state changes while approximately keeping front-to-back order
+	The implementation roughly follows the suggested implemenation on Tom Forsyth's article
+	on render state changes. It requires sorting only on bucket level and therefore has very
+	low overhead
 */
 class RenderQueue
@@ -24,43 +46,53 @@
 	/** Constructor taking a render queue
 	*/
-	RenderQueue(RenderState *state);
-	/** Enqueues an entity
+	RenderQueue(RenderState *state, Camera *cam);
+
+	~RenderQueue();
+	/** Enqueues an entity.
 	*/
 	void Enqueue(SceneEntity *entity);
+	/** Sets the current render state
+	*/
+	void SetRenderState(RenderState *state);
+	/** Sets the current render state
+	*/
+	void SetCamera(Camera *cam);
+	/** Returns the number entities currently in the queue.
+	*/
+	inline int GetSize() const { return (int)mSize; }
+	/** Renders and clears the queue.
+	*/
+	void Apply();
+
+
+protected:
+
+	inline bool FitsInBucket(SceneEntity *ent, size_t idx) const;
+
+	/** Sorts the render queue by materials / textures.
+	*/
+	void Sort();
+	/** Clears the render queue
+	*/
+	void Clear();
 	/** Renders the contents of the render queue.
 	*/
 	void Render();
-	/** Sets the current render state
-	*/
-	void SetRenderState(RenderState *state);
-	/** Clears the render queue
-	*/
-	void Clear();
-	/** Returns the number entities currently in the queue.
-	*/
-	inline int GetSize() const { return (int)mEntities.size(); }
-	/** Renders and clears the queue.
-	*/
-	void Apply();
 	/** Prints the current state of the render queue.
 	*/
 	void Print();
 
-protected:
-
-	/** Sorts the render queue by materials / textures.
-	*/
-	void Sort();
-
-
 	///////////
 
 	RenderState *mState;
-	SceneEntityContainer mEntities;
+	Camera *mCamera;
+	//SceneEntityContainer mEntities;
 	int mMinSizeForSorting;
+
+	/// each bucket contains objects with similar materials that don't cause a hard state change
+	std::vector<RenderQueueBucket *> mBuckets;
+
+	int mSize;
 };
-
-/// measures sort time for detailed benchmarks
-static PerfTimer sortTimer;
 
 
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/SceneEntity.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/SceneEntity.cpp	(revision 2795)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/SceneEntity.cpp	(revision 2802)
@@ -13,5 +13,5 @@
 						 Material *mat,
 						 Matrix4x4 *trafo):
-mGeometry(geometry), mMaterial(mat), mTransform(trafo)
+mGeometry(geometry), mMaterial(mat), mTransform(trafo), mRenderQueueBucket(NULL)
 {
 }
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/StopAndWaitTraverser.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/StopAndWaitTraverser.cpp	(revision 2800)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/StopAndWaitTraverser.cpp	(revision 2802)
@@ -33,8 +33,6 @@
 				OcclusionQuery *query = IssueOcclusionQuery(node);
 
-				waitTimer.Entry();
-				bool visible = query->GetQueryResult() > mVisibilityThreshold;
-				waitTimer.Exit();
-
+				const bool visible = query->GetQueryResult() > mVisibilityThreshold;
+			
 				if (visible)
 				{
@@ -43,10 +41,6 @@
 				else
 				{
-					node->SetVisible(false);
 					++ mStats.mNumQueryCulledNodes;
 				}
-				
-				// update node's visited flag (could be interesting for the visualization)
-				node->SetVisible(visible);		
 			}
 		}
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/chcdemo.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/chcdemo.cpp	(revision 2801)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/chcdemo.cpp	(revision 2802)
@@ -168,5 +168,5 @@
 	visCamera->Yaw(.5 * M_PI);
 
-	renderQueue = new RenderQueue(&state);
+	renderQueue = new RenderQueue(&state, camera);
 
 	glutInitWindowSize(winWidth, winHeight);
@@ -518,5 +518,5 @@
 	// note: have to flush queue in order to get reliable timings
 	// for optimal performance, remove this
-	glFinish();
+	//glFinish();
 
 	algTimer.Start();
@@ -575,5 +575,5 @@
 	// note: have to flush queue in order to get reliable timings
 	// for optimal performance, remove this
-	glFinish();
+	//glFinish();
 	algTime = algTimer.Elapsedms();
 
@@ -1091,9 +1091,12 @@
 	const float expFactor = 0.3f;
 
-	// if there was something fishy going on in this frame => don't count
-	if (algTime < 1000) 
-		renderTime = algTime * expFactor + (1.0f - expFactor) * algTime;
-
-	accumulatedTime += renderTime;
+	//if (useRenderQueue) cout << "rq overhead: " << 1e6f * rqTimer.TotalTime() << " ms" << endl;
+
+	// if some strange render time spike happened in this frame => don't count
+	//if (algTime < 1000) renderTime = algTime * expFactor + (1.0f - expFactor) * algTime;
+
+	renderTime = 1e3f * (elapsedTime * expFactor + (1.0f - expFactor) * elapsedTime);
+
+	accumulatedTime += elapsedTime * 1e3f;
 
 	if (accumulatedTime > 500) // update every fraction of a second
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/CHCPlusPlusTraverser.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/CHCPlusPlusTraverser.cpp	(revision 2800)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/CHCPlusPlusTraverser.cpp	(revision 2802)
@@ -15,10 +15,6 @@
 void CHCPlusPlusTraverser::HandleQueryResult(OcclusionQuery *query)
 {
-	waitTimer.Entry();
-
 	// wait until result available
 	const int visible = query->GetQueryResult() > mVisibilityThreshold;
-
-	waitTimer.Exit();
 
 	// multiquery
@@ -199,5 +195,4 @@
 	if (mUseRenderQueue) ApplyRenderQueue();
 
-	restTimer.Entry();
 
 	//////////////
@@ -220,6 +215,4 @@
 		HandleQueryResult(query);
 	}
-
-	restTimer.Exit();
 }
 
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/FrustumCullingTraverser.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/FrustumCullingTraverser.cpp	(revision 2795)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/FrustumCullingTraverser.cpp	(revision 2802)
@@ -1,6 +1,4 @@
 #include "FrustumCullingTraverser.h"
 #include "SceneEntity.h"
-
-using namespace std;
 
 
@@ -20,13 +18,6 @@
 		mDistanceQueue.pop();
 	
-		// interesting for the visualization, so rest and set
-		node->SetVisible(false);
-
 		if (mBvh->IsWithinViewFrustum(node))
 		{
-			// update node's visited flag => needed for rendering
-			// so set it also here
-			//node->SetLastVisited(mFrameID);
-			node->SetVisible(true);
 			TraverseNode(node);
 		}
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderTraverser.h
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderTraverser.h	(revision 2801)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderTraverser.h	(revision 2802)
@@ -216,8 +216,4 @@
 
 
-/// timers for detailed benchmarks
-static PerfTimer restTimer;
-static PerfTimer waitTimer;
-static PerfTimer queryTimer;
 
 }
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderQueue.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderQueue.cpp	(revision 2801)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderQueue.cpp	(revision 2802)
@@ -4,4 +4,6 @@
 #include "Texture.h"
 #include "Material.h"
+#include "Camera.h"
+
 
 using namespace std;
@@ -13,43 +15,62 @@
 {
 
+static Camera *sCam = NULL;
 
-inline static bool CompTexture(SceneEntity *ent1, SceneEntity *ent2)
+
+inline static bool CompDist(SceneEntity *e1, SceneEntity *e2)
 {
-	// group by texture size
-	Texture *t1 = ent1->GetMaterial()->GetTexture();
-	Texture *t2 = ent2->GetMaterial()->GetTexture();
-
-	int tsize1 = t1 ? t1->GetByteSize() : 0;
-	int tsize2 = t2 ? t2->GetByteSize() : 0;
-
-	return tsize1 > tsize2;
+	return 
+		(SqrMagnitude(e1->GetBoundingBox().Center() - sCam->GetPosition()) <
+		 SqrMagnitude(e2->GetBoundingBox().Center() - sCam->GetPosition()));
 }
 
 
-#ifdef SORT_ALPHA
-
-inline static bool CompMat(SceneEntity *ent1, SceneEntity *ent2)
-{ 
-	return ent1->GetMaterial()->IsAlphaTestEnabled() < ent2->GetMaterial()->IsAlphaTestEnabled();
+inline static bool CompDist2(RenderQueueBucket *b1, RenderQueueBucket *b2)
+{
+	return (b1->mMinDistance < b2->mMinDistance);
 }
 
-#else
 
-inline static bool CompMat(SceneEntity *ent1, SceneEntity *ent2)
-{
-	return ent1->GetMaterial() < ent2->GetMaterial();
-}
-
-#endif
-
-
-RenderQueue::RenderQueue(): mState(NULL), mMinSizeForSorting(3)
+RenderQueue::RenderQueue(): 
+mState(NULL), 
+mMinSizeForSorting(3),
+mCamera(NULL),
+mSize(0)
 {
 }
 
 
-RenderQueue::RenderQueue(RenderState *state):
-mState(state), mMinSizeForSorting(3)
+RenderQueue::RenderQueue(RenderState *state, Camera *cam):
+mState(state), 
+mMinSizeForSorting(3),
+mCamera(cam),
+mSize(0)
 {
+	sCam = cam;
+}
+
+
+RenderQueue::~RenderQueue()
+{
+	for (size_t i = 0; i < mBuckets.size(); ++ i)
+	{
+		DEL_PTR(mBuckets[i]);
+	}
+}
+
+
+bool RenderQueue::FitsInBucket(SceneEntity *ent, size_t idx) const
+{
+	Material *mat = ent->GetMaterial();
+
+	// test if entity 
+	if (mat->IsAlphaTestEnabled() != mBuckets[idx]->mAlphaTestEnabled)
+		return false;
+
+	int tsize = mat->GetTexture() ? mat->GetTexture()->GetByteSize() : 0;
+	if (tsize != mBuckets[idx]->mTextureSize)
+		return false;
+
+	return true;
 }
 
@@ -57,12 +78,57 @@
 void RenderQueue::Enqueue(SceneEntity *entity)
 {
-	mEntities.push_back(entity);
+	RenderQueueBucket *bucket;
+	++ mSize;
+
+	if (entity->mRenderQueueBucket)
+	{
+		bucket = entity->mRenderQueueBucket;
+	}
+	else
+	{
+		bool bucketFound = false;
+
+		size_t i = 0;
+
+		for (; i < mBuckets.size(); ++ i)
+		{
+			if (bucketFound = FitsInBucket(entity, i))
+				break;
+		}
+
+		// create new bucket
+		if (!bucketFound)
+		{
+			RenderQueueBucket *bucket = new RenderQueueBucket();
+
+			Material *mat = entity->GetMaterial();
+
+			bucket->mAlphaTestEnabled = mat->IsAlphaTestEnabled();
+			bucket->mTextureSize = mat->GetTexture() ? mat->GetTexture()->GetByteSize() : 0;
+
+			mBuckets.push_back(bucket);
+
+			// assume that the incoming nodes are ordered by distance => set min dist
+			// on first incoming node
+			float dist = SqrMagnitude(entity->GetBoundingBox().Center() - mCamera->GetPosition());
+			mBuckets[i]->mMinDistance = dist;
+
+			//cout << "num buckets: " << (int)mBuckets.size() << endl;
+		}
+
+		bucket = mBuckets[i];
+		entity->mRenderQueueBucket = bucket;
+	}
+
+	bucket->mEntities.push_back(entity);
 }
-	
+
 
 void RenderQueue::Clear()
 {
-	mEntities.clear();
+	for (size_t i = 0; i < mBuckets.size(); ++ i)
+		mBuckets[i]->mEntities.clear();
 
+	mSize = 0;
 }
 
@@ -76,17 +142,15 @@
 void RenderQueue::Render()
 {
-	if (mEntities.size() >= mMinSizeForSorting)
+	Sort();
+	
+	// render all buckets
+	for (size_t i = 0; i < mBuckets.size(); ++ i)
 	{
-		sortTimer.Entry();
-		Sort();
-		sortTimer.Exit();
-	}
-	
-	SceneEntityContainer::const_iterator sit, sit_end = mEntities.end();
-
-	for (sit = mEntities.begin(); sit != sit_end; ++ sit)
-	{
-		SceneEntity *ent = *sit;
-		ent->Render(mState);
+		SceneEntityContainer::const_iterator sit, sit_end = mBuckets[i]->mEntities.end();
+		for (sit = mBuckets[i]->mEntities.begin(); sit != sit_end; ++ sit)
+		{
+			SceneEntity *ent = *sit;
+			ent->Render(mState);
+		}
 	}
 
@@ -97,29 +161,19 @@
 void RenderQueue::Print()
 {
-	SceneEntityContainer::const_iterator sit, sit_end = mEntities.end();
+	for (size_t i = 0; i < mBuckets.size(); ++ i)
+	{
+		Debug << "\n******\nbucket " << i << endl;
 
-	Debug << "\nrq size: " << GetSize() << endl;
-	Debug << "texture size: " << endl;
+		SceneEntityContainer::const_iterator sit, sit_end = mBuckets[i]->mEntities.end();
 
-	// show ordering by texture size
-	for (sit = mEntities.begin(); sit != sit_end; ++ sit)
-	{
-		SceneEntity *ent = *sit;
-		Texture *t = ent->GetMaterial()->GetTexture();
+		for (sit = mBuckets[i]->mEntities.begin(); sit != sit_end; ++ sit)
+		{
+			SceneEntity *ent = *sit;
 	
-		int tsize = t ? t->GetByteSize() : 0;
-		Debug << tsize << " ";
-	}
-
-	// show ordering by material
-	Debug << "\nmaterial: " << endl;
-	
-	for (sit = mEntities.begin(); sit != sit_end; ++ sit)
-	{
-#ifdef SORT_ALPHA
-		Debug << (*sit)->GetMaterial()->IsAlphaTestEnabled() << " ";
-#else
-		Debug << (*sit)->GetMaterial() << " ";
-#endif
+			Material *mat = ent->GetMaterial();
+			int tsize = mat->GetTexture() ? mat->GetTexture()->GetByteSize() : 0;
+			float dist = SqrMagnitude(ent->GetBoundingBox().Center() - mCamera->GetPosition());
+			Debug << "e: " << ent << " a: " << mat->IsAlphaTestEnabled() << " s: " << tsize << " d: " << dist << " " << ent->GetBoundingBox() << " g: " << ent->GetGeometry() << " t: " << ent->GetTransformation() << " m: " << ent->GetMaterial() << endl;
+		}
 	}
 }
@@ -135,15 +189,6 @@
 void RenderQueue::Sort()
 {
-#ifdef SORT_ALPHA
-	// sort by texture size
-	sort(mEntities.begin(), mEntities.end(), CompTexture);
-	// sort by alpha test enabled
-	stable_sort(mEntities.begin(), mEntities.end(), CompMat);
-#else
-	// sort by material
-	sort(mEntities.begin(), mEntities.end(), CompMat);
-	// sort by texture size
-	stable_sort(mEntities.begin(), mEntities.end(), CompTexture);
-#endif
+	// sort buckets itself
+	sort(mBuckets.begin(), mBuckets.end(), CompDist2);
 }
 
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.cpp	(revision 2793)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.cpp	(revision 2802)
@@ -987,5 +987,5 @@
 }
 
-//int AxisAlignedBox3::GetIndexFarthestVertex(const Vector3 &vecPlaneNormal)
+
 int AxisAlignedBox3::GetIndexNearestVertex(const Vector3 &vecPlaneNormal)
 {
@@ -1000,5 +1000,4 @@
 
 
-//int AxisAlignedBox3::GetIndexNearestVertex(const Vector3 &vecPlaneNormal)
 int AxisAlignedBox3::GetIndexFarthestVertex(const Vector3 &vecPlaneNormal)
 {
@@ -1010,13 +1009,4 @@
 	
 	return 4 * x + 2 * y + z;
-
-	/*int index;
-
-	if (vecPlaneNormal.x <= 0.0f)
-		index = (vecPlaneNormal.y <= 0.0f) ? 0 : 3;
-	else
-		index = (vecPlaneNormal.y <= 0.0f) ? 1 : 2;
-
-	return (vecPlaneNormal.z <= 0.0f) ? index : 7 - index;*/
 }
 
