How to generate a face list from vertices?

Question

I have a little background in writing toy finite volume CFD codes. In 2D Cartesian scenarios, I typically take $x_{\min}$, $x_{\max}$, $y_{\min}$, $y_{\max}$, and the number of points in $x$ and $y$ to calculate $\Delta x$ and $\Delta y$. Then, I compute cell centers and assemble a 1D array of cells. To perform field operations, I loop over this array of cells, storing items at node centers and interpolating to faces as necessary.

In researching more advanced projects, I see that a face-based data structure is advantageous in terms of conservation, flexibility, and application of boundary conditions.

My question: For a Cartesian 2D domain, how does one generate a list of faces from arrays of vertex coordinates? These faces should compose quadrilateral cells. Can this be done explicitly?

Obviously, I could create an extremely simple 2D Cartesian mesh in something like Gmsh, but then I'd have to read in a mesh and parse the file. I can write this functionality eventually, but for my own edification, I want to quickly explore a face-based code.

Answer 1

As with many questions in computation, a lot of this comes down to what you are trying to achieve. For structured meshes on quadrilaterals, the best and most efficient way to deal with this is not to bother and work implicitly, as you've (kind of suggested). If your cell centred variable has index pair (i,j), then you can label faces to the left/right (depending on your numbering and boundary conditions) as (i,j) and faces up/down as (i,j) and keep the two lists separate. If you are working on what is sometimes known as the Arakawa C grid, then this also gives you the indices for your U and V variables respectively.

This becomes a little bit more interesting when your mesh is truly unstructured. In that case, it's likely that you are building your entire topology from a set of mappings from an element/cell index onto the vertex indices. Indeed this is what a meshing program such as GMSH fundamentally gives you. For a structured mesh, you could cheat if necessary by e.g. numbering both cells and vertices outwards in a spiral. A fairly simple algorithm to get face neighbour pairs is then something like:

1. Build a mapping $K$ from vertices/nodes to cells/elements, by sweeping through your cell list once.
2. For cell $m$, work around the edges in order.
3. For each edge, identify both vertices, $p_1$ and $p_2$.
4. For each cell in $K$ that $p_1$ belongs to, check if $p_2$ also belongs to it. The first one you find which isn't $m$ is the neighbour . If $m$<$n$, then this is the first time you've found that face.

To repeat though, this is overkill for structured meshes.