From b0b9732359d43325c8bd820abeb8417353365a0c Mon Sep 17 00:00:00 2001 From: x2048 Date: Sat, 2 Apr 2022 10:42:27 +0200 Subject: Add depth sorting for node faces (#11696) Use BSP tree to order transparent triangles https://en.wikipedia.org/wiki/Binary_space_partitioning --- src/client/mapblock_mesh.cpp | 257 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 255 insertions(+), 2 deletions(-) (limited to 'src/client/mapblock_mesh.cpp') diff --git a/src/client/mapblock_mesh.cpp b/src/client/mapblock_mesh.cpp index 03522eca9..8c7d66186 100644 --- a/src/client/mapblock_mesh.cpp +++ b/src/client/mapblock_mesh.cpp @@ -30,6 +30,7 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "client/meshgen/collector.h" #include "client/renderingengine.h" #include +#include /* MeshMakeData @@ -1003,6 +1004,173 @@ static void applyTileColor(PreMeshBuffer &pmb) } } +/* + MapBlockBspTree +*/ + +void MapBlockBspTree::buildTree(const std::vector *triangles) +{ + this->triangles = triangles; + + nodes.clear(); + + // assert that triangle index can fit into s32 + assert(triangles->size() <= 0x7FFFFFFFL); + std::vector indexes; + indexes.reserve(triangles->size()); + for (u32 i = 0; i < triangles->size(); i++) + indexes.push_back(i); + + root = buildTree(v3f(1, 0, 0), v3f(85, 85, 85), 40, indexes, 0); +} + +/** + * @brief Find a candidate plane to split a set of triangles in two + * + * The candidate plane is represented by one of the triangles from the set. + * + * @param list Vector of indexes of the triangles in the set + * @param triangles Vector of all triangles in the BSP tree + * @return Address of the triangle that represents the proposed split plane + */ +static const MeshTriangle *findSplitCandidate(const std::vector &list, const std::vector &triangles) +{ + // find the center of the cluster. + v3f center(0, 0, 0); + size_t n = list.size(); + for (s32 i : list) { + center += triangles[i].centroid / n; + } + + // find the triangle with the largest area and closest to the center + const MeshTriangle *candidate_triangle = &triangles[list[0]]; + const MeshTriangle *ith_triangle; + for (s32 i : list) { + ith_triangle = &triangles[i]; + if (ith_triangle->areaSQ > candidate_triangle->areaSQ || + (ith_triangle->areaSQ == candidate_triangle->areaSQ && + ith_triangle->centroid.getDistanceFromSQ(center) < candidate_triangle->centroid.getDistanceFromSQ(center))) { + candidate_triangle = ith_triangle; + } + } + return candidate_triangle; +} + +s32 MapBlockBspTree::buildTree(v3f normal, v3f origin, float delta, const std::vector &list, u32 depth) +{ + // if the list is empty, don't bother + if (list.empty()) + return -1; + + // if there is only one triangle, or the delta is insanely small, this is a leaf node + if (list.size() == 1 || delta < 0.01) { + nodes.emplace_back(normal, origin, list, -1, -1); + return nodes.size() - 1; + } + + std::vector front_list; + std::vector back_list; + std::vector node_list; + + // split the list + for (s32 i : list) { + const MeshTriangle &triangle = (*triangles)[i]; + float factor = normal.dotProduct(triangle.centroid - origin); + if (factor == 0) + node_list.push_back(i); + else if (factor > 0) + front_list.push_back(i); + else + back_list.push_back(i); + } + + // define the new split-plane + v3f candidate_normal(normal.Z, normal.X, normal.Y); + float candidate_delta = delta; + if (depth % 3 == 2) + candidate_delta /= 2; + + s32 front_index = -1; + s32 back_index = -1; + + if (!front_list.empty()) { + v3f next_normal = candidate_normal; + v3f next_origin = origin + delta * normal; + float next_delta = candidate_delta; + if (next_delta < 10) { + const MeshTriangle *candidate = findSplitCandidate(front_list, *triangles); + next_normal = candidate->getNormal(); + next_origin = candidate->centroid; + } + front_index = buildTree(next_normal, next_origin, next_delta, front_list, depth + 1); + + // if there are no other triangles, don't create a new node + if (back_list.empty() && node_list.empty()) + return front_index; + } + + if (!back_list.empty()) { + v3f next_normal = candidate_normal; + v3f next_origin = origin - delta * normal; + float next_delta = candidate_delta; + if (next_delta < 10) { + const MeshTriangle *candidate = findSplitCandidate(back_list, *triangles); + next_normal = candidate->getNormal(); + next_origin = candidate->centroid; + } + + back_index = buildTree(next_normal, next_origin, next_delta, back_list, depth + 1); + + // if there are no other triangles, don't create a new node + if (front_list.empty() && node_list.empty()) + return back_index; + } + + nodes.emplace_back(normal, origin, node_list, front_index, back_index); + + return nodes.size() - 1; +} + +void MapBlockBspTree::traverse(s32 node, v3f viewpoint, std::vector &output) const +{ + if (node < 0) return; // recursion break; + + const TreeNode &n = nodes[node]; + float factor = n.normal.dotProduct(viewpoint - n.origin); + + if (factor > 0) + traverse(n.back_ref, viewpoint, output); + else + traverse(n.front_ref, viewpoint, output); + + if (factor != 0) + for (s32 i : n.triangle_refs) + output.push_back(i); + + if (factor > 0) + traverse(n.front_ref, viewpoint, output); + else + traverse(n.back_ref, viewpoint, output); +} + + + +/* + PartialMeshBuffer +*/ + +void PartialMeshBuffer::beforeDraw() const +{ + // Patch the indexes in the mesh buffer before draw + + m_buffer->Indices.clear(); + if (!m_vertex_indexes.empty()) { + for (auto index : m_vertex_indexes) + m_buffer->Indices.push_back(index); + } + m_buffer->setDirty(scene::EBT_INDEX); +} + /* MapBlockMesh */ @@ -1173,8 +1341,31 @@ MapBlockMesh::MapBlockMesh(MeshMakeData *data, v3s16 camera_offset): scene::SMeshBuffer *buf = new scene::SMeshBuffer(); buf->Material = material; - buf->append(&p.vertices[0], p.vertices.size(), - &p.indices[0], p.indices.size()); + switch (p.layer.material_type) { + // list of transparent materials taken from tile.h + case TILE_MATERIAL_ALPHA: + case TILE_MATERIAL_LIQUID_TRANSPARENT: + case TILE_MATERIAL_WAVING_LIQUID_TRANSPARENT: + { + buf->append(&p.vertices[0], p.vertices.size(), + &p.indices[0], 0); + + MeshTriangle t; + t.buffer = buf; + for (u32 i = 0; i < p.indices.size(); i += 3) { + t.p1 = p.indices[i]; + t.p2 = p.indices[i + 1]; + t.p3 = p.indices[i + 2]; + t.updateAttributes(); + m_transparent_triangles.push_back(t); + } + } + break; + default: + buf->append(&p.vertices[0], p.vertices.size(), + &p.indices[0], p.indices.size()); + break; + } mesh->addMeshBuffer(buf); buf->drop(); } @@ -1187,6 +1378,7 @@ MapBlockMesh::MapBlockMesh(MeshMakeData *data, v3s16 camera_offset): } //std::cout<<"added "< triangle_refs; + m_bsp_tree.traverse(rel_camera_pos, triangle_refs); + + // arrange index sequences into partial buffers + m_transparent_buffers.clear(); + + scene::SMeshBuffer *current_buffer = nullptr; + std::vector current_strain; + for (auto i : triangle_refs) { + const auto &t = m_transparent_triangles[i]; + if (current_buffer != t.buffer) { + if (current_buffer) { + m_transparent_buffers.emplace_back(current_buffer, current_strain); + current_strain.clear(); + } + current_buffer = t.buffer; + } + current_strain.push_back(t.p1); + current_strain.push_back(t.p2); + current_strain.push_back(t.p3); + } + + if (!current_strain.empty()) + m_transparent_buffers.emplace_back(current_buffer, current_strain); +} + +void MapBlockMesh::consolidateTransparentBuffers() +{ + m_transparent_buffers.clear(); + + scene::SMeshBuffer *current_buffer = nullptr; + std::vector current_strain; + + // use the fact that m_transparent_triangles is already arranged by buffer + for (const auto &t : m_transparent_triangles) { + if (current_buffer != t.buffer) { + if (current_buffer != nullptr) { + this->m_transparent_buffers.emplace_back(current_buffer, current_strain); + current_strain.clear(); + } + current_buffer = t.buffer; + } + current_strain.push_back(t.p1); + current_strain.push_back(t.p2); + current_strain.push_back(t.p3); + } + + if (!current_strain.empty()) { + this->m_transparent_buffers.emplace_back(current_buffer, current_strain); + } +} + video::SColor encode_light(u16 light, u8 emissive_light) { // Get components -- cgit v1.2.3