1 files changed, 121 insertions, 4 deletions

diff --git a/src/client/mapblock_mesh.h b/src/client/mapblock_mesh.h
index 3b17c4af9..169b3a8c1 100644
--- a/src/client/mapblock_mesh.h
+++ b/src/client/mapblock_mesh.h
@@ -71,6 +71,102 @@ struct MeshMakeData
 	void setSmoothLighting(bool smooth_lighting);
 };
 
+// represents a triangle as indexes into the vertex buffer in SMeshBuffer
+class MeshTriangle
+{
+public:
+	scene::SMeshBuffer *buffer;
+	u16 p1, p2, p3;
+	v3f centroid;
+	float areaSQ;
+
+	void updateAttributes()
+	{
+		v3f v1 = buffer->getPosition(p1);
+		v3f v2 = buffer->getPosition(p2);
+		v3f v3 = buffer->getPosition(p3);
+
+		centroid = (v1 + v2 + v3) / 3;
+		areaSQ = (v2-v1).crossProduct(v3-v1).getLengthSQ() / 4;
+	}
+
+	v3f getNormal() const {
+		v3f v1 = buffer->getPosition(p1);
+		v3f v2 = buffer->getPosition(p2);
+		v3f v3 = buffer->getPosition(p3);
+
+		return (v2-v1).crossProduct(v3-v1);
+	}
+};
+
+/**
+ * Implements a binary space partitioning tree 
+ * See also: https://en.wikipedia.org/wiki/Binary_space_partitioning
+ */
+class MapBlockBspTree
+{
+public:
+	MapBlockBspTree() {}
+
+	void buildTree(const std::vector<MeshTriangle> *triangles);
+
+	void traverse(v3f viewpoint, std::vector<s32> &output) const
+	{
+		traverse(root, viewpoint, output);
+	}
+
+private:
+	// Tree node definition;
+	struct TreeNode
+	{
+		v3f normal;
+		v3f origin;
+		std::vector<s32> triangle_refs;
+		s32 front_ref;
+		s32 back_ref;
+
+		TreeNode() = default;
+		TreeNode(v3f normal, v3f origin, const std::vector<s32> &triangle_refs, s32 front_ref, s32 back_ref) :
+				normal(normal), origin(origin), triangle_refs(triangle_refs), front_ref(front_ref), back_ref(back_ref)
+		{}
+	};
+
+
+	s32 buildTree(v3f normal, v3f origin, float delta, const std::vector<s32> &list, u32 depth);
+	void traverse(s32 node, v3f viewpoint, std::vector<s32> &output) const;
+
+	const std::vector<MeshTriangle> *triangles = nullptr; // this reference is managed externally
+	std::vector<TreeNode> nodes; // list of nodes
+	s32 root = -1; // index of the root node
+};
+
+/*
+ * PartialMeshBuffer
+ *
+ * Attach alternate `Indices` to an existing mesh buffer, to make it possible to use different
+ * indices with the same vertex buffer.
+ *
+ * Irrlicht does not currently support this: `CMeshBuffer` ties together a single vertex buffer
+ * and a single index buffer. There's no way to share these between mesh buffers.
+ *
+ */
+class PartialMeshBuffer
+{
+public:
+	PartialMeshBuffer(scene::SMeshBuffer *buffer, std::vector<u16> &&vertex_indexes) :
+			m_buffer(buffer), m_vertex_indexes(std::move(vertex_indexes))
+	{}
+
+	scene::IMeshBuffer *getBuffer() const { return m_buffer; }
+	const std::vector<u16> &getVertexIndexes() const { return m_vertex_indexes; }
+
+	void beforeDraw() const;
+	void afterDraw() const;
+private:
+	scene::SMeshBuffer *m_buffer;
+	mutable std::vector<u16> m_vertex_indexes;
+};
+
 /*
 	Holds a mesh for a mapblock.
 
@@ -125,7 +221,23 @@ public:
 			m_animation_force_timer--;
 	}
 
+	/// update transparent buffers to render towards the camera
+	void updateTransparentBuffers(v3f camera_pos, v3s16 block_pos);
+	void consolidateTransparentBuffers();
+
+	/// get the list of transparent buffers
+	const std::vector<PartialMeshBuffer> &getTransparentBuffers() const
+	{
+		return this->m_transparent_buffers;
+	}
+
 private:
+	struct AnimationInfo {
+		int frame; // last animation frame
+		int frame_offset;
+		TileLayer tile;
+	};
+
 	scene::IMesh *m_mesh[MAX_TILE_LAYERS];
 	MinimapMapblock *m_minimap_mapblock;
 	ITextureSource *m_tsrc;
@@ -144,12 +256,10 @@ private:
 	// Maps mesh and mesh buffer (i.e. material) indices to base texture names
 	std::map<std::pair<u8, u32>, std::string> m_crack_materials;
 
-	// Animation info: texture animationi
+	// Animation info: texture animation
 	// Maps mesh and mesh buffer indices to TileSpecs
 	// Keys are pairs of (mesh index, buffer index in the mesh)
-	std::map<std::pair<u8, u32>, TileLayer> m_animation_tiles;
-	std::map<std::pair<u8, u32>, int> m_animation_frames; // last animation frame
-	std::map<std::pair<u8, u32>, int> m_animation_frame_offsets;
+	std::map<std::pair<u8, u32>, AnimationInfo> m_animation_info;
 
 	// Animation info: day/night transitions
 	// Last daynight_ratio value passed to animate()
@@ -158,6 +268,13 @@ private:
 	// of sunlit vertices
 	// Keys are pairs of (mesh index, buffer index in the mesh)
 	std::map<std::pair<u8, u32>, std::map<u32, video::SColor > > m_daynight_diffs;
+
+	// list of all semitransparent triangles in the mapblock
+	std::vector<MeshTriangle> m_transparent_triangles;
+	// Binary Space Partitioning tree for the block
+	MapBlockBspTree m_bsp_tree;
+	// Ordered list of references to parts of transparent buffers to draw
+	std::vector<PartialMeshBuffer> m_transparent_buffers;
 };
 
 /*!