From 274b6fb1b02692cc422bad9040d1abe5d545505a Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Thu, 17 Mar 2022 21:55:18 +0200 Subject: [PATCH] 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. --- source/render/instancearray.cpp | 142 ++++++++++++++++++++++++------- source/render/instancearray.h | 143 +++++++++++++++++++++++--------- 2 files changed, 218 insertions(+), 67 deletions(-) diff --git a/source/render/instancearray.cpp b/source/render/instancearray.cpp index a03fbf20..0a3d6b68 100644 --- a/source/render/instancearray.cpp +++ b/source/render/instancearray.cpp @@ -14,8 +14,10 @@ using namespace std; 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(4096U/instance_size, 8U)) { 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); } -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()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()get_size()>0 && instance_buffer->get_size()=b.begin && addrget_matrix(); + Slot &slot = slots[index]; + + --instance_count; + if(slot.array_index(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(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(); @@ -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); - mesh->draw_instanced(renderer, vtx_setup, instances.size()); + mesh->draw_instanced(renderer, vtx_setup, instance_count); } } // namespace GL diff --git a/source/render/instancearray.h b/source/render/instancearray.h index e6f8690c..f2a9b2c0 100644 --- a/source/render/instancearray.h +++ b/source/render/instancearray.h @@ -15,8 +15,96 @@ class Buffer; 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 storage; + std::vector slots; + std::vector 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 + T *create(A &); + + template + void destroy(T *); + + template + 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 +inline T *InstanceArrayBase::create(A &array) +{ + size_t index = allocate(); + return new(get_address(index)) T(object, array, index); +} + +template +inline void InstanceArrayBase::destroy(T *obj) +{ + char *addr = reinterpret_cast(obj); + obj->~T(); + release(find_index(addr)); +} + +template +inline void InstanceArrayBase::destroy_all() +{ + for(unsigned i=0; i(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 @@ -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. + +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 +class InstanceArray: public InstanceArrayBase { -public: - template +private: class Instance: public T { private: @@ -41,47 +137,20 @@ public: virtual void set_matrix(const Matrix &); }; -private: - const Object &object; - std::vector 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(); } - /** 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 - 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(*this); } + void remove(T &obj) { destroy(&obj); } }; -template -T &InstanceArray::append() -{ - Instance *inst = new Instance(object, *this, instances.size()); - append(inst); - return *inst; -} template -void InstanceArray::Instance::set_matrix(const Matrix &m) +inline void InstanceArray::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 -- 2.45.2