43 changes: 28 additions & 15 deletions src/client/clientmap.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -56,6 +56,7 @@ struct MeshBufListList

class Client;
class ITextureSource;
class PartialMeshBuffer;

/*
ClientMap
Expand Down Expand Up @@ -85,21 +86,7 @@ class ClientMap : public Map, public scene::ISceneNode
ISceneNode::drop();
}

void updateCamera(const v3f &pos, const v3f &dir, f32 fov, const v3s16 &offset)
{
v3s16 previous_block = getContainerPos(floatToInt(m_camera_position, BS) + m_camera_offset, MAP_BLOCKSIZE);

m_camera_position = pos;
m_camera_direction = dir;
m_camera_fov = fov;
m_camera_offset = offset;

v3s16 current_block = getContainerPos(floatToInt(m_camera_position, BS) + m_camera_offset, MAP_BLOCKSIZE);

// reorder the blocks when camera crosses block boundary
if (previous_block != current_block)
m_needs_update_drawlist = true;
}
void updateCamera(v3f pos, v3f dir, f32 fov, v3s16 offset);

/*
Forcefully get a sector from somewhere
Expand Down Expand Up @@ -150,6 +137,10 @@ class ClientMap : public Map, public scene::ISceneNode
f32 getCameraFov() const { return m_camera_fov; }

private:

// update the vertex order in transparent mesh buffers
void updateTransparentMeshBuffers();

// Orders blocks by distance to the camera
class MapBlockComparer
{
Expand All @@ -167,6 +158,26 @@ class ClientMap : public Map, public scene::ISceneNode
v3s16 m_camera_block;
};


// reference to a mesh buffer used when rendering the map.
struct DrawDescriptor {
v3s16 m_pos;
union {
scene::IMeshBuffer *m_buffer;
const PartialMeshBuffer *m_partial_buffer;
};
bool m_reuse_material:1;
bool m_use_partial_buffer:1;

DrawDescriptor(v3s16 pos, scene::IMeshBuffer *buffer, bool reuse_material) :
m_pos(pos), m_buffer(buffer), m_reuse_material(reuse_material), m_use_partial_buffer(false)
{}

DrawDescriptor(v3s16 pos, const PartialMeshBuffer *buffer) :
m_pos(pos), m_partial_buffer(buffer), m_reuse_material(false), m_use_partial_buffer(true)
{}
};

Client *m_client;
RenderingEngine *m_rendering_engine;

Expand All @@ -179,6 +190,7 @@ class ClientMap : public Map, public scene::ISceneNode
v3f m_camera_direction = v3f(0,0,1);
f32 m_camera_fov = M_PI;
v3s16 m_camera_offset;
bool m_needs_update_transparent_meshes = true;

std::map<v3s16, MapBlock*, MapBlockComparer> m_drawlist;
std::map<v3s16, MapBlock*> m_drawlist_shadow;
Expand All @@ -190,4 +202,5 @@ class ClientMap : public Map, public scene::ISceneNode
bool m_cache_bilinear_filter;
bool m_cache_anistropic_filter;
bool m_added_to_shadow_renderer{false};
u16 m_cache_transparency_sorting_distance;
};
57 changes: 55 additions & 2 deletions src/client/content_mapblock.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -381,12 +381,12 @@ void MapblockMeshGenerator::drawAutoLightedCuboid(aabb3f box, const f32 *txc,
box.MinEdge *= f->visual_scale;
box.MaxEdge *= f->visual_scale;
}
box.MinEdge += origin;
box.MaxEdge += origin;
if (!txc) {
generateCuboidTextureCoords(box, texture_coord_buf);
txc = texture_coord_buf;
}
box.MinEdge += origin;
box.MaxEdge += origin;
if (!tiles) {
tiles = &tile;
tile_count = 1;
Expand Down Expand Up @@ -1377,6 +1377,59 @@ void MapblockMeshGenerator::drawNodeboxNode()

std::vector<aabb3f> boxes;
n.getNodeBoxes(nodedef, &boxes, neighbors_set);

bool isTransparent = false;

for (const TileSpec &tile : tiles) {
if (tile.layers[0].isTransparent()) {
isTransparent = true;
break;
}
}

if (isTransparent) {
std::vector<float> sections;
// Preallocate 8 default splits + Min&Max for each nodebox
sections.reserve(8 + 2 * boxes.size());

for (int axis = 0; axis < 3; axis++) {
// identify sections

if (axis == 0) {
// Default split at node bounds, up to 3 nodes in each direction
for (float s = -3.5f * BS; s < 4.0f * BS; s += 1.0f * BS)
sections.push_back(s);
}
else {
// Avoid readding the same 8 default splits for Y and Z
sections.resize(8);
}

// Add edges of existing node boxes, rounded to 1E-3
for (size_t i = 0; i < boxes.size(); i++) {
sections.push_back(std::floor(boxes[i].MinEdge[axis] * 1E3) * 1E-3);
sections.push_back(std::floor(boxes[i].MaxEdge[axis] * 1E3) * 1E-3);
}

// split the boxes at recorded sections
// limit splits to avoid runaway crash if inner loop adds infinite splits
// due to e.g. precision problems.
// 100 is just an arbitrary, reasonably high number.
for (size_t i = 0; i < boxes.size() && i < 100; i++) {
aabb3f *box = &boxes[i];
for (float section : sections) {
if (box->MinEdge[axis] < section && box->MaxEdge[axis] > section) {
aabb3f copy(*box);
copy.MinEdge[axis] = section;
box->MaxEdge[axis] = section;
boxes.push_back(copy);
box = &boxes[i]; // find new address of the box in case of reallocation
}
}
}
}
}

for (auto &box : boxes)
drawAutoLightedCuboid(box, nullptr, tiles, 6);
}
Expand Down
257 changes: 255 additions & 2 deletions src/client/mapblock_mesh.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -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 <array>
#include <algorithm>

/*
MeshMakeData
Expand Down Expand Up @@ -1003,6 +1004,173 @@ static void applyTileColor(PreMeshBuffer &pmb)
}
}

/*
MapBlockBspTree
*/

