CODEWITHSUNDEEP
algorithm3dgeometry
Cahit Burak Küçüksütcü
Cahit Burak Küçüksütcü

Reputation: 587

Separating Mesh

I've a problem with separating meshes. There is a combined mesh which has 1 vertex buffer and 1 index buffer for triangles. But the mesh has 2 seperated objects at least. For example there are 2 quads with no vertex shared (and with no index shared of course) and their geometry is in 1 single mesh (1 vertex buffer, 1 index buffer). So how can I create 2 meshes from them. Is there any algorithm for that.

I've tried to add first vertex in a new mesh then look for index which points this vertex, then I add this index and its related 2 indices (and vertices) of triangle to new mesh but indices must be changed.

I am sorry for missing info about my question. I ment seperating logicaly. For example in programming. If one single mesh in below has unshared submeshes like in the picture. I want it seperated in to 2 mesh classes. I want an algorithm a mathematical solution for that, not a tool doing this for me.

Mesh partitioning

Upvotes: 1

Views: 964

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32597

Firstly, initialize a union-find data structure with the number of vertices. Then find all connected components as follows:

for each triangle index i1, i2, i3 in indices
    union-find.union(i1, i2)
    union-find.union(i1, i3)

Then initialize an empty map (or dictionary) that will map old vertex indices to new ones:

Dictionary<int, int> indexMap;

Furthermore, we will need new lists for vertices:

Dictionary<int, List<Vertex>> vertices;
Dictionary<int, List<int>> indices;

Then distribute the vertices to the correct lists as follows:

for i from 0 to vertex count -1
    componentRepresentative := union-find.find(i)
    if(!vertices.ContainsKey(componentRepresentative))
        vertices.Add(new List<Vertex>());
        indices.Add(new List<int>());
    var list = vertices[componentRepresentative];
    list.Add(vertexBuffer[i]);
    indexMap.Add(i, list.Count - 1)

At this point we have separated the vertex buffers. We still need to separate the index buffers similarly.

for i from 0 to index count - 1
    componentRepresentative := union-find.find(indexbuffer[i])
    var list = indices[componentRepresentative]
    list.Add(indexMap[indexBuffer[i]])

Overall time complexity is nearly O(n) (for an ideal union-find structure).

Upvotes: 2

Related Questions