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())
vtx_setup.set_instance_array(instance_data);
}
-InstanceArray::~InstanceArray()
+InstanceArrayBase::~InstanceArrayBase()
{
- for(ObjectInstance *i: instances)
- delete i;
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();
- 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)
- 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();
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
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
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:
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:
- 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>
-void InstanceArray::Instance<T>::set_matrix(const Matrix &m)
+inline void InstanceArray<T>::Instance::set_matrix(const Matrix &m)
{
T::set_matrix(m);
- array.update_instance_matrix(index);
+ array.update_instance_matrix(index, *this->get_matrix());
}
} // namespace GL
projects / libs / gl.git / commitdiff