CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home > Forums > General Forums > Main CFD Forum

What is the data structure of an unstructured mesh?

Register Blogs Members List Search Today's Posts Mark Forums Read

Like Tree10Likes
  • 1 Post By FMDenaro
  • 1 Post By LuckyTran
  • 2 Post By FMDenaro
  • 1 Post By sbaffini
  • 2 Post By ander
  • 3 Post By sbaffini

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
Old   July 15, 2023, 23:54
Question What is the data structure of an unstructured mesh?
  #1
New Member
 
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2
Aerterliusi is on a distinguished road
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.

Last edited by Aerterliusi; July 16, 2023 at 08:59. Reason: make question more accurate
Aerterliusi is offline   Reply With Quote

Old   July 16, 2023, 05:03
Default
  #2
Senior Member
 
Arjun
Join Date: Mar 2009
Location: Nurenberg, Germany
Posts: 1,274
Rep Power: 34
arjun will become famous soon enougharjun will become famous soon enough
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.
arjun is offline   Reply With Quote

Old   July 16, 2023, 06:28
Default
  #3
Senior Member
 
Filippo Maria Denaro
Join Date: Jul 2010
Posts: 6,781
Rep Power: 71
FMDenaro has a spectacular aura aboutFMDenaro has a spectacular aura aboutFMDenaro has a spectacular aura about
Quote:
Originally Posted by Aerterliusi View Post
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.



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.
Aerterliusi likes this.
FMDenaro is offline   Reply With Quote

Old   July 16, 2023, 08:38
Default
  #4
New Member
 
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2
Aerterliusi is on a distinguished road
Quote:
Originally Posted by arjun View Post
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.
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?
Aerterliusi is offline   Reply With Quote

Old   July 16, 2023, 14:59
Default
  #5
Senior Member
 
Lucky
Join Date: Apr 2011
Location: Orlando, FL USA
Posts: 5,678
Rep Power: 66
LuckyTran has a spectacular aura aboutLuckyTran has a spectacular aura aboutLuckyTran has a spectacular aura about
Quote:
Originally Posted by Aerterliusi View Post
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.
arjun likes this.
LuckyTran is offline   Reply With Quote

Old   July 16, 2023, 15:49
Default
  #6
New Member
 
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2
Aerterliusi is on a distinguished road
Quote:
Originally Posted by LuckyTran View Post
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
Aerterliusi is offline   Reply With Quote

Old   July 16, 2023, 15:59
Default
  #7
Senior Member
 
Filippo Maria Denaro
Join Date: Jul 2010
Posts: 6,781
Rep Power: 71
FMDenaro has a spectacular aura aboutFMDenaro has a spectacular aura aboutFMDenaro has a spectacular aura about
Quote:
Originally Posted by Aerterliusi View Post
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.
arjun and Aerterliusi like this.
FMDenaro is offline   Reply With Quote

Old   July 16, 2023, 16:06
Default
  #8
New Member
 
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2
Aerterliusi is on a distinguished road
Quote:
Originally Posted by FMDenaro View Post
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.
Aerterliusi is offline   Reply With Quote

Old   July 17, 2023, 03:16
Default
  #9
Senior Member
 
sbaffini's Avatar
 
Paolo Lampitella
Join Date: Mar 2009
Location: Italy
Posts: 2,154
Blog Entries: 29
Rep Power: 39
sbaffini will become famous soon enoughsbaffini will become famous soon enough
Send a message via Skype™ to sbaffini
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
Aerterliusi likes this.
sbaffini is offline   Reply With Quote

Old   July 18, 2023, 10:10
Default
  #10
Member
 
Anders Aamodt Resell
Join Date: Dec 2021
Location: Oslo, Norway
Posts: 64
Rep Power: 4
ander is on a distinguished road
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:

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
}
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:
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
The second is how the solution could be updated using explicit euler. Now the access happens over the cells:
Code:
for i = 1:N_CELLS
    U[i] += dt / list_of_cell_volumes[i] * R[i]
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.
FMDenaro and Aerterliusi like this.
ander is offline   Reply With Quote

Old   July 18, 2023, 11:17
Default
  #11
Senior Member
 
sbaffini's Avatar
 
Paolo Lampitella
Join Date: Mar 2009
Location: Italy
Posts: 2,154
Blog Entries: 29
Rep Power: 39
sbaffini will become famous soon enoughsbaffini will become famous soon enough
Send a message via Skype™ to sbaffini
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.
FMDenaro, ander and Aerterliusi like this.
sbaffini is offline   Reply With Quote

Old   July 18, 2023, 17:13
Default
  #12
New Member
 
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2
Aerterliusi is on a distinguished road
Quote:
Originally Posted by ander View Post
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:

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
}
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:
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
The second is how the solution could be updated using explicit euler. Now the access happens over the cells:
Code:
for i = 1:N_CELLS
    U[i] += dt / list_of_cell_volumes[i] * R[i]
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.
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.
Aerterliusi is offline   Reply With Quote

Old   July 18, 2023, 17:23
Default
  #13
New Member
 
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2
Aerterliusi is on a distinguished road
Quote:
Originally Posted by sbaffini View Post
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. You are discussing more details now, including some cautions about cache access efficiency and storage waste. Your example of Fluent increased my understanding.
Aerterliusi is offline   Reply With Quote

Old   July 20, 2023, 09:09
Default
  #14
Member
 
Anders Aamodt Resell
Join Date: Dec 2021
Location: Oslo, Norway
Posts: 64
Rep Power: 4
ander is on a distinguished road
Quote:
Originally Posted by sbaffini View Post
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.
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.
ander is offline   Reply With Quote

Old   August 3, 2023, 05:32
Default
  #15
New Member
 
sruthi825
Join Date: Aug 2023
Posts: 1
Rep Power: 0
sruthi825 is on a distinguished road
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
sruthi825 is offline   Reply With Quote

Old   August 3, 2023, 07:59
Default
  #16
New Member
 
Aster
Join Date: Jun 2023
Posts: 17
Rep Power: 2
Aerterliusi is on a distinguished road
Quote:
Originally Posted by sruthi825 View Post
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
Aerterliusi is offline   Reply With Quote

Reply

Tags
grid, mesh

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are On


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


All times are GMT -4. The time now is 07:51.