Meshlets Merging and Simplification.

[icarolelis1]

Since the meshopt_meshlet is purely indexing structs for outputing meshlet_triangles and vertices. I would like to know how could I merge two meshlets and then simplify their geometry. Could anyone please explain that process to me, I'm having a hard time dealing with the indirection of all indexes to properly achieve that. This is What I tried so far.

//Merge the geomtry of the two neighbor clusters

             Cluster father;
             Cluster children1               = active_clusters[neighbor_of_i];
             Cluster children2               = active_clusters[i];
             father.meshlet.triangle_offset  = min(children1.meshlet.triangle_offset,children2.meshlet.triangle_offset);
             father.meshlet.vertex_offset    = min(children1.meshlet.vertex_offset,children2.meshlet.vertex_offset);
             father.meshlet.vertex_count     = children1.meshlet.vertex_count + children2.meshlet.vertex_count;
             father.meshlet.triangle_count   = children1.meshlet.triangle_count + children2.meshlet.triangle_count;
             father.aabb                     = compute_cluster_aabb(vertices,father.meshlet);//Compute AABB  

             //Get slice of the buffers
             auto vertex_offset = father.meshlet.vertex_offset;
             auto vertex_count  = father.meshlet.vertex_count;
             auto index_offset  = father.meshlet.triangle_offset;
             auto index_count   = father.meshlet.triangle_count;

             std::vector<Vertex>   positions(vertices.begin() + vertex_offset , vertices.begin() + vertex_offset + vertex_count);
             std::vector<uint32_t> indices (g_indices.begin() + index_offset, g_indices.begin() + index_offset + index_count);

             //Check if Merged cluster needs to split
             if(father.meshlet.triangle_count > MAX_TRIANGLES)
             {
                 Logger::Info("Merged Cluster has more than %d triangles",MAX_TRIANGLES);
                 //Split the merged cluster into two new cluster...
                 // ... 
             }

             //Simplify cluster father by .50 factor;
             size_t nextIndicesTarget = size_t(double(indices.size()) * 0.50);
             size_t indicesCount = indices.size();

             while(indices.size() % 3 !=0)
                 indices.push_back(indices[indices.size()-1]);

             //Simplify the geomtry formed by the merged cluster
             size_t simplified_indices_count = meshopt_simplify(
                                                                 indices.data(),
                                                                 indices.data(),
                                                                 indices.size(),
                                                                 &positions[0].position.x,
                                                                 positions.size(),
                                                                 sizeof(Vertex),
                                                                 nextIndicesTarget,
                                                                 1e-4f);

[zeux]

The way I would approach this I think is I would create a small fictional vertex buffer & index buffer that has a fairly small number of vertices and triangles and is indexed locally. It's possible to only work with indices but meshopt_simplify cost scales linearly with total number of vertices, not just number of vertices referred by the index buffer, so splitting a large mesh into 10K clusters and then simplifying the union of just 2-3 can be much more expensive than it should be otherwise.

Sketch (not tested or compiled) below. I would also recommend using more than two source meshlets as that provides the maximum amount of freedom for the simplifier. Also you'd want to use meshopt_SimplifyLockBorder flag to ensure that the resulting set of triangles doesn't have gaps with independently simplified groups of neighboring clusters.

struct ClusterVertex { vec3 position; unsigned int index; }; // index = original index in the original vertex buffer

// assumed state:
// unsigned int* meshlet_vertices - aggregate array of vertex indices for meshlet data
// unsigned char* meshlet_triangles - aggregate array of triangle indices for meshlets
// Vertex* vertices - actual vertex buffer that meshlet_vertices[] refers to

// temporary; indices refer to position within local_vertices
std::vector<ClusterVertex> local_vertices;
std::vector<unsigned int> local_indices;

// local_vertices & local_indices can be reserved to the full size with an extra loop

