What is the data structure of an unstructured mesh?
 

I am a beginner in CFD. I am not very familiar with the data structure of unstructured meshes. Suppose I have two modules now, one is a mesh generation program and the other is a solver. What is the protocol between these two modules? Or: how is the data generated by the mesh generation program organized? Or: As a programmer who only develops the solver, what kind of data structure should I assume exists?

If the answer is very long, could you please recommend some related materials, such as books, web links, or video tutorials? If the answer is not too long, could you explain the data structure for 2D triangular unstructured mesh or 3D tetrahedral unstructured mesh? Thank you very much.

---------

After reading a response, I realized that the data structure is not all fixed. I guessed it would be like that. Actually, I don't really want to know the data structure down to the level of arrays or linked lists. I want to understand to what extent, for example, we need a data structure that allows us to input the index of a control volume to obtain the index of all vertices, and then obtain the coordinates from the index of the vertices; we need a data structure that allows us to input the index of a control volume to obtain the index of surrounding neighboring control volumes; perhaps we need to classify each control volume? Distinguish between boundary and non-boundary control volumes?

The specific implementation of the data structure can vary, but perhaps this kind of "black box", which can obtain some other information given some information such as the index of a control volume or the index of a face, is similar. Generally speaking, how many of these "black boxes" do we need to meet our needs for writing a solver? and what is the input and output of the "black boxes". i just want to get a general description of this.

it all depends on the solver you are writing. so it is very personal. I have three multiphsics softwares and two of them use the data structure where control volumes are stored as list of faces and then left cell and right cell. When i write it for GPU i use a structure that tells me for each cell the faces it is made up of.

So it is all not fixed.

Generally, you can think of something that for a single index k produces the x(k),y(k),z(k) position. But for unstructured grids you need of the infos to reconstruct the topology, that is how you can reconstruct the elements, the connections, that is the index k communicating with other nodes and so on.


I suggest to see the manual of Tecplot do read the data structures that are needed for the unstructured grid, it is useful to understand.

Thank you, I have a vague understanding of this from your answer. The key is that we need to be able to access information about vertices, faces, and index of neighboring control volumes based on the index of the control volume.

By the way, you said you only need to know about the left and right cells, so are your two solvers 1D?

A single face is logically the boundary between two cells. Left/Right just refers to a convention used for the cell on one side versus the cell on the other side. The same left/right logic is used on 3D grids. Sometimes you see it referred to as the +/- side of a face. More bookkeeping convention, a face has two area normals, one pointing to the left cell and another normal facing to the right cell. I.e. A sort of inward vector and outward vector.

got it, simple interpolation is using value of the left cell and the right cell even in 3D, but the stencil could be larger

The key to understand in a FV code on unstructured grid is that you need to process first all the faces, not the node.

For example, a face numbered k has the infos to give you the index of the left and the index of the right nodes. From each of them you get the connection to other nodes required for the computation of the fluxes.
Clearly, you have a mark to know if the face is on the boundary.


Computed the fluxes for all the faces you just process the node to compute the average value by summing the faces of the FV.

Yes, it would be very convenient if I had a pointer from the face to the index of the two control volumes. Previously, I only thought about needing a data structure to obtain vertices and faces from the index of a control volume. However, if we also have the opposite information flow, that is, from the face to the control volume, then we have all the information.

For completely general unstructured grids, a typical grid file will have:

face -> left/right cells (grouped by boundaries and interior zones)

face -> face nodes

Everything else can be built from them, so it's not saved on file.

The solver needs the first for the fluxes/bc and the latter to build face normals.

If you actually need a dedicated data structure for cell -> faces (or even cell -> neighbor cells) is possibly a matter of performances, as it is heavy on memory. Some algorithms do need it, but sometimes they can be rewritten using the base data structures

Here is a possible procedure for how to generate a standard (face-based) mesh for an unstructured cell centered fvm. With face based, I mean that the cells are accessed through the faces, which is sufficient for most operations needed by a solver (as opposed to accessing neigboring cells or faces via each cell).

To construct the grid used by the solver you would start with a native mesh generated by a meshing software. This mesh need to contain nodes and connectivities of all the elements of the mesh. It also need to store the surface elements of each boundary patch. This mesh will be structured the same way as a finite element mesh. If you create a solver, you will typically read in this native mesh from a file.

Here is an example of such a mesh file for a 2D triangular mesh with two elements (ignoring the boundaries):

nodes:
x0 y0
x1 y1
x2 y2
x3 y3

connectivities:
0 1 2
2 3 1

The second step is to construct the grid (face-based structure) used by the solver. For a cell centered grid, each element of the native mesh will become a fv cell and each face shared by two elements will become a fv face.
I am not aware of references that explains the algorithms to do this step, but I guess this might be one of those problems it's possible to solve on your own, I know I did.

