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

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

What is the algorithm to write the simple code?

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

Thank you very much Mr Jarmo Monttinen.

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

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

Markus:

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

MG

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.

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

Ananda:

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

MG

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!

TRADOS 6.5.5 Freelance Edition

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