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
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 physDim
≥
expDim
). 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).
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.
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).
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.
In a pyramid element, the collapsed point on all four tri faces must be at the apex of the pyramid (fig. 17.5).
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.
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.
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.
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
.
/*
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.
Label the apex of the first pyra (0) with the highest available ID (13).
Pyra 0 shares a tri face with prism 2, so we must ID the corresponding node (12) on the opposite face of prism 2.
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).
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.
We have now labelled all the nodes, but if any were yet unlabelled, we would give them the remaining IDs (from low to high).
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).
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).
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.