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

Neighboring cells in TETRA_4 unstructured grids

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

Reply
 
LinkBack Thread Tools Display Modes
Old   August 14, 2004, 05:59
Default Neighboring cells in TETRA_4 unstructured grids
  #1
Amaresh Dalal
Guest
 
Posts: n/a
Hi All,

We are obtaining tetrahedron unstructured grids from a gridgeneration software and we are using the grid data in CGNS format to solve the NS equations by the finite volume method.

In our solver, we need to know the neighboring elements sharing each face. For example, a tetrahedron element has four neighbors. CGNS does not give this information. Then how do we obtain the neighboring element sharing the face in an efficient way?

Any help will be much appreciated.

Thanking you,

Amaresh Dalal
  Reply With Quote

Old   August 16, 2004, 13:46
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #2
Jarmo Monttinen
Guest
 
Posts: n/a
Definitely not efficient.. but you can write a rather simple code that will create the required data-structure from the existing ones. Worked well for me.

-- Jarmo
  Reply With Quote

Old   August 16, 2004, 15:03
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #3
Amaresh Dalal
Guest
 
Posts: n/a
What is the algorithm to write the simple code?
  Reply With Quote

Old   August 16, 2004, 15:12
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #4
Jarmo Monttinen
Guest
 
Posts: n/a
It depends on what data structures you have originally.

I think mine was originally node-based and had to convert it into a segment-based format. So I simply looped over all nodes in the domain and found the cells on the two sides of each segment that connected to the node in question... then flagged the segments that were already used. Takes a while to convert it this way but was very easy to write and debug.. and you can just do this as an additional pre-processing step after you have the grid. Sorry I can't be more specific, I wrote this maybe 4 years ago in a similar situation so I don't remember the details.

-- Jarmo

  Reply With Quote

Old   August 16, 2004, 15:52
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #5
Amaresh Dalal
Guest
 
Posts: n/a
Thank you very much Mr Jarmo Monttinen.
  Reply With Quote

Old   August 17, 2004, 08:58
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #6
MG
Guest
 
Posts: n/a
Jarmo,

Your algorithm is quite straightforward, however, it's complexity is of order O(N^2), where N is the number of nodes. It's okay to use this very intuitive algorithm for relatively small N, but think about large N, say N close to a million, or even larger. That, I guess, where you start experiencing a problem.

I've never done (seen) any algorithm that is better than O(N^2). (Frankly, I have not done much work in this area of FV, FEM, but I believe this is a general problem of computational geometry and think many people might be interested in it). Somehow I think there should be an algorithm with the O(NlogN) complexity. The fast algorithm, with tree-like structure, and so on to permit a fast search over the set of nodes. Or, at least, I think it's doable. Have you ever come across this kind of algorithm? If you have, please share your experience here.

Thanks.

MG
  Reply With Quote

Old   August 17, 2004, 10:45
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #7
Markus Lummer
Guest
 
Posts: n/a
It is possible to calculate the bounding boxes for every tetra and sort them into an R-Tree. Then one can easily extract the indices of the neighboring tetras from the R-Tree and has to do the point search only on few tetras.

Regards, Markus
  Reply With Quote

Old   August 17, 2004, 12:02
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #8
MG
Guest
 
Posts: n/a
Markus:

Thank you. By any chance, have you seen any paper in refereed journals on this topic?

MG
  Reply With Quote

Old   August 17, 2004, 14:08
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #9
Ananda Himansu
Guest
 
Posts: n/a
Jarmo's O(NC^2) algorithm should serve Amaresh's immediate needs, unless the mesh is very large. It has the virtue of simplicity.

Some years ago, I implemented an O(NC*logNC) algorithm to calculate unstructured-mesh connectivity (sorry, but the source code does not belong to me). For simplicity, consider a mesh of only tetrahedra. You are given the map from cell-number C to the node-numbers N of the four vertices of each cell, as an array C2N(1:NC,1:4), where NC is the number of cells.

(a) Generate a list of every face of every cell (for a total of 4*NC faces), which is an O(NC) process. This can be done by scanning each cell in the given order, listing the four faces systematically (by listing the node numbers of the three vertices of each face) and storing the list in an array F2N(1:4*NC,1:4). The first three columns of this array, i.e. F2N(1:4*NC,1:3), contain the vertices of the faces. The fourth column, i.e. F2N(1:4*NC,4), contains the cell number that each face belongs to, so you remember where the face came from.

(b) Next, sort the vertices of each face such that the node numbers of each face are in ascending (or descending) order, which is an O(NC) process. Here, you actually move the vertices around in each row of the array F2N.

