OpenMesh: fast search of common neighbor vertices

Question

I have a function which finds the common neighbors of two vertices v1 and v2, i.e. those vertices that are connected to both v1 and v2:

std::vector<MyMesh::VertexHandle> find_common_neighbors(MyMesh & mesh, MyMesh::VertexHandle & v1, MyMesh::VertexHandle & v2){
    std::vector<MyMesh::VertexHandle> common_neighbors;

    //iterate over neighbors of v1
    for(MyMesh::VertexVertexIter it1 = mesh.vv_iter(v1); it1.is_valid(); ++it1) {
      //neighbors of v2
      for(MyMesh::VertexVertexIter it2 = mesh.vv_iter(v2); it2.is_valid(); ++it2) {
        if ((*it1)==(*it2)){
            common_neighbors.push_back(*it1);     
        }
      }
    }
    return common_neighbors;

The function simply iterates over the neighborhood of v1 and v2 and checks if finds any vertex that appears in both neighborhoods. Unfortunately, this function seems to be the bottleneck of my code, thus my question is whether there is a more optimal way to accomplish this in OpenMesh?

Answer 1

I'm not an expert on OpenMesh proper, but it looks like you are using a rather efficient Circulator to find these pairs of vertices.

The only obvious problem with your function is the fact you are allocating and returning the std::vector object.

The declaration

std::vector<MyMesh::VertexHandle> common_neighbors;

defines an empty vector (and subsequent push_backs internally call malloc which is unpredictably expensive). The least you can do here is preallocate the approximate expected amount of vertices.

If you are calling this function for a large (10000+ ?) number of distinct v1, v2 pairs, you should change the signature of your function to

std::vector<MyMesh::VertexHandle> find_common_neighbors(MyMesh & mesh,
               MyMesh::VertexHandle & v1, MyMesh::VertexHandle & v2,
               std::vector<MyMesh::VertexHandle>& common_neighbors);

and pass preallocated common_neighbors there.

You should probably also give more context (how do you call this function, what do you actually do with these vertices - e.g., if you need a v3 adjacent to both v1 and v2 and then make a triangular face (v1,v2,v3), then probably you should just take a v1-v2 edge and iterate over adjacent triangles...) so that more optimization can be provided.