+// 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
+};
+
+class PartialMeshBuffer
+{
+public:
+ PartialMeshBuffer(scene::SMeshBuffer *buffer, const std::vector<u16> &vertex_indexes) :
+ m_buffer(buffer), m_vertex_indexes(vertex_indexes)
+ {}
+
+ scene::IMeshBuffer *getBuffer() const { return m_buffer; }
+ const std::vector<u16> &getVertexIndexes() const { return m_vertex_indexes; }
+
+ void beforeDraw() const;
+private:
+ scene::SMeshBuffer *m_buffer;
+ std::vector<u16> m_vertex_indexes;
+};
+