(c) Next, sort the faces themselves into lexicographic order, which is an O(NC*logNC) process. To do this, first of all, sort the faces using the third column of F2N, i.e. F2N(1:4*NC,3), as a key to be put into ascending (or descending, it does not matter, as long as you are consistent during all the following steps) order. Next, use a STABLE sorting algorithm to similarly sort the faces using as a key the second column of F2N, i.e. F2N(1:4*NC,2). Finally, use the stable sorting algorithm to sort the faces using the first column of F2N as a key. A stable sorting algorithm is defined as one that preserves the relative order of items with duplicate (equal) keys. For efficiency during this step, you should not actually move the faces around in the array F2N. Instead, use "rank" and "index" arrays (as described for example in Numerical Recipes in Fortran 2/e, Section 8.4) to keep track of the order of the faces. At the end of this step (c), the index array lists the faces in F2N in ascending order of their vertex with smallest node number, and within each sublist of identical smallest node number, the faces are in ascending order of second smallest node number, and within each subsublist of identical 2nd column key, the faces are in ascending order of largest node number.

(d) Now you can simply scan the F2N array in the order given by the index array, comparing each face with the previous one scanned. This takes 4*NC-1 face comparisons, or 12*NC-3 node comparisons, which is an O(NC) process. Every time you encounter duplicate faces, you have two cells which share a common face. The two cell numbers are in the fourth column of the two rows involved. In a well formed conforming mesh, each face can be shared by at most two cells, and no cell by itself has two or more identical faces. Any face which is not shared by two cells is a boundary face. When you encounter two identical faces, you store the two cell numbers in a connectivity data structure. You can also generate a face numbering at this time. You can use a face-to-cell array F2C(1:NF,1:2) or a neighboring cell array C2C(1:NC,1:4), depending on whether your flux balancing is face-based or cell-based.

I used some programming refinements to make the algorithm a little more efficient, but it remained an O(NC*logNC) algorithm. I would be interested to know of any faster algorithms for the job, perhaps the tree-based algorithms as speculated by MG and Markus? Judging by how fast Tecplot calculates the connectivity when you load a mesh of even a couple of million cells, I imagine that the commercial packages employ faster algorithms. Of course, for static meshes, the connectivity calculation is a tiny part of the flow computation, and is done only once, so an O(NC*logNC) algorithm is quite acceptable.
  Reply With Quote

Old   August 18, 2004, 12:39
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #10
Jarmo Monttinen
Guest
 
Posts: n/a
True, this is a very expensive way of re-ordering the mesh and if I were to write another grid generator or to improve the existing one, I would most likely create other data structures while generating the grid. This would make the task a bit less expensive.

But I chose to go with the O(N^2) method as my grids at the time were small enough for that to work. And a computer did the job faster that I would have been able to debug a fancier code.

-- Jarmo
  Reply With Quote

Old   August 19, 2004, 16:46
Default Re: Neighboring cells in TETRA_4 unstructured grid
  #11
MG
Guest
 
Posts: n/a
Ananda:

Thank you. This is quite interesting algorithm, could be very helpful in the future.

MG
  Reply With Quote

Old   August 19, 2004, 17:23
Default You are quite welcome
  #12
Ananda Himansu
Guest
 
Posts: n/a
MG, you are welcome. Looking back at my post, I see that I failed to mention that for step (c), it is important to use an efficient sorting algorithm that costs O(NC*logNC), such as heapsort or mergesort, and not more elementary and expensive algorithms such as bubble sort or insertion sort or selection sort. Otherwise, we would be back to an O(NC^2) algorithm!
  Reply With Quote

Old   September 19, 2004, 11:54
Default Re: You are quite welcome
  #13
sandra
Guest
 
Posts: n/a
TRADOS 6.5.5 Freelance Edition

Contact: sandra@sandra.cjb.net [FULL Version] [Downloadable] [Cracked]
  Reply With Quote

Reply

Thread Tools
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 On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
SnappyHexMesh for internal Flow vishwa OpenFOAM Native Meshers: snappyHexMesh and Others 23 August 6, 2014 03:50
Import netgen mesh to OpenFOAM hsieh Open Source Meshers: Gmsh, Netgen, CGNS, ... 32 September 13, 2011 05:50
snappyHexMesh won't work - zeros everywhere! sc298 OpenFOAM Native Meshers: snappyHexMesh and Others 2 March 27, 2011 21:11
snappyHexMesh aborting Tobi OpenFOAM Native Meshers: snappyHexMesh and Others 0 November 10, 2010 04:23
physical boundary error!! kris CD-adapco 2 August 3, 2005 00:32


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