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.

  • 1
    $\begingroup$ Are you assuming your cells are quadrilaterals, or something more generic? $\endgroup$ – origimbo Jan 29 '19 at 13:59
  • $\begingroup$ @origimbo, Thanks for the reply. Yes--I'm thinking the cells should be quadrilaterals (just because that agrees with my rudimentary understanding at the moment). Thanks! $\endgroup$ – coffeecake Jan 29 '19 at 14:17
  • 1
    $\begingroup$ Do you have a routine that takes an index of a cell and gives you indicies of vertices belonging to this cell? $\endgroup$ – 56th Jan 30 '19 at 10:13
  • $\begingroup$ @56th, Thanks for the note. I don't currently, but I could add that fairly quickly. I see now that I could construct a list of four faces associated with each Cartesian cell based on the corner vertices. In my mind, I know which vertices should be connected, but is there an algorithm to determine this without a priori knowledge of the grid spacing? Also, What algorithm does one employ to remove duplicate faces? Thank you for your constructive help. $\endgroup$ – coffeecake Jan 30 '19 at 13:10
  • 1
    $\begingroup$ @coffeecake You can simply return vertices in e.g. counterclockwise order. In order to avoid duplicates, you may use an associative container based on a hash table (in C++ it would be std::unordered_set or std::unordered_map; using the unordered_map you can use indicies of vertices as a key and e.g. array of indicies of neighboring cells as a value if you need this info). Insertion of an element to these containers will cost you $O(1)$ on average which is optimal. $\endgroup$ – 56th Jan 30 '19 at 17:30

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.

| cite | improve this answer | |
  • $\begingroup$ My middle name is "overkill"! Thanks for the help. This is good stuff to get me started. $\endgroup$ – coffeecake Jan 30 '19 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.