void MapBlockBspTree::buildTree(const std::vector<MeshTriangle> *triangles)
{
this->triangles = triangles;

nodes.clear();

// assert that triangle index can fit into s32
assert(triangles->size() <= 0x7FFFFFFFL);
std::vector<s32> 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<s32> &list, const std::vector<MeshTriangle> &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<s32> &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<s32> front_list;
std::vector<s32> back_list;
std::vector<s32> 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<s32> &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
*/
Expand Down Expand Up @@ -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();
}
Expand All @@ -1187,6 +1378,7 @@ MapBlockMesh::MapBlockMesh(MeshMakeData *data, v3s16 camera_offset):
}

//std::cout<<"added "<<fastfaces.getSize()<<" faces."<<std::endl;
m_bsp_tree.buildTree(&m_transparent_triangles);

// Check if animation is required for this mesh
m_has_animation =
Expand Down Expand Up @@ -1298,6 +1490,67 @@ bool MapBlockMesh::animate(bool faraway, float time, int crack,
return true;
}

void MapBlockMesh::updateTransparentBuffers(v3f camera_pos, v3s16 block_pos)
{
// nothing to do if the entire block is opaque
if (m_transparent_triangles.empty())
return;

v3f block_posf = intToFloat(block_pos * MAP_BLOCKSIZE, BS);
v3f rel_camera_pos = camera_pos - block_posf;

std::vector<s32> 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<u16> 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<u16> 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
Expand Down
101 changes: 101 additions & 0 deletions src/client/mapblock_mesh.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -71,6 +71,91 @@ 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
};

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;
};

/*
Holds a mesh for a mapblock.
Expand Down Expand Up @@ -125,6 +210,15 @@ class MapBlockMesh
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:
scene::IMesh *m_mesh[MAX_TILE_LAYERS];
MinimapMapblock *m_minimap_mapblock;
Expand Down Expand Up @@ -158,6 +252,13 @@ class MapBlockMesh
// 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;
};

/*!
Expand Down
15 changes: 14 additions & 1 deletion src/client/tile.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -260,6 +260,18 @@ struct TileLayer
&& (material_flags & MATERIAL_FLAG_TILEABLE_VERTICAL);
}

bool isTransparent() const
{
switch (material_type) {
case TILE_MATERIAL_BASIC:
case TILE_MATERIAL_ALPHA:
case TILE_MATERIAL_LIQUID_TRANSPARENT:
case TILE_MATERIAL_WAVING_LIQUID_TRANSPARENT:
return true;
}
return false;
}

// Ordered for size, please do not reorder

video::ITexture *texture = nullptr;
Expand Down Expand Up @@ -308,7 +320,8 @@ struct TileSpec
for (int layer = 0; layer < MAX_TILE_LAYERS; layer++) {
if (layers[layer] != other.layers[layer])
return false;
if (!layers[layer].isTileable())
// Only non-transparent tiles can be merged into fast faces
if (layers[layer].isTransparent() || !layers[layer].isTileable())
return false;
}
return rotation == 0
Expand Down
1 change: 1 addition & 0 deletions src/defaultsettings.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -244,6 +244,7 @@ void set_default_settings()
settings->setDefault("enable_particles", "true");
settings->setDefault("arm_inertia", "true");
settings->setDefault("show_nametag_backgrounds", "true");
settings->setDefault("transparency_sorting_distance", "16");

settings->setDefault("enable_minimap", "true");
settings->setDefault("minimap_shape_round", "true");
Expand Down