Connected components based on vertices

[stla]

Hello,

Using boost/graph/connected_components.hpp, I'm able to compute the connected components of a mesh where each component is given by a set of vertices. This allows me to construct the mesh corresponding to each component and to get in this mesh the original properties of the splitted mesh, e.g. the normals, vertex colors, etc. I'm not able to do that with PMP because it computes the connected components given by sets of faces. So I think it would be nice to have the connected components given by sets of vertices in CGAL. But maybe you didn't implement that because of a potential issue?

[afabri]

It is not clear what you want to achieve. Given this mesh

what do you want in case

• a,b,d have id 0, and c has id1
• a,b have id 0, and c,d have id 1

Would it make sense to give a face the id of it's three vertices in case they have the same id. You then had faces with id and the faces at the transition between two CCs.

[stla]

For me there's only one connected component here. Two connected components must be separate. But you're right, there's a potential problem. It could happen that two connected components share a common vertex. So we would have to duplicate this vertex.

I think that Boost constructs the connected components from the edges.

Here is the code I use:

    Vertex_index_map vccmap = mesh.add_property_map<vertex_descriptor, std::size_t>("v:CC").first;
    const std::size_t ncc = connected_components(mesh, vccmap);
    std::vector<std::vector<EMesh3::Vertex_index>> components(ncc);
    for(EMesh3::Vertex_index v : mesh.vertices()) {
      std::size_t c = vccmap[v];
      components[c].push_back(v);
    }

Wondering what would happend if there's a common vertex... Will try later.

[afabri]

I think that Boost constructs the connected components from the edges.

The BGL has no notion of faces, that is there are just vertices and edges. When computing connected components of faces you can consider the faces as vertices, and there is an edge between two vertices if the faces share an edge. This is also called a dual graph

[MaelRL]

Wondering what would happend if there's a common vertex... Will try later.

What you see as two CCs will be part of the same, single CC. What defines separation between two sets of vertices?

I imagine this thread is related to #7148, but it's difficult to get a big picture that would allow understanding if you're trying to solve something that could have been dealt more easily upstream.

[stla]

Hmm I will take a look at the dual graph notion.

No, it's not related to #7148 With PMP::connected_components you can keep the face properties. I just wanted a way to keep the vertex properties, such as colors or normals. And my implementation looks successful so far.

[stla]

I think I was wrong: if we can retrieve the original face indices in the parent mesh, then we can retrieve the original vertex indices in the parent mesh. Indeed, take a vertex in a component. You can get its face. Then you can get the index of the corresponding face in the parent mesh. Then you can retrieve the corresponding vertex in the parent mesh by using the index of the vertex within the face.

[stla]

I'm not able to retrieve the vertex descriptor in the parent mesh. What's wrong in this code:

// input: cv is a vertex descriptor in the component mesh `cmesh`
face_descriptor cf = cmesh.face(cmesh.halfedge(cv)); // the face of cv in cmesh
face_descriptor pf = // my code to get the face in the parent mesh `mesh` - it works
int vi = CGAL::vertex_index_in_face(cv, cf, cmesh); 
halfedge_descriptor ph = mesh.halfedge(pf);
while(vi > 0) {
  ph = mesh.next(ph);
  vi--;
}
vertex_descriptor pv = mesh.source(ph); // should be the vertex descriptor in the 
                                         // parent mesh corresponding to `cv`

[stla]

I see: something has disturbed the order of the vertices within the faces. Don't know what yet.

[stla]

I found: I use copy_face_graph somewhere, and this disturbs the order of the vertices and my property maps. I have to use the optional parameter vertex_to_vertex_map to correct the property maps.

[stla]

Completely stupid. With Filtered_face_graph and copy_face_graph using vertex_to_vertex_map, it is straightforward to transfer the vertex properties of the parent mesh to a connected component. There's no need to retrieve the face indices of the component in the parent mesh, and no need to use the vertex indices within the faces.