Use a persistent sorted array in ZSortedScene

Typically the order of renderables changes very little between frames, so
it's possible to use insertion sort which is very fast for almost-sorted
arrays.

diff --git a/source/zsortedscene.cpp b/source/zsortedscene.cpp
index 0d50ae1ea46fe9536f19c9ee094dee5272beb7a1..709c5c26787478cf260d3257d069550aa38e59e6 100644 (file)
--- a/source/zsortedscene.cpp
+++ b/source/zsortedscene.cpp
@@ -12,6 +12,18 @@ ZSortedScene::ZSortedScene():
        reference(FURTHEST)
 { }
 
+void ZSortedScene::add(const Renderable &r)
+{
+       if(renderables.insert(&r).second && !sorted_cache.empty())
+               sorted_cache.push_back(&r);
+}
+
+void ZSortedScene::remove(const Renderable &r)
+{
+       renderables.erase(&r);
+       sorted_cache.clear();
+}
+
 void ZSortedScene::set_order(SortOrder o)
 {
        order = o;
@@ -24,12 +36,22 @@ void ZSortedScene::set_reference(DepthReference r)
 
 void ZSortedScene::render(Renderer &renderer, const Tag &tag) const
 {
+       if(renderables.empty())
+               return;
+
        const Camera *camera = renderer.get_camera();
        if(!camera)
-               return SimpleScene::render(renderer, tag);
+       {
+               for(RenderableSet::const_iterator i=renderables.begin(); i!=renderables.end(); ++i)
+                       renderer.render(**i, tag);
+               return;
+       }
 
-       std::vector<DepthRenderable> sorted_renderables;
-       sorted_renderables.reserve(renderables.size());
+       if(sorted_cache.empty())
+       {
+               sorted_cache.reserve(renderables.size());
+               sorted_cache.insert(sorted_cache.end(), renderables.begin(), renderables.end());
+       }
 
        const Vector3 &camera_pos = camera->get_position();
        const Vector3 &look_dir = camera->get_look_direction();
@@ -37,29 +59,54 @@ void ZSortedScene::render(Renderer &renderer, const Tag &tag) const
        float sign = 1.0f-order*2.0f;
 
        bool use_frustum = setup_frustum(renderer);
-       for(RenderableSet::const_iterator i=renderables.begin(); i!=renderables.end(); ++i)
-               if(!use_frustum || !frustum_cull(**i))
+       for(SortedArray::iterator i=sorted_cache.begin(); i!=sorted_cache.end(); ++i)
+       {
+               i->in_frustum = (!use_frustum || !frustum_cull(*i->renderable));
+               if(i->in_frustum)
                {
-                       float z = 0;
-                       if(const Matrix *model_matrix = (*i)->get_matrix())
+                       if(const Matrix *model_matrix = i->renderable->get_matrix())
                        {
-                               if(const Geometry::BoundingSphere<float, 3> *bsphere = (*i)->get_bounding_sphere())
-                                       z = dot(*model_matrix*bsphere->get_center()-camera_pos, look_dir)+bsphere->get_radius()*radius_factor;
+                               if(const Geometry::BoundingSphere<float, 3> *bsphere = i->renderable->get_bounding_sphere())
+                                       i->depth = dot(*model_matrix*bsphere->get_center()-camera_pos, look_dir)+bsphere->get_radius()*radius_factor;
                                else
-                                       z = dot(*model_matrix*Vector3()-camera_pos, look_dir);
+                                       i->depth = dot(*model_matrix*Vector3()-camera_pos, look_dir);
+                               i->depth *= sign;
                        }
-                       sorted_renderables.push_back(DepthRenderable(z*sign, *i));
+                       else
+                               i->depth = 0;
                }
+       }
 
-       sort(sorted_renderables.begin(), sorted_renderables.end());
+       for(SortedArray::iterator i=sorted_cache.begin(), j=i; i!=sorted_cache.end(); ++i)
+               if(i->in_frustum)
+               {
+                       if(i!=j)
+                               swap(*i, *j);
+
+                       if(j!=sorted_cache.begin() && *j<*(j-1))
+                       {
+                               SortedRenderable sr = *j;
+                               SortedArray::iterator k = j-1;
+                               *j = *k;
+                               while(k!=sorted_cache.begin() && sr<*(k-1))
+                               {
+                                       *k = *(k-1);
+                                       --k;
+                               }
+                               *k = sr;
+                       }
+
+                       ++j;
+               }
 
-       for(vector<DepthRenderable>::const_iterator i=sorted_renderables.begin(); i!=sorted_renderables.end(); ++i)
-               i->renderable->render(renderer, tag);
+       for(SortedArray::const_iterator i=sorted_cache.begin(); (i!=sorted_cache.end() && i->in_frustum); ++i)
+               renderer.render(*i->renderable, tag);
 }
 
 
-ZSortedScene::DepthRenderable::DepthRenderable(float d, const Renderable *r):
-       depth(d),
+ZSortedScene::SortedRenderable::SortedRenderable(const Renderable *r):
+       in_frustum(false),
+       depth(0.0f),
        renderable(r)
 { }
 

diff --git a/source/zsortedscene.h b/source/zsortedscene.h
index f9f6f7eed40bd9cfa527540c5417c6fbce3ae75e..5c876697cae9ee3a878c42be2fc48156471ee9ce 100644 (file)
--- a/source/zsortedscene.h
+++ b/source/zsortedscene.h
@@ -23,25 +23,34 @@ enum DepthReference
 Sorts renderables by their distance from the camera before rendering.  Requires
 renderables to have a matrix.
 */
-class ZSortedScene: public SimpleScene
+class ZSortedScene: public Scene
 {
 private:
-       struct DepthRenderable
+       struct SortedRenderable
        {
+               bool in_frustum;
                float depth;
                const Renderable *renderable;
 
-               DepthRenderable(float, const Renderable *);
+               SortedRenderable(const Renderable *);
 
-               bool operator<(const DepthRenderable &o) const { return depth<o.depth; }
+               bool operator<(const SortedRenderable &o) const { return depth<o.depth; }
        };
 
+       typedef std::set<const Renderable *> RenderableSet;
+       typedef std::vector<SortedRenderable> SortedArray;
+
+       RenderableSet renderables;
        SortOrder order;
        DepthReference reference;
+       mutable SortedArray sorted_cache;
 
 public:
        ZSortedScene();
 
+       virtual void add(const Renderable &);
+       virtual void remove(const Renderable &);
+
        /// Sets the sort order.  Default is back to front.
        void set_order(SortOrder);