
[Sponsors] 
What is the data structure of an unstructured mesh? 

LinkBack  Thread Tools  Search this Thread  Display Modes 
July 15, 2023, 23:54 
What is the data structure of an unstructured mesh?

#1 
New Member
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2 
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 nonboundary 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. Last edited by Aerterliusi; July 16, 2023 at 08:59. Reason: make question more accurate 

July 16, 2023, 05:03 

#2 
Senior Member
Arjun
Join Date: Mar 2009
Location: Nurenberg, Germany
Posts: 1,274
Rep Power: 34 
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. 

July 16, 2023, 06:28 

#3  
Senior Member
Filippo Maria Denaro
Join Date: Jul 2010
Posts: 6,781
Rep Power: 71 
Quote:
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. 

July 16, 2023, 08:38 

#4  
New Member
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2 
Quote:
By the way, you said you only need to know about the left and right cells, so are your two solvers 1D? 

July 16, 2023, 14:59 

#5 
Senior Member
Lucky
Join Date: Apr 2011
Location: Orlando, FL USA
Posts: 5,678
Rep Power: 66 
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.


July 16, 2023, 15:49 

#6  
New Member
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2 
Quote:


July 16, 2023, 15:59 

#7  
Senior Member
Filippo Maria Denaro
Join Date: Jul 2010
Posts: 6,781
Rep Power: 71 
Quote:
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. 

July 16, 2023, 16:06 

#8  
New Member
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2 
Quote:


July 17, 2023, 03:16 

#9 
Senior Member

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 

July 18, 2023, 10:10 

#10 
Member
Anders Aamodt Resell
Join Date: Dec 2021
Location: Oslo, Norway
Posts: 64
Rep Power: 4 
Here is a possible procedure for how to generate a standard (facebased) 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 (facebased 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 facebased grid data structure could look like this: Code:
Faces{ list_of_indices of_owner_cells (size = N_FACES) list_of_indices_of_neighbour_cells (size = N_FACES) list_of_face_vectors (size = N_FACES) } Cells{ list_of_cell_volumes (size = N_CELLS) //possibly other lists such as cell centers or vectors from cell centers //to face centers } 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: Code:
//U denotes a list of conservative variables //R denotes the residual (minus the sum of fluxes for each control volume). for face_index = 1:N_FACES i = list_of_indices of_owner_cells[face_index] j = list_of_indices of_neighbour_cells[face_index] S_ij = list_of_face_vectors[face_index] flux = compute_flux(U[i], U[j], S_ij) R[i] += flux R[j] = flux Code:
for i = 1:N_CELLS U[i] += dt / list_of_cell_volumes[i] * R[i] 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. 

July 18, 2023, 11:17 

#11 
Senior Member

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. 

July 18, 2023, 17:13 

#12  
New Member
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2 
Quote:
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. 

July 18, 2023, 17:23 

#13  
New Member
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2 
Quote:


July 20, 2023, 09:09 

#14  
Member
Anders Aamodt Resell
Join Date: Dec 2021
Location: Oslo, Norway
Posts: 64
Rep Power: 4 
Quote:
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. 

August 3, 2023, 05:32 

#15 
New Member
sruthi825
Join Date: Aug 2023
Posts: 1
Rep Power: 0 
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 highlevel 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.cfdonline.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 

August 3, 2023, 07:59 

#16  
New Member
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2 
Quote:


Tags 
grid, mesh 
Thread Tools  Search this Thread 
Display Modes  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
[Commercial meshers] Problem with Mesh conversion from FLUENT Meshing to OpenFOAM  mn17jyf  OpenFOAM Meshing & Mesh Conversion  3  November 1, 2023 09:49 
Bad elements after generating unstructured volume mesh  max_beetle  Pointwise & Gridgen  0  October 24, 2017 01:52 
[Commercial meshers] fluentMeshToFoam multidomain mesh conversion problem  Attesz  OpenFOAM Meshing & Mesh Conversion  12  May 2, 2013 10:52 
[ICEM] Just started unstructured mesh !  diamondx  ANSYS Meshing & Geometry  6  September 5, 2012 07:15 
Structure or unstructured mesh  Nikos  Siemens  2  November 9, 2006 18:35 