Using two arrays to store undirected edges instead of a map

Alec Jacobson

November 07, 2014

weblog/

I profiled some of the libigl code the other day and found a performance leak corresponding to the way I sometimes dealt with undirected edges. In a triangle mesh, each oriented triangle has three directed edges. It's sometimes useful to find other triangles with the same edges. So if my first triangle has an edge {i,j} I may want to find all other triangles who have either also an edge {i,j} or have the reverse edge {j,i}. The slow way of storing such a relationship is with a std::map or std::unordered_map. For example you might write,

std::map<std::pair<int,int>,std::vector<int>> edge_to_faces;
for each face f in F
{
  for each edge {i,j} in F(f)
  {
    if(i<j)
    {
      edge_to_faces[make_pair<int,int>(i,j)].push_back(f);
    }else
    {
      edge_to_faces[make_pair<int,int>(j,i)].push_back(f);
    }
  }
}

You can do slightly better using an std::unordered_map (aka hash map) and writing a compress(i,j) function which maps your {i,j} or {j,i} pair to a single number.

Turns out it's much faster to build and to use two arrays. One which maps each directed edge instance to a unique undirected edge and then an array for the data stored at each undirected edge. Libigl provides a way of getting this first array via the igl::unique_edge_map function:

igl::unique_edge_map(F,E,uE,EMAP,uE2E);

Then the previous example looks like:

std::vector<int,std::vector<int>> uedge_to_faces;
for each face f in F
{
  for each cth edge {i,j} in F(f)
  {
    uedge_to_faces[EMAP(f+c*m)].push_back(f);
  }
}

Storing EMAP and uedge_to_faces is technically more memory than just edge_to_faces, but not asymptotically more if the data we're storing for each undirected is O(#F), as is the case here. I think this boils down to memory access. The maps access is scattered but the array is contiguous. The price to build EMAP is a sort: O(m log m), but it can be down in place once and for all, where as the map needs to maintain a sort while building and conduct O(log m) searches when accessing.