# How to efficiently get mesh cell/face connectivity?

If I have 3 lists: points, faces and cells that represents a mesh, where:

• points is a list of x,y,z coordinates, for example

 [-0.05, -0.05,  0.  ],
[-0.05,  0.05,  0.  ],
[ 0.05, -0.05,  0.  ],
...

• faces is a list of list of points, where each row is a list of point indices that represents a face

 [ 1,  4,  8,  7],
[ 7,  8,  6,  3],
[ 4,  0,  5,  8],
...

• cells is a list of list of points, where each row is a list of point indices that represents a cell

 [ 1,  7,  8,  4, 11, 16, 17, 10],
[ 7,  3,  6,  8, 16, 15, 14, 17],
[ 4,  8,  5,  0, 10, 17, 12,  9],
...


For each face, I need to get the two cells ids that are sharing the face (in case of boundary face, there is only one cell that owns that face).

For a small mesh, I can iterate over cells, and for each cell iterate over all faces and check if a face points are in current cell (two for loops and a face-cells map), which is of course awfully slow.

Is there a smarter way to efficiently get face connectivity of my mesh?

## 2 Answers

Assuming that you are working with cubic cells, you can create a vector called point2cell, such that point2cell[iPoint] gives you the indeces of the cells sharing the point iPoint. This can be done by looping over the cells vector. Take a look at the following pseudo-code:

for iCell = 1:nCell
for iPointLoc = 1:8
iPoint = cells[iCell][iPointLoc]
point2cell[iPoint].insert( iCell )


Next, you can loop over the faces, take one point, take all the cells sharing that point, and looking at the matching between a face and a cell:

for iFace = 1:nFace
for iPointLoc = 1:4
iPoint = faces[iFace][iPointLoc]
for iCellLoc = 1:8
iCell = point2Cell[iPoint][iCellLoc]
if( cells[iCell] matches faces[iFace])
face2cell[iFace].insert( iCell )


The first loop is linear in the number of cells while the second is linear in the number of faces.

I think you can achive order N performance if you sort the list of points, list of faces and list of cells in the same manner, i.e., if you sort row-column-layer by midpoints of your three entity types. If that is the case, you can approximate the offset that you will need to find your associated elements. Then you can iterate in your neighbourhood of the approximated offset to find what you need.

Example to clearify: Lets say you have a 2D grid with 9 quadrilaterals. You sort the 16 Points row-column wise, the faces also row-column-wise by their centers and finally the 9 cells row-column wise by their midpoints. If you then want to find the two neighbour cells for a face, you can calculate the offset efficiently. This should take you from Order $$O(N^2)$$ to $$O(N)$$.

This of course assumes structured grids.