lexicographic ordering in 3D

[Juan Carlos Araujo Cabarcas]

Dear all,

I have been designing 2D grids according to the standards given in:
    https://www.dealii.org/8.4.1/doxygen/deal.II/structGeometryInfo.html

The procedure goes as follows,
1) we introduce a set of vertices as points (x_i,y_i), numbered by the index "i",
2) connect them forming quads/cells and store the numbering as: cell_nodes [k] = {i1,i2,i3,i4},
3) making sure that i1,i2,i3,i4 follow a lexicographic ordering explained in .../structGeometryInfo.html.

In 2D it is messy already to satisfy 1), 2), 3) for non-trivial/primitive meshes, but we always can sketch the situation, because it is 2D, and by rotating cells (ordering) we hope that eventually a solution will come out.

Now, the sketch part is not available in 3D and the number of permutations/rotations has increased dramatically. This leads me to the following question:

Is there a tool within deal.II to impose 3), when 1) and 2) are given?
In other words, is there any tool available, such that we get an array new_cell_nodes satisfying a lexicographic ordering, by inputting the arrays: vertex, cell_nodes?

Ideas on how to achieve this are greatly appreciated!

Thanks in advance,
Juan Carlos Araújo, Umeå Universitet

[Wolfgang Bangerth]

Juan Carlos,

> The procedure goes as follows,
> 1) we introduce a set of vertices as points (x_i,y_i), numbered by the
> index "i",
> 2) connect them forming quads/cells and store the numbering as:
> cell_nodes [k] = {i1,i2,i3,i4},
> 3) making sure that i1,i2,i3,i4 follow a lexicographic ordering
> explained in .../structGeometryInfo.html.
>
> In 2D it is messy already to satisfy 1), 2), 3) for
> non-trivial/primitive meshes, but we always can sketch the situation,
> because it is 2D, and by rotating cells (ordering) we hope that
> eventually a solution will come out.
>
> Now, the sketch part is not available in 3D and the number of
> permutations/rotations has increased dramatically. This leads me to the
> following question:
>
> Is there a tool within deal.II to impose 3), when 1) and 2) are given?
> In other words, is there any tool available, such that we get an array
> new_cell_nodes satisfying a lexicographic ordering, by inputting the
> arrays: vertex, cell_nodes?

In 2d, it would in principle be possible to write such code that, given
an unordered set of vertices brings them into an order so that they form
a lexicographic ordering. That's because -- at least for convex
quadrilaterals -- you can find the centroid of the vertices, sort them
in counter-clockwise sense, and then swap the last two.

But that can't work in 3d. Think, for example, of the vertices of a
cube. Number them as you usually would, and you'd get a cube -- a valid
geometry. But then rotate the top surface by 90 degrees: the (unsorted
set of) vertices are in the exact same location, but the geometry you
want to describe (a "twisted" cube) is a different, though equally
valid, one. In other words, you can't infer the geometry someone has in
mind just from knowing where the vertices are. Consequently, it is not
possible to write a code that can always get that right.


The only thing we can do for you is to avoid having to deal with the
tedium of orienting cells relative to each other. This is what the
GridReordering class does for you.

Best
W.

--
------------------------------------------------------------------------
Wolfgang Bangerth email: bang...@colostate.edu
www: http://www.math.colostate.edu/~bangerth/

[Juan Carlos Araujo Cabarcas]

Thanks for your quick and useful answer, and explanation ... GridReordering was what I needed!
Now I see that I did not mean lexicographic order, that I had assumed from the begining in 2), but it didn't read like that in the email.
I apologize for the wrong formulation of the question.

Some constructive criticism though ... In the documentation of GridReordering,
https://www.dealii.org/8.4.0/doxygen/deal.II/classGridReordering.html

The statement: ... "Hence, for creating a Triangulation based on the resulting CellData the Triangulation::create_triangulation_compatibility() (and not the Triangulation::create_triangulation()) function must be used."

should be stated more times and in places where it would be easier to reach, like in the description of GridReordering::reorder_cells() in the Member Function Documentation, or/and in the exceptions of Triangulation::create_triangulation().  It took me a while to realize that it had to be done!