Changeset 2802

Timestamp:

06/28/08 16:12:59 (17 years ago)

Author:

mattausch

Message:

worked on renderqueue

Location:

GTP/trunk/App/Demos/Vis/FriendlyCulling

Files:

• data/city/model/city.bvh (deleted)
• data/city/model/city.dem (deleted)
• src/AxisAlignedBox3.cpp (modified) (3 diffs)
• src/AxisAlignedBox3.h (modified) (2 diffs)
• src/Bvh.cpp (modified) (1 diff)
• src/CHCPlusPlusTraverser.cpp (modified) (3 diffs)
• src/FrustumCullingTraverser.cpp (modified) (2 diffs)
• src/RenderQueue.cpp (modified) (6 diffs)
• src/RenderQueue.h (modified) (2 diffs)
• src/RenderTraverser.cpp (modified) (2 diffs)
• src/RenderTraverser.h (modified) (1 diff)
• src/SceneEntity.cpp (modified) (1 diff)
• src/SceneEntity.h (modified) (4 diffs)
• src/StopAndWaitTraverser.cpp (modified) (2 diffs)
• src/Timer/PerfTimer.h (modified) (1 diff)
• src/chcdemo.cpp (modified) (4 diffs)

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.cpp

@@ -987 +987 @@
 }
 
-//int AxisAlignedBox3::GetIndexFarthestVertex(const Vector3 &vecPlaneNormal)
+
 int AxisAlignedBox3::GetIndexNearestVertex(const Vector3 &vecPlaneNormal)
 {
@@ -1000 +1000 @@
 
 
-//int AxisAlignedBox3::GetIndexNearestVertex(const Vector3 &vecPlaneNormal)
 int AxisAlignedBox3::GetIndexFarthestVertex(const Vector3 &vecPlaneNormal)
 {
@@ -1010 +1009 @@
         
         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;*/
 }
 

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.h

@@ -341 +341 @@
         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 +352 @@
         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;
 }

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.cpp

@@ -154 +154 @@
         }
 
-        //cout << "scene box: " << mBox << endl;
+        cout << "scene box: " << mBox << endl;
 }
 

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/CHCPlusPlusTraverser.cpp

@@ -15 +15 @@
 void CHCPlusPlusTraverser::HandleQueryResult(OcclusionQuery *query)
 {
-        waitTimer.Entry();
-
         // wait until result available
         const int visible = query->GetQueryResult() > mVisibilityThreshold;
-
-        waitTimer.Exit();
 
         // multiquery
@@ -199 +195 @@
         if (mUseRenderQueue) ApplyRenderQueue();
 
-        restTimer.Entry();
 
         //////////////
@@ -220 +215 @@
                 HandleQueryResult(query);
         }
-
-        restTimer.Exit();
 }
 

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/FrustumCullingTraverser.cpp

@@ -1 +1 @@
 #include "FrustumCullingTraverser.h"
 #include "SceneEntity.h"
-
-using namespace std;
 
 
@@ -20 +18 @@
                 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);
                 }

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderQueue.cpp

@@ -4 +4 @@
 #include "Texture.h"
 #include "Material.h"
+#include "Camera.h"
+
 
 using namespace std;
@@ -13 +15 @@
 {
 
+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 +78 @@
 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 +142 @@
 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 +161 @@
 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 +189 @@
 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);
 }
 

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderQueue.h

@@ -10 +10 @@
 
 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 +46 @@
         /** 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;
 
 

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderTraverser.cpp

@@ -168 +168 @@
         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 +233 @@
 OcclusionQuery *RenderTraverser::IssueOcclusionQuery(BvhNode *node)
 {
-        queryTimer.Entry();
-
         OcclusionQuery *query = mQueryHandler.RequestQuery();
         query->AddNode(node);
 
         IssueOcclusionQuery(*query);
-
-        queryTimer.Exit();
 
         return query;

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/RenderTraverser.h

@@ -216 +216 @@
 
 
-/// timers for detailed benchmarks
-static PerfTimer restTimer;
-static PerfTimer waitTimer;
-static PerfTimer queryTimer;
 
 }

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/SceneEntity.cpp

@@ -13 +13 @@
                                                  Material *mat,
                                                  Matrix4x4 *trafo):
-mGeometry(geometry), mMaterial(mat), mTransform(trafo)
+mGeometry(geometry), mMaterial(mat), mTransform(trafo), mRenderQueueBucket(NULL)
 {
 }

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/SceneEntity.h

@@ -13 +13 @@
 class Geometry;
 class RenderState;
-
+struct RenderQueueBucket;
 
 /** Class representing a scene entity.
@@ -20 +20 @@
 class SceneEntity
 {
+        friend class RenderQueue;
+
 public:
         /** Creates a scene entity.
@@ -52 +54 @@
 
         inline Material *GetMaterial() const  { return mMaterial; }
+        inline Matrix4x4 *GetTransformation() const  { return mTransform; }
 
 protected:
@@ -61 +64 @@
         
         int mLastRendered;
+        /// pointer to the renderqueue bucket this entity belongs to
+        RenderQueueBucket *mRenderQueueBucket;
 };
 

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/StopAndWaitTraverser.cpp

@@ -33 +33 @@
                                 OcclusionQuery *query = IssueOcclusionQuery(node);
 
-                                waitTimer.Entry();
-                                bool visible = query->GetQueryResult() > mVisibilityThreshold;
-                                waitTimer.Exit();
-
+                                const bool visible = query->GetQueryResult() > mVisibilityThreshold;
+                        
                                 if (visible)
                                 {
@@ -43 +41 @@
                                 else
                                 {
-                                        node->SetVisible(false);
                                         ++ mStats.mNumQueryCulledNodes;
                                 }
-                                
-                                // update node's visited flag (could be interesting for the visualization)
-                                node->SetVisible(visible);              
                         }
                 }

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Timer/PerfTimer.h

@@ -22 +22 @@
 #define _PERFTIMER_H
 
-// RDTSC timer does not work with modern CPUs
+// note: RDTSC timer does not work with modern CPUs
 #define NO_RDTSC_TIMER
 

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/chcdemo.cpp

@@ -168 +168 @@
         visCamera->Yaw(.5 * M_PI);
 
-        renderQueue = new RenderQueue(&state);
+        renderQueue = new RenderQueue(&state, camera);
 
         glutInitWindowSize(winWidth, winHeight);
@@ -518 +518 @@
         // note: have to flush queue in order to get reliable timings
         // for optimal performance, remove this
-        glFinish();
+        //glFinish();
 
         algTimer.Start();
@@ -575 +575 @@
         // note: have to flush queue in order to get reliable timings
         // for optimal performance, remove this
-        glFinish();
+        //glFinish();
         algTime = algTimer.Elapsedms();
 
@@ -1091 +1091 @@
         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