17.2 Theory

17.2.1 Mesh Hierarchy

The most fundamental thing we need to understand is how meshes are stored. The hierarchy of components that form a mesh is given in fig. 17.1


MCEFENN.E.F.E.C.eoladoo..d..a..l..o..smecgddgcemhpmeeeeeempoe111222eosnnsittit12tee12

Figure 17.1


Meshes have a dimensionality of their own (eg. for a surface mesh expDim = 2, for a volume mesh expDim = 3), and exist in n-dimensional physical space (physDim, where physDimexpDim). Composites are collections of elements. For elements which have the same dimensionality as the physical space they are in, they are grouped by their type. Note: boundary tri and quad elements are all grouped into a singular composite. Boundary element are elements that form the boundary of a mesh area/volume. These are one dimension lower than the physical dimension (eg. in 3D space, mesh volumes have boundary surfaces).

17.2.2 Vertex node ordering rules

Collapsed points

NekMesh supports quadrilateral (quad) and triangular (tri) 2D elements, and tetrahedral (tet), prism, pyramid (pyra) and hexahedral (hex) 3D element. Elements with tri faces (all except quads and hexes) use a collapsed coordinate systems (fig. 17.1b) [2], a feature which introduces constraints when assembling and connecting 3D elements.

In the code, we indicate which node in a tri face is the collapsed point by giving it the highest node id (in InputCGNS.cpp and InputStar.cpp the node ordering is done in the function ResetNodes). Note that the relative ordering between nodes in different faces (even if in the same element) has no affect.


ξξ012312

(a) Coordinate system for the reference quadrilateral.

ξξ01212

(b) Collapsed coordinate system for the reference triangle. Node 2 is considered the ’collapsed point’.
Figure 17.2 Coordinate systems for 2D elements/faces.


Tri interface rule

This rule simply states that when tri faces on two elements meet, the collapsed point must be the same for each tri (fig. 17.3).


(a) Valid element: neighbouring tri faces are alligned

(b) Invalid element: neighbouring tri faces are misalligned
Figure 17.3 Tri interface rule


Prism rule

For prism elements, the collapsed point on both the tri faces must correspond (ie. there must be an edge joining them) (fig. 17.4). Combining this with rule 1., we see that in a prism line (line of prisms joined by their tri faces), they all must be oriented in the same way.


(a) Valid element: two tri faces are alligned

(b) Invalid element: two tri faces are misalligned
Figure 17.4 Prism rule


Pyramid rule

In a pyramid element, the collapsed point on all four tri faces must be at the apex of the pyramid (fig. 17.5).


(a) Valid element: collapsed points at the apex for all tri faces

(b) Invalid element: collapsed points not at the apex for all tri faces
Figure 17.5 Pyramid rule


Tet and Hex elements

Tet and hex elements 17.6 are more flexible in their orientation due to their symmetry (and lack of tri faces in the case of hexes), so don’t introduce any additional rules.


(a)

(b)
Figure 17.6 Hex and tet elements...


Impossible meshes

When we combine the three rules simultaniously, there are a few mesh cases which are impossible to mesh 17.7, but it is considered the responsibility of the mesh generator to avoid these. Therefore NekMesh deals with meshes that are possible and are likely to be produced my a CFD mesh generator.



Figure 17.7


Since pyramid elements are the cause of these impossible meshes, one method used to rectify problematic pyramids is to use pyramid shielding (fig. 17.8). The idea is to replace any problematic pyramid with a smaller pyramid, plus four tets shielding the triangular pyramid faces from any neighbouring pyramid or prism elements. This decouples the pyramid’s apex from neighbouring elements, due to the aforementioned flexibility of tets.


(a) Before

(b) After
Figure 17.8 Before and after of the process of pyramid shielding. The pyra no longer restricts the orientation of neighbouring elements, so the impossible cases are avoided.


Implementation

Assuming we are given a valid mesh, we now need an algorithm (see alg. 1) to order the nodes to define the orientation of the elements in accordance with the three rules. In InputCGNS.cpp and InputStar.cpp, this is implemented as the function ResetNodes.


