From 274b6fb1b02692cc422bad9040d1abe5d545505a Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
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<size_t>(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()<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();
@@ -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<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
@@ -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<typename T = ObjectInstance>
+class InstanceArray: public InstanceArrayBase
 {
-public:
-	template<typename T>
+private:
 	class Instance: public T
 	{
 	private:
@@ -41,47 +137,20 @@ public:
 		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
-- 
2.45.2