As already explained in other comments, each face will have an owner and a neighbour cell, and a face vector (a normal vector with length equal to the face area), pointing from the owner cell to the neighbour cell.

A possible finished face-based grid data structure could look like this:

Containers storing cell based quantities such as the solution, residual, etc would follow the same access pattern as the cell volumes.

Here are two examples of how the data structures could be used by the solver.
The first is computation of the flux balance for a first order scheme, in this case access happens via the faces:
The second is how the solution could be updated using explicit euler. Now the access happens over the cells:
Note that how to handle the boundaries has to be decided, you can select to either use ghost cells, or compute the boundary fluxes directly. Note that the above structure would be applicable for a ghost cell implementation (the ghost cells would be contained in list_of_indices_of_neighbour_cells, and all area normal vectors would be pointing out of the domain at the boundary), I'm not entirely sure how exactly the boundaries are handled if the face fluxes are specified directly.

You can take a look at the book "Computational Fluid Dynamics:
Principles and Applications" (free pdf of older book can be found online).
The chapter "Spatial Discretization -> Unstructured Finite Volume Schemes -> General Discretisation Methodologies" explains some of this, and there are also many other useful chapters covering this topic.

As a matter of fact, going from a textbook to a practical implementation requires some effort and additional thinking/testing or, however, a certain experience.

For example, never have face cell neighbors in two separate arrays. The two neighbors are almost always needed together, and you are putting some stress on the cache if not doing this. Just use a 2xNfaces (In Fortran) or an Nfacesx2 array (C/C++).

A similar thinking could go into other face based data. In certain cases it might actually have sense to lay them down into a struct or derived data type (say face neighbors AND area vector AND whatever you might need in the face loop). BUT, you must be careful on any possible padding by the compiler, that could cause a much larger memory consumption.

As another example, consider how Fluent meshes are written to file (n nodes and m faces):

nodes:
x0 y0 z0
x1 y1 z1
.
xn yn zn

faces:
n0 i0_0 i0_1 i0_2 ... i0_n0 cL_0 cR_0
n1 i1_0 i1_1 i1_2 ... i1_n1 cL_1 cR_1
.
nm im_0 im_1 im_2 ... im_nm cL_m cR_m

The important thing here is that you don't need to build your main face->cells data structure as it is already on file (cL and cR at the end of each face line). This is especially important for mesh partitioning on solver startup, because that is what is needed by, say, METIS.

Thank you very much, your answer is very informative. You made me realize that there is a process in actual computation where the results from general mesh generation software are transformed into data structures needed by solvers, which I was not aware of before. I also didn't know what the results from mesh generation software were, but through your answer, I now understand a simple concrete example: nodes+connectivities are indeed enough information (ignoring boundaries). (However, this is indeed too simple, and it would be great if mesh generation software could output more efficient information for solvers although contains some redundancy)

In the end, you also showed how this data structure is used in the solver, which closed the loop on this question. Thank you very much. By the way, I am currently reading the book you recommended, and I really like it. It provides a very general framework of almost all existing algorithm.

Thank you very much. You are discussing more details now, including some cautions about cache access efficiency and storage waste. Your example of Fluent increased my understanding.

I didn’t consider the argument about memory access, to thanks for pointing that out. I’m no expert on padding when using structs, but I guess you would be fine if you for instance only put types of 4 or 8 bytes in the struct(?) In C/C++ I guess you could test this by verifying that sizeof(MyStruct) == sizeof(sum of all individual datatypes in MyStruct)

When it comes to the second point about how to build the face structure from the native mesh, I am quite sure that this structure is not stored by all mesh formats (su2 format is one example, this format only store a finite element type mesh). I have also looked into METIS and it seems that you can partititon the mesh without having the face structure (the latter being a graph type data structure), but use the function METIS_PartMeshDual to partition a native mesh for a FV code. I guess you could then construct a face structure for each partitioned domain. Not sure if this is the usual way it’s done or if it’s more common to partition the mesh on the face/graph structure directly. I’m looking into this since I would like to implement it myself.

Absolutely, I understand your question better now. In the context of Computational Fluid Dynamics (CFD), the interaction between the mesh generation program and the solver involves a high-level understanding of how data is organized.

For learning more about this topic, you can look into books like:

"Computational Fluid Dynamics: Principles and Applications" by Jiri Blazek
"An Introduction to Computational Fluid Dynamics: The Finite Volume Method" by H.K. Versteeg and W. Malalasekera
Online resources like:

CFD Online (https://www.cfd-online.com/)
YouTube tutorials by organizations like LearnCAx, Prof. John Anderson, and more.
Remember that practical experience with a simple CFD code will often teach you more than theory alone.


If you need developer visit IT Staff Augmentation Services

Thanks for your recommendations