Redesign InstanceArray

It now stores the instances contiguously in memory instead of allocating
them individually.  Consequently only one type of instance is allowed in
any particular array.

diff --git a/source/render/instancearray.cpp b/source/render/instancearray.cpp
index a03fbf20dff9ca2766c15067087389e0d2902fd3..0a3d6b685ad3ffb98b9ee6265db0eba2c3328431 100644 (file)
--- a/source/render/instancearray.cpp
+++ b/source/render/instancearray.cpp
@@ -14,8 +14,10 @@ using namespace std;
 namespace Msp {
 namespace GL {
 
 namespace Msp {
 namespace GL {
 

-InstanceArray::InstanceArray(const Object &o):
-       object(o)
+InstanceArrayBase::InstanceArrayBase(const Object &o, size_t s):
+       object(o),
+       instance_size(s),
+       default_count(max<size_t>(4096U/instance_size, 8U))

 {
        const Technique *tech = object.get_technique();
        for(const auto &kvp: tech->get_methods())
 {
        const Technique *tech = object.get_technique();
        for(const auto &kvp: tech->get_methods())


@@ -46,53 +48,133 @@ InstanceArray::InstanceArray(const Object &o):
        vtx_setup.set_instance_array(instance_data);
 }
 
        vtx_setup.set_instance_array(instance_data);
 }
 

-InstanceArray::~InstanceArray()
+InstanceArrayBase::~InstanceArrayBase()

 {
 {

-       for(ObjectInstance *i: instances)
-               delete i;

        delete instance_buffer;
        delete instance_buffer;

+       for(Block &b: storage)
+               delete[] b.begin;

 }
 
 }
 

-void InstanceArray::append(ObjectInstance *inst)
+void InstanceArrayBase::add_block(size_t count)

 {
 {

-       instances.push_back(inst);
-       if(instance_data.size()<instances.size())
+       storage.emplace_back();
+       Block &block = storage.back();
+       block.begin = new char[count*instance_size];
+       block.end = block.begin+count*instance_size;
+
+       size_t block_index = storage.size()-1;
+       size_t base = slots.size();
+       slots.resize(base+count);
+       for(size_t i=0; i<count; ++i)
+       {
+               Slot &slot = slots[base+i];
+               slot.next_free = base+i+1;
+               slot.block_index = block_index;
+               slot.index_in_block = i;
+       }
+
+       if(first_free>0)
+               slots[last_free].next_free = base;
+       else
+       {
+               first_free = base;
+               last_free = slots.size()-1;
+       }
+
+       slots.back().next_free = first_free;
+}
+
+size_t InstanceArrayBase::allocate()
+{
+       if(first_free<0)
+               add_block(default_count);
+
+       size_t index = first_free;
+       Slot &slot = slots[index];
+       if(first_free==last_free)
+       {
+               first_free = -1;
+               last_free = -1;
+       }
+       else
+       {
+               first_free = slot.next_free;
+               slots[last_free].next_free = first_free;
+       }
+
+       slot.used = true;
+       slot.array_index = instance_count++;
+       if(instance_data.size()<instance_count)

        {
                instance_data.append();
        {
                instance_data.append();

-               unsigned req_size = instance_data.get_required_buffer_size();
-               if(instance_buffer->get_size()>0 && instance_buffer->get_size()<req_size)
-               {
-                       delete instance_buffer;
-                       instance_buffer = new Buffer;
-                       instance_data.use_buffer(instance_buffer);
-               }
+               array_order.push_back(index);

        }
        }

-       update_instance_matrix(instances.size()-1);
+       else
+               array_order[slot.array_index] = index;
+
+       return index;

 }
 
 }
 

-void InstanceArray::remove(ObjectInstance &inst)
+char *InstanceArrayBase::get_address(size_t index) const

 {
 {

-       auto i = find(instances, &inst);
-       if(i==instances.end())
-               throw key_error(&inst);
+       const Slot &s = slots[index];
+       return storage[s.block_index].begin+s.index_in_block*instance_size;
+}
+
+size_t InstanceArrayBase::find_index(char *addr) const
+{
+       size_t base = 0;
+       for(const Block &b: storage)
+       {
+               if(addr>=b.begin && addr<b.end)
+                       return base+(addr-b.begin)/instance_size;
+               base += (b.end-b.begin)/instance_size;
+       }

 
 

-       delete *i;
-       *i = instances.back();
-       instances.pop_back();
+       throw out_of_range("InstanceArrayBase::find_index");

 }
 
 }
 

-void InstanceArray::update_instance_matrix(unsigned index)
+void InstanceArrayBase::release(size_t index)

 {
 {

-       const Matrix &m = *instances[index]->get_matrix();
+       Slot &slot = slots[index];
+
+       --instance_count;
+       if(slot.array_index<instance_count)
+       {
+               size_t swap_index = array_order[instance_count];
+               unsigned stride = instance_data.get_format().stride();
+               const char *src = instance_data[swap_index];
+               char *dst = instance_data.modify(slot.array_index);
+               copy(src, src+stride, dst);
+               slots[swap_index].array_index = slot.array_index;
+               array_order[slot.array_index] = swap_index;
+               array_order[instance_count] = -1;
+       }

 
 

-       float *d = reinterpret_cast<float *>(instance_data.modify(index)+matrix_offset);
+       slot.used = false;
+       if(first_free>=0)
+       {
+               slot.next_free = first_free;
+               slots[last_free].next_free = index;
+       }
+       else
+       {
+               slot.next_free = index;
+               first_free = index;
+       }
+       last_free = index;
+}
+
+void InstanceArrayBase::update_instance_matrix(size_t index, const Matrix &matrix)
+{
+       float *d = reinterpret_cast<float *>(instance_data.modify(slots[index].array_index)+matrix_offset);

        for(unsigned i=0; i<12; ++i)
        for(unsigned i=0; i<12; ++i)

-               d[i] = m(i/4, i%4);
+               d[i] = matrix(i/4, i%4);

 }
 
 }
 

-void InstanceArray::render(Renderer &renderer, Tag tag) const
+void InstanceArrayBase::render(Renderer &renderer, Tag tag) const

 {
 {

-       if(instances.empty())
+       if(!instance_count)

                return;
 
        const Technique *tech = object.get_technique();
                return;
 
        const Technique *tech = object.get_technique();


@@ -109,7 +191,7 @@ void InstanceArray::render(Renderer &renderer, Tag tag) const
        Renderer::Push push(renderer);
        renderer.set_pipeline_key(this, tag.id);
        method->apply(renderer);
        Renderer::Push push(renderer);
        renderer.set_pipeline_key(this, tag.id);
        method->apply(renderer);

-       mesh->draw_instanced(renderer, vtx_setup, instances.size());
+       mesh->draw_instanced(renderer, vtx_setup, instance_count);

 }
 
 } // namespace GL
 }
 
 } // namespace GL

diff --git a/source/render/instancearray.h b/source/render/instancearray.h
index e6f8690c68cd5b2000d25f9bb7d770f063fcc1f4..f2a9b2c00be5930c281a8341851d838af949ba1f 100644 (file)
--- a/source/render/instancearray.h
+++ b/source/render/instancearray.h
@@ -15,8 +15,96 @@ class Buffer;
 class Object;
 class ObjectInstance;
 
 class Object;
 class ObjectInstance;
 

+class InstanceArrayBase: public Renderable, public NonCopyable
+{
+private:
+       struct Block
+       {
+               char *begin = 0;
+               char *end = 0;
+       };
+
+       struct Slot
+       {
+               bool used = false;
+               union
+               {
+                       std::uint16_t array_index;
+                       std::uint16_t next_free;
+               };
+               std::uint16_t block_index;
+               std::uint16_t index_in_block;
+       };
+
+       const Object &object;
+       VertexArray instance_data;
+       Buffer *instance_buffer = 0;
+       VertexSetup vtx_setup;
+       int matrix_location = -1;
+       unsigned matrix_offset = 0;
+       std::size_t instance_size;
+       std::size_t default_count;
+       std::vector<Block> storage;
+       std::vector<Slot> slots;
+       std::vector<int> array_order;
+       int first_free = -1;
+       int last_free = -1;
+       std::size_t instance_count = 0;
+
+protected:
+       InstanceArrayBase(const Object &, std::size_t);
+       ~InstanceArrayBase();
+
+private:
+       void add_block(std::size_t);
+       std::size_t allocate();
+       char *get_address(std::size_t) const;
+       std::size_t find_index(char *) const;
+       void release(std::size_t);
+protected:
+       template<typename T, typename A>
+       T *create(A &);
+
+       template<typename T>
+       void destroy(T *);
+
+       template<typename T>
+       void destroy_all();
+
+       void update_instance_matrix(std::size_t, const Matrix &);
+
+public:
+       std::size_t size() const { return instance_count; }
+
+       virtual void render(Renderer &, Tag) const;
+};
+
+template<typename T, typename A>
+inline T *InstanceArrayBase::create(A &array)
+{
+       size_t index = allocate();
+       return new(get_address(index)) T(object, array, index);
+}
+
+template<typename T>
+inline void InstanceArrayBase::destroy(T *obj)
+{
+       char *addr = reinterpret_cast<char *>(obj);
+       obj->~T();
+       release(find_index(addr));
+}
+
+template<typename T>
+inline void InstanceArrayBase::destroy_all()
+{
+       for(unsigned i=0; i<slots.size(); ++i)
+               if(slots[i].used)
+                       reinterpret_cast<T *>(get_address(i))->~T();
+}
+
+

 /**
 /**

-Renders multiple instances of an Object in an efficient manner.
+Stores and renders multiple instances of an Object in an efficient manner.

 
 The instance specific transform is passed to the shader in an attribute with
 the name instance_transform.  The attribute should have the type vec4[3].  Each
 
 The instance specific transform is passed to the shader in an attribute with
 the name instance_transform.  The attribute should have the type vec4[3].  Each


@@ -24,11 +112,19 @@ elements of the array corresponds to a row of the transform matrix.
 
 If the Mesh or Technique of the Object is changed during the lifetime of the
 InstanceArray, behaviour is undefined.
 
 If the Mesh or Technique of the Object is changed during the lifetime of the
 InstanceArray, behaviour is undefined.

+
+The instance type must have a constructor accepting a const Object &.  If it
+has a virtual function with the signature void set_matrix(const Matrix &), it
+will be used to update the instance matrix.  The original function is also
+called.
+
+Instance created by the array have stable addresses.  However after an instance
+is removed, its address may later be reused for another instance.

 */
 */

-class InstanceArray: public Renderable, public NonCopyable
+template<typename T = ObjectInstance>
+class InstanceArray: public InstanceArrayBase

 {
 {

-public:
-       template<typename T>
+private:

        class Instance: public T
        {
        private:
        class Instance: public T
        {
        private:


@@ -41,47 +137,20 @@ public:
                virtual void set_matrix(const Matrix &);
        };
 
                virtual void set_matrix(const Matrix &);
        };
 

-private:
-       const Object &object;
-       std::vector<ObjectInstance *> instances;
-       VertexArray instance_data;
-       Buffer *instance_buffer = 0;
-       VertexSetup vtx_setup;
-       int matrix_location = -1;
-       unsigned matrix_offset = 0;
-

 public:
 public:

-       InstanceArray(const Object &);
-       ~InstanceArray();
-
-       void set_matrix_attribute(const std::string &);
+       InstanceArray(const Object &o): InstanceArrayBase(o, sizeof(Instance)) { }
+       ~InstanceArray() { destroy_all<T>(); }

 
 

-       /** Adds a new instance to the array.  The instance class must have a
-       constructor taking a const reference to Object as its sole parameter. */
-       template<typename T = ObjectInstance>
-       T &append();
-private:
-       void append(ObjectInstance *);
-       void update_instance_matrix(unsigned);
-public:
-       void remove(ObjectInstance &);
-
-       virtual void render(Renderer &, Tag) const;
+       T &append() { return *create<Instance>(*this); }
+       void remove(T &obj) { destroy(&obj); }

 };
 
 };
 

-template<typename T>
-T &InstanceArray::append()
-{
-       Instance<T> *inst = new Instance<T>(object, *this, instances.size());
-       append(inst);
-       return *inst;
-}

 
 template<typename T>
 
 template<typename T>

-void InstanceArray::Instance<T>::set_matrix(const Matrix &m)
+inline void InstanceArray<T>::Instance::set_matrix(const Matrix &m)

 {
        T::set_matrix(m);
 {
        T::set_matrix(m);

-       array.update_instance_matrix(index);
+       array.update_instance_matrix(index, *this->get_matrix());

 }
 
 } // namespace GL
 }
 
 } // namespace GL