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);
 }
 