// merge meshlets into a big mesh, with local_indices referring to local_vertices; local_vertices tracks original vertex buffer index
for (meshopt_Meshlet m : children)
{
    size_t local_offset = local_vertices.size();

    for (unsigned int v = 0; v < m.vertex_count; ++v)
    {
        unsigned int global_index = meshlet_vertices[m.vertex_offset + v];
        local_vertices.push_back(ClusterVertex { vertices[global_index].position, global_index });
    }

    for (unsigned int t = 0; t < m.triangle_count; ++t)
    {
        local_indices.push_back(local_offset + meshlet_triangles[m.triangle_offset + t * 0]);
        local_indices.push_back(local_offset + meshlet_triangles[m.triangle_offset + t * 1]);
        local_indices.push_back(local_offset + meshlet_triangles[m.triangle_offset + t * 2]);
    }
}

// simplify the resulting small mesh (0.5 factor)
int target_index_count = int((local_indices.size() / 3) * 0.5) * 3;

local_indices.resize(meshopt_simplify(&local_indices[0], &local_indices[0], local_indices.size(), &local_vertices[0].position.x, local_vertices.size(), sizeof(ClusterVertex), target_index_count, 1e-2f, meshopt_SimplifyLockBorder));

// construct a index buffer that refers to the original (global / per-mesh) vertex array
std::vector<unsigned int> global_indices;
global_indices.reserve(local_indices.size());

for (size_t i = 0; i < local_indices.size(); ++i)
    global_indices.push_back(local_vertices[local_indices[i]].index);

// now you have a real small index buffer (global_indices) that represents the simplification of a union of the input meshets, and you can split it into meshlets again by calling meshopt_buildMeshlets again.

[gents83]

After some iterations it seems that once grouping meshlets it's "sort of mandatory" to remap and optimize the new grouped mesh, otherwise the simplify seems to not be able to reduce it.
Here you can find a result example (adding the "optimization pass" before simplyfing):

PS: It's just a test trying to group together meshlets with common edges, then simplyfing and re-dividing in meshlets. Better adjacency and grouping algorithm should be implemented on my side before then using the generated DAG for Nanite-style stuff

[zeux]

Right - you can't split the vertices on the border in the sense that the simplifier needs to get the same index for them after merging the meshlets. The code above doesn't take this into account, so yeah it's not correct. What should happen is that if global_index is the same for two vertices, they get the same local index as well :(

I'm now thinking that it would be nice if meshopt_simplify could just be called with the references into the original vertex buffer. This requires a separate flag, eg meshopt_simplifySparseInput, because the simplifier will need to perform some remapping internally for this to be efficient. I'm not sure how feasible this is but I've added this to my TODO list to investigate.

[zeux]

Just to circle back on this, this discussion / advise is now irrelevant :) latest changes introduce a new flag, meshopt_SimplifySparse, which makes "splitting a large mesh into 10K clusters and then simplifying the union of just 2-3 can be much more expensive than it should be otherwise" irrelevant. The flag changes the meaning of the error parameter so it's often useful to combine it with meshopt_SimplifyErrorAbsolute. A new demo snippet in demo/main.cpp, simplifyClusters, demonstrates the usage.

With that it should be possible to operate directly on the mesh subsets using global indices (that point to the original vertex buffer).

[gents83]

Hey @zeux thanks a lot for your work, I've had a chance to try your latest changes and they work amazingly ❤️

I've a question related to texture UV and seams.

What would be the best strategy to have consistency and avoid artifacts on those across clusters and LOD levels in your opinion?

[zeux]

If you mean cluster seams, then I think this should be independent of UV; either specifying SimplifyLockBorder or using (new as of 0.21) vertex_locks input to meshopt_simplifyWithAttributes (which you can call with 0 attributes if necessary) should work to guarantee seamless LOD. Of course you need to do the whole Nanite hierarchical dance carefully to ensure that a cluster group gets transitioned simultaneously.

Wrt UV seams and UV quality in general, it's a somewhat complicated topic, but this is not cluster related. In general, UV seams should be handled automatically - however, there are cases with UV mirroring (#718) where this is not done, and textures along different borders of a seam may not align exactly if the UV edge has a different length in UV space on both sides. Additionally, it may be worth trying to pass UV as attributes to the simplifier with some weight, although note that this is an area of active work (tracked in #158) and there's some limitations that exist right now that may not make it optimal. Overall I would expect work to happen on all of this in the coming months.