nodeID ← 0 ;  /* stores the lowest available ID revNodeID ← numNodes -1 ;  /* stores the highest available ID /* assign the apex node as the collapsed point and set the orientation of any prism lines that are connected to a pyramid tri face foreach pyramid : pyramids do /* give the apex node the highest available ID apex node ← revNodeID; revNodeID ← revNodeID - 1; foreach tri : pyramid tri faces do if tri is shared with another pyramid then assert: other pyramid shares the same apex node; end else if tri is shared with a prism then define the prism line; /* traverse the prism line, recursively assigning the highest available ID to the corresponding node end else /* it is either shared with a tet or ends in free space continue; end end end /* set the orientation of the remaining prisms foreach prism : prisms do if any nodes have ID then /* this prism has already been dealt with continue; end create a list of the prisms in the prism line; define the prism line; end /* give the remaining nodes an ID (low to high) foreach node : nodes do if node has ID then continue; end /* Give node the lowest available ID node ← nodeID; nodeID ← nodeID + 1; end Algorithm 1: Setting ordering of node IDs in mesh


Let’s work through a simple example implementation. Say we are given the test mesh in fig 17.9; it contains 6 elements (2 pyras and 4 prisms) and 14 nodes. We must assign each of the nodes a unique ID (0-13), compatible with the three rules.

  1. Label the apex of the first pyra (0) with the highest available ID (13).

  2. Pyra 0 shares a tri face with prism 2, so we must ID the corresponding node (12) on the opposite face of prism 2.

  3. We move to the next pyra (1) and assert that of all the ID’d nodes, the apex has the highest ID (true, since only the apex has been ID’d).

  4. With the pyramids correctly oriented, we move to the untouched prisms (3, 4, 5), which all form a prism line. We arbitrarily assign the line of nodes labelled 11-8-5-2 as the line of collapsed points and ensure that the points along this line have the highest ID on their respective tri faces.

  5. We have now labelled all the nodes, but if any were yet unlabelled, we would give them the remaining IDs (from low to high).


111769410318520123453201

Figure 17.9 Node ordering determined by ResetNodesalgorithm. Element IDs (already given): blue, node IDs: red.


17.2.3 Higher-order node ordering rules

As well as the order of the global node IDs, we also need to take care with the ordering of higher order nodes when creating elements, since the NekMesh convention is different from other formats (namely .gmsh and .cgns). Shown in figure 17.10, we can see that the method for ordering quad and tri nodes is the same: primary nodes (in black) are always included (clockwise), followed by mid-edge nodes (in red) for all higher order elements (also clockwise). Mid-face nodes (in blue) are optional, but if included they are next (ordered row-by-row).


0123

(a) Orientation of quad face is indicated by the arrow (0 → 1 → 2 → 3). This is same representation will be used for 3D elements.

0123456789111111111122222012345678901234

(b) Node ordering given for a 4th order quad element with mid-edge and mid-face nodes.

012

(c) Orientation of tri face is indicated by the arrow (0 → 1 → 2 → 3).

01234567891111101234

(d) Node ordering given for a 4th order tri element with mid-edge and mid-face nodes.
Figure 17.10 Node ordering rules for higher order quad and tri elements


Using the edge and face definitions in fig 17.11, we can derive the node ordering for higher order 3D elements too. As in the 2D case, it is a concatenation of the vertices, then all the mid-edge nodes, then all the mid-face nodes (if included) then all the mid-volume nodes (if included).


02123013450123

(a) High-order tet

60123402314578012345

(b) High-order prism

237012340145601234

(c) High-order pyra

2370123450145689110123456701

(d) High-order hex
Figure 17.11 Node ordering rules for higher order 3D elements elements


Mid-volume nodes are ordered in a similar fashion to mid-face nodes. They are given slice-by-slice, parallel to and moving away from face 0, and with the orientation dictated by face 0. This is most easily seen in the example given in fig. 17.12. For pyra and prisms, the slices are still quads, but with the size of/number of nodes in each slice decreasing away from face 0. For tets, the slices are triangular and with decreasing size.


0399111111111111111111111111101245678900000000001111111111222220123456789012345678901234

Figure 17.12 Volume node ordering for a 4th